基于相异性邻域的改进K-means算法

李汉波 魏福义 张嘉龙 刘志伟

摘要：K-means算法从样本集随机选取初始聚类中心导致聚类结果不稳定，且聚类性能易受奇异点影响。针对以上缺陷，文章定义基于相异度矩阵的邻域半径概念，依次选取最小邻域半径对应的样本作为初始聚类中心，直到邻域半径达到样本集的平均邻域半径;若选取的聚类中心数量不足K个，逐步缩小邻域参数探索，直到选出K个。随后给出基于实验的剔除奇异点公式，得到最终的聚类结果。实验结果表明，算法在准确度和迭代次数两方面均有所改进。

关键词：K-means聚类;相异度;邻域半径;初始聚类中心;奇异点

中图分类号：TP273.4    文献标识码：A    文章编号：2096-4706（2021）07-0067-04

Improved K-means Algorithm Based on Dissimilarity Neighborhood

LI Hanbo，WEI Fuyi，ZHANG Jialong，LIU Zhiwei

（South China Agricultural University，Guangzhou  510642，China）

Abstract：The K-means algorithm selects the initial clustering centers from the sample set at random，which leads to unstable clustering results，and the clustering performance is easily affected by singularity. In view of above defects，the paper defines the concept of neighborhood radius based on the dissimilarity matrix，and successively selects the samples corresponding to the minimum neighborhood radius as the initial clustering centers，until the neighborhood radius reaches the average neighborhood radius of the sample set;if the number of selected clustering centers is less than K，the neighborhood parameter is gradually reduced to explore，until K initial clustering centers are selected. Then the formula of eliminating singular points based on experiment is given，and the final clustering result is obtained. Experimental results show that the algorithm is improved in accuracy and iteration times.

Keywords：K-means clustering;dissimilarity;neighborhood radius;initial cluster center;singularity

收稿日期：2021-03-24

基金项目：国家自然科学基金青年项目（117 01189）;广东省大学生创新创业项目（S20201056 4034）;华南农业大学微达安产业学院项目

0  引  言

聚类是衡量数据相似性的重要手段，聚类分析是机器学习与数据挖掘的热点研究领域。聚类算法是根据样本性质对数据进行划分的一种无监督学习算法。K-means算法[1]由MacQueen于1967年提出，属于基于划分的聚类算法，以其收敛速度快、简单有效的优点得到了广泛的应用[2-4]，但聚类性能易受奇异点影响，且算法随机选取初始聚类中心会导致聚类结果陷入局部最优解。

针对K-means算法随机选取初始聚类中心导致聚类结果不稳定的缺陷，一些学者在K-means算法的基础上提出了多种改进措施[5-9]。文献[10]基于最近距离的原则，从样本数量最多的聚类中选择离散量最大与最小的两个样本作为初始聚类中心。文献[11]利用局部方差反映数据密集程度的特性，提出一种基于最小局部方差优化初始聚类中心的改进K-means算法。文献[6]和文献[12]通过构造样本集的相异度矩阵，依次选取最大相异度参数对应的样本作为初始聚类中心。以上算法均能削弱K-means算法对初始聚类中心选取的敏感性，并能取得较为良好的改进效果，但未考慮奇异点对算法性能的影响。

本文构造样本集的相异度矩阵，定义了可变邻域参数τ和邻域半径，从最小邻域半径开始，按邻域半径递增的原则寻找初始聚类中心，直到当前邻域半径达到样本集的平均邻域半径。若选取的初始聚类中心数量小于K个，缩小邻域参数τ，循环执行以上步骤，直到选出K个初始聚类中心。在选取初始聚类中心的过程中，寻找邻域半径最大的若干个样本作为样本集的奇异点。在K-means算法进行迭代时，先剔除奇异点，以消除奇异点对算法性能的影响，最后再把奇异点按距离最近原则归类。实验及其分析结果表明，该方法对K-means算法的性能具有良好的改进效果。

1  基于相异性邻域的K-means算法

首先基于相异度矩阵，提出三个新概念，得到一种改进初始聚类中心选取方法;然后定义了剔除奇异点的公式，给出改进的K-means算法。

1.1  改进的初始聚类中心选取算法

以相异度矩阵代替样本的欧式距离，能消除属性值差异过大对初始聚类中心选取的影响。本文通过相异度矩阵对样本集中各属性进行归一化处理，给出基于相异度矩阵的三个概念，提出一种新的初始聚类中心选取方法。

1.1.1  相关概念

设待聚类的样本集：X={x1，x2，x3，…，xn}，其中xi=

{xi1，xi2，xi3，…，xim}，n为样本集的样本数量，m为样本属性的数量。

计算样本的相异度并构造相异度矩阵[6]：

（1）计算样本xi与xj之间的相异度rij：

rij=

其中max{xrs}为第s个属性的最大值，min{xrs}为第s个属性的最小值。

（2）将所有样本的相异度表示成n×n的相异度矩阵：

在相异度矩阵R的基础上，引入邻域参数τ，将τ初始化为τ=，随后根据需要逐步减少，即取值为 -1，-2，-3，…，其中K表示样本集的分类数， 表示向下取整。

定义1：对于相异度矩阵R和鄰域参数τ，将Ri中的元素从小到大排序，第τ个值称为样本xi的τ邻域半径，记作Ra（τ，xi）。其中Ri={ri1，ri2，…，rin}表示相异度矩阵的第i（i=1，2，…，n）行。以xi为中心，Ra（τ，xi）为半径的邻域中有τ个样本。

定义2：对于样本集X={x1，x2，x3，…，xn}，集合{Ra（τ，x1），Ra（τ，x2），Ra（τ，x3），…，Ra（τ，xn）}称为对应参数τ的邻域半径集合，记为M（τ）。

定义3：集合M（τ）的平均值称为样本集的平均邻域半径，记为m（τ）。

当样本xi的τ邻域半径Ra（τ，xi）大于平均邻域半径m（τ）时，可认为样本xi周围分布的样本较为稀疏。

1.1.2  初始聚类中心选取方法

作为K-means算法初始聚类中心改进方法，需要选取周围样本分布较密集的样本，样本xi的τ邻域半径Ra（τ，xi）越小，说明该样本周围分布的样本越密集，即可以选择xi作为某一类的初始聚类中心。对于样本集X={x1，x2，x3，…，xn}，已选为初始聚类中心的样本集合记为Z={z1，z2，…，zk};记集合L={l1，l2，…，lk}，其中li（i=1，2，…，k）表示zi为样本集X中的第li个样本。

设当前已选为初始聚类中心的数量为k=0，遴选K个初始聚类中心的具体步骤为：

步骤1：构造相异度矩阵，初始化邻域参数τ，即令τ=  ;初始化Z集合为空集。

步骤2：构造τ邻域半径集合M（τ），计算平均邻域半径m（τ）。

步骤3：从M（τ）选取最小值Ra（τ，xi）的样本xi作为第一个初始聚类中心，并标记样本xi，随后将样本xi加入集合Z，令k=k+1。

步骤4：从集合M（τ）选取最小值Ra（τ，xj）且未被标记的样本xj作为下一个初始聚类中心候选样本，若Ra（τ，xj）≥m（τ），则跳转到步骤6。

步骤5：若Ra（τ，xj）+Ra（τ，zk）

步骤6：清空当前已选为初始聚类中心的集合Z，令τ=τ-1，k=0，执行步骤2。

步骤7：若k==K，表明K个初始聚类中心选取完毕，记录当前的邻域半径集合M（τ）和初始聚类中心集合Z;否则，执行步骤4。

1.2  剔除奇异点

K-means算法迭代过程中，奇异点的存在会给聚类结果带来误差[13]。当样本集分布呈现簇状时，K-means算法能够取得很好的聚类效果。在簇状子集中，距离簇中心越远的样本，该样本的离散度越大，即越有理由认定该样本为样本集的奇异点。不同数据集大小不一且分类数量不同。为了合理甄别并剔除奇异点，本文基于样本集的分布规律以及样本集的邻域半径性质，提出一种新的剔除奇异点方法。根据实验经验，本文定义q=K·个样本为样本集的奇异点。在Iris数据集中，选取的奇异点数量为9个，占数据集的比例为6%;在Seed数据集中，选取的奇异点数量为12个，占数据集的比例为5.7%;在Wine数据集中，选取的奇异点数量为12个，占数据集的比例为6.7%。

奇异点分布在较为稀疏的样本区域，被选为奇异点的样本具有与其他样本差异显著的特征[14，15]。由定义1和定义2可知，邻域半径Ra（τ，xi）越大，样本xi周围分布的样本越稀疏，表明在样本集X中，样本xi与其余样本差异显著，即可选取样本xi作为样本集的奇异点。因此，有：

（1）本文从遴选初始聚类中心步骤7的M（τ）中选取邻域半径最大的前q个样本作为样本集的奇异点，记奇异点集为G={g1，g2，g3，…，gq};

（2）在K-means算法的迭代过程中，参与相似性划分的样本集为：Y=X/G={y1，y2，y3，…，yt}，其中t=n-q。

1.3  K-means算法与数据聚类

由以上分析可知，本文算法可消除奇异点对聚类中心的影响，改进的K-means算法具体执行步骤为：

步骤1：集合Z中的K个样本Z={z1，z2，…，zk}作为改进K-means算法的初始聚类中心。

步骤2：在已剔除奇异点的样本集合Y中，分别求出样本yi（i=1，2，…，t）与K个聚类中心的欧式距离Dis{yi，zj}（j=1，2，…，K），记最小欧式距离为dis（yi，zj）=

Dis{yi，zj}，并将样本yi划分到第j个簇Cj，其中Y=C1? C2?…?CK。

步骤3：计算新的簇中心，其中ci∈Cj，j=1，2，…，K，N（Cj），表示Cj的样本数量。

步骤4：若=zj对于j=1，2，…，K均成立，K-means算法迭代完毕，得到最终的聚类中心集合{z1，z2，…，zk}，跳转到步骤5;否则，将新求得的簇中心作为下一次迭代的聚类中心，即令zj=，其中j=1，2，…，K，重新执行步骤2。

步骤5：在样本集X中，根据样本xi（i=1，2，…，n）与最终聚类中心{z1，z2，…，zk}的最小欧式距离dis（yi，zj），将样本xi划分为第j类，其中j=1，2，…，K。算法结束，得到样本集X的K类的聚类结果。

2  实验结果与分析

为验证改进算法的有效性，本文采用UCI[16]数据库中的Iris、Seed和Wine数据集作为数据集，并将传统K-means算法[1]、文献[17]算法和本文算法的实验结果进行对比分析。

2.1  实验评价指标

本文采用准确度和迭代次数作为判定聚类算法性能优劣的指标。设原始样本集聚为K类，则聚类准确度的计算公式[12]为：

MP=

n为样本集数量，ai表示正确划分为第i类的样本数量，MP值越高，表示聚类的准确度越高。迭代次数越少，表示聚类的效率性越高。

2.2  实验结果及其分析

由于K-means算法聚类结果波动性较大，实验对K-means算法采取多次运算求平均值，并与文献[17]算法和本文提出的算法进行对比，以提高实验结论的合理性。实验结果如表1至表3所示。

Iris数据集含有150个样本，样本的属性维度为4，分为3类。由表1可以看出，在Iris数据集中，K-means算法的平均准确率仅为81.43%，文献[17]算法的准确率为89.33%，本文算法的准确率达到90.00%，高于K-means算法的平均准确率和文献[17]算法的准确率。且本文算法的迭代为3次，均低于K-means算法和文献[17]算法，聚类效率性较好。

Seed数据集含有210个样本，样本的属性维度为7，分为3类。由表2可以看出，在Seed数据集中，本文算法的准确率达到90.95%，在三种算法中效果最佳。且本文算法的迭代次数为7.0次，低于K-means算法的9.1次和文献[17]算法的8.0次。

Wine数据集含有178个样本，样本的属性维度为13，分为3类。由表3可以看出，在Wine数据集中，K-means算法的准确率为65.08%，本文算法的准确率为70.22%，与文献[17]算法相同，但高于K-means算法的准确度。且本文算法的迭代次数为3.00次，对比于前两种算法，本文算法具有最高的聚类效率性。可以说明，本文算法在Wine数据集的聚类性能较良好。

由表1至表3、图1和图2可见，改进之后的算法总体性能优于K-means算法和文献[17]算法。在Iris、Seed和Wine数据集中，对比于传统K-means算法，本文算法的准确率分别提高了8.57%、1.64%和5.14%，迭代次数分别减少了5.25次、2.10次和5.55次;對比于文献[17]算法，本文算法在Iris和Seed数据集的准确度分别提高了0.67%和1.43%，并在Wine数据集取得等效的准确度，且在迭代次数方面，本文算法分别减少了4次、1次和2次。

综上所述，与K-means算法和文献[17]算法相比，本文算法能取得较好的准确度，且迭代次数大幅度下降，聚类效率性高。这是由于本文算法在选取初始聚类中心时，充分考虑样本集的整体分布，倾向于选取密集程度较大的样本作为初始聚类中心，且被选为初始聚类中心的各样本相互距离较远，使得选取为初始聚类中心的样本更接近于局部簇状样本集的中心。在K-means算法迭代过程中，消除了奇异点对聚类中心更新的影响，使算法能够收敛到较优的结果。

3  结  论

本文提出基于相异性邻域的改进K-means算法，综合了相异度与欧式距离优化数据聚类的优点，并剔除奇异点的影响，使得算法在准确度与迭代次数两方面的性能提升显著，具有良好的聚类效果。实验结果表明，该算法有效地削弱K-means算法选取初始聚类中心的盲目性，且能消除奇异点对聚类性能的影响，对比于K-means算法，改进之后的算法准确率分别提高了8.57%、1.64%和5.14%，迭代次数分别减少了5.25次、2.10次和5.55次。

参考文献：

[1] MACQUEEN J B. Some Methods for Classification and Analysis of Multivariate Observations [C]//Proc. of 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley：Univ.California Press，1967：281-297.

[2] 赵庆.基于Hadoop平台下的Canopy-Kmeans高效算法 [J].电子科技，2014，27（2）：29-31.

[3] 高国琴，李明.基于K-means算法的温室移动机器人导航路径识别 [J].农业工程学报，2014，30（7）：25-33.

[4] 彭育辉，杨辉宝，李孟良，等.基于K-均值聚类分析的城市道路汽车行驶工况构建方法研究 [J].汽车技术，2017（11）：13-18.

[5] 韩凌波，王强，蒋正锋，等.一种改进的K-means初始聚类中心选取算法 [J].计算机工程与应用，2010，46（17）：150-152.

[6] 孟子健，马江洪.一种可选初始聚类中心的改进K均值算法 [J].统计与决策，2014（12）：12-14.

[7] 唐东凯，王红梅，胡明.优化初始聚类中心的改进K-means算法 [J].小型微型计算机系统，2018，39（8）：1819-1823.

[8] 李武，赵娇燕，严太山.基于平均差异度优选聚类中心的改进K-均值聚类算法 [J].控制与决策，2017，32（4）：759-762.

[9] 杨华晖，孟晨，王成，等.基于目标特征选择和去除的改进K-means聚类算法 [J].控制与决策，2019，34（6）：1219-1226.

[10] 刘美玲，黄名选，汤卫东.基于离散量优化初始聚类中心的K-means算法 [J].计算机工程与科学，2017，39（6）：1164-1170.

[11] 王世其，张文斌，蔡潮森，等.最小局部方差优化初始聚类中心的K-means算法 [J].软件导刊，2020，19（6）：196-200.

[12] 董秋仙，朱赞生.一种新的选取初始聚类中心的K-means算法 [J].统计与决策，2020，36（16）：32-35.

[13] 蒋丽，薛善良.优化初始聚类中心及确定K值的K-means算法 [J].计算机与数字工程，2018，46（1）：21-24+113.

[14] 左进，陈泽茂.基于改进K均值聚類的异常检测算法 [J].计算机科学，2016，43（8）：258-261.

[15] 张硕，金鑫，李兆峰，等.基于网络LOF和自适应K-means的离群点检测算法 [J].指挥信息系统与技术，2019，10（1）：90-94.

[16] ASUNCION A，NEWMAN D.UCI Machine Learning Respository [EB/OL].[2015-06-01].http：//archive.ics.uci.edu.

[17] 曹端喜，唐加山，陈香.一种优化初始聚类中心的自适应聚类算法 [J].软件导刊，2020，19（7）：28-31.

作者简介：李汉波（1999—），男，汉族，广东茂名人，本科

在读，研究方向：数据挖掘;通讯作者：魏福义（1964—），男，汉族，山西阳泉人，教授，硕士，研究方向：组合矩阵论、人工智能;张嘉龙（2000—），男，汉族，广东梅州人，本科在读，研究方向：人工智能;刘志伟（2001—），男，汉族，广东茂名人，本科在读，研究方向：人工智能。