一种改进K-means聚类的近邻传播最大最小距离算法

王美琪 李 建

(西南石油大学计算机科学学院 四川 成都 610500)

0 引 言

初始聚类中心对K-means聚类结果影响极大。经典的K-means聚类算法采用随机选取初始聚类中心的方式，有以下不足：① 易导致聚类结果的不稳定；② 有取得离群点作为初始聚类中心的可能；③ 某些初始聚类中心可能离群体太远，有的初始聚类中心可能相互之间隔得太近。为克服这些缺点，文献[1-3]分别采用构造最小生成树、最短路径加权属性图、最大最小距离MMD(Max-Min Distance)算法计算K-means的初始聚类中心，获得了一定的效果。但实验发现，在聚类簇数较大时，因k值的限定，MMD算法获得的初始聚类中心有同类多点而导致初始类的缺失，虽然K-means算法通过迭代移动聚类中心部分最后接近实际中心，但仍有部分将陷入局部最优。且MMD初始聚类中心往往在簇的边界，这无形中影响了算法收敛速度。近邻传播算法(Affinity Propagation，AP)可根据相似参考度进行全局寻优，获得多个具有代表性的聚类中心[4-5]，但由于选到同类多点而导致聚类数目一般大于实际簇数，直接用AP聚类中心作为K-means初始聚类中心聚类的结果不符合实际。

本文提出一种近邻传播算法和最大最小距离算法联合计算K-means初始聚类中心的算法(APMMD)。该算法首先通过近邻传播算法从整个样本集中全局寻优，获得Kap(Kap>k)个具有代表性的候选中心点，再利用最大最小距离算法从Kap个候选中心点中选择k个初始聚类中心。将该算法获得的初始聚类中心应用于K-means聚类，在多个UCI数据集上进行实验，通过已知分类对比，用Purity、AC、NMI、JC、RI和FMI有效性评价指标及迭代次数验证。结……