一种服务于K-means的初始中心选取方法_李秋云.pdf

www.ChinaAET.comComputer Technology and Its Applications计算机技术与应用一种服务于 K-means 的初始中心选取方法李秋云1，刘燕武2（1.中国运载火箭技术研究院 北京宇航系统工程研究所，北京 100076；2.中国电子信息产业集团有限公司，广东 深圳 518000）摘 要：聚类是数据挖掘领域最重要的技术之一，K-means 是其中使用频率最高的举足轻重的聚类算法。然而，K-means 算法表现严重依赖于初始中心，选取多少个初始中心以及选择哪些数据点作为初始中心对 K-means 算法十分重要。基于此，提出一种初始中心选取方法 DPCC（Density Peak Clustering Centers）。DPCC 方法基于密度和距离生成一个选取决策图，将数据集中所有的密度峰值点凸显出来。这些密度峰值点即为 DPCC 方法为 K-means 算法提供的初始中心。实验表明，DPCC 方法不仅可为 K-means 提供初始中心数量，还能有效提高 K-means 算法的准确度，并缩减 K-means 算法的执行时间。关键词：聚类；初始中心；决策图中图分类号：TP3-0 文献标志码：A DOI:10.16157/j.issn.0258-7998.223066中文引用格式：李秋云，刘燕武.一种服务于 K-means 的初始中心选取方法J.电子技术应用，2023，49(3)：134-138.英文引用格式：Li Qiuyun，Liu Yanwu.An initial centers selection method serving K-meansJ.Application of Electronic Technique，2023，49(3)：134-138.An initial centers selection method serving K-meansLi Qiuyun1，Liu Yanwu2(1.Beijing Institute of Astronautical Systems Engineering，China Academy of Launch Vehicle Technology，Beijing 100076，China；2.China Electronics Corporation，Shenzhen 518000，China)Abstract：Clustering is one of the most important data mining technologies,and K-means is the most famous and commonly used clustering algorithm.However,the performance of K-means depends heavily on the initial centers.It is very important for K-means to select how many initial centers and which data points to choose as the initial centers.Therefore,an initial centers selection method called DPCC(density peak clustering centers)is proposed.DPCC generates a selection decision graph based on density and distance,so as to highlight all density peak points in dataset.These density peak points are the initial centers provided by DPCC for K-means.Experiments show that DPCC not only provides decision support for the number of initial centers,but also improves the accuracy of K-means and reduces the running time of K-means.Key words：clustering；initial centers；decision graph0 引言聚类是一种无监督分析方法，其目的是识别出数据集中的所有数据簇，并将每个簇中的数据点看作一类。在众多聚类算法中，K-means1是使用频率最高的举足轻重的算法之一。K-means 算法从数据集中选取 k 个数据点作为初始聚类中心，按照距离最近原则，将其他数据点分配给这 k 个初始中心得到初始簇，再将处于初始簇中心的数据点作为新的聚类中心。重复上述过程，直到聚类中心不再改变为止。K-means 算法的原理相对简单，这也是其受到广泛追捧的原因。然而，该算法也存在着明显缺陷：（1）分析之前，需要明确 k 值。在 K-means 算法中，k值就是簇的数量。若 k 被设置为 10，那么 K-means 算法将识别出 10 个数据簇。但聚类是一种无监督分析任务，在聚类之前无法得知数据集存在多少簇。显然，K-means 算法的机理与聚类初衷是相矛盾的。在真实分析场景中，常常会出现 k 值多于或少于真实簇数的情况，影响聚类准确度。（2）初始中心易聚团。K-means 算法随机将 k 个数据点确定为初始聚类中心，易造成多个聚类中心出现在134Computer Technology and Its Applications计算机技术与应用电子技术应用 2023年 第49卷 第3期同一簇内，导致该簇被分解为多类。（3）迭代次数无法控制。K-means 算法需要经过多次迭代直至聚类中心不再改变为止。通常情况下，聚类中心最终会迭代到密度稠密区。也就是说，初始中心越远离密度核心，K-means 算法的迭代次数越多，运行时间越长。又因初始中心是随机选取的，致使 K-means 算法的运行时间无法控制。针对上述问题，本文提出一种名为 DPCC（Density Peak Clustering Centers）的方法，为 K-means 算法提供初始中心。DPCC 运用于 K-means 算法之前，通过计算数据点密度以及与高密度数据点间最近距离生成决策图，以凸显数据集中所有的密度峰值点。这些密度峰值点即可作为 K-means 算法的初始中心。结合 DPCC 方法后，K-means 算法有 3 大优势：（1）提供 k 值依据。决策图可以凸显出簇的数量。实验显示，该数量与真实簇的数量保持一致。（2）初始中心相互远离。决策图凸显的密度峰值点不会出现聚团。实验显示，峰值点作为初始中心可大幅提升 K-means 算法的准确度。（3）缩减迭代次数。由于密度峰值点本身就在密度核心区，使 K-means 算法的迭代次数可以控制在 12 次内，算法运行时间大幅缩减。1 相关技术近几年，聚类相关研究快速发展。自聚类任务出现以来，迄今为止已有上千种聚类算法被相继提出。这些算法可分为多个分支，如基于中心、基于密度、基于网络和基于层次。基于中心的聚类算法不直接识别簇，而是首先识别聚类中心。这类算法认为聚类中心是待分析数据集中最具代表的点，可以代表数据集中剩余的数据点。在识别出所有聚类中心后，这类算法会根据相应的分配原则将其他数据点分配到各个聚类中心所代表的簇中，以得到聚类结果。这类算法的聚类过程通常较为简单，但缺点也十分明显，即需要事先指定簇的数量。本文关注的K-means 是最经典的中心聚类算法，常见的基于中心聚类算法还有 BK-means2、PQK-means3等。基于密度的聚类算法通常根据数据点密度差异识别簇，这类算法在准确度上常比基于中心的聚类算法更高，但调参较为复杂，不适用于真实且复杂的分析场景。一般情况下，簇核心密度远高于簇边界数据点。基于此，密度聚类算法认定被低密度数据点包围的高密度区域为一个簇。DBSCAN4是最著名的密度聚类算法。该算法将高密度数据点定义为核心点，将核心点邻域内数据点间的关系定义为直接密度可达，该可达关系具有传递性。被直接密度可达传递连接的数据点则称之为密度可达。它将具有密度可达关系的数据点识别为一类，并将与其核心点具有非密度可关系的离散点识别为异常。常见基于密度的聚类算法还有OPTICS5、DENCLUE6、FIDC7等。基于网络的聚类算法近几年逐渐兴起。这类算法通常将神经网络与聚类原理相结合，在训练网络的过程中逐渐实现聚类损失最小化。由于神经网络具有较好的特征学习能力，这类算法在图像数据集上具有较好表现。但是这类算法对计算硬件要求较高，且缺乏可解释性。MIXAE8算法是一个极具代表性的网络聚类算法。该算法镶嵌了 k 个卷积自编码网络，k 为簇的数量。通过不断训练该网络，k 个网络的参数逐渐出现差异化。该算法认为待分析数据集中每个簇中的数据点特征不同，它们之间的差异可以表现在卷积自编码网络的参数上，因此将偏向同一网络参数的数据点认定为一个簇。常 见 基 于 网 络 的 聚 类 算 法 还 有 DLNC9、DSCN10、DGMM11、AGCN12、DeepCluster13等。基于层次的聚类算法同样不直接聚类，而是以嵌套的形式递归得到聚类结果。AGNES14是最经典的层次聚类算法，它将每个数据点看作一个簇得到初始层结果，通过寻找最近的 2 个簇进行合并得到第 2 层结果。再按照上述方法不断合并，直到所有数据点被合并为 1个簇。最终，AGNES 的聚类过程被保存在一个层次结构中，该结构的切面即可作为聚类结果。尽管这类算法实现简单，但选择哪个结果层尚未有一个可以满足所有数据集的合理依据，在真实场景中实操性较差。常见基于 层 次 的 聚 类 算 法 还 有 HDBSCAN15、FINCH16、BIRCH17等。2 原理本文借鉴 DPC18算法，提出了 DPCC 方法来解决 K-means 算法的缺陷。DPCC 的核心思想是识别出待分析数 据 集 中 的 密 度 峰 值 点，然 后 将 密 度 峰 值 点 作 为 K-means 算法的初始聚类中心。众所周知，密度峰值点在局部区域内一定拥有最大密度。因此，密度峰值点有两个特征，一是密度较大，二是与其他大密度点距离较远。为了让计算机理解该特征，需要构建两个指标去量化它们。这两个指标分别为数据点密度以及与更高密度数据点的最近距离。其中，数据点i密度i被定义为：i=j(dij-dc)（1）式中，如果x i dij（2）定义了这两个指标后，计算机即可将那些i和i值135Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com明显大于其他数据点的数据点认定为密度峰值点。但怎么才是“明显大”呢？又或者说，超过什么阈值，i和i才能称之为“大”呢？一个有效的途径是将所有数据点根据各自的i和i值置于一个横坐标为、纵坐标为的图中，该图被称为决策图。在决策图中，密度峰值点与普通点表现出明显差异。由于密度峰值点的i和i值都较大，它们一定会出现在决策图的右上角区域。而普通数据点的i或i值较小，它们只能出现在坐标轴附近。基于此，就可以轻易识别出所有的密度峰值点。3 实验本节将通过实验展示 DPCC 方法的优势，并将原始K-means 与结合 DPCC 方法的 K-means 进行了比较。3.1 k 值确定效果正如上文所述，K-means 算法的一个主要弊端是在聚类之前需要确定簇的数量（即 k 值），而本文提出的DPCC 可协助 K-means 获得正确的簇数。在真实世界中，数据集是多样的，为全方位展示 DPCC 的有效性，本文在不同类型数据集上测试 DPCC 方法。3.1.1 高斯数据集高斯数据集在真实世界数据集中屡见不鲜，因此有必要验证 DPCC 方法是否可以准确识别出高斯数据集中簇的数量。本文在一组常见的高斯数据集上测试了DPCC 方 法。这 组 数 据19由 3 个 数 据 集 组 成，分 别 为A1、A2、A3。从 A1 到 A3，簇的数量越来越多。图 1 展示了这 3 个数据集的原始分布（第 1 行）以及 DPCC 的决策图（第 2 行）。其中，原始分布图中横、纵坐标分别为数据的第一、二维属性值；决策图中横、纵坐标分别为和值（下同）。实验结果显示，DPCC 决策图中右上角凸显的数据点数量与簇的数量完全一致。因此，DPCC方法对高斯数据集具有鲁棒性。3.1.2 形状数据集相比于高斯数据集，形状数据集较难识别。由于形状簇中数据点分布复杂，K-means 算法易在一个形状簇中识别出多个聚类中心，而在多个相互靠近的簇中只识别出一个聚类中心。因此，验证 DPCC 方法对形状数据集的鲁棒性对 K-means 算法极为重要。本文选择了 2 个常 见 的 形 状 数 据 集，分 别 为 pathbased20、spiral20。其中，pathbased 数据集中 2 个高斯簇被 1 个环形簇包围，spiral 数据集中 3 个簇螺旋交织在一起。图 2 展示了这 2个数据集的原始分布以及 DPCC 的决策图。实验结果显示，DPCC 的决策图中右上角数据点的数量仍与簇的数量完全一致。因此，DPCC 方法对形状数据集具有鲁棒性。3.1.3 重合数据集重合数据集表现为不同簇间的边界发生重合，导致簇间相似性难以判断。在一组常见的重合数据集上测试了 DPCC，这组数据21由 4 个数据集组成，分别为 S1、S2、S3、S4。这 4 个数据集均包含 15 个簇，但是从 S1 到S4，簇的重合度越来越高，甚至 S4 数据集中簇的边界已完全模糊。图 3 展示了这 4 个数据集的原始分布以及DPCC 的决策图。实验结果显示，无论数据集的重合度如何，DPCC 的决策图中右上角均都有 15 个点，与簇的数量完全一致。3.2 运行时间对比本文专门选择了规模较大的 Aggregation22、S1、S2、图 1DPCC 方法在高斯数据集上的表现136Computer Technology and Its Applications计算机技术与应用电子技术应用 2023年 第49卷 第3期S3、S4、D3123数据集，在其上测试了 K-means 算法的原始运行时间以及经 DPCC 方法优化后 K-means 的运行时间。这里设置 K-means 算法的迭代停止条件为聚类中心变化幅度小于 0.000 1。测试结果记录在表 1 中，实验结果显示，DPCC 方法可以极大缩减 K-means 算法的运行时间。究其原因，随机初始聚类中心密度大小参差不齐，K-means 需要迭代多次才能找到稳定的聚类中心，致使 K-means 的原始运行时间较长。甚至在 D31 数据集上，K-means 算法执行了 10 min 以上，聚类中心仍未达到稳定态，已失去了实际意义。而 DPCC 方法识别的初始中心本身为每个簇的密度最大值点，由于密度最大值点具有较多邻居，因此它通常是整个簇中离其他数据点最近的数据点，使得 K-means 无需进行迭代即可找到稳定的聚类中心，缩减了 K-means 算法的运行时间。3.3 准确度对比本文又在 Aggregation、Flame24、R1523、D31、Compound25、Pathbased 数据集上分别测试了 K-means 算法的原始聚类准确度以及经过 DPCC 方法优化后 K-means算 法 的 聚 类 准 确 度。聚 类 准 确 度 被 NMI 指 数 衡 量。NMI 指数越接近 1，聚类结果越准确。测试结果记录在表 2，实验结果显示，DPCC 方法使得 K-means 算法的准确度均取得较大提升，平均提升幅度超过 20%。究其原因，随机选取的初始聚类中心可能使 K-means 算法陷入局部最优，而 DPCC 方法识别的初始聚类中心由于密度大，使 K-means 算法跳出了局部最优陷阱，从而具有更高的聚类准确度。4 结论本文提出了一种 DPCC 方法来优化 K-means 算法，DPCC 方法通过将簇密度最大的数据点作为 K-means 算法的初始聚类中心点，从而解决 K-means 算法的一系列缺陷。本文设计了大量实验来验证 DPCC 方法。实验结果显示，DPCC 方法可有效帮助 K-means 算法确定参数 k 值，且可靠性高，适用于高斯数据集、形状数据集、图 3DPCC 方法在重合数据集上的表现表 2算法准确度比较（NMI 值）随机初始中心DPCC 中心Agg0.640.85Flame0.320.44R150.760.99D31-0.97Com0.660.73Pat0.480.54注：Agg 指的是 Aggregation 数据集，Com 指的是 Compound 数据集，Pat 值得是 Pathbased 数据集。图 2DPCC 方法在形状数据集上的表现表 1算法运行时间比较（s）随机初始中心DPCC 中心Aggregation0.1080.096S10.970.90S20.960.83S30.940.88S40.990.87D31-1.15注；K-means 算法以随机初始中心在 D31 数据集上运行超过10 min 仍未得到结果。137Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com重合数据集这些常见的数据类型；DPCC 方法可有效缩短 K-means 算法的执行时间，执行时间平均缩短超过10%；DPCC 算法可有效提升 K-means 算法的聚类准确度，准确度平均提升超过 20%。参考文献 1 MACQUEEN J.Some methods for classification and analysis of multivariate observationsC/Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability，1967,1:281-297.2 GONG Y,PAWLOWSKI M,YANG F,et al.Web scale photo hash clustering on a single machineC/IEEE Conference on Computer Vision and Pattern Recognition.IEEE,2015:19-27.3 MATSUI Y,OGAKI K,YAMASAKI T,et al.Pqk-means:billion-scale clustering for product-quantized codesC/Proceedings of the 2017 ACM on Multimedia Conference.ACM,2017:1725-1733.4 ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noiseC/KDD96:Proceedings of the Second International Conference on Knowledge Discovery and Data Mining,1996:226-231.5 ANKERST M,BREUNIG M M,KRIEGEL H P,et al.OPTICS:ordering points to identify the clustering structureJ.ACM Sigmod Record,1999,28(2):49-60.6 HINNEBURG A,KEIM D A.An efficient approach to clustering in large multimedia databases with noiseC/KDD98:Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining,1998,98:58-65.7 LAOHAKIAT S,SA-ING V.An incremental density-based clustering framework using fuzzy local clusteringJ.Information Sciences,2021,547:404-426.8 ZHANG D,SUN Y,ERIKSSON B,et al.Deep unsupervised clustering using mixture of autoencodersJ.arXiv preprint arXiv:1712.07788,2017.9 CHEN G.Deep learning with nonparametric clusteringJ.arXiv preprint arXiv:1501.03084,2015.10 JI P,ZHANG T,LI H,et al.Deep subspace clustering networksJ.arXiv preprint arXiv:1709.02508,2017.11 WANG J,JIANG J.Unsupervised deep clustering via adaptive GMM modeling and optimizationJ.Neurocomputing,2021,433:199-211.12 PENG Z,LIU H,JIA Y,et al.Attentiondriven graph clustering networkC/Proceedings of the 29th ACM International Conference on Multimedia,2021:935-943.13 CARON M,BOJANOWSKI P,JOULIN A,et al.Deep clustering for unsupervised learning of visual featuresC/Proceedings of the European Conference on Computer Vision(ECCV)，2018:132-149.14 KAUFMAN L,ROUSSEEUW P J.Finding groups in data:an introduction to cluster analysisM.John Wiley&Sons,2009.15 MCINNES L,HEALY J,ASTELS S.hdbscan:hierarchical density based clusteringJ.Journal of Open Source Software,2017,2(11):205.16 SARFRAZ S,SHARMA V,STIEFELHAGEN R.Efficient parameter-free clustering using first neighbor relationsC/Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition，2019:8934-8943.17 ZHANG T,RAMAKRISHNAN R,LIVNY M.Birch:an efficient data clustering method for very large databasesJ.ACM Sigmod Record,1996,25(2):103-114.18 RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaksJ.Science,2014,344(6191):1492-1496.19 KRKKINEN I,FRNTI P.Dynamic local search algorithm for the clustering problemM.Joensuu,Finland:University of Joensuu,2002.20 CHANG H,YEUNG D Y.Robust path-based spectral clusteringJ.Pattern Recognition,2008,41(1):191-203.21 FRNTI P,VIRMAJOKI O.Iterative shrinking method for clustering problemsJ.Pattern Recognition,2006,39(5):761-775.22 GIONIS A,MANNILA H,TSAPARAS P.Clustering aggregationJ.ACM Transactions on Knowledge Discovery from Data(TKDD),2007,1(1):4-es.23 VEENMAN C J,REINDERS M J T,BACKER E.A maximum variance cluster algorithmJ.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(9):1273-1280.24 FU L,MEDICO E.FLAME,a novel fuzzy clustering method for the analysis of DNA microarray dataJ.BMC Bioinformatics,2007,8(1):1-15.25 ZAHN C T.Graph-theoretical methods for detecting and describing gestalt clustersJ.IEEE Transactions on Computers,1971,100(1):68-86.（收稿日期：2022-06-06）作者简介：李秋云（1993-），男，硕士，工程师，主要研究方向：数字工程、数据分析。刘 燕 武（1976-），通 信 作 者，男，本科，工程师，主要研究方向：数字平台 建 设，E-mail：。扫码下载电子文档138