杨一帆 贺国先 李永定

摘要：K-means算法的聚类效果与初始聚类中心的选择以及数据中的孤立点有很大关联，具有很强的不确定性。针对这个缺点，提出了一种优化初始聚类中心选择的K-means算法。该算法考虑数据集的分布情况，将样本点分为孤立点、低密度点和核心点，之后剔除孤立点与低密度点，在核心点中选取初始聚类中心，孤立点不参与聚类过程中各类样本均值的计算。按照距离最近原则将孤立点分配到相应类中完成整个算法。实验结果表明，改进的K-means算法能提高聚类的准确率，减少迭代次数，得到更好的聚类结果。

关键词：聚类;K-means;最近邻点密度;初始聚类中心;孤立点

Abstract：The clustering effect of K-means algorithm is closely related to the selection of initial clustering center and the isolated points in the data， so it has strong uncertainty.In order to solve this problem， a novel K-means algorithm based on nearest neighbor density is proposed. In this algorithm， considering the distribution of the data set， the sample points are divided into isolated points， low density points and core points， and then the isolated points and low density points are eliminated， and the initial clustering center is selected in the core points. Isolated points do not participate in the calculation of the mean value of all kinds of samples in the process of clustering. The outlier is assigned to the corresponding class according to the nearest principle to complete the whole algorithm. The experimental results show that the improved K-means algorithm can improve the clustering accuracy， reduce the number of iterations， and get better clustering results.

Key words： clustering; k-means; nearest neighbor density; initial clustering center; isolated points

聚类就是按一定的标准把物理或抽象对象的集合分成若干类别的过程，聚类后得到的每一个簇中的对象要尽可能的相似，不同簇中的对象尽量的相异[1-2]。聚类分析是一种无指导的学习方式，作为数据挖掘的一个重要研究方向，被广泛应用到商务智能、图像识别、Web搜索等领域。到目前为止，已经形成了很多聚类分析的方法，例如：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法等等[3]。

K-means聚类算法是数据挖掘中应用最广泛的算法之一[4]。该算法易于实现，收敛速度快，处理数据集时有较好的伸缩性。但是该算法在开始运行时初始聚类中心的选取是随机的，如果初始聚类中心随机选在了数据中的孤立点，那么最后的聚类效果就不会很理想。因此如何选取合适的聚类中心从而避免孤立点的影响一直以来都是K-means算法的一个重要研究方向。……