聚類有效性評價綜述

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

關鍵詞：聚類；聚類評價；有效性指數

中圖分類號：TP311文獻標志碼：A

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

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

1聚類評價方法

1．1外部評價法

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

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

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

2聚類有效性評價的應用

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

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

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

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

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

3結束語

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

參考文獻：

［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]張惟皎，劉春煌，李芳玉.聚類質量的評價方法[J].計算機工程， 2005，31(20):10－12.

[5]李潔， 高新波， 焦李成.一種基于修正劃分模糊度的聚類有效性函數[J].系統工程與電子技術， 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]楊占華.聚類分析研究及其在文本挖掘中的應用[D].成都：西南交通大學，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].計算機科學，2007，34(2):207－210.

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