資料挖掘中聚類算法比較研究(zt)

資料挖掘中聚類算法比較研究

張紅雲　劉向東　段曉東　苗奪謙　馬垣

(同濟大學電子與資訊工程學院　上海 200092)

(大連民族學院計算機系　大連 116600)

(鞍山科技大學計算機科學與工程學院　鞍山 114002)

　　摘　要 ：聚類算法是資料挖掘的核心技術，本文綜合提出了評價聚類算法好壞的5個标準，基于這5個标準，對資料挖掘中常用聚類算法作了比較分析，以便于人們更容易、更快捷地找到一種适用于特定問題的聚類算法。

　　關鍵詞 ：資料挖擁；平衡疊代削減聚類算法；代表點聚類算法；基于密度的聚類算法

THE COMPARISON OF CLUSTERING METHODS IN DATA MINING

　　Abstract : Clustering method is the core of data mining technology. In this paper, five standards were put forward which are used to evaluate these clustering methods. These clustering methods were compared and analyzed according to the standards so that people can easily and quickly find a clustering method that suit a special problem.

　　Keywords : Data Mining; BIRCH; DBSCAN; CURE

1 引言

　 　把資料庫中的對象分類是資料挖掘的基本操作，其準則是使屬于同一類的個體間距離盡可能小，而不同類個體間距離盡可能大，為了找到效率高、通用性強的聚類 方法人們從不同角度提出了近百種聚類方法，典型的有K-means方法、K-medoids方法、CLARANS方法,BIRCH方法等，這些算法适用于 特定的問題及使用者。本文綜合提出了評價聚類算法好壞的5個标準，基于這5個标準，對資料挖掘中常用聚類方法作了比較分析，以便于人們更容易、更快捷地找到 一種适用于特定問題及使用者的聚類算法。

2 資料挖掘聚類算法研究及比較架構

　 　聚類算法一般分為分割和分層兩種。分割聚類算法通過優化評價函數把資料集分割為K個部分，它需要K作為輸人參數。典型的分割聚類算法有K-means算 法, K-medoids算法、CLARANS算法。分層聚類由不同層次的分割聚類組成，層次之間的分割具有嵌套的關系。它不需要輸入參數，這是它優于分割聚類 算法的一個明顯的優點，其缺點是終止條件必須具體指定。典型的分層聚類算法有BIRCH算法、DBSCAN算法和CURE算法等。

　　本文對各聚類算法的比較研究基于以下5個标準：

　　① 是否适用于大資料量，算法的效率是否滿足大資料量高複雜性的要求;

　　② 是否能應付不同的資料類型，能否處理符号屬性;

　　③ 是否能發現不同類型的聚類;

　　④ 是否能應付髒資料或異常資料;

　　⑤ 是否對資料的輸入順序不敏感。

　　下面将在該架構下對各聚類算法作分析比較。

3 資料挖掘常用聚類算法比較分析

　　3.1 BIRCH算法

　 　BIRCH算法即平衡疊代削減聚類法，其核心是用一個聚類特征3元組表示一個簇的有關資訊，進而使一簇點的表示可用對應的聚類特征，而不必用具體的一組 點來表示。它通過構造滿足分支因子和簇直徑限制的聚類特征樹來求聚類。BIRCH算法通過聚類特征可以友善地進行中心、半徑、直徑及類内、類間距離的運 算。算法的聚類特征樹是一個具有兩個參數分枝因子B和類直徑T的高度平衡樹。分枝因子規定了樹的每個節點子女的最多個數，而類直徑展現了對一類點的直徑大 小的限制即這些點在多大範圍内可以聚為一類，非葉子結點為它的子女的最大關鍵字，可以根據這些關鍵字進行插人索引，它總結了其子女的資訊。

　　聚 類特征樹可以動态構造，是以不要求所有資料讀人記憶體，而可以在外存上逐個讀人。新的資料項總是插人到樹中與該資料距離最近的葉子中。如果插人後使得該葉子 的直徑大于類直徑T，則把該葉子節點分裂。其它葉子結點也需要檢查是否超過分枝因子來判斷其分裂與否，直至該資料插入到葉子中，并且滿足不超過類直徑，而 每個非葉子節點的子女個數不大于分枝因子。算法還可以通過改變類直徑修改特征樹大小，控制其占記憶體容量。

　　BIRCH算法通過一次掃描就可以進 行較好的聚類，由此可見，該算法适合于大資料量。對于給定的M兆記憶體空間，其空間複雜度為O(M)，時間間複雜度為O(dNBlnB(M/P)).其中d 為維數,N為節點數,P為記憶體頁的大小，B為由P決定的分枝因子。I/O花費與資料量成線性關系。BIRCH算法隻适用于類的分布呈凸形及球形的情況，并 且由于BIRCH算法需提供正确的聚類個數和簇直徑限制，對不可視的高維資料不可行。

　　3.2 CURE算法

　　CURE算法即使用代 表點的聚類方法。該算法先把每個資料點看成一類，然後合并距離最近的類直至類個數為所要求的個數為止。CURE算法将傳統對類的表示方法進行了改進，回避 了用所有點或用中心和半徑來表示一個類，而是從每一個類中抽取固定數量、分布較好的點作為描述此類的代表點，并将這些點乘以一個适當的收縮因子，使它們更 靠近類的中心點。将一個類用代表點表示，使得類的外延可以向非球形的形狀擴充，進而可調整類的形狀以表達那些非球形的類。另外，收縮因子的使用減小了嗓音 對聚類的影響。CURE算法采用随機抽樣與分割相結合的辦法來提高算法的空間和時間效率，并且在算法中用了堆和K-d樹結構來提高算法效率。

　　3.3 DBSCAN算法

　 　DBSCAN算法即基于密度的聚類算法。該算法利用類的密度連通性可以快速發現任意形狀的類。其基本思想是：對于一個類中的每個對象，在其給定半徑的領 域中包含的對象不能少于某一給定的最小數目。在DBSCAN算法中，發現一個類的過程是基于這樣的事實：一個類能夠被其中的任意一個核心對象所确定。為了 發現一個類，DBSCAN先從對象集D中找到任意一對象P，并查找D中關于關徑Eps和最小對象數Minpts的從P密度可達的所有對象。如果P是核心對 象，即半徑為Eps的P的鄰域中包含的對象不少于Minpts,則根據算法，可以找到一個關于參數Eps和Minpts的類。如果P是一個邊界點，則半徑 為Eps的P鄰域包含的對象少于Minpts，P被暫時标注為噪聲點。然後，DBSCAN處理D中的下一個對象。

　　密度可達對象的擷取是通過不 斷執行區域查詢來實作的。一個區域查詢傳回指定區域中的所有對象。為了有效地執行區域查詢，DBSCAN算法使用了空間查詢R-樹結構。在進行聚類前，必 須建立針對所有資料的R*-樹。另外，DBSCAN要求使用者指定一個全局參數Eps(為了減少計算量，預先确定參數Minpts)。為了确定取 值，DBSCAN計算任意對象與它的第k個最臨近的對象之間的距離。然後，根據求得的距離由小到大排序，并繪出排序後的圖，稱做k-dist圖。k- dist圖中的橫坐标表示資料對象與它的第k個最近的對象間的距離；縱坐标為對應于某一k-dist距離值的資料對象的個數。R*-樹的建立和k- dist圖的繪制非常消耗時間。此外，為了得到較好的聚類結果，使用者必須根據k-dist圖，通過試探標明一個比較合适的Eps值。DBSCAN算法不進 行任何的預處理而直接對整個資料集進行聚類操作。當資料量非常大時，就必須有大記憶體量支援，I/O消耗也非常大。其時間複雜度為O(nlogn)(n為數 據量)，聚類過程的大部分時間用在區域查詢操作上。DBSCAN算法對參數Eps及Minpts非常敏感，且這兩個參數很難确定。

　　3.4 K-pototypes算法

　　K-pototypes算法結合了K-means方法和根據K-means方法改進的能夠處理符号屬性的K-modes方法，同K-means方法相比，K-pototypes 算法能夠處理符号屬性。

　　3.5 CLARANS算法

　 　CLARANS算法即随機搜尋聚類算法，是一種分割聚類方法。它首先随機選擇一個點作為目前點，然後随機檢查它周圍不超過參數Maxneighbor個 的一些鄰接點，假如找到一個比它更好的鄰接點，則把它移人該鄰接點，否則把該點作為局部最小量。然後再随機選擇一個點來尋找另一個局部最小量，直至所找到 的局部最小量數目達到使用者要求為止。該算法要求聚類的對象必須都預先調人記憶體，并且需多次掃描資料集，這對大資料量而言，無論時間複雜度還是空間複雜度都 相當大。雖通過引人R-樹結構對其性能進行改善，使之能夠處理基于磁盤的大型資料庫，但R*-樹的構造和維護代價太大。該算法對髒資料和異常資料不敏感， 但對資料物人順序異常敏感，且隻能處理凸形或球形邊界聚類。

　　3.6 CLIQUE算法

　　CLIQUE 9法即自動子空間聚類算法。該算法利用自頂向上方法求出各個子空間的聚類單元。CUQUE算法主要用于找出在高維資料空間中存在的低維聚類。為了求出d維 空間聚類，必須組合給出所有d-1維子空間的聚類，導緻其算法的空間和時間效率都較低，而且要求使用者輸入兩個參數：資料取值空間等間隔距離和密度闊值。這 2個參數與樣木資料緊密相關，使用者一般難以确定。CLIQUE算法對資料輸人順序不敏感。

4 總結

基于上述分析，我們得到各聚類算法的比較結果，結論如表1所示。

　　表1 聚類算法比較結果表

算法  算法效率 适合的資料類型 發現的聚類類型 對髒資料或異常資料的敏感性 對資料輸入順序的敏感性

BIRCH  高  數值  凸形或球形 不敏感    不太敏感

DBSCAN  一般  數值  任意形狀 敏感    敏感

CURE  較高  數值  任意形狀 不敏感    不太敏感

K-poto  一般  數值和符号 凸形或球形 敏感    一般

CLARANS 較低  數值  凸形或球形 不敏感    非常敏感

CUQUE  較低  數值  凸形或球形 一般    不敏感

　　由于每個方法都有其特點和不同的适用領域，在資料挖掘中，使用者應該根據實際需要選擇恰當的聚類算法。

參考文獻 ：[略]