基于密度和中心指标的Canopy二分K-均值算法优化

摘要/Abstract

摘要： 针对二分K-均值算法由于随机选取初始中心及人为定义聚类数而造成的聚类结果不稳定问题，提出了基于密度和中心指标的Canopy二分K-均值算法SDC_Bisecting K-Means。首先计算样本中数据密度及其邻域半径；然后选出密度最小的数据并结合Canopy算法的思想进行聚类，将得到的簇的个数及其中心作为二分K-均值算法的输入参数；最后在二分K-均值算法的基础上引入指数函数和中心指标对原始样本进行聚类。利用UCI数据集和自建数据集进行模拟实验对比，结果表明SDC_Bisecting K-Means不仅使得聚类结果更精确，同时算法的运行速度更快、稳定性更好。

关键词: 聚类, 二分K-均值算法, 密度, 邻域半径, 指数函数, 中心指标

Abstract: Aiming at the problem of unstable clustering results caused by the random selection of initial centers and artificially defining the number of clusters in the bisecting K-means algorithm, a Canopy bisecting K-means algorithm based on density and center index is proposed. Firstly, the algorithm calculates the data density in the sample and its neighborhood radius. Secondly, the data with the smallest density are selected and the ideas of the Canopy algorithm is combined for clustering. The number of clusters and cluster centers are obtained as the input parameters of the bisecting K-means algorithm. Finally, based on the bisecting K-means algorithm, the exponential function and central index are introduced to cluster the original samples. UCI data set and self-built data set were used to compare simulation experiments. The results show that the algorithm not only makes the clustering results more accurate and faster, but also has better stability.

Key words: clustering, bisecting K-Means algorithm, density, neighborhood radius, exponential function, central index

沈郭鑫, 蒋中云. 基于密度和中心指标的Canopy二分K-均值算法优化[J]. 计算机工程与科学, 2022, 44(02): 372-380.

SHEN Guo-xin, JIANG Zhong-yun. A Canopy bisecting K-Means algorithm based on density and central index[J]. Computer Engineering & Science, 2022, 44(02): 372-380.

参考文献［21］

［1］	Aguwa C,Olya M H,Monplaisir L.Modeling of fuzzy-based voice of customer for business decision analytics［J］.Knowledge Based Systems,2017,125:136-145.
［2］	Tang J L,Zhang Z G,Wang D,et al.Research on weeds identification based on K-means feature learning［J］.Soft Com- puting,2018,22(22):7649-7658.
［3］	Vinodhini G, Chandrasekaram R M. A sampling based sentiment mining approach for e-commerce applications［J］.Information Processing & Management,2017,53(1):223-236.
［4］	Yoo I, Hu X H. A comprehensive comparison study of document clustering for a biomedical digital library MEDLINE［C］∥Proc of the 6th ACM/IEEE-CS Joint Conference on Digital Libraries,2006:220-229．
［5］	Silva J D A，Hruschka E R.Extending k-means-based algorithms for evolving data streams with variable number of clusters［C］∥Proc of International Conference on Machine Learning and Applications and Workshops ( ICMLA),2011:14-19．
［6］	Jiang Li,Xue Shan-liang. A K-means algorithm based on optimizing the initial clustering center and determining the K value ［J］.Computer & Digital Engineering,2018,46(1):21-24.(in Chinese)
［7］	Rezaee M R,Lelieveldt B P F,Reiber J H C．A new cluster validity index for the fuzzy C-means［J］.Pattern Recognition Letters,1998,19(3):237-246．
［8］	Xie Juan-ying, Qu Ya-nan.K-medios clustering algorithms with optimized initial seeds by density peak［J］. Journal of Frontiers of Computer Science & Technology,2016,10(2):230-247.(in Chinese)
［9］	Guo Wei-xia，Xue Tao，Li Ting. Analysis of student score and graduation destination based on Hadoop′s Canopy-K-means parallel algorithm［J］. Journal of Xi'an Polytechnic University,2018,32(6):705-712. (in Chinese)
［10］	Qiu Guo-yong， Zhang Jiao. Adaptive SVM decision tree classification algorithm based on bisecting K-means［J］. Application Research of Computers,2012,29(10)：3685-3687. (in Chinese)
［11］	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,2000:525-526.
［12］	Chen Sheng-fa，Jia Rui-yu. An improved K-medoids algorithm based on density weight Canopy［J］. Computer Engineering & Science,2019,41(10):1823-1828. (in Chinese)
［13］	Zhao Xin，Wang Li-juan，Xing Yan-ni，et al. Optimization and parallel strategy of improved CK-means［J］. Application Research of Computers，2020，37(11)：3287-3291. (in Chinese)
［14］	Xie Juan-ying，Guo Wen-juan，Xie Wei-xin，et al. K-means clustering algorithm based on optimal initial centers related to pattern distribution of samples in space［J］. Application Research of Computers,2012,29(3):888-892. (in Chinese)
［15］	Xie Juan-ying，Jiang Shuai，Wang Chun-xia，et al. An improved global K-means clustering algorithm［J］. Journal of Shaanxi Normal University(Natural Science Edition),2010,38(2):18-22. (in Chinese)
［16］	Zhang Tian,Yin Chang-chuan,Pan Lin,et al. Score analysis of undergraduate students based on improved clustering and association rules mining［J］. Journal of Beijing University of Posts and Telecommunications (Social Sciences Edition),2018,20(2):91-96. (in Chinese)
［17］	Chakraborty S, Das S. k-Means clustering with a new divergence-based distance metric:Convergence and perfor- mance analysis［J］.Pattern Recognition Letters,2017,100:67-73.
［18］	Abuaiadah D.Using bisect k-means clustering technique in the analysis of Arabic documents［J］.ACM Transactions on Asian and Low-Resource Language Information Processing,2016,15(3):1-13.
［19］	Wang Jian-ren， Ma Xin， Duan Gang-long. Improved K-means clustering k-value selection algorithm［J］. Computer Engineering and Applications,2019,55(8):27-33. (in Chinese)
［20］	Tang Ze-kun，Zhu Ze-yu，Yang Yi，et al. d-K-means algorithm based on distance and density［J］. Application Research of Computers，2020，37(6)：1719-1723. (in Chinese)
［21］	Yang Yan， Jin Fan，Kamel M. Survey of clustering validity evaluation［J］. Application Research of Computers,2008,25(6):1630-1632. (in Chinese)
［22］	Hubert L,Arabie P.Comparing oartitions ［J］.Journal of Classification,1985,2(1):193-218.
［23］	Vinh N H,Epps J,Nailey J.Information theoretic measures for clusterings comparision:Is a correction for chance necessary?［C］∥Proc of the 26th Annual International Confe- rence on Machine Learning,2009:1073-1080.
	附中文参考文献：
［6］	蒋丽,薛善良.优化初始聚类中心及确定K值的K-means算法［J］.计算机与数字工程,2018,46(1):21-24.
［8］	谢娟英，屈亚楠．密度峰值优化初始中心的K-medios聚类算法［J］.计算机科学与探索,2016,10(2):230-247.
［9］	郭卫霞,薛涛,李婷.基于Hadoop的Canopy-K-means并行算法的学生成绩与毕业流向关系分析［J］.西安工程大学学报,2018,32(6):705-712.
［10］	裘国永,张娇.基于二分K-均值的SVM决策树自适应分类方法［J］.计算机应用研究,2012,29(10):3685-3687.
［12］	陈胜发,贾瑞玉.基于密度权重Canopy的改进K-medoids算法［J］.计算机工程与科学,2019,41(10):1823-1828.
［13］	赵鑫,汪丽娟,行艳妮,等.
	改进的CK-means优化及并行策略［J］.计算机应用研究,2020,37(11):3287-3291.
［14］	谢娟英,郭文娟,谢维信,等.基于样本空间分布密度的初始聚类中心优化K-均值算法［J］.计算机应用研究,2012,29(3):888-892.
［15］	谢娟英,蒋帅,王春霞,等.一种改进的全局K-均值聚类算法［J］.陕西师范大学学报(自然科学版),2010,38(2):18-22.
［16］	张甜,尹长川,潘林,等.基于改进的聚类和关联规则挖掘的学生成绩分析［J］.北京邮电大学学报(社会科学版),2018,20(2):91-96.
［19］	王建仁,马鑫,段刚龙.改进的K-means聚类k值选择算法［J］.计算机工程与应用,2019,55(8):27-33.
［20］	唐泽坤,朱泽宇,杨裔,等.基于距离和密度的d-K-means算法［J］.计算机应用研究,2020,37(6):1719-1723.
［21］	杨燕,靳蕃,Kamel M.聚类有效性评价综述［J］.计算机应用研究,2008,25(6):1630-1632.

[1]	陈彪, 陈才, 张坤, 叶琴. FCBGA封装的CPU芯片散热性能影响因素研究[J]. 计算机工程与科学, 2023, 45(03): 406-410.
[2]	李超, 涂国庆, . 高密度LoRa网络优化方法研究[J]. 计算机工程与科学, 2023, 45(03): 426-433.
[3]	李帅, 常锦才, 李吕牧之, 蔡昆杰, . 基于差分隐私保护的Stacking集成聚类算法研究[J]. 计算机工程与科学, 2022, 44(08): 1402-1408.
[4]	李兰, 刘杰, 张洁. 基于YOLOv4改进算法的复杂行人检测模型研究[J]. 计算机工程与科学, 2022, 44(08): 1449-1456.
[5]	陈奉贤. 基于NR-Transformer的集群作业运行时间预测[J]. 计算机工程与科学, 2022, 44(07): 1181-1190.
[6]	庞兴龙, 朱国胜, 杨少龙, 李修远. 一种基于聚类与噪声的网络流量分类方法[J]. 计算机工程与科学, 2022, 44(07): 1207-1215.
[7]	黄志强, 李军, 张世义. 基于轻量级神经网络的目标检测研究[J]. 计算机工程与科学, 2022, 44(07): 1265-1272.
[8]	刘榕, 伍欣, 敖斌, 文青, 李宽. 用于CD56图像分割的细胞标注精细化与自适应加权损失[J]. 计算机工程与科学, 2022, 44(05): 870-878.
[9]	刘云, 肖添, 王梓宇. 动态特征选择算法对恶意行为检测的优化研究[J]. 计算机工程与科学, 2022, 44(04): 665-673.
[10]	袁泉, 晏飞扬, 文志云, 张振康, . 基于谱聚类的社交网络差分隐私保护算法研究[J]. 计算机工程与科学, 2022, 44(02): 251-256.
[11]	许光宇, 丁健. 基于特征聚类的大视差图像拼接算法 [J]. 计算机工程与科学, 2022, 44(02): 283-290.
[12]	颜廷龙, 李瑛, 王凤芹. 基于MRF模型的飞机飞行动作识别划分算法[J]. 计算机工程与科学, 2022, 44(01): 159-164.
[13]	苏小会, 张玉西, 徐淑萍, 尚煜. 改进K-means聚类算法行驶工况及油耗研究[J]. 计算机工程与科学, 2021, 43(11): 2020-2026.
[14]	谢挺, 刘瑞华, 魏正元. 一类连续的K-means 等价聚类模型及其优化算法[J]. 计算机工程与科学, 2021, 43(11): 2077-2083.
[15]	阎红灿, 王子茹, 李伟芳, 谷建涛. 伴随时间的模糊聚类协同过滤推荐算法[J]. 计算机工程与科学, 2021, 43(11): 2084-2090.