李瑞珠 刘锡鹏
摘要:针对不同的数据特点,已有多种用于算法优化的聚类评价指标被提出。大量数据测试发现,仅使用单一评价指标无法可靠地体现数据的聚类划分优劣,传统的单一指标聚类优化算法在聚类准确度上还有待提高。一种新型的多指标投票评价策略被提出,并应用于粒子群聚类优化算法中。多指标投票评价的设计思路是依靠过半数的评价指标对解的优劣进行判定,从而避免单一指标的错误评价影响优化算法中的群体更新。经多份数据测试,与单指标评价的聚类算法进行对比,多指标评价粒子群聚类优化算法获得更优的聚类结果。
关键词:多指标投票;粒子群算法;聚类优化;单指标;指标评价
中图分类号:TP301.6 文献标识码:A
文章编号:1009-3044(2021)13-0184-04
Abstract: For different data characteristics, a variety of clustering evaluation indicators for algorithm optimization have been proposed. A large number of data tests have found that only a single evaluation index cannot reliably reflect the pros and cons of data clustering. The traditional single index clustering optimization algorithm needs to be improved in clustering accuracy. A new multi-index voting evaluation strategy is proposed and applied to the particle swarm optimization algorithm. The design idea of multi-index voting evaluation is to rely on more than half of the evaluation indexes to judge the pros and cons of the solution, so as to avoid the wrong evaluation of a single index from affecting the group update in the optimization algorithm. After multiple data tests, compared with the single-index evaluation clustering algorithm, the multi-index evaluation particle swarm optimization algorithm obtains better clustering results.
Key words: multi-index voting; PSO; clustering optimization; single index; index evaluation
1 背景
聚類分析提供由个别数据对象到数据对象所指派到簇的抽象。而目前已有的算法面对日前趋于多样化的数据集,仍然存在可提高的空间。
基于粒子群优化(Particle Swarm Optimization, PSO)的聚类算法已在UCI标准数据集iris与wine上做了测试,并与K-means算法、粒子群 K-means算法进行对比[1],对比结果仍可优化。尔后,一种自适应惯性权重函数对粒子群算法进行动态调整的设计被提出,并融入K-means算法,帮助初始化聚类中心,应用于电子病历聚类分析,提高了聚类准确率和效率[2]。
Omran等人[3]提出了一种基于粒子群优化的无指导图像分类算法。这是最早提出的基于粒子群的聚类算法的应用,之后的粒子群聚类算法大都遵循其基本思想。Elhabyan等人[4]将基于PSO算法的聚类方法应用于无线传感网,并在传感网络的生命周期上取得更优的效果。Santar等人[5]提出了针对无线传感的能量有效性的粒子群聚类算法,提高能量优化率。Kaur等人[6]继续将PSO算法应用于无线传感网中,完成了群集内和群集间能耗的平衡。Vidyadhari等人[7]将PSO算法用于自适应文本聚类,在标准数据集的测试上,提高了文本聚类的正确率。综上,无论国内抑或是国外,对于有关粒子群的聚类算法的研究都是针对具体某一应用,聚类的综合性能还存在提高的空间,且对比对于单一评价标准来说还可拓展。
本文对7种常用的聚类内部指标,与4个外部指标进行聚类分析比较,通过对7份经典数据集的聚类分析发现单一指标值的优劣不一定代表聚类质量的优劣,因此认为对于目前单指标评价的聚类存在缺陷。
为解决单指标单一的指导问题,提高结合基于PSO算法的聚类方法的综合性能,本文设计了多指标综合评价机制,提出一种基于多指标投票综合评价的粒子群聚类方法,集成多个内部指标,基于优化历史信息与当前种群的解质量,自适应选择对当前解最合理的聚类评价结果,并与单指标的基于粒子群的聚类算法进行多数据集实验测试对比。实验数据表明,多指标综合评价机制的加入能有效提高聚类的准确度,相较单指标评价,多指标评价表现更优。
2 相关工作
2.1 聚类有效性指标
内部指标的选择有很多,本文选择应用较为广泛的、针对类间距与类内距的7个指标,如表1所示。
其中CH[8]、Dunn[9]、SIL[10]、DB[11]、CS[12]提出较早,都已在具体的数据问题上得到了应用[13],因此作为多指标评价机制主要成员较为可靠。GD33与GD53,提高了Dunn指标的抗噪能力,选择二者旨在克服多样化数据集的噪声特点,完成对优化聚类的指导。
对于已知聚类分类类别,用于检验算法聚类结果优劣的指标,称为外部指标。常用的外部指标有调整的兰德系数(Adjust Rand Index,简称ARI),Jaccard系数(简称JacI)和Fowlkes and Mallows 系数(简称FMI)。这些指标值都是越大越好,当值为1时表示完全正确的分类。其中ARI是对兰德系数R指标的调整,改进了随机产生聚类时,指标值不为0的情况[18]。Jaccard系数[19]不注重聚类使用的方法,只注重结果,符合针对聚类结果的评价要求。FMI结合查准率与查全率的思想完成聚类性能的评价[20]。本文综合上述3个外部指标,较为全面地完成聚类结果与性能的评价。
2.2 粒子群聚类算法
本文采用基于粒子群聚类算法[21],结合6份经典数据集,进行聚类测试,分析聚类测试结果,计算7个内部指标,并计算该聚类结果与标记数据对比获得的3个外部指标,验证单指标聚类存在的缺陷。
2.2.1 编码方案
设定聚类类别数的最大值[Kmax],种群的个体编码为D=[Kmax+Kmax*d]维的向量
[Zi=(Ti1,Ti2,...,TiKmax,mi1,mi2,...,miKmax)],[d]为数据维度数,[mij]是簇中心的坐标向量,[Tij(j=1,...,Kmax)]是得到类别质心点的激活阈值。如果[Tij]大于0.5,则对应簇的质心点[mij]被激活,否则不被激活。
如图1所示,一个维度[d]为2,最大聚類类别数[Kmax]为4的某个个体,0.5为激活阈值,第二个位置0.4小于0.5,因此它对应的第二个质心为未激活状态,以此类推,其他位置的阈值大于0.5从而被激活。因此,这个个体的聚类数目为3。
2.2.2 算法流程
下面简要介绍PSO算法流程:
1)在[0,1]范围内初始化每个粒子的激活阈值。
2)在每个维度的变量动态范围的10%-20%左右随机初始化每个粒子的速度。
3)对于种群中的每一个粒子,提取聚类中心,并将每个对象分配给特定的集群中心形成集群,然后计算适应度。
4)更新全局与局部最优解,根据如下公式(1)与公式(2)更新粒子的速度与位置。
其中,[vkid]表示第k次迭代粒子i速度矢量的第d维分量; [xkid]表示第k次迭代粒子i位置矢量的第d维分量;[c1],[c2]表示加速度常数;[r1],[r2]表示两个随机参数,取值范围[0,1];[ω]表示惯性权重。粒子i的历史最优解用pbesti=(pbesti1, pbesti2,…, pbestid)表示,整个群体找到的已知最优解用gbest=( gbest1, gbest2,…, gbestd)表示。
5)循环执行步骤3)与步骤4),直到从全局获得最佳的集群分区,达到最终终止条件时获得最终解决方案,该条件为所需的最大迭代次数。
3 单指标实验分析
本文首先研究了多种内部指标在聚类优化中的评价能力。基于PSO的聚类测试实验数据参数设置如表2所示:
用于单指标实验的6份经典数据集信息如表3所示。其中包括用于二分类的经典数据集breastcancer、banknotes,常用于分类学习的标准数据集iris、wine,多变量分类数据集faults,以及双月数据集half-ring。
下面将各个指标值做了标准化计算绘制于同一坐标系中,具体标准化公式如下所示:
[nindexi=indexi/max(index1,index2,...,indexL)] (3)
其中,[L]表示测试的指标总数,[indexi]表示当前指标值。
图2是以wine数据集为例,以迭代代数为横坐标,以CH指标越大越好为PSO聚类算法的优化目标下,得到的最优解对应各个内外部指标根据标准化公式计算得到的相对值为纵坐标绘制的迭代变化趋势图,用于观察每一个内部指标在聚类评价时的表现。
当外部指标已经达到最优值的时候单内部指标评价并没有达到最优,如图2(a)中的CH指标等,而当内部指标评价达到最优的时候,外部指标甚至仅有0.5的表现,例如图2(b)与(c)等。这个结果反映出了单一内部指标在找到较优的聚类解时,其对解质量好坏的区分能力不足,单一指标值的优劣不一定代表聚类质量的优劣, 单内部指标指导下的聚类存在缺陷。
4 多指标评价聚类优化投票评价策略
为了更加合理地利用指标的指示能力,本文提出多指标评价的聚类优化投票评价策略。
具体做法就是在粒子群算法的迭代过程中,把传统的根据单一内部指标计算适应度进行粒子更新的步骤,更改为多指标评价的方式。7个内部指标作为选择更优解的7个评委,分别对所有解进行自己独立的评价,根据指标值的大小完成评价,类似于投票,将自己的一票投给各自认为更好的解,根据解所得到的票数多少,确定局部最优解,再与全局最优解进行对比,从而确定全局最优解。
步骤1:初始化方式与PSO算法相同。此外,初始化7个指标评价信息indexi(i=1,…,7);记录所有个体i的pbesti都为初始解xi;
步骤2:进入算法迭代过程:
while(迭代次数小于最大迭代次数)do {
a.采用PSO迭代过程更新种群。对于每一个粒子i,根据指标公式计算得到7个新的指标值indexj(j=1,…,7);
b.初始化当前种群的最优个体号bi = 0,初始化全局最优gbest的7个指标值indexn(n=1,…,7);
c.所有指标对解质量优化与否进行评价:
indexi与计算得到的指标值indexj进行比较,CH、Dunn、SIL、GD33、GD53值较大的个体得到对应指标的支持,DB、CS值较小的个体得到对应指标的支持,更新得到对应指标支持的评价信息indexi,未得到支持的评价信息不做更新;
d.匯总多指标评价结果:①超过一半的内部指标(≥4)认为解质量变优则用当前解替换pbest;
②超过一半的内部指标(≥4)认为当前解优于全局最优解,则将当前个体的个体号作为当前种群的最优个体号,bi = 当前个体号,同时更新当前种群最优内部指标indexn(n=1,…,7), bi个体更新为全局最优指代gbest;
}
end while
5 实验测试与比较
5.1 实验数据
为增加不同分布类型的数据拓展算法综合性能测试,本实验除了表3中标准数据集UCI中的经典数据与多变量数据、环形数据,还使用了如表4所示的人工生成数据,其中50d4c、50d10c、100d4c三份数据集用于高维空间的测试,是以高维度创建的椭圆形簇;2d4c、2d10c、2d20c、10d20c是由标准聚类模型生成的聚类。
5.2 实验设置
本实验测试了PSO聚类算法,并加入本文提出的多指标评价方法进行实验测试,对比其分别使用单指标CH,Dunn和SIL进行优化的结果。外部指标AR、FM、Jaccard用于聚类优化算法的评价对比标准。
5.3 结果对比与分析
为展示多指标评价这一步骤的加入对聚类算法的影响,下面将基于PSO的聚类分别对比增加了多指标评价步骤的PSO聚类,仍然以三个外部指标作为对比标准。表5是多指标评价PSO聚类优化算法与单指标PSO聚类算法的外部指标对比,以CH、Dunn、SIL指标为例。
观察单指标聚类的外部指标结果,可以发现在单指标的指导聚类下,部分数据集的聚类结果十分不理想,例如:表5中transfution、banknotes等数据集,3个外部指标的评价未到达0.6,甚至仅有0.11的评价。而且,单指标指导聚类在不同数据集的测试中表现也较为不稳定。
最后,综合观察表5,可以很清晰地看出,13份数据集中,11份数据集(84.62%的数据集)的聚类结果外部指标值在加入多指标评价后大于未加入该步骤的聚类方法的外部指标,这表示多指标评价机制在提高聚类的准确度上具有优势,有助于优化聚类,且面对多样化的数据集,包括:标准数据集、人工生成数据集,多指标评价机制的加入都大大提高了聚类优化能力。
为了进一步分析算法迭代收敛情况,图3给出了iris数据集的多指标评价PSO与单指标(CH、Dunn、SIL)评价的PSO算法的最优解在外部指标ARI下的变化趋势对比图。图中可以发现,单指标ARI指标值仅在0.7左右,而多指标综合评价下的聚类结果相对比单指标的聚类结果更优,达到了0.9的效果,与单指标的结果对比可以更快获得更优的结果。加入多指标评价策略的PSO收敛速度更快,结果也优于相同迭代次数下的PSO算法。
综上可以认为:多指标综合评价下的聚类结果在准确率与寻优效率上得到了理想提高。
6 结束语
多指标评价粒子群自适应聚类优化算法通过多指标评价机制与粒子群聚类算法的结合,提高粒子群聚类算法的聚类准确度,此外,实验结果还发现,加入多指标评价能有效改善单指标对聚类的单一化指导,让数据从历史解过程中向所属类别靠拢。后续,在不影响算法准确率的基础上提高算法的效率问题是重点需要研究的内容。
参考文献:
[1] 姚丽娟,罗可,孟颖.一种基于粒子群的聚类算法[J].计算机工程与应用,2012,48(13):150-153,175.
[2] 沐燕舟,丁卫平,高峰,等.基于自适应PSO的改进K-means算法及其在电子病历聚类分析应用[J].计算机与数字工程,2019,47(8):1861-1865.
[3] Omran M G, Engelbrecht A P, Salman A.Image classification using particle swarm optimization[C]//Proc of the 4th Asia-Pacific Conference on Simulated Evolution and Learning,2002:370-374.
[4] Elhabyan R S, Yagoub M C E.PSO-HC:Particle swarm optimization protocol for hierarchical clustering in Wireless Sensor Networks[C]//International Conference on Collaborative Computing: Networking.IEEE,2015.
[5] Santar Pal Singh,Subhash Chander Sharma.PEECA:PSO-Based energy efficient clustering algorithm for wireless sensor networks[C]// International Journal of Computer Network and Information Security,2017,5(9):31-37.
[6] Kaur T,Kumar D.Particle swarm optimization-based unequal and fault tolerant clustering protocol for wireless sensor networks[J].IEEE Sensors Journal,2018,18(11):4614-4622.
[7] Vidyadhari C,Sandhya N,Premchand P.Particle grey wolf optimizer (PGWO) algorithm and semantic word processing for automatic text clustering[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2019,27(2):201-223.
[8] Caliński T,Harabasz J.A dendrite method for cluster analysis[J].Communications in Statistics,1974,3(1):1-27.
[9] Dunn J C.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J].Journal of Cybernetics,1973,3(3):32-57.
[10] Rousseeuw P J.Silhouettes:a graphical aid to the interpretation and validation of cluster analysis[J].Journal of Computational and Applied Mathematics,1987(20):53-65.
[11] Davies D L,Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979,PAMI-1(2):224-227.
[12] Chou C H,Su M C,Lai E.A new cluster validity measure and its application to image compression[J].Pattern Analysis and Applications,2004,7(2):205-220.
[13] Lord E,Diallo A B,Makarenkov V.Classification of bioinformatics workflows using weighted versions of partitioning and hierarchical clustering algorithms[J].BMC Bioinformatics,2015,16(1):1-19.
[14] Rathore P,Ghafoori Z,Bezdek J C,et al.Approximating dunn's cluster validity indices for partitions of big data[J].IEEE Transactions on Cybernetics,2019,49(5):1629-1641.
[15] Xu R,Xu J,Wunsch D C.A comparison study of validity indices on swarm-intelligence-based clustering[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),2012,42(4):1243-1256.
[16] Hang W L,Choi K S,Wang S T.Synchronization clustering based on central force optimization and its extension for large-scale datasets[J].Knowledge-Based Systems,2017,118:31-44.
[17] Kim M,Ramakrishna R S.New indices for cluster validity assessment[J].Pattern Recognition Letters,2005,26(15):2353-2363.
[18] Rand W M.Objective criteria for the evaluation of clustering methods[J].Journal of the American Statistical Association,1971,66(336):846-850.
[19] Halkidi M,Batistakis Y,Vazirgiannis M.On clustering validation techniques[J].Journal of Intelligent Information Systems,2001,17(2/3):107-145.
[20] Fowlkes E B,Mallows C L.A method for comparing two hierarchical clusterings[J].Journal of the American Statistical Association,1983,78(383):553-569.
[21] Chen G B,Song A,Zhang C J,et al.Automatic clustering approach based on particle swarm optimization for data with arbitrary shaped clusters[C]//2016 Seventh International Conference on Intelligent Control and Information Processing (ICICIP).December 1-4,2016,Siem Reap.IEEE,2016:41-48.
【通聯编辑:谢媛媛】