机器学习-KMeans

一、 K-均值聚类算法

聚类是一种无监督学习，它将相似的对象归到同一个簇中。簇内对象越相似，聚类效果越好。K-Means算法就是其中的一种聚类算法。其实现代码如下：

#1.KMeans均值聚类算法
#2.伪代码
"""
       创建k个点作为起始质心（随机选择）
       当任意一个点的簇分配结果发生改变时
           对数据中的每个数据点
               对每个质心
                   计算质心与数据点之间的距离
                将数据点分配到距其最近的簇
            对每一个簇，计算簇中所有点的均值并将均值作为质心
"""
def KMeans(dataSet,k,distMeas=disEclud,createCent=randCent):
    """
    :param dataSet:      数据集
    :param k:            质心数目
    :param distMeas:     计算欧式距离函数
    :param createCent:   创建随机质心函数
    :return:
    """
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))          #创建矩阵来存储每个点的簇分配结果，第一列为簇的索引值，第二例为误差
    centroids=createCent(dataSet,k)
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(m):
            minDist=inf;
            minIndex=-1
            for j in range(k):
                disJI=distMeas(centroids[j,:],dataSet[i,:]) #寻找质心，通过对每个点遍历所有质心并计算点到每个质心的距离来完成
                if disJI<minDist:
                    minDist=disJI
                    minIndex=j
            if clusterAssment[i,0]!=minIndex:               #如果任一点的簇分配结果发生改变，则更新标志位
                clusterChanged=True
            clusterAssment[i,:]=minIndex,minDist**2
        print(centroids)

        for cent in range(k):                               #遍历所有质心，并更新他们的取值
            ptsInClus=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:]=mean(ptsInClus,axis=0)
    return centroids,clusterAssment
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

K-均值算法收敛但聚类效果较差的原因是：K-均值算法收敛到了局部最小，而非全局最小。

二、 二分K-均值聚类算法

为了克服K-均值算法收敛于局部最小，可以使用二分K-均值算法。该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中的一个簇继续进行划分，选择哪一簇划分取决于对其划分是否可以最大程度降低SSE(误差平方和)的值。上述过程基于SSE划分过程不断重复，直到得到用户指定的簇数目位置。实现代码如下：

#1.二分KMeans算法
#2.伪代码
"""
      将所有点看成一个簇
      当簇的数目小于k时
          对于每一个簇
              计算总误差
              在给定的簇上面进行KMeans聚类(k=2)
              计算将该簇一分为二之后的总误差
          选择使得误差最小的那个簇进行划分操作        
"""
def biKMeans(dataSet,k,distMeas=disEclud):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))             #创建矩阵用于保存分配结果以及平方误差
    centroid0=mean(dataSet,axis=0).tolist()[0]   #将所有点看成一个簇，求得其平均值的中心
    centList=[centroid0]                         #中心值列表，最开始只有一个簇，所以只有一个中心
    for j in range(m):
        clusterAssment[j,1]=distMeas(mat(centroid0),dataSet[j,:])**2  #求得一个簇时，循环求得所有点到中心点的误差，并放入矩阵中
    while(len(centList)<k):                      #判断是否分到想要的簇数
        lowestSSE=inf                            #初始最小误差平方和SSE为正无穷
        for i in range(len(centList)):           #循环每个簇
            ptsInCurrCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]  #分类结果等于i数据集的提取出来
            centroidMat,splitClustAss=KMeans(ptsInCurrCluster,2,distMeas)     #使用KMeans进行二分类
            sseSplit=sum(splitClustAss[:,1])                                  #分类之后的总误差
            sseNotSplit=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])#分类之前不等于i的分类结果的总误差
            print("sseSplit,and notSplit:",sseSplit,sseNotSplit)
            if(sseSplit+sseNotSplit)<lowestSSE:                               #分类之后的总误差+分类之前的总误差小于最小误差
                bestCentToSplit=i                                             #分类i
                bestNewCents=centroidMat                                      #新分类点的中心坐标
                bestClusAss=splitClustAss.copy()                              #分类之后的结果以及平方误差
                bestClustSSE=sseNotSplit+sseSplit                             #分类之后的平方误差

        #更新簇的分配结果
        bestClusAss[nonzero(bestClusAss[:,0].A==1)[0],0]=len(centList)
        bestClusAss[nonzero(bestClusAss[:,0].A==0)[0],0]=bestCentToSplit

        print("the bestCentToSplit is:",bestCentToSplit)
        print("the len of bestClustAss is :",len(bestClusAss))
        centList[bestCentToSplit]=bestNewCents[0,:]                           #将新分配的坐标中心替换
        centList.append(bestNewCents[1,:])                                    #将第二个坐标中心加入cenList中
        clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClusAss
    return  centList,clusterAssment
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

三、 完整的实现代码

"""
1.机器学习-KMeans
2.姓名：pcb
3.日期：2019.01.14
"""

from numpy import *
import matplotlib.pyplot as plt

#加载数据
def loadDataSet(filename):
    dataMat=[]
    fr=open(filename)
    for line in fr.readlines():
        curLine=line.strip().split('\t')
        #fltLine=map(float,currLine)
        fltLine = []
        for i in curLine:
            fltLine.append(float(i))
        dataMat.append(fltLine)
    return dataMat

#计算两个向量的欧式距离
def disEclud(vecA,vecB):
    return sqrt(sum(power(vecA-vecB,2)))

#给定数据集，构建一个包含k个随机质心的集合
def randCent(dataSet,k):
    n=shape(dataSet)[1]
    centroids=mat(zeros((k,n)))
    for j in range(n):
        minJ=min(dataSet[:,j])
        rangeJ=float(max(dataSet[:,j])-minJ)
        centroids[:,j]=minJ+rangeJ*random.rand(k,1)
    return centroids

#1.KMeans均值聚类算法
#2.伪代码
"""
       创建k个点作为起始质心（随机选择）
       当任意一个点的簇分配结果发生改变时
           对数据中的每个数据点
               对每个质心
                   计算质心与数据点之间的距离
                将数据点分配到距其最近的簇
            对每一个簇，计算簇中所有点的均值并将均值作为质心
"""
def KMeans(dataSet,k,distMeas=disEclud,createCent=randCent):
    """
    :param dataSet:      数据集
    :param k:            质心数目
    :param distMeas:     计算欧式距离函数
    :param createCent:   创建随机质心函数
    :return:
    """
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))          #创建矩阵来存储每个点的簇分配结果，第一列为簇的索引值，第二例为误差
    centroids=createCent(dataSet,k)
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(m):
            minDist=inf;
            minIndex=-1
            for j in range(k):
                disJI=distMeas(centroids[j,:],dataSet[i,:]) #寻找质心，通过对每个点遍历所有质心并计算点到每个质心的距离来完成
                if disJI<minDist:
                    minDist=disJI
                    minIndex=j
            if clusterAssment[i,0]!=minIndex:               #如果任一点的簇分配结果发生改变，则更新标志位
                clusterChanged=True
            clusterAssment[i,:]=minIndex,minDist**2
        print(centroids)

        for cent in range(k):                               #遍历所有质心，并更新他们的取值
            ptsInClus=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:]=mean(ptsInClus,axis=0)
    return centroids,clusterAssment

#1.二分KMeans算法
#2.伪代码
"""
      将所有点看成一个簇
      当簇的数目小于k时
          对于每一个簇
              计算总误差
              在给定的簇上面进行KMeans聚类(k=2)
              计算将该簇一分为二之后的总误差
          选择使得误差最小的那个簇进行划分操作        
"""
def biKMeans(dataSet,k,distMeas=disEclud):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))             #创建矩阵用于保存分配结果以及平方误差
    centroid0=mean(dataSet,axis=0).tolist()[0]   #将所有点看成一个簇，求得其平均值的中心
    centList=[centroid0]                         #中心值列表，最开始只有一个簇，所以只有一个中心
    for j in range(m):
        clusterAssment[j,1]=distMeas(mat(centroid0),dataSet[j,:])**2  #求得一个簇时，循环求得所有点到中心点的误差，并放入矩阵中
    while(len(centList)<k):                      #判断是否分到想要的簇数
        lowestSSE=inf                            #初始最小误差平方和SSE为正无穷
        for i in range(len(centList)):           #循环每个簇
            ptsInCurrCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]  #分类结果等于i数据集的提取出来
            centroidMat,splitClustAss=KMeans(ptsInCurrCluster,2,distMeas)     #使用KMeans进行二分类
            sseSplit=sum(splitClustAss[:,1])                                  #分类之后的总误差
            sseNotSplit=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])#分类之前不等于i的分类结果的总误差
            print("sseSplit,and notSplit:",sseSplit,sseNotSplit)
            if(sseSplit+sseNotSplit)<lowestSSE:                               #分类之后的总误差+分类之前的总误差小于最小误差
                bestCentToSplit=i                                             #分类i
                bestNewCents=centroidMat                                      #新分类点的中心坐标
                bestClusAss=splitClustAss.copy()                              #分类之后的结果以及平方误差
                bestClustSSE=sseNotSplit+sseSplit                             #分类之后的平方误差

        #更新簇的分配结果
        bestClusAss[nonzero(bestClusAss[:,0].A==1)[0],0]=len(centList)
        bestClusAss[nonzero(bestClusAss[:,0].A==0)[0],0]=bestCentToSplit

        print("the bestCentToSplit is:",bestCentToSplit)
        print("the len of bestClustAss is :",len(bestClusAss))
        centList[bestCentToSplit]=bestNewCents[0,:]                           #将新分配的坐标中心替换
        centList.append(bestNewCents[1,:])                                    #将第二个坐标中心加入cenList中
        clusterAssment[nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClusAss
    return  centList,clusterAssment

def main():
# #1.--------KMeans----------------------------------
#     dataMat=mat(loadDataSet('testSet.txt'))
#     myCentroids,clustAssing=KMeans(dataMat,4)
# #--------------------------------------------------

#2----------二分KMeans算法---------------------------
    dataMat3=mat(loadDataSet('testSet3.txt'))
    centList,myNewAssments=biKMeans(dataMat3,3)
    print (centList)
#---------------------------------------------------
if __name__=='__main__':
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136