自適應(yīng)AP聚類算法研究

賴健瓊

摘? 要： 偏向參數(shù)和阻尼因子是影響AP聚類算法聚類效果的兩個(gè)重要參數(shù)，但他們均取固定值。隨著數(shù)據(jù)量的改變，原有參數(shù)取值不能使算法聚類結(jié)果達(dá)到最優(yōu)。鑒此，本文提出自適應(yīng)AP聚類算法，當(dāng)數(shù)據(jù)量發(fā)生改變時(shí)，自動(dòng)調(diào)整并獲取最優(yōu)的偏向參數(shù)和阻尼因子，最終得到最優(yōu)聚類結(jié)果。與原來(lái)算法相比，改進(jìn)后的算法能自動(dòng)消除震蕩，還可獲取最優(yōu)聚類結(jié)果，提高聚類結(jié)果的準(zhǔn)確性和算法快速性。通過(guò)人造數(shù)據(jù)集和Iris數(shù)據(jù)集實(shí)驗(yàn)，證明了自適應(yīng)AP聚類算法的有效性。

關(guān)鍵詞： AP聚類; 自適應(yīng)AP聚類; 偏向參數(shù); 阻尼因子

中圖分類號(hào)：TP18? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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上提出的一種基于代表點(diǎn)的新的聚類算法。該算法開始時(shí)是將N個(gè)數(shù)據(jù)點(diǎn)都作為代表點(diǎn)（或稱作數(shù)據(jù)中心），利用N個(gè)數(shù)據(jù)點(diǎn)之間的相似度構(gòu)造[N×N]相似度矩陣作為“消息傳遞”基礎(chǔ)，通過(guò)迭代求精尋找最優(yōu)代表點(diǎn)列表，將各數(shù)據(jù)點(diǎn)分配給最近代表點(diǎn)所屬的類，最終得到新的聚類結(jié)果。然而經(jīng)典的K-means聚類算法，聚類數(shù)目需要用戶自己設(shè)定，對(duì)初始聚類中心敏感，易產(chǎn)生局部最優(yōu)解，這些不足導(dǎo)致每次聚類結(jié)果幾乎總是不同。和經(jīng)典聚類算法K-means聚類相比，AP聚類算法不單避免了這些缺陷，而且有簡(jiǎn)單、高效和快速等優(yōu)點(diǎn)。例如，將75000個(gè)DNA片段分組為2000組，通常需要花上數(shù)百小時(shí)的計(jì)算時(shí)間完成的任務(wù)可能在幾分鐘之內(nèi)就可以完成[3]。

AP聚類算法自提出以來(lái)就得到相關(guān)專業(yè)人士的青睞，在很多領(lǐng)域得到廣泛的應(yīng)用。如商務(wù)智能[4]、圖像分割[5]、生物醫(yī)學(xué)[6]和文本數(shù)據(jù)挖掘[7]等方面。AP聚類算法中有兩個(gè)重要參數(shù)：置于相似度矩陣similarity對(duì)角線上的偏向參數(shù)p和responsibility（吸引度）、availability（歸屬度）在迭代更新中防止發(fā)生震蕩的阻尼因子lamda。如何選擇合適偏向參數(shù)產(chǎn)生最優(yōu)聚類結(jié)果，以及當(dāng)算法發(fā)生震蕩后如何消除震蕩并收斂是AP聚類算法尚未解決的問題。針對(duì)這個(gè)問題，王開軍[8-9]，肖宇[10]，劉曉勇[11]，胡久松[12]等人對(duì)該算法進(jìn)行改進(jìn)。

原始AP聚類算法偏向參數(shù)p和阻尼因子lamda的選擇影響聚類算法的準(zhǔn)確性和收斂速度。由于原有的法中p（根據(jù)先驗(yàn)知識(shí)選取或取相似度矩陣similarity的中值）和lamda（一般取0.5～0.9）均取固定值，隨著數(shù)據(jù)量的增大，不僅會(huì)使最終的聚類結(jié)果的準(zhǔn)確度降低，還很有可能導(dǎo)致算法因產(chǎn)生震蕩而無(wú)法收斂。為了處理上述問題，本文提出了自適應(yīng)AP聚類算法，即當(dāng)數(shù)據(jù)量不斷增加時(shí)，通過(guò)固定步長(zhǎng)縮減p值搜尋最佳p值;在算法運(yùn)行時(shí)，若發(fā)生震蕩，則自動(dòng)調(diào)整阻尼因子消除震蕩，得到最佳lamda值;找出p和lamda最佳組合，最后利用此組合完成聚類即得到最佳聚類結(jié)果。

1 AP聚類算法

AP聚類算法是通過(guò)數(shù)據(jù)對(duì)象之間的“消息傳遞”完成聚類，主要是以數(shù)據(jù)點(diǎn)之間的相似度similarity（采用負(fù)歐氏距離作為標(biāo)準(zhǔn)）為基礎(chǔ)，運(yùn)用吸引度responsibility和歸屬度availability兩種消息進(jìn)行循環(huán)更新迭代，最終尋找出最優(yōu)聚類結(jié)果。設(shè)有N個(gè)數(shù)據(jù)點(diǎn)構(gòu)成的數(shù)據(jù)集X={x，x，…，x}，其中任意兩個(gè)數(shù)據(jù)點(diǎn)之間的相似度為

其中，simi（i，k）主對(duì)角線上的值用偏向參數(shù)值p去替換，p越大，表明該點(diǎn)被選為代表點(diǎn)的概率就越大。所以，最終的聚類數(shù)目會(huì)隨著p的改變而發(fā)生改變，一般在無(wú)先驗(yàn)知識(shí)的情況下將p設(shè)定為simi（i，k）的中值。定義R（i，k）為候選代表點(diǎn)k對(duì)每個(gè)數(shù)據(jù)點(diǎn)i的吸引程度，A（i，k）為數(shù)據(jù)點(diǎn)i支持k作為代表點(diǎn)的程度。Ri，k+A（i，k）越大，代表點(diǎn)k作為數(shù)據(jù)中心（exemplar）的可能性就越大。

AP算法的工作流程如下。

① 初始化吸引度[R（i，k）]和歸屬度R（i，k）均為與相似矩陣simi（i，k）同構(gòu)的零矩陣;

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

其中，R（i，k）代表本次迭代的值，R（i，k）代表上一次迭代的值，lamda代表阻尼因子（其作用是當(dāng)AP聚類算法發(fā)生震蕩時(shí)，增大lamda可以消除震蕩[1]）。

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

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

②相同。

④ 不斷循環(huán)②到③直到算法收斂或達(dá)到最大迭代次數(shù)，停止更新且產(chǎn)生一系列高質(zhì)量的聚類中心。

⑤ 根據(jù)產(chǎn)生的聚類中心序列，將其他各數(shù)據(jù)點(diǎn)按距離最近的準(zhǔn)則分配給聚類中心所屬的類，最終取得新的聚類結(jié)果。

2 自適應(yīng)AP聚類算法

AP聚類算法中有偏向參數(shù)p和阻尼因子lamda兩個(gè)重要參數(shù)，它們的取值最終影響了聚類結(jié)果的準(zhǔn)確性和算法的收斂性。由文獻(xiàn)[1]可知，相似矩陣simi（i，k）的主對(duì)角線上的值為p，即p出現(xiàn)在式⑹中，在迭代過(guò)程中，p越大，R（k，k）和A（i，k）都會(huì)變大。又R（k，k）+A（k，k）越大，則k點(diǎn)成為聚類中心（exemplar）的可能性就越大。因而，放大或縮小p的值能夠增加或減少AP聚類算法的聚類數(shù)目。然而，在文獻(xiàn)[1]中，p的取值為相似度矩陣[simi（i，k）]的中值，得到最終的聚類數(shù)目并不是最優(yōu)聚類數(shù)目。除此之外，在AP聚類算法中的R（i，k）和A（i，k）的每一步迭代更新都利用了阻尼因子這一重要參數(shù)。阻尼因子lamda在迭代更新中起到改進(jìn)算法收斂性的作用。當(dāng)算法發(fā)生震蕩不能收斂時(shí)，可以通過(guò)增大阻尼因子的值來(lái)消除震蕩。但是，在原始AP算法聚類算法中，p和lamda都是取固定值，隨著數(shù)據(jù)量的不斷增加，這將導(dǎo)致原有的取值不再適用即不能得到最優(yōu)的聚類數(shù)目。因此，當(dāng)數(shù)據(jù)量不斷增加時(shí)，如何自動(dòng)調(diào)節(jié)p和lamda使算法能得到最優(yōu)的聚類結(jié)果是目前需要解決的一個(gè)重要問題。

本文以尋找最優(yōu)偏向參數(shù)p和阻尼因子lamda為目標(biāo)，對(duì)AP聚類算法進(jìn)行優(yōu)化，得到新的聚類算法即自適應(yīng)AP聚類算法。該算法的主要功能是，當(dāng)數(shù)據(jù)量大時(shí)，利用改進(jìn)后的算法可以通過(guò)以固定步長(zhǎng)縮減P值得到最優(yōu)偏向參數(shù);當(dāng)算法發(fā)生震蕩時(shí)，能夠自動(dòng)調(diào)節(jié)阻尼因子消除震蕩;最終達(dá)到提高聚類結(jié)果的準(zhǔn)確性和算法的收斂速度。

基本思想：AP聚類算法輸出的聚類數(shù)目主要取決于偏向參數(shù)p的大小，但是，對(duì)于不同量級(jí)的數(shù)據(jù)集，p取何值能產(chǎn)生最優(yōu)數(shù)據(jù)結(jié)果卻是未知的。改進(jìn)的思路：①通過(guò)先驗(yàn)知識(shí)將p的值取為[-50]，通過(guò)不斷循環(huán)迭代在算法收斂時(shí)得到聚類數(shù)目K;②將p值按步長(zhǎng)10逐漸減小，得到一系列的K;③利用Silhouette（輪廓系數(shù)）[13]來(lái)估計(jì)哪一個(gè)K值是最優(yōu)的聚類數(shù)目。

另外，AP聚類算法的快速性或收斂性主要由lamda來(lái)決定，當(dāng)算法發(fā)生震蕩時(shí)，可以通過(guò)增大lamda來(lái)消除震蕩。但是，隨著lamda的增加，吸引度的更新會(huì)變慢，算法需要更多的迭代次數(shù)才能達(dá)到lamda等于0.5時(shí)的更新效果。對(duì)此改進(jìn)的思路：①R（i，k）和A（i，k）每進(jìn)行一次更新，利用震蕩度來(lái)檢測(cè)算法是否發(fā)生震蕩，其中震蕩度OI等于本次迭代的聚類數(shù)目減去上一次迭代的聚類數(shù)目大于零的次數(shù)N除以算法開始穩(wěn)定時(shí)已經(jīng)迭代的次數(shù)T，即OI=N/T，OI越大，算法震蕩越厲害，反之，震蕩越小[11];②若發(fā)生震蕩，以一定的步長(zhǎng)增大lamda的值;③重復(fù)上述步驟直到達(dá)到約束條件，算法終止。

具體算法流程如下。

⑴ 初始化吸引度R（i，k）和歸屬度R（i，k）均為與相似矩陣simi（i，k）同構(gòu)零矩陣。

⑵ 令p=-50，lamda=0.5，不斷循環(huán)更新R（i，k）和A（i，k），直到達(dá)到約束條件得到聚類數(shù)目記為K。

⑶ 令p=p-10，不斷循環(huán)更新R（i，k）和A（i，k），直到達(dá)到約束條件得到一系列聚類數(shù)目為K（根據(jù)經(jīng)驗(yàn)l=10）。

⑷ 在⑵和⑶步驟中，若檢測(cè)到算法發(fā)生震蕩且無(wú)法收斂，則lamda（取值范圍0.5～0.9）以0.1的步長(zhǎng)來(lái)消除震蕩，直到算法收斂。

⑸ 利用輪廓系數(shù)Silhouette（sil）指標(biāo)對(duì)⑵和⑶步中的到的聚類質(zhì)量和聚類數(shù)目進(jìn)行評(píng)估，sil越大，表示聚類質(zhì)量越好，對(duì)應(yīng)的聚類數(shù)目K即最優(yōu)聚類數(shù)目。

3 實(shí)驗(yàn)結(jié)果和分析

本節(jié)將AP算法和改進(jìn)后的自適應(yīng)AP聚類算法進(jìn)行實(shí)驗(yàn)比較，把輪廓系數(shù)、迭代次數(shù)和聚類數(shù)目作為評(píng)價(jià)指標(biāo)，驗(yàn)證自適應(yīng)AP聚類算法的有效性。

3.1 實(shí)驗(yàn)數(shù)據(jù)說(shuō)明

本實(shí)驗(yàn)的運(yùn)行環(huán)境是Win7 32位操作系統(tǒng)，物理內(nèi)存6GB，Python3.7（IDLE）;運(yùn)行參數(shù)設(shè)置最大迭代次數(shù)為5000次。所有程序在同一臺(tái)筆記本電腦上運(yùn)行。以scikit-learn 的clustering中AP聚類算法Python源程序?yàn)榛A(chǔ)，采用人造數(shù)據(jù)集和UCI公共數(shù)據(jù)集兩類數(shù)據(jù)集來(lái)驗(yàn)證算法的有效性。人造數(shù)據(jù)集是選用sklearn包中提供的函數(shù)，以[1， 1]，[-1， -1]，[1， -1]三個(gè)點(diǎn)為中心隨機(jī)生成150、300、500、700和1000個(gè)數(shù)據(jù)，即標(biāo)準(zhǔn)的聚類數(shù)目個(gè)數(shù)為3。

3.2 AP與自適應(yīng)AP的比較

本實(shí)驗(yàn)是將AP算法和自適應(yīng)AP算法的聚類性能進(jìn)行實(shí)驗(yàn)比較，以檢驗(yàn)自適應(yīng)AP聚類算法能否正確找到最優(yōu)偏向參數(shù)p和阻尼因子lamda組合。AP算法采用p=-50，lamda=0.5進(jìn)行聚類，自適應(yīng)AP聚類算法以p=-50，lamda=0.5作為初始值，完成第一次聚類，將得到的聚類數(shù)目記為K和輪廓系數(shù)sill，其中l(wèi)=2，3，…，10。接下來(lái)每次改變p（根據(jù)實(shí)驗(yàn)p=p-10）的步長(zhǎng)進(jìn)行聚類，得到新的聚類數(shù)目記為K和輪廓系數(shù)sil。同時(shí)，在每次聚類中利用震蕩度OI來(lái)檢測(cè)是否發(fā)生震蕩，若算法發(fā)生震蕩且不收斂，則每次以lamda=lamda+0.1進(jìn)行調(diào)整，直到算法收斂。表1為兩種算法的聚類結(jié)果，分別用聚類數(shù)目，輪廓系數(shù)和迭代次數(shù)來(lái)衡量算法的準(zhǔn)確性和收斂性。

根據(jù)表1中的數(shù)據(jù)可以看出，AP聚類算法的阻尼因子取0.5、偏向參數(shù)取-50，隨著數(shù)據(jù)量的不斷增加，聚類數(shù)目在不斷增加（從3個(gè)增加到7個(gè)），聚類質(zhì)量在不斷下降（從0.740降到0.468），從而降低了算法的準(zhǔn)確性，迭代次數(shù)不斷增加（從65次增加到1740次），算法的收斂速度也大大降低了，由此可以說(shuō)明，隨著數(shù)據(jù)量的不斷增加，偏向參數(shù)和阻尼因子均取固定值，算法很難得到好的聚類效果;相比AP聚類算法，自適應(yīng)AP聚類算法通過(guò)不斷的調(diào)整偏向參數(shù)和阻尼因子，隨著數(shù)據(jù)量的不斷增加，聚類數(shù)目k=3，聚類質(zhì)量均得到提升，迭代次數(shù)與原算法相比大大降低了，由此可以得出：該算法的準(zhǔn)確性和聚類效果均得到提高，運(yùn)行速率也得到了提升?，F(xiàn)在以數(shù)據(jù)data=500為例，所得結(jié)果如圖1、圖2所示。

圖1是偏向參數(shù)、阻尼因子和輪廓系數(shù)三者之間的關(guān)系;圖2是偏向參數(shù)、阻尼因子和迭代次數(shù)三者之間的關(guān)系通過(guò)圖1和圖2可以得到當(dāng)p=-120，lamda=0.8時(shí)，最大輪廓系數(shù)sil=0.765

和最少迭代次數(shù)iteration=28。圖3和圖4是AP聚類算法和自適應(yīng)AP聚類算法的可視化結(jié)果。圖3是AP聚類算法p=-50，lamda=0.5時(shí)，得到聚類數(shù)目為4，輪廓系數(shù)為0.665，迭代次數(shù)為577。圖4是自適應(yīng)AP聚類算法，p=-120，lamda=0.8時(shí)，得到聚類數(shù)目為3，輪廓系數(shù)為0.765，迭代次數(shù)為28。通過(guò)圖3和圖4可知，當(dāng)數(shù)據(jù)為500個(gè)數(shù)據(jù)點(diǎn)時(shí)，自適應(yīng)AP聚類算法與AP聚類算法相比準(zhǔn)確性提高了25%，聚類質(zhì)量提高了15%，迭代次數(shù)從577次降到了28次，大大的提高了算法的運(yùn)行速率。由此可以證明，與AP聚類算法相比，自適應(yīng)AP聚類算法在準(zhǔn)確性、聚類效果和快速性方面，都得到很大的改善和提高。

為了進(jìn)一步說(shuō)明自適應(yīng)AP聚類算法的性能，本文使用聚類常用的UCI公共數(shù)據(jù)集中的（鳶尾花）Iris對(duì)兩種算法進(jìn)行比較。Iris數(shù)據(jù)集，共有150個(gè)數(shù)據(jù)，特征維數(shù)為4，共分為三大類;AP算法最終的聚類結(jié)果是聚類數(shù)目為3，輪廓系數(shù)為0.638，迭代次數(shù)為39，而自適應(yīng)AP聚類算法最終的聚類結(jié)果是聚類數(shù)目為3，輪廓系數(shù)為0.646，迭代次數(shù)為26;通過(guò)對(duì)比，聚類質(zhì)量提高了2%，迭代次數(shù)從39降到了26，即算法的收斂速度得到了提高。由此可以得出，自適應(yīng)AP聚類算法比原算法在準(zhǔn)確性，聚類效果和收斂性方面更有優(yōu)勢(shì)，對(duì)比實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

4 結(jié)束語(yǔ)

本文提出了一種自適應(yīng)AP聚類算法，主要是通過(guò)自適應(yīng)調(diào)整原有AP聚類算法的偏向參數(shù)和阻尼因子來(lái)改善算法的準(zhǔn)確性和快速性。本算法利用輪廓系數(shù)作為聚類有效性和聚類質(zhì)量的評(píng)判指標(biāo)，利用震蕩度作為判斷算法發(fā)生震蕩后是否收斂的指標(biāo)，自適應(yīng)調(diào)整并獲取最優(yōu)偏向參數(shù)和阻尼因子組合，最終得到最優(yōu)聚類結(jié)果。并且，通過(guò)人造數(shù)據(jù)集和UCI公共數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，證明自適應(yīng)AP聚類算法的有效性。

參考文獻(xiàn)（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] 張秀春.基于改進(jìn)的AP聚類的圖像分割算法[A]. 中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì).第36屆中國(guó)控制會(huì)議論文集（D）[C].中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)：中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)，2017：5

[6] 張耀楠，陳傳慎，康雁.基于仿射傳播聚類選擇的多Atlas右心室精準(zhǔn)分割[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 王開軍，李健，張軍英，等.半監(jiān)督的仿射傳播聚類[J].計(jì)算機(jī)工程，2007，33（23）：197-198

[9] 王開軍，張軍英，李丹，等.自適應(yīng)仿射傳播聚類[J].自動(dòng)化學(xué)報(bào)，2007，33（12）：1242-1246

[10] 肖宇，于劍.基于近鄰傳播算法的半監(jiān)督聚類[J].軟件學(xué)報(bào)，2008，19（11）：2803-2813

[11] 劉曉勇，付輝.一種快速聚類算法[J].山東大學(xué)學(xué)報(bào)工學(xué)版，2011，41（4）：20-23

[12] 胡久松，劉宏立，顏志，等.一種自適應(yīng)阻尼因子的仿射傳播聚類算法[J].西北大學(xué)學(xué)報(bào)自然科學(xué)版，2018，48（3）：3-368

[13] 王開軍，李健，張軍英，過(guò)立新.聚類分析中類數(shù)估計(jì)方法的實(shí)驗(yàn)比較[J].計(jì)算機(jī)工程，2008，34（9）：198-199，202