算法原理
由于传统的KMeans算法的聚类结果易受到初始聚类中心点选择的影响，因此在传统的KMeans算法的基础上进行算法改进，对初始中心点选取比较严格，各中心点的距离较远，这就避免了初始聚类中心会选到一个类上，一定程度上克服了算法陷入局部最优状态。
二分KMeans(Bisecting KMeans)算法的主要思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。以上隐含的一个原则就是：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点越接近于他们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次划分，因为误差平方和越大，表示该簇聚类效果越不好，越有可能是多个簇被当成了一个簇，所以我们首先需要对这个簇进行划分。
代码实现
本文在实现过程中采用数据集4k2_far.txt，聚类算法实现过程中默认的类别数量为4。其中辅助函数存于myUtil.py文件和K均值核心函数存于kmeans.py文件，具体参考《KMeans (K均值)算法讲解及实现》。
二分K均值主函数逻辑思想如下代码所示：
# -*- encoding:utf-8 -*- from kmeans import * import matplotlib.pyplot as plt dataMat = file2matrix("testData/4k2_far.txt", " ") # 从文件构建的数据集 dataSet = dataMat[:, 1:] # 提取数据集中的特征列 k = 4 # 外部指定1,2,3...通过观察数据集有4个聚类中心 m = shape(dataSet)[0] # 返回矩阵的行数 # 初始化第一个聚类中心: 每一列的均值 centroid0 = mean(dataSet, axis=0).tolist()[0] centList =[centroid0] # 把均值聚类中心加入中心表中 # 初始化聚类距离表,距离方差 # 列1：数据集对应的聚类中心,列2:数据集行向量到聚类中心距离的平方 ClustDist = mat(zeros((m, 2))) for j in range(m): ClustDist[j,1] = distEclud(centroid0,dataSet[j,:])**2 ''' color_cluster(ClustDist[:, 0:1], dataSet, plt) drawScatter(plt, mat(centList), size=60, color='red', mrkr='D') plt.show() ''' # 依次生成k个聚类中心 while (len(centList) < k): lowestSSE = inf # 初始化最小误差平方和。核心参数，这个值越小就说明聚类的效果越好。 # 遍历cenList的每个向量 #----1. 使用ClustDist计算lowestSSE，以此确定:bestCentToSplit、bestNewCents、bestClustAss----# for i in xrange(len(centList)): # 从dataSet中提取类别号为i的数据构成一个新数据集 ptsInCurrCluster = dataSet[nonzero(ClustDist[:, 0].A == i)[0], :] # 应用标准kMeans算法(k=2),将ptsInCurrCluster划分出两个聚类中心,以及对应的聚类距离表 centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2) # 计算splitClustAss的距离平方和 sseSplit = sum(multiply(splitClustAss[:, 1], splitClustAss[:, 1])) # 此处求欧式距离的平方和 # 计算ClustDist[ClustDist第1列!=i的距离平方和 sseNotSplit = sum(ClustDist[nonzero(ClustDist[:, 0].A != i)[0], 1]) if (sseSplit + sseNotSplit) < lowestSSE: # 算法公式: lowestSSE = sseSplit + sseNotSplit bestCentToSplit = i # 确定聚类中心的最优分隔点 bestNewCents = centroidMat # 用新的聚类中心更新最优聚类中心 bestClustAss = splitClustAss.copy() # 深拷贝聚类距离表为最优聚类距离表 lowestSSE = sseSplit + sseNotSplit # 更新lowestSSE # 回到外循环 # ----2. 计算新的ClustDist----# # 计算bestClustAss 分了两部分: # 第一部分为bestClustAss[bIndx0,0]赋值为聚类中心的索引 bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList) # 第二部分 用最优分隔点的指定聚类中心索引 bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit # 以上为计算bestClustAss # ----3. 用最优分隔点来重构聚类中心----# # 覆盖: bestNewCents[0,:].tolist()[0]附加到原有聚类中心的bestCentToSplit位置 # 增加: 聚类中心增加一个新的bestNewCents[1,:].tolist()[0]向量 centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0] centList.append(bestNewCents[1, :].tolist()[0]) # 以上为计算centList # 将bestCentToSplit所对应的类重新更新类别 ClustDist[nonzero(ClustDist[:, 0].A == bestCentToSplit)[0], :] = bestClustAss ''' color_cluster(ClustDist[:, 0:1], dataSet, plt) drawScatter(plt, mat(centList), size=60, color='red', mrkr='D') plt.show() ''' # 输出生成的ClustDist：对应的聚类中心(列1),到聚类中心的距离(列2),行与dataSet一一对应 color_cluster(ClustDist[:, 0:1], dataSet, plt) print "cenList:",mat(centList) # 绘制聚类中心图形 drawScatter(plt, mat(centList), size=60, color='red', mrkr='D') plt.show()
评估分类结果
上述代码的”’注释部分给出了每次迭代时，聚类中心的变化情况，如下所示：
二分K均值聚类中心变化情况
相关