圖聚類(lèi)質(zhì)量評(píng)價(jià)指標(biāo)體系的對(duì)比分析研究.pdf

1、現(xiàn)實(shí)世界中存在著諸多大型系統(tǒng)，為了更好地了解其結(jié)構(gòu)、功能以及預(yù)測(cè)其在特定的情況下所表現(xiàn)出來(lái)的行為，網(wǎng)絡(luò)的思想被引入到它的分析和研究中，并且取得了很大的成功，如:人際關(guān)系網(wǎng)、科學(xué)家協(xié)作網(wǎng)、蛋白質(zhì)交互網(wǎng)、因特網(wǎng)、萬(wàn)維網(wǎng)等。網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)是這些網(wǎng)絡(luò)所共有的屬性。對(duì)此我們可以把網(wǎng)絡(luò)抽象為一個(gè)由節(jié)點(diǎn)和邊組成的圖，節(jié)點(diǎn)代表現(xiàn)實(shí)世界中的實(shí)體，而邊代表現(xiàn)實(shí)世界中實(shí)體與實(shí)體之間的關(guān)系，如:在科學(xué)家協(xié)作網(wǎng)絡(luò)中，科學(xué)家這個(gè)實(shí)體被抽象為圖中的節(jié)點(diǎn)，而具有協(xié)作關(guān)系

2、的科學(xué)家之間就被抽象為一條邊。發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)即對(duì)網(wǎng)絡(luò)抽象的圖進(jìn)行聚類(lèi)的過(guò)程。圖聚類(lèi)是根據(jù)節(jié)點(diǎn)的相似性發(fā)現(xiàn)團(tuán)體的過(guò)程，是一個(gè)非常值得研究的領(lǐng)域，其應(yīng)用廣泛。
　　聚類(lèi)作為數(shù)據(jù)挖掘的一項(xiàng)關(guān)鍵步驟，在眾多應(yīng)用中起著舉足輕重的作用。發(fā)展至今積累了許多成熟的聚類(lèi)方法，且各個(gè)方法都有其自己的使用范圍。對(duì)于同一數(shù)據(jù)集不同的聚類(lèi)方法所輸出的聚類(lèi)結(jié)果也不盡相同。那么，如何評(píng)價(jià)聚類(lèi)結(jié)果的好壞？在具體的應(yīng)用中，為了選擇最恰當(dāng)?shù)木垲?lèi)方法，人們從不同

3、的角度提出了一些聚類(lèi)評(píng)價(jià)指標(biāo)。圖聚類(lèi)質(zhì)量評(píng)價(jià)體系是評(píng)價(jià)聚類(lèi)算法聚類(lèi)結(jié)果好壞的重要指標(biāo)。通過(guò)評(píng)價(jià)我們不僅可以度量聚類(lèi)算法的有效性，而且可以很好地了解給定圖的動(dòng)態(tài)關(guān)系。圖聚類(lèi)質(zhì)量評(píng)價(jià)是圖聚類(lèi)最重要的方面之一。然而，對(duì)于同一聚類(lèi)結(jié)果，不同的評(píng)價(jià)指標(biāo)評(píng)價(jià)結(jié)果不盡相同。每種評(píng)價(jià)指標(biāo)都有其適用范圍，超出了指標(biāo)本身的適用范圍將會(huì)出現(xiàn)指標(biāo)的失效[1]。如何保證聚類(lèi)及聚類(lèi)評(píng)價(jià)的有效性成為聚類(lèi)應(yīng)用的一個(gè)關(guān)鍵問(wèn)題。大量的研究集中于基于某種或某些評(píng)價(jià)指標(biāo)比較聚

4、類(lèi)算法的有效性，而較少比較評(píng)價(jià)指標(biāo)。然而在沒(méi)有確定聚類(lèi)評(píng)價(jià)指標(biāo)有效性的前提下，這種比較算法的有效性就顯得不合理。目前在聚類(lèi)評(píng)價(jià)指標(biāo)的有效性方面沒(méi)有形成統(tǒng)一的共識(shí)。
　　Kleinberg關(guān)于發(fā)展一個(gè)一般性的聚類(lèi)理論，提出了基于聚類(lèi)函數(shù)的“三公理”，旨在說(shuō)明“什么是聚類(lèi)函數(shù)”，他提出聚類(lèi)函數(shù)應(yīng)該滿足尺度不變性(Function ScaleInvariance)、一致性(Function Consistency)和豐富性(Functi

5、on Richness)，并得出矛盾的結(jié)論，即滿足“三公理”的聚類(lèi)函數(shù)不存在。Ackerman and Ben-David在Kleinberg的基礎(chǔ)上對(duì)其進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化和改進(jìn)，把基于聚類(lèi)函數(shù)的公理化轉(zhuǎn)化為基于聚類(lèi)質(zhì)量度量的公理化，并增加了一個(gè)公理進(jìn)行補(bǔ)充，使得滿足該公理的的聚類(lèi)質(zhì)量度量存在并且不會(huì)出現(xiàn)矛盾的情況。
　　本文從圖聚類(lèi)的框架結(jié)構(gòu)出發(fā)，即相似性度量、聚類(lèi)算法以及聚類(lèi)質(zhì)量評(píng)價(jià)，對(duì)圖聚類(lèi)質(zhì)量評(píng)價(jià)指標(biāo)體系進(jìn)行分析和研究。在實(shí)驗(yàn)