基于聚合距离参数的改进K-means算法

王巧玲 乔非 蒋友好

摘 要：针对传统K均值聚类（K-means）算法随机选择初始中心及K值导致的聚类结果不确定且精度不高问题，提出了一种基于聚合距离的改进K-means算法。首先，基于聚合距离参数筛选出优质的初始聚类中心，并将其作用于K-means算法。然后，引入戴维森堡丁指数（Davies-Bouldin Index， DBI）作为算法的准则函数，循环更新聚类直到准则函数收敛，最后完成聚类。改进算法提供了优质的初始聚类中心及K值，避免了聚类结果的随机性。二维数值型仿真数据的聚类结果表明，改进算法在数据样本数达到10000时仍能保持较好的聚类效果。针对Iris和Seg 这两个UCI标准数据集的调整兰德系数，改进算法比传统算法性能分别提高了83.7%和 71.0%，最终验证了改进算法比传统算法聚类结果的准确性更高。

关键词：聚合距离参数;聚类中心;聚类评判指标;戴维森堡丁指数（DBI）;数据聚类

中图分类号：TP301.6

文献标志码：A

Improved K-means algorithm with aggregation distance coefficient

WANG Qiaoling， QIAO Fei*， JIANG Youhao

School of Electronics and Information Engineering， Tongji University， Shanghai 201804， China

Abstract：

Initial centers and K value are determined randomly in the traditional K-means algorithm， which makes clustering results uncertain and with low precision. Therefore， an improved K-means algorithm based on aggregation distance was proposed. Firstly， high-quality cluster centers were filtered out based on the aggregation distance coefficient as the initial centers of the K-means algorithm. Secondly， Davies-Bouldin Index （DBI） was introduced as the criterion function of the algorithm， and the clustering was cyclically updated until the criterion function converged. Finally， the clustering was completed. The proposed algorithm provides good initial clustering centers and K value， avoiding the randomness of clustering results. The clustering results of two-dimensional numerical simulation data show that the improved algorithm can still maintain a good clustering effect when the number of  data samples reaches 10000. For the adjusted Rand coefficients of the two UCI standard datasets named Iris and Seg， the improved algorithm respectively improves the performance of clustering by 83.7% and 71.0% compared to the traditional algorithm. It can be seen that the improved algorithm can increase the accuracy of the clustering result compared with the traditional algorithm.

Key words：

aggregation distance coefficient; cluster center; clustering evaluation index; Davies-Bouldin Index （DBI）; data clustering

0 引言

随着云计算、物联网等技术的出现，企业日趋信息化，应用系统中的数据量呈指数级增长。数据挖掘技术能够帮助用户从大量数据中分析出其所蕴涵的有价值的信息。聚类算法就是一种典型的数据挖掘方法，它是一种无监督的机器学习算法，适合于将不含训练集的大数据以相似度为依据进行聚类[1-3]。

K均值聚类（K-means）是一种常见的聚类算法，它在处理大规模数据集时可保持较好的可伸缩性和高效性[4-6]。然而，传统的K-means算法也存在一些缺陷：1）初始聚类中心的选择是随机的，这使得聚类结果不稳定，准确性较低。2）聚类个数K值的选择是随机的，若K值过大，则类与类之间的相似度太小;若K值过小，则类与类之间的相似度过大，这两种情况都会导致聚类结果不准确。

很多学者针对K-means算法的缺点提出了相应的改进。郁启麟[7]采用关系矩阵和度中心性选择K个初始聚类中心，以此来改进K-means算法。文献[8]中提出了一种基于优化抽样聚类的方法，一定程度上解决了K-means算法聚类精度不足和收敛速度慢的问题。文献[9]中提出了用随机取样策略来避免决策选取陷入局部最小。为了解决K-means算法初始聚类中心和K值随机性的问题，文献[10]应用了Canopy-Kmeans算法，先由Canopy算法对数据集进行粗聚类，得到一定数量的类，每个类的中心作为K-means算法的初始聚類中心，类的个数决定K值的大小。然而Canopy算法的两个阈值是随机选择的，这导致了获得的初始中心和K值存在随机性，从而影响聚类效果。

针对K-means算法初始聚类中心和K值选择问题，本文提出了一种基于聚合距离参数的改进K-means算法。对给定数据集中的每一个数据点进行聚合度及其所属类的距离分析，筛选出符合条件的数据点作为初始聚类中心，符合条件的数据点的个数即为K值。改進的算法能够确定最优的初始聚类中心及聚类个数，从而避免了聚类结果的不确定性。最后，采用可视化数据及UCI标准数据集，验证了改进算法聚类结果的准确性。

1 聚合距离参数

初始聚类中心及K值选择不准确，会导致K-means算法聚类结果准确性不高，因此，本文提出了聚合距离参数，以筛选出一定量的优质的初始聚类中心。聚合距离参数中涉及到的一些相关定义和概念如下：

欧氏距离 设每一个数据点包含m个属性，即xi={xi1，xi2，…，xim}，则xi、xj之间的距离可以表示为：

d（xi，xj）=∑ms=1（xis-xjs）2（1）

数据集平均距离 即为一个数据集合中所有数据点之间的平均欧氏距离。

Avgd（D）=2n（n-1）∑n-1i=1∑nj=i+1d（xi，xj）（2）

邻域半径 R=Avgd（D）nreleR，其中n表示数据点的个数，releR为邻域半径调节系数，范围在0～1，根据经验，releR取0.13时，聚类效果最佳[11-13]。

聚合度 点xi的聚合度Deg（xi）表示为与其距离小于半径的点的个数，即：

Deg（xi）=∑nj=1f（dij-R）; f（x）=1， x≤0

0，x>0（3）

集合平均距离 与点xi的距离小于邻域半径的所有点组成一个集合，那么点xi所在集合的平均距离可以定义为：

Cavgd（xi）=2Deg（xi）（Deg（xi）-1）∑Deg（xi）-1i=1∑Deg（xi）j=i+1d（xi，xj）（4）

集合平均距离可以衡量一个数据点所在集合的紧密度， 值越小，表示Cavgd（xi）所在集合越紧密。

聚合度距离 聚合度距离表示点xi与其他具有较高聚合度点xj之间的距离。若所有点中xi的聚合度最大，则其聚合度距离为xi与其余任何点的最大距离。若xi的聚合度不是所有点中最大的，则其聚合度距离为xi与其余任何点的最小距离。即：

G（xi）=min（d（xi，xj））， 存在xj满足Deg（xj）>Deg（xi）

max（d（xi，xj）），不存在xj满足Deg（xj）>Deg（xi）（5）

聚合距离参数 聚合距离参数由聚合度、集合平均距离及聚合度距离3个参数决定。即：

ω（xi）=Deg（xi）·G（xi）Cavgd（xi）（6）

聚合度Deg（xi）越大，表明点xi周围的数据点越密集。聚合度距离G（xi）越大，则两个簇之间的相异程度越高。集合平均距离Cavgd（xi）越小，则其倒数越大，表明由xi组成的集合中的元素越紧密。由此可见，聚合距离参数值越大的点，越适合作为聚类中心。

2 改进K-means算法

2.1 改进初始聚类中心

由聚合距离参数筛选最优初始聚类中心步骤如下：

1）根据式（2）～（6），计算出数据集中所有数据点相关参数，从而得到每一个数据点的聚合距离参数。

2）筛选出聚合距离值最大的点，作为第一个初始聚类中心，并依次计算其他点到该点的欧氏距离：若距离小于邻域半径R，将该点从数据集中移除;若距离大于R，则不作处理。

3）从剩余点中筛选出聚合距离值最大的点，作为第二个初始聚类中心，并依次计算其他点到该点的欧氏距离，若距离小于邻域半径R，将该点从数据集中移除。

4）重复步骤3）和步骤4），直到数据集为空。

5）输出一系列符合条件的优质初始聚类中心。

2.2 改进准则函数

传统K-means的准则函数一般为平方误差和函数，该函数计算了每个聚类样本与其聚类中心的平方距离之和，但仅片面地衡量了一个类之内数据是否紧凑，没有考虑到类与类之间的相异性，因此，本文采用戴维森堡丁指数（Davies-Bouldin Index， DBI）指标函数作为K-means算法的准则函数[14-15]。

类间距离 类间距离 Dis（i， j）表示为第i个类与第j个类之间的距离，即第i个聚类中心vi与第j个聚类中心vj的欧氏距离。

Dis（i， j）=‖vi-vj‖（7）

类内标准误差 类内标准误差Si表示为第i个聚类Ci中每一个数据点x与该类的中心点vi之间的欧氏距离标准误差和，即：

Si=1Ni∑x∈Ci‖x-vi‖（8）

其中Ni表示第i个聚类Ci包含的数据对象个数。

DBI指标

DBI=1K∑K-1i=1∑Kj=i+1maxSi+SjDis（i， j）（9）

其中K表示为数据集的所有聚类个数。

DBI指标由类之间的距离和类内的距离决定。好的聚类结果应该满足同一个类中数据之间的相似程度大，而类与类之间的相似程度小。DBI指标不仅考虑了类内的相似性，还考虑了类与类之间的相异性：如果一个类的类内距离较小，则DBI的分子较小，表明类中数据点的相似程度大;如果类与类之间的距离较大，则DBI的分母较大，表明类之间的相异性较大。因此，DBI指标数值越小，表明聚类效果越好。

2.3 改进算法总流程

改进算法根据聚合距离参数选取一定数量的最优中心，作为K-means的初始聚类中心，用DBI指标作为准则函数，若准则函数收敛，则说明聚类效果达到最优，聚类完成，输出聚类结果。整体的算法流程如下所示。

算法1 基于聚合距离参数的改进K-means算法。

输入：数据集;

输出：聚类结果。

有序号的程序——————————Shift+Alt+Y

程序前

M=数据点个数

R=邻域半径

1）

for i in range（M）

2）

计算两两数据点之间的欧氏距离

3）

计算每个数据点xi的聚合距离参数ω（xi）

4）

选出ω（xi）数值最大的数据点，作为第一个初始聚聚类中心，并将其从数据集中移除

5）

计算剩余各点xj到该聚类中心xi的距离di， j

6）

if di， j < R

7）

则将点xj从数据集中移除

8）

else if di， j≥R

9）

不作處理

10）

end

11）

重复步骤4）～10），直到数据集为空。

12）

输出一定个数的最优中心作为K-means算法的初始聚类中心

13）

输入中心个数N

14）

执行改进K-means算法，将数据集分为N个聚类

15）

if 准则函数DBI=1K∑K-1i=1∑Kj=i+1maxSi+SjDis（i， j）不收敛

16）

继续循环执行改进K-means算法

17）

else if 准则函数收敛

18）

改进K-means算法执行完毕

19）

end

20）

输出聚类结果

程序后

3 实验结果与分析

3.1 可视化数据集

为了更好地说明改进算法的优异性，本节使用Python中的make_blobs模块生成二维数值型仿真数据。首先，为了便于可视化处理，生成两组均包含200个样本点的数据。图1（a）和图1（b）的结果表明，改进算法找到了优质的初始聚类中心，成功将数据分成了2类和3类，聚类结果准确，从而改进算法的有效性得以验证。然后，为了检验算法面对较大样本时的效果，再生成一组达到10000样本数的数据。图1（c）的结果表明，改进算法仍能很好地完成聚类。

3.2 标准数据集

3.2.1 评估指标

标准数据集指明了每一个数据点真实所属的类，即true_label，而实际的聚类结果也会有一个相对应的标签，即pred_label，用于表示每个数据点实际被分到的类。对于标准数据集，本文采用以下指标进行评估：调整兰德系数、互信息、Fowlkes-Mallows 指标、同质性和完整性，这些指标都用于衡量true_label和pred_label的相似程度。

3.2.2 实验结果

本文采用了UCI网站上的标准数据集，数据集名称及其属性如表1所示。

为了更深入地进行对比，本文采用了传统K-means算法，Canopy算法及改进K-means算法对标准数据集进行聚类。聚类结果的评估指标如图2所示。

图2（a）显示调整兰德系数指标结果，调整兰德系数表示两个数据分布之间的相似度，其范围从-1到1。值越大，表明聚类结果与实际情况越一致;若值为负，表明两个数据分布相互独立，匹配程度很低。改进K-means算法相比于传统K-means，调整兰德系数指标均可有效提高。其中Iris和Seg 这两个数据集，改进算法比传统算法的调整兰德系数指标分别提高了83.7%和71.0%。

图2（b）和图2（c）分别显示互信息及Fowlkes-Mallows指标结果。这两个指标用于表示两个变量true_label和pred_label是否有关系，以及关系的接近程度。互信息和Fowlkes-Mallows指标的范围都为0～1，如果值较大，则表示true_label和pred_label之间的关系更接近。实验结果表明，改进算法在各个数据集上，互信息及Fowlkes-Mallows指标的数值都明显比传统K-means算法有提高。即改进K-means的实际聚类结果与标准结果更接近，聚类效果更好。

图3表示同质性和完整性的实验结果。同质性表示每个群集只包含单个类的成员，完整性表示给定类的所有成员都分配给同一个群集，这两个指标通常一起使用，范围为0到1之间，值越大表明聚类效果越好。

通过比较图2和图3的整体结果可知：1）改进K-means算法的评估指标数值均高于其他两个算法，即改进算法的实际聚类结果与标准结果更一致，这说明了其性能是优于传统算法的。2）对于不同的数据集来说，同一个算法聚类结果的评估指标数值也不一样，这说明聚类效果会因不同的数据集而波动。3）Canopy的聚类结果大多比传统K-means算法差，有时比传统K-means更好，这是因为Canopy的聚类结果很大程度上取决于两个阈值，且阈值在实验中是随机选择的。如果阈值更准确，最终的聚类结果将更好，指标将更好。而改进的K-means算法避免了随机性，并且始终具有更好的聚类结果。

4 结语

K-means算法是聚类算法中的重要方法。本文针对传统K-means算法的不足，提出了基于聚合距离参数的改进K-means算法。首先，通过使用聚合距离参数获取一定的最优聚类中心;然后，将最优聚类中心应用于改进的K-means，并且改进的K-means算法将根据新的准则函数DBI收敛，当准则函数达到最小值时，聚类结束，输出聚类结果。

改进的K-means算法有效地解决了初始聚类中心和K值选择不确定的问题，实验结果表明，改进的K-means算法比传统K-means算法，在聚类效果上有很大的提升。

未来工作中将会采用改进的K-means算法来对工业大数据进行聚类。由于工业大数据大都具有时效性，因此，将考虑对大数据进行降维，从而减少聚类算法的计算时间。同时，会在Hadoop平台上并行化实现大数据的聚类，提高时间效能。最后基于改进算法得出的聚类结果，提出针对工业大数据的异常值检测方法，从而将改进算法应用于工业大数据领域，有效检测工业设备运行的健康程度。

参考文献

[1]王治和，黄梦莹，杜辉，等. 基于密度峰值与密度聚类的集成算法[J].计算机应用，2019，39（2）：398-402. （WANG Z H， HUANG M Y， DU H， et al. Integrated algorithm based on density peaks and density-based clustering J]. Journal of Computer Applications， 2019， 39（2）： 398-402.）

[2]McLOUGHLIN F， DUFFY A， CONLON M. A clustering approach to domestic electricity load profile characterisation using smart metering data [J]. Applied Energy， 2015， 141： 190-199.

[3]ALI A-W， WU J， JENKINS N. K-means based load estimation of domestic smart meter measurements [J]. Applied Energy， 2016， 194： 333-342.

[4]杨辉华，王克，李灵巧，等.基于自适应布谷鸟搜索算法的K-means聚类算法及其应用[J].计算机应用，2016，36（8）：2066-2070.（YANG H H， WANG K， LI L Q， et al. K-means clustering algorithm based on adaptive cuckoo search and its application [J]. Journal of Computer Applications， 2016， 36（8）： 2066-2070.）

[5]黄韬，刘胜辉，谭艳娜.基于K-means聚类算法的研究[J].计算机技术与发展，2011，21（7）：54-57.（HUANG T， LIU S H， TAN Y N. Research of clustering algorithm based on K-means [J]. Computer Technology and Development， 2011， 21（7）：54-57.）

[6]王骏，王士同，邓赵红. 特征加权距离与软子空间学习相结合的文本聚类新方法[J].计算机学报， 2012， 35（8）： 1655-1665. （WANG J， WANG S T， DENG Z H. A novel text clustering algorithm based on feature weighting distance and soft subspace learning [J]. Chinese Journal of Computers， 2012， 35（8）： 1655-1665. ）

[7]郁启麟. K-means算法初始聚类中心选择的优化[J]. 计算机系统应用， 2017， 26（5）： 170-174. （YU Q L. Optimization of initial clustering centers selection method for K-means algorithm [J]. Computer Systems & Applications， 2017， 26（5）： 170-174.）

[8]周润物，李智勇，陈少淼，等.面向大数据处理的并行优化抽样聚类K-means算法[J].计算机应用，2016，36（2）：311-315.（ZHOU R W， LI Z Y， CHEN S M， et al. Parallel optimization sampling clustering K-means algorithm for big data processing [J]. Journal of Computer Applications， 2016， 36（2）： 311-315.）

[9]王丽娟，郝志峰，蔡瑞初，等. 基于随机取样的选择性K-means聚类融合算法[J]. 计算机应用， 2013， 33（7）： 1969-1972. （WANG L J， HAO Z F， CAI R C， et al. Selective K-means clustering ensemble based on random sampling [J]. Journal of Computer Applications， 2013， 33（7）： 1969-1972.）

[10]毛典輝.基于MapReduce的Canopy-Kmeans改进算法[J]. 计算机工程与应用， 2012， 48（27）： 22-26. （MAO D H. Improved Canopy-Kmeans algorithm based on MapReduce [J]. Computer Engineering and Applications， 2012， 48（27）： 22-26.）

[11]趙昱，陈琴，苏一丹，等. 基于邻域相似度的近邻传播聚类算法[J]. 计算机工程与设计， 2018， 39（7）： 1883-1888. （ZHAO Y， CHEN Q， SU Y D， et al. Affinity propagation clustering algorithm based on neighborhood similarity [J]. Computer Engineering and Design， 2018， 39（7）： 1883-1888.）

[12]刘鹏，王明阳，王焱.基于自适应动态球半径的K邻域搜索算法[J]. 机械设计与制造工程， 2016， 45（6）： 83-86.（LIU P， WANG M Y， WANG Y. K domain search algorithm based on adaptive dynamic sphere radius [J]. Machine Design and Manufacturing Engineering， 2016， 45（6）： 83-86.）

[13]NGUYEN D， LE T， NGUYEN S. An algorithmic method of calculating neighborhood radius for clustering in-home activities within smart home environment [C]// Proceedings of the 7th International Conference on Intelligent Systems， Modelling and Simulation. Piscataway， NJ： IEEE， 2016： 42-47.

[14]COELHO G P， BARBANTE C C， BOCCATO L， et al. Automatic feature selection for BCI： an analysis using the Davies-Bouldin index and extreme learning machines [C]// Proceedings of the 2012 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2012： 1-8.

[15]THOMAS J C R， PEAS M S， MORA M. New version of Davies-Bouldin index for clustering validation based on cylindrical distance [C]// Proceedings of the 32nd International Conference of the Chilean Computer Science Society. Piscataway， NJ： IEEE， 2013： 49-53.

This work is partially supported by the Major Program of National Natural Science Foundation of China （71690230， 71690234）.

WANG Qiaoling， born in 1994， M. S. candidate. Her research interests include clustering algorithm， big data analysis.

QIAO Fei， born in 1967， Ph. D.， professor. Her research interests include big data analysis， complex manufacturing planning and scheduling， intelligent production systems.

JIANG Youhao， born in 1976， Ph. D. candidate. His research interests include big data analysis， intelligent production systems.