基于最大距离积与最小距离和协同K聚类算法

邹臣嵩 杨 宇

1(广东松山职业技术学院电气工程系 广东 韶关 512126) 2(广东松山职业技术学院机械工程系 广东 韶关 512126)

0 引 言

聚类分析作为统计学的一个分支，是机器学习领域的重要课题之一，目前被广泛应用于模式识别、图像分析、生命科学等领域的研究中。聚类的目的是将一个具有多维属性的数据集按照相似性分割成若干个子集，使得同一子集内各数据对象之间的相似性尽可能大，而不同子集间的相似性尽可能小[1-2]。聚类分析算法主要包括划分法、网格法、密度法、层次法以及基于模型的方法。作为一种典型的划分法，K-means算法具有简单、可靠、收敛速度快等优点，但其缺点也极为明显，仅适合对聚类结果为球形的数值型数据进行聚类，同时该算法对“噪声”较为敏感，因此增加了聚类结果的不稳定性。

国内外专家学者从聚类准确率、聚类耗时以及整体聚类质量等多角度对K-means算法进行了改进[3-9]，但这些改进更多集中在利用样本的分布信息优化初始聚类中心的选择，而针对簇中心在迭代过程中的更新方法改进较少。为此，本文提出了基于最大距离积与最小距离和协同的K聚类改进算法，根据样本集的分布特征划分数据集，启发式地确定初始聚类中心。在簇中心更新过程中，根据聚类完成后簇内距离之和最小的思想[6]，提出了“簇中心到簇内样本距离之和最小算法”MSDCC(Minimum Sum of Distance between Cluster Centers and Clusters)，并用MSDCC算法取代传统K-means的均值中心法来确定新的簇中心。UCI数据集的实验测试表明，本文算法的聚类准确率、整体耗时、Jaccard系数等有效性评价指标优于传统 K-means算法和文献[5-6]的算法，具有更好的聚类效果。

1 K-means聚类算法及其研究现状

传统K-means算法以k为参数，将n个对象分为k个簇，目标是簇内相似度高，簇间相似度低，通常将聚类误差平方和作为评价聚类质量的准则函数。K-means算法的流程是：首先随机选取k个数据对象作为初始聚类中心，对剩余的每个对象根据其与各个中心的距离划分到最近的簇，然后将每个簇的平均值作为新的簇中心，并再次按最小距离划分样本到新的簇，如此反复迭代直到准则函数收敛，即各簇中心保持不变。

传统的K-means算法对初始聚类中心敏感，选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率。此外，传统的K-means算法仅适合数值型数据且聚类结果为球形的数据集，不适合于发现非凸形状的簇或者大小差别很大的簇[8]。因此,当样本集中存在孤立点时，孤立点的某个或某几个特征值必然与样本中的其他数据对象相差甚远，均值中心法生成的簇中心将严重偏离真实中心，只能通过多次迭代来修正聚类中心，不仅耗时严重，还可能因此而降低聚类准确率。所以，恰当地选择初始聚类中心，合理地改进簇中心更新算法不仅可以提高聚类准确率，还可以减少簇中心更新耗时，进而从整体上提升算法的运算效率。

近年来研究人员围绕聚类中心的选择与优化提出了新的计算方法，目的是令中心点更加分散，更加符合样本的分布情况。如熊忠阳等[5]在密度法的基础上选取到所有已初始化聚类中心距离乘积最大的高密度点作为聚类中心；翟东海等[6]用最大距离法选取初始簇中心，并构造了一种将文本相似度转化为文本距离的方法；盛华等[7]针对K-means算法存在的问题，提出一种融合K-means算法与聚类的快速搜索和发现密度峰算法的聚类算法；周鹿扬等[8]提出了一种基于聚类中心的快速聚类算法，将数据集中较大或延伸状的簇分割成若干球状簇，而后合并这些小簇，较好地适应任意形状数据集。田诗宵等[9]为各样本点引入局部密度指标，根据其局部密度分布情况，选取处于密度峰值的点作为初始质心；褚睿鸿等[10]提出了一个基于密度峰值的聚类集成模型，使用改进的最大信息系数表示各基聚类结果之间的相关性；陈晋音等[11]提出了基于自动确定密度聚类中心的聚类算法。

在上述文献基础上，本文将聚类算法的准确率与时间性能的提升作为研究目标，提出了基于最大距离积与最小距离和协同的K聚类改进算法，从初始聚类中心的合理性选择和簇中心的快速更新两个方面对K-means算法进行了改进。

2 基于最大距离积与最小距离和协同K聚类算法

本文算法将聚类划分成两个阶段：选择初始聚类中心阶段和更新簇中心阶段，基本思路如下。

在选择初始聚类中心阶段，首先计算样本集X中各数据对象的密度，从而得到样本集的平均密度。然后将密度值大于样本平均密度一定倍数的数据对象视为高密度点，并划分至高密度点集合D中，再计算D中各高密度点与样本集X的中心Xcenter之间的距离，将到Xcenter距离最远的高密度点C1存储至初始聚类中心集合C中，再将与Xcenter和C1距离乘积最大的高密度点C2存储至C中。同理，在集合D中选取到Xcenter、C1及C2距离乘积最大的高密度点C3存储至C中。以此类推，得到全部初始聚类中心集合C={C1，C2，…，Ck}。

本文算法的基本概念、算法描述以及时间复杂度分析具体如下。

2.1 基本概念

设X={X1,X2,…,Xi,…,Xn}为含有n个数据对象的样本集合，每个样本含有p个属性Xi={Xi1,Xi2,…,Xip}。现将该集合划分为k个簇，即X={Cluster1,Cluster2,…,Clusterk}，每簇含样本m个，簇中心所构成的集合C={C1,C2,…,Ck}(k

定义1空间两点间的欧氏距离定义为：

(1)

式中：i=1,2,…,n;j=1,2,…,n;w=1,2,…,p。

定义2空间任意两点间距离平均值定义为：各样本间的距离总和除以从样本集中任意选取两个样本的所有排列次数。

(2)

定义3样本Xi的密度定义为：以Xi为圆心，以α×avgDist为半径的圆内(含圆上)所包含数据对象的个数，即当满足条件d(Xi,Xj)≤α×avgDist时，count()函数累计加1，α是半径调节系数，默认值为1。

(3)

式中：i=1,2,…,n;j=1,2,…,n。

定义4样本集X的平均密度定义为：

(4)

定义5高密度点集合定义为：密度高于样本集X的平均密度一定倍数的数据对象组成的集合。

D={Xh}

(5)

式中：Xh为满足dens(Xh)≥β×avgDens的数据对象，Xh∈X，β是密度调节系数，默认值为1。

定义6样本集X的中心是X的均值，定义为：

(6)

定义7样本Xi与簇内其他数据对象的距离之和定义为：

(7)

式中：Xi∈Clustert，Xj∈Clustert，t=1,2,…,k。

定义8簇内距离和矩阵定义为：

(8)

式中：t=1,2,…,k。

定义9在簇中心更新过程中，将与簇内其他样本距离之和最小的数据对象Xi作为该簇的中心，Xi满足以下条件：

distSum_X(i)=min(distSum_Cluster(t))

(9)

式中：t=1,2,…,k。

定义10聚类误差平方和E的定义为：

(10)

式中：Xij是第i簇的第j个数据对象，Ci是第i簇的中心。

2.2 算法描述

1) 选择初始聚类中心：

(1) 根据式(1)-式(3)计算样本集X中各数据对象的密度；

(2) 根据式(4)-式(6)得到高密度点集合D和样本集中心Xcenter；

(3) 根据式(1)计算D到Xcenter的距离，选择满足max(d(Di，Xcenter))的数据对象Di作为第一个初始聚类中心C1加入集合C中；

(4) 选择满足max(d(Dj，Xcenter)×d(Dj，C1))的数据对象Dj作为第二个初始聚类中心C2加入集合C中；

(5) 重复步骤(4)，直到集合C中的元素个数等于k，即|C|=k。

2) 更新簇中心：

(1) 根据式(1)计算样本集X中各数据对象与C中各中心点的距离，并按最小距离将各对象划分至最近的簇中；

(2) 根据式(7)、式(8)得到簇内距离和矩阵distSum_Cluster；

(3) 根据式(9)从distSum_Cluster中查询簇内样本距离之和最小的数据对象，并将其作为一个新的簇中心存入集合C′中；

(4) 重复2)中的步骤(2)、(3)，更新各簇的中心，直到|C′|=k，再用C′取代C。

3) 划分数据：

(1) 将样本集X中的数据对象按距离划分到最近的簇中；

(2) 根据式(10)计算本次聚类误差平方和E，判断是否收敛，如果收敛，则聚类算法结束，否则转到2)，再次更新簇中心。

2.3 时间复杂度分析

K-means算法的时间复杂度为O(nkT)，其中T是算法的迭代次数，k是聚类个数，n是数据集样本个数。与传统K-means算法相比，本文算法的时间复杂度有两处变化：一是在初始聚类中心的选择上用基于密度的最大距离乘积法取代传统的随机选取算法；二是在更新簇中心过程中用MSDCC算法取代了传统的均值算法，时间复杂度变为O(n2+nkt)。在初始聚类中心选择阶段，n2>n，所用时间大于传统算法，但各中心点相对分散且具有较强代表性，这使得簇中心在更新过程中可以快速逼近全局最优解，因此迭代次数减少，故t<

对于小规模样本集，本文算法的时间性能在整体上优于传统K-means和文献[5-6]，实验测试也证明了上述分析。但对于大样本集，初始聚类中心的选择耗时较长，此时本文算法的时间性能将有所下降。

3 实验结果与分析

本文的实验环境：Intel Core i3-4010 1.70 GHz，2 GB内存，500 GB硬盘，Win7操作系统，实验平台为Matlab 2011b，测试所用的6个UCI数据集描述如表1所示。

表1 实验所用的UCI数据集

为检验MSDCC算法对聚类准确率和聚类时间这两项指标的影响，实验中对文献[5-6]算法和本文算法进行了交叉验证，具体为：用MSDCC算法取代文献[5-6]在簇中心更新过程中所使用的均值法；用均值法取代本文的MSDCC算法。文献[5-6]和本文算法改动前后的对比实验结果如表2-表4所示。为便于理解，修改后的算法分别记为“文献[5] + ”、“文献[6] + ”和“本文-”。

表2 均值法和MSDCC法的聚类准确率比较 %

表3 均值法和MSDCC法的簇更新时间比较 ms

表4 均值法和MSDCC法的迭代次数比较

从表2-表4可见，使用MSDCC算法后，文献[5-6]和本文算法的聚类准确率稳中有升，迭代次数明显小于使用前，簇中心更新时间明显减少。由于MSDCC算法和“均值中心法”在簇中心更新过程中的选择方式不同，前者需要重新计算样本间的距离，运算量远大于后者，所以每次更新所用时间必然大于后者。但是MSDCC算法遵循这样一个事实，即每次簇更新后，簇中心必然被其他样本紧密围绕，簇中心与簇内其他样本的距离之和一定最小。因此，每次簇更新后所选择的簇中心更加接近最优解，进而减少了簇中心的更新次数，减少了更新耗时。

图1-图8是K-means算法、文献[5-6]算法和本文算法在UCI数据集上的对比实验结果。考虑到K-means算法的特殊性，将算法运行20次后所得到的平均值作为其最终结果。

图1 初始中心选择耗时比较 图2 簇中心更新耗时比较

图3 聚类总耗时比较 图4 簇中心更新次数比较

图5 Rand指数比较 图6 Jaccard系数比较

图7 Adjusted Rand Index参数比较 图8 聚类准确率比较

由图1可知，在初始聚类中心选择阶段，三种改进算法耗时明显大于传统K-means算法，这是因为后者在选取聚类中心时无需额外计算，固耗时少，速度快。而三种改进算法对这一过程进行了优化，计算量有不同程度的增加，耗时也相对增加。此外，本文算法在该阶段的耗时略高于文献[5-6]，主要原因是：本文算法先对整个样本集的密度参数进行了计算，在此基础上又采用了最大距离乘积法对高密度点集合从分布合理性的角度进行了多次筛选，增加了计算开销，故耗时略高。

由图2可知，在簇中心更新阶段，三种改进算法的耗时明显小于传统K-means算法，这是因为三种改进算法的初始聚类中心基本体现了数据对象的大致分布，从而减少了本阶段的迭代次数(结果详见表4)，故耗时减少。需要特别指出的是，本文算法在此阶段的耗时小于文献[5-6]，这说明使用MSDCC算法所得到的簇中心，可以更准确地反映数据集的整体分布情况。

由图3、图4可知，与其他三种算法相比，本文算法总耗时短、迭代次数少、收敛速度快，这是由于K-means算法随机选择初始聚类中心，容易导致同一个簇的两个数据对象被错误的当作两个簇中心，使得总迭代次数与总耗时同时增加。另一方面，文献[5-6]虽然对初始聚类中心的选择进行了改进，但簇中心的更新依然沿用传统K-means的均值算法，这使得中心点代表性较差，因此迭代次数及总耗时都大于本文算法。

关于算法聚类结果的评价，本文还采用三个典型的外部评价指标[12-16]和聚类准确率对四种算法分别进行了比较。如图5-图8所示，本文算法在Rand指数、Jaccard系数、Adjusted Rand Index参数、聚类准确率这四个聚类有效性指标对比测试中，结果优于其他三种算法。UCI数据集的实验结果分析可以得出：本文算法在收敛速度、聚类准确率等多项评价指标中表现良好，因此，可以应用于实际数据的聚类。

4 结 语

本文将聚类算法的准确率与时间性能的提升作为研究目标,根据数据对象的自然分布，给出了密度参数的计算公式。并在此基础上改进了最大距离乘积法，得到了具有良好代表性的初始聚类中心，在簇中心更新过程中，提出了“簇中心到簇内样本距离之和最小算法”，选取合适的数据对象作为簇中心。对比测试表明，本文算法对聚类中心的选取更加合理，聚类结果更加理想。在实际应用中，本算法对现代学徒制的课程序列进行了聚类挖掘[17]，快速准确地完成了课程的识别、分类、分级和序化四个的任务，评测指标优于其他三种算法。但是在实验中也发现，在中小规模数据集上本文算法的时间性能明显优于传统K-means算法，但随着数据集规模的增大，本算法的时间性能出现下滑。因此，作为下一步研究工作，应在提高聚类准确率的同时进一步提升算法的整体时间性能，以寻求更为合理高效的聚类方法。

参 考 文 献

[1] 于海涛,贾美娟,王慧强,等.基于人工鱼群的优化K-means聚类算法[J].计算机科学,2012,39(12):60-64.

[2] Han Jiawei,Kamber M,裴健.数据挖掘概念与技术[M].范明,孟小峰,译.3版.北京:机械工业出版社,2013:288-347.

[3] Zhang X,Furtlehner C,Germainrenaud C,et al.Data Stream Clustering With Affinity Propagation[J].IEEE Transactions on Knowledge & Data Engineering,2013,26(7):1644-1656.

[4] Ntoutsi I,Zimek A,Palpanas T,et al.Density-based Projected Clustering over High Dimensional Data Streams[C]//Proceedings of the 2012 SIAM International Conference on Data Mining,2012:987-998.

[5] 熊忠阳,陈若田,张玉芳.一种有效的K-means聚类中心初始化方法[J].计算机应用研究,2011,28(11):4188-4190.

[6] 翟东海,鱼江,高飞,等.最大距离法选取初始簇中心的K-means文本聚类算法的研究[J].计算机应用研究,2014,31(3):713-715,719.

[7] 盛华,张桂珠.一种融合K-means和快速密度峰值搜索算法的聚类方法[J].计算机应用与软件,2016,33(10):260-264,269.

[8] 周鹿扬,程文杰,徐建鹏,等.一种基于聚类中心的快速聚类算法[J].计算机科学,2016,43(S1):454-456,484.

[9] 田诗宵,丁立新,郑金秋.基于密度峰值优化的K-means文本聚类算法[J].计算机工程与设计,2017,38(4):1019-1023.

[10] 褚睿鸿,王红军,杨燕,等.基于密度峰值的聚类集成[J].自动化学报,2016,42(9):1401-1412.

[11] 陈晋音,何辉豪.基于密度的聚类中心自动确定的混合属性数据聚类算法研究[J].自动化学报,2015,41(10):1798-1813.

[12] 张惟皎,刘春煌,李芳玉.聚类质量的评价方法[J].计算机工程,2005,31(20):10-12.

[13] 于剑,程乾生.模糊聚类方法中的最佳聚类数的搜索范围[J].中国科学E辑:技术科学,2002,32(2):274-280.

[14] 卞彩峰,邱建林,陈燕云,等.基于粒计算的k值选取及其应用[J].计算机工程与设计,2015,36(11):3082-3086.

[15] Hubert L,Arabie P.Comparing partitions[J].Journal of Classification,1985,2(1):193-218.

[16] 谢娟英,郭文娟,谢维信,等.基于样本空间分布密度的初始聚类中心优化K-均值算法[J].计算机应用研究,2012,29(3):888-892.

[17] 杨宇,邹臣嵩,谭永洲,等.一种基于序列聚类的现代学徒制课程体系建构方法[J].韶关学院学报,2017(6):22-25.