聚類有效性評價綜述

摘要：在聚類分析應(yīng)用中，迫切需要一種客觀公正的質(zhì)量評價方法來評判聚類結(jié)果的有效性。為此，從外部評價法、內(nèi)部評價法和相對評價法三個方面，歸納綜述了常用的聚類有效性評價方法，并討論了模糊聚類評價法和聚類最佳類別數(shù)的自動確定問題。

關(guān)鍵詞：聚類；聚類評價；有效性指數(shù)

中圖分類號：TP311文獻標(biāo)志碼：A

文章編號：1001－3695(2008)06－1630－03

聚類分析是數(shù)據(jù)挖掘過程中的一種重要手段和工具，它可以發(fā)現(xiàn)隱含在數(shù)據(jù)集中的簇，標(biāo)志出感興趣的分布或模式。聚類問題是將一組對象分成若干個簇或聚類，使簇內(nèi)的對象盡可能具有最大的相似性，不同簇之間的對象盡可能有最大的相異性。聚類過程可以看做是一種無監(jiān)督的學(xué)習(xí)過程，因為沒有預(yù)先定義的分類或示例來表明數(shù)據(jù)集中哪種期望的關(guān)系是有效的，多數(shù)聚類算法依靠假設(shè)和猜測進行。如何用一種客觀公正的質(zhì)量評價方法來評判聚類結(jié)果的有效性是一個困難而復(fù)雜的問題。廣義上講，聚類有效性評價包括聚類質(zhì)量的度量、聚類算法適合某種特殊數(shù)據(jù)集的程度，以及某種劃分的最佳聚類數(shù)目[1]。常用的聚類有效性評價方法有外部評價法、內(nèi)部評價法和相對評價法[2~4]。外部和內(nèi)部評價法均基于統(tǒng)計測試，具有較高的計算復(fù)雜性，這些方法中的有效性指數(shù)是為了度量一個數(shù)據(jù)集與預(yù)先已知結(jié)構(gòu)的相符程度。相對評價法尋求一個聚類算法在一定假設(shè)和參數(shù)下能定義的最好聚類結(jié)果。此外，還有一類針對軟（模糊）劃分的聚類評價方法，稱之為模糊聚類有效性度量[3~5]。在聚類性能評價方法中，某些有效性指數(shù)能夠求得具有最佳聚類數(shù)目的劃分[1， 5~11]。這也是目前聚類評價的應(yīng)用熱點之一。

1聚類評價方法

1．1外部評價法

外部評價方法意味著評判聚類算法的結(jié)果是基于一種預(yù)先指定的結(jié)構(gòu)。這種結(jié)構(gòu)反映了人們對數(shù)據(jù)集聚類結(jié)構(gòu)的直觀認識。每個數(shù)據(jù)項的分類標(biāo)記已知。下面介紹兩種常用的外部評價法。

1）F－measure它組合了信息檢索中查準(zhǔn)率（precision）與查全率（recall）的思想來進行聚類評價。一個聚類j及與此相關(guān)的分類i的precision與recall定義為[12]

文獻[16]在研究KFCM聚類算法的有效性準(zhǔn)則時，將XB、FS、CWB等六個著名的模糊有效性指數(shù)推廣到高維特征空間，得到其對應(yīng)的核化形式。

2聚類有效性評價的應(yīng)用

聚類是一種無教師的學(xué)習(xí)，沒有關(guān)于分類的先驗信息，按照相似性準(zhǔn)則把數(shù)據(jù)劃分成各種不同的類別。但在大多數(shù)聚類算法中，需要用戶事先輸入希望產(chǎn)生的簇的個數(shù)，這使聚類結(jié)果帶有一定的主觀性和人為誤差。而在聚類性能評價的研究中，聚類有效性問題經(jīng)常可轉(zhuǎn)換為最佳類別數(shù)的自動確定。

Halkidi等人在文獻[1]中利用SD有效性指數(shù)評價一個聚類算法以不同輸入?yún)?shù)得到的不同劃分，從而選取具有最佳聚類個數(shù)的聚類結(jié)果。

自組織映射（self－organizing map，SOM）聚類是由Kohonen教授提出的一種無監(jiān)督的聚類方法。它由全互連的輸入層和競爭層組成，模擬人腦的處理過程，通過若干個單元競爭當(dāng)前對象來實現(xiàn)聚類。Ressom等人提出自適應(yīng)雙SOM（ADSOM）模型[8]，具有靈活的拓撲結(jié)構(gòu)和可視化優(yōu)勢，不需要關(guān)于聚類數(shù)目的先驗知識，利用基于樹的評價指數(shù)確定聚類數(shù)目。文獻[9]用例子說明了SD指數(shù)可以求得最佳SOM聚類個數(shù)。Wu等人將多代表點評價指數(shù)[6]，不僅用做全局尋求輸入數(shù)據(jù)的最好劃分數(shù)目，而且局部用于確定層次SOM聚類算法兩鄰域簇的合并[10，11]。

筆者在文獻[7]中提出基于聚類有效性指數(shù)的蟻群聚類算法，利用基于多代表點的評價指數(shù)CDbw[6]自動求得最佳聚類數(shù)目；同時，用其局部有效性指數(shù)減少孤立點。

文獻[5]探討了用修正的劃分模糊度指數(shù)如何確定數(shù)值型數(shù)據(jù)和類屬型數(shù)據(jù)聚類中的最佳類別數(shù)。

3結(jié)束語

聚類性能評價是聚類分析中的一個重要研究課題，其不得不面對的主要困難是聚類后，怎樣評價返回的聚類結(jié)果的質(zhì)量？然而，迄今為止，還沒有一個對所有應(yīng)用領(lǐng)域都普遍適用的評價方法，聚類評價方法往往與特定應(yīng)用問題、采用的聚類算法等因素有關(guān)。探索更加成熟、行之有效的聚類有效性度量方法，是今后努力的方向。

參考文獻：

［1］HALKIDI M，VAZIRGIANNIS M，BATISTAKIS Y.Quality scheme assessment in the clustering process[C]//Proc of the 4th Eur Conf Principles and Practice of Knowledge Discovery in Databases.2000:165－276.

[2]THEODORIDIS S， KOUTROUBAS K. Pattern recognition[M]. [S.l.]:Academic Press， 1999.

[3]HALKIDI M， BATISTAKIS Y， VAZIRGIANNIS M. On clustering validation techniques[J].Intelligent Information Systems，2001，17(2－3):107－145.

[4]張惟皎，劉春煌，李芳玉.聚類質(zhì)量的評價方法[J].計算機工程， 2005，31(20):10－12.

[5]李潔， 高新波， 焦李成.一種基于修正劃分模糊度的聚類有效性函數(shù)[J].系統(tǒng)工程與電子技術(shù)， 2005，27(4):723－726.

[6]HALKIDI M，VAZIRGIANNIS M. Clustering validity assessment using multi representatives[C]//Proc of SETN Conference.2002.

[7]YANG Yan， KAMEL M， JIN Fan.A model of document clustering using ant colony algorithm and validity index[C]//Proc of IEEE International Joint Conference on Neural Networks.Montreal:[s.n.]，2005:2730－2735.

[8]RESSOM H，WANG D，NATARAJAN P.Adaptive double self－organizing maps for clustering gene expression profiles[J].Neural Networks，2003，16(5－6):633－640.

[9]楊占華.聚類分析研究及其在文本挖掘中的應(yīng)用[D].成都：西南交通大學(xué)，2006.

[10]WU Si－tao，CHOW T W S.Self－organizing－map based clustering using a local clustering validity index[J].Neural Processing Letters，2003，17（3）:253－271.

[11]WU Si－tao，CHOW T W S.Clustering of the self－organizing map using a clustering validity index based on inter－cluster and intra－cluster density[J].Pattern Recognition，2004，37（2）:175－188.

[12]STEINBACH M，KARYPIS G，KUMAR V.A comparison of document clustering techniques[C]//Proc of KDD－2000 Workshop on Text Mining.2000.

[13]HE Ji，TAN A H，TAN C L.Modified ART 2A growing network capable of generating a fixed number of nodes[J].IEEE Trans on Neural Networks，2004，15(3):728－737.

[14]HE Ji，TAN A H，TAN C L，et al.On quantitative evaluation of clustering systems[C]//Proc of Information Retrieval and Clustering. Boston， MA: Kluwer，2003.

[15]REZAEE M R， LELIEVELDT B P F， REIBER J H C.A new cluster validity for the fuzzy C－mean[J].Pattern Recognition Letters，1998，19(3－4):237－246.

[16]普運偉，金煒東，朱明，等.核模糊C均值算法的聚類有效性研究[J].計算機科學(xué)，2007，34(2):207－210.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文