圖聚類質(zhì)量評價指標體系的對比分析研究.pdf

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

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

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

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

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