一種新的屬性圖重疊聚類挖掘算法

張昕堯　高宏

摘要： 屬性圖各節(jié)點附有的節(jié)點屬性標(biāo)簽，為節(jié)點提供了更加豐富的信息，在數(shù)據(jù)挖掘應(yīng)用，特別是數(shù)據(jù)聚類問題中如何有效利用這些豐富的信息，已經(jīng)成為開展此類研究的研究目的。不同于傳統(tǒng)圖聚類，屬性圖上的聚類要同時考慮圖的結(jié)構(gòu)信息和節(jié)點的屬性信息，因此如何平衡兩者之間的關(guān)系，這是屬性圖聚類主要關(guān)注所在。目前已提出的屬性圖聚類算法，部分算法的效率很高，然而聚類質(zhì)量較差，同時一些算法可以得到較好的聚類結(jié)構(gòu)，然而算法消耗大量的系統(tǒng)資源，效率也較低。這些算法均沒有考慮簇之間存在重疊的情況，這導(dǎo)致無法得到更高精度的聚類結(jié)構(gòu)。因而提出一種屬性圖上的重疊聚類挖掘算法，實驗表明，提出的算法可以得到更高的聚類精度，特別是可以提升聚類內(nèi)部節(jié)點的屬性相似度。

關(guān)鍵詞：

中圖分類號：TP301.6 文獻標(biāo)識碼：A文章編號：2095-2163（2012）05-0027-04

0 引言

聚類是數(shù)據(jù)挖掘中的主要方法之一，其目的在于通過自動化方法發(fā)現(xiàn)大量數(shù)據(jù)中存在的聚集特性，以提取其中蘊含的潛在規(guī)律。很多數(shù)據(jù)都具有網(wǎng)絡(luò)的形式（如人際關(guān)系網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)、萬維網(wǎng)等），對這些數(shù)據(jù)可以運用圖數(shù)據(jù)結(jié)構(gòu)加以科學(xué)化、體系化的有效組織。采用傳統(tǒng)的聚類方法，不能解決圖上的節(jié)點間聚類，因此，對于在圖上發(fā)現(xiàn)簇的圖聚類問題，已經(jīng)日益得到了來自研究人員的廣泛而深入的關(guān)注。圖聚類問題可以簡單描述為：已知一個節(jié)點集合及節(jié)點間連邊情況，如何發(fā)現(xiàn)那些具有連接結(jié)構(gòu)上相似性的節(jié)點子集。一般來說，同簇的節(jié)點間的連接應(yīng)該更稠密，同時，屬于不同簇的節(jié)點之間的連接更稀疏。目前的工作雖然很多，但對于聚類這一模糊的概念，還沒有一個統(tǒng)一的精確定義，關(guān)于聚類特性的形成機制，也處于探索和發(fā)展中。

屬性圖上的聚類問題是圖聚類問題中的一個特例。屬性圖的定義為：節(jié)點間存在邊的同時，每個節(jié)點或每條邊（注：文中工作只考慮節(jié)點屬性）擁有特有的屬性標(biāo)簽。屬性圖上的聚類不僅要考慮到節(jié)點間結(jié)構(gòu)上的相似性，同時還要考慮節(jié)點屬性間的相似性，然而，由于節(jié)點間的連接和節(jié)點具有的屬性這兩者體現(xiàn)的是完全不同的信息，因此如何協(xié)調(diào)處理兩者間的關(guān)系是一個難題。隨著網(wǎng)絡(luò)的發(fā)展和計算機采集、處理數(shù)據(jù)的能力不斷提升，屬性圖的應(yīng)用前景廣闊，目前也已經(jīng)開展了一部分研究工作。當(dāng)前處理節(jié)點屬性圖聚類問題主要有兩種方法：

（1）基于節(jié)點相似性的方法：主要思想是同時考慮節(jié)點的結(jié)構(gòu)和屬性來定義點對間的相似性，根據(jù)屬性相似性為每個邊分配權(quán)重，并將屬性圖聚類問題轉(zhuǎn)化為帶權(quán)圖的聚類問題。文獻？眼1？演將邊的權(quán)重定義為端點間具有相同屬性值的屬性個數(shù)，之后在帶權(quán)圖上聚類；文獻？眼2？演提出與文獻？眼1？演類似的屬性相似性度量，并擴展至屬性具有連續(xù)值域的情況。上述工作均為人工定義結(jié)構(gòu)和屬性間的權(quán)重，方法的效率雖然很高，但聚類效果并不好，而且由于需要人工定義權(quán)重，對于不同應(yīng)用背景圖數(shù)據(jù)的可拓展性很差。文獻？眼3？演首先假定節(jié)點和屬性間的權(quán)重值以及多個屬性間的權(quán)重值，再根據(jù)權(quán)重確定節(jié)點間的隨機游走距離，即節(jié)點間的相似性，之后采用類似K-Mean的方法不斷優(yōu)化得到聚類各簇，同時根據(jù)每次迭代產(chǎn)生的簇確定下一輪迭代的屬性權(quán)重。該方法的聚類質(zhì)量提升較大，但在每次迭代中都要根據(jù)新的屬性權(quán)重，重新計算點對之間的隨機游走距離矩陣，效率低，資源消耗大。