于 悅,盧 罡,郭俊霞

(北京化工大學(xué) 信息科學(xué)與工程學(xué)院,北京 100029)

1 引言

如今,隨著大量網(wǎng)絡(luò)應(yīng)用平臺(tái)的產(chǎn)生,用戶(hù)會(huì)根據(jù)自身的不同特點(diǎn)(社會(huì)角色)來(lái)選擇不同的應(yīng)用平臺(tái)并與他人進(jìn)行交互和信息資源的共享,所以,同一個(gè)用戶(hù)可以在多種平臺(tái)上處于不同的關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)中,這樣的網(wǎng)絡(luò)結(jié)構(gòu)也被稱(chēng)為多維關(guān)系網(wǎng)絡(luò),每個(gè)維度代表一種不同的關(guān)系視角[1],例如,不同學(xué)術(shù)期刊論文可以構(gòu)建不同的作者協(xié)作網(wǎng)絡(luò),在某些期刊中兩個(gè)同社團(tuán)的作者(研究領(lǐng)域相同),在其他期刊中也認(rèn)為應(yīng)該在同一個(gè)社團(tuán);又如,兩個(gè)用戶(hù)在某些社交平臺(tái)是好友關(guān)系,在其他社交平臺(tái)中則認(rèn)為這兩個(gè)用戶(hù)是好友的可能性很高,所以利用不同關(guān)系網(wǎng)絡(luò)的信息來(lái)發(fā)覺(jué)某個(gè)應(yīng)用中隱藏的社團(tuán)結(jié)構(gòu)并進(jìn)行有利的信息整合是現(xiàn)代信息挖掘的主要方向.

在傳統(tǒng)的單視角社區(qū)發(fā)現(xiàn)算法中,我們可以將人物關(guān)系整合到圖的拓?fù)浣Y(jié)構(gòu)中,用戶(hù)代表圖中的節(jié)點(diǎn),邊表示用戶(hù)間的交互關(guān)系和關(guān)聯(lián)屬性,社區(qū)發(fā)現(xiàn)的過(guò)程被看作是圖聚類(lèi)分析的過(guò)程,因此,基于圖劃分的單視角聚類(lèi)算法被相繼提出,如K均值(K-means)算法[2]、譜聚類(lèi)算法(Spectral Clustering)算法[3]、規(guī)范割集準(zhǔn)則(Ncut)算法[4]、對(duì)稱(chēng)非負(fù)矩陣因式分解(symNMF)算法[5,6]等.這些算法有明顯的兩個(gè)特點(diǎn)[7]:(1)切割式聚類(lèi),即節(jié)點(diǎn)被聚類(lèi)到?jīng)]有交集的聚簇中;(2)簡(jiǎn)單的圖形構(gòu)造,即兩個(gè)節(jié)點(diǎn)之間最多只有一條代表關(guān)系的連邊.然而在很多實(shí)際應(yīng)用中,表示社區(qū)結(jié)構(gòu)的圖數(shù)據(jù)往往來(lái)自于不同的視角(領(lǐng)域),單視角的劃分和構(gòu)造難以綜合考慮多種因素.例如,在現(xiàn)實(shí)生活中,企業(yè)需要尋求某個(gè)研究領(lǐng)域中的專(zhuān)家.根據(jù)論文作者之間的引用及合作關(guān)系可以得到社團(tuán)劃分結(jié)果為R1=({A,B,C,D,G,K},{L,M,N,O,P,Q},{P});同時(shí),根據(jù)項(xiàng)目合作和協(xié)助關(guān)系的社團(tuán)劃分結(jié)果為R2=({A,C,D,E,F,P},{L,M,N,O,R},{Q}).可以看出,第一個(gè)視角不能將P進(jìn)行有效的劃分,同理,第二個(gè)視角不能將Q進(jìn)行有效劃分,所以,這種劃分結(jié)果考慮的用戶(hù)關(guān)系較為單一,很難有效解決這種多維關(guān)系網(wǎng)絡(luò)的問(wèn)題.

針對(duì)以上這種同源異構(gòu)的數(shù)據(jù),近年來(lái)基于多視角聚類(lèi)方法比較受關(guān)注,文獻(xiàn)[8,9]的算法都是圖切割原理結(jié)合不同的視角關(guān)系來(lái)定義的,它們根據(jù)切割聚簇內(nèi)節(jié)點(diǎn)代價(jià)大、切割聚間節(jié)點(diǎn)代價(jià)小的原理,提出相應(yīng)的目標(biāo)函數(shù)公式,將離散問(wèn)題轉(zhuǎn)換為連續(xù)問(wèn)題,對(duì)其進(jìn)行優(yōu)化,求出函數(shù)收斂后所對(duì)應(yīng)的聚類(lèi)結(jié)果.這些算法的關(guān)鍵在于收斂條件的確定,而極值點(diǎn)和最值點(diǎn)不易確定.文獻(xiàn)[10]的CCA算法,是用其它視角的聚類(lèi)結(jié)果來(lái)更新本視角下節(jié)點(diǎn)的初始狀態(tài),用聯(lián)合訓(xùn)練的方法,通過(guò)對(duì)拉普拉斯矩陣不斷的更新迭代來(lái)改善聚類(lèi)精度.文獻(xiàn)[11]的CSC算法是對(duì)CCA的改進(jìn),利用拉普拉斯矩陣的特征向量對(duì)相似矩陣進(jìn)行迭代更新,使矩陣中同屬一個(gè)聚簇的節(jié)點(diǎn)權(quán)值相近,簇間節(jié)點(diǎn)的權(quán)值不同,最后串聯(lián)個(gè)視角的特征向量進(jìn)行融合,并用K-means算法聚類(lèi)結(jié)果.文獻(xiàn)[12]的SCSC算法針對(duì)CSC算法進(jìn)行改進(jìn),利用選擇投票的方式,對(duì)強(qiáng)視角(節(jié)點(diǎn)信息完全)和弱視角(顯示部分節(jié)點(diǎn)信息)做不同的選擇處理,最終實(shí)現(xiàn)多視角聚類(lèi).但該處理方法較簡(jiǎn)單,主要針對(duì)多稀疏實(shí)例集的稀疏關(guān)系聚類(lèi),精度提升較差.文獻(xiàn)[12,13]都是使用正則化方法,使用基于拉普拉斯特征向量來(lái)調(diào)節(jié)缺失函數(shù),這樣由每個(gè)拉普拉斯矩陣得出的聚簇結(jié)果在所有的視角中是一致的.這些算法假設(shè)前提為不同視角下的節(jié)點(diǎn)分布是相同的,假設(shè)條件比較苛刻.文獻(xiàn)[14]提出的CGC算法利用節(jié)點(diǎn)之間的關(guān)聯(lián)矩陣關(guān)系,對(duì)視角中不同的實(shí)例集進(jìn)行一對(duì)多和多對(duì)多的處理,實(shí)現(xiàn)最后的聚類(lèi),然而該算法中選取關(guān)聯(lián)關(guān)系困難,沒(méi)有明確的公式定義.

傳統(tǒng)多視角聚類(lèi)都有兩個(gè)限制:(1)每個(gè)視角下的節(jié)點(diǎn)關(guān)系不同,但每個(gè)視角要求使用相同的節(jié)點(diǎn),且每個(gè)視角中的節(jié)點(diǎn)聚簇個(gè)數(shù)要求相同.(2)每個(gè)視角基本上必須擁有圖結(jié)構(gòu)中的充分劃分信息.以上限制條件,導(dǎo)致這些方法往往不能反映真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu),所以在實(shí)際應(yīng)用中的適應(yīng)性比較差.

本文針對(duì)傳統(tǒng)的單視角社區(qū)發(fā)現(xiàn)算法的局限性和現(xiàn)有的多關(guān)系社區(qū)發(fā)現(xiàn)算法的不足提出一個(gè)協(xié)同選擇聚類(lèi)的多視角社區(qū)發(fā)現(xiàn)算法,并從多個(gè)方面對(duì)算法進(jìn)行改進(jìn),本文主要貢獻(xiàn)點(diǎn)包括以下3個(gè)方面.

(1)使用局部協(xié)同訓(xùn)練方法解決大多數(shù)多視角聚類(lèi)算法中實(shí)例和聚簇條件的限制,允許不同視角中選擇不同數(shù)量的節(jié)點(diǎn),每個(gè)視角的劃分?jǐn)?shù)量也可以不同.

(2)解決傳統(tǒng)多視角算法中其他視角的決定性修正而導(dǎo)致聚類(lèi)不準(zhǔn)確的問(wèn)題.本文只對(duì)各個(gè)視角中可識(shí)別節(jié)點(diǎn)(在其他視角中有關(guān)系)的聚類(lèi)結(jié)果進(jìn)行強(qiáng)促進(jìn)處理和弱促進(jìn)處理,迭代更新每個(gè)視角中識(shí)別節(jié)點(diǎn)關(guān)系的相似矩陣,促進(jìn)各視角中部分結(jié)構(gòu)的融合.

(3)將局部學(xué)習(xí)和聯(lián)合訓(xùn)練相結(jié)合,利用每個(gè)視角中的不可識(shí)別節(jié)點(diǎn)(在其他視角中無(wú)關(guān)系)的鄰居節(jié)點(diǎn)劃分情況,來(lái)得到非標(biāo)記節(jié)點(diǎn)的最終歸屬.

本文的結(jié)構(gòu)分為以下幾個(gè)章節(jié):第1節(jié)是對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)的介紹和新算法的提出;第2節(jié)提出多視角局部協(xié)同選擇聚類(lèi)算法(co-MLSC)并介紹其原理;第3節(jié)介紹該算法中的核心公式;最后,通過(guò)實(shí)驗(yàn),驗(yàn)證算法的有效性.

2 局部協(xié)同選擇多視角聚類(lèi)算法

2.1 譜聚類(lèi)

譜聚類(lèi)[3](CS)方法是利用拉普拉斯矩陣特征向量的性質(zhì)來(lái)挖掘社團(tuán)方法,其定義為:設(shè)G= (V(G),E(G))是網(wǎng)絡(luò)圖結(jié)構(gòu),其中節(jié)點(diǎn)集為V(G)= {v1,v2,...vm},邊集為E(G).譜聚類(lèi)的算法流程如算法1所示.

算法1.譜聚類(lèi)(CS)輸入:相似矩陣S∈Rm×m,聚類(lèi)個(gè)數(shù)k∈N輸出:該相似矩陣所代表的點(diǎn)的聚類(lèi)結(jié)果C∑1.計(jì)算S的對(duì)角矩陣2.計(jì)算拉普拉斯矩陣L = D–S?3.計(jì)算L的前k個(gè)特征向量,4.正規(guī)化U矩陣的每一行5.樣例j屬于聚簇c當(dāng)且僅當(dāng)通過(guò)K-means算法得到U的j行屬于聚簇c6.計(jì)算并返回結(jié)果矩陣

聚類(lèi)結(jié)果矩陣C表示聚類(lèi)結(jié)果矩陣,其中第i行j列的元素表示視角中實(shí)體i與實(shí)體j是否在同一個(gè)聚簇中,在則為1,反之則為0.

2.2 co-MLSC算法

本節(jié)設(shè)計(jì)一種多視角協(xié)同選擇的聚類(lèi)算法,該算法是基于多視角譜聚類(lèi)算法的基礎(chǔ)上提出的.針對(duì)多視角聚類(lèi)算法應(yīng)用到實(shí)際網(wǎng)絡(luò)關(guān)系中的限制問(wèn)題,該算法將每個(gè)視角中的實(shí)例分為兩種,當(dāng)某個(gè)視角中的兩個(gè)節(jié)點(diǎn)在其他視角中存在并屬于同一社團(tuán)結(jié)構(gòu),則這兩個(gè)節(jié)點(diǎn)在該視角中為可識(shí)別節(jié)點(diǎn),反之,如果某一個(gè)節(jié)點(diǎn)在其他視角中不存在或存在但沒(méi)有對(duì)應(yīng)的關(guān)系,則節(jié)點(diǎn)在該視角中為不可識(shí)別節(jié)點(diǎn).所以,co-MLSC對(duì)實(shí)例的處理也分為兩種方法,其中包括多視角中可識(shí)別節(jié)點(diǎn)的強(qiáng)弱關(guān)系促進(jìn)方法和各個(gè)單視角中不可識(shí)別節(jié)點(diǎn)的劃分方法,其流程如算法2所示.

算法2.協(xié)同式多視角選擇聚類(lèi)算法(co-MLSC)輸入:各個(gè)view的相似度矩陣,各個(gè)view中聚類(lèi)個(gè)數(shù).輸出:最終聚類(lèi)結(jié)果.1.Initialize:.2.用譜聚類(lèi)CS算法得到各視角初始聚類(lèi)結(jié)果矩陣,j∈d,3.for i = 1 to iter do //iter表示迭代次數(shù)4. for π = 0 to d–1 do 5. ;//構(gòu)建選擇調(diào)節(jié)矩陣6. ;//構(gòu)建局部?jī)?yōu)化矩陣7. ;//修正相似矩陣8. 對(duì)更新后的相似矩陣S使用譜聚類(lèi)算法;9. //修正結(jié)果矩陣10. 更新π視角聚類(lèi)中心;11. end for 12.end for 13.return Call;

3 核心矩陣的構(gòu)建

這里我們提出針對(duì)兩種實(shí)例的處理方法,其中包括選擇調(diào)節(jié)矩陣的構(gòu)建和局部?jī)?yōu)化矩陣的構(gòu)建,選擇調(diào)節(jié)矩陣主要是利用多個(gè)視角中可識(shí)別節(jié)點(diǎn)協(xié)同訓(xùn)練的作用,對(duì)可識(shí)別節(jié)點(diǎn)間相似度權(quán)值進(jìn)行強(qiáng)促進(jìn)或弱促進(jìn)處理,其目的在于集成各視角中由可識(shí)別節(jié)點(diǎn)組成的部分社團(tuán)結(jié)構(gòu).局部?jī)?yōu)化矩陣則是對(duì)各視角中不可識(shí)別節(jié)點(diǎn)進(jìn)行聚類(lèi),這里利用機(jī)器學(xué)習(xí)中的核嶺回歸分析方法,將每個(gè)不可識(shí)別節(jié)點(diǎn)的鄰居節(jié)點(diǎn)社團(tuán)劃分結(jié)果做為訓(xùn)練集,以估計(jì)不可識(shí)別節(jié)點(diǎn)最終的社團(tuán)歸屬并對(duì)最終社團(tuán)結(jié)構(gòu)進(jìn)行完善.

3.1 選擇調(diào)節(jié)矩陣

在這里我們要定義可識(shí)別節(jié)點(diǎn)對(duì)視角π進(jìn)行更新的調(diào)節(jié)矩陣,利用共識(shí)矩陣(co-association)原理,計(jì)算各視角中可識(shí)別節(jié)點(diǎn)的同簇劃分概率,通過(guò)概率大小值來(lái)調(diào)節(jié)視角π的原始相似度矩陣,構(gòu)建方法如公式(1)所示:

公式(1)中,不同于傳統(tǒng)的共識(shí)矩陣構(gòu)建方法,為了解決了其他視角的過(guò)度調(diào)整問(wèn)題,使其計(jì)算同簇劃分概率中分子的比重不同,如果兩個(gè)同社區(qū)的實(shí)例在其他多個(gè)視角中也在同一個(gè)社區(qū),則我們將這種促進(jìn)作用放大;如果兩個(gè)非同社區(qū)的實(shí)例在其他多個(gè)視角中屬于同一個(gè)社區(qū),雖同樣有促進(jìn)作用,其分子影響比重較小.所以,上式中可以認(rèn)為選擇調(diào)節(jié)矩陣是促進(jìn)關(guān)系結(jié)構(gòu)的過(guò)程,不存在其他視角的抑制作用而導(dǎo)致的過(guò)度性調(diào)整,只有當(dāng)兩個(gè)實(shí)例在所有視角中都屬于同一個(gè)社團(tuán)結(jié)構(gòu)時(shí),式中的同簇劃分概率為1,影響值2.7(e1),屬于強(qiáng)促進(jìn),其他多種情況均為弱促進(jìn).

公式(2)表示π視角與其他視角可識(shí)別節(jié)點(diǎn)關(guān)系聚類(lèi)情況的整合.例如,節(jié)點(diǎn)i和節(jié)點(diǎn)j在π視角中同一個(gè)社區(qū),并且在其他h(h＜d)個(gè)視角中也在同一個(gè)社區(qū),那么節(jié)點(diǎn)i和節(jié)點(diǎn)j在同一個(gè)社區(qū)的概率會(huì)變大,促進(jìn)作用會(huì)大幅度增強(qiáng).

公式(3)表示其他視角中聚類(lèi)效果明顯的實(shí)例對(duì),對(duì)視角π是有促進(jìn)作用的.如果節(jié)點(diǎn)i和節(jié)點(diǎn)j在其他大多數(shù)視角中屬于同一個(gè)社區(qū)結(jié)構(gòu),那么節(jié)點(diǎn)i和節(jié)點(diǎn)j在同一個(gè)社區(qū)的概率也會(huì)變大,促進(jìn)作用會(huì)小幅度增強(qiáng).

下面用3個(gè)實(shí)例的關(guān)系來(lái)展示該更新過(guò)程.假設(shè)我們得到3個(gè)視角關(guān)系的聚類(lèi)結(jié)果矩陣,如圖1所示.其中3個(gè)視角的實(shí)例集聚類(lèi)結(jié)果分別為{(a,b)(c)(d,e)},{(a,b,d)(c)(m)(e,t)},{(a,b,c)(m)(d,e)}.

圖1 3個(gè)視角的聚類(lèi)結(jié)果矩陣

圖2可以看出,由于3個(gè)視角的共同影響,實(shí)例A與實(shí)例B在同一個(gè)社區(qū)的可能性比較大,在3個(gè)視角中都是強(qiáng)促進(jìn)關(guān)系.在第1個(gè)視角中,盡管實(shí)例c和實(shí)例d沒(méi)有與實(shí)例a,b劃分到一個(gè)簇中,但在其他視角的作用下對(duì)其相似度關(guān)系會(huì)起到弱促進(jìn)的作用,同理e和d;在視角2中,m實(shí)例在視角3中也出現(xiàn)了但其聚類(lèi)結(jié)構(gòu)中沒(méi)有和其他節(jié)點(diǎn)有任何促進(jìn)關(guān)系,所以我們也可以將其當(dāng)作不可識(shí)別節(jié)點(diǎn)處理,參加不可識(shí)別節(jié)點(diǎn)局部?jī)?yōu)化矩陣的構(gòu)建,這里t為不可識(shí)別節(jié)點(diǎn);在視角3中實(shí)例c在本視角中和a,b實(shí)例同簇,在其他視角中無(wú)促進(jìn)作用,所以在該視角中仍然作不可識(shí)別節(jié)點(diǎn)處理來(lái)避免其劃分不準(zhǔn)確的問(wèn)題,如果節(jié)點(diǎn)c與節(jié)點(diǎn)a和節(jié)點(diǎn)b的關(guān)聯(lián)度大則在下節(jié)優(yōu)化矩陣構(gòu)建中仍然為同簇.

圖2 3個(gè)視角的選擇調(diào)節(jié)矩陣

3.2 局部?jī)?yōu)化矩陣

局部?jī)?yōu)化矩陣的構(gòu)建是利用局部學(xué)習(xí)和聯(lián)合訓(xùn)練相結(jié)合的方法,應(yīng)用監(jiān)督學(xué)習(xí)的思想來(lái)解決無(wú)監(jiān)督學(xué)習(xí)中的聚類(lèi)問(wèn)題.我們將每個(gè)視角中無(wú)法通過(guò)其他視角進(jìn)行聯(lián)合聚類(lèi)的節(jié)點(diǎn)集稱(chēng)為不可識(shí)別節(jié)點(diǎn)集,那么局部?jī)?yōu)化矩陣構(gòu)建的基本原理,就是基于核嶺回歸函數(shù)[15],利用節(jié)點(diǎn)的鄰居節(jié)點(diǎn)來(lái)估計(jì)不可識(shí)別節(jié)點(diǎn)集的劃分.通過(guò)提出優(yōu)化函數(shù)的方式來(lái)得到不可識(shí)別節(jié)點(diǎn)集的最好的聚類(lèi)結(jié)果如公式(4)所示:

其中,n表示不可識(shí)別節(jié)點(diǎn)個(gè)數(shù),c表示聚簇個(gè)數(shù),表示節(jié)點(diǎn)i在l聚簇中的標(biāo)簽值,這里Fn×c為標(biāo)準(zhǔn)劃分矩陣(FTF=I),公式中表示核向量機(jī)的輸出函數(shù)[16],利用核函數(shù)的監(jiān)督方法,訓(xùn)練節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)標(biāo)簽集,得到其在聚簇l下的估測(cè)劃分值.其中的計(jì)算如公式(5)所示:

其中K(xi,xj)是徑向基核函數(shù),這里xi為核函數(shù)中心,Ni表示xi的鄰居節(jié)點(diǎn)集,β為回歸參數(shù).

3.2.1 利用核嶺回歸計(jì)算F

我們將求解公式(4)的問(wèn)題轉(zhuǎn)換成求解公式(6)的問(wèn)題:

其中,Ki為xi鄰居節(jié)點(diǎn)集的相似矩陣,表示向量這里利用核嶺回歸(KRR)算法求得公式(6)中回歸參數(shù)為帶入公式(5)得公式(7):

3.2.2 獲得最終局部?jī)?yōu)化矩陣L

根據(jù)文獻(xiàn)[17,18]中的聚類(lèi)算法,使用(PM)P表示聚類(lèi)劃分結(jié)果,其中如果表示xi在l聚簇中且上文中我們先使用標(biāo)準(zhǔn)劃分矩陣(PM)F表示劃分結(jié)果,其中F的初始定義為這里通過(guò)公式(10)可得到劃分矩陣P.

上式中I是單位矩陣,根據(jù)F矩陣可以很容易的得到非標(biāo)記節(jié)點(diǎn)的劃分L矩陣如公式(11):

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本文我們主要使用來(lái)自于UCI數(shù)據(jù)庫(kù)的Iris和Wine數(shù)據(jù)集和DBLP數(shù)據(jù)集進(jìn)行測(cè)試實(shí)驗(yàn).Iris數(shù)據(jù)集包含150個(gè)鳶尾花實(shí)例樣本,每個(gè)實(shí)例包含4個(gè)屬性(花瓣長(zhǎng)度,花瓣寬度,葉子長(zhǎng)度,葉子寬度)進(jìn)行描述,Wine數(shù)據(jù)集與Iris數(shù)據(jù)集基本類(lèi)似,包含178個(gè)葡萄酒樣本,每個(gè)實(shí)例有13個(gè)屬性信息(化學(xué)分析指標(biāo))描述,其中如表1所示,實(shí)驗(yàn)中,隨機(jī)選取幾種屬性構(gòu)成一個(gè)多視角結(jié)構(gòu),節(jié)點(diǎn)為實(shí)例向量,邊的權(quán)值表示各實(shí)例間的相似度值,聚類(lèi)結(jié)果將數(shù)據(jù)集分配到各自類(lèi)別中.

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

DBLP數(shù)據(jù)集我們提取了與數(shù)據(jù)庫(kù)方向相關(guān)的 4個(gè)會(huì)議(SIGMOD,VLDB,ICDE,SIGKDD)的作者及論文,作者總數(shù)為9628,論文總數(shù)為10175.每個(gè)會(huì)議形成一個(gè)社會(huì)網(wǎng)絡(luò),節(jié)點(diǎn)為作者,邊表示作者間協(xié)作關(guān)系.最終形成的每個(gè)社區(qū)將代表具有相似研究興趣的課題小組.如表2所示.

表2 DBLP數(shù)據(jù)集

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

規(guī)范化互信息(Nomalized Mutual Information,NMI)[19]用來(lái)度量網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)與經(jīng)過(guò)算法所得到的聚簇結(jié)構(gòu)的相似性.假定兩個(gè)集合向量X和Y,NMI的定義如公式(9)所示,NMI的取值為0～1之間,取值越大(接近1時(shí)),表示聚類(lèi)結(jié)果越精確.

模塊度評(píng)價(jià)方法[20]是一種基于內(nèi)部標(biāo)準(zhǔn)的聚類(lèi)效果衡量指標(biāo),一般用于沒(méi)有已知的聚簇結(jié)果對(duì)比時(shí)衡量聚類(lèi)效果的優(yōu)劣.模塊化是指網(wǎng)絡(luò)中連接社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的邊所占的比例和另一個(gè)隨機(jī)網(wǎng)絡(luò)中連接社群結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的邊所占比例的期望值之差.

模塊度的計(jì)算如公式(13)所示,取值范圍在0到1之間,并且值越接近1表示簇內(nèi)越緊密而簇間越分離.

4.3 性能評(píng)估

實(shí)驗(yàn)1.本實(shí)驗(yàn)比較Wine數(shù)據(jù)集和Iris數(shù)據(jù)集的多視角聚類(lèi)結(jié)果.Wine數(shù)據(jù)集中隨機(jī)選取4個(gè)屬性表示4個(gè)視角,同理,Iris數(shù)據(jù)集中選取3個(gè)視角,分別比較節(jié)點(diǎn)重合率為100%、75%、50%、25%條件下的協(xié)同聚類(lèi)結(jié)果,如圖3至圖10所示,從圖中可以看出,隨著各個(gè)視角中相同點(diǎn)個(gè)數(shù)的增加,社區(qū)發(fā)現(xiàn)的準(zhǔn)確率逐漸提升,當(dāng)重復(fù)率為100%時(shí),迭代過(guò)程就變成傳統(tǒng)的多視角聚類(lèi)算法.同時(shí),對(duì)于屬性條件區(qū)分能力差的視角,通過(guò)其他視角的相互影響,能夠有效提高該視角社區(qū)發(fā)現(xiàn)的準(zhǔn)確性.并且,隨著迭代次數(shù)的增加,每個(gè)視角中可識(shí)別節(jié)點(diǎn)的局部社區(qū)結(jié)構(gòu)得到集成處理,各個(gè)視角的聚類(lèi)結(jié)果都呈現(xiàn)收斂的狀態(tài).

圖3 Wine多視角協(xié)同選擇聚類(lèi)(重合率100%)

圖4 Wine多視角協(xié)同選擇聚類(lèi)(重合率75%)

圖5 Wine多視角協(xié)同選擇聚類(lèi)(重合率50%)

實(shí)驗(yàn)2.圖11和圖12是顯示在同樣覆蓋率的條件下,將3個(gè)視角的聚類(lèi)精度與2個(gè)視角聚類(lèi)精度進(jìn)行比較,可以看出3個(gè)視角的屬性關(guān)系比2個(gè)視角的屬性關(guān)系達(dá)到收斂狀態(tài)后精度更高,表明視角越多所包含的實(shí)例關(guān)系屬性越完全,聚類(lèi)效果越好.這里我們選取100%覆蓋率,是保證1視角和2視角的初始聚類(lèi)精度相同.

圖6 Wine多視角協(xié)同選擇聚類(lèi)(重合率25%)

圖7 Iris多視角協(xié)同選擇聚類(lèi)(重合率100%)

圖8 Iris多視角協(xié)同選擇聚類(lèi)(重合率75%)

圖9 Iris多視角協(xié)同選擇聚類(lèi)(重合率50%)

實(shí)驗(yàn)3.本實(shí)驗(yàn)將co-MLSC算法和CSC及CS算法算法進(jìn)行比較,各視角間節(jié)點(diǎn)集重合率為75%,從圖13中可以看出,當(dāng)將譜聚類(lèi)算法選取固定的最優(yōu)聚類(lèi)中心的時(shí)候,單視角的聚類(lèi)結(jié)果呈持平狀,說(shuō)明在單視角聚類(lèi)中CS算法聚類(lèi)結(jié)果已達(dá)到最優(yōu)狀態(tài).當(dāng)重合率為75%的時(shí),不能直接使用CSC算法,所以我們必須將各視角中的非識(shí)別節(jié)點(diǎn)添加到其他視角中并將相似度進(jìn)行填0處理.CSC的過(guò)度調(diào)整過(guò)程使低精度視角明顯影響高精度視角的走勢(shì).通過(guò)比較可以看出co-MLSC算法并沒(méi)有過(guò)度調(diào)整的缺點(diǎn).

圖10 Iris多視角協(xié)同選擇聚類(lèi)(重合率25%)

圖11 2個(gè)視角的Iris數(shù)據(jù)聚類(lèi)結(jié)果趨勢(shì)圖

圖12 3個(gè)視角的Iris數(shù)據(jù)聚類(lèi)結(jié)果趨勢(shì)圖

實(shí)驗(yàn)4.使用DBLP數(shù)據(jù)集構(gòu)建真實(shí)的基于作者協(xié)助關(guān)系的多維網(wǎng)絡(luò),由于數(shù)據(jù)的重復(fù)率普遍較低,所以我們進(jìn)行了一定的人工調(diào)節(jié),刪除合作者為1的論文,并對(duì)作者統(tǒng)一ID值,然而若將數(shù)據(jù)重復(fù)率控制太高的話(huà)每個(gè)領(lǐng)域內(nèi)數(shù)據(jù)數(shù)目將非常少,所以我們只能將數(shù)據(jù)集的重復(fù)率控制在 40%以下進(jìn)行變化,具體實(shí)驗(yàn)結(jié)果如圖14所示.這里我們僅取SIGMOD,VLDB,ICDE3個(gè)視圖關(guān)系結(jié)構(gòu),該實(shí)驗(yàn)表現(xiàn)了本文提出的局部協(xié)同聚類(lèi)算法在數(shù)據(jù)重復(fù)率較低的情況下有促進(jìn)其他視角的作用,并且也體現(xiàn)出該算法在真實(shí)構(gòu)建的多維網(wǎng)絡(luò)中有很好的適用性.

圖13 co-MLSC、CSC、CS算法的比較結(jié)果圖

圖14 DBLP數(shù)據(jù)集社團(tuán)發(fā)現(xiàn)精度走勢(shì)

5 總結(jié)

針對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)技術(shù)的不足,本文提出一種基于局部協(xié)同選擇聚類(lèi)的多視角社區(qū)發(fā)現(xiàn)算法co-MLSC,該算法充分考慮了各視角間聚類(lèi)的協(xié)同作用,利用聯(lián)合選擇的方法相互促進(jìn)來(lái)確定聚類(lèi)中心結(jié)構(gòu),同時(shí)也是對(duì)多個(gè)視角的聚類(lèi)中心進(jìn)行融合的過(guò)程,以此來(lái)提升社區(qū)發(fā)現(xiàn)的準(zhǔn)確性.另外,使用核嶺回歸估計(jì)的方法將每個(gè)視角下的不可識(shí)別節(jié)點(diǎn)進(jìn)行劃分,最后通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的可行性和有效性.

下一步工作將對(duì)迭代式協(xié)同聚類(lèi)算法的計(jì)算復(fù)雜度進(jìn)行分析,提出優(yōu)化策略來(lái)降低社區(qū)發(fā)現(xiàn)算法的執(zhí)行代價(jià).

1 Tang L,Wang XF,Liu H.Uncoverning groups via heterogeneous interaction analysis.Proceedings of the 9th IEEE International Conference on Data Mining.Miami Beach,FL,USA.2009.503–512.

2 Kanungo T,Mount DM,Netanyahu NS,et al.An efficient K-means clustering algorithm:Analysis and implementation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(7):881–892.[doi:10.1109/TPAMI.2002.1017616]

3 Ng AY,Jordan MI,Weiss Y.On spectral clustering:Analysis and an algorithm.Advances in Neural Information Processing Systems 14.2001.

4 Shi JB,Malik J.Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888–905.[doi:10.1109/34.868688]

5 Kuang D,Dingo C,Park H.Symmetric nonnegative matrix factorization for graph clustering.Proceedings of the 2012 SIAM International Conference on Data Mining.Anaheim,CA,USA.2012.106–117.

6 Xu W,Liu X,Gong YH.Document clustering based on nonnegative matrix factorization.Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Toronto,Canada.2003.267–273.

7 Strehl A,Ghosh J.Cluster ensembles-a knowledge reuse framework for combining multiple partitions.The Journal of Machine Learning Research,2003,(3):583–617.

8 Christoudias CM,Urtasun R,Darrell T.Multi-view learning in the presence of view disagreement.Proceedings of the 24th Conference on Uncertainty in Artificia lIntelligence .Helsinki,Finland.2008.

9 Muslea I,Minton S,Knoblock CA.Active +semi-supervised learning=robust multi-view learning.Proceedings of the 19th International Conference on Machine Learning.San Francisco,CA,USA.2002.435–442.

10 Chaudhuri K,Kakade SM,Livescu K,et al.Multi-view clustering via canonical correlation analysis.Proceedings of the 26th Annual International Conference on Machine Learning.Montreal,Quebec,Canada.2009.129–136.

11 Kumar A,Daumé H.A co-training approach for multi-view spectral clustering.Proceedings of the 28th International Conference on Machine Learning.Bellevue,WA,USA.2011.393–400.

12 Kumar A,Rai P,Daumé H III.Co-regularized multi-view spectral clustering.Proceedings of the 24th International Conference on Neural Information Processing Systems.Granada,Spain.2011.1413–1421.

13 Niu DL,Dy JG,Jordan MI.Multiple non-redundant spectral clustering views.Proceedings of the 27th International Conference on Machine Learning.Haifa,Israel.2010.

14 Cheng W,Zhang X,Guo ZS,et al.Flexible and robust coregularized multi-domain graph clustering.Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Chicago,IL,USA.2013.320–328.

15 Shawe-Taylor J,Cristianini N.Kernel Methods for Pattern Analysis.Cambridge,UK:Cambridge University Press,2004.

16 Schlkopf B,Smola AJ.Learning with Kernels:Support Vector Machines,Regularization,Optimization,and Beyond.Cambridge,MA:The MIT Press,2001.

17 Chan PK,Schlag MDF,Zien JY.Spectral k-way ratio-cut partitioning and clustering.IEEE Transactions on Computeraided Design of Integrated Circuits and Systems,1994,13(9):1088–1096.[doi:10.1109/43.310898]

18 Yu SX,Shi JB.Multiclass spectral clustering.Proceedings of the 9th IEEE International Conference on Computer Vision.Nice,France.2003.

19 Ng AY,Jordan MI,Weiss Y.On spectral clustering:Analysis and an algorithm.Advances in Neural Information Processing Systems.2002.849–856.

20 Newman MEJ,Girvan M.Finding and evaluating community structure in networks.Physical Review E,2004,69(2):026113.[doi:10.1103/PhysRevE.69.026113]