多屬性無向加權(quán)圖上的聚類方法研究.pdf

1、隨著社會信息化的推進(jìn)和通訊技術(shù)以及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，信息的流量越來越龐大，存儲的數(shù)據(jù)量正在以指數(shù)速度迅速增長，圖是一種廣泛使用的數(shù)據(jù)結(jié)構(gòu)，它能很好地表示數(shù)據(jù)對象之間的結(jié)構(gòu)關(guān)系。在現(xiàn)實世界中，諸多系統(tǒng)以網(wǎng)絡(luò)圖的結(jié)構(gòu)形式存在，如因特網(wǎng)、萬維網(wǎng)、人際關(guān)系網(wǎng)、科學(xué)家協(xié)作網(wǎng)和電話網(wǎng)等等。同時用于描述真實世界網(wǎng)絡(luò)結(jié)構(gòu)的圖的規(guī)模也具有較大的增長趨勢。目前面對浩渺無際的數(shù)據(jù)，人們迫切需要從數(shù)據(jù)汪洋中去粗存精、去偽存真，通過技術(shù)手段分析得到有用的結(jié)果。

2、
　　 圖聚類是一個非常有趣和具有挑戰(zhàn)性的研究課題，近年來已經(jīng)引起眾多研究者的廣泛關(guān)注，并應(yīng)用到多個領(lǐng)域。圖聚類的目的是按照各種不同的標(biāo)準(zhǔn)把大型圖的節(jié)點拆分成不同的簇，使得同一簇內(nèi)的節(jié)點連接緊密，不同簇之間節(jié)點的連接稀疏。許多現(xiàn)有的圖聚類方法主要關(guān)注圖的拓?fù)浣Y(jié)構(gòu)，使得每個簇達(dá)到一個有凝聚力的內(nèi)部結(jié)構(gòu)。但是在實際應(yīng)用中由于圖結(jié)構(gòu)數(shù)據(jù)集的異質(zhì)性，圖本身存在著諸多的潛在信息，如圖節(jié)點的屬性信息和節(jié)點間的權(quán)重信息等等。隨著圖結(jié)構(gòu)數(shù)據(jù)集的

3、日趨龐大和復(fù)雜，僅僅分析圖的拓?fù)浣Y(jié)構(gòu)信息很難得到理想的聚類結(jié)果。為此本文在綜合考慮圖的拓?fù)浣Y(jié)構(gòu)、節(jié)點屬性以及節(jié)點間權(quán)重的基礎(chǔ)上提出了兩種新的圖聚類方法來解決上述問題。
　　 1.多屬性網(wǎng)絡(luò)圖結(jié)構(gòu)化凝聚層次聚類方法
　　 圖聚類的目的是按照各種不同的標(biāo)準(zhǔn)把大型圖的節(jié)點拆分成不同的簇。該方法綜合考慮圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點屬性信息，利用節(jié)點的屬性信息輔以圖的拓?fù)浣Y(jié)構(gòu)產(chǎn)生新的簇，避免了傳統(tǒng)圖聚類方法的單一性。該方法首先通過在原圖上添

4、加多個屬性節(jié)點的方法來增強(qiáng)同屬性節(jié)點間的緊密度，同時可以讓非連通圖變?yōu)檫B通圖；再根據(jù)節(jié)點的直接鄰居關(guān)系計算邊的結(jié)構(gòu)化相似度，為了提高新添加的屬性節(jié)點的貢獻(xiàn)，本文計算屬性節(jié)點轉(zhuǎn)移概率矩陣，由此得到相鄰節(jié)點間的相似度值。該方法只訪問圖節(jié)點和邊各一次、簡單、高效。
　　 2.基于最大最小距離度量的加權(quán)網(wǎng)絡(luò)圖結(jié)構(gòu)化聚類方法
　　 該方法統(tǒng)一考慮圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點間的權(quán)重，使具有較大權(quán)重邊連接的兩點不被分開、同時使聚類結(jié)果的拓?fù)浣Y(jié)