Abstract: To solve this problems that the traditional K-means algorithm has sensitivity to the initial cluster centers, a new improved K-means algorithm is proposed. The algorithm builds minimum spanning tree and then splits it to get K initial clusters and the relevant initial cluster centers. The initial cluster centers are found to be very closed to the desired cluster centers for iterative clustering algorithms. Theory analysis and experimental results demonstrate that the improved algorithms can enhance the clustering performance, get stable clustering in a higher accuracy.

Key words: K-means algorithm, clustering, initial clustering centers, TDKM algorithm

摘要： 针对传统K-means算法对初始聚类中心敏感的问题，提出了基于数据样本分布情况的动态选取初始聚类中心的改进K-means算法。该算法根据数据点的距离构造最小生成树，并对最小生成树进行剪枝得到K个初始数据集合，得到初始的聚类中心。由此得到的初始聚类中心非常地接近迭代聚类算法收敛的聚类中心。理论分析与实验表明，改进的K-means算法能改善算法的聚类性能，减少聚类的迭代次数，提高效率，并能得到稳定的聚类结果，取得较高的分类准确率。

关键词: K-means算法, 聚类, 初始聚类中心, TDKM算法