K-均值聚类算法(K-means)

程序1,随机生成K个样本中心:

#计算两组数据间的欧氏距离

def distEclud(vecA, vecB):

return sqrt(sum(power(vecA - vecB, 2)))

#构造质心

def randCent(dataSet, k):

n = shape(dataSet)[1]#求出数据的列数

centroids = mat(zeros((k, n)))#生成k组n列的矩阵,值全为0

for j in range(n):#对每一列的数字随机生成

minJ = min(dataSet[:, j])#读取某列中的最小值

rangeJ = float(max(dataSet[:, j]) - minJ)#某列数据范围

centroids[:, j] = minJ + rangeJ * random.rand(k, 1)#随机矩阵该列的值为最小值+数据范围乘以一个0到1的随机数,rand(k, 1)生成k行1列的随机矩阵

return centroids

该程序片段会根据传入的dataSet和k值计算出k个初始质心

程序2,计算kMeans

#计算kMeans,返回K个中心点以及各组数据离中心点的距离

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):

m = shape(dataSet)[0]#获取待分组样本总数

clusterAssment = mat(zeros((m,2)))#用于保存各组样本属于哪个簇,同时保存与簇中心的距离

centroids = createCent(dataSet, k)#随机创建k个质心

clusterChanged = True#质心变化标志,初始化为true,在循环中,任何一个质心发生变化,该值就为true

while clusterChanged:

clusterChanged = False

for i in range(m):#对m组样本进行循环

minDist = inf#取正无穷

minIndex = -1#取下标为-1

for j in range(k):#对每个质心进行循环

distJI = distMeas(centroids[j,:],dataSet[i,:])#计算第i组样本离质心j的距离

if distJI < minDist:#若距离比上一步计算的最小距离还小

minDist = distJI#更新该值

minIndex = j#则样本i离质心j最近

if clusterAssment[i,0] != minIndex:#若保存的质心与新计算的质心不一致

clusterChanged = True

clusterAssment[i,:] = minIndex,minDist**2#计算的质心,与质心距离平方

print centroids

for cent in range(k):#对k个中心进行循环

ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#将属于第cent个中心的所以样本从dataSet中取出

centroids[cent,:] = mean(ptsInClust, axis=0) #根据簇cent中的所有样本,计算新的质心

return centroids, clusterAssment#返回最终稳定的质心,以及各样本所属质心和距离

程序的详细过程都写在注释中.大致思路是,根据传入的dataSet和k值,以及构造初始质心的方法,计算距离的方法等参数生成最终的质心,以及各样本距离所属质心和与质心的距离.计算过程中只要发现任何一个质心发生了调整,则继续进行下一轮计算,直到各质心保持不变为止.

程序2的改进

问题来了,对待分组样本,如何能够事先知道可以分为多少组呢?并且,如何衡量该聚类的效果好坏呢?其实上面的程序有可能陷入局部最小值,而非全局最小值.有一种度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和),误差平方也就是上面程序2的clusterAssment中下标为1的那些数据.

首先我们假设k的值已经固定,即明确数据要分成多少类.由于采用SSE指标,那么离质心越远的点对该指标的影响最大.为了降低SSE的值,首先想到的是可以增加质心的个数,将SSE最大的那个簇采用k`=2重新聚类.但是增加质心个数又违背了k的个数固定这个条件.因为增加了一个质心,那么我们再将其中某两个质心进行合并是不是又减少了一个质心呢?如何选择哪写质心进行合并?有两种办法,第一是合并最近的质心,第二是合并两个使得SSE增幅最小的质心.

二分K-Means算法

为了避免陷入局部最小值,可以使用二分K-Means算法(bisecting K-means).

假设数据会被分成k个组,首先将所有数据当成一个簇,将该簇一分为2,然后选择其中一个簇再进行二分.每次二分都会增加一个簇,直到簇的数目达到K为止.选择哪一个簇进行二分呢?哪个簇进行二分能最大成都降低SSE的值就选择哪个簇进行二分.

程序3,二分K-Means算法

#二分K-Means算法

def biKmeans(dataSet, k, distMeas=distEclud):

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):#当前质心数小于设定质心数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)#将该簇进行二分

sseSplit = sum(splitClustAss[:,1])#计算二分后的SSE

sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])#不在该簇中其他点的SSE

print "sseSplit, and notSplit: ",sseSplit,sseNotSplit

if (sseSplit + sseNotSplit) < lowestSSE:#两者相加,若比最低SSE还要低

bestCentToSplit = i#就在第i个质心上

bestNewCents = centroidMat#i簇上的二分质心

bestClustAss = splitClustAss.copy()#返回K个中心点以及各组数据离中心点的距离

lowestSSE = sseSplit + sseNotSplit#最低SSE更新为当前最低值

#每次二分会新增一个质心,,bestClustAss每次都是分成0和1两种情况,

#比如之前有两个质心0和1,发现其中1簇可以继续二分,那么现在就有三个质心,将新的1设置为2,将新的0设置为1,

#那么现在的三个质心分别为0,1,2,原来的0保持不变

bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #将其中是1的更新为最新增加的簇

bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit#将其中为0的继续保存在之前那个质心编号内

print 'the bestCentToSplit is: ',bestCentToSplit

print 'the len of bestClustAss is: ', len(bestClustAss)

centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#将最佳二分的i簇原来的质心替换成新生成的第一个质心

centList.append(bestNewCents[1,:].tolist()[0])#将新生成的第二个质心也追加到最佳质心列表中

clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#最佳二分的i簇新的相关信息

return mat(centList), clusterAssment

若k值不确定,有一个Canopy算法可以用在K-Means之前用于确定k的个数以及初始的质心坐标。