數據挖掘中的聚類算法綜述

摘要：聚類是數據挖掘中用來發現數據分布和隱含模式的一項重要技術。全面總結了數據挖掘中聚類算法的研究現狀，分析比較了它們的性能差異和各自存在的優點及問題，并結合多媒體領域的應用需求指出了其今后的發展趨勢。

關鍵詞：數據挖掘； 聚類； 聚類算法

中圖法分類號：TP391文獻標識碼：A

文章編號：1001－3695(2007)01－0010－04

1引言

隨著信息技術和計算機技術的迅猛發展，人們面臨著越來越多的文本、圖像、視頻以及音頻數據，為幫助用戶從這些大量數據中分析出其間所蘊涵的有價值的知識，數據挖掘（Data Mining， DM）技術應運而生。所謂數據挖掘，就是從大量無序的數據中發現隱含的、有效的、有價值的、可理解的模式，進而發現有用的知識，并得出時間的趨向和關聯，為用戶提供問題求解層次的決策支持能力。與此同時，聚類作為數據挖掘的主要方法之一，也越來越引起人們的關注。

本文比較了數據挖掘中現有聚類算法的性能，分析了它們各自的優缺點并指出了其今后的發展趨勢。

2DM中現有的聚類算法

聚類是一種常見的數據分析工具，其目的是把大量數據點的集合分成若干類，使得每個類中的數據之間最大程度地相似，而不同類中的數據最大程度地不同。在多媒體信息檢索及數據挖掘的過程中，聚類處理對于建立高效的數據庫索引、實現快速準確的信息檢索具有重要的理論和現實意義。

本文以聚類算法所采用的基本思想為依據將它們分為五類，即層次聚類算法、分割聚類算法、基于約束的聚類算法、機器學習中的聚類算法以及用于高維數據的聚類算法，如圖1所示。

2．1層次聚類算法

層次聚類算法通過將數據組織成若干組并形成一個相應的樹狀圖來進行聚類，它又可以分為兩類，即自底向上的聚合層次聚類和自頂向下的分解層次聚類。聚合聚類的策略是先將每個對象各自作為一個原子聚類，然后對這些原子聚類逐層進行聚合，直至滿足一定的終止條件；后者則與前者相反，它先將所有的對象都看成一個聚類，然后將其不斷分解直至滿足終止條件。

對于聚合聚類算法來講，根據度量兩個子類的相似度時所依據的距離不同，又可將其分為基于SingleLink，CompleteLink和AverageLink的聚合聚類。SingleLink在這三者中應用最為廣泛，它根據兩個聚類中相隔最近的兩個點之間的距離來評價這兩個類之間的相似程度，而后兩者則分別依據兩類中數據點之間的最遠距離和平均距離來進行相似度評價。

CURE，ROCK和CHAMELEON算法是聚合聚類中最具代表性的三個方法。

Guha等人在1998年提出了CURE算法[1]。該方法不用單個中心或對象來代表一個聚類，而是選擇數據空間中固定數目的、具有代表性的一些點共同來代表相應的類，這樣就可以識別具有復雜形狀和不同大小的聚類，從而能很好地過濾孤立點。ROCK算法[2]是對CURE的改進，除了具有CURE算法的一些優良特性之外，它還適用于類別屬性的數據。CHAMELEON算法[3]是Karypis等人于1999年提出來的，它在聚合聚類的過程中利用了動態建模的技術。

2．2分割聚類算法

分割聚類算法是另外一種重要的聚類方法。它先將數據點集分為k個劃分，然后從這k個初始劃分開始，通過重復的控制策略使某個準則最優化以達到最終的結果。這類方法又可分為基于密度的聚類、基于網格的聚類、基于圖論的聚類和基于平方誤差的迭代重分配聚類。

2．2．1基于密度的聚類

基于密度的聚類算法從數據對象的分布密度出發，將密度足夠大的相鄰區域連接起來，從而可以發現具有任意形狀的聚類，并能有效處理異常數據。它主要用于對空間數據的聚類。

DBSCAN[4]是一個典型的基于密度的聚類方法，它將聚類定義為一組密度連接的點集，然后通過不斷生長足夠高密度的區域來進行聚類。DENCLUE[5]則根據數據點在屬性空間中的密度來進行聚類。從本質上講，DENCLUE是基于密度的聚類算法與基于網格的預處理的結合，它受目標數據的維度影響較小。此外，Ankerst等人提出的OPTICS，Xu等人提出的DBCLASD和馬帥等人提出的CURD算法也采用了基于密度的聚類思想，它們均針對數據在空間中呈現的不同密度分布對DBSCAN作了相應的改進。

2．2．2基于網格的聚類

基于網格的聚類從對數據空間劃分的角度出發，利用屬性空間的多維網格數據結構，將空間劃分為有限數目的單元以構成一個可以進行聚類分析的網格結構。該方法的主要特點是處理時間與數據對象的數目無關，但與每維空間所劃分的單元數相關；而且，基于其間接的處理步驟（數據→網格數據→空間劃分→數據劃分），該方法還與數據的輸入順序無關。與基于密度的聚類只能處理數值屬性的數據所不同的是，基于網格的聚類可以處理任意類型的數據，但以降低聚類的質量和準確性為代價。

STING[6]是一個基于網格多分辨率的聚類方法，它將空間劃分為方形單元，不同層次的方形單元對應不同層次的分辨率。STING+[7]則對其進行了改進以用于處理動態進化的空間數據。CLIQUE[8]也是一個基于網格的聚類算法，它結合了網格聚類與密度聚類的思想，對于處理大規模高維數據具有較好的效果。除這些算法以外，以信號處理思想為基礎的WaveCluster[9]算法也屬基于網格聚類的范疇。

2．2．3基于圖論的聚類

基于圖論的方法是把聚類轉換為一個組合優化問題，并利用圖論和相關的啟發式算法來解決該問題。其做法一般是先構造數據集的最小生成樹（Minimal Spanning Tree，MST），然后逐步刪除MST中具有最大長度的那些邊，從而形成更多的聚類。基于超圖的劃分和基于光譜的圖劃分方法[10]是這類算法的兩個主要應用形式。該方法的一個優點在于它不需要進行一些相似度的計算，就能把聚類問題映射為圖論中的一個組合優化問題。

2．2．4基于平方誤差的迭代重分配聚類

基于平方誤差的重分配聚類方法的主要思想是逐步對聚類結果進行優化、不斷將目標數據集向各個聚類中心進行重新分配以獲得最優解（判斷是否是最優解的目標函數通常通過平方誤差計算法得到）。此類方法又可進一步分為概率聚類算法、考慮了最近鄰影響的最近鄰聚類算法以及Kmedoids算法和Kmeans算法。

（1）概率聚類算法的重要代表是Mitchell等人于1997年提出的期望最大化算法（Expectation Maximization，EM）[11]。它除了能處理異構數據之外，還具有另外幾個重要的特性：①能處理具有復雜結構的記錄；②能夠連續處理成批的數據；③具有在線處理能力；④產生的聚類結果易于解釋。

（2）最近鄰距離的計算在聚類過程中起著基礎性的作用，這也正是導致產生最近鄰聚類算法的直接因素。共享最近鄰算法（Shared Nearest Neighbor，SNN）[12]就是該類算法的典型代表之一，它把基于密度的方法與ROCK算法的思想結合起來，通過只保留數據點的K個最近鄰居從而簡化了相似矩陣，并且也保留了與每個數據點相連的最近鄰居的個數，但是其時間復雜度也提高到了O(N2)（N為數據點個數）。

（3）Kmedoids方法用類中的某個點來代表該聚類，這種方法能有效處理異常數據。它的兩個最早版本是PAM和CLARA算法[13]，此后又有CLARANS[14]及其一系列的擴展算法。這類方法具有兩個優點：它能處理任意類型的屬性；它對異常數據不敏感。

（4）Kmeans算法是目前為止應用最為廣泛的一種聚類方法，其每個類別均用該類中所有數據的平均值（或加權平均）來表示，這個平均值即被稱作聚類中心。該方法雖然不能用于類別屬性的數據，但對于數值屬性的數據，它能很好地體現聚類在幾何和統計學上的意義。但是，原始Kmeans算法也存在如下缺陷：①聚類結果的好壞依賴于對初始聚類中心的選擇；②容易陷入局部最優解；③對K值的選擇沒有準則可依循；④對異常數據較為敏感；⑤只能處理數值屬性的數據；⑥聚類結果可能不平衡。

為克服原始Kmeans算法存在的不足，研究者從各自不同的角度提出了一系列Kmeans的變體，如Bradley和Fayyad等人從降低聚類結果對初始聚類中心的依賴程度入手對它作了改進，同時也使該算法能適用于大規模的數據集[15]；Dhillon等人則通過調整迭代過程中重新計算聚類中心的方法使其性能得到了提高[16]；Zhang等人利用權值對數據點進行軟分配以調整其迭代優化過程[17]；Pelleg等人提出了一個新的Xmeans算法來加速其迭代過程[18]；Sarafis則將遺傳算法應用于Kmeans的目標函數構建中，并提出了一個新的聚類算法[19]；為了得到平衡的聚類結果，文獻[20]利用圖論的劃分思想對Kmeans作了改進；文獻[21]則將原始算法中的目標函數對應于一個各向同性的高斯混合模型；Berkhin等人[22]將Kmeans的應用擴展到了分布式聚類。

2．3基于約束的聚類算法

真實世界中的聚類問題往往是具備多種約束條件的，然而由于在處理過程中不能準確表達相應的約束條件、不能很好地利用約束知識進行推理以及不能有效利用動態的約束條件，使得這一方法無法得到廣泛的推廣和應用。這里的約束可以是對個體對象的約束，也可以是對聚類參數的約束，它們均來自相關領域的經驗知識。該方法的一個重要應用在于對存在障礙數據的二維空間數據進行聚類。COD（Clustering with Obstructed Distance）[23]就是處理這類問題的典型算法，其主要思想是用兩點之間的障礙距離取代了一般的歐氏距離來計算其間的最小距離。更多關于這一聚類算法的總結可參考文獻[24]。

2．4機器學習中的聚類算法

機器學習中的聚類算法是指與機器學習相關、采用了某些機器學習理論的聚類方法，它主要包括人工神經網絡方法以及基于進化理論的方法。

自組織映射（SelfOrganizing Map，SOM）[25]是利用人工神經網絡進行聚類的較早嘗試，它也是向量

量化方法的典型代表之一。該方法具有兩個主要特點：①它是一種遞增的方法，即所有的數據點是逐一進行處理的；②它能將聚類中心點映射到一個二維的平面上，從而實現可視化。此外， 文獻[26]中提出的一種基于投影自適應諧振理論的人工神經網絡聚類也具有很好的性能。

在基于進化理論的聚類方法中，模擬退火的應用較為廣泛，SINICC算法[27]就是其中之一。在模擬退火中經常使用到微擾因子，其作用等同于把一個點從當前的聚類重新分配到一個隨機選擇的新類別中，這與Kmeans中采用的機制有些類似。

遺傳算法也可以用于聚類處理，它主要通過選擇、交叉和變異這三種遺傳算子的運算以不斷優化可選方案從而得到最終的聚類結果。

利用進化理論進行聚類的缺陷在于它依賴于一些經驗參數的選取，并且具有較高的計算復雜度。為了克服上述不足之處，有研究者嘗試組合利用多種策略，如將遺傳算法與Kmeans結合起來，并且使用變長基因編碼，這樣不僅能提高Kmeans算法的效率，還能運行多個Kmeans算法以確定合適的K值[28]。

2．5用于高維數據的聚類算法

高維數據聚類是目前多媒體數據挖掘領域面臨的重大挑戰之一。對高維數據聚類的困難主要來源于以下兩個因素：①高維屬性空間中那些無關屬性的出現使得數據失去了聚類趨勢；②高維使數據之間的區分界限變得模糊。

除了降維這一最直接的方法之外，對高維數據的聚類處理還包括子空間聚類以及聯合聚類技術等。

CACTUS[29]采用了子空間聚類的思想，它基于對原始空間在二維平面上的一個投影處理。CLIQUE也是用于數值屬性數據的一個簡單的子空間聚類方法，它不僅同時結合了基于密度和基于網格的聚類思想，還借鑒了Apriori算法，并利用MDL（Minimum Description Length）原理選擇合適的子空間。

聯合聚類對數據點和它們的屬性同時進行聚類。以文本為例，文獻[30]中提出了文本聯合聚類中一種基于雙向劃分圖及其最小分割的代數學方法，并揭示了聯合聚類與圖論劃分之間的關系。

3現有聚類算法的性能比較

從上面的分析介紹不難看出，這些現有的聚類算法在不同的應用領域中均表現出了不同的性能，也就是說，很少有一種算法能同時適用于若干個不同的應用背景。

總體來說，分割聚類算法的應用最為廣泛，其收斂速度快，且能夠擴展以用于大規模的數據集；缺點在于它傾向于識別凸形分布、大小相近、密度相近的聚類，而不能發現形狀比較復雜的聚類，并且初始聚類中心的選擇和噪聲數據會對聚類結果產生較大的影響。層次聚類方法不僅適用于任意屬性和任意形狀的數據集，還可以靈活控制不同層次的聚類粒度，因此具有較強的聚類能力，但它大大延長了算法的執行時間；此外，對層次聚類算法中已經形成的聚類結構不能進行回溯處理。

基于約束的聚類通常只用于處理某些特定應用領域中的特定需求。機器學習中的人工神經網絡和模擬退火等方法雖然能利用相應的啟發式算法獲得較高質量的聚類結果，但其計算復雜度往往較高，同時其聚類結果的好壞也依賴于對某些經驗參數的選取。在針對高維數據的子空間聚類和聯合聚類等算法中，雖然通過在聚類過程中選維、逐維聚類和降維從一定程度上減少了高維度帶來的影響，但它們均不可避免地帶來了原始數據信息的損失和相應的聚類準確性的降低，因此，尋求這類算法在聚類質量和算法時間復雜度之間的折中也是一個重要的問題。

本文選取聚類算法所處理的目標數據的屬性（數值型N/類別型C）、算法的時間復雜度、能否處理大規模數據集、能否處理異常數據（噪聲數據）、能否處理高維數據、能否發現復雜的聚類形狀、是否受初始聚類中心影響以及是否受數據輸入順序影響這八個參數，總結比較了一些有代表性的算法的性能，如表1所示。

表1部分聚類算法性能總結與比較

表1中，算法的時間復雜度都是針對低維數據而言的，Kmeans和GA也均為原始的標準算法；n為目標數據的數目，對于CURE算法來講，由于它的執行依賴于對樣本集（Sample）的選擇，所以其時間復雜度由樣本集的數據數目來決定。

從表1中反映出來的一個最突出的問題在于，這些算法絕大多數不適用于高維數據，而那些少數可以用于高維數據的算法，其時間復雜度也往往會隨著維度的升高而顯著增高。

總之，雖然一些算法相對其他方法在某些方面的性能有了一定程度的提高，但它不可能在任何應用背景下均具有很好的結果，即幾乎沒有一個算法能同時在表1中所示的八個方面都具有優良的性能。因此對于它們的改進還有一個相當大的空間。

4總結與展望

聚類算法的研究具有廣泛的應用前景，其今后的發展也面臨著越來越多的挑戰。以其在多媒體領域中的應用為例，鑒于多媒體特征數據本身所具備的高維性、復雜性、動態性以及容易達到大規模的特性，對多媒體數據聚類算法的設計還應該更多地考慮以下幾個方面的內容：

（1）融合不同的聚類思想形成新的聚類算法，從而綜合利用不同聚類算法的優點。

（2）處理大規模數據和高維數據的能力，這是多媒體數據挖掘中聚類算法必須解決的關鍵問題。

（3）對聚類的結果進行準確評價，以判斷是否達到最優解，這也自然要求聚類結果具有可解釋性。

（4）選取合適的聚類類別數，這是一個重要的參數。它的確定應更多地依賴于相關的經驗知識以及對目標數據集所進行的必要的預處理。

（5）對數據進行合理的預處理。該過程包括對高維數據以及對大規模數據建立索引等，它不僅是實現（4）的前提之一，也為獲得更準確的聚類結果提供了一個重要的手段。

（6）在聚類過程中使用合適的相似計算公式及評價準則。合理的相似性評判準則對聚類結果的準確性起著不容忽視的作用。

（7）將領域知識引入聚類過程。領域知識的引入不僅有助于選擇合適的模式表達機制、選擇合適的聚類算法，還能使以上很多方面的問題都能得到合理的解決，從而提高相應的聚類算法的性能。

在多媒體數據聚類的應用中，對原始數據如圖像等進行特征提取，并用這些特征數據代替原始數據進行聚類，均體現了領域知識的融合。

參考文獻：

［1］Guha S， Rastogi R， Shim K. CURE： An Efficient Clustering Algorithm for Large Databases[C]. Seattle： Proceedings of the ACM SIGMOD Conference，1998.7384.

［2］Guha S， Rastogi R， Shim K. ROCK： A Robust Clustering Algorithm for Categorical Attributes[C]. Sydney: Proceedings of the 15th ICDE，1999.512521.

［3］Karypis G， Han EH， Kumar V. CHAMELEON： A Hierarchical Clustering Algorithm Using Dynamic Modeling [J]. IEEE Computer，1999，32(8)：6875.

［4］Ester M， Kriegel HP， Sander J， et al. A Densitybased Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]. Portland: Proceedings of the 2nd ACM SIGKDD，1996.226231.

［5］Hinneburg A， Keim D. An Efficient Approach to Clustering Large Multimedia Databases with Noise[C]. New York:Proceedings of the 4th ACM SIGKDD，1998.5865.

［6］Wang W， Yang J， Muntz R. STING： A Statistical Information Grid Approach to Spatial Data Mining[C]. Athens: Proceedings of the 23rd Conference on VLDB，1997.186195.

［7］Wang W， Yang J， Muntz R R. STING+： An Approach to Active Spatial Data Mining[C]. Sydney:Proceedings of the 15th ICDE，1999.116125.

［8］Agrawal R， Gehrke J， Gunopulos D， et al. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[C]. Seattle: Proceedings of the ACM SIGMOD Conference，1998.94105.

［9］Sheikholeslami G，Chatterjee S，Zhang A. WaveCluster：A Multireso￣lution Clustering Approach for Very Large Spatial Databases[C]. New York: Proceedings of the 24th Conference on VLDB，1998.428439.

［10］Chris Ding.A Tutorial on Spectral Clustering[C].ICML，20-04.

［11］Mitchell T. Machine Learning[M]. New York： McGrawHill， 1997.

［12］Ertoz L， Steinbach M， Kumar V. Finding Clusters of Different Sizes，Shapes， and Densities in Noisy， High Dimensional Data[R]. Minnea￣polis:University of Minnesota，2002.

［13］Kaufman L， Rousseeuw P. Finding Groups in Data： An Introduction to Cluster Analysis[M]. New York： John Wiley and Sons， 1990.

［14］Ng R， Han J. Efficient and Effective Clustering Methods for Spatial Data Mining[C]. Santiago: Proceedings of the 20th Conference on VLDB，1994.144155.

［15］Bradley P， Fayyad U. Refining Initial Points for Kmeans Clustering[C]. Madison: Proceedings of the 15th ICML，1998.9199.

［16］Dhillon I， Guan Y， Kogan J. Refining Clusters in High Dimensional Data[C]. Arlington: The 2nd SIAM ICDM， Workshop on Clustering High Dimensional Data，2002.

［17］Zhang B. Generalized Kharmonic Means: Dynamic Weighting of Data in Unsupervised Learning[C]. Chicago: Proceedings of the 1st SIAM ICDM，2001.

［18］Pelleg D，Moore A. Xmeans： Extending Kmeans with Efficient Estimation of the Number of the Clusters[C]. Proceedings of the 17th ICML， 2000.

［19］Sarafis I， Zalzala A M S， Trinder P W. A Genetic Rulebased Data Clustering Toolkit[C]. Honolulu: Congress on Evolutionary Computation(CEC)，2002.

［20］Strehl A，Ghosh J. A Scalable Approach to Balanced， Highdimensional Clustering of Market Baskets[C]. Proceedings of the 17th International Conference on High Performance Computing， Bangalore：Springer LNCS，2000.525536.

［21］Banerjee A，Ghosh J. On Scaling up Balanced Clustering Algorithms[C]. Arlington:Proceedings of the 2nd SIAM ICDM，2002.

［22］Berkhin P，Becher J. Learning Simple Relations： Theory and Applications[C]. Arlington:Proceedings of the 2nd SIAM ICDM，2002.333349.

［23］Tung A K H， Hou J，Han J. Spatial Clustering in the Presence of Obstacles[C]. Heidelberg:Proceedings of the 17th ICDE，2001.359367.

［24］Han J， Kamber M， Tung A K H. Spatial Clustering Methods in Data Mining： A Survey[C]. Geographic Data Mining and Knowledge Discovery， 2001.

［25］Kohonen T. SelfOrganizing Maps[M]. Springer Series in Information Sciences，2001.30.

［26］Yongqiang Cao，Jianhong Wu. Dynamics of Projective Adaptive Resonance Theory Model： The Foundation of PART Algorithm[J].IEEE Transactions on Neural Network， 20-04， 15(2)： 245260.

［27］Brown D， Huntley C. A Practical Application of Simulated Annealing to Clustering[R]. University of Virginia， 1991.

［28］Cristofor D， Simovici D A. An Informationtheoretical Approach to Clustering Categorical Databases Using Genetic Algorithms[C]. Arlington:The 2nd SIAM ICDM， Workshop on Clustering High Dimensional Data，2002.

［29］Ganti V， Gehrke J， Ramakrishna R. CACTUSClustering Categorical Data Using Summaries[C]. San Diego: Proceedings of the 5th ACM SIGKDD，1999.7383.

［30］Dhillon I. Coclustering Documents and Words Using Bipartite Spectral Graph Partitioning[C]. San Franciso: Proceedings of the 7th ACM SIGKDD，2001.269274.

作者簡介：

賀玲（1976），女，博士研究生，主要研究方向為多媒體信息系統、多媒體數據挖掘；吳玲達，女，教授，博導，主要研究方向為多媒體信息系統與虛擬現實技術；蔡益朝（1976），主要研究方向為智能決策。

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