Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (24): 105-111.

Previous Articles     Next Articles

Improved K-means algorithm based on expectation of density and clustering validity index

HE Yunbin, XIAO Yupeng, WAN Jing, LI Song   

  1. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
  • Online:2013-12-15 Published:2013-12-11

基于密度期望和有效性指标的K-均值算法

何云斌,肖宇鹏,万  静,李  松   

  1. 哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080

Abstract: The traditional K-means clustering algorithm must be given in advance the number of clusters k, but in the actual cases, k is difficult to establish; in addition, traditional K-means clustering algorithm is sensitive to initialization and easily falls into local optimum. In view of this, this paper presents an improved K-means algorithm based on expectation of density and Silhouette validity index. The algorithm chooses the furthest mutual distance k sample objects as the initial centers, which belong to the expectation of density region. The experimental result shows that the improved K-means algorithm has not only the weak dependence on initial data, but also fast convergence and high clustering quality. Meanwhile, the new algorithm can automatically analyze the clustering quality in different k values and determine the optimal number of clusters by selecting the Silhouette validity index. The experiment and analysis demonstrate the feasibility and effectiveness of the proposed algorithm.

Key words: K-means clustering, initial clustering centers, expectation of density, optimization of k

摘要: 传统K-均值聚类算法虽然收敛速度快,但存在聚类数k无法预先确定,并且算法对初始中心点敏感的缺点。针对上述缺点,提出了基于密度期望和聚类有效性Silhouette指标的K-均值优化算法。给出了基于密度期望的初始中心点选取方案,将处于密度期望区间内相距最远的k个样本作为初始聚类中心。该方案可有效降低K-均值算法对初始中心点的依赖,从而获得较高的聚类质量。在此基础上,可进一步通过选择合适的聚类有效性指标Silhouette指标分析不同k值下的每次聚类结果,确定最佳聚类数,则可有效改善k值无法预先确定的缺点。实验及分析结果验证了所提出方案的可行性和有效性。

关键词: K-均值聚类, 初始聚类中心点, 期望密度, k值优化