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

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

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

0 引 言

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

上述文獻改進AP算法的思路是給偏向參數注入數據分布特征的先驗知識，提高AP辨識聚類中心的能力，從而提高聚類精度。基于此思想，本文提出一種基于鄰域相似度的近鄰傳播聚類算法(affinity propagation clustering algorithm based on neighborhood similarity，ZC-AP)，用鄰域相似度描述數據樣本的空間分布特征，取代原AP算法的聚類度量作為新的聚類依據，并將鄰域相似度作為數據樣本的先驗知識注入偏向參數，提高AP算法對復雜特征數據的聚類準確性。通過分析數據樣本的統計特性，對數據概率分布曲線進行擬合，自適應地確定鄰域半徑和鄰域密度，利用鄰域相似度構建出相似度矩陣并求得偏向參數。最后在UCI數據集上驗證本文算法的可行性。

1 數據樣本鄰域相似度的計算方法

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

圖1 數據樣本的密度分布

定義1 對于一個數據樣本Yi，將Yi的Eps鄰域

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

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

(1)

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

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

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

(2)

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

定義3 結合共同數據點集和歐氏距離，將數據集中點之間的相似度關系定義為鄰域相似度Tn

(3)

(4)

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

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

(2)當兩點相距較近時，若它們共同數據點數較少，即Rn較小，此時Tn也會很小；若它們的共同數據點數較大，即Rn較大，此時Tn也較大。

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

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

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

輸入：數據集V={X1,X2,X3…,Xn}；

輸出：聚類中心的位置和個數；

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

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

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

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

步驟5 構造循環，進行以下步驟：

(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中尋找最大的數據樣本即為聚類中心點。

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

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

上述算法步驟中，步驟2較為關鍵，其細節說明如下。

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

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

(11)

多項式擬合公式為

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

(12)

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

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

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

(13)

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

(2)進行列排序并轉置得到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)矩陣的概率分布曲線進行數據擬合，得到擬合曲線。

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

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

3 實驗與分析

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

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

(1)準確率(accuracy，ACC)

準確率ACC表示聚類結果的正確率

(16)

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

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

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

(17)

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

(3)芮氏指標(rand index，RI)

芮氏指標是在聚類結果與真實簇間關系未知時的準確性評價指標[17]

(18)

f00表示具有不同類標簽的數據點被分到不同類別的數目，f11表示具有相同類標簽的數據點被分到同一類別的數目，N表示數據樣本總數。

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

表1 UCI測試數據集

本文算法(ZC-AP)與傳統AP算法、M-AP算法作比較，以ACC、NMI、RI作為評價指標，結果見表2。圖2是用表2數據繪制的準確率直方圖，直觀地展示3種算法在5個數據集上準確率ACC的比較。從表2和圖2可看出，改進后的ZC-AP算法在5個數據集上的測試結果均優于原始AP算法和M-AP算法。以Twomoon數據集為例，原始AP算法的ACC、NMI、RI項指標分別為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倍，說明改進算法在該數據集上的準確率有了較大提高，聚類結果與真實類標號吻合度較高。在German數據集上，ZC-AP算法比原AP算法在ACC、NMI、RI指標上分別提高了5.4%，34.5%和5.2%，比M-AP算法提高了7.7%、61.8%、5.2%。在Wpbc、Breast、Soybean等數據集上算法的準確率ACC均優于AP算法。

表2 聚類結果比較

圖2 聚類結果直方圖

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

圖3 3種算法在Twomoon數據集上的聚類結果

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

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

表3 人工選擇Eps及相應準確率

圖4 KNN

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

圖5 多項式擬合曲線

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

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

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

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

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

(19)

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

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

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

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

4 結束語

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

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

(2)采用統計學方法分析數據集的統計特性，根據數據概率分布自動求出鄰域半徑，提高了AP算法的自適應性。