一种优化初始聚类中心的自适应聚类算法

曹端喜 唐加山 陈香

摘 要：K均值算法（K-Means）是聚类算法中最受欢迎且最健壮的一种算法，然而在实际应用中，存在真实数据集划分的类数无法提前确定及初始聚类中心点随机选择易使聚类结果陷入局部最优解的问题。因此提出一种基于最大距离中位数及误差平方和（SSE）的自适应改进算法。该算法根据计算获取初始聚类中心点，并通过SSE变化趋势决定终止聚类或继续簇的分裂，从而自动确定划分的类簇个数。采用UCI的4种数据集进行实验。结果表明，改进后的算法相比传统聚类算法在不增加迭代次数的情况下，聚类准确率分别提高了17.133%、22.416%、1.545%、0.238%，且聚类结果更加稳定。

关键词：聚类算法;K-Means算法;初始聚类中心;自适应

DOI：10. 11907/rjdk. 201478 开放科学（资源服务）标识码（OSID）：

中图分类号：TP301文献标识码：A 文章编号：1672-7800（2020）007-0028-04

An Adaptive Clustering Algorithm by Optimizing Initial Clustering Centers

CAO Duan-xi1，TANG Jia-shan2，CHEN Xiang2

（1. School of Communication and Information Engineering， Nanjing University of Posts and Telecommunications;

2. School of Science， Nanjing University of Posts and Telecommunications， Nanjing 210000，China）

Abstract：K-Means is one of the most popular and robust clustering algorithms. However， in practical applications， the number of classes divided by the real data set cannot be determined in advance and the random selection of the initial clustering center point easily leads to the problem that the clustering result falls into the local optimal solution. To this end， this paper proposes an adaptive and improved algorithm based on the maximum distance median and the sum of squared errors （SSE）. The algorithm obtains the initial cluster center point through calculation， and decides to terminate the cluster or continue the division of the cluster based on the change trend of the SSE， so as to automatically determine the number of clusters to be divided. The results of experiments using four UCI data sets show that the improved algorithm improves the clustering accuracy by 17.133%， 22.416%， 1.545%， and 0.238% respectively without increasing the number of iterations compared to the traditional clustering algorithm， and the clustering results are more stable.

Key Words： clustering algorithm; K-Means algorithm; initial clustering center; adaptive

0 引言

“物以類聚”指将同类事物聚在一起。在数据科学方面，将相类似的数据通过某种准则聚集在一起，从而发现数据间的联系，称为聚类。在实际问题中，聚类分析无法事先知道待操作数据划分的类结果，类结果的形成完全取决于数据集中样本之间的内在联系[1]，这种发现内在结构的方法，是一种无监督学习方法。聚类技术是数据挖掘领域的重要方法。近年来随着数据量的倍增及大数据技术的发展，该技术备受关注，其在模式识别、图像分割[2]、文档聚类[3]、市场细分[4-5]、特征学习[6-7]等方面应用广泛。

K-Means[8]算法是一种基于划分的无监督学习聚类算法[9]，最早由Macqueen提出，该算法由于其简单、快速的特点得到了广泛应用，但算法存在难以估计簇数、随机选择的初始聚类中心会使结果陷入局部最优化、对离群点和孤立点敏感、无法识别非球形簇的数据等缺陷。

目前K-Means算法研究方向主要分为聚类簇数[k]值确定与初始聚类中心点确定两个方面。国内外众多学者提出了许多改进算法。文献[10]基于图像分割的思想，利用数据维数密度分析，使用分水岭算法对原始数据集进行分割，根据分割的区域中心点确定初始聚类中心，分割的区域个数作为簇数[k]。该方法在一定程度上能够获得准确的[k]值与初始聚类中心，但分水岭算法存在噪声敏感及过分割现象，若数据集含有噪声则聚类结果精度将大幅下降;文献[11]利用LOF离群点检测算法筛除离群点，在筛选后的样本中利用最大最小距离算法选择初始聚类中心，能有效避免离群点的影响，但筛选过程降低了算法效率;文献[12]通过比较[k]取所有可能值的聚类结果，选出其中聚类结果最佳[k]值，提出一种确定类簇个数的方法，但当[k]值变化范围很大时，该方法将耗费大量时间和精力;文献[13]提出的X-means算法，采用贝叶斯信息准则（BIC）计算得分，利用K-Means算法二分相应的簇，以此确定最优类簇个数;文献[14]利用期望最大化算法理论，提出似然函数的碎石图方法，对于不规则数据集的聚类结果比利用BIC方法更加可靠;文献[15]利用最小方差与密度之间的关系，提出一种利用最小方差优化初始聚类中心的方法，该方法在方差计算与比较上时间复杂度过高，且对于存在孤立点的数据不能获得较好的聚类结果;文献[16]采用最大最小距离方法，通过两阶段搜索获取最佳初始聚类中心，对数据集采用先分割后合并的思想获得分类结果，提出一种多中心距离算法。该方法对于不规则簇有良好的聚类能力。

本文在分析已有算法的基础上，提出一种基于最大距离中位数的改进算法，该算法基于K-Means算法，通过计算获取初始聚类中心点，可自适应确定类簇个数，在不增加迭代次数的情况下提升聚类结果准确率。仿真结果表明，本文算法聚类结果更加稳定。

1 最大距离中位数与SSE的自适应聚类算法

1.1 算法基本思想

K-Means算法基本思想为：将含有[n]个对象的数据集S划分为[k]个簇，簇中每个对象到簇中心距离最小。K-Means算法是一个不断迭代的过程[17]，影响该算法性能的一个重要方面是初始聚类中心点的选择，K-Means算法采用随机获取的方法，聚类结果易陷入局部最优解，另外在使用时必须提前设置好k值，具有一定局限性。

本文算法初始聚类中心点选择，借鉴K-Means++[18]算法的思想，将数据集中最有可能成为聚类中心且相距最远的两个点作为最初的选择点。在数据集中存在噪声或孤立点的情况下，如果直接选择相距最远两点作为初始聚类中心，一旦选择到的点为噪声或孤立点，聚类结果会陷入局部最优解。故本文提出最大距离中位数的方法，根据当前聚类数据点与相距最远两点和当前聚类中心点之间的距离大小关系，获取距离值为中位数的数据点，作为下一轮迭代的初始聚类中心点。该方法可有效避免选择噪声或者孤立点对聚类结果产生的影响。具体过程如下。

首先获取相距最远的点[xa]、[xb]，记录距离为[Dist]。计算所有点与[xa]、[xb]之间的距离[d]以及与初始聚类中心[ic]（当前簇的聚类中心点）之间的距离[dc]，为使数据点限定在各自相应的簇中，采用[dDist/2]且[dcDist/2]作为数据点过滤准则，满足要求的点的总距离[dsum=d+dc]会被记录下来;最后对记录集中的[dsum]进行从小到大排序，选择距离值为中位数的点作为新的初始聚类中心点。

通过SSE值变化趋势实现自动确定聚类簇数，曲线变化程度下降幅度最大位置为肘部，对应[k]值为最佳聚类个数，由此可得在此[k]值下聚类的SSE值为最佳值，往后会增加聚类个数，但SSE值变化很小，产生如图1所示的类似于肘部一般的曲线。但一些数据集在聚类过程中呈现出的SSE值变化曲线下降比较平滑，如图2所示，不易于直觀获取最佳的聚类个数[k]。本文对于第一种情况，由于变化曲线递减程度比较明显，利用本次与前一次的SSE差值对比[（SSE（t-1）-SSE（t））/SSE（t）]获取变化量;第二种情况，由于变化趋势不明显，可以采用区间变化值进行比较，每次比较两段区间内的SSE值变化量，即采用[SSE（t-2）-][SSE（t-1）]与[SSE（t-1）-SSE（t）]对比;将两种方法得出的变化量与设定的阈值进行比较，如果变化量小于设定的阈值变化量，则终止聚类运算，否则继续进行簇分裂操作，从而实现自动确定聚类簇数。簇分裂操作是根据已划分的簇SSE值与簇数据个数的平均值大小选择分裂平均值最大的簇，平均SSE值越大在一定程度上可以说明数据之间差异性较大，需要分裂以降低数据之间的差异性。簇的分裂采用K-Means算法。[SSE]值计算公式为：

其中，[k]表示当前类簇个数，[x]表示簇[Ci]中的数据点，[Oi]表示当前类簇质心。

1.2 算法步骤

给定数据集[S={x1，x2，？，xn}]，设定算法初始聚类中心集[C]，K-Means算法初始聚类中心点集合[C]，阈值[δ1]、[δ2]，聚类个数最大值[kmax]，迭代处理标志[flag]（[flag=3]表示算法步骤（3）进入迭代，[flag=7]表示跳转至步骤（7）），算法具体步骤如下：

（1）计算数据集S中所有数据点之间的距离[d（xi，xj）]，保存并从小到大排序。

（2）由于初始簇由当前整个数据集组成，故令初始[SSE（0）=∞]，[t=1]（簇数最小为1，也表示当前类簇的个数） ， 计算质心作为聚类初始中心[C（1）={X}]。

（3）定义迭代标志[flag=3]，处理过程中若发生变化，下一轮即满足聚类终止条件结束聚类。判断[C（t）=kmax]（[C（t）]也表示聚类簇数），若成立表示初始聚类中心点数已到达最大聚类个数，终止聚类，[flag=7];否则分别计算所有划分好的簇[Si]（[i]=1，…，t，表示第几个簇）的[SSE]值以及簇的数据个数[Num]。判断[SSE]值下降趋势变化量与阈值之间的关系：[SSE（t-1）-SSE（t）SSE（t）<δ1]，满足则终止聚类，[flag=7];否则继续判断[t3]（确保SSE含有两段可比较的曲线）且[SSE（t-2）-SSE（t-1）SSE（t-1）-SSE（t）<δ2]，满足则终止聚类，[flag=7]，否则执行步骤（4）。

（4）根据计算的[SSE]获取[SSE]均值最大的簇，记为[Smax=maxSSENum]，当前簇聚类中心标记为[cmax]，随后利用最大距离法找出[Smax]中相距最远的两个点[xa]和[xb]，两点之间距离记为[Dist=dxa，xb]，计算数据中所有满足要求的点，利用中位数方法获取距离中位数点[xc]和[xd]，返回[xc，xd]。

（5）令[t=t+1]（进行分裂操作，簇数加1），此时[xc，xd]两点分开拷贝至前一个聚类初始中心点[Ccmax]处，另一点则拷贝至当前初始聚类中心点[Ct]处。

（6）将[C]中的点作为初始聚类中心点，采用传统K-Means算法划分簇[Smax]，将[C]拷贝至[C]，在K-Means算法迭代中更新聚类中心集[C]，生成[C]个簇。之后将[C]拷贝至初始聚类中心集[C]中，[flag=3]。

（7）结束聚类运算，输出最终结果[t]、[C]，此时[t]值即最佳的类簇个数[k]值，初始聚类中心点集为[C]。

步骤（3）中根据SSE值的变化趋势判断是否终止聚类或继续簇分裂操作，从而自适应获取聚类簇数。步骤（4）是对于当前划分的簇中需进一步分裂的簇，决定要分裂哪一个簇，通过最大距离中位数方法获取新一轮迭代的初始聚类中心点。选择距离中位数点作为初始聚类中心可避免数据偏移（左偏或右偏）带来的影响，紧密度更高。

本文算法与K-Means算法最大的不同在于初始聚类中心点的选择，K-Means算法是随机选择，而本文算法是通过计算获取。K-Means算法时间复杂度为[O（knt）]，本文算法的时间复杂度为[O（n2）+O（k2nt）]，其中[k]为类别数，[n]为数据集包含的对象个数，[t]为聚类的迭代次数。虽然计算数据集中数据点之间的距离增加了算法时间开销，但是通过最大距离中位数方法获取的初始聚类中心点，相比随机选择的初始聚类中心点，最大距离方法降低了初始聚类中心点分布集中度，使得中心点分布更为分散。过于集中的点会增加迭代次数，而较分散的点通常会减少迭代次数[19]。中位数选择紧密程度相对高的点，即点距离聚类实际中心点更近，可进一步减少算法迭代次数，缩短迭代算法时间，迭代次数越少表明算法收敛越快，收敛性越好;其次本文算法可根据SSE值变化自动获取簇数k值大小，去除聚类之前对簇数k值的预估过程，在一定程度上提升了聚类算法效率。

2 实验结果与分析

2.1 实验数据集与实验环境

本文实验采用加州大学欧文分校提供的UCI机器学习库，选取Iris、Balance-scale、Wine、Seeds数据集作为测试数据集。实验编程语言为Java，测试用的主机CPU为Intel？ CoreTM i5-4210U CPU，主频为1.7GHz，内存为12GB，改进算法在IDEA上进行测试。实验主要性能指标为聚类准确率、迭代次数和运行时间。实验选择的Iris、Balance-scale、Wine、Seeds 4个数据集的统计信息如表1所示 。实验参数[δ1]为0.75，[δ2]为0.18，聚类最大个数[kmax]为[n]，其中[n]为数据集数据个数。

2.2 实验结果分析

由于K-Means算法聚类结果不稳定，实验中对K-Means算法运行结果采取运算10次结果取均值的方法参与比较，有利于提高实验结果分析合理性。

将不同算法运用至4个数据集上进行实验，将数据集分别读入写好的运算程序中，实验结果如表2—表4所示。其中表2为在Iris与Balance-scale数据集上的实验结果，表3为Wine数据集与Seeds数据集的实验结果，表4为各数据集在各算法下平均运行时间。

为了验证本文提出算法相比其它优化初始中心点算法具有较好的性能，本文选取文献[20]算法进行实验结果对比。

从表2—表3可以看出，在聚类准确率方面，本文算法相比传统算法在不增加迭代次数的情况下，Iris、Balance-scale、Wine、Seeds数据集聚类结果准确率分别提高了17.133%、22.416%、9.545%、0.238%。本文算法通过自适应得到各个数据集的类簇个数，其中Iris、Wine、Seeds数据集得出的类簇个数与数据集类簇个数一致，Balance-scale数据集本文算法自动获取2个类簇，相比数据集真实类簇个数少1个，但聚类准确率提升了22.416%，迭代次数减少了13.7次。

相比文献[20]算法，本文算法在不降低聚类准确率的同时，Iris、Wine、Seeds数据集运算迭代次数分别减少1次、4次、4次，对于Balance-scale数据集，虽然迭代次数一致，但准确率提升了0.96%。上述聚类结果对比表明，通过最大距离中位数方法计算获取的初始聚类中心点距离类簇实际聚类中心点更近，算法收敛次数更少，收敛速度更快，本文算法在初始聚类中心点的选择上性能更优。

从表4可以看出，由于文献[20]算法在算法开始阶段需计算各个数据点之间的距离大小并排序，且在进行簇分裂计算时需根据相应算法计算选出相对最佳初始聚类中心点，这些计算增加了算法时间复杂度，所以本文算法与文献[20]算法相比，运行时间更短。从本文算法与文献[20]算法的运行时间对比可以看出，4个数据集在本文算法下进行实验的整体运行时间均比文献[20]算法更短，表明迭代次数的减少可有效降低整体算法时间复杂度，提升算法运行效率。

3 结语

本文针对传统K-Means算法存在的主要缺陷，提出了一种基于最大距离中位数与SSE的自适应改进算法，利用最大距离取中位数的方法，通過计算获取初始聚类中心点，并根据SSE值变化趋势决定终止聚类或继续簇的分裂，自动确定数据划分类簇个数。实验结果表明，该算法可获取较高的聚类准确率和较为可观的收敛速度，聚类结果稳定且可自动获取聚类类簇个数，具有一定的技术优势和应用价值。

参考文献：

[1] 海沫，张书云，马燕林. 分布式环境中聚类问题算法研究综述[J]. 计算机应用研究，2013，30（9）：2561-2564.

[2] 邹旭华，叶晓东，谭治英.  一种密度峰值聚类的彩色图像分割方法[J].  小型微型计算机系统，2017，38（4）：868-871.

[3] SARDAR T H，ANRISA A. An analysis of MapReduce efficiency in document clustering using parallel K-means algorithm[J]. Future Computing and Informatics Journal，2018， 3（2）： 200-209.

[4] TLEIS M，CALLIERIS R，ROMA R. Segmenting the organic food market in Lebanon： an application of K-means cluster analysis[J]. British Food Journal， 2017， 119（7）： 1423-1441.

[5] HUNG P D，NGOC ND，HANH T D. K-means clustering using R A case study of market segmentation[C]. Proceedings of the 2019 5th International Conference on E-Business and Applications，2019：100-104.

[6] TANG J L，WANG D，ZHANG Z G，et al.Weed identification based on K-means feature learning combined with convolutional neural network[J]. Computers and Electronics in Agriculture，2017，135： 63-70.

[7] TANG J L， ZHANG Z G， WANG D， et al. Research on weeds identification based on K-means feature learning[J]. Soft Computing， 2018， 22（22）： 7649-7658.

[8] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]. Proceedings of Berkeley Symposium on Mathematical Statistics & Probability，1965：281-297.

[9] SAROJ K. Review：study on simple K-mean and modified K-mean clustering technique[J]. International Journal of Computer Science Engineering and Technology， 2016， 6（7）：279-281.

[10] WANG X，JIAO Y，FEI S. Estimation of clusters number and initial centers of K-means algorithm using watershed method[C]. Guiyang： International Symposium on Distributed Computing & Applications for Business Engineering & Science， 2015.

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

[12] 周世兵，徐振源，唐旭清.  K-means算法最佳聚类数确定方法[J]. 计算机应用，2010，30（8）：1995-1998.

[13] GOODE A. X-means： extending K-means with efficient estimation of the number of clusters[M]. Berlin：Springer，2000.

[14] 赵杨璐，段丹丹，胡饶敏，等. 基于EM算法的混合模型中子总体个数的研究[J]. 数理统计与管理， 2020， 39（1）：35-50.

[15] 谢娟英，王艳娥. 最小方差优化初始聚类中心的K-Means算法[J].  计算机工程，2014， 40（8）：205-211，223.

[16] 周涓，熊忠阳，张玉芳，等. 基于最大最小距离法的多中心聚类算法[J]. 计算机应用，2006，26 （6）：1425-1427.

[17] ANIL K J. Data clustering： 50 years beyond K-means[J]. Pattern Recognition Letters，2010， 31（8）：651-666.

[18] ARTHUR D，VASSILVITSKII S. K-means++： the advantages of careful seeding[C]. New Orleans： Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms， 2007.

[19] AGRAWL R， IMIELINSKI T， IYERB， et al. Mining K-Means rules between sets of items in large database[C]. Proceedings of ACM SIGMOD Conference on Management of Data，2013：1-10.

[20] 成衛青，卢艳红. 一种基于最大最小距离和SSE的自适应聚类算法[J]. 南京邮电大学学报（自然科学版），2015，35（2）：102-107.

（责任编辑：江 艳）