數(shù)據(jù)挖掘中的聚類算法的綜述

應(yīng)劭霖

(江西省化學(xué)工業(yè)學(xué)校)

1 引言

隨著信息技術(shù)和計算機技術(shù)的迅猛發(fā)展，人們面臨著越來越多的文本、圖像、視頻以及音頻數(shù)據(jù)，為幫助用戶從這些大量數(shù)據(jù)中分析出其間所蘊涵的有價值的知識，數(shù)據(jù)挖掘(Data Mining，DM)技術(shù)應(yīng)運而生。所謂數(shù)據(jù)挖掘[1]是指從大量無序的數(shù)據(jù)中提取隱含的、有效的、可解的、對決策有潛在價值的知識和規(guī)則，為用戶提供問題求解層的決策支持能力。

聚類算法是一種有效的非監(jiān)督的機器學(xué)習(xí)算法，是數(shù)據(jù)挖掘中的一個非常重要研究課題。聚類的定義：聚類是將數(shù)據(jù)劃分成群的過程。通過確定數(shù)據(jù)之間在預(yù)先制定的屬性上的相似性來完成聚類任務(wù)，這樣最相似的數(shù)據(jù)就聚集成簇。聚類與分類的不同點：聚類的類別取決于數(shù)據(jù)本身；而分類的類別是由數(shù)據(jù)分析人員預(yù)先定義好的。

Everitt[5]關(guān)于聚類所下的定義為：一個類簇內(nèi)的實體是相似的，不同類簇的實體是不相似的；一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離；類簇可以描述為一個包含密度相對較高的點集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點集的區(qū)域與其他區(qū)域(類簇)相分離。

典型的聚類過程主要包括數(shù)據(jù)準(zhǔn)備、特征選擇和特征提取、接近度計算、聚類(或分組)、對聚類結(jié)果進行有效性評估等步驟[3]、[4]、[6]、[7]。

聚類過程：

(1)數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降維。

(2)特征選擇：從最初的特征中選擇最有效的特征，并將其存儲于向量中。

(3)特征提?。和ㄟ^對所選擇的特征進行轉(zhuǎn)換形成新的突出特征。

(4)聚類(或分組)：首先選擇合適特征類型的某種距離函數(shù)或構(gòu)造新的距離函數(shù)進行接近程度的度量，然后執(zhí)行聚類或分組。

(5)聚類結(jié)果評估：是指對聚類結(jié)果進行評估。評估主要有3種：外部有效性評估、內(nèi)部有效性評估和相關(guān)性測試評估。

當(dāng)人們使用數(shù)據(jù)挖掘工具對數(shù)據(jù)中的模型和關(guān)系進辨識的時候，通常第一個步驟就是聚類，其目的就是將集中的數(shù)人為地劃分成若干類，使簇內(nèi)相似度盡可能大、簇間相似度盡可小，以揭示這些數(shù)據(jù)分布的真實情況。但任何聚類算法都對數(shù)據(jù)本身有一定的預(yù)先假設(shè)，根據(jù)文獻[1]的理論，如果數(shù)據(jù)集本身的分布并不符合預(yù)先的假設(shè)，則算法的結(jié)果將毫無意義。因此，面對定的應(yīng)用問題，如何選擇合適的聚類算法是聚類分析研究中的重要課題。本文比較了數(shù)據(jù)挖掘中現(xiàn)有聚類算法的性能，分析它們各自的優(yōu)缺點，并指出了其今后的發(fā)展趨勢。

2 聚類算法的分類

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

本文以聚類算法所采用的基本思想為依據(jù)將它們分為四類，即層次聚類算法、分割聚類算法、基于約束的聚類算法、機器學(xué)習(xí)中的聚類算法。

2.1 層次聚類算法

層次聚類算法通過將數(shù)據(jù)組織成若干組并形成一個相應(yīng)的樹狀圖來進行聚類，它又可以分為兩類，即自底向上的聚合層次聚類和自頂向下的分裂層次聚類。聚結(jié)型算法采用自底向上的策略，首先把每個對象單獨作為一個聚類，然后根據(jù)一定的規(guī)則合并成為越來越大的聚類，直到最后所有的對象都歸入到一個聚類中。大多數(shù)層次聚類算法都屬于聚結(jié)型算法，它們之間的區(qū)別在于類間的相似度的定義不同。與聚結(jié)型算法相反，分裂型算法采用自頂向下的方法，它先將所有的對象都看成一個聚類，然后將其不斷分解直至每個對象都獨自歸入一個聚類。一般情況下不使用分裂型方法，因為在較高的層次很難進行正確的拆分。純粹的層次聚類算法的缺點在于一旦進行合并或分裂之后，就無法再進行調(diào)整?，F(xiàn)在的一些研究側(cè)重于層次聚類算法與循環(huán)的重新分配方法的結(jié)合。

主要的層次聚類算法有BIRCH，CURE，ROCK，CHAMELEON，AMOEBA，COBWEB，Clustering with Random Walks算法等。CURE算法[2]不用單個中心或?qū)ο髞泶硪粋€聚類，而是選擇數(shù)據(jù)空間中固定數(shù)目的、具有代表性的一些點共同來代表相應(yīng)的類，這樣就可以識別具有復(fù)雜形狀和不同大小的聚類，從而能很好地過濾孤立點。ROCK算法[3]是對CURE的改進，除了具有CURE算法的一些優(yōu)良特性之外，它還適用于類別屬性的數(shù)據(jù)。CHAMELEON算法[4]是Karypis等人于1999年提出來的，它在聚合聚類的過程中利用了動態(tài)建模的技術(shù)。

2.2 分割聚類算法

分割聚類算法是另外一種重要的聚類方法。它先將數(shù)據(jù)點集分為k個劃分，然后從這k個初始劃分開始，通過重復(fù)的控制策略使某個準(zhǔn)則最優(yōu)化以達到最終的結(jié)果。這類方法又可分為基于密度的聚類、基于網(wǎng)格的聚類和基于平方誤差的迭代重分配聚類。

2.2.1 基于密度的聚類

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

DBSCAN[4]是一個典型的基于密度的聚類方法，它將聚類定義為一組密度連接的點集，然后通過不斷生長足夠高密度的區(qū)域來進行聚類。DENCLUE[5]則根據(jù)數(shù)據(jù)點在屬性空間中的密度來進行聚類。從本質(zhì)上講，DENCLUE是基于密度的聚類算法與基于網(wǎng)格的預(yù)處理的結(jié)合，它受到目標(biāo)數(shù)據(jù)的維度影響較小。此外，Ankerst等人提出的OPTICS，Xu等人提出的DB-CLASD和馬帥等人提出的CURD算法也采用了基于密度的聚類思想，它們都針對數(shù)據(jù)在空間中呈現(xiàn)的不同密度分布對DB-SCAN作了相應(yīng)的改進。

2.2.2 基于網(wǎng)格的聚類

基于網(wǎng)格的聚類從對數(shù)據(jù)空間劃分的角度出發(fā)，利用屬性空間的多維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將空間劃分為有限數(shù)目的單元以構(gòu)成一個可以進行聚類分析的網(wǎng)格結(jié)構(gòu)。該方法的主要特點是處理時間與數(shù)據(jù)對象的數(shù)目無關(guān)，但與每維空間所劃分的單元數(shù)相關(guān)；而且，基于其間接的處理步驟：數(shù)據(jù)→網(wǎng)格數(shù)據(jù)→空間劃分→數(shù)據(jù)劃分，該方法還與數(shù)據(jù)的輸入順序無關(guān)。與基于密度的聚類只能處理數(shù)值屬性的數(shù)據(jù)所不同的是，基于網(wǎng)格的聚類可以處理任意類型的數(shù)據(jù)，但以降低聚類的質(zhì)量和準(zhǔn)確性為代價。

STING[6]是一個基于網(wǎng)格多分辨率的聚類方法，它將空間劃分為方形單元，不同層次的方形單元對應(yīng)不同層次的分辨率。CLIQUE[8]也是一個基于網(wǎng)格的聚類算法，它結(jié)合了網(wǎng)格聚類與密度聚類的思想，對于處理大規(guī)模高維數(shù)據(jù)具有較好的效果。除這些算法以外，以信號處理思想為基礎(chǔ)的Wave-Cluster[9]算法也屬基于網(wǎng)格聚類的范疇。

2.2.3 基于平方誤差的迭代重分配聚類

基于平方誤差的重分配聚類方法的主要思想是逐步對聚類結(jié)果進行優(yōu)化、不斷將目標(biāo)數(shù)據(jù)集向各個聚類中心進行重新分配以獲得最優(yōu)解。此類方法又可進一步分為概率聚類算法、考慮了最近鄰影響的最近鄰聚類算法以及K-medoids算法和K-means算法。

(1)概率聚類算法的重要代表是Mitchell等人于1997年提出的期望最大化算法(ExpectationMaximization，EM)[11]。它除了能處理異構(gòu)數(shù)據(jù)之外，還具有另外幾個重要的特性：①能處理具有復(fù)雜結(jié)構(gòu)的記錄；②能夠連續(xù)處理成批的數(shù)據(jù)；③具有在線處理能力；④產(chǎn)生的聚類結(jié)果易于解釋。

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

(3)K-means算法是目前為止應(yīng)用最為廣泛的一種聚類方法，其每個類別均用該類中所有數(shù)據(jù)的平均值(或加權(quán)平均)來表示，這個平均值即被稱作聚類中心。該方法雖然不能用于類別屬性的數(shù)據(jù)，但對于數(shù)值屬性的數(shù)據(jù)，它能很好地體現(xiàn)聚類在幾何和統(tǒng)計學(xué)上的意義。但是，原始K-means算法也存在如下缺陷：①聚類結(jié)果的好壞依賴于對初始聚類中心的選擇；②容易陷入局部最優(yōu)解；③對K值的選擇沒有準(zhǔn)則可依循；④對異常數(shù)據(jù)較為敏感；⑤只能處理數(shù)值屬性的數(shù)據(jù)；⑥聚類結(jié)果可能不平衡。

為克服原始K-means算法存在的不足，研究者從各自不同的角度提出了一系列K-means的變體，如Bradley和Fayyad等人從降低聚類結(jié)果對初始聚類中心的依賴程度入手對它作了改進，同時也使該算法能適用于大規(guī)模的數(shù)據(jù)集[15]；Dhillon等人則通過調(diào)整迭代過程中重新計算聚類中心的方法使其性能得到了提高[10]。

2.3 基于約束的聚類算法

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

2.4 機器學(xué)習(xí)中的聚類算法

機器學(xué)習(xí)中的聚類算法是指與機器學(xué)習(xí)相關(guān)、采用了某些機器學(xué)習(xí)理論的聚類方法，它主要包括人工神經(jīng)網(wǎng)絡(luò)方法以及基于進化理論的方法。

自組織映射(Self-Organizing Map，SOM)[9]是利用人工神經(jīng)網(wǎng)絡(luò)進行聚類的較早嘗試，它也是向量量化方法的典型代表之一。該方法具有兩個主要特點：①它是一種遞增的方法，即所有的數(shù)據(jù)點是逐一進行處理的；②它能將聚類中心點映射到一個二維的平面上，從而實現(xiàn)可視化。此外，文獻[10]中提出的一種基于投影自適應(yīng)諧振理論的人工神經(jīng)網(wǎng)絡(luò)聚類也具有很好的性能。

在基于進化理論的聚類方法中，模擬退火的應(yīng)用較為廣泛，SINICC算法[7]就是其中之一。在模擬退火中經(jīng)常使用到“微擾因子”，其作用等同于把一個點從當(dāng)前的聚類重新分配到一個隨機選擇的新類別中，這與K-means中采用的機制有些類似。遺傳算法也可以用于聚類處理，它主要通過選擇、交叉和變異這三種遺傳算子的運算以不斷優(yōu)化可選方案從而得到最終的聚類結(jié)果。

3 幾個典型的聚類算法

3.1 BIRCH算法

BIRCH是一個層次聚類方法，它利用層次方法的平衡迭代進行聚類。其核心是用一個聚類特征三元組表示一個簇的有關(guān)信息，從而使一簇點的表示可用對應(yīng)的聚類特征。它通過構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹來求聚類。該算法通過聚類特征可以方便地進行中心、半徑、直徑及類內(nèi)、類間距離的運算。算法具有對象數(shù)目的線性易伸縮性，及良好的聚類質(zhì)量。一次掃描就可以進行較好的聚類，其計算復(fù)雜度為O(n)。

3.2 DBSCAN算法

DBSCAN是基于密度的聚類算法，可以將足夠高密度的區(qū)域分為簇，并可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的類。該算法利用類的密度連通性可以快速發(fā)現(xiàn)任意形狀的類?；舅枷胧牵簩τ谝粋€類中的每個對象，在其給定半徑的領(lǐng)域中包含的對象不能少于某一給定的最小數(shù)目。DBSCAN算法不進行任何的預(yù)處理而直接對整個數(shù)據(jù)集進行聚類操作。當(dāng)數(shù)據(jù)量非常大時，就必須有大量內(nèi)存支持，I/O消耗也非常大。其時間復(fù)雜度為O(nlogn)，聚類過程的大部分時間用在區(qū)域查詢操作上。

DBSCAN算法能夠發(fā)現(xiàn)空間數(shù)據(jù)庫中任意形狀的密度連通集；在給定合適的參數(shù)條件下，能很好地處理噪聲點；對用戶領(lǐng)域知識要求較少；對數(shù)據(jù)的輸入順序不太敏感；適用于大型數(shù)據(jù)庫。但DBSCAN算法要求事先指定領(lǐng)域和閾值，具體使用的參數(shù)依賴于應(yīng)用的目的。

3.3 CLARANS算法

CLARANS通過利用多次不同抽樣改進了CLARA算法，是一種k-中心點聚類方法。它首先隨機選擇一個點作為當(dāng)前點，然后隨機檢查它周圍不超過參數(shù)Maxeighbar個的一些鄰接點。假如找到一個比它更好的鄰接點，則把它移入該鄰接點，否則把該點作為局部最小量。然后再隨機選擇一個點來尋找另一個局部最小量，直至所找到的局部最小量數(shù)目達到用戶要求為止。該算法要求聚類的對象必須預(yù)先調(diào)入內(nèi)存，并且需多次掃描數(shù)據(jù)集，其時空復(fù)雜度都相當(dāng)大，雖通過引入R*—樹結(jié)構(gòu)對其性能進行改善，但構(gòu)造和維護代價太大。該算法對“臟數(shù)據(jù)”和“異常數(shù)據(jù)”不敏感，但對數(shù)據(jù)輸入順序異常敏感，且只能處理凸形或球形邊界聚類，效率較高。

4 現(xiàn)有聚類算法的性能比較

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

總體來說，分割聚類算法的應(yīng)用最為廣泛，其收斂速度快，且能夠擴展以用于大規(guī)模的數(shù)據(jù)集；缺點在于它傾向于識別凸形分布、大小相近、密度相近的聚類，而不能發(fā)現(xiàn)形狀比較復(fù)雜的聚類，并且初始聚類中心的選擇和噪聲數(shù)據(jù)會對聚類結(jié)果產(chǎn)生較大的影響。層次聚類方法不僅適用于任意屬性和任意形狀的數(shù)據(jù)集，還可以靈活控制不同層次的聚類粒度，因此具有較強的聚類能力，但它大大延長了算法的執(zhí)行時間；此外，對層次聚類算法中已經(jīng)形成的聚類結(jié)構(gòu)不能進行回溯處理?；诩s束的聚類通常只用于處理某些特定應(yīng)用領(lǐng)域中的特定需求。機器學(xué)習(xí)中的人工神經(jīng)網(wǎng)絡(luò)和模擬退火等方法雖然能利用相應(yīng)的啟發(fā)式算法獲得較高質(zhì)量的聚類結(jié)果，但其計算復(fù)雜度往往較高，同時其聚類結(jié)果的好壞也依賴于對某些經(jīng)驗參數(shù)的選取。在針對高維數(shù)據(jù)的子空間聚類和聯(lián)合聚類等算法中，雖然通過在聚類過程中選維、逐維聚類和降維從一定程度上減少了高維度帶來的影響，但它們均不可避免地帶來了原始數(shù)據(jù)信息的損失和相應(yīng)的聚類準(zhǔn)確性的降低。因此，尋求這類算法在聚類質(zhì)量和算法時間復(fù)雜度之間的折中也是一個重要的問題。

總之，雖然一些算法相對其他方法在某些方面的性能有了一定程度的提高，但它不可能在任何應(yīng)用背景下均具有很好的結(jié)果，各有各的優(yōu)勢和不足。因此對于它們的改進還有一個相當(dāng)大的空間。

5 總結(jié)與展望

通過以上的分析得知，沒有一種算法是十全十美的，建議使用者根據(jù)實際情況，例如發(fā)現(xiàn)聚類的形狀、數(shù)據(jù)輸入順序是否敏感、適用數(shù)據(jù)庫的大小或者算法效率，來選擇聚類算法。

一般情況下有以下結(jié)論：

(1)目標(biāo)數(shù)據(jù)庫如果比較大，建議使用綜合性的聚類算法，如：BIRCH、CURE、DBSCAN和STING等，以提高算法效率。

(2)如果聚類的形狀是球形或者凸形，BIRCH和CLARANS比較適合。

(3)一般而言，聚類算法對數(shù)據(jù)輸入的順序都比較敏感。如果希望不敏感，可以選用基于網(wǎng)格的STING算法。

(4)將不同類型的聚類算法相互結(jié)合(例如BIRCH算法和CURE算法)，綜合各自的優(yōu)點，以滿足不同的聚類要求。是今后聚類算法的一個重要發(fā)展方向。

聚類分析是數(shù)據(jù)挖掘中一種非常有用的技術(shù)，它可作為特征和分類算法的預(yù)處理步驟，也可將聚類結(jié)果用于進一步關(guān)聯(lián)分析，還可以作為一個獨立的工具來獲得數(shù)據(jù)分布的情況。聚類算法的研究具有廣泛的應(yīng)用前景，其今后的發(fā)展也面臨著越來越多的挑戰(zhàn)。首先是聚類算法的選擇，建議使用者根據(jù)實際情況(例如發(fā)現(xiàn)聚類的形狀、數(shù)據(jù)輸入順序是否敏感、適用數(shù)據(jù)庫的大小或者算法效率)來選擇合適的聚類算法。其次，對于特征數(shù)據(jù)本身所具備的高維性、復(fù)雜性、動態(tài)性以及容易達到大規(guī)模的特性，聚類算法的設(shè)計還應(yīng)該更多地考慮融合不同的聚類思想形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點。

[1]蔡偉杰,張曉輝,朱建秋,朱揚勇.關(guān)聯(lián)規(guī)則挖掘綜述,2004.

[2]薛惠鋒,張文宇,寇曉東.智能數(shù)據(jù)挖掘技術(shù).西安:西北工業(yè)大學(xué)出版社,2005.

[3]王光宏,蔣平.數(shù)據(jù)挖掘綜述.同濟大學(xué)學(xué)報.2004年2月.

[4]Han J W,Micheline K.數(shù)據(jù)挖掘概念與技術(shù).范明,孟曉峰譯.北京：機械工業(yè)出版社,2001.

[5]夏火松,數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)[M]北京:科學(xué)出版社,2004.

[6]蘇新寧,楊建林,鄧三鴻,等.數(shù)據(jù)挖掘理論與技術(shù)[M].北京:科學(xué)技術(shù)文獻出版社.2003:53～65.

[7]陳京明著.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù).北京:電子工業(yè)出版,2004.8.

[8]Mehmed Kantardzic.數(shù)據(jù)挖掘—概念、模型、方法和算法[M].陳茵,程雁譯北京:清華大學(xué)出版社.2003.

[9]Pearl J.Data Mining with Graphical Models[D].Computer Science Dept.Standford University.2000.

[10]GantiV,Gehrke J,RamakrishnaR. CACTUS-ClusteringCategorical DataUsing Summaries[C].San Diego:Proceedings of the 5th ACMSIGKDD,1999.73-83.

[11]TungAKH,Hou J,Han J.SpatialClustering in the Presence ofOb-stacles[C].Heidelberg: Proceedings of the 17th ICDE,2001.359-367.

[12]Han J,KamberM,TungA KH.SpatialClusteringMethods in Data Mining:A Survey[C]. GeographicDataMining andKnowledgeDis-covery,2001.