數據挖掘中的聚類分析方法

摘要：聚類分析是多元統計分析的重要方法之一，該方法在許多領域都有廣泛的應用。本文首先對聚類的分類做簡要的介紹，然后給出了常用的聚類分析方法的基本思想和優缺點，并對常用的聚類方法作比較分析，以便人們根據實際的問題選擇合適的聚類方法。

關鍵詞：聚類分析；數據挖掘

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)12-20ppp-0c

Cluster Anlaysis Methods of Data Mining

HUANG Li-wen

(School of Science， Quanzhou Normal University， Quanzhou 362000， China)

Abstract: Cluster analysis is one of the important methods of multivariate statistical analysis， and this method has a wide range of applications in many fields. In this paper， the classification of the cluster is introduced briefly， and then gives some common methods of cluster analysis and the advantages and disadvantages of these methods，and these clustering method were compared and anslyzed so that people can chose suitable clustering methods according to the actual issues.

Key words: Cluster Analysis; Data Mining?

1 引言

聚類分析是數據挖掘中的重要方法之一，它把一個沒有類別標記的樣本集按某種準則劃分成若干個子類，使相似的樣品盡可能歸為一類，而不相似的樣品盡量劃分到不同的類中。目前，該方法已經被廣泛地應用于生物、氣候學、經濟學和遙感等許多領域，其目的在于區別不同事物并認識事物間的相似性。因此，聚類分析的研究具有重要的意義。

本文主要介紹常用的一些聚類方法，并從聚類的可伸縮性、類的形狀識別、抗“噪聲”能力、處理高維能力和算法效率五個方面對其進行比較分析，以便人們根據實際的問題選擇合適的聚類方法。

2 聚類的分類

聚類分析給人們提供了豐富多彩的分類方法，這些方法大致可歸納為以下幾種[1，2，3，4]：劃分方法、層次方法、基于密度的聚類方法、基于網格的聚類方法和基于模型的聚類方法。

2.1 劃分法(partitionging methods)

給定一個含有n個對象（或元組）的數據庫，采用一個劃分方法構建數據的k個劃分，每個劃分表示一個聚簇，且k≤n。在聚類的過程中，需預先給定劃分的數目k，并初始化k個劃分，然后采用迭代的方法進行改進劃分，使得在同一類中的對象之間盡可能地相似，而不同類的中的對象之間盡可能地相異。這種聚類方法適用于中小數據集，對大規模的數據集進行聚類時需要作進一步的改進。

2.2 層次法(hietarchical methods)

層次法對給定數據對象集合按層次進行分解，分解的結果形成一顆以數據子集為節點的聚類樹，它表明類與類之間的相互關系。根據層次分解是自低向上還是自頂向下，可分為凝聚聚類法和分解聚類法：凝聚聚類法的主要思想是將每個對象作為一個單獨的一個類，然后相繼地合并相近的對象和類，直到所有的類合并為一個，或者符合預先給定的終止條件；分裂聚類法的主要思想是將所有的對象置于一個簇中，在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者符合預先給定的終止條件。在層次聚類法中，當數據對象集很大，且劃分的類別數較少時，其速度較快，但是，該方法常常有這樣的缺點：一個步驟（合并或分裂）完成，它就不能被取消，也就是說，開始錯分的對象，以后無法再改變，從而使錯分的對象不斷增加，影響聚類的精度，此外，其抗“噪聲”的能力也較弱，但是若把層次聚類和其他的聚類技術集成，形成多階段聚類，聚類的效果有很大的提高。

2.3 基于密度的方法(density-based methods)

該方法的主要思想是只要臨近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類。也就是說，對于給定的每個數據點，在一個給定范圍的區域中必須至少包含某個數目的點。這樣的方法就可以用來濾處＂噪聲＂孤立點數據，發現任意形狀的簇。

2.4 基于網格的方法(grid-based methods)

這種方法是把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構上進行。用這種方法進行聚類處理速度很快，其處理時間獨立于數據對象的數目，只與量化空間中每一維的單元數目有關。

2.5 基于模型的方法(model-based method)

基于模型的方法為每個簇假定一個模型，尋找數據對給定模型的最佳擬合。該方法經常基于這樣的假設：數據是根據潛在的概率分布生成的。該方法主要有兩類：統計學方法和神經網絡方法。

3 常用的聚類算法

目前，已經提出的聚類算法很多，常用的聚類算法主要有以下幾種：系統聚類法、動態聚類法、CLARANS、CURE、DBSCAN、STING和模糊聚類法（FCM）。

3.1 系統聚類法

系統聚類法[5]是將n個樣品看成n類，即一類包含一個樣品；然后將性質最接近的兩類合并成一個新類，這樣就得到n-1類，再從這n-1類中找出性質最接近的兩類加以合并，成了n-2類；如此下去，最后所有的樣品均成一類；將上述類的合并過程畫成一張圖（這圖常稱為聚類圖），這樣便可決定分多少類，每類各有什么樣品。

系統聚類法的計算簡單，而且其聚類結果給出一個譜系圖，因此，可以根據該圖選擇所需要的聚類結果。但是，它也有不足之處，其主要表現在以下幾個方面：1）當樣品數量很多時，而且只需要劃分為較少的類別時，這種聚類方法的重復計算量很大；2）當某一樣品劃歸某一個類后，其屬性不變，若分類方法的選擇不當，對聚類的精度影響很大；3）對大數據量進行處理時，計算機內存開銷很大，有時，計算機受此限制而無法進行聚類分析，而且其速度很慢；4）抗干擾的能力很弱。

3.2 動態聚類算法

動態聚類法[5]就是在開始時先建立一批初始中心，而讓待分的各個樣品依據某種判別準則向初始中心凝聚，然后再逐步修改調整中心，重新分類；并根據各類離散性統計量（如均方差）和兩類間可分離性的統計量（如類間標準化距離、J-M距離等）再進行合并和分裂。此后在修改調整中心，這樣不斷繼續下去，直到分類比較合適為止。

動態聚類法使用隨機方式選擇 作為初始聚類中心，按照算法的迭代執行，整個算法的結束條件是類的重心（或凝聚點）不再改變，它的計算復雜性是O(nkt)，其中，n為樣本數量，k為聚類數，t為迭代次數。與系統聚類法相比，動態聚類法明顯的優勢是運算量小，能用于處理龐大的樣本數據，也為實時處理提供了一定的可能性，但其也存在一些缺點，主要表現在以下幾個方面:（1）動態聚類法要求用戶必須事先給出聚類的數目，選擇初始劃分的最佳方向、更新分區和停止準則，且其結果與數據輸入順序有關，不同的初始值可能會導致不同的結果；（2）對于噪聲和孤立點敏感，很容易受例外情況的影響，適用于發現球狀類，但不適合發現非凸面狀的簇，不適合大小差別較大的簇；（3）一個對象只能屬于一個類中，不能多維揭示其多重屬性。

3.3 CLARANS算法

CLARANS[2，6，9]也叫隨機搜索聚類算法，是一種分割聚類方法。該算法是基于CLARA算法的改進，與CLARA算法不同的是：CLARA算法在每個階段都選取一個固定樣本，而CLARANS在搜索的每一步都帶一定的隨機性選取一個樣本，在替換了一個中心點后得到的聚類結果被稱為當前聚類結果的鄰居，搜索的鄰居點數目被用戶定義的一個參數加以限制。如果找到一個比它更好的鄰居，則把中心點移到該鄰居節點上，否則把該點作為局部最小量，然后再隨機選擇一個點來尋找另一個局部最小量。

該算法能夠探測孤立點，并適用于大型數據庫，但其計算復雜度復雜度較高，大約為O(n2)；此外，該算法對數據輸入的順序敏感，適用于凸形或球形數據。

3.4 CURE算法

CURE[6，7，8]算法是一種使用代表點的聚類算法。該方法首先把每個數據點看成一簇，然后再以一個特定的收縮因子向中心“收縮”，即合并兩個距離最近的代表點的簇，直至達到預先給定的聚類個數為止。它回避了用所有點或單個質心來表示一個簇的傳統方法，將一個簇用多個代表點來表示，使CURE可以適應非球形的幾何形狀。另外，收縮因子降底了噪音對聚類的影響，從而使CURE對孤立點的處理更加健壯，而且能識別非球形和大小變化比較大的簇。

該算法采用隨機抽樣與分割相結合的方法來提高聚類效率，對于大型數據庫，它也具有良好的伸縮性，運行速度很快，而且有較好的聚類效果，其計算復雜度為O(n)。

3.5 DBSCAN算法

DBSCAN算法[6，7，8，9]是一種基于高密度連接區域密度的聚類算法。該方法將密度足夠高的區域劃分為簇，并可以在帶有“噪聲”的空間數據庫中發現任意形狀的聚類。其主要的思想是通過檢查數據庫中每個點的ε-鄰域來尋找聚類。如果第一個點p的ε-鄰域包含多于MinPts個點，則創建一個以P作為核心對象的新簇，否則先把它暫時標為噪聲點，跳到下一個點，并判斷它是否為核心點。然后反復地尋找從這些核心點直接密度可達的對象，當沒有新的點可以被添加到任何簇時，該過程結束。

該算法可以數據集中的所有簇和噪聲，但其不對數據集進行預處理而直接進行聚類操作，當數據集很大時，占用內存很大，而且I/O消耗也很大，如果采用空間索引，其計算復雜度為O(nlogn)，否則，其計算復雜度為O(n2)。

3.6 STING算法

STING算法[2，3，8]是一種基于風格的多分辨率聚類技術，它將空間區域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構，高層的每個單元被劃分為多個低一層的單元，高層單元的統計參數可以很容易地從低層單元計算得到，而統計信息的查詢則采用自頂向下的基于網格的方法。這些參數包括：屬性無關的參數count;屬性相關的參數m(平均值)、s(標準偏差)、min(最小值)、max(最大值)以及該單元中屬性值遵循的分布(distribution)類型。該算法預先計算和存儲每個單元的統計信息，它不依賴于查詢的匯總信息。

該算法主要優點是效率高，有利于并行處理和增量更新；它通過掃描數據庫一次來計算單元的統計信息，因而其計算復雜度為O(n)。在層次結構建立后，其查詢處理的計算復雜度為O(m)，其中m為最低層網格單元的數目。其缺點是聚類質量取決于網格結構最低層的粒度，粒度的大小會明顯影響處理代價，特別是當數據集的維數較高時，由于生成網格層次及每一層的單元數較多，算法的效率會降低。

3.7 模糊聚類算法（FCM）

傳統的聚類分析是一種硬劃分，它把每個待識別的對象嚴格地劃分到某類中，具有“非此即彼”的性質；而在實際中，大多數對象并沒有嚴格的屬性，它們在性態和類屬方面存在著中介性，具有“亦此亦彼”的性質；鑒于此，人們開始用模糊的方法來處理這類問題，從而產生了模糊聚類的方法，也就是說，模糊聚類法[5]是將模糊數學的思想觀點用到聚類分析中產生的方法，其關鍵是隸屬函數的確定。該方法多用于定性變量的分類。其主要算法如下：

（1）選擇一個初始模糊分類方案，將n個樣本分成k個模糊類，得到一個模糊隸屬度矩陣U={uij，i=1，2，…，n;j=1，2，…，k}，其中uij表示樣本Xi對模糊集Cj的隸屬度，uij∈[0，1]；

（2）利用矩陣 計算模糊評判函數的值，模糊評判函數通常是一個與對應的分類相聯系的加權平方誤差和

是第k個模糊集的中心，重新分配樣本到各模糊集以減少評判函數的值并重新計算U；

（3）重復（2），直到矩陣U不再有較大的變動。

模糊聚類解決了一些混合對象的歸類問題，同時，當樣本數較少的時候，應用該方法的優越性也比較明顯，另外，其抗干擾的能力也較強；但是，它對一些隱含類的提取能力還有待于進一步的改進，除此之外，預定的分類數目一般也是人為決定的，同動態聚類一樣，就可能出現人為預定的分類數與實際存在的類數不相符這種情況，從而影響分類的結果。

4 聚類的性能比較

基于上述的分析，現從可伸縮性、類的形狀識別、抗噪聲能力、處理高維能力和算法效率五個方面對常用聚類算法的性能進行了比較，結果如下表。通過這些比較，可以給聚類算法研究和應用的選擇提供參考。

5 結束語

目前，已經提出的聚類算法很多，每種方法都有其優缺點和不同的適用領域，可以根據上述的分析，選擇適合特定問題的聚類方法；但是，在實際應用中，由于數據的復雜性，往往用某種聚類算法進行聚類劃分得到的效果不佳，可能要綜合多種聚類方法才能得到較好的聚類效果。因此，在將來的研究中，需要做好對現有聚類算法的改進和融合，以便得到更好的聚類方法。

參考文獻：

[1] 孫孝萍.基于聚類分析的數據挖掘算法研究[D].碩士學位論文，2002.4.

[2] 覃擁軍，劉先鋒.數據挖掘中的聚類研究[J].科技咨詢導報，2007(16):28-30.

[3] 梁志榮.數據挖掘中聚類分析的技術方法[J]. 電腦開發與應用，2007，20(6):37-39.

[4] 谷淑化，呂維先，馬于濤.關于數據挖掘中聚類分析算法的比較[J].現代計算機，2005(3):26-29.

[5] 黃利文.基于幾何概率的聚類分析[D]. 碩士學位論文，2006(1).

[6] 張紅云，劉向東，段曉東等.數據挖掘中聚類算法比較[J].計算機應用與軟件，2003(2):5-6.

[7] 王勁波，翁偉，許華榮.數據挖掘中基于密度的聚類分析方法[J].統計與決策，2005(10):139-141.

[8] 劉泉鳳，陸蓓. 數據挖掘中聚類算法的比較研究[J].浙江水利水電專科學校學報，2005，17(2):55-58.

[9] 丁學鈞，楊克儉，李虹等.數據挖掘中聚類算法的比較研究[J].河北建筑工程學院學報，2004，22(3):125-127.

收稿日期：2008-02-17

作者簡介：黃利文（1979-），男，助教。

注：在表1中，n為樣本數量，k為聚類數目，t為迭代次數。