基于Kruskal算法进行初值选取的改进的K-means算法.pdf

中国科技论文在线 基于 Kruskal 算法进行初值选取的改进的 K-means 算法 任倩，卓新建** 5 （北京邮电大学理学院，北京 100876） 摘要：K-means算法是聚类算法中最经典的划分算法之一，它对初值的依赖性很强，聚类结 果随初始聚类中心选择的不同而波动很大。本文基于图论中著名的Kruskal算法提出了一种 改进的 K-means 算法，该算法首先运用 Kruskal 算法生成聚类对象的最小生成树（MST）， 然后按权值从大到小删去K-1条边，将得到的 K个连通子图中对象的均值作为初始聚类中心 10 进行聚类。仿真实验表明，该算法较传统k-means算法有更好的聚类效果和准确性。 关键词：聚类；K-means算法；Kruskal算法；MST 中图分类号：TP301 Improved K-means Algorithm of Choosing the Clustering 15 Center Based on Kruskal Algorithm REN Qian, ZHUO Xinjian (School of Science,Beijing University of Post and Communication, Beijing 100876) Abstract: K-means algorithm is one of the most classic partition algorithms in clustering algorithms. The result obtained by K-means algorithm varies with the choice of the initial 20 clustering center. Motivated by this, an improved K-means algorithm is proposed based on the Kruskal algorithm, which is famous in graph theory. The procedure of this algorithm is shown as follows: Firstly, the minimum spanning tree (MST) of the clustered objects is obtained by using Kruskal algorithm. Then K-1 edges are deleted based on weights in a descending order. At last, the average value of the objects contained by the k-connected graph resulting from last two steps 25 is regarded as the initial clustering center to cluster. Simulation exeriment shows that the improved K-means algorithm has a better clustering effect and higher efficiency than the traditional one. Keywords:Clustering; K-means Algorithm; Kruskal Algori