自适应AP聚类算法研究

赖健琼

摘  要： 偏向参数和阻尼因子是影响AP聚类算法聚类效果的两个重要参数，但他们均取固定值。随着数据量的改变，原有参数取值不能使算法聚类结果达到最优。鉴此，本文提出自适应AP聚类算法，当数据量发生改变时，自动调整并获取最优的偏向参数和阻尼因子，最终得到最优聚类结果。与原来算法相比，改进后的算法能自动消除震荡，还可获取最优聚类结果，提高聚类结果的准确性和算法快速性。通过人造数据集和Iris数据集实验，证明了自适应AP聚类算法的有效性。

关键词： AP聚类; 自适应AP聚类; 偏向参数; 阻尼因子

中图分类号：TP18          文献标识码：A     文章编号：1006-8228（2022）04-38-05

Research on adaptive AP clustering algorithm

Lai Jianqiong

（School of Intelligent Technology， Tianfu College of Swufe， Mianyang， Sichuan 621000， China）

Abstract： Bias parameter and damping factor are two important parameters that affect the clustering effect of AP clustering algorithm， but they both take fixed values. As the amount of data changes， the original parameter values cannot make the algorithm clustering result optimal. In this paper， an adaptive AP clustering algorithm is proposed. When the amount of data changes， it automatically adjusts and obtains the optimal bias parameters and damping factors， and finally obtains the optimal clustering result. Compared with the original algorithm， the improved algorithm can automatically eliminate the vibration， and can also obtain the optimal clustering results， which improves the accuracy of the clustering results and the speed of the algorithm. Experiments on artificial datasets and Iris datasets demonstrate the effectiveness of the adaptive AP clustering algorithm.

Key words： AP clustering; adaptive AP clustering; bias parameter; damping factor

0 引言

AP（Affinity propagation）[1-2]聚类算法是Frey和Dueck在2007年的Science上提出的一种基于代表点的新的聚类算法。该算法开始时是将N个数据点都作为代表点（或称作数据中心），利用N个数据点之间的相似度构造[N×N]相似度矩阵作为“消息传递”基础，通过迭代求精寻找最优代表点列表，将各数据点分配给最近代表点所属的类，最终得到新的聚类结果。然而经典的K-means聚类算法，聚类数目需要用户自己设定，对初始聚类中心敏感，易产生局部最优解，这些不足导致每次聚类结果几乎总是不同。和经典聚类算法K-means聚类相比，AP聚类算法不单避免了这些缺陷，而且有简单、高效和快速等优点。例如，将75000个DNA片段分组为2000组，通常需要花上数百小时的计算时间完成的任务可能在几分钟之内就可以完成[3]。

AP聚类算法自提出以来就得到相关专业人士的青睐，在很多领域得到广泛的应用。如商务智能[4]、图像分割[5]、生物医学[6]和文本数据挖掘[7]等方面。AP聚类算法中有两个重要参数：置于相似度矩阵similarity对角线上的偏向参数p和responsibility（吸引度）、availability（歸属度）在迭代更新中防止发生震荡的阻尼因子lamda。如何选择合适偏向参数产生最优聚类结果，以及当算法发生震荡后如何消除震荡并收敛是AP聚类算法尚未解决的问题。针对这个问题，王开军[8-9]，肖宇[10]，刘晓勇[11]，胡久松[12]等人对该算法进行改进。

原始AP聚类算法偏向参数p和阻尼因子lamda的选择影响聚类算法的准确性和收敛速度。由于原有的法中p（根据先验知识选取或取相似度矩阵similarity的中值）和lamda（一般取0.5～0.9）均取固定值，随着数据量的增大，不仅会使最终的聚类结果的准确度降低，还很有可能导致算法因产生震荡而无法收敛。为了处理上述问题，本文提出了自适应AP聚类算法，即当数据量不断增加时，通过固定步长缩减p值搜寻最佳p值;在算法运行时，若发生震荡，则自动调整阻尼因子消除震荡，得到最佳lamda值;找出p和lamda最佳组合，最后利用此组合完成聚类即得到最佳聚类结果。

1 AP聚类算法

AP聚类算法是通过数据对象之间的“消息传递”完成聚类，主要是以数据点之间的相似度similarity（采用负欧氏距离作为标准）为基础，运用吸引度responsibility和归属度availability两种消息进行循环更新迭代，最终寻找出最优聚类结果。设有N个数据点构成的数据集X={x，x，…，x}，其中任意两个数据点之间的相似度为

其中，simi（i，k）主对角线上的值用偏向参数值p去替换，p越大，表明该点被选为代表点的概率就越大。所以，最终的聚类数目会随着p的改变而发生改变，一般在无先验知识的情况下将p设定为simi（i，k）的中值。定义R（i，k）为候选代表点k对每个数据点i的吸引程度，A（i，k）为数据点i支持k作为代表点的程度。Ri，k+A（i，k）越大，代表点k作为数据中心（exemplar）的可能性就越大。

AP算法的工作流程如下。

① 初始化吸引度[R（i，k）]和歸属度R（i，k）均为与相似矩阵simi（i，k）同构的零矩阵;

② 利用式⑵和式⑶更新R（i，k）。

其中，R（i，k）代表本次迭代的值，R（i，k）代表上一次迭代的值，lamda代表阻尼因子（其作用是当AP聚类算法发生震荡时，增大lamda可以消除震荡[1]）。

③ 利用式⑷和式⑸更新A（i，k）。

其中，A（i，k）代表本次迭代的值，A（i，k）代表上一次迭代的值，lamda作用与步骤

②相同。

④ 不断循环②到③直到算法收敛或达到最大迭代次数，停止更新且产生一系列高质量的聚类中心。

⑤ 根据产生的聚类中心序列，将其他各数据点按距离最近的准则分配给聚类中心所属的类，最终取得新的聚类结果。

2 自适应AP聚类算法

AP聚类算法中有偏向参数p和阻尼因子lamda两个重要参数，它们的取值最终影响了聚类结果的准确性和算法的收敛性。由文献[1]可知，相似矩阵simi（i，k）的主对角线上的值为p，即p出现在式⑹中，在迭代过程中，p越大，R（k，k）和A（i，k）都会变大。又R（k，k）+A（k，k）越大，则k点成为聚类中心（exemplar）的可能性就越大。因而，放大或缩小p的值能够增加或减少AP聚类算法的聚类数目。然而，在文献[1]中，p的取值为相似度矩阵[simi（i，k）]的中值，得到最终的聚类数目并不是最优聚类数目。除此之外，在AP聚类算法中的R（i，k）和A（i，k）的每一步迭代更新都利用了阻尼因子这一重要参数。阻尼因子lamda在迭代更新中起到改进算法收敛性的作用。当算法发生震荡不能收敛时，可以通过增大阻尼因子的值来消除震荡。但是，在原始AP算法聚类算法中，p和lamda都是取固定值，随着数据量的不断增加，这将导致原有的取值不再适用即不能得到最优的聚类数目。因此，当数据量不断增加时，如何自动调节p和lamda使算法能得到最优的聚类结果是目前需要解决的一个重要问题。

本文以寻找最优偏向参数p和阻尼因子lamda为目标，对AP聚类算法进行优化，得到新的聚类算法即自适应AP聚类算法。该算法的主要功能是，当数据量大时，利用改进后的算法可以通过以固定步长缩减P值得到最优偏向参数;当算法发生震荡时，能够自动调节阻尼因子消除震荡;最终达到提高聚类结果的准确性和算法的收敛速度。

基本思想：AP聚类算法输出的聚类数目主要取决于偏向参数p的大小，但是，对于不同量级的数据集，p取何值能产生最优数据结果却是未知的。改进的思路：①通过先验知识将p的值取为[-50]，通过不断循环迭代在算法收敛时得到聚类数目K;②将p值按步长10逐渐减小，得到一系列的K;③利用Silhouette（轮廓系数）[13]来估计哪一个K值是最优的聚类数目。

另外，AP聚类算法的快速性或收敛性主要由lamda来决定，当算法发生震荡时，可以通过增大lamda来消除震荡。但是，随着lamda的增加，吸引度的更新会变慢，算法需要更多的迭代次数才能达到lamda等于0.5时的更新效果。对此改进的思路：①R（i，k）和A（i，k）每进行一次更新，利用震荡度来检测算法是否发生震荡，其中震荡度OI等于本次迭代的聚类数目减去上一次迭代的聚类数目大于零的次数N除以算法开始稳定时已经迭代的次数T，即OI=N/T，OI越大，算法震荡越厉害，反之，震荡越小[11];②若发生震荡，以一定的步长增大lamda的值;③重复上述步骤直到达到约束条件，算法终止。

具体算法流程如下。

⑴ 初始化吸引度R（i，k）和归属度R（i，k）均为与相似矩阵simi（i，k）同构零矩阵。

⑵ 令p=-50，lamda=0.5，不断循环更新R（i，k）和A（i，k），直到达到约束条件得到聚类数目记为K。

⑶ 令p=p-10，不断循环更新R（i，k）和A（i，k），直到达到约束条件得到一系列聚类数目为K（根据经验l=10）。

⑷ 在⑵和⑶步骤中，若检测到算法发生震荡且无法收敛，则lamda（取值范围0.5～0.9）以0.1的步长来消除震荡，直到算法收敛。

⑸ 利用轮廓系数Silhouette（sil）指标对⑵和⑶步中的到的聚类质量和聚类数目进行评估，sil越大，表示聚类质量越好，对应的聚类数目K即最优聚类数目。

3 实验结果和分析

本节将AP算法和改进后的自适应AP聚类算法进行实验比较，把轮廓系数、迭代次数和聚类数目作为评价指标，验证自适应AP聚类算法的有效性。

3.1 实验数据说明

本实验的运行环境是Win7 32位操作系统，物理内存6GB，Python3.7（IDLE）;運行参数设置最大迭代次数为5000次。所有程序在同一台笔记本电脑上运行。以scikit-learn 的clustering中AP聚类算法Python源程序为基础，采用人造数据集和UCI公共数据集两类数据集来验证算法的有效性。人造数据集是选用sklearn包中提供的函数，以[1， 1]，[-1， -1]，[1， -1]三个点为中心随机生成150、300、500、700和1000个数据，即标准的聚类数目个数为3。

3.2 AP与自适应AP的比较

本实验是将AP算法和自适应AP算法的聚类性能进行实验比较，以检验自适应AP聚类算法能否正确找到最优偏向参数p和阻尼因子lamda组合。AP算法采用p=-50，lamda=0.5进行聚类，自适应AP聚类算法以p=-50，lamda=0.5作为初始值，完成第一次聚类，将得到的聚类数目记为K和轮廓系数sill，其中l=2，3，…，10。接下来每次改变p（根据实验p=p-10）的步长进行聚类，得到新的聚类数目记为K和轮廓系数sil。同时，在每次聚类中利用震荡度OI来检测是否发生震荡，若算法发生震荡且不收敛，则每次以lamda=lamda+0.1进行调整，直到算法收敛。表1为两种算法的聚类结果，分别用聚类数目，轮廓系数和迭代次数来衡量算法的准确性和收敛性。

根据表1中的数据可以看出，AP聚类算法的阻尼因子取0.5、偏向参数取-50，随着数据量的不断增加，聚类数目在不断增加（从3个增加到7个），聚类质量在不断下降（从0.740降到0.468），从而降低了算法的准确性，迭代次数不断增加（从65次增加到1740次），算法的收敛速度也大大降低了，由此可以说明，随着数据量的不断增加，偏向参数和阻尼因子均取固定值，算法很难得到好的聚类效果;相比AP聚类算法，自适应AP聚类算法通过不断的调整偏向参数和阻尼因子，随着数据量的不断增加，聚类数目k=3，聚类质量均得到提升，迭代次数与原算法相比大大降低了，由此可以得出：该算法的准确性和聚类效果均得到提高，运行速率也得到了提升。现在以数据data=500为例，所得结果如图1、图2所示。

图1是偏向参数、阻尼因子和轮廓系数三者之间的关系;图2是偏向参数、阻尼因子和迭代次数三者之间的关系通过图1和图2可以得到当p=-120，lamda=0.8时，最大轮廓系数sil=0.765

和最少迭代次数iteration=28。图3和图4是AP聚类算法和自适应AP聚类算法的可视化结果。图3是AP聚类算法p=-50，lamda=0.5时，得到聚类数目为4，轮廓系数为0.665，迭代次数为577。图4是自适应AP聚类算法，p=-120，lamda=0.8时，得到聚类数目为3，轮廓系数为0.765，迭代次数为28。通过图3和图4可知，当数据为500个数据点时，自适应AP聚类算法与AP聚类算法相比准确性提高了25%，聚类质量提高了15%，迭代次数从577次降到了28次，大大的提高了算法的运行速率。由此可以证明，与AP聚类算法相比，自适应AP聚类算法在准确性、聚类效果和快速性方面，都得到很大的改善和提高。

为了进一步说明自适应AP聚类算法的性能，本文使用聚类常用的UCI公共数据集中的（鸢尾花）Iris对两种算法进行比较。Iris数据集，共有150个数据，特征维数为4，共分为三大类;AP算法最终的聚类结果是聚类数目为3，轮廓系数为0.638，迭代次数为39，而自适应AP聚类算法最终的聚类结果是聚类数目为3，轮廓系数为0.646，迭代次数为26;通过对比，聚类质量提高了2%，迭代次数从39降到了26，即算法的收敛速度得到了提高。由此可以得出，自适应AP聚类算法比原算法在准确性，聚类效果和收敛性方面更有优势，对比实验结果如图5、图6所示。

4 结束语

本文提出了一种自适应AP聚类算法，主要是通过自适应调整原有AP聚类算法的偏向参数和阻尼因子来改善算法的准确性和快速性。本算法利用轮廓系数作为聚类有效性和聚类质量的评判指标，利用震荡度作为判断算法发生震荡后是否收敛的指标，自适应调整并获取最优偏向参数和阻尼因子组合，最终得到最优聚类结果。并且，通过人造数据集和UCI公共数据集进行实验对比，证明自适应AP聚类算法的有效性。

参考文献（References）：

[1] Frey B J， Dueck D.Clustering by passing messages betweendata points[J].Science，2007，315（5814）：972-976

[2] Frey B J， Dueck D.Response to comment on “clustering bypassing messages between data points”[J].Science，2008，319（5864）：726-727

[3] Marc Mézard.Where Are the Exemplars ？[J].Science，2007，315（5814）：949-951

[4] Leilei Sun， Chonghui Guo， Chuanren Liu， Hui Xiong.Fastaffinity propagation clustering based on incomplete similarity matrix[J].KNOWLEDGE AND INFORMATION SYSTEMS，2017，51（3）：941-963

[5] 张秀春.基于改进的AP聚类的图像分割算法[A]. 中国自动化学会控制理论专业委员会.第36届中国控制会议论文集（D）[C].中国自动化学会控制理论专业委员会：中国自动化学会控制理论专业委员会，2017：5

[6] 张耀楠，陈传慎，康雁.基于仿射传播聚类选择的多Atlas右心室精准分割[J].东北大学学报（自然科学版），2014，35（6）：795-799

[7] GUAN R， SHI X， MARCHESE M， et al.Text clustering withseeds affinity propagation[J].IEEE Transactions on Knowledge and Data Engineering， 2011，23（4）：627-637

[8] 王开军，李健，张军英，等.半监督的仿射传播聚类[J].计算机工程，2007，33（23）：197-198

[9] 王开军，张军英，李丹，等.自适应仿射传播聚类[J].自动化学报，2007，33（12）：1242-1246

[10] 肖宇，于剑.基于近邻传播算法的半监督聚类[J].软件学报，2008，19（11）：2803-2813

[11] 刘晓勇，付辉.一种快速聚类算法[J].山东大学学报工学版，2011，41（4）：20-23

[12] 胡久松，刘宏立，颜志，等.一种自适应阻尼因子的仿射传播聚类算法[J].西北大学学报自然科学版，2018，48（3）：3-368

[13] 王开军，李健，张军英，过立新.聚类分析中类数估计方法的实验比较[J].计算机工程，2008，34（9）：198-199，202