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

广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (4): 33-40.

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

石亚冰, 黄予, 覃晓, 元昌安

广西师范学院计算机与信息工程学院,广西南宁530023

收稿日期:2013-05-10 出版日期:2013-12-20 发布日期:2018-11-26
通讯作者: 元昌安(1964—),男,安徽合肥人,广西师范学院教授,博士。E-mail:yca@gxtc.edu.cn
基金资助:
国家自然科学基金资助项目(61363037,61363074);广西自然科学基金资助项目(2011GXNSFD018025);广西自然科学青年基金资助项目(2012GXNSFBA053161)

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

SHI Ya-bing, HUANG Yu, QIN Xiao, YUAN Chang-an

College of Computer and Information Engineering,Guangxi Teachers Education University,Guangxi Nanning 530023,China

Received:2013-05-10 Online:2013-12-20 Published:2018-11-26

摘要/Abstract

摘要： 作为典型的启发式聚类算法,K-Means受到初始模型的影响而存在两个缺陷:算法对初始模型非常敏感和聚类效果差强人意。若给K-Means一个能够反映数据分布特征的初始种子集,这些种子既处于数据密集区域,又尽可能相互之间远离,这样一个初始模型对于提高启发式算法性能具有重要意义。本文据此给出距离密度混合选择(HYDD)种子优化方案的基本思路:对数据集进行密度排序,在此基础上选取密度大且满足距离大于密度直径的数据作为候选初始种子集,在候选初始种子集上,利用点点之间距离从大到小选取K个所需的种子,最后利用该初始种子集引导K-Means算法来搜索聚类结果。在5组仿真数据集和3组真实数据集上的实验结果表明,HYDD K-Means算法能够稳定的获取具备高内聚、高分离这一优良特征的聚类簇。

关键词: 聚类, 初始种子, 启发式搜索, K-Means算法

Abstract: 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 reflect 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 rearranges the original data on the principle of decreasing density,then the date higher density and longer distance than the diameter wer interted into a candidate set.Secondly,k seeds is selected from the candidate set based on the theory that the sum of distance is decreasing.Finally,K-Means is run with the initial 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.

Key words: clustering, initial seeds, heuristic searching, K-Means algorithm

中图分类号:

TP301.6

石亚冰, 黄予, 覃晓, 元昌安. 基于优化初始种子新策略的K-Means聚类算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 33-40.

SHI Ya-bing, HUANG Yu, QIN Xiao, YUAN Chang-an. K-Means Clustering Algorithm Based on a Novel Approach for Improved Initial Seeds[J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(4): 33-40.

参考文献

[1] CHANDRA B,GUPTA M.A novel approach for distance-based semi-supervised clustering using functional link neural network[J].Soft Comput,2013,17(3):369-379.
[2] JARMAN I H,ETCHEKKS T A,BACCIU D,et al.Clustering of protein expression data:a benchmark of statistical and neural approaches[J].Soft Comput,2011,15(8):1459-1469.
[3] 沙贝贝,谢丽聪.一种基于频繁项集的搜索引擎聚类浏览算法[J].广西师范大学学报:自然科学版,2011,29(2):151-155.
[4] MANSOORI E G.GACH:A grid-based algorithm for hierarchical clustering of high-dimensional data[J].Soft Comput,2013,17(8):1-8.
[5] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[6] QIAN Wei-ning,ZHOU Ao-ying.Analyzing popular clustering algorithms from different viewpoints[J].Journal of Software,2002,13(8):1382-1394.
[7] BRADLEY P S,FAYYAD U M.Refining initial points for K-Means clustering[C]//Proceedings of 15th International Conference on Machine Learning.San Francisco CA:Morgan Kaufmann,1998:91-99.
[8] 宗瑜,金萍,李明楚.BK-means:骨架初始解K-means[J].计算机工程与应用,2009,45(14):49-52.
[9] McQUEEN J B.Some methods for classification and analysis of multivariate observation[C]//LE CAM L M,NEYMAN J.Berkeley Symposium on Mathematical Statistics and Probability.Berkeley:University of California Press,1967:281-297.
[10] KATSAVOUNIDIS I,KUO C C J,ZHANG Zhen.A new initialization technique for generalized Floyd iteration[J].IEEE Signal Process Lett,1994,1(10):144-146.
[11] 袁方,周志勇,宋鑫.初始聚类中心优化的K-means算法[J].计算机工程,2007,33(3):65-66.
[12] 韩凌波,王强,蒋正峰,等.一种改进的K-means初始聚类中心选取算法[J].计算机工程与应用,2010,46(17):150-152.
[13] 黄敏,何中市,邢欣来,等.一种新的K-means聚类中心选取算法[J].计算机工程与应用,2011,47(35):132-134.
[14] 陈福集,蒋芳.基于2d-距离改进的K-means聚类算法研究[J].太原理工大学学报,2012,43(2):114-118.
[15] 任培花,王丽珍.不确定域环境下基于DKC值改进的K-means聚类算法[J].计算机科学,2013,40(4):181-184.
[16] 石亚冰,元昌安,覃晓,等.基于最大维密度的全局优化空间聚类算法[J].计算机仿真,2013,30(3):277-281.
[17] HE Ji,TAN An-hwee,TAN Chew-lim,et al.On quantitative evaluation of clustering systems[C]//WU Wei-li,XIONG Hui,SHEKHAR S.Clustering and Information Retrieval.Norwell,MA:Kluwer Academic Publishers,2003.
[18] HE Ji,LAN Man,TAN Chew-lim,et al.Initialization of cluster refinement algorithms:a review and comparative study[C]//Proceedings of 2004 IEEE International Joint Conference on Neural Networks.New York:IEEE Press,2004:297-302.

相关文章 15

[1]	王勋, 李廷会, 潘骁, 田宇. 基于改进模糊C均值聚类与Otsu的图像分割方法[J]. 广西师范大学学报（自然科学版）, 2019, 37(4): 68-73.
[2]	苏雷,李俊英. 国家重点生态功能区县域生态环境质量状况分级标准探讨[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 196-202.
[3]	刘金龙, 郭岩, 余智华, 刘悦, 俞晓明, 程学旗. 基于词聚类的跨媒体突发事件检测方法[J]. 广西师范大学学报（自然科学版）, 2019, 37(1): 23-31.
[4]	林越, 刘廷章, 黄莉荣, 奚晓晔, 潘建. 基于双向KL距离聚类算法的变压器状态异常检测[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 20-26.
[5]	林越,刘廷章,陈一凡,金勇,梁立新. 基于AP-HMM混合模型的充电桩故障诊断[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 25-33.
[6]	闫妍,胡宝清,侯满福,史莎娜. 广西岩溶区县域石漠化治理模式适宜性评价[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 145-153.
[7]	胡郁葱, 陈杰, 邹小健, 陈枝伟. 基于两阶段聚类的电动自行车出行者选择研究[J]. 广西师范大学学报（自然科学版）, 2017, 35(3): 22-29.
[8]	唐祺玲,陈志林,周善义. 基于属级阶元的中国蚁科昆虫地理区划研究[J]. 广西师范大学学报（自然科学版）, 2017, 35(1): 82-91.
[9]	曹永春, 邵亚斌, 田双亮, 蔡正琦. 一种基于免疫遗传算法的聚类方法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 59-64.
[10]	马静, 邹艳丽, 李福涛, 莫玉芳. 最大度受限LBA网络模型研究[J]. 广西师范大学学报（自然科学版）, 2011, 29(4): 21-24.
[11]	郑磊, 朱正礼, 侯迎坤. 基于改进的微粒群算法的WSN节点部署策略[J]. 广西师范大学学报（自然科学版）, 2011, 29(4): 56-62.
[12]	沈泽豪, 叶中行. 期货公司客户风险管理的模糊聚类分析[J]. 广西师范大学学报（自然科学版）, 2011, 29(3): 101-104.
[13]	徐丽, 丁世飞, 郭锋锋. 基于改进属性约简的粗核聚类算法[J]. 广西师范大学学报（自然科学版）, 2011, 29(3): 105-109.
[14]	沙贝贝, 谢丽聪. 一种基于频繁项集的搜索引擎聚类浏览算法[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 151-155.
[15]	周鑫, 郝志峰, 蔡瑞初, 温雯. 带噪声的文本聚类及其在反垃圾邮件中的应用[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 156-160.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed