重疊聚類(lèi)和屬性圖聚類(lèi)算法研究.pdf

1、現(xiàn)實(shí)生活中有大量事物可以建模成圖數(shù)據(jù)結(jié)構(gòu),因此,對(duì)于圖數(shù)據(jù)的數(shù)據(jù)挖掘有很廣泛的應(yīng)用領(lǐng)域和很重要的應(yīng)用價(jià)值。聚類(lèi)是數(shù)據(jù)挖掘中十分重要的方法之一,因此,圖數(shù)據(jù)中的聚類(lèi)問(wèn)題被人們很自然地提出,并已做了大量深入的研究工作。本文針對(duì)圖聚類(lèi)問(wèn)題中的兩個(gè)問(wèn)題,提出相應(yīng)的改進(jìn)算法:
　　傳統(tǒng)的聚類(lèi)要求不同的分組之間不能有公共的重疊部分,而這顯然與現(xiàn)實(shí)情況相沖突。以人際關(guān)系網(wǎng)絡(luò)為例,每個(gè)人都屬于不同的社交圈子,比如同事圈子、朋友圈子等,聚類(lèi)時(shí)顯然不

2、能強(qiáng)行將這個(gè)人劃分入唯一的一個(gè)圈子,因此需要圈子之間允許重疊。對(duì)此,有人提出了圖的重疊聚類(lèi)算法。基于邊聚類(lèi)的方法可以很好的解決重疊聚類(lèi)的問(wèn)題,該方法將邊作為聚類(lèi)對(duì)象,對(duì)邊進(jìn)行聚類(lèi),結(jié)果再轉(zhuǎn)化為基于節(jié)點(diǎn)的聚類(lèi)。在該算法的思想上,本文提出將邊轉(zhuǎn)化為重邊,利用圖的重疊聚類(lèi)算法對(duì)邊進(jìn)行聚類(lèi),目的在于得到更精確的聚類(lèi)結(jié)構(gòu)。所提出的算法在真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)表明,該算法可以得到很好的聚類(lèi)結(jié)果。
　　更一般的圖數(shù)據(jù)結(jié)構(gòu)不僅包括拓?fù)浣Y(jié)構(gòu)信息,而且節(jié)點(diǎn)

3、(和/或邊)可以攜帶用于描述自身性質(zhì)的屬性標(biāo)簽,這種更一般形式的圖稱為屬性圖。由于從真實(shí)生活中提取到的數(shù)據(jù)可以組織成屬性圖的形式,這種對(duì)事物的表達(dá)更加精確,因此屬性圖的應(yīng)用十分廣泛,在屬性圖上進(jìn)行數(shù)據(jù)挖掘可以得到更精確或更有趣的結(jié)果。本文針對(duì)屬性圖的聚類(lèi)問(wèn)題,利用節(jié)點(diǎn)的屬性信息為每條邊賦權(quán),提出賦權(quán)過(guò)程的具體算法,并利用已有的帶權(quán)圖聚類(lèi)算法對(duì)屬性圖進(jìn)行聚類(lèi)。算法中采用EM算法對(duì)屬性的權(quán)重進(jìn)行學(xué)習(xí),得到屬性權(quán)重矩陣。實(shí)驗(yàn)表明,該算法優(yōu)于當(dāng)