NO IMAGE

《計算機應用與軟體》2003 Vol.20 No.2 : 5~6

資料探勘中聚類演算法比較研究
張紅雲 劉向東 段曉東 苗奪謙 馬垣
(同濟大學電子與資訊工程學院 上海 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  較低                 數值                     凸形或球形                    一般                                           不敏感


  由於每個方法都有其特點和不同的適用領域,在資料探勘中,使用者應該根據實際需要選擇恰當的聚類演算法。

參考文獻:[略]