基于約束投影的近鄰傳播聚類算法

錢雪忠,趙建芳,賈志偉

(1.江南大學物聯網工程學院,江蘇 無錫 214122;2.成都信息工程學院,四川 成都 610225)

基于約束投影的近鄰傳播聚類算法

錢雪忠1,趙建芳1,賈志偉2

(1.江南大學物聯網工程學院,江蘇 無錫 214122;2.成都信息工程學院,四川 成都 610225)

提出了一種基于約束投影的近鄰傳播AP聚類算法。AP算法是在數據點相似度矩陣的基礎上進行聚類的，很多傳統的聚類方法都無法與其相媲美。但是，對于結構復雜的數據，AP算法往往得不到理想的結果。文中算法先對約束信息進行擴展，然后利用擴展的約束信息指導投影矩陣的獲取，在低維空間中，利用約束信息對聚類結果進行修正。實驗表明，文中算法與對比算法相比，時間性能更優，聚類效果更佳。

半監督；聚類；約束信息；投影；近鄰傳播

1 引言

將物理或抽象對象的集合分成由類似的對象組成的多個類的過程稱為聚類。聚類算法是在沒有任何先驗信息的情況下進行的，因此這類方法又稱為無監督學習方法。然而，在很多實際問題中，有時候我們可以獲得少部分的先驗信息，如何利用先驗信息來改善聚類算法的性能成為一個新的研究熱點，所提出的算法稱為半監督聚類算法[1]。通常先驗信息是由領域專家給出的，先驗信息可分為類標記信息和成對約束信息。類標記信息明確了某數據點應屬于的類，而成對約束信息則規定了某兩個數據點之間的聯系，若它們應屬于同一個類，則稱這兩個數據點之間存在正約束關系(Must-link)，反之，則稱它們存在負約束關系(Cannot-link)。半監督聚類算法大致可分為兩類，一類是基于約束的方法，另一類是基于距離的方法。前者利用成對約束先驗信息來指導最優聚類的搜索過程。如司文武、錢江濤等人在文獻[2]中提出了一種基于譜聚類的半監督聚類算法。該方法利用標簽數據信息，調整點與點之間形成的相似度矩陣，最后基于被調整的聚類矩陣進行譜聚類。而在文獻[3]中，趙鳳和焦李成等人提出了利用先驗信息來尋找能夠體現數據結構的特征向量組合，并且在UCI數據集和MINIST手寫數據集上驗證了算法的有效性和魯棒性。后者則是利用先驗信息來訓練相似性距離測度函數，使之盡量滿足所給的先驗信息，再使用基于距離的方法來聚類。如Xing E P等人[4]提出利用標識信息并基于凸的方法優化了的馬氏距離。Klein D等人[5]提出利用標記信息并基于圖的方法改進了歐式距離。而Li Tao等人[6]充分利用先驗信息所隱藏的信息，提出了基于特征向量的空間映射及矩陣因數分解的方法。然而，同時集成約束和聚類的方法也受到了研究者的關注。如Bilenko M等人[7]通過把距離約束轉化為距離度量，改進了K-means算法，并將上述兩種思想集成于一個框架之下。Basu S等人[8]提出了一種統一的半監督聚類概率模型，利用改進后的隱式空間數據間的距離反映約束關系。

本文所提出的基于約束投影的近鄰傳播聚類算法屬于基于約束的方法。近鄰傳播聚類算法APC(Affinity Propagation Clustering)[9]是Frey B J在《Science》中提出來的。與以往的聚類方法相比，該方法可更快地處理大規模數據，得到更好的聚類效果。文中作者將近鄰傳播算法應用在人臉圖像聚類、基因表達數據的基因識別、手寫體字符識別、最優航空路線確定等問題上，實驗結果表明，近鄰傳播聚類算法在很短的時間內就能得到K中心算法花費很長時間才能達到的聚類效果。近鄰傳播算法的應用范圍比以往的聚類算法更廣，這是因為它對樣本點間形成的相似度矩陣的對稱性沒有任何要求。然而對于本身具有復雜結構的數據集，近鄰傳播算法也不能得到合理的效果[10]。針對近鄰傳播算法的這一缺陷，本文在半監督近鄰傳播算法的基礎上進一步利用先驗信息，使得先驗信息的應用提前到降維過程中。在降維過程中應用先驗信息一方面能約簡數據集，使得近鄰傳播算法更好地發揮其性能；另一方面使約簡后的數據集最大程度上保留原數據集的信息。實驗結果表明，基于約束投影的近鄰傳播聚類算法能很好地彌補近鄰傳播算法處理復雜數據效果不佳的缺陷，在時間性能和聚類結果方面都能取得較為滿意的效果。

2 AP算法及SAP算法

2.1 AP算法

近鄰傳播算法的目的是找到最優類代表點集合(Exemplar)，使得所有數據點到最近的類代表點的相似度之和最大。AP算法是在數據點的相似度矩陣S(Similarity)上進行聚類的。由于聚類的目標是使數據點與其類代表點之間的距離最小化，所以任意兩點的相似度可定義為兩點距離平方的相反數。

AP算法引入兩個重要的信息量參數，分別為吸引度R(Responsibility)和歸屬度A(Availability)。R(i,k)從點xi指向xk，表示xk適合作為數據點xi的聚類中心程度。A(i,k)是從點xk指向xi，表示點xi選擇點xk作為其聚類中心的程度。AP算法的迭代過程是不斷更新每一個點的吸引度和歸屬度的過程，迭代過程直到產生高質量的Exemplar結束。R和A的更新公式如下：

R(i,k)=S(i,k)-max{A(i,j)+S(i,j)}

(j∈{1,2,…,N,且j≠k})

(1)

(j∈{1,2,…,N,且j≠i,j≠k})

(2)

R(k,k)=p(k)-max{A(k,j)+S(k,j)}

(j∈{1,2,…,N,且j≠k}

(3)

第i次迭代后，吸引度Ri和歸屬度Ai要與前一次的Ri-1和Ai-1進行加權更新，更新公式如下：

Ri=(1-lam)*Ri+lam*Ri-1

(4)

Ai=(1-lam)*Ai+lam*Ai-1

(5)

其中，lam∈[0.5,1)。

2.2SAP算法

SAP算法是利用先驗信息來調整點與點之間的相似度矩陣，從而形成新的相似度矩陣S，在新得到的相似度矩陣的基礎上進行AP算法[11]。算法根據所給的先驗信息對相似度矩陣進行初步調整。當兩個數據點屬于正約束集，即(xi,xj)∈M時，認為這兩個數據點之間有很高的相似度，調整相似度矩陣，令S(i,j)=0；當兩個數據點屬于負約束集，即(xi,xj)∈C，認為這兩個數據點相似度極低，則調整相似度矩陣，令S(i,j)=-∞。在初步調整之后，算法又基于最短路徑原則對不包含在先驗信息中的數據點的相似度進行了全局調整。調整方法為：如果某對數據點既不在正約束集M中，又不在負約束集C中，但存在第三個數據點與這對數據點中兩個數據點分別相連，并且這一數據點與這兩個數據點的相似度之和大于這對數據點的初始相似度，則調整這對數據點的相似度為較大的相似度。最后利用C集中的信息對上述調整進行修正。上述過程轉化成公式為：

若(xi,xj)∈M,則：

S(i,j)=S(j,i)=0

(6)

若(xi,xj)∈C,則:

S(i,j)=S(j,i)=-∞

(7)

若(xi,xj)?{M∪C},則:

S(i,j)=S(j,i)=

max{S(i,j),S(i,k)+S(k,j)}

(8)

若(xi,xj)?{M∪C}&(xi,xk)∈C&(xk,xj)∈M,則:

S(i,j)=S(j,i)=-∞

(9)

雖然AP算法對相似度矩陣的對稱性沒有要求，能在很短的時間內得到K-means算法花費很長時間才能得到的聚類效果，但是對于結構復雜的數據集，其處理時間很長，且不能得到理想的聚類結果。SAP算法在AP算法的基礎上加入先驗信息，在一定程度上提高了AP算法的性能，但是其時間性能卻還是有待改善。據此提出了基于約束投影的近鄰傳播聚類算法。

3 基于約束投影的近鄰傳播聚類算法

3.1 約束投影

首先對先驗信息做如下規定：若數據點xi和xj在聚類后屬于同一個類，則稱(xi,xj)是一個正約束對；若數據點xi和xj在聚類后不能屬于同一個類，則稱(xi,xj)是一個負約束對，所有正約束對的集合稱為正約束集M，所有負約束對的集合稱為負約束集C。根據約束傳播理論可知，如果(xi,xj)∈M,且(xj,xk)∈M，則可以得到(xi,xk)∈M；如果(xi,xj)∈C，且(xj,xk)∈M，則可以得到(xi,xk)∈C。根據上述約束傳播，可以得到更多的約束，更新正約束集M和負約束集C，得到擴充的約束集M和C。

數據投影是根據某一準則，將高維數據變換到有意義的低維表示[12]。在利用約束信息指導投影矩陣的獲取時，除了考慮根據約束傳播原理更新的約束集M和C以外，還需考慮以下問題：在一個很小的局部區域內的數據點應該具有相似的特性，在高維空間中離正約束對最近的一對數據點，如果不屬于負約束集，在低維空間中應盡量使其靠近。同理可得，離負約束對最近的一對數據點，如果不屬于正約束集，在低維空間中應盡量使其遠離。為了解決上述問題，我們分別建立臨時正約束集M′和臨時負約束集C′，對M集和C集做臨時的擴充。這里所說的臨時擴充是指這一步擴充所得的約束信息僅用于指導投影矩陣的獲取，而在低維空間中進行聚類時，使用的監督信息是根據約束傳播原理所得到的M集和C集。M′和C′的計算方法如下：

?xl∈Nk(xi),若dist(xi,xj)≥dist(xl,xj),且M(xl)∩C(xj)=?,C(xl)∩M(xj)=?,則M′=M∪{(xl,xj)};

?xl∈Nk(xi),若dist(xi,xj)≤dist(xl,xj),且M(xl)∩M(xj)=?,則令C′=C∪{(xl,xj)}。

其中，Nk(xi)表示xi的k最鄰近集，dist(xi,xj)表示數據點xi和數據點xj之間的歐氏距離，M(xi)、C(xi)分別表示與數據點xi有正約束關系和負約束關系的所有數據點的集合。

為了在投影時充分利用M′和C′所包含的信息，我們對M′和C′所包含的信息進行了量化，量化的目標是使得M′中的數據點投影到低維空間中的距離盡量縮小，而C′中的數據點投影到低維空間中的距離盡量拉大，量化過程如下：

(10)

其中，λ是伸縮因子，用于控制信息量的放大與縮小程度。dist(xi,xj)是數據點xi與數據點xj之間的歐氏距離。

為求得投影矩陣，構造目標函數f(W)：

(11)

展開整理得：

WT(XDXT-XGXT)W=

WTX(D-G)XTW

(12)

其中，D是對角矩陣，Dii=∑jgi,j。為求得最大值，構造拉格朗日函數并且對ωi求導，投影矩陣W由矩陣D-G的前k個最大特征向量組成。

3.2 算法執行過程

基于約束投影的近鄰傳播聚類算法CBPAP(Constraints Based Projection Affinity Propagation) 對約束信息進行了兩次擴展，第一次擴展是基于約束傳播進行的，旨在從邏輯的角度擴大約束信息集，也可稱為真擴展。第二次擴展的目的是為了數據投影后能更準確地反映其原有的特性。第二次擴展是基于最小鄰域進行的，由于本次擴展生成的約束集并不用于低維空間中的聚類，因此稱為臨時擴展。將臨時擴展所得到的約束進行量化，并用于指導投影矩陣的獲取。在低維空間中，參照SAP算法的執行過程，對相似度矩陣進行修改，在修改后的相似度矩陣上進行迭代求解。與SAP算法不同的是，CBPAP算法在修改相似度矩陣時使用第一次擴展所產生的約束信息，而利用第二次擴展所產生的約束信息對聚類結果進行調整，這樣做的目的是為了使聚類結果既滿足約束信息的要求，又符合某一鄰域內的數據點具有相似特性的觀點。具體做法是查看聚類結果，若聚類結果中有數據點違反了M′中的約束信息，則分別計算這兩個數據點到其聚類中心的距離，調整這兩個數據點到距離較小的數據點所在的類中；若聚類結果中有數據點違反了C′中的約束信息，計算這兩個數據點到所有類的聚類中心的距離，在不違反C′約束信息的情況下，分別調整這兩個數據點到離其聚類中心距離最小的類中。CBPAP算法的執行過程如下：

(1)基于約束傳播對正約束集M和負約束集C進行第一次擴展。若(xi,xj)∈M,(xj,xk)∈M，則M=M+(xi,xk)；若(xi,xj)∈C,(xj,xk)∈M，則C=C+(xi,xk)。

(2)計算臨時約束集M′和C′，并根據gi,j的計算方法量化M′和C′中的信息。對于任意(xi,xj)屬于M′或C′，分別計算xi、xj的k近鄰集Nk(xi)、Nk(xj)，?xl∈Nk(xi)，若dist(xi,xj)≥dist(xl,xj)，且Ml∩Cj=?，Cl∩Mj=?，則令M′=M∪{(xl,xj)}；若(xi,xj)∈C，分別計算xi、xj的k近鄰集Nk(xi)、Nk(xj)，?xl∈Nk(xi)，若dist(xi,xj)≤dist(xl,xj)，且Ml∩Mj=?，則令C′=C∪{(xl,xj)}。根據gi,j的計算方法量化M′和C′中的信息。

(3)利用量化的信息指導投影矩陣W的獲取，并將原數據點空間X={x1,…,xn}?Rd投影到空間Y={y1,…,yn}?Rk。

(4)調整相似度矩陣S。若(yi,yj)∈M，調整S(i,j)=0。

(5)基于最短路徑原則進行全面調整。如果(yi,yj)?{M∪C}，則S(i,j)=max{S(i,j),S(i,k)+S(k,j)}。

(6)利用C集對上述兩步的調整進行修正。若(yi,yj)?{M∪C}并且(yi,yk)∈C、(yk,yj)∈M，則S(i,j)=-∞,S(j,i)=-∞。

(7)在調整后的相似性矩陣上迭代計算R(i,k)和A(i,k)，直到產生最優Exemplar或者達到最大迭代次數為止。

(8)利用臨時約束信息對聚類結果進行調整。

4 實驗及結果

本實驗在UCI數據集上進行，他們分別是Iris、Balance、Austra、Ionosphere和Air,表1對這些數據集的相關特性進行了描述。

Table 1 Information of dataset UCI

約束信息通常是由鄰域專家標記產生的，實驗中，為了避免人為標記帶來的偶然性，我們對數據點進行編號，每次隨機產生一組數字，如果這組數字對應的編號所代表的數據點在同一個類中，則將這兩個數據點組成一組正約束對加入正約束集中，否則組成負約束對加入負約束集中。實驗輸出的結果是100次實驗的平均值。在這100次實驗中，每次實驗都隨機產生新的約束對。實驗利用監督信息，將三組數據集都降到了三維空間。實驗所用的機器為Intel Core2 Duo CPU，2.0 GHz，內存為1.00 GB。

首先本文設計了驗證算法時間性能的實驗，表2列出了AP算法在各數據集上的運行時間，表3列出了約束為5、10、15和20的情況下SAP算法和CBPAP算法的時間性能對比，時間的單位為s。

Table 2 Time of AP

由表2可以看出，隨著維數的增多，AP算法的運行時間變長，換言之，AP算法對于高維數據的處理效果是不理想的。由表3可以看出，CBPAP算法的時間性能明顯優于SAP算法。綜合表2和表3，SAP算法和CBPAP較AP算法都有所提高，且CBPAP提高的程度比SAP算法要高。

Table 3 Contrast of time between SAP and CBPAP

Table 4 Output of average CRI

除了上述驗證算法聚類效果的實驗以外，本文還采用CRI指標對兩類半監督的AP算法的聚類效果進行對比。

CRI指標被視為常用的半監督聚類評價指標[5]，其定義如下：

(13)

其中，totalfreedecisions=n(n-1)/2-Cn，n為數據點的數目，Cn表示約束對的數目。correctfreedecisions表示劃分正確的數據對的數目減去約束對中劃分正確的數據對的數目。對于相同數量的約束對進行100次實驗，并輸出其平均結果。表4為實驗結果輸出的平均CRI值。

由表4可以看出，在約束對數目相同的情況下，CBPAP算法的聚類效果顯然優于SAP算法。而CBPAP算法在處理樣本數較多的Balance數據集和特征數較多的Ionosphere數據集時所表現出的優越性就更為突出了。產生這種優勢的原因是由兩方面組成的：第一，在利用監督信息進行約束投影的時候對約束信息進行了兩次擴展，這兩次擴展既考慮了邏輯上的正確性又顧及了數據的空間特性，所求得的投影空間能在約簡數據空間的同時更好地保留原數據集的特性，這樣的處理方式能有效地解決AP算法處理復雜數據集時效果不理想的弊端；第二，在聚類結束后利用臨時約束信息對聚類結果進行了修正，這樣能進一步提高聚類效果。

5 結束語

本文提出了基于約束投影的近鄰傳播聚類算法。該方法在整個聚類過程中多次使用了約束信息，能充分挖掘和利用約束信息指導聚類。文中兩次擴展了約束信息，邏輯擴展在保證約束信息正確的情況下增大了約束信息集，而臨時擴充符合數據點的空間特性，為數據集的投影和最后聚類修正提供保證。實驗結果表明，文中所提出的方法能很好地解決AP算法處理復雜數據集性能不佳的弊端，為半監督AP算法的研究提供了一種新思路。然而，本文在第二次擴展約束信息集的時候不能完全保證約束信息的正確性，這對于后來的聚類效果是有影響的，并且在進行降維時所選擇的降維空間數是一個經驗值，不能很好地從理論方面解釋怎樣的空間維數是最合適的。因此，如何結合數據集本身的特性來擴展約束信息并選取合適的降維空間，將是下一步的研究方向。

[1] Zhu Xiao-jin.Semi-supervised learning literature survey[R]. Computer Science TR 1530, Wl:University of Wisconsin:Department of Computer Sciences,2008.

[2] Si Wen-wu, Qian Jiang-tao.Semi-supervised clustering based on spectral clustering[J].Computer Applications, 2005,26(6):1347-1349.(in Chinese)

[3] Zhao Feng, Jiao Li-cheng, Liu Han-qiang,et al. Semi-supervised eigenvector selection for spectral clustering[J]. Pattern Recognition and Artificial Intelligence,2011,24(1):48-55.(in Chinese)

[4] Xing E P, Ng A Y, Michael I, et al. Distance metric learning with application to clustering with side-information[C]∥Advances in Neural Information Processing Systerm,2003:505-512.

[5] Klein D, Kamver S D. From instance-level constraints to space-level constraints:Making the most of prior knowledge in data clustering[C]∥Proc of ICML’02, 2002:307-314.

[6] Ding C,Li Tao,Peng Wei.On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing[J].Computational Statistics and Data Analysis,2008, 52(8):3913-3927.

[7] Bilenko M，Basu S，Mooney R J．Integrating constraints and metric learning in semi-supervised clustering[C]∥Proc of ICML’04, 2004:11．

[8] Basu S，Banerjee A，Mooney R J．Semi-supervised clustering by seeding[C]∥Proc of the 19th International Conference on Machine Learning, 2002:27-34．

[9] Frey B J，Dueck D．Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[10] Yuan Li-yong, Wang Ji-yi.An improved semi-supervised K-means clustering algorithm[J].Computer Engineering & Science,2011,33(6):138-143.(in Chinese)

[11] Xiao Yu, Yu Jian. Semi-supervised clustering based on affinity propagation algorithm[J].Journal of Software,2008,19(11):2803-2813.(in Chinese)

[12] An S, Liu W, Venkatesh S. Exploiting side information in locality preserving projection[C]∥Proc of Conference on Computer Vision and Pattern Recognition (CVPR), 2008:1-8.

附中文參考文獻：

[2] 司文武,錢江濤.一種基于譜聚類的半監督聚類方法[J].計算機應用,2005,26(6):1347-1349.

[3] 趙鳳,焦李成,劉漢強，等.半監督譜聚類特征向量選擇算法[J].模式識別與人工智能,2011,24(1):48-55.

[10] 袁利永,王基一.一種改進的半監督K-means聚類算法[J].計算機工程與科學,2011,33(6):138-143.

[11] 肖宇,于劍.基于近鄰傳播算法的半監督聚類[J].軟件學報,2008,19(11):2803-2813.

QIAN Xue-zhong,born in 1967,MS,associate professor,his research interests include database technology, data mining, and network security.

趙建芳(1988-),女,江蘇張家港人，碩士生，研究方向為數據挖掘。E-mail:Zhao_jian_fang@foxmail.com

ZHAO Jian-fang,born in 1988,MS candidate,her research interest includes data mining.

賈志偉(1988-),男,江蘇連云港人，碩士生，研究方向為數據挖掘。E-mail:441065471@qq.com

JIA Zhi-wei,born in 1988,MS candidate,his research interest includes data mining.

Constraint projection based affinity propagation

QIAN Xue-zhong1，ZHAO Jian-fang1，JIA Zhi-wei2
(1.School of Internet of Things Engineering,Jiangnan University,Wuxi 214122;2.Chengdu University of Information Technology,Chengdu 610225,China)

A clustering algorithm, named constraint projection based affinity propagation (AP), is proposed. The AP algorithm conducts clustering based on similarity matrix, outperforming many traditional clustering algorithms. However, for those datasets with complex structure, the AP algorithm cannot always achieve the ideal results. Firstly, constraints are enlarged. Secondly, the enlarged constrains are used in getting the projection matrix. At last, the clustering result is updated by the enlarged constraints in the space with lower dimension. The result shows that, compared with the comparison algorithms, the proposal is better in both time performance and clustering results.

semi-supervised;clustering;constraints;projection;affinity propagation

2012-09-04;

2012-12-21

國家自然科學基金資助項目(61103129)；江蘇省科技支撐計劃資助項目(BE2009009)

1007-130X(2014)03-0524-06

TP274

A

10.3969/j.issn.1007-130X.2014.03.026

錢雪忠(1967-),男,江蘇無錫人，碩士，副教授，研究方向為數據庫技術、數據挖掘和網絡安全。E-mail:qxzvb@163.com

通信地址：214122 江蘇省無錫市江南大學物聯網工程學院

Address:School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,Jiangsu,P.R.China