多維空間可調(diào)整的近鄰傳播聚類算法*

錢雪忠，王衛(wèi)濤

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

1 引言

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

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

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

2 近鄰傳播算法

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

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

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

根據(jù)以上公式迭代計(jì)算歸屬度矩陣和吸引度矩陣，最終使得聚類目標(biāo)函數(shù)最大化，其聚類目標(biāo)函數(shù)如下：

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

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

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

3 MSAAP算法

3.1 算法描述

3.1.1 熵值法計(jì)算屬性權(quán)重

熵值是具有不確定性的一種度量。信息量越大，不確定性就越小，熵也就越??；信息量越小，不確定性越大，熵也越大。因此根據(jù)熵的特性，可以利用熵值來判斷某個(gè)指標(biāo)的離散程度，指標(biāo)的離散程度越大，該指標(biāo)對(duì)綜合評(píng)價(jià)的影響（權(quán)重）越大，其熵值越小。同時(shí)熵在信息論中已經(jīng)得到廣泛的應(yīng)用，因此本文通過計(jì)算數(shù)據(jù)樣本點(diǎn)的熵值來確定各個(gè)屬性的權(quán)重，可以更能真實(shí)表達(dá)數(shù)據(jù)集的特性。

計(jì)算熵值的過程需要依次計(jì)算歸一化指標(biāo)、指標(biāo)比重、指標(biāo)熵值、信息熵冗余度、指標(biāo)權(quán)值。其公式如下：

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

圖1中的橫軸為數(shù)據(jù)集的維數(shù)，縱軸為每一維特征的權(quán)重，從圖中可以看出，通過計(jì)算樣本點(diǎn)各個(gè)屬性的熵值可以很好地區(qū)分出屬性的重要程度，然后根據(jù)實(shí)際實(shí)驗(yàn)的需要，選取若干個(gè)權(quán)重屬性。圖中用到的數(shù)據(jù)集的具體屬性在第4章中介紹。

3.1.2 根據(jù)權(quán)重計(jì)算相似度矩陣

Fig.1 Attributes weighted graphs calculated by entropy method圖1 通過熵值法計(jì)算的屬性權(quán)重圖

其中，r為核變換系數(shù)。

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

Fig.2 Comparison chart of wine data set圖2 wine數(shù)據(jù)集對(duì)比圖

Fig.3 Comparison chart of YaleB data set圖3 YaleB數(shù)據(jù)集對(duì)比圖

圖中es_rate為歐式距離平方的負(fù)數(shù)計(jì)算的相似度比值，ds_rate為密度自適應(yīng)計(jì)算的相似度比值，ws_rate為本文采用的加權(quán)密度自適應(yīng)比值。從結(jié)果看出，ws_rate的比值是最大的，說明了此方法在計(jì)算同類數(shù)據(jù)點(diǎn)的相似度比es_rate和ds_rate更大，在計(jì)算不同類數(shù)據(jù)點(diǎn)之間時(shí)，ws_rate相比另外兩種則更小，說明ws_rate計(jì)算相似度更準(zhǔn)確。為保證實(shí)驗(yàn)的公正性，同類數(shù)據(jù)點(diǎn)和不同類數(shù)據(jù)點(diǎn)都是隨機(jī)選取的，并做10次對(duì)比實(shí)驗(yàn)。

3.1.3 根據(jù)多維空間調(diào)整個(gè)體空間分布

AP算法每次迭代后，會(huì)有吸引度和歸屬度矩陣生成，吸引度和歸屬度矩陣的加和表示了兩兩數(shù)據(jù)點(diǎn)之間的相似程度，因此將吸引度和歸屬度加和的指標(biāo)作為衡量指標(biāo)，來調(diào)整個(gè)體的空間分布。

首先需要前期處理工作，為了避免正負(fù)數(shù)的相互抵消，首先采用sigmoid函數(shù)將AR矩陣映射到[0,1]區(qū)間內(nèi)，AR為歸屬度矩陣A和吸引度矩陣R之和。然后根據(jù)3.1.1節(jié)計(jì)算出的權(quán)重矩陣W，選出前l(fā)個(gè)屬性，屬性集合為ls。

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

其中，1表示正相關(guān)，-1表示負(fù)相關(guān)，j∈ls時(shí)的計(jì)算步驟如下：

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中，左側(cè)圖為調(diào)整前的樣本點(diǎn)分布，右側(cè)為調(diào)整后的樣本點(diǎn)分布，其中左側(cè)圖中處于坐標(biāo)軸的中心黑點(diǎn)為當(dāng)前調(diào)整的樣本點(diǎn)。圖4是從模型的角度來分析整體數(shù)據(jù)點(diǎn)調(diào)整的基本規(guī)律，為了更好地展示，采用二維空間來表示，因此劃分的總的子空間數(shù)目為22，其中A、B、C、D分別代表四個(gè)空間，每個(gè)空間內(nèi)包含若干當(dāng)前數(shù)據(jù)點(diǎn)的鄰域點(diǎn)，然后分別計(jì)算：

Fig.4 Chart of spatial adjustment圖4 空間調(diào)整分布示意圖

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

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

Table 1 Parameter selection table of wine表1 wine數(shù)據(jù)集的參數(shù)選取表

Table 2 Parameter selection table of leuk72_3k表2 leuk72_3k數(shù)據(jù)集的參數(shù)選取表

表1和表2中固定值對(duì)應(yīng)的數(shù)據(jù)為freq取一定值時(shí)所對(duì)應(yīng)的準(zhǔn)確率和時(shí)間，sigmoid對(duì)應(yīng)的數(shù)據(jù)為本文利用sigmoid函數(shù)計(jì)算頻率對(duì)應(yīng)的準(zhǔn)確率和時(shí)間。從表中可以看出頻率的選取與準(zhǔn)確率沒有比例關(guān)系，對(duì)于任意的數(shù)據(jù)集可能是任意的固定值，因此在實(shí)際的仿真實(shí)驗(yàn)有一定的難度，同時(shí)當(dāng)頻率取某個(gè)固定值時(shí)準(zhǔn)確率高了，那么時(shí)間就會(huì)很慢，時(shí)間快了，準(zhǔn)確率就會(huì)下降。而利用sigmoid函數(shù)計(jì)算頻率就會(huì)在保證準(zhǔn)確率的同時(shí)，降低時(shí)間復(fù)雜度。此處提到的準(zhǔn)確率會(huì)在本文4.1節(jié)介紹。

3.2 算法步驟

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

Output：idx：Clustering results.

1.w=entropy(X)//由3.1.1節(jié)計(jì)算

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計(jì)算

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 實(shí)驗(yàn)結(jié)果與分析

不同指標(biāo)往往具有不同的量綱和單位，這樣會(huì)影響數(shù)據(jù)分析的結(jié)果，為了消除指標(biāo)之間的量綱的影響，本文對(duì)數(shù)據(jù)集進(jìn)行了歸一化處理。本文選取了13個(gè)UCI數(shù)據(jù)集和ORL、YaleB、JAFFE人臉數(shù)據(jù)庫(kù)。數(shù)據(jù)集信息見表3。

4.1 評(píng)價(jià)指標(biāo)

為了更加客觀地反映聚類算法的優(yōu)劣，本文選取F-Measure作為算法的評(píng)價(jià)指標(biāo)，F(xiàn)-measure是由precision（精確率）和recall（召回率）共同表示，準(zhǔn)確率（F-measure）通常用來表示聚類準(zhǔn)確性的優(yōu)劣。計(jì)算公式如下：

Table 3 Information of data set表3 數(shù)據(jù)集信息

4.2 參數(shù)調(diào)整分析

由于在實(shí)驗(yàn)過程中，引入了鄰域的閾值和特征維度兩個(gè)參數(shù)，當(dāng)參數(shù)不同時(shí)，實(shí)驗(yàn)結(jié)果也不同。因此需要在大量的實(shí)驗(yàn)中，找出適合不同數(shù)據(jù)集的參數(shù)，表4、表5為本文做的參數(shù)選取實(shí)驗(yàn)。

表4、表5中，eps表示閾值，dim表示維度。從表4、表5可以看出，參數(shù)閾值和維度對(duì)聚類結(jié)果影響很大，因?yàn)樵趯?shí)驗(yàn)中，閾值是控制樣本點(diǎn)的鄰域個(gè)數(shù)，能影響散落在各個(gè)空間中鄰域點(diǎn)的數(shù)目，最終會(huì)影響樣本點(diǎn)的分布的調(diào)整，所以閾值對(duì)聚類結(jié)果影響較大。而維度是m個(gè)權(quán)重最大的屬性，當(dāng)m取不同值時(shí)，選取的屬性個(gè)數(shù)就不同，而在調(diào)整樣本點(diǎn)分布時(shí)，所改變的樣本點(diǎn)的屬性不同，因此最終對(duì)聚類結(jié)果影響較大。

Table 4 Parameter selection table of wine表4 wine數(shù)據(jù)集的參數(shù)選取表

Table 5 Parameter selection table of zoo表5 zoo數(shù)據(jù)集的參數(shù)選取表

4.3 準(zhǔn)確率、時(shí)間、類數(shù)分析

本文從準(zhǔn)確率、時(shí)間、聚類類數(shù)3個(gè)維度對(duì)AP、AP-VSM、DAAP、SAP、APAP、MSAAP進(jìn)行了對(duì)比。其中，F(xiàn)為準(zhǔn)確率（F-measure），Time單位為秒（s）。對(duì)比如表6所示。

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

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

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

Table 6 Table of F-measure,Time and clusters表6 F-measure、時(shí)間、類數(shù)對(duì)比表

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

4.4 效果圖分析

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

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

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

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

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

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

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

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

5 結(jié)束語

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