基于优化初始种子新策略的K-Means聚类算法  

K-Means Clustering Algorithm Based on a Novel Approach for Improved Initial Seeds

作　　者：石亚冰[1] 黄予[1] 覃晓[1] 元昌安[1] 

机构地区：[1]广西师范学院计算机与信息工程学院,广西南宁530023

出　　处：《广西师范大学学报（自然科学版）》2013年第4期33-40,共8页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(61363037;61363074);广西自然科学基金资助项目(2011GXNSFD018025);广西自然科学青年基金资助项目(2012GXNSFBA053161)

摘　　要：作为典型的启发式聚类算法,K-Means受到初始模型的影响而存在两个缺陷:算法对初始模型非常敏感和聚类效果差强人意。若给K-Means一个能够反映数据分布特征的初始种子集,这些种子既处于数据密集区域,又尽可能相互之间远离,这样一个初始模型对于提高启发式算法性能具有重要意义。本文据此给出距离密度混合选择(HYDD)种子优化方案的基本思路:对数据集进行密度排序,在此基础上选取密度大且满足距离大于密度直径的数据作为候选初始种子集,在候选初始种子集上,利用点点之间距离从大到小选取K个所需的种子,最后利用该初始种子集引导K-Means算法来搜索聚类结果。在5组仿真数据集和3组真实数据集上的实验结果表明,HYDDK-Means算法能够稳定的获取具备高内聚、高分离这一优良特征的聚类簇。K-Means is one of classical and heuristic clustering algorithm ,which is sensitive to the model＇s initial state. This makes the initialization of the model deterministic to the clustering solution, and the process usually can obtain the local optima result. The study on supplying a initial seeds set that can re- flect the characteristics about the distribution of the data is of great value for clustering research. They would be selected in a denser region as far as possible and would be dispersive as much as possible. And then Hybrid Distance Density Based Seeking （HYDD） stategy is offered, first of all,this method rear- ranges the original data on the principle of decreasing density, then the date higher density and longer distance than the diameter wer interred into a candidate set. Secondly,k seeds is selected from the candi- date set based on the theory that the sum of distance is decreasing. Finally,K-Means is run with the ini- tial seed set. Experiments results on 5 synthesis and 3 real datasets show that HYDD K-Means could obtain clusters which have maximal intra-cluster homogeneity and maximal inter-cluster separation.

关 键 词：聚类 初始种子 启发式搜索 K-MEANS算法 

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