1、第 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)摘 要 随着数据爆发式的增长，数据挖掘算法的使用更加频繁，因此选取合适的数据挖掘算法进行数据分
2、析是非常有必要的。本文对确定 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
3、 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
4、-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 dem
5、and 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 de
6、mand 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-mean
7、s Algorithm;Canopy Algorithm;Cluster Center 1 引言 聚类算法是用“物以类聚”的思想1，把性质相同或相近的数据划分到同一个分组，把性质差异较大的数据划分到不同的分组。K-means 算法是基于划分的一种迭代聚类算法2。该算法优点如下：（1）收敛速度快。这一特征在处理组别之间差距较大的凸面数据时体现得尤为明显。不同组别相似度低，组内数据相似度高，则在迭代计算时，速度会很快，聚类也会达到很好的效果3。（2）算法复杂度为 O=N*K*t，是线性关系。其中，N 是数据集总数据个数，K 即为分组个数，t是算法直到收敛总的迭代次数。在处理大数据集时的可伸缩性比较
8、强4。因算法复杂度低，执行效率较高，很适用于海量数据集的聚类处理。K-means 算法虽优点突出，但同时也存在着如下缺点：58 姚蒙等：K-means 算法的初始值选取问题的研究 第 7 期（1）K 值确定存在困难。K-means 算法在执行时，分组数量 K 的值需要提前指定，目标数据集的不同会导致难以预先指定K 值。K 值的选取必须根据数据集本身的数据特征和实验期望通过处理所得到的分组数来共同决定。因此，K 值的选取存在困难，在处理数据集前很难确定该数据集最合适的分组数5。（2）初始聚类中心不易确定。算法的执行需要指定初始的聚类中心。K-means 算法的执行步骤就是根据初始中心分组，通过不
9、断的迭代，最终得到收敛结果。初始聚类中心的选取如同 K 值的选取一样，选取不同的聚类中心会导致聚类结果的不同6。因为 K-means 算法选取误差的平方和 SSE 作为度量聚类质量的目标函数，如式（1）所示：SSE=dist(Ci,x)2xiCiKi=1 (1)其中，dist 表示两个点的欧氏距离，Ci为 K 个分组中的任意一个，xi为 Ci分组中的数据。因该函数存在多个极小值，如果初始聚类中心选取不当，会使算法执行后的最终结果在某一极小值上，而并非全局最优解，导致聚类结果与实际偏差较大。（3）易受噪声点和孤立点的影响。在数据采集过程中，虽然会有一定程度的鉴别和筛选，但当数据集的规模到达一定程
10、度后，最终获取的结果难免会体现在数据收集过程中的过失。例如，出现错误的一些数据在进行聚类时会成为“噪声点”；一些数据虽未出错但与其他剩余数据差别较大，并存在于数据集中时，则在聚类中会成为“孤立点”。由于 K-means 算法的特性，所有数据都会在迭代计算中，导致分组的聚类中心有可能会因噪声点、孤立点的数据而使其偏离实际值，无法得到很好的聚类效果7。鉴于以上问题，本文提出了数据预处理的方法，以优化 K-means 算法的执行效果。通过数据预处理，确定K-means算法的初值K和初始聚类中心，使得 K-means 算法的执行结果更具参考意义。2 K-means 算法初值选取方法 当前存在的数据预处
11、理方法较多，如选取低复杂度算法优先进行一次运算。本文基于这种方案，选取 Canopy 算法作为 K-means 算法的初始步骤8。整个数据预处理的过程分为三步：（1）执行 Canopy算法。（2）数据集“降噪”。（3）合并剩余分组并检验阈值的选取。2.1 获取Canopy初始分组 当 Canopy 算法执行后，会生成多个 canopies（即 canopy 分组）。以图 1 为例，简要分析 Canopy处理后的结果，图 1 中出现了从 A 到 F 共 6 个分组。每个分组的中心为圆心，虚线部分小圆半径 D1，实线部分大圆半径为 D2。假设任意一点与圆心的距离为 dis，当 disD1 时，称该
12、点与当前分组为强关联点；当 D1disD2 时，该点与当前分组为弱关联点。图 1 Canopy 结果 2.2 数据集“降噪”通过图 1 的执行结果可以看出，Canopy 算法执行后会给出若干个分组（即 canopies）及每个分组的数据中心。若以 canopies 的数量作为 K-means 算法的K值，以各个canopies的数据中心作为K-means算法的初始聚类中心，Canopy 算法的执行结果可以直接作为 K-means 算法的初始值。这种做法在一定程度上减少了 K-means 算法初值选取的随机性，提高了 K-means 算法的处理精度。但为了使 K-means算法的精度更高，获得一
13、个更好的分组结果，就必须对 canopies 进行进一步处理。首先需要进行整个数据集的降噪。如图 1 中的分组 E，该分组中只包含了 1 个数据点，且距离该数据点 D2 范围内并不存在弱关联点。综合上述对数据集的分析，该点可作为两种对象分别进行处理：（1）将其作为噪声点，直接从数据集中删除。（2）将其作为孤立点，专门列出分组，在进行 K-means 算法时将其挑出，避免其干扰分组效果。对于是噪声点还是孤立点的判断，需要溯源到数据采集环节，根据实际情况加以2023 年 福 建 电 脑 59 判断。但不管是当作噪声点还是孤立点来处理，均为“降噪”过程。2.3 合并分组 将分组 E 降噪处理后，再观
14、察 AD 及 F 等 5个 canopies 分组。首先观察 F 分组，所有的数据点都集合在以分组中心为圆心、D1 为半径的圆内，即所有点均和当前分组强关联。同时，与分组中心距离 dis 在 D1disD2 范围内并不存在任何数据点，即没有与当前分组若关联的数据。因此这个组无需跟其他任何分组进行合并，直接作为 K-means算法分组中的一个显然是非常合适的。接着分析分组 A、B 和分组 C、D。首先分析 A、B 分组，A 组中有 3 个弱关联的点在 B 组的强关联点中；同时，B 组中也有 3 个弱关联点在 A 组的强关联点中。这种过程在实际讨论中可以总结为两组存在弱关联交叉。通过分析可以得出，
15、这两组数据存在合并的可能性（分组之间的距离较近，组内数据的相似度较高）。C、D 两组中互为弱关联的数据点比 A、B 两组更多，同样存在合并分组的可能性。对于分组是否合并的问题，进行三种考虑：（1）直接判断两个分组中心点的距离。若中心点距离dis2D1 时，即认为两组相似度较高，合并分组。（2）采用阈值法，指定一个参考阈值 t，通过判断两个分组弱关联数据的多少，制定合并策略。例如，假设两个分组 Ci和 Cj，分别包含 P、Q 个数据，其中 Ci中有 p 个强关联的点在 Cj的弱关联的点中，Cj中有 q 个强关联的点在 Ci的弱关联的点中，则阈值可定义为 t=(p+q)/(P+Q)。若阈值运算结果
16、大于参考阈值，则两个分组合并，否则不合并。（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也是需要指定的，而指定初