多維空間可調整的近鄰傳播聚類算法*

錢雪忠，王衛濤

江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

聚類分析是對一組對象進行處理，最終將對象分成幾類，使得同一類對象之間的相似度更大，不同類對象的相似度更小。在聚類分析的發展過程中，提出了k-means、DBSCAN、FCM等聚類算法，2007年Frey和Dueck在Science闡述了近鄰傳播聚類算法（affinity propagation，AP）的原理和應用。與其他聚類方法相比，近鄰傳播算法不需事先設定聚類的個數，不需初始化聚類中心點，是一種快速有效的聚類算法。由于AP算法是基于中心的聚類算法，因此在處理緊湊的具有超球形分布的數據集上有較好的性能，但是不適合具有任意空間形狀和多重尺度的數據集。

針對上述問題，Dong等[1]提出了可變相似性度量的近鄰傳播聚類（affinity propagation of variable similarity measure，AP-VSM），該方法采用可變度量來改善數據的總體分布特性，該方法在處理一些復雜的高維數據時有較好的效果，然而該方法在處理不同類之間有相互交叉的情況時效果較差；Jia等[2]提出了基于光譜尺寸減小的密度自適應近鄰傳播聚類（density-adaptive affinity propagation clustering algorithm based on spectral dimension reduction，DAAP），該方法采用最短路徑構建相似度矩陣，利用該方法能夠較好地處理多尺度數據集的問題，但是該算法在計算最短路徑時算法時間復雜度過大；Gan等[3]提出了子空間近鄰傳播聚類（subspace clustering using affinity propagation，SAP），該算法利用屬性權重計算相似度矩陣，并在迭代過程中動態更新屬性的權重，從而更新相似度矩陣，利用該方法可以較好地處理復雜空間的數據，但是在處理樣本量較大時稍顯不足；Li等[4]提出了自適應調整偏向參數的近鄰傳播聚類算法（adjustable preference affinity propagation clustering，APAP），該方法為不同的數據點設置不同的偏向參數，并動態更新，該方法適合高斯分布以及流行分布的數據，但不適合處理圖像相關的數據集。

本文針對文獻[1-4]中處理數據集中不同類數據有交叉的問題，算法時間復雜度過大的問題，不適合處理多樣本的問題以及不適合處理圖像相關的數據等問題提出了MSAAP（multidimensional similarity adaptive affinity propagation）算法。首先，針對文獻[5-8]的想法，本文根據熵值法計算數據集的屬性權重，然后根據屬性權重和高斯核函數構造出一種更加準確的計算相似度矩陣的方法；接著針對文獻[9-13]的想法，本文根據權重矩陣選取優先級高的屬性，跟該屬性的個數n，將空間分成2的n次方個子空間，最后針對文獻[14-20]，本文提出計算分布各個子空間的鄰域數據點的吸引度和歸屬度之和，進而調整該樣本點的空間分布。然后調整后的樣本點去重新迭代計算相似度、吸引度和歸屬度，一直到迭代結束。本文在第3章詳細介紹該算法的計算過程。

2 近鄰傳播算法

AP算法把所有的樣本點作為候選聚類中心點。AP算法主要利用數據集中任意兩個樣本點之間的相似度進行迭代計算。其中相似度的定義為兩個樣本點之間歐式距離平方的負數，計算相似度矩陣的公式如下：

在AP算法中需要設置偏向參數的值，默認設置為相似度矩陣的均值，即p=median(s)。該算法在計算過程中引入了歸屬度矩陣A(availability)和吸引度矩陣R(responsibility)，在算法迭代過程中兩個信息矩陣不斷地迭代更新。其中：A=(a(i,j))m×n,a(i,j)是樣本點j向樣本點i發送的信息值，表示為樣本點i選擇樣本點j作為聚類中心點的合適程度；R=(r(i,j))m×n,r(i,j)是樣本點i向樣本點j發送的信息值，表示為樣本點j作為樣本點i聚類中心點的合適程度。歸屬度矩陣和吸引度矩陣的迭代更新的計算公式如下：

在計算歸屬度矩陣相似度矩陣過程中，為了防止震蕩，引入了阻尼因子λ來增強算法的穩定性，計算公式如下：

根據以上公式迭代計算歸屬度矩陣和吸引度矩陣，最終使得聚類目標函數最大化，其聚類目標函數如下：

式中，ci為樣本點i的聚類中心點，C是由ci組成的向量，i=1,2,…,N（N為樣本點個數），S(C)為所有樣本點到各自的聚類中心點的相似度之和。其中δk(C)計算公式如下：

此式為一致性約束懲罰項，如果有樣本點i選擇k作為其聚類中心點，即ci=k，那么樣本點k必定選擇自身為聚類中心點，即ck=k，否則函數取值-∞，使樣本點i在下次迭代中不再選擇k作為自身聚類中心點。

迭代后通過計算A+R的值來確定聚類中心點，當(r(k,k)+a(k,k))＞0時，樣本點k即為聚類中心點。各個樣本點的聚類中心點ci的計算公式如下：該式表示為每個樣本點選擇歸屬度和吸引度之和最大的聚類中心點作為自身的聚類中心點。

3 MSAAP算法

3.1 算法描述

3.1.1 熵值法計算屬性權重

熵值是具有不確定性的一種度量。信息量越大，不確定性就越小，熵也就越小；信息量越小，不確定性越大，熵也越大。因此根據熵的特性，可以利用熵值來判斷某個指標的離散程度，指標的離散程度越大，該指標對綜合評價的影響（權重）越大，其熵值越小。同時熵在信息論中已經得到廣泛的應用，因此本文通過計算數據樣本點的熵值來確定各個屬性的權重，可以更能真實表達數據集的特性。

計算熵值的過程需要依次計算歸一化指標、指標比重、指標熵值、信息熵冗余度、指標權值。其公式如下：

式中，xij為數據集中第i個數據點的第j項指標，i=1,2,…,n（n為樣本點個數），j=1,2,…,d（d為樣本點屬性個數）；k=1/ln(n)＞0，滿足ej≥ 0。ej表示第j項指標的熵值，rj表示信息熵冗余度，wj則表示為最終的指標權重。

圖1中的橫軸為數據集的維數，縱軸為每一維特征的權重，從圖中可以看出，通過計算樣本點各個屬性的熵值可以很好地區分出屬性的重要程度，然后根據實際實驗的需要，選取若干個權重屬性。圖中用到的數據集的具體屬性在第4章中介紹。

3.1.2 根據權重計算相似度矩陣

Fig.1 Attributes weighted graphs calculated by entropy method圖1 通過熵值法計算的屬性權重圖

其中，r為核變換系數。

為了充分驗證本文所采用的相似度計量方法的有效性，需要通過數據集的相似性度量來對比，本文通過任意選取兩個同類的數據點和一個不同類的數據點，分別計算出這兩組的相似度s1和s2，然后計算出一個比值rate=(s1-s2)/s2，這樣做的目的在于保證在做不同相似度對比實驗時，都在同一個數量級內，使得實驗結果具有更好的可靠性。對比結果見圖2、圖3。

Fig.2 Comparison chart of wine data set圖2 wine數據集對比圖

Fig.3 Comparison chart of YaleB data set圖3 YaleB數據集對比圖

圖中es_rate為歐式距離平方的負數計算的相似度比值，ds_rate為密度自適應計算的相似度比值，ws_rate為本文采用的加權密度自適應比值。從結果看出，ws_rate的比值是最大的，說明了此方法在計算同類數據點的相似度比es_rate和ds_rate更大，在計算不同類數據點之間時，ws_rate相比另外兩種則更小，說明ws_rate計算相似度更準確。為保證實驗的公正性，同類數據點和不同類數據點都是隨機選取的，并做10次對比實驗。

3.1.3 根據多維空間調整個體空間分布

AP算法每次迭代后，會有吸引度和歸屬度矩陣生成，吸引度和歸屬度矩陣的加和表示了兩兩數據點之間的相似程度，因此將吸引度和歸屬度加和的指標作為衡量指標，來調整個體的空間分布。

首先需要前期處理工作，為了避免正負數的相互抵消，首先采用sigmoid函數將AR矩陣映射到[0,1]區間內，AR為歸屬度矩陣A和吸引度矩陣R之和。然后根據3.1.1節計算出的權重矩陣W，選出前l個屬性，屬性集合為ls。

然后將根據樣本點的距離求出閾值Eps，本文中Eps是通過距離矩陣的平均數（Median(D)）計算得出的。因為距離矩陣的平均數反映的是整個數據集樣本點之間距離的平均情況，利用該平均數可以過濾一些邊緣點、噪聲點的干擾。當兩個樣本之間的距離小于該閾值時表明這兩個樣本相對整個數據集來說更有可能屬于同一類簇，反之，則說明該兩個樣本屬于同一類簇的可能性較低，接著根據閾值Eps計算每個樣本點的鄰域areas，通過areas中的樣本點去調整當前樣本的區域分布，如果D(i,k)≤Eps，則areas(t)=k,t=t+1。如果areas為空，則處理下一個數據點；如果不為空，則根據l值計算出需要劃分的子空間數目nums=2l。接著初始化2l個空間的初始狀態，初始化的計算公式如下：

其中，1表示正相關，-1表示負相關，j∈ls時的計算步驟如下：

1.首先初始化變量：nums=2l

2.forcol=1∶l

3.index=cols(col)，step=2(l-col),frep=0,flag=1

4.fort=1∶nums

5.frep=frep+1

6.iffrep≤step status(t,index)=flagend if

7.iffrep==step

8.frep=0

9.ifflag==1flag=-1elseflag=1end if

10.end if

11.end for

12.end for

圖4中，左側圖為調整前的樣本點分布，右側為調整后的樣本點分布，其中左側圖中處于坐標軸的中心黑點為當前調整的樣本點。圖4是從模型的角度來分析整體數據點調整的基本規律，為了更好地展示，采用二維空間來表示，因此劃分的總的子空間數目為22，其中A、B、C、D分別代表四個空間，每個空間內包含若干當前數據點的鄰域點，然后分別計算：

Fig.4 Chart of spatial adjustment圖4 空間調整分布示意圖

接著計算max{sumA,sumB,sumC,sumD}，求出吸引度和歸屬度之和最大的區域，并計算出該區域中所有數據點的中心點center，然后用center代替當前處理的數據點x，最后繼續迭代計算下一個數據點。當計算完所有數據點之后，更新數據集的相似度矩陣s、偏向參數p，然后進行下次迭代。

在實驗中，為了縮短運行時間，同時保證迭代過程更加穩定，在迭代過程中增加更新頻率freq，如果滿足 mod(iter,freq)=0，則update(data,s,p)；反之，則 continue，繼續下次迭代。在本文中freq是通過sigmoid函數計算出的，sigmoid函數是一個從大到小變化的平滑函數，在AP算法迭代的初始階段，幅度較大，既保證了迭代的速率又保證對數據集一個整體的調整變換。隨著算法迭代的深入，幅度縮小，保證了對個別數據點的調整，同時也避免了算法為了適應不同數據集而去不斷調整頻率的大小，這樣保證了算法的效率性和魯棒性。表1和表2是頻率選取固定值和sigmoid函數計算的對比實驗。當固定值為1時，為每次迭代都更新。以此來驗證采用sigmoid函數在此處的有效性。

Table 1 Parameter selection table of wine表1 wine數據集的參數選取表

Table 2 Parameter selection table of leuk72_3k表2 leuk72_3k數據集的參數選取表

表1和表2中固定值對應的數據為freq取一定值時所對應的準確率和時間，sigmoid對應的數據為本文利用sigmoid函數計算頻率對應的準確率和時間。從表中可以看出頻率的選取與準確率沒有比例關系，對于任意的數據集可能是任意的固定值，因此在實際的仿真實驗有一定的難度，同時當頻率取某個固定值時準確率高了，那么時間就會很慢，時間快了，準確率就會下降。而利用sigmoid函數計算頻率就會在保證準確率的同時，降低時間復雜度。此處提到的準確率會在本文4.1節介紹。

3.2 算法步驟

Input：X={x1,x2,…,xn}.

Output：idx：Clustering results.

1.w=entropy(X)//由3.1.1節計算

3.pm=Median(Sn×n)

4.iter←0

5.A′=AP.update(A),R′=AP.update(R)

6.frep=floor(a?ln(iter)/ln(b)+c)

7.if mod(iter,frep)==0

8.AR=sigmoid(A+R)

9.ls=sort(w,-1)(1∶l)

10.fori=1∶n

12.Eps=Median(dis)t=0

13.fork=1∶n-1

14.ifdis(i,k)≤Eps t=t+1areas(t)=kend if

15.end for

16.iflength(areas)＞0

17.status=init(l,cols)//由表1計算

18.fork=1∶length(areas)

19.forj=1∶l

20.ifx(i,j)＞x(k,j)status′=-1end if

21.ifx(I,j)≤x(k,j)status′=1end if

22.end for

23.index=find(status′,status) set(index,t)=kt=t+1

24.end for

25.fort=1∶nums

26.sumARs=sum(AR(set(t)))

27.end for

28.x(i)=avg(max(sumARs))

29.end if

30.end for

31.Algorithm terminated.

4 實驗結果與分析

不同指標往往具有不同的量綱和單位，這樣會影響數據分析的結果，為了消除指標之間的量綱的影響，本文對數據集進行了歸一化處理。本文選取了13個UCI數據集和ORL、YaleB、JAFFE人臉數據庫。數據集信息見表3。

4.1 評價指標

為了更加客觀地反映聚類算法的優劣，本文選取F-Measure作為算法的評價指標，F-measure是由precision（精確率）和recall（召回率）共同表示，準確率（F-measure）通常用來表示聚類準確性的優劣。計算公式如下：

Table 3 Information of data set表3 數據集信息

4.2 參數調整分析

由于在實驗過程中，引入了鄰域的閾值和特征維度兩個參數，當參數不同時，實驗結果也不同。因此需要在大量的實驗中，找出適合不同數據集的參數，表4、表5為本文做的參數選取實驗。

表4、表5中，eps表示閾值，dim表示維度。從表4、表5可以看出，參數閾值和維度對聚類結果影響很大，因為在實驗中，閾值是控制樣本點的鄰域個數，能影響散落在各個空間中鄰域點的數目，最終會影響樣本點的分布的調整，所以閾值對聚類結果影響較大。而維度是m個權重最大的屬性，當m取不同值時，選取的屬性個數就不同，而在調整樣本點分布時，所改變的樣本點的屬性不同，因此最終對聚類結果影響較大。

Table 4 Parameter selection table of wine表4 wine數據集的參數選取表

Table 5 Parameter selection table of zoo表5 zoo數據集的參數選取表

4.3 準確率、時間、類數分析

本文從準確率、時間、聚類類數3個維度對AP、AP-VSM、DAAP、SAP、APAP、MSAAP進行了對比。其中，F為準確率（F-measure），Time單位為秒（s）。對比如表6所示。

從準確率來看，MSAAP算法在這16個數據集上，相比其他5種算法有了明顯的提升。AP-VSM、DAAP、SAP、APAP這4種算法都有各自適合的數據集。DAAP在Sonar、YaleB等數據集上處理效果較其他方法差；SAP在leuk72_3k、haberman、ORL等數據集上處理效果較差；APAP在JAFFE數據集上處理效果較差。而本文提出的MSAAP處理這16個數據集相比其他算法都有較好的改進。

從時間方面看，DAAP算法由于需要計算最短路徑，時間復雜度最大，其次本文提出的MSAAP算法需要在迭代中調整樣本點的空間分布，因此時間復雜度稍大，MSAAP的時間復雜度為O(m×n2)，AP、AP-VSM、SAP、DAAP算法的時間復雜度都為O(m×n)，其中m為近鄰傳播算法的迭代次數，n為樣本點數。

從聚類類數來看，AP-VSM和SAP分別有6個數據集與真實類數不同，APAP有5個，DAAP有3個，但都比原始AP算法更接近真實類數，而MSAAP算法在這16個數據集上最終的聚類個數都與真實類數相符。

Table 6 Table of F-measure,Time and clusters表6 F-measure、時間、類數對比表

從準確率、時間、類數來看，MSAAP算法除了在時間復雜度上略大于AP、AP-VSM、SAP、APAP這4種算法外，準確率、類數相比來說更好。從整體來看，本文算法具有更好的聚類性能。

4.4 效果圖分析

為了直觀地看出6種聚類算法優劣，本文通過聚類效果圖展示的形式，來更加直觀地反映表4數據的有效性。為了更好地顯示聚類效果，通過PCA將數據集降至2維，從而可以在平面上顯示最終的聚類結果。本文選取wine、seeds、YaleB、JAFFE數據庫進行對比。wine有178個樣本點，13維屬性，3類數據，wine的屬性變量為連續變量，是流行分布的，是不平衡的數據；seeds有210個樣本點，7維屬性，3類數據，seeds的所有屬性值都為實值連續的；YaleB數據庫有45個樣本點，192×168維屬性，5類數據，YaleB每幅圖像都有相對較大的光照變化、表情變化、部分缺損以及姿態變化；JAFFE數據庫有50個樣本點，256×256維屬性，5類數據，每個人有7種表情的圖片。

wine和seeds數據集聚類難度在于3類數據在分布的區域位置上相互交叉，不同類的數據點之間的距離比同類之間的距離要近，如果算法中用一些傳統的相似度計算公式或者維度選取不合適會造成聚類結果的差異性。YaleB和JAFFE數據庫聚類難度在于孤立點較多，會造成聚類時選取聚類中心點過多，最終聚類的類數與實際情況不符。聚類效果圖見圖5到圖8。

Fig.5 wine data set clustered by 6 methods圖5 wine數據集6種方法聚類效果圖

Fig.6 seeds data set clustered by 6 methods圖6 seeds數據集6種方法聚類效果圖

Fig.7 YaleB data set clustered by 6 methods圖7 YaleB數據集6種方法聚類效果圖

Fig.8 JAFFE data set clustered by 6 methods圖8 JAFFE數據集6種方法聚類效果圖

圖5到圖8左至右依次為原始數據分布圖，AP、AP-VSM、DAAP、SAP、APAP、MSAAP聚類效果圖，從圖5、圖6和圖8可知，當數據集中有若干個數據點為孤立點時，AP、AP-VSM、DAAP、SAP、APAP這5種算法將這些孤立點單獨聚為一類，而MSAAP算法很好地處理了這些孤立點，證明該方法在處理邊緣點時效果較好。同時從4幅圖中可以看出MSAAP聚類的效果圖中的類數以及聚類中心點的選取都與原始數據相符合，聚類后樣本點分布的區域與原始數據集分布的很接近，區域密度也類似，并且類與類之間相互交叉得很少。而其他5種算法在處理這些數據集時均出現聚類結果與原始數據不一致的情況。

從這些效果圖中可以直觀地看出MSAAP算法對傳統AP算法有了明顯的改進，同時相比較本文中提到的其他改進算法也有明顯的改進。再結合表6的數據分析說明MSAAP具有很好的聚類性能。

5 結束語

本文介紹了近鄰傳播算法(AP)和基于多維空間調整數據點空間分布的原理與步驟，首先介紹了熵的概念，并通過熵值求解屬性的權重的計算步驟；其次利用熵值權重構造新型的相似度矩陣；然后對數據點在多維空間分布的位置進行動態調整的問題進行建模和求解；最后在UCI數據集和人臉數據庫上進行了對比實驗。證明了本文所研究的方法在處理多重尺度和任意形狀的數據集時具有較好的聚類效果。