计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 460-464.

• 大数据与数据挖掘 • 上一篇    下一篇

基于内聚度和耦合度的二分K均值方法

郁湧1,2,康庆怡1,陈长赓1,阚世林1,骆永军1   

  1. 云南大学软件学院 昆明6505041
    云南省软件工程重点实验室 昆明6505042
  • 出版日期:2018-06-20 发布日期:2018-08-03
  • 作者简介:郁 湧(1980-),男,博士,副教授,CCF会员,主要研究方向为软件工程、数据分析,E-mail:yuy1219@163.com。
  • 基金资助:
    国家自然科学基金项目(61462091),云南大学数据驱动的软件工程省科技创新团队项目(2017HC012)资助

Bisecting K-means Clustering Method Based on Cohesion and Coupling

YU Yong1,2,KANG Qing-yi1,CHEN Chang-geng1,KAN Shi-lin1,LUO Yong-jun1   

  1. School of Software,Yunnan University,Kunming 650504,China1
    Key Laboratory for Software Engineering of Yunnan Province,Kunming 650504,China2
  • Online:2018-06-20 Published:2018-08-03

摘要: 聚类分析是数据挖掘中最重要的技术之一,它在社会经济的各个领域都具有重要作用,并被广泛应用。K均值算法是最经典、应用最广泛的聚类方法之一,但其缺点是过度依赖初始条件和聚类数目难以确定,这制约了其应用范围。引入簇的内聚度和耦合度的定义与度量方法,基于“高内聚低耦合”的原理,在二分K均值聚类过程中对得到的簇进行不断的分裂和合并,并判断聚类结果是否满足要求以确定聚类的次数和簇的个数,从而实现对二分K均值聚类过程的改进。在Iris数据集上的实验测试与分析表明该算法不仅更加稳定,而且其聚类结果的正确率也较高。

关键词: 聚类, 二分k均值, 内聚度, 耦合度

Abstract: Clustering analysis is one of the most important techniques in data mining.It has important role and wide application in every field of social economy.K-means is one kind of the simple and widely used clustering methods,but its disadvantage is that it depends on the initial conditions and the number of clusters is difficult to determine.This paper introduced the cohesion and coupling of cluster,and presented the measurement of cohesion and coupling.Based on the principle of “high cohesion and low coupling”,the clusters are constantly divided and merged in the process of bisecting K-Means clustering algorithm.By judging whether the clustering results meet the requirements,it can determine the number of clusters,thus improving the bisecting K-Means clustering algorithm.The experimental results on Iris data show that the algorithm is not only more stable,but also has higher clustering accuracy.

Key words: Clustering, Bisecting K-means, Cohesion, Coupling

中图分类号: 

  • TP391
[1]HAN J W,KAMBER M,PEI J.Data mining:concepts and techniques(3rd ed)[M].Burlington:Elsevier Science,2011.
[2]ILLHOI Y,HU X H.A comprehensive comparison study of document clustering for a biomedical digital library MEDLINE[C]∥Proceedings of the 6th ACM/IEEE-CS Joint Conference on Digital Libraries.New York,USA:ACM,2006:220-229.
[3]SILVA J D A,HRUSCHKA E R.Extending k-Means-Based Algorithms for Evolving Data Streams with Variable Number of Clusters[C]∥International Conference on Machine Learning and Applications and Workshops.2011:14-19.
[4]SAVARESI S M,BOLEY D.On the Performance of Bisecting K-Means and PDDP[C]∥Proc.of the 1st SIAM International Conference on Data Mining.Chicago,USA:2001:1-14.
[5]刘广聪,黄婷婷,陈海南.改进的二分K均值聚类算法[J].计算机应用与软件,2015,32(2):261-263.
[6]VAMSI K B S,SATHEESH P,SUNEEL K R.Comparative Study of K-means and Bisecting K-means Techniques in Wordnet Based Document Clustering[J].International Journal of Engineering and Advanced Technology,2012,1(6):119-234.
[7]张军伟,王念滨,黄少滨,等.二分K均值聚类算法优化及并行研究[J].计算机工程,2011,37(17):23-25.
[8]裘国永,张娇.基于二分K-均值的SVM决策树自适应分类方法[J].计算机应用研究,2012,29(10):3685-3709.
[9]STEINBACH M,KARYPIS G,KUMAR V.A Comparison of Document Clustering Techniques[C]∥Proc.of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Boston,USA,2000:525-526.
[10]LIU X Z,FENG G C.Kernel Bisecting K-Means Cluster- ing for SVM Training Sample Reduction[C]∥Proc.of the 19th International Conference on Pattern Recognition.Tampa,USA,2008:1-4.
[11]戴东波,汤春蕾,熊赟.基于整体和局部相似性的序列聚类算法[J].软件学报,2010,21(4):702-717.
[1] 秦悦, 丁世飞. 半监督聚类综述[J]. 计算机科学, 2019, 46(9): 15-21.
[2] 杨震, 王红军. 基于轨迹划分与密度聚类的移动用户重要地点识别方法[J]. 计算机科学, 2019, 46(8): 23-27.
[3] 蔡莉, 李英姿, 江芳, 梁宇. 面向城市热点区域的不平衡数据聚类挖掘研究[J]. 计算机科学, 2019, 46(8): 16-22.
[4] 孙书亚, 方欢, 方贤文. 日志诱导下的形态学片段流程聚类方法[J]. 计算机科学, 2019, 46(8): 71-77.
[5] 雒僖, 范九伦, 于海燕, 梁丹. 基于阴影集的截集式可能性C-均值聚类截集门限的选取[J]. 计算机科学, 2019, 46(8): 249-254.
[6] 孙国道, 周志秀, 李思, 刘义鹏, 梁荣华. 基于地理标签的推文话题时空演变的可视分析方法[J]. 计算机科学, 2019, 46(8): 42-49.
[7] 张会兵, 钟昊, 胡晓丽. 基于主题分析的用户评论聚类方法[J]. 计算机科学, 2019, 46(8): 50-55.
[8] 王丽芳, 史超宇, 蔺素珍, 秦品乐, 高媛. 基于联合图像块聚类自适应字典学习的多模态医学图像融合[J]. 计算机科学, 2019, 46(7): 238-245.
[9] 李晓光, 邵超. 基于网格数据中心的密度峰值聚类算法[J]. 计算机科学, 2019, 46(6A): 457-460.
[10] 王楠, 孙善武. 基于半监督聚类分析的无人机故障识别[J]. 计算机科学, 2019, 46(6A): 192-195.
[11] 侯媛媛, 何儒汉, 李敏, 陈佳. 结合卷积神经网络多层特征融合和K-Means聚类的服装图像检索方法[J]. 计算机科学, 2019, 46(6A): 215-221.
[12] 李建军, 侯跃, 杨玉. 基于情景感知的用户兴趣推荐模型[J]. 计算机科学, 2019, 46(6A): 502-506.
[13] 黄海燕, 刘晓明, 孙华勇, 杨志才. 聚类分析算法在不确定性决策中的应用[J]. 计算机科学, 2019, 46(6A): 593-597.
[14] 刘紫熠, 刘卿, 王崇, 王季孟, 王玥, 刘金硕, 殷泽豪. 基于智能电表运行故障数据的纵向分析模型[J]. 计算机科学, 2019, 46(6A): 436-438.
[15] 钟熙, 孙祥娥. 基于Kmeans++聚类的朴素贝叶斯集成方法研究[J]. 计算机科学, 2019, 46(6A): 439-441.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .