聚類(lèi)分析中幾種算法的比較

將數(shù)據(jù)庫(kù)中的對(duì)象進(jìn)行聚類(lèi)是聚類(lèi)分析的基本操作，其準(zhǔn)則是使屬于同一類(lèi)的個(gè)體間距離盡可能小，而不同類(lèi)個(gè)體間距離盡可能大，為了找到效率高、通用性強(qiáng)的聚 類(lèi)方法人們從不同角度提出了近百種聚類(lèi)方法，典型的有K-means方法、K-medoids方法、CLARANS方法,BIRCH方法等，這些算法適用 于特定的問(wèn)題及用戶(hù)。本文綜合提出了評(píng)價(jià)聚類(lèi)算法好壞的5個(gè)標(biāo)準(zhǔn)，基于這5個(gè)標(biāo)準(zhǔn)，對(duì)數(shù)據(jù)挖掘中常用聚類(lèi)方法作了比較分析，以便于人們更容易、更快捷地找 到一種適用于特定問(wèn)題及用戶(hù)的聚類(lèi)算法。

聚類(lèi)算法研究及比較框架
　　聚類(lèi)算法一般有五種方法，最主要的是劃分方法和層次方法兩種。劃分聚類(lèi)算法通過(guò)優(yōu)化評(píng)價(jià)函數(shù)把數(shù)據(jù)集分割為K個(gè)部分，它需要K作為 輸人參數(shù)。典型的分割聚類(lèi)算法有K-means算法, K-medoids算法、CLARANS算法。層次聚類(lèi)由不同層次的分割聚類(lèi)組成，層次之間的分割具有嵌套的關(guān)系。它不需要輸入?yún)?shù)，這是它優(yōu)于分割聚類(lèi) 算法的一個(gè)明顯的優(yōu)點(diǎn)，其缺點(diǎn)是終止條件必須具體指定。典型的分層聚類(lèi)算法有BIRCH算法、DBSCAN算法和CURE算法等。
　　對(duì)各聚類(lèi)算法的比較研究基于以下5個(gè)標(biāo)準(zhǔn)：
　?、?是否適用于大數(shù)據(jù)量，算法的效率是否滿(mǎn)足大數(shù)據(jù)量高復(fù)雜性的要求;
　?、?是否能應(yīng)付不同的數(shù)據(jù)類(lèi)型，能否處理符號(hào)屬性;
　?、?是否能發(fā)現(xiàn)不同類(lèi)型的聚類(lèi);
　　④ 是否能應(yīng)付臟數(shù)據(jù)或異常數(shù)據(jù);
　?、?是否對(duì)數(shù)據(jù)的輸入順序不敏感。
　　下面將在該框架下對(duì)各聚類(lèi)算法作分析比較。

數(shù)據(jù)挖掘常用聚類(lèi)算法比較分析 
    3.1 K-pototypes算法
　　K-pototypes算法結(jié)合了K-means方法和根據(jù)K-means方法改進(jìn)的能夠處理符號(hào)屬性的K-modes方法，同K-means方法相比，K-pototypes 算法能夠處理符號(hào)屬性。

3.2 CLARANS算法（劃分方法）
　　CLARANS算法即隨機(jī)搜索聚類(lèi)算法，是一種分割聚類(lèi)方法。它首先隨機(jī)選擇一個(gè)點(diǎn)作為當(dāng)前點(diǎn)，然后隨機(jī)檢查它周?chē)怀^(guò)參數(shù)Maxneighbor 個(gè)的一些鄰接點(diǎn)，假如找到一個(gè)比它更好的鄰接點(diǎn)，則把它移人該鄰接點(diǎn)，否則把該點(diǎn)作為局部最小量。然后再隨機(jī)選擇一個(gè)點(diǎn)來(lái)尋找另一個(gè)局部最小量，直至所找 到的局部最小量數(shù)目達(dá)到用戶(hù)要求為止。該算法要求聚類(lèi)的對(duì)象必須都預(yù)先調(diào)人內(nèi)存，并且需多次掃描數(shù)據(jù)集，這對(duì)大數(shù)據(jù)量而言，無(wú)論時(shí)間復(fù)雜度還是空間復(fù)雜度 都相當(dāng)大。雖通過(guò)引人R-樹(shù)結(jié)構(gòu)對(duì)其性能進(jìn)行改善，使之能夠處理基于磁盤(pán)的大型數(shù)據(jù)庫(kù)，但R*-樹(shù)的構(gòu)造和維護(hù)代價(jià)太大。該算法對(duì)臟數(shù)據(jù)和異常數(shù)據(jù)不敏 感，但對(duì)數(shù)據(jù)物人順序異常敏感，且只能處理凸形或球形邊界聚類(lèi)。

3.3 BIRCH算法（層次方法）
　　BIRCH算法即平衡迭代削減聚類(lèi)法，其核心是用一個(gè)聚類(lèi)特征3元組表示一個(gè)簇的有關(guān)信息，從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類(lèi)特征，而不必用具體的一 組點(diǎn)來(lái)表示。它通過(guò)構(gòu)造滿(mǎn)足分支因子和簇直徑限制的聚類(lèi)特征樹(shù)來(lái)求聚類(lèi)。BIRCH算法通過(guò)聚類(lèi)特征可以方便地進(jìn)行中心、半徑、直徑及類(lèi)內(nèi)、類(lèi)間距離的運(yùn) 算。算法的聚類(lèi)特征樹(shù)是一個(gè)具有兩個(gè)參數(shù)分枝因子B和類(lèi)直徑T的高度平衡樹(shù)。分枝因子規(guī)定了樹(shù)的每個(gè)節(jié)點(diǎn)子女的最多個(gè)數(shù)，而類(lèi)直徑體現(xiàn)了對(duì)一類(lèi)點(diǎn)的直徑大 小的限制即這些點(diǎn)在多大范圍內(nèi)可以聚為一類(lèi)，非葉子結(jié)點(diǎn)為它的子女的最大關(guān)鍵字，可以根據(jù)這些關(guān)鍵字進(jìn)行插人索引，它總結(jié)了其子女的信息。
　　聚類(lèi)特征樹(shù)可以動(dòng)態(tài)構(gòu)造，因此不要求所有數(shù)據(jù)讀人內(nèi)存，而可以在外存上逐個(gè)讀人。新的數(shù)據(jù)項(xiàng)總是插人到樹(shù)中與該數(shù)據(jù)距離最近的葉子中。如果插人后使得 該葉子的直徑大于類(lèi)直徑T，則把該葉子節(jié)點(diǎn)分裂。其它葉子結(jié)點(diǎn)也需要檢查是否超過(guò)分枝因子來(lái)判斷其分裂與否，直至該數(shù)據(jù)插入到葉子中，并且滿(mǎn)足不超過(guò)類(lèi)直 徑，而每個(gè)非葉子節(jié)點(diǎn)的子女個(gè)數(shù)不大于分枝因子。算法還可以通過(guò)改變類(lèi)直徑修改特征樹(shù)大小，控制其占內(nèi)存容量。
　　BIRCH算法通過(guò)一次掃描就可以進(jìn)行較好的聚類(lèi)，由此可見(jiàn)，該算法適合于大數(shù)據(jù)量。對(duì)于給定的M兆內(nèi)存空間，其空間復(fù)雜度為O(M)，時(shí)間間復(fù)雜度 為O(dNBlnB(M/P)).其中d為維數(shù),N為節(jié)點(diǎn)數(shù),P為內(nèi)存頁(yè)的大小，B為由P決定的分枝因子。I/O花費(fèi)與數(shù)據(jù)量成線(xiàn)性關(guān)系。BIRCH算法 只適用于類(lèi)的分布呈凸形及球形的情況，并且由于BIRCH算法需提供正確的聚類(lèi)個(gè)數(shù)和簇直徑限制，對(duì)不可視的高維數(shù)據(jù)不可行。
　　3.4 CURE算法（層次方法）
　　CURE算法即使用代表點(diǎn)的聚類(lèi)方法。該算法先把每個(gè)數(shù)據(jù)點(diǎn)看成一類(lèi)，然后合并距離最近的類(lèi)直至類(lèi)個(gè)數(shù)為所要求的個(gè)數(shù)為止。CURE算法將傳統(tǒng)對(duì)類(lèi)的 表示方法進(jìn)行了改進(jìn)，回避了用所有點(diǎn)或用中心和半徑來(lái)表示一個(gè)類(lèi)，而是從每一個(gè)類(lèi)中抽取固定數(shù)量、分布較好的點(diǎn)作為描述此類(lèi)的代表點(diǎn)，并將這些點(diǎn)乘以一個(gè) 適當(dāng)?shù)氖湛s因子，使它們更靠近類(lèi)的中心點(diǎn)。將一個(gè)類(lèi)用代表點(diǎn)表示，使得類(lèi)的外延可以向非球形的形狀擴(kuò)展，從而可調(diào)整類(lèi)的形狀以表達(dá)那些非球形的類(lèi)。另外， 收縮因子的使用減小了嗓音對(duì)聚類(lèi)的影響。CURE算法采用隨機(jī)抽樣與分割相結(jié)合的辦法來(lái)提高算法的空間和時(shí)間效率，并且在算法中用了堆和K-d樹(shù)結(jié)構(gòu)來(lái)提 高算法效率。
　　3.5 DBSCAN算法（基于密度的方法）
　　DBSCAN算法即基于密度的聚類(lèi)算法。該算法利用類(lèi)的密度連通性可以快速發(fā)現(xiàn)任意形狀的類(lèi)。其基本思想是：對(duì)于一個(gè)類(lèi)中的每個(gè)對(duì)象，在其給定半徑的 領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。在DBSCAN算法中，發(fā)現(xiàn)一個(gè)類(lèi)的過(guò)程是基于這樣的事實(shí)：一個(gè)類(lèi)能夠被其中的任意一個(gè)核心對(duì)象所確定。為 了發(fā)現(xiàn)一個(gè)類(lèi)，DBSCAN先從對(duì)象集D中找到任意一對(duì)象P，并查找D中關(guān)于關(guān)徑Eps和最小對(duì)象數(shù)Minpts的從P密度可達(dá)的所有對(duì)象。如果P是核心 對(duì)象，即半徑為Eps的P的鄰域中包含的對(duì)象不少于Minpts,則根據(jù)算法，可以找到一個(gè)關(guān)于參數(shù)Eps和Minpts的類(lèi)。如果P是一個(gè)邊界點(diǎn)，則半 徑為Eps的P鄰域包含的對(duì)象少于Minpts，P被暫時(shí)標(biāo)注為噪聲點(diǎn)。然后，DBSCAN處理D中的下一個(gè)對(duì)象。
　　密度可達(dá)對(duì)象的獲取是通過(guò)不斷執(zhí)行區(qū)域查詢(xún)來(lái)實(shí)現(xiàn)的。一個(gè)區(qū)域查詢(xún)返回指定區(qū)域中的所有對(duì)象。為了有效地執(zhí)行區(qū)域查詢(xún)，DBSCAN算法使用了空間查 詢(xún)R-樹(shù)結(jié)構(gòu)。在進(jìn)行聚類(lèi)前，必須建立針對(duì)所有數(shù)據(jù)的R*-樹(shù)。另外，DBSCAN要求用戶(hù)指定一個(gè)全局參數(shù)Eps(為了減少計(jì)算量，預(yù)先確定參數(shù) Minpts)。為了確定取值，DBSCAN計(jì)算任意對(duì)象與它的第k個(gè)最臨近的對(duì)象之間的距離。然后，根據(jù)求得的距離由小到大排序，并繪出排序后的圖，稱(chēng) 做k-dist圖。k-dist圖中的橫坐標(biāo)表示數(shù)據(jù)對(duì)象與它的第k個(gè)最近的對(duì)象間的距離；縱坐標(biāo)為對(duì)應(yīng)于某一k-dist距離值的數(shù)據(jù)對(duì)象的個(gè)數(shù)。 R*-樹(shù)的建立和k-dist圖的繪制非常消耗時(shí)間。此外，為了得到較好的聚類(lèi)結(jié)果，用戶(hù)必須根據(jù)k-dist圖，通過(guò)試探選定一個(gè)比較合適的Eps值。 DBSCAN算法不進(jìn)行任何的預(yù)處理而直接對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類(lèi)操作。當(dāng)數(shù)據(jù)量非常大時(shí)，就必須有大內(nèi)存量支持，I/O消耗也非常大。其時(shí)間復(fù)雜度為 O(nlogn)(n為數(shù)據(jù)量)，聚類(lèi)過(guò)程的大部分時(shí)間用在區(qū)域查詢(xún)操作上。DBSCAN算法對(duì)參數(shù)Eps及Minpts非常敏感，且這兩個(gè)參數(shù)很難確定。
　　3.6 CLIQUE算法（綜合了基于密度和基于網(wǎng)格的算法）
　　CLIQUE算法即自動(dòng)子空間聚類(lèi)算法。該算法利用自頂向上方法求出各個(gè)子空間的聚類(lèi)單元。CLUQUE算法主要用于找出在高維數(shù)據(jù)空間中存在的低維 聚類(lèi)。為了求出d維空間聚類(lèi)，必須組合給出所有d-1維子空間的聚類(lèi)，導(dǎo)致其算法的空間和時(shí)間效率都較低，而且要求用戶(hù)輸入兩個(gè)參數(shù)：數(shù)據(jù)取值空間等間隔 距離和密度闊值。這2個(gè)參數(shù)與樣木數(shù)據(jù)緊密相關(guān)，用戶(hù)一般難以確定。CLIQUE算法對(duì)數(shù)據(jù)輸人順序不敏感。

4 總結(jié)
基于上述分析，我們得到各聚類(lèi)算法的比較結(jié)果，結(jié)論如下：　
算法 算法效率 適合的數(shù)據(jù)類(lèi)型 發(fā)現(xiàn)的聚類(lèi)類(lèi)型 對(duì)臟數(shù)據(jù)或異常數(shù)據(jù)的敏感性 對(duì)數(shù)據(jù)輸入順序的敏感性
BIRCH       高          數(shù)值             凸形或球形            不敏感                  不太敏感
DBSCAN   一般         數(shù)值            任意形狀                敏感                       敏感
CURE       較高         數(shù)值           任意形狀               不敏感                  不太敏感
K-poto     一般      數(shù)值和符號(hào)      凸形或球形             敏感                     一般
CLARANS 較低         數(shù)值            凸形或球形            不敏感                 非常敏感
CUQUE    較低         數(shù)值             凸形或球形             一般                    不敏感
由于每個(gè)方法都有其特點(diǎn)和不同的適用領(lǐng)域，在數(shù)據(jù)挖掘中，用戶(hù)應(yīng)該根據(jù)實(shí)際需要選擇恰當(dāng)?shù)木垲?lèi)算法。