自適應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