基于全局中心的高密度不唯一的K-means算法研究  

Improved K-means algorithm based on global center and nonuniqueness high-density points

作　　者：何云斌[1] 刘雪娇[1] 王知强[2] 万静[1] 李松[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]黑龙江财经学院计算机与信息工程系,哈尔滨150025

出　　处：《计算机工程与应用》2016年第1期48-54,共7页Computer Engineering and Applications

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

摘　　要：传统的K-means算法敏感于初始中心点的选取,并且无法事先确定准确的聚类数目k,不利于聚类结果的稳定性。针对传统K-means算法的以上不足,提出了基于全局中心的高密度不唯一的新方法——NDK-means,该方法通过标准差确定有效密度半径,并从高密度区域中选取具有代表性的样本点作为初始聚类中心。此外算法针对最高密度点不唯一的情况进行特别分析,选取距离全局中心最远的点集作为最优的初始中心点集合。在NDK-means算法基础上结合有效性指标BWP对聚类结果进行分析,从而解决了最佳有效聚类数目无法事先确定的不足。理论研究与实验结果表明所提方法的聚类结果具有更好的稳定性和可行性。The traditional K-means algorithm is sensitive to the selection of the initial clustering center, moreover the clustering number-k can not be confirmed beforehand. Then it is not conductive to the stability of the clustering. Considering this defection, a new improved algorithm—NDK-means（Nonuniqueness high-Density K-means） is proposed which is based on the global clustering center. In this algorithm, the highest-density points are not unique. To determine the radius,the standard deviation is applied to the new algorithm, then the initial clustering centers can be selected from a set of the high-density areas of points. When the highest-density points are not unique, the proposed new algorithm selects a set of initial clustering centers which are the furthest distance from the global clustering center. Besides, the new algorithm can determine the optimal number of cluster by selecting the BWP validity index. Finally, the experimental and analysis results show the new proposed method outperforms than the traditional K-means algorithm in terms of the validity and stability.

关 键 词：K-MEANS算法 初始中心 聚类数 基于密度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]