錢雪忠,趙建芳,賈志偉

(1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122;2.成都信息工程學(xué)院,四川 成都 610225)

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

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

(1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122;2.成都信息工程學(xué)院,四川 成都 610225)

提出了一種基于約束投影的近鄰傳播AP聚類算法。AP算法是在數(shù)據(jù)點(diǎn)相似度矩陣的基礎(chǔ)上進(jìn)行聚類的，很多傳統(tǒng)的聚類方法都無法與其相媲美。但是，對于結(jié)構(gòu)復(fù)雜的數(shù)據(jù)，AP算法往往得不到理想的結(jié)果。文中算法先對約束信息進(jìn)行擴(kuò)展，然后利用擴(kuò)展的約束信息指導(dǎo)投影矩陣的獲取，在低維空間中，利用約束信息對聚類結(jié)果進(jìn)行修正。實驗表明，文中算法與對比算法相比，時間性能更優(yōu)，聚類效果更佳。

半監(jiān)督；聚類；約束信息；投影；近鄰傳播

1 引言

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

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

2 AP算法及SAP算法

2.1 AP算法

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

AP算法引入兩個重要的信息量參數(shù)，分別為吸引度R(Responsibility)和歸屬度A(Availability)。R(i,k)從點(diǎn)xi指向xk，表示xk適合作為數(shù)據(jù)點(diǎn)xi的聚類中心程度。A(i,k)是從點(diǎn)xk指向xi，表示點(diǎn)xi選擇點(diǎn)xk作為其聚類中心的程度。AP算法的迭代過程是不斷更新每一個點(diǎn)的吸引度和歸屬度的過程，迭代過程直到產(chǎn)生高質(zhì)量的Exemplar結(jié)束。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進(jìn)行加權(quán)更新，更新公式如下：

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

(4)

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

(5)

其中，lam∈[0.5,1)。

2.2SAP算法

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

若(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算法對相似度矩陣的對稱性沒有要求，能在很短的時間內(nèi)得到K-means算法花費(fèi)很長時間才能得到的聚類效果，但是對于結(jié)構(gòu)復(fù)雜的數(shù)據(jù)集，其處理時間很長，且不能得到理想的聚類結(jié)果。SAP算法在AP算法的基礎(chǔ)上加入先驗信息，在一定程度上提高了AP算法的性能，但是其時間性能卻還是有待改善。據(jù)此提出了基于約束投影的近鄰傳播聚類算法。

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

3.1 約束投影

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

數(shù)據(jù)投影是根據(jù)某一準(zhǔn)則，將高維數(shù)據(jù)變換到有意義的低維表示[12]。在利用約束信息指導(dǎo)投影矩陣的獲取時，除了考慮根據(jù)約束傳播原理更新的約束集M和C以外，還需考慮以下問題：在一個很小的局部區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)應(yīng)該具有相似的特性，在高維空間中離正約束對最近的一對數(shù)據(jù)點(diǎn)，如果不屬于負(fù)約束集，在低維空間中應(yīng)盡量使其靠近。同理可得，離負(fù)約束對最近的一對數(shù)據(jù)點(diǎn)，如果不屬于正約束集，在低維空間中應(yīng)盡量使其遠(yuǎn)離。為了解決上述問題，我們分別建立臨時正約束集M′和臨時負(fù)約束集C′，對M集和C集做臨時的擴(kuò)充。這里所說的臨時擴(kuò)充是指這一步擴(kuò)充所得的約束信息僅用于指導(dǎo)投影矩陣的獲取，而在低維空間中進(jìn)行聚類時，使用的監(jiān)督信息是根據(jù)約束傳播原理所得到的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)表示數(shù)據(jù)點(diǎn)xi和數(shù)據(jù)點(diǎn)xj之間的歐氏距離，M(xi)、C(xi)分別表示與數(shù)據(jù)點(diǎn)xi有正約束關(guān)系和負(fù)約束關(guān)系的所有數(shù)據(jù)點(diǎn)的集合。

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

(10)

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

為求得投影矩陣，構(gòu)造目標(biāo)函數(shù)f(W)：

(11)

展開整理得：

WT(XDXT-XGXT)W=

WTX(D-G)XTW

(12)

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

3.2 算法執(zhí)行過程

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

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

(2)計算臨時約束集M′和C′，并根據(jù)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)}。根據(jù)gi,j的計算方法量化M′和C′中的信息。

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

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

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

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

(7)在調(diào)整后的相似性矩陣上迭代計算R(i,k)和A(i,k)，直到產(chǎn)生最優(yōu)Exemplar或者達(dá)到最大迭代次數(shù)為止。

(8)利用臨時約束信息對聚類結(jié)果進(jìn)行調(diào)整。

4 實驗及結(jié)果

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

Table 1 Information of dataset UCI

約束信息通常是由鄰域?qū)＜覙?biāo)記產(chǎn)生的，實驗中，為了避免人為標(biāo)記帶來的偶然性，我們對數(shù)據(jù)點(diǎn)進(jìn)行編號，每次隨機(jī)產(chǎn)生一組數(shù)字，如果這組數(shù)字對應(yīng)的編號所代表的數(shù)據(jù)點(diǎn)在同一個類中，則將這兩個數(shù)據(jù)點(diǎn)組成一組正約束對加入正約束集中，否則組成負(fù)約束對加入負(fù)約束集中。實驗輸出的結(jié)果是100次實驗的平均值。在這100次實驗中，每次實驗都隨機(jī)產(chǎn)生新的約束對。實驗利用監(jiān)督信息，將三組數(shù)據(jù)集都降到了三維空間。實驗所用的機(jī)器為Intel Core2 Duo CPU，2.0 GHz，內(nèi)存為1.00 GB。

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

Table 2 Time of AP

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

Table 3 Contrast of time between SAP and CBPAP

Table 4 Output of average CRI

除了上述驗證算法聚類效果的實驗以外，本文還采用CRI指標(biāo)對兩類半監(jiān)督的AP算法的聚類效果進(jìn)行對比。

CRI指標(biāo)被視為常用的半監(jiān)督聚類評價指標(biāo)[5]，其定義如下：

(13)

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

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

5 結(jié)束語

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

[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.

附中文參考文獻(xiàn)：

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

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

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

[11] 肖宇,于劍.基于近鄰傳播算法的半監(jiān)督聚類[J].軟件學(xué)報,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-),女,江蘇張家港人，碩士生，研究方向為數(shù)據(jù)挖掘。E-mail:Zhao_jian_fang@foxmail.com

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

賈志偉(1988-),男,江蘇連云港人，碩士生，研究方向為數(shù)據(jù)挖掘。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

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

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

TP274

A

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

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

通信地址：214122 江蘇省無錫市江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院

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