Abstract: The traditional K-means algorithm is sensitive to the selection of the initial clustering center, moreover the clustering number-k can not be confirmed beforehand. Then it is not conductive to the stability of the clustering. Considering this defection, a new improved algorithm—NDK-means（Nonuniqueness high-Density K-means） is proposed which is based on the global clustering center. In this algorithm, the highest-density points are not unique. To determine the radius, the standard deviation is applied to the new algorithm, then the initial clustering centers can be selected from a set of the high-density areas of points. When the highest-density points are not unique, the proposed new algorithm selects a set of initial clustering centers which are the furthest distance from the global clustering center. Besides, the new algorithm can determine the optimal number of cluster by selecting the BWP validity index. Finally, the experimental and analysis results show the new proposed method outperforms than the traditional K-means algorithm in terms of the validity and stability.

Key words: K-means algorithm, initial clustering center, number of clusters, density-based

摘要： 传统的K-means算法敏感于初始中心点的选取，并且无法事先确定准确的聚类数目[k]，不利于聚类结果的稳定性。针对传统K-means算法的以上不足，提出了基于全局中心的高密度不唯一的新方法——NDK-means，该方法通过标准差确定有效密度半径，并从高密度区域中选取具有代表性的样本点作为初始聚类中心。此外算法针对最高密度点不唯一的情况进行特别分析，选取距离全局中心最远的点集作为最优的初始中心点集合。在NDK-means算法基础上结合有效性指标BWP对聚类结果进行分析，从而解决了最佳有效聚类数目无法事先确定的不足。理论研究与实验结果表明所提方法的聚类结果具有更好的稳定性和可行性。

关键词: K-means算法, 初始中心, 聚类数, 基于密度