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

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

作　　者：何云斌[1] 肖宇鹏[1] 万静[1] 李松[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机工程与应用》2013年第24期105-111,共7页Computer Engineering and Applications

基　　金：黑龙江省自然科学基金(No.F201134);黑龙江省教育厅科学技术研究项目(No.12531120)

摘　　要：传统K-均值聚类算法虽然收敛速度快,但存在聚类数k无法预先确定,并且算法对初始中心点敏感的缺点。针对上述缺点,提出了基于密度期望和聚类有效性Silhouette指标的K-均值优化算法。给出了基于密度期望的初始中心点选取方案,将处于密度期望区间内相距最远的k个样本作为初始聚类中心。该方案可有效降低K-均值算法对初始中心点的依赖,从而获得较高的聚类质量。在此基础上,可进一步通过选择合适的聚类有效性指标Silhouette指标分析不同k值下的每次聚类结果,确定最佳聚类数,则可有效改善k值无法预先确定的缺点。实验及分析结果验证了所提出方案的可行性和有效性。The traditional Kmeans 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 Kmeans clustering algorithm is sensitive to initialization and easily falls into local optimum. In view of this, this paper presents an improved Kmeans algorithm based on expectation of density and Silhou ette 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 Kmeans algorithm has not only the weak depen dence 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.

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

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