K-means算法的初始值选取问题的研究_姚蒙.pdf

第 39 卷 第 7 期 福 建 电 脑 Vol.39 No.7 2023 年 7 月 Journal of Fujian Computer Jul.2023 姚蒙，男，1988年生，主要研究领域为算法、数据结构、数据挖掘等。E-mail:。何鹏程，男，1991年生，主要研究领域为算法、数据挖掘。E-mail:。K-means 算法的初始值选取问题的研究 姚蒙1 何鹏程2 1(信阳职业技术学院网络信息管理中心 河南 信阳 464100)2(信阳职业技术学院数学与信息工程学院 河南 信阳 464100)摘 要 随着数据爆发式的增长，数据挖掘算法的使用更加频繁，因此选取合适的数据挖掘算法进行数据分析是非常有必要的。本文对确定 K-means 算法初始值的问题，提出了一种数据预处理的优化方案。通过对目标数据集进行 Canopy 算法处理，并对 Canopy 算法执行后的分组进行降噪、合并，以最终的分组个数作为 K-means 算法的分组 K 值，并以各分组的重心作为初始聚类重心，从而确定 K-means 算法的初始值。对比实验的结果显示，优化后的 K-means 算法具有更好的聚类效果。关键词 数据挖掘；K-means 算法；Canopy 算法；聚类中心 中图法分类号 TP301.6 DOI:10.16707/ki.fjpc.2023.07.011 Research on Initial Value Selection of K-means Algorithm YAO Meng1,HE Pengcheng2 1(Network information Management Center,Xinyang Vocational and Technical College,Xinyang,China,464000)2(Department of Mathematics and Information Engineering,Xinyang Vocational and Technical College,Xinyang,China,464000)Abstract As a fast-moving consumer product,cigar products are also limited by tobacco monopoly laws and mainly sold offline,which makes it difficult for consumers to obtain data and cannot meet the demand for cigar consumption insights.The available cigar consumption data mainly includes search data that generate demand for cigars and evaluation data after cigar consumption.This paper aims to build a cigar Data dictionary with insight into cigar consumption demand.The visualization results indicate that the search data for Great Wall cigars increased by 5%in 2022,providing insight into the growth in consumer demand for Great Wall cigars.The associated term Cigar Express Network has emerged,revealing the emergence of a new model for cigar purchase.After marketing personnel conducted promotional training for retail customers,the local delivery model increased by 37.6%year-on-year.Keywords Data Mining;K-means Algorithm;Canopy Algorithm;Cluster Center 1 引言 聚类算法是用“物以类聚”的思想1，把性质相同或相近的数据划分到同一个分组，把性质差异较大的数据划分到不同的分组。K-means 算法是基于划分的一种迭代聚类算法2。该算法优点如下：（1）收敛速度快。这一特征在处理组别之间差距较大的凸面数据时体现得尤为明显。不同组别相似度低，组内数据相似度高，则在迭代计算时，速度会很快，聚类也会达到很好的效果3。（2）算法复杂度为 O=N*K*t，是线性关系。其中，N 是数据集总数据个数，K 即为分组个数，t是算法直到收敛总的迭代次数。在处理大数据集时的可伸缩性比较强4。因算法复杂度低，执行效率较高，很适用于海量数据集的聚类处理。K-means 算法虽优点突出，但同时也存在着如下缺点：58 姚蒙等：K-means 算法的初始值选取问题的研究 第 7 期（1）K 值确定存在困难。K-means 算法在执行时，分组数量 K 的值需要提前指定，目标数据集的不同会导致难以预先指定K 值。K 值的选取必须根据数据集本身的数据特征和实验期望通过处理所得到的分组数来共同决定。因此，K 值的选取存在困难，在处理数据集前很难确定该数据集最合适的分组数5。（2）初始聚类中心不易确定。算法的执行需要指定初始的聚类中心。K-means 算法的执行步骤就是根据初始中心分组，通过不断的迭代，最终得到收敛结果。初始聚类中心的选取如同 K 值的选取一样，选取不同的聚类中心会导致聚类结果的不同6。因为 K-means 算法选取误差的平方和 SSE 作为度量聚类质量的目标函数，如式（1）所示：SSE=dist(Ci,x)2xiCiKi=1 (1)其中，dist 表示两个点的欧氏距离，Ci为 K 个分组中的任意一个，xi为 Ci分组中的数据。因该函数存在多个极小值，如果初始聚类中心选取不当，会使算法执行后的最终结果在某一极小值上，而并非全局最优解，导致聚类结果与实际偏差较大。（3）易受噪声点和孤立点的影响。在数据采集过程中，虽然会有一定程度的鉴别和筛选，但当数据集的规模到达一定程度后，最终获取的结果难免会体现在数据收集过程中的过失。例如，出现错误的一些数据在进行聚类时会成为“噪声点”；一些数据虽未出错但与其他剩余数据差别较大，并存在于数据集中时，则在聚类中会成为“孤立点”。由于 K-means 算法的特性，所有数据都会在迭代计算中，导致分组的聚类中心有可能会因噪声点、孤立点的数据而使其偏离实际值，无法得到很好的聚类效果7。鉴于以上问题，本文提出了数据预处理的方法，以优化 K-means 算法的执行效果。通过数据预处理，确定K-means算法的初值K和初始聚类中心，使得 K-means 算法的执行结果更具参考意义。2 K-means 算法初值选取方法 当前存在的数据预处理方法较多，如选取低复杂度算法优先进行一次运算。本文基于这种方案，选取 Canopy 算法作为 K-means 算法的初始步骤8。整个数据预处理的过程分为三步：（1）执行 Canopy算法。（2）数据集“降噪”。（3）合并剩余分组并检验阈值的选取。2.1 获取Canopy初始分组 当 Canopy 算法执行后，会生成多个 canopies（即 canopy 分组）。以图 1 为例，简要分析 Canopy处理后的结果，图 1 中出现了从 A 到 F 共 6 个分组。每个分组的中心为圆心，虚线部分小圆半径 D1，实线部分大圆半径为 D2。假设任意一点与圆心的距离为 dis，当 disD1 时，称该点与当前分组为强关联点；当 D1disD2 时，该点与当前分组为弱关联点。图 1 Canopy 结果 2.2 数据集“降噪”通过图 1 的执行结果可以看出，Canopy 算法执行后会给出若干个分组（即 canopies）及每个分组的数据中心。若以 canopies 的数量作为 K-means 算法的K值，以各个canopies的数据中心作为K-means算法的初始聚类中心，Canopy 算法的执行结果可以直接作为 K-means 算法的初始值。这种做法在一定程度上减少了 K-means 算法初值选取的随机性，提高了 K-means 算法的处理精度。但为了使 K-means算法的精度更高，获得一个更好的分组结果，就必须对 canopies 进行进一步处理。首先需要进行整个数据集的降噪。如图 1 中的分组 E，该分组中只包含了 1 个数据点，且距离该数据点 D2 范围内并不存在弱关联点。综合上述对数据集的分析，该点可作为两种对象分别进行处理：（1）将其作为噪声点，直接从数据集中删除。（2）将其作为孤立点，专门列出分组，在进行 K-means 算法时将其挑出，避免其干扰分组效果。对于是噪声点还是孤立点的判断，需要溯源到数据采集环节，根据实际情况加以2023 年 福 建 电 脑 59 判断。但不管是当作噪声点还是孤立点来处理，均为“降噪”过程。2.3 合并分组 将分组 E 降噪处理后，再观察 AD 及 F 等 5个 canopies 分组。首先观察 F 分组，所有的数据点都集合在以分组中心为圆心、D1 为半径的圆内，即所有点均和当前分组强关联。同时，与分组中心距离 dis 在 D1disD2 范围内并不存在任何数据点，即没有与当前分组若关联的数据。因此这个组无需跟其他任何分组进行合并，直接作为 K-means算法分组中的一个显然是非常合适的。接着分析分组 A、B 和分组 C、D。首先分析 A、B 分组，A 组中有 3 个弱关联的点在 B 组的强关联点中；同时，B 组中也有 3 个弱关联点在 A 组的强关联点中。这种过程在实际讨论中可以总结为两组存在弱关联交叉。通过分析可以得出，这两组数据存在合并的可能性（分组之间的距离较近，组内数据的相似度较高）。C、D 两组中互为弱关联的数据点比 A、B 两组更多，同样存在合并分组的可能性。对于分组是否合并的问题，进行三种考虑：（1）直接判断两个分组中心点的距离。若中心点距离dis2D1 时，即认为两组相似度较高，合并分组。（2）采用阈值法，指定一个参考阈值 t，通过判断两个分组弱关联数据的多少，制定合并策略。例如，假设两个分组 Ci和 Cj，分别包含 P、Q 个数据，其中 Ci中有 p 个强关联的点在 Cj的弱关联的点中，Cj中有 q 个强关联的点在 Ci的弱关联的点中，则阈值可定义为 t=(p+q)/(P+Q)。若阈值运算结果大于参考阈值，则两个分组合并，否则不合并。（3）引入 canopies 分组重心的概念，通过判断分组重心之间的距离来确定分组是否合并。由于 Canopy 算法执行后的分组中心比较随机，该点未必能够有效代表分组中的所有数据。因此需要找出分组中更加具有代表性的数据，这个数据用虚拟的重心点（计算出来的重心值未必存在于原数据集中）较为合适。首先计算出每个 canopies 的重心，假设 Canopy 算法执行后生成了 n 个分组，用 C1、C2、Cn表示，n 个分组分别包含 m1、m2、mn个数据点，则第i 个分组 Ci的重心 fi可以表示为式（2）。fi=1mixxci (2)其中，mi为该分组的数据个数，x 为分组 Ci内的点。通过比较任意两个分组重心之间的距离 disij来判断是否合并分组。本文给出的方案是 disij2D1，按照分组合并方案，则 A、B 分组不合并。以 C、D 分组为例，以同样的方法可得 disCD2D1，（disCD 为 C、D 分组的重心距离）合并两个分组。2.4 验证Canopy阈值选取 由于 Canopy 算法执行前的两个阈值 D1、D2也是需要指定的，而指定初始值会出现和 K-means算法同样的问题，难以确定。阈值选取的随机性也会导致算法运行的不可靠。因此，通过分组合并情况来讨论 Canopy 阈值选取的合理性。对于分组合并过多的情况，有理由怀疑其阈值选取过小，直接导致较大的数据集分组被划分成了若干个小的分组，需要将阈值调大。对于分组合并较少的情况，需要适当的调小阈值，以获取更多的分组数量，再重新进行上述预处理的过程。阈值的调整过程虽然增加了数据的计算量，但可以使最终 canopy 分组的个数接近实际分组个数。3 实验及结果分析 为了使实验数据更具代表性，实验的样本量不宜过大，且样本选择要相对密集（如果实验样本选取不当，如出现样本点均匀散步在抽象的多维空间上，则不论采取那种算法，聚类效果都会打折扣，更无法体现算法改良前后的效果对比）。因此，本文对比实验数据选取了 UCI 上的标准 Iris（鸢尾花）作为实验数据集。该数据集包含 150 个数据样本，每个样本包含4 个数据（可将数据抽象为 4 维空间上的点），分别对应花瓣和花萼的长度和宽度。为了使实验结果看起来更加直观，将实验抽取花瓣和花萼的长度两组数据进行对比，使得每个数据对应为平面上的一个点，可以更清楚地看到聚类效果。60 姚蒙等：K-means 算法的初始值选取问题的研究 第 7 期 3.1 对比实验设计 3.1.1 获取初始分组值（1）获取 Canopy 初始分组。通过数据集的最值分析，选取 Canopy 算法的初始初始值，D1、D2 分别为 0.3、0.6。经过算法的执行，一共生成了 11 组分组，对应的分组结果如表 1 所示。表 1 canopy 分组信息表 组别 Canopy 重心（保留两位小数）包含数据个数 1(5.24，1.49)31 2(4.68，1.41)19 3(6.39，4.90)25 4(5.68，3.99)20 5(5.98，4.58)18 6(4.20，3.40)4 7(6.34，5.50)11 8(6.50，5.80)3 9(6.86，5.71)9 10(7.55，6.38)9 11(4.90，4.50)1（2）数据集“降噪”。实验数据集采用的是标准数据集，不存在噪声点，但根据 canopy 后的结果可以看出，部分分组包含的数据点较小，如第 6、8 和第 11 组，数据点均不足 5 个，将这几个分组视为孤立点。将分组数量从原来的 11 个降低为现在的 8 个。（3）合并分组。根据算法改良思想，需要对现存的 8 个分组进行分组合并的可行性分析和处理。这个步骤需要计算剩余数据分组的重心及两两重心间的距离。当距离在 0.6 以内时，可以合并两个分组。两两分组计算的结果一共有 28 个，因结果较多，表 2 只列举了需要合并的分组信息。表 2 合并分组信息表 组别 组别 重心距离 重心均值 弱关联数据个数 1 2 0.56(4.95,1.45)19 3 5 0.51(6.18,4.74)20 6 7 0.56(6.60,5.60)8 通过上述信息表可知，需要合并的分组一共有3 对（1、2 组，3、5 组和 6、7 组）。分组合并后，可以得到当前 K 值为 5。3.1.2 进行对比实验（1）改进前算法的执行结果。对比实验选取相同的 K 值 5，首先采用随机选取初始聚类中心的方法，执行 K-means 算法。本次实验迭代的次数为 17 次，得到的聚类结果如图 2所示。（2）改进后算法的执行效果。同样选取 K 值为 5，对于不需合并的分组，初始聚类中心采用 canopy 分组的重心，对于合并后的分组，初始聚类中心选用两个分组的重心均值。此次实验 K-means 算法迭代了 2 次。实验结果如图 3所示。图 2 改进前算法执行效果 2023 年 福 建 电 脑 61 图 3 改进后算法执行效果（3）算法执行效果对比。经过预处理后的数据，不仅在分组上更加合理，而且算法的迭代次数相应地有所减少。在鸢尾花数据集中，有一组数据花瓣长度小于2。这组数据与其他数据点差别较大，应当视为一类数据。改进后的算法将该组数据划分到了一个分组中（图 3 的分组一），结果与数据集的实际情况相符。而改进前的算法将这组数据分成了 3 组（图2 的分组三、分组四、分组五）。这是由于改进前算法执行时随机选取的 5 个聚类中心，其中有 3 个都位于这个小集合中。由此可见，初始聚类中心选取的随机性导致了聚类结果的分组不理想，算法精度较低。通过对比，验证了改进后的算法分组更为合理，提升了算法的精度。为了验证优化后的算法减少了迭代次数，增加了 10 组对比实验，并记录了改进前算法的迭代次数，结果为：17、13、11、12、15、9、17、13、10、14。3.2 实验效果分析 从聚类分组效果上分析，改进后的算法在聚类效果上要优于改进前。改进后算法的分组中的数据点分布更加均匀、合理，聚类分组结果与数据的真实分组情况较为接近。随机选取初始聚类中心会导致聚类结果太过依赖初始值，导致每次实验的结果都不相同。实验结果较大的波动会造成实验结果的可信度较低。改进后算法的迭代次数也明显优于改进前，算法改进前的迭代次数较多。10 组随机实验，仅有一组迭代次数小于 10 次，其余均大于 10 次。实验论证了通过预处理的方法，在提高 K-means 算法的精度的同时优化了算法的迭代次数。4 总结 本文通过对 K-means 算法的研究，提出了使用数据预处理的方法，最终获取 K-means 算法的初始分组和聚类中心的算法改进思路，并通过对比实验论证了算法改进效果。在下一步的研究中，计划将改进后的算法进行并行化设计，让改进后的算法具备海量数据集的处理能力，让算法的适用性扩大到更广阔的领域中。参 考 文 献 1 蔡志铃.聚类算法中图学习的若干方法研究博士学位论文.电子科技大学,成都,2022 2 何选森,何帆,徐丽,樊跃平.K-Means 算法最优聚类数量的确定.电子科技大学学报,2022,51(06):904-912 3 Nazeer K A A,Sebastian M P.Improving the Accuracy and Efficiency of the k-means Clustering Algorithm/Proceedings of the World Congress on Engineering,2009:1-3 4 Xiong H,Wu J,Chen J.K-means clustering versus validation measures:a data-distribution perspective.Systems,Man,and Cybernetics,Part B:Cybernetics,IEEE Transactions on,2009,39(2):318-331 5 董天宝,唐健,曾芳玲.基于 K 均值聚类的新型选星算法.计算机仿真,2022,39(11):22-26 6 程艳云,周鹏.动态分配聚类中心的改进 K 均值聚类算法.计算机技术与发展,2017,27(02):33-36 7 王森,刘琛,邢帅杰.K-means 聚类算法研究综述.华东交通大学学报,2022,39(05):119-126 8 张子璇,沙秀艳,肖霏,粟宝婵,隋雨陆,孟子宸.基于犹豫模糊 Canopy-K均值聚类算法的研究与应用.计算机与现代化,2022(11):17-21