基于鄰域相似度的近鄰傳播聚類算法

趙 昱，陳 琴，蘇一丹，陳慧姣

(廣西大學(xué) 計算機與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

近鄰傳播聚類算法(AP)[1-3]本質(zhì)上是一種基于中心的聚類算法，對特征規(guī)整的數(shù)據(jù)聚類效果較好，但對于特征復(fù)雜的數(shù)據(jù)辨識能力低，聚類效果較差[4-6]。針對此問題，有學(xué)者提出了相關(guān)改進，文獻[7]通過進行局部聚類求得點簇集，提高聚類準(zhǔn)確率；文獻[8]通過對數(shù)據(jù)進行降維處理提高AP算法的精確度；文獻[9]對大型數(shù)據(jù)集進行預(yù)處理，并結(jié)合CVM壓縮和合并的方法提高算法的準(zhǔn)確率；文獻[10]使用核函數(shù)辨識數(shù)據(jù)特征，在一定程度上克服了AP算法對于數(shù)據(jù)集敏感的問題，但核函數(shù)的類型和工作參數(shù)對AP聚類精度有直接影響，需要優(yōu)化以提高聚類精度[11]。

上述文獻改進AP算法的思路是給偏向參數(shù)注入數(shù)據(jù)分布特征的先驗知識，提高AP辨識聚類中心的能力，從而提高聚類精度?；诖怂枷耄疚奶岢鲆环N基于鄰域相似度的近鄰傳播聚類算法(affinity propagation clustering algorithm based on neighborhood similarity，ZC-AP)，用鄰域相似度描述數(shù)據(jù)樣本的空間分布特征，取代原AP算法的聚類度量作為新的聚類依據(jù)，并將鄰域相似度作為數(shù)據(jù)樣本的先驗知識注入偏向參數(shù)，提高AP算法對復(fù)雜特征數(shù)據(jù)的聚類準(zhǔn)確性。通過分析數(shù)據(jù)樣本的統(tǒng)計特性，對數(shù)據(jù)概率分布曲線進行擬合，自適應(yīng)地確定鄰域半徑和鄰域密度，利用鄰域相似度構(gòu)建出相似度矩陣并求得偏向參數(shù)。最后在UCI數(shù)據(jù)集上驗證本文算法的可行性。

1 數(shù)據(jù)樣本鄰域相似度的計算方法

近鄰傳播聚類算法(AP)的基本思想是：對于數(shù)據(jù)集X={X1,X2,…,XN}，使用距離公式計算相似度矩陣S，對支持度矩陣(responsibility，R)和歸屬度矩陣(availability，A)進行迭代更新，通過R和A篩選出聚類中心點。相似度矩陣S對角線上的元素S(i,i)稱為偏向參數(shù)(pre-ference)，它表示數(shù)據(jù)樣本Xi成為聚類中心的可能性，此參數(shù)影響聚類中心的產(chǎn)生。初始時AP算法對角線元素S(i,i)取相同的值，表示每一個數(shù)據(jù)樣本作為聚類中心的概率相同，記作：S(i,i)=p。在AP算法中，點間距離作為唯一的度量依據(jù)直接影響到S矩陣的構(gòu)建、偏向參數(shù)的取值和R矩陣、A矩陣的迭代更新[12-14]。如圖1所示，樣本Xi、Xj、Xk的距離關(guān)系滿足d(Xj，Xk)

圖1 數(shù)據(jù)樣本的密度分布

定義1 對于一個數(shù)據(jù)樣本Yi，將Yi的Eps鄰域

NEps(Yi)定義為以Yi為球心，以Eps為半徑的多維超球體區(qū)域，即

NEps(Yi)={Yi∈D|dist(Yi,Yu)≤Eps}

(1)

其中，D為多維實空間上的數(shù)據(jù)集，且D?Rd，dist(Yi,Yu)表示Yi與數(shù)據(jù)集中任意一個對象Yu的間距。選擇的Eps越大，則該處數(shù)據(jù)點越稀疏，反之則數(shù)據(jù)點會越密集，所以如何選擇合適的鄰域半徑對聚類效果十分重要。

定義2 對于數(shù)據(jù)集中的兩點Yi和Yu，將Yi為中心，Eps為半徑的區(qū)域看作一個圓，圓內(nèi)包含的數(shù)據(jù)點數(shù)稱為以Yi為圓心，Eps為半徑的鄰域密度，記做N1；同理，把以Yu為圓心，Eps為半徑的鄰域密度記做N2，將它們的交集即N1、N2相同數(shù)據(jù)點的集合定義為Rn

Rn(Yi,Yu)=
{(dist(N1,Yi)

(2)

由式(2)可看出：Rn可能為空，也可能非空。當(dāng)Yi、Yu所在區(qū)域密度較大，那么Rn也相對較大。

定義3 結(jié)合共同數(shù)據(jù)點集和歐氏距離，將數(shù)據(jù)集中點之間的相似度關(guān)系定義為鄰域相似度Tn

(3)

(4)

其中，dist(Yi,Yu)表示Yi、Yu兩點的歐氏距離，d為數(shù)據(jù)維數(shù)。鄰域相似度Tn具有如下性質(zhì)：

(1)當(dāng)兩點相距很遠(yuǎn)時，它們共同區(qū)域中數(shù)據(jù)點的個數(shù)幾乎為零，即Rn=0。鄰域相似度Tn與歐氏距離類似，直接對數(shù)據(jù)點進行從屬判斷。

(2)當(dāng)兩點相距較近時，若它們共同數(shù)據(jù)點數(shù)較少，即Rn較小，此時Tn也會很?。蝗羲鼈兊墓餐瑪?shù)據(jù)點數(shù)較大，即Rn較大，此時Tn也較大。

對于復(fù)雜數(shù)據(jù)集，鄰域相似度Tn能提高同一簇中各樣本點之間的相似性，較傳統(tǒng)歐氏距離更容易辨別數(shù)據(jù)特征。

2 基于鄰域相似度的近鄰傳播聚類算法

用鄰域相似度改進的AP算法流程如下：

輸入：數(shù)據(jù)集V={X1,X2,X3…,Xn}；

輸出：聚類中心的位置和個數(shù)；

步驟1 初始化算法的參數(shù)，包括：阻尼因子x，最大迭代次數(shù)maxits，連續(xù)收斂次數(shù)convits，初始化支持度和歸屬度矩陣。

步驟2 讀入數(shù)據(jù)集，計算數(shù)據(jù)集中兩點X1和Xk之間的歐氏距離，由此構(gòu)建最近鄰數(shù)據(jù)集合，對該集合的數(shù)據(jù)概率分布曲線進行擬合，求解導(dǎo)數(shù)與微分方程，求得密度半徑Eps。

步驟3 求點X1和Xk的鄰域密度，以及它們之間的相同數(shù)據(jù)點集Rn。

步驟4 通過式(3)求出Tn，從而構(gòu)造相似度矩陣S,并求出偏向參數(shù)P。

步驟5 構(gòu)造循環(huán)，進行以下步驟：

(1)計算并更新支持度矩陣R

(5)

ri(i,k)=λ×ri-1(i,k)+(1-λ)×ri(i,k)

(6)

其中

r(k,k)=p(k)-max{a(k,j)+s(k,j)}

(7)

(8)

(2)計算并更新歸屬度矩陣A

(9)

ai(i,k)=λ×ai-1(i,k)+(1-λ)×ai(i,k)

(10)

(3)計算E=R+A，從E中尋找最大的數(shù)據(jù)樣本即為聚類中心點。

(4)若該次迭代已經(jīng)超過最大迭代次數(shù)maxits，或是連續(xù)convits次迭代聚類情況不發(fā)生改變，則迭代結(jié)束，否則繼續(xù)進行迭代直到超過最大迭代次數(shù)或找到聚類中心點。

步驟6 輸出聚類中心點的信息。

上述算法步驟中，步驟2較為關(guān)鍵，其細(xì)節(jié)說明如下。

由步驟2求得的最近鄰數(shù)據(jù)集合繪制概率分布曲線，對距離的概率分布進行數(shù)據(jù)擬合，求取合適的Eps半徑。選取常用的高斯擬合和多項式擬合函數(shù)進行數(shù)據(jù)擬合，其中,高斯擬合的公式為

f(x)=a×exp(-((x-b)/c)2)

(11)

多項式擬合公式為

f(x)=axn+bxn-1+cxn-2+…+dx+e

(12)

根據(jù)擬合結(jié)果，得到擬合組內(nèi)方差SSE；均方根誤差R-SSE；相關(guān)系數(shù)R-square[15,16]；通過比較擬合精度和計算復(fù)雜度，選擇合適的擬合函數(shù)進行計算。對于一個已知樣本，通過以下步驟求其鄰域半徑Eps。

(1)首先計算數(shù)據(jù)集的距離分布矩陣

DISTn×n={dist(i,j)|1≤i≤n，1≤j≤n}

(13)

得到一個n行n列的對稱矩陣。

(2)進行列排序并轉(zhuǎn)置得到KNNn×n矩陣

KNNn×n=sort(DISTn×n)

(14)

為計算方便，去掉第一列的全零集合并進行列排序得到KNNn×(n-1)矩陣(以下簡稱KNN矩陣)

KNNn×(n-1)=sort(KNN0n×n(1:end;2:end))

(15)

(3)對KNNn×(n-1)矩陣的概率分布曲線進行數(shù)據(jù)擬合，得到擬合曲線。

(4)對擬合函數(shù)進行求解，去掉邊界點得到所求Eps半徑。

上述算法中，在AP算法的偏向參數(shù)中注入了數(shù)據(jù)樣本之間相似度的先驗知識，提高了AP算法對復(fù)雜數(shù)據(jù)特征的辨識能力。在步驟2中通過分析數(shù)據(jù)樣本的統(tǒng)計特性自動求出鄰域半徑，提高了鄰域相似度對不同數(shù)據(jù)集的自適應(yīng)性。

3 實驗與分析

在PC機上進行仿真實驗，處理器為Intel Pentium G460(2.8 GHZ)，內(nèi)存8 GB，在Windows7 x64平臺上用MATLAB實現(xiàn)算法。

選取以下3個指標(biāo)對聚類算法的性能進行評價。

(1)準(zhǔn)確率(accuracy，ACC)

準(zhǔn)確率ACC表示聚類結(jié)果的正確率

(16)

其中，K為聚類結(jié)果的簇數(shù)目，Li表示聚類結(jié)果中第i簇內(nèi)的數(shù)據(jù)樣本能正確聚類的數(shù)目。聚類結(jié)果與真實類別個數(shù)完全相符時準(zhǔn)確率為1，兩者越不相符準(zhǔn)確率越低。

(2)正則化互信息(normalized mutual information，NMI)

正則化互信息用來檢驗數(shù)據(jù)樣本間的吻合程度

(17)

其中，K為簇數(shù)目，Ni和Nj表示第i、j個聚類的樣本數(shù)目，N為樣本總數(shù)，Nij表示第i個聚類結(jié)果與第j類的契合程度。NMI在[0,1]內(nèi)取值，該值的大小表示聚類結(jié)果與真實情況吻合度的高低。

(3)芮氏指標(biāo)(rand index，RI)

芮氏指標(biāo)是在聚類結(jié)果與真實簇間關(guān)系未知時的準(zhǔn)確性評價指標(biāo)[17]

(18)

f00表示具有不同類標(biāo)簽的數(shù)據(jù)點被分到不同類別的數(shù)目，f11表示具有相同類標(biāo)簽的數(shù)據(jù)點被分到同一類別的數(shù)目，N表示數(shù)據(jù)樣本總數(shù)。

本文實驗取阻尼因子為0.8，迭代次maxits為1000，收斂迭代次數(shù)convits為50。選取的5個UCI測試數(shù)據(jù)集屬性見表1。

表1 UCI測試數(shù)據(jù)集

本文算法(ZC-AP)與傳統(tǒng)AP算法、M-AP算法作比較，以ACC、NMI、RI作為評價指標(biāo)，結(jié)果見表2。圖2是用表2數(shù)據(jù)繪制的準(zhǔn)確率直方圖，直觀地展示3種算法在5個數(shù)據(jù)集上準(zhǔn)確率ACC的比較。從表2和圖2可看出，改進后的ZC-AP算法在5個數(shù)據(jù)集上的測試結(jié)果均優(yōu)于原始AP算法和M-AP算法。以Twomoon數(shù)據(jù)集為例，原始AP算法的ACC、NMI、RI項指標(biāo)分別為0.272、0.184、0.603，M-AP算法為0.728、0.184、0.603，而ZC-AP算法達到了0.997、0.969、0.993，ZC-AP比原始AP算法分別提高了3.67倍、5.27倍、1.65倍，比M-AP算法分別提高了1.37倍、5.27倍、1.65倍，說明改進算法在該數(shù)據(jù)集上的準(zhǔn)確率有了較大提高，聚類結(jié)果與真實類標(biāo)號吻合度較高。在German數(shù)據(jù)集上，ZC-AP算法比原AP算法在ACC、NMI、RI指標(biāo)上分別提高了5.4%，34.5%和5.2%，比M-AP算法提高了7.7%、61.8%、5.2%。在Wpbc、Breast、Soybean等數(shù)據(jù)集上算法的準(zhǔn)確率ACC均優(yōu)于AP算法。

表2 聚類結(jié)果比較

圖2 聚類結(jié)果直方圖

為更直觀觀察ZC-AP聚類效果，我們從測試數(shù)據(jù)集中選擇一個二維數(shù)據(jù)集Twomoon，將3種算法的聚類結(jié)果描繪在二維坐標(biāo)軸上，如圖3所示。由圖3可看出，原始AP算法和M-AP算法雖然可將數(shù)據(jù)樣本分為兩類，但聚類準(zhǔn)確率較低，而改進算法ZC-AP給出了正確的聚類結(jié)果。所以在對特征復(fù)雜數(shù)據(jù)樣本進行聚類時，通過使用鄰域相似度增大了同一簇點之間的相似程度，提高了聚類準(zhǔn)確率。

圖3 3種算法在Twomoon數(shù)據(jù)集上的聚類結(jié)果

在ZC-AP算法中，通過分析數(shù)據(jù)概率分布情況自動確定了鄰域半徑，而在人工選擇鄰域半徑時，Eps需要在[0,50]之間隨機選取，表3是以Wpbc數(shù)據(jù)集為例，展示人工選擇鄰域半徑的聚類結(jié)果。由表3可看出：隨機選取的Eps半徑對聚類結(jié)果的影響很大，且聚類準(zhǔn)確度均低于改進算法。例如，當(dāng)Eps取0.258時，ACC為0.424，當(dāng)Eps取10.821時，ACC為0.763，兩者差別較大，由改進算法可以求得Eps為0.377，此時聚類精度達到0.818，NMI指標(biāo)和RI指標(biāo)也相應(yīng)提升。因此改進算法較好地解決了鄰域半徑人工選取不當(dāng)影響AP精度的問題。

ZC-AP算法需要擬合數(shù)據(jù)概率分布曲線，以Twomoon數(shù)據(jù)集為例，圖4、表4、圖5展示了擬合過程，此過程說明如下：

表3 人工選擇Eps及相應(yīng)準(zhǔn)確率

圖4 KNN

擬合函數(shù)SSER-SSER-SQUARE高斯擬合0.008 2510.98540.002 349多項式擬合0.006 2040.98920.002 039

圖5 多項式擬合曲線

(1)計算Twomoon數(shù)據(jù)集的距離分布矩DISTn×n。

(2)對DISTn×n進行轉(zhuǎn)置排序并繪圖得到KNNn×(n-1)圖，該圖包含1502個樣本點信息，由1502條曲線組成，排列較為密集，此處任取其中100條線顯示其變化規(guī)律。

(3)KNNn×(n-1)圖中各條曲線變化趨勢大致相同，均在某點處急劇上升，其中K的取值范圍為[1,1502]，在該區(qū)間上K的取值對結(jié)果影響不大，可任意取值，為方便計算，取K=4反映其它曲線形狀，繪制其概率分布圖，分別進行多項式擬合和高斯擬合，比較擬合評價指標(biāo)，發(fā)現(xiàn)高斯擬合精度高，但是擬合階數(shù)也高，因此計算復(fù)雜度高。而在相同計算復(fù)雜度下，多項式擬合階數(shù)較低，同時擬合精度較高，選擇三階多項式擬合和二次高斯擬合作比較，擬合結(jié)果見表4。

由表4可看出，三階多項式擬合組內(nèi)方差、均方根誤差、相關(guān)系數(shù)這三項參數(shù)均優(yōu)于二次高斯擬合，故選擇多項式擬合求取Eps半徑。多項式擬合效果如圖5所示。

(4)對f(x)求二次導(dǎo)數(shù)可得f(x)″=12ax2+6bx+2c,求解二次導(dǎo)數(shù)方程的解為

(19)

舍去靠近邊界的點，可得Eps=f(x0)。

(5)求以Eps為半徑的鄰域密度矩陣SRn。

(6)求鄰域相似度矩陣STn。

(7)進行吸引度矩陣R和支持度矩陣A的計算和迭代更新。

4 結(jié)束語

本文提出一種基于鄰域相似度的AP聚類算法，提高了傳統(tǒng)AP算法在特征復(fù)雜數(shù)據(jù)集上的聚類精度，引入一種通過數(shù)據(jù)集相關(guān)統(tǒng)計特性自動確定鄰域半徑的方法，提高了算法的自適應(yīng)性。在UCI數(shù)據(jù)集上與傳統(tǒng)AP算法進行了聚類效果比較，驗證了算法的可行性，得到以下結(jié)論：

(1)采用鄰域相似度作為新的聚類依據(jù)，取代原AP算法中的距離度量，能使算法在復(fù)雜數(shù)據(jù)集上的聚類精確度得到提高。

(2)采用統(tǒng)計學(xué)方法分析數(shù)據(jù)集的統(tǒng)計特性，根據(jù)數(shù)據(jù)概率分布自動求出鄰域半徑，提高了AP算法的自適應(yīng)性。