二分K-means算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

二分K-means聚类（bisecting K-means）

算法优缺点：

由于这个是K-means的改进算法，所以优缺点与之相同。

算法思想：

1.要了解这个首先应该了解K-means算法，可以看这里这个算法的思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇（或者选择最大的簇等，选择方法多种）。以此进行下去，直到簇的数目等于用户给定的数目k为止。
2.以上隐含着一个原则是：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点月接近于它们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次的划分，因为误差平方和越大，表示该簇聚类越不好，越有可能是多个簇被当成一个簇了，所以我们首先需要对这个簇进行划分。
3.关于二分K-means的优点《Machine Learning in Action》说的是能够克服K-means收敛于局部最小，但是想了一下感觉这个并不能保证收敛到全局最优值（而且后面运行代码结果也会出现不太好的情况，不知道这算不算是个证据）
4.通过查阅一些资料和总结，二分K-means聚类的优点有：

二分K均值算法可以加速K-means算法的执行速度，因为它的相似度计算少了
不受初始化问题的影响，因为这里不存在随机点的选取，且每一步都保证了误差最小

所以说这个算法也并不能够保证完全不受K的影响一定归到全局最小，只是相对较优，并且还有了一定的速度提升。理解有偏差欢迎指正。

函数：

biKmeans(dataSet, k, distMeas=distEclud)
这个函数实现了二分算法，过程大体如下（代码中注释已经很详细了）：
1.初始化全部点的质心，并建立所需要的数据存储结构
2.对每一个簇尝试二分（最开始就是一个簇），选出最好的
3.更新各个簇的元素个数

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

     m = shape(dataSet)[0]

     clusterAssment = mat(zeros((m,2)))#记录簇分配的结果及误差

     centroid0 = mean(dataSet, axis=0).tolist()[0]#计算整个数据集的质心

     centList =[centroid0] #create a list with one centroid

     for j in range(m):#计算初始聚类点与其他点的距离

         clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2

     while (len(centList) < k):

         lowestSSE = inf

         for i in range(len(centList)):#尝试划分每一簇

             ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]#get the data points currently in cluster i

             centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)#对这个簇运行一个KMeans算法，k=2

             sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum

             sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])

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

             if (sseSplit + sseNotSplit) < lowestSSE:##划分后更好的话

                 bestCentToSplit = i

                 bestNewCents = centroidMat

                 bestClustAss = splitClustAss.copy()

                 lowestSSE = sseSplit + sseNotSplit

         bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #更新簇的分配结果change 1 to 3,4, or whatever

         bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit

         print 'the bestCentToSplit is: ',bestCentToSplit

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

         centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids

         centList.append(bestNewCents[1,:].tolist()[0])

         clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE

     return mat(centList), clusterAssment