K-means算法的优化及应用

方诗乔 胡佩玲 黄莹莹 张昕

摘  要：针对K-means算法易受初始值和异常点影响，以及聚类数选取依靠人工经验和初始聚类中心选取随机等缺点，提出一种基于改进Canopy算法的K-means聚类算法。首先将初始数据集进行预处理和分类，然后选取特殊的阈值利用改进的Canopy算法得到聚类数和初始聚类中心，再运行K-means算法实现最终聚类。经检验得知，改进后的算法减少了对人工选择的依赖，并且聚类准确度有了明显的提高。最后将改进后的算法应用于顾客细分实例，取得了良好的分类效果，证明了优化算法的实用性。

关键词：Canopy算法；主成分分析法；局部密度；顾客细分

中图分类号：TP301.6    文献标识码：A  文章编号：2096-4706（2023）06-0111-05

Optimization and Application of K-means Algorithm

FANG Shiqiao， HU Peiling， HUANG Yingying， ZHANG Xin

（College of Mathematics and Informatics， South China Agricultural University， Guangzhou  510642， China）

Abstract： In view of the shortcomings of K-means algorithm that is easily affected by initial values and outliers， and that the selection of clustering number depends on artificial experience and the selection of initial clustering center is random， a K-means clustering algorithm based on improved Canopy algorithm is proposed. First， the initial data set is preprocessed and classified， and then a special threshold is selected to obtain the number of clusters and the initial cluster center using the improved Canopy algorithm， and then the K-means algorithm is run to achieve the final clustering. The test shows that the improved algorithm reduces the dependence on manual selection， and the clustering accuracy has significantly improved. Finally， the improved algorithm is applied to a customer segmentation example， and good classification results are obtained， which proves the practicability of the optimized algorithm.

Keywords： Canopy algorithm; principal component analysis; local density; customer segmentation

0  引  言

为满足聚类的不同需求，聚类分析的常用方法一般可划分为五类：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法和基于模型的聚类算法[1]。其中K-means算法是最经典的无监督划分算法，它具有算法思想简单、收敛速度快、对大规模数据集处理效率高等特点，被广泛运用于商业、电子商务、大数据挖掘等领域。

Canopy算法是一种简单、快捷的对象聚类算法，一般用在K-means算法之前的粗聚类。它可以减少相似样本的计算量，但是由于聚类中心的选取是随机的，故聚类效果可能受到噪声点或离群点的影响。此外，阈值T1、T2的取值也会影响Canopy的重叠率，影响最终的聚类效果。

针对Canopy-Kmeans聚类算法[2]初始聚类中心选取随机、算法受噪声点影响等问题，陈胜发等人提出了基于密度权重的Canopy的改进K-medoids算法[3]用于提高精确度；王海燕等人提出了Canopy+_K-means算法[4]从阈值获取方式和初始聚类中心的选取两方面进行了改进；鲁茜提出一种利用距离分布直方图改进Canopy算法中阈值T1、T2取值的算法[5]。这些算法在寻优性能上确有提高，但在聚类准确度和算法复杂程度方面仍有待改进。

本文提出基于数据预处理，优化Canopy算法阈值选取和聚类中心更新的算法，得到一种新的Canopy-Kmeans-pro算法，综合实例数据和现实应用双方面验证，该改进后的算法在聚类准确率、聚类效果上均有改善，且具备一定的现实意义。

1  数据预处理

设X=x1， x2，…， xn是包含n个样本对象的数据集，每个样本对象有m维特征属性。其中xij（i=1， 2，…， n，j=1， 2，…， m）是第i个数据对象的第j维属性。

首先对Xn×m作归一化处理：

其中  是Xn×m矩陣中每行数据的最小值， 是Xn×m矩阵中每行数据的最大值，得到归一化数据矩阵Yn×m。

再对矩阵Yn×m运用PCA主成分分析法，将原始的高维数据集降为简单的二维数据集，得到数据矩阵Dn×2。

2  优化算法

2.1  相关概念

定义1：数据对象xi和xj之间的欧式距离为zij：

得到距离矩阵Zn×n，其中zii=0，zij=zji。

定义2：设每个数据对象到其他数据对象的距离为第p小的距离的平均值为z0，其中参数为p：

定义3：数据对象xi的局部密度[6]为ρi：

其中函数 。

平均密度为 ：

定义4：若数据对象xi不是局部密度最大的点，则si表示xi到局部密度比它大的点的距离的最小值；若数据对象xi是局部密度最大的点，则si表示xi到其他点距离的最大值。

平均距离为 ：

定义5：若数据对象xi满足  且 ，即该数据对象的局部密度较大且与比它具有更大局部密度的对象的距离也较大，则认为这类数据点更有机会成为聚类中心[7]，因此将满足这两个条件的数据点的全体称为预备聚类中心集Hp×2。不同原始数据集的Hp×2可能具有不同的维度p。

定义6：预备聚类中心集Hp×2的均值点为 ：

定义7：预备聚类中心集Hp×2中每个数据点hi到均值点  的距离bi为：

定义8：预备聚类中心集Hp×2中数据点hi到均值点  距离的方差为s2：

其中 。

2.2  改进Canopy算法

取阈值 ，

满足T1＞T2。

其中，L1=max（bi），L2=min（bi）。

输入：预备聚类中心集Hp×2={h1， h2，…， hp}，阈值T1和T2。

输出：聚类数k和初始聚类中心center={c1， c2，…， ck}。

步骤1：从预备聚类中心集Hp×2中选择局部密度ρ最大的数据对象作为第一个聚类中心c1，将它添加到center={c1}后从Hp×2中删除。

步骤2：计算Hp×2中剩余数据对象到center中各点的距离，以c1为例：

（1）若数据点hi到c1的距离大于T1，则将hi作为一个新的聚类中心c2添加到center中，并将hi从Hp×2中删除；

（2）若距离大于T2且小于T1，则将hi划分到c1所在的类C1中，然后计算类C1中所有数据点的均值点作为新的c1；

（3）若距离小于T2，则将hi划分到c1所在的类C1中，然后计算类C1中所有数据点的均值点作为新的c1，并将hi从Hp×2中删除。

步骤3：重复步骤2，直到预备聚类中心集Hp×2为空[6]。

2.3  改进K-means算法

输入：聚类数k和初始聚类中心center={c1， c2，…， ck}

输出：k个聚簇

步骤1：计算Dn×2中每个数据对象到初始聚类中心c1， c2，…， ck的距离，并将该对象划分到离其最近的聚类中心所属的集合。

步骤2：分别计算k个集合中数据点的中位数，作为更新后的聚类中心c1， c2，…， ck。

步骤3：重复步骤2，直到所有的聚类中心相邻两次迭代结果的改变量不超过0.01。

3  仿真实验

本文实验均在MATLAB 2020a软件环境下，操作系统为Intel（R）Core（TM） i5-8265U CPU @处理器，主频1.60 GHz，内存8 GB的计算机中进行。

为了验证本文算法的有效性，从UCI数据集中选取了四个人工数据集Wine、Iris、Seed_dataset、Vehicle作为实验数据集，如表1所示。将本文算法与王海燕等人提出的Canopy+_K-means算法[4]和陈胜发等人提出的基于密度权重的Canopy的改进K-medoids算法[3]就聚类正确率、误差平方和[8]以及聚类数k值三个方面进行比较，保证所有算法均在同一环境下运行10次，并取相应算法的最优值和平均值作为分析数据，数据集属性与实验结果如表2、图1、图2所示。

对降维后的人工数据集Wine、Iris、Seeds_dataset、Vehicle使用本文算法并进行可视化处理，结果如图3至图6所示，由图可知，聚类结果基本符合算法的测试数值。

由上述实验结果可直观看出，本文算法优化了原始K-means算法中初始聚类中心以及聚类数k值的选取方法，获取的k值准确度明显高于Canopy+_K-means算法和DWC_K-medoids算法，并且对于实验中的四个数据集，本文算法均能选取出正确的k值。在此基础上，通过聚类正确率和误差平方和两个指标对算法进行进一步的评价，可以发现，本算法较其他能正确分类的算法而言，聚类正确率最高且误差平方和最小。因此，可以认为本文算法的改进是有成效的，优化效果较好，对于不同属性的数据集有较强的兼容性，具有推广意义。

4  算法应用

4.1  应用背景

伴随着互联网技术的不断提升，数据的应用也越来越多元化，客户细分也成为销售行业了解目标受众的重要一环。客户细分能够帮助增长客户数量、提升客户生命周期价值，是识别客户需求的有力手段。通过客户细分的技术，针对顾客需求的异质性，营销团队可以规划相应的策略，从而更经济地为细分客户群提供服务，同时企业可以开发具有独特吸引力的产品和服务来实现盈利能力最大化。

4.2  数据解释

此真实数据集为2 000名来自某一特定区域的“快速消費品”购买者的行为信息，所有数据均通过购买者的个人购物卡收集。数据集已经过预处理，没有缺失值，数据集属性如表3所示。

4.3  聚类结果及分析

由于男女消费者购买心理和行为具有明显差异，为了使客户细分的分析更准确且有成效，先对真实数据集按照性别进行分类后，再利用本文算法分别对数据集中的男性与女性数据进行聚类分析。效果如图7、图8所示。

由图7、图8可以直观地看出聚类结果为男性顾客4类、女性顾客3类，并且各类之间“距离”差异显著，同类之间“距离”相对紧密，聚类效果可观。为了进一步分析各个类别的特征，分别对男性顾客和女性顾客各个属性的平均值进行统计，结果如表4至7所示。

针对快速消费品市场的特点，我们认为已婚男性相较于单身男性的购买频率更高，并且生活城市越大型，经济收入越高者，越具有购买潜力。因此将男性顾客概括为以下四种顾客类型。

第一类为边缘型顾客，这类顾客对于“快速消费品”的需求和购买力较低，但也具有一定的消费贡献值，因此精确地把这类客户区分出来，有利于更好地调配资源。

第二类为忠诚型顾客，这类顾客的消费金额和频率较高，是最重要的客户来源。针对这类顾客，为其提供个性化服务，保持其对企业的信任度，是长期维持顾客对企业高忠诚度的关键。

第三类为潜在型顾客，这类顾客在客户资源中的整体占比较大，消费金额较低于忠诚型顾客，但消费需求高。针对这类顾客，企业需要保证专业性、时效性以及多样性，提高顾客对企业的认可程度。

第四类为不定型顾客，这类顾客的消费频率较低，其购物喜好具有不确定性。针对这类顾客，企业可以主动了解顾客的需求以及购买动机，运用适当的推销策略提高客户的购买欲。

同样地，根据女性顾客的年龄、婚姻状况、居住城市规模以及收入等因素，我们可以将女性顾客概括为三种顾客类型，分别为潜在型顾客、忠诚型顾客以及边缘型顾客。针对这三类顾客采取精准的营销策略，有利于提升顾客的购买欲以及企业核心竞争力。

5  结  论

本文在传统K-means算法和Canopy算法的基础上提出了一种新的聚类算法Canopy-Kmeans-pro算法，该算法不仅解决了传统K-means算法聚类数k值需要人工确定和初始聚类中心需要随机选取的问题，还解决了Canopy算法对阈值T1、T2的确定问题，在很大程度上体现了算法的智能性。经过检验，本文算法的聚类效果相比于Canopy+_K-means算法和DWC_K-medoids算法在准确率和误差上均有明显的优势。将算法应用于快速消费品市场的顾客细分，对顾客进行快速聚类，可使企业人员直观地判断每种顾客类型的特点，进而采取精准的营销策略，提升企业的核心竞争力。

参考文献：

[1] 杨爽爽，石鸿雁.基于改进果蝇优化的密度峰值聚类算法 [J].微电子学与计算机，2022，39（9）：26-34.

[2] 邱荣太.基于Canopy的高效K-means算法 [J].现代营销：学苑版，2012（3）：244-246.

[3] 陈胜发，贾瑞玉.基于密度权重Canopy的改进K-medoids算法 [J].计算机工程与科学，2019，41（10）：1823-1828.

[4] 王海燕，崔文超，许佩迪，等.Canopy在划分聚类算法中对K选取的优化 [J].吉林大学学报：理学版，2020，58（3）：634-638.

[5] 鲁茜，蒙祖强.Canopy算法中T值选取的优化及聚类效果的改进 [J].信息与电脑：理论版，2021，33（6）：61-65.

[6] 袁逸铭，刘宏志，李海生.基于密度峰值的改进K-Means文本聚類算法及其并行化 [J].武汉大学学报：理学版，2019，65（5）：457-464.

[7] 薛京花，刘震宇，崔适时.对K-means算法初始聚类中心选取的优化 [J].电子世界，2012（5）：11-14+18.

[8] 沈郭鑫，蒋中云.基于密度和中心指标的Canopy二分K-均值算法优化 [J].计算机工程与科学，2022，44（2）：372-380.

作者简介：方诗乔（2000—），女，汉族，广东深圳人，本科在读，研究方向：数学与应用数学；胡佩玲（2001—），女，汉族，广东广州人，本科在读，研究方向：数学与应用数学；黄莹莹（2001—），女，汉族，广东河源人，本科在读，研究方向：信息与计算科学。

收稿日期：2022-11-06