基于结构系数的K-means初始聚类中心选择算法.pdf

2023 年第 5 期计算机与数字工程收稿日期：2022年11月7日，修回日期：2022年12月10日基金项目：广东省大学生创新创业项目“基于图像变换与压缩算法的荔枝损伤研究”（编号：S202010564034）；华南农业大学微达安产业学院项目资助。作者简介：李汉波，男，研究方向：机器学习与数据挖掘。魏福义，男，硕士，教授，研究方向：组合矩阵论和人工智能。张嘉龙，男，研究方向：人工智能。刘志伟，男，研究方向：人工智能。黄杰，男，研究方向：统计应用。方月宜，女，研究方向：应用数学。1引言聚类分析是数据挖掘中的一个重要研究领域。聚类算法是衡量数据相似性的典型算法，它以“物以类聚”的思想，在文档分析、图像压缩1、特征提取、图像分割等领域得到广泛的应用。MacQueen于1967年首次提出K-means算法，它基于样本间相似度对数据进行划分，具有聚类效果好和收敛速度快等特点，属硬聚类算法2。传统K-means算法随机选取初始聚类中心会导致聚类结果不稳定3。为了削弱初始聚类中心选取的随机性对聚类结果不稳定的影响，研究确定初始聚类中心的有效方法具有重要意义。一个好的聚类算法具备各类中包含的样本点彼此相似，并且聚类中心在空间分布上尽量分散4的特征，这样才能更好地让每一类体现不同于其他类的特性。确定聚类中心和数据分类问题一直是大数据研究的热点内容512。文献 13 运用了相异度的概念，通过构造相异度矩阵，选取K个与其他样本相异度较低且聚类个数最多的样本作为初始总第 403期2023 年第 5期计算机与数字工程Computer&Digital EngineeringVol.51No.5基于结构系数的 K-means 初始聚类中心选择算法李汉波魏福义张嘉龙刘志伟黄杰方月宜（华南农业大学数学与信息学院广州510642）摘要传统的K-means算法选取初始聚类中心时的不确定性会导致聚类结果不稳定。论文提出了基于相异度的邻域及其结构系数的概念，从最小的结构系数开始，按照其递增顺序寻找初始聚类中心；随后采用依次缩小邻域的技巧逐步探索，直到找到K个初始聚类中心。该方法同时得到li（i=0，1，2，q）个初始聚类中心及其对应的数据分类结果。实验证明，对比于以往的算法，新算法具有更高的分类准确率以及更少的迭代次数。关键词K-means聚类；相异度；初始聚类中心；结构系数中图分类号TP31DOI：10.3969/j.issn.1672-9722.2023.05.003Algorithm for Selecting K-means Initial Clustering CentersBased on the Structure CoefficientLI HanboWEI FuyiZHANG JialongLIU ZhiweiHUANG JieFANG Yueyi（College of Mathematics and Information，South China Agricultural University，Guangzhou510642）AbstractThe uncertainty in selecting initial clustering centers usually leads to unstable clustering results of the traditionalK-means method.This paper proposes a new concept of neighborhood and structure coefficients based on dissimilarity.This algorithm looks for the initial clustering centers in order of ascending structure coefficients，starting from the neighborhood with thesmallest coefficient.The above procedure is repeated with the neighborhood reduced until the K initial clustering centers are found.By the proposed algorithm，it can finally obtain li（i=0，1，2，q）initial clustering centers and the corresponding data classificationresults.Experiments show that this algorithm achieves higher classification accuracy and needs less number of iterations than the existing algorithms.Key WordsK-means clustering，dissimilarity，initial cluster centers，structure coefficientsClass NumberTP31993第 51 卷聚类中心，该算法削弱了传统算法对初始聚类中心的敏感性，在传统算法的基础上具有更高的分类准确率。文献 14 在文献 13 的基础上增加了一个判断，当最大相异度参数不唯一时，提出了一种合理选取最大相异度参数值的解决方案，改进算法与文献 13 的算法在准确率和迭代次数方面有所优化。而文献 15 提出了一种基于最大距离中位数及误差平方和（SSE）的自适应改进算法，通过SSE变化趋势决定终止聚类或继续簇的分裂。本文算法基于文献 13 的相异度概念，定义一个可变邻域参数，从最小结构系数开始，按结构系数递增的顺序寻找初始聚类中心，直到找到 K 个初始聚类中心。本文实验表明：采用新方法构造的算法相比文献 13、文献 14 以及文献 15 具有更高的准确率和更少的迭代次数。2改进的选取初始聚类中心算法首先给出基于相异度的四个新概念，在此基础上推导改进的K-means选取初始聚类中心的新方法，最后得到基于结构系数的新算法。2.1基本概念设待聚类样本数据：X=x1x2x3xn，其中xi=xi1xi2xi3xim，n为数据集中的样本数，m为样本属性的个数。采用三个步骤计算样本间相异度并构造相异度矩阵13：1）计算不同样本的第 s 个属性的相异度：r(s)ij=|xis-xjsmaxxrs-minxrs，ij12n，其 中r(s)ij表示样本xi与xj之间第s个属性的相异度，xrs为第s个属性的所有取值；2）计算不同样本的相异度：rij=s=1mr(s)ij，其中rij表示样本xi与xj之间的相异度；3）构造相异度矩阵：R=0r12r13 r1nr210r22 r2nr31r320 r3nrn1rn2rn30记Ri=ri1ri2rii-1rii+1rin，其 中 i=1，2，n。定义1 对于样本xi和邻域参数，从Ri中任意取-1个元素求和，和最小的值称为样本xi的邻域的结构系数，记为D（，xi）。定义 2 设-rijR，若j=1-1-rij和最小，则-rij对应的样本xj(j=12-1)和xi组成的集合称为样本xi的邻域，记为U（，xi）；U（，xi）中的样本称为邻域的内点。在参数确定的条件下，样本xi对应于结构系数D（，xi）和邻域U（，xi）。定义3 对于样本集X=x1x2x3xn，集合D(x1)D(x2)D(xn)称为对应参数的结构系数集合，记为M（）。定义4 数min1inD(xi)称为对应参数的最小结构系数，记为D（）。由定义2和定义4可知，最小结构系数D（）对应含有个样本最密集的邻域。对于样本集X，若要选取K个聚类中心，则nK，其中nK表示数nK取下整。2.2算法思想本文从=nK出发，计算并确定D（）及其对应的邻域U（，xi），逐步寻找初始聚类中心。遴选K个初始聚类中心的方法：1）首先采用三个步骤构造出相异度矩阵，以及计算邻域的结构系数集合M（）；2）计算M（）的最小结构系数D（），其对应的样本不妨设为xi，将样本xi作为第一个初始聚类中心，同时标记其邻域U（，xi）的内点，并将其结构系数都设置为，记新的结构系数集合为M1（）；3）选取M1（）中最小结构系数D（），其对应的样本不妨设为xj，将样本xj作为候选点。若邻域U（，xj）的内点均没有被标记，则选取xj作为下一个初始聚类中心，并标记其所有内点，同时将内点的结构系数设置为。否则，将D（，xj）设为，随后选取M1（）中最小的元素对应的样本作为候选点；4）反复进行以上判断直至所有样本的结构系数都为，此时得到的初始聚类中心个数记为l0；5）若l0K，则选择前K个候选点为初始聚类中心；若l0K，则清空初始聚类中心和内点标记；6）缩小邻域参数，循环以上方法，直到选出K个初始聚类中心。根据以上分析，得到算法的流程图如图 1 所示。按照上述算法流程，设参数=nK缩小 q 次李汉波等：基于结构系数的K-means初始聚类中心选择算法9942023 年第 5 期计算机与数字工程后，即=nK-q时，得到K个初始聚类中心，与其对应的K个邻域表示对数据集X的K个分类结果。设分别取nKnK-1nK-inK-lq时，得到的初始聚类中心个数依次为l0l1liK，按照新算法，同时得到li=(i=01q)个初始聚类中心和相应数据聚类结果。图 1算法流程图3实验结果与分析以常用的五个UCI数据集为实验数据，将本文算法与文献 5、文献 6 和文献 7 的算法进行对比实验，验证新算法的有效性。3.1实验数据集UCI数据集作为标准数据集，经常用于测试机器学习算法的性能，为了验证以上算法选取初始聚类中心的有效性，本文采用UCI数据集中的Diabetes数据集、Iris数据集、Harbeman数据集、Wine数据集和Seed数据集作为实验数据集，数据集详细信息如表1所示。表 1实验数据集描述信息数据集DiabetesIrisHabermanWineSeed样本数量768150306178210属性维度843137分类数23233每类样本数268，50050，50，50225，8159，71，4870，70，70由 于 Diabetes 数 据 集、Haberman 数 据 集 和Wine数据集各维度属性取值范围差异较大，先对这三个数据集进行零-均值规范化，以便消除属性差异对聚类性能的影响。对于每一维度属性，有如下计算公式：x*i=xi-xii其中，-xi为样本数据第i维属性的均值，i为样本数据第i维属性的标准差。3.2聚类效果评价指标衡量聚类算法性能的评价指标有许多种，本文选用准确度和迭代次数作为判定聚类算法性能优劣的指标。设数据要求分为K类，则准确度的计算公式14如下：MP=i=1Kin其中n为样本总量，i表示被正确划分为第i类的样本数量，MP值越接近1，表示聚类效果越好。对于数据集要求分为K类，在保证准确度前提下，迭代次数越少越好。3.3实验结果和分析表2表6分别是文献 13、14、15 算法和本文算法在5个UCI数据集上的对比实验。表2Diabetes数据集的实验结果文献 13 算法文献 14 算法本文算法准确率/%66.3268.4571.35迭代次数979在 Diabetes 数据集中，使用本文算法改进的K-means算法的准确率最高，为71.35%。虽然在迭995第 51 卷代次数方面略微高于文献 14 算法，但与文献 13算法持平。由此可见，本文算法对于Diabetes数据集聚类性能具有改良效果。表3Iris数据集的实验结果文献 13 算法文献 14 算法文献 15 算法本文算法准确率/%89.3389.3389.3389.33迭代次数4274对 于 Iris 数 据 集，本 文 算 法 的 准 确 率 为89.33%，准确率效果与文献 13、14、15 的算法持平。在迭代次数方面，本文算法与文献 13 算法性能相同，相比文献 15 迭代次数减少3次，但略逊于文献 14 算法。表4Haberman数据集的实验结果文献 13 算法文献 14 算法本文算法准确率/%74.5175.4974.84迭代次数865在Haberman数据集中，虽然本文算法在准确度方面略低于文献 14 算法，但略高于文献 13 算法。且本文算法的迭代次数为5，均低于文献 13和文献 14 算法的迭代次数。表5Wine数据集的实验结果文献 13 算法文献 14 算法本文算法准确率/%97.1997.1994.94迭代次数864在Wine数据集中，本文算法在准确度方面略逊于文献 13、14 算法，但相对于文献 13、14算法，本文算法的迭代次数较小，收敛速度快。因此，本文算法对于Wine数据集的改进性能可以接受。表6算法在Seed数据集的实验结果文献 15 算法本文算法准确率/%89.5289.52迭代次数83在Seed数据集中，对比于文献 15 算法，本文算法能取得相同的准确率，且本文算法的迭代次数为3，远低于文献 15 算法。由表 2表 6 的实验结果可见，相比于文献13、14、15 算法，本文算法均能取得较为良好的聚类效果。4结语K-means算法应用广泛，但由于其选取初始聚类中心的随机性，会导致聚类结果不稳定。针对这一缺陷，本文提出邻域及其结构系数的概念，在充分考虑数据集的整体分布后，结合数据集的局部密集程度和样本的相异度这两个性质，选取周围密集程度较大且相距较远的样本作为初始聚类中心，采用依次缩小邻域的方法，逐个找出K个不同的初始聚类中心。同时，本文给出了一种数据聚类新方法，不仅得到数据集的K个初始聚类中心，而且还得到了li=(i=01q-1)个初始聚类中心及其对应的数据分类。实验结果表明，新方法有效地削弱了传统K-means算法选取初始聚类中心的盲目性，改进后的算法提高了准确度和减少了迭代次数，具有准确性高和收敛速度快的聚类效果。参 考 文 献1谢小军，苏涛.基于矢量量化压缩密集连接层的图像压缩研究 J.信息技术，2020，44（04）：97-101，106.XIE Xiaojun，SU Tao.Image compression based on vectorquantization compression dense connection layer J.Information Technology，2020，44（04）：97-101，106.2杜洪波，白阿珍，朱立军.基于改进的密度峰值算法的K-means算法 J.统计与决策，2018，34（18）：20-24.DU Hongbo，BAI Azhen，ZHU Lijun.K-means AlgorithmBased on Improved Density Peak Algorithm J.Statisticsand decision，2018，34（18）：20-24.3张靖，段富.优化初始聚类中心的改进 k-means 算法J.计算机工程与设计，2013，34（05）：1691-1694，1699.ZHANG Jing，DUAN Fu.Improved K-means algorithmwith meliorated initial centersJ.Computer Engineeringand Applications，2013，34（05）：1691-1694，1699.4刘一鸣，张化祥.可变阈值的K-Means初始中心选择方法 J.计算机工程与应用，2011，47（32）：56-58.LIU Yiming，ZHANG Huaxiang.Approach to selectinginitial centers for K-Means with variable thresholdJ.Computer Engineering and Applications，2011，47（32）：56-58.5刘广聪，黄婷婷，陈海南.改进的二分K均值聚类算法J.计算机应用与软件，2015，32（02）：261-263，277.LIU Guangcong，HUANG Tingting，CHEN Hainan.Improved Bisecting K-means Clustering Algorithm J.Com（下转第1107页）李汉波等：基于结构系数的K-means初始聚类中心选择算法9962023 年第 5 期计算机与数字工程8TU C C，YANG C，LIU Z Y，et al.Network representation learning：an overviewJ.Scientia Sinica Informations，2017，47（8）：980-996.9蒋宗礼，李苗苗，张津丽.基于融合元路径图卷积的异质网络表示学习J.计算机科学，2020，47（07）：231-235.JIANG Zongli，LI Miaomiao，ZHANG Jinli.Graph Convolution of Fusion Meta-path Based Heterogeneous NetworkRepresentation Learning J.Computer Science，2020，47（07）：231-235.10Mikolov T，Sutskever I，Chen K，et al.Distributed representations of words and phrases and their compositionalityJ.Advances in Neural Information Processing Systems，2013，26：3111-3119.11Mikolov T，Chen K，Corrado G，et al.Efficient estimation of word representations in vector spaceJ.ArXivPreprint ArXiv：1301.3781，2013.12Tang J，Qu M，Wang M，et al.Line：Large-scale information network embedding C/Proceedings of the 24thInternational Conference on World Wide Web，2015：1067-1077.13Grover A，Leskovec J.node2vec：Scalable feature learning for networks C/Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining，2016：855-864.14Dong Y，Chawla N V，Swami A.metapath2vec：Scalable representation learning for heterogeneous networksC/Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2017：135-144.15Wang H，Wang J，Wang J，et al.Graphgan：Graph representation learning with generative adversarial nets C/Proceedings of the AAAI Conference on Artificial Intelligence，2018：2508-2515.puter Applications and Software，2015，32（02）：261-263，277.6胡伟.改进的层次K均值聚类算法 J.计算机工程与应用，2013，49（02）：157-159.HU Wei.Improved hierarchical K-means clustering algorithm J.Computer Engineering and Applications，2013，49（02）：157-159.7李金涛，艾萍，岳兆新，等.基于K-means聚类算法的改进 J.国外电子测量技术，2017，36（06）：9-13，21.LI Jintao，AI Ping，YUE Zhaoxin，et al.Improvement ofclustering algorithm based on K-means J.Foreign Electronic Measurement Technology，2017，36（06）：9-13，21.8王勇，唐靖，饶勤菲，等.高效率的K-means最佳聚类数确定算法 J.计算机应用，2014，34（05）：1331-1335.WANG Yong，TANG Jing，RAO Qinfei，et al.High efficient K-means algorithm for determining optimal numberof clusters J.Journal of Computer Applications，2014，34（05）：1331-1335.9熊开玲，彭俊杰，杨晓飞，等.基于核密度估计的K-means 聚类优化 J.计算机技术与发展，2017，27（02）：1-5.XIONG Kailing，PENG Junjie，YANG Xiaofei，et al.K-means Clustering Optimization Based on Kernel Density EstimationJ.Computer Technology and Development，2017，27（02）：1-5.10Jahangoshai Rezaee Mustafa，Eshkevari Milad，SaberiMorteza，et al.GBK-means clustering algorithm：An improvement to the K-means algorithm based on the bargaining game J.Research Gate，2021，213：106672.11Benchara Fatma Zahra，Youssfi Mohamed.A new scalable distributed k-means algorithm based on Cloud micro-services for High-performance computing J.Parallet Computing，2021，101：102736.12王艳娥，梁艳，司海峰，等.基于K-means算法的最佳聚类数研究 J.电子设计工程，2020，28（24）：52-56.WANG Yane，LIANG Yan，SI Haifeng，et al.Researchon the best clustering number based on K-means algorithmJ.Electronic Design Engineering，2020，28（24）：52-56.13孟子健，马江洪.一种可选初始聚类中心的改进k均值算法 J.统计与决策，2014（12）：12-14.MENG Zijian，MA Jianghong.An improved K-means algorithm with selectable initial clustering centers J.Statistics and decision，2014（12）：12-14.14董秋仙，朱赞生.一种新的选取初始聚类中心的K-means算法 J.统计与决策，2020，36（16）：32-35.DONG Qiuxian，ZHU Zansheng，A New K-means Algorithm for Selecting Initial Clustering CenterJ.Statistics and Decision，2020，36（16）：32-35.15曹端喜，唐加山，陈香.一种优化初始聚类中心的自适应聚类算法 J.软件导刊，2020，19（07）：28-31.CAO Duanxi，TANG Jiashan，CHEN Xiang.An Adaptive Clustering Algorithm by Optimizing Initial Clustering CentersJ.Software Guide，2020，19（07）：28-31.（上接第996页）1107