Improved k-means clustering algorithm  

一种改进的k-means聚类算法(英文)

作　　者：夏士雄[1] 李文超[1] 周勇[1] 张磊[1] 牛强[1] 

机构地区：[1]中国矿业大学计算机科学与技术学院,徐州221008

出　　处：《Journal of Southeast University(English Edition)》2007年第3期435-438,共4页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No50674086);Specialized Research Fund for the Doctoral Program of Higher Education (No20060290508);the Youth Scientific Research Foundation of China University of Mining and Technology (No2006A047)

摘　　要：In allusion to the disadvantage of having to obtain the number of clusters of data sets in advance and the sensitivity to selecting initial clustering centers in the k-means algorithm, an improved k-means clustering algorithm is proposed. First, the concept of a silhouette coefficient is introduced, and the optimal clustering number Kopt of a data set with unknown class information is confirmed by calculating the silhouette coefficient of objects in clusters under different K values. Then the distribution of the data set is obtained through hierarchical clustering and the initial clustering-centers are confirmed. Finally, the clustering is completed by the traditional k-means clustering. By the theoretical analysis, it is proved that the improved k-means clustering algorithm has proper computational complexity. The experimental results of IRIS testing data set show that the algorithm can distinguish different clusters reasonably and recognize the outliers efficiently, and the entropy generated by the algorithm is lower.针对k-means算法事先必须获知聚类数目以及难以确定初始中心的缺点,提出了一种改进的k-means聚类算法.首先引入轮廓系数的概念,通过计算不同K值下簇集中各对象的轮廓系数确定事先未知分类信息的数据集中所包含的最优聚类数Kopt;然后通过凝聚层次聚类的方法获得数据集的分布,确定初始聚类中心;最后利用传统的k-means方法完成聚类.理论分析表明,所提出的算法具有适度的计算复杂度.IRIS测试数据集的实验结果表明了该算法能够合理区分不同类型的簇集,且可以有效地识别离群点,聚合后的结果簇集具有较低的熵值.

关 键 词：CLUSTERING k-means algorithm silhouette coefficient 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]