一种对K-means算法的改进

李光明，李 梁，张建刚

(重庆理工大学计算机科学与工程学院，重庆 400054)

0 引言

数据挖掘是指从大量数据中提取或“挖掘”知识［1］。聚类是一种无监督学习，它把形式相似的对象聚集在一起。使得在同一簇中的对象之间相似度大，不同簇中的对象之间的相似度小。聚类算法已广泛应用在模式识别、图像处理、过程优化、配方设计等许多领域中，并取得了良好效果，受到了人们广泛重视［2］。目前最流行的聚类算法之一就是K-means算法。

部分成果讲述了对K均值初始聚类中心的研究。Duda etal［3］讲述了用递归的方法初始化簇均值，此方法的另一种形式包括整个数据集的平均值，然后随机的用微扰函数干扰它k次。张玉英［2］提出了基于密度和聚类对象方向的改进算法。算法采取聚类对象分布密度方法来确定初始聚类中心，然后根据对象的聚类方向来发现任意形状的簇。连凤娜［4］提出了一种改进的K-means算法，主要从数据预处理、初始聚类中心的选择方面进行了改进。顾洪博［5］对近年来K-means算法的研究现状与进展进行总结。对较有代表性的初始聚类中心改进的算法，从思想、关键技术和优缺点等方面进行分析。

提出了一种基于反向最近邻(RNN)搜索的K均值稳定的初始化方案，这是一种与上述研究不同的方法。本方法的主要优点是通过该方法得到的初始划分比较接近最终解决方案，根据几个评估标准K均值的性能也得到了显著的提高。该方法的计算复杂度相对较低，并且样本集中的离群点也可以通过该方法检测出来。……