各種聚類算法及改進算法的研究

摘要：該文詳細闡述了數(shù)據(jù)挖掘領域的常用聚類算法及改進算法，并比較分析了其優(yōu)缺點，提出了數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅赋龈髯缘奶攸c，以便于人們更快、更容易地選擇一種聚類算法解決特定問題和對聚類算法作進一步的研究。并給出了相應的算法評價標準、改進建議和聚類分析研究的熱點、難點。上述工作將為聚類分析和數(shù)據(jù)挖掘等研究提供有益的參考。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類算法；聚類分析

中圖法分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)25-1539-03

Research Of Various Clustering Algorithm And Its Improved Algorithm

WANG An-zhi， LI Ming-dong， LI Chao

(Computer College， China West Normal University， Nanchong 637002， China)

Abstract: This paper summarizes the basic principles of the clustering algorithm， describes each kind of clustering algorih m in detail， makes comparative analysis on their advantages and disadvantages， puts forward the typical requests of clustering， points out their characteristics so that people can easily find a clustering method that suit a special problem and research further on the clustering algorithm. Finally， the research hotspot， difficulty and and improved advices of the data clustering are addressed. The above work can give a valuable reference for data clustering and data mining.

Key words: data mining; clustering algorithm; clustering analys

1 引言

隨著經(jīng)濟社會和科學技術(shù)的高速發(fā)展，各行各業(yè)積累的數(shù)據(jù)量急劇增長，如何從海量的數(shù)據(jù)中提取有用的信息成為當務之急。聚類是將數(shù)據(jù)劃分成群組的過程，即把數(shù)據(jù)對象分成多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。它對未知數(shù)據(jù)的劃分和分析起著非常有效的作用。通過聚類，能夠識別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。為了找到效率高、通用性強的聚類方法人們從不同角度提出了許多種聚類算法，一般可分為基于層次的，基于劃分的，基于密度的，基于網(wǎng)格的和基于模型的五大類。

2 數(shù)據(jù)挖掘?qū)垲愃惴ǖ囊?/p>

(1)可兼容性：要求聚類算法能夠適應并處理屬性不同類型的數(shù)據(jù)。(2)可伸縮性：要求聚類算法對大型數(shù)據(jù)集和小數(shù)據(jù)集都適用。(3)對用戶專業(yè)知識要求最小化。(4)對數(shù)據(jù)類別簇的包容性：即聚類算法不僅能在用基本幾何形式表達的數(shù)據(jù)上運行得很好，還要在以其他更高維度形式表現(xiàn)的數(shù)據(jù)上同樣也能實現(xiàn)。(5)能有效識別并處理數(shù)據(jù)庫的大量數(shù)據(jù)中普遍包含的異常值，空缺值或錯誤的不符合現(xiàn)實的數(shù)據(jù)。(6)聚類結(jié)果既要滿足特定約束條件，又要具有良好聚類特性，且不丟失數(shù)據(jù)的真實信息。(7)可讀性和可視性：能利用各種屬性如顏色等以直觀形式向用戶顯示數(shù)據(jù)挖掘的結(jié)果。(8)處理噪聲數(shù)據(jù)的能力。(9)算法能否與輸入順序無關(guān)。

3 各種聚類算法介紹

隨著人們對數(shù)據(jù)挖掘的深入研究和了解，各種聚類算法的改進算法也相繼提出，很多新算法在前人提出的算法中做了某些方面的提高和改進，且很多算法是有針對性地為特定的領域而設計。某些算法可能對某類數(shù)據(jù)在可行性、效率、精度或簡單性上具有一定的優(yōu)越性，但對其它類型的數(shù)據(jù)或在其他領域應用中則不一定還有優(yōu)勢。所以，我們必須清楚地了解各種算法的優(yōu)缺點和應用范圍，根據(jù)實際問題選擇合適的算法。

3.1 基于層次的聚類算法

基于層次的聚類算法對給定數(shù)據(jù)對象進行層次上的分解，可分為凝聚算法和分裂算法。

(1)自底向上的凝聚聚類方法。這種策略是以數(shù)據(jù)對象作為原子類，然后將這些原子類進行聚合。逐步聚合成越來越大的類，直到滿足終止條件。凝聚算法的過程為：在初始時，每一個成員都組成一個單獨的簇，在以后的迭代過程中，再把那些相互鄰近的簇合并成一個簇，直到所有的成員組成一個簇為止。其時間和空間復雜性均為O(n2)。通過凝聚式的方法將兩簇合并后，無法再將其分離到之前的狀態(tài)。在凝聚聚類時，選擇合適的類的個數(shù)和畫出原始數(shù)據(jù)的圖像很重要。

(2)自頂向下分裂聚類方法。與凝聚法相反，該法先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終結(jié)條件。其主要思想是將那些成員之間不是非常緊密的簇進行分裂。跟凝聚式方法的方向相反，從一個簇出發(fā)，一步一步細化。它的優(yōu)點在于研究者可以把注意力集中在數(shù)據(jù)的結(jié)構(gòu)上面。一般情況下不使用分裂型方法，因為在較高的層很難進行正確的拆分。

3.2 基于密度的聚類算法

很多算法都使用距離來描述數(shù)據(jù)之間的相似性，但對于非凸數(shù)據(jù)集，只用距離來描述是不夠的。此時可用密度來取代距離描述相似性，即基于密度的聚類算法。它不是基于各種各樣的距離，所以能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。其指導思想是：只要一個區(qū)域中的點的密度（對象或數(shù)據(jù)點的數(shù)目）大過某個閾值，就把它加到與之相近的聚類中去。該法從數(shù)據(jù)對象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來，從而可發(fā)現(xiàn)任意形狀的簇，并可用來過濾“噪聲”數(shù)據(jù)。常見算法有DBSCAN，DENCLUE等。

3.3 基于劃分的聚類算法

給定一個N個對象的元組或數(shù)據(jù)庫，根據(jù)給定要創(chuàng)建的劃分的數(shù)目k，將數(shù)據(jù)劃分為k個組，每個組表示一個簇類（<=N）時滿足如下兩點：(1)每個組至少包含一個對象；(2)每個對象必須屬于且只屬于一個組。算法先隨機創(chuàng)建一個初始劃分，然后采用一種迭代的重定位技術(shù)，通過將對象根據(jù)簇類之間的差異從一個劃分移到另一個劃分來提高簇類內(nèi)數(shù)據(jù)之間的相似程度。一種好的劃分的一般準則是：在同一個類中的對象盡可能“接近”或相似，而不同類中的對象盡可能“遠離”或不同。為了達到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。典型的劃包括：K-means，PAM，EM等。劃分法收斂速度快，在對中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用。缺點是它傾向于識別凸形分布大小相近、密度相近的聚類，不能發(fā)現(xiàn)分布形狀比較復雜的聚類，它要求類別數(shù)目k可以合理地估計，且初始中心的選擇和噪聲會對聚類結(jié)果產(chǎn)生很大影響。還要求用戶預先指定聚類個數(shù)。

3.4 基于網(wǎng)格的聚類算法

首先將數(shù)據(jù)空間量化為有限個單元的網(wǎng)格結(jié)構(gòu)，然后對量化后的單個的單元為對象進行聚類。典型的算法有STING，CLIQUE等。網(wǎng)格聚類法處理速度快，處理時間與數(shù)據(jù)對象的數(shù)目無關(guān)，一般由網(wǎng)格單元的數(shù)目決定。缺點是只能發(fā)現(xiàn)邊界是水平或垂直的聚類，不能檢測到斜邊界。該類算法也不適用于高維情況，因為網(wǎng)格單元的數(shù)目隨著維數(shù)的增加而呈指數(shù)增長。另外還有下列問題： 一是如何選擇合適的單元大小和數(shù)目，二是怎樣對每個單元中對象的信息進行匯總，三是存在量化尺度的問題。

3.5 基于模型的聚類算法

基于模型的方法給每一個聚簇假定了一個模型，然后去尋找能夠很好滿足這個模型的數(shù)據(jù)集。這個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)，它由一系列的概率分布決定，也可能通過基于標準的統(tǒng)計數(shù)字自動決定聚類的數(shù)目。它的一個潛在假定是：目標數(shù)據(jù)集是由一系列的概率分布所決定的。一般有2種嘗試方向：統(tǒng)計的方案和神經(jīng)網(wǎng)絡的方案。COBWEB是一種流行的簡單增量概念聚類算法，以一個分類樹的形式來創(chuàng)建層次聚類，它的輸入對象用分類屬性-值對來描述。COBWEB的優(yōu)點為：可以自動修正劃分中類的數(shù)目；不需要用戶提供輸入?yún)?shù)。缺點為：COBWEB基于這樣一個假設：在每個屬性上的概率分布是彼此獨立的。但這個假設并不總是成立。且對于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導致時間和空間復雜性的劇烈變化，不適用于聚類大型數(shù)據(jù)庫的數(shù)據(jù)。

3.6 模糊聚類算法

現(xiàn)實中很多對象沒有嚴格的屬性，其類屬和形態(tài)存在著中介性，適合軟劃分。恰好模糊聚類具有描述樣本類屬中間性的優(yōu)點，因此成為當今聚類分析研究的主流。常用的模糊聚類有動態(tài)直接聚類法、最大樹法、FCM等。基本原理為：假設有N個要分析的樣本，每個樣本有M個可量化的指標，一般步驟為：(1)標準化數(shù)據(jù)：常用的數(shù)據(jù)標準化方法有：小數(shù)定標規(guī)范化，最大最小值規(guī)范化，標準差規(guī)范化等。(2)建立模糊相似矩陣，標定相似系數(shù)。(3)計算多極相似矩陣，計算整體相似關(guān)系矩陣，有傳遞閉包法，動態(tài)直接聚類法，最大樹法等。(4)給定一個聚類水平，計算絕對相似矩陣。按行列調(diào)整絕對相似矩陣，每個分塊即為一個分類。

3.6.1 模糊C-均值聚類算法

FCM算法用隸屬度確定每個樣本屬于某個聚類的程度。它與K平均算法和中心點算法等相比，計算量可大大減少，因為它省去了多重迭代的反復計算過程，效率將大大提高。同時，模糊聚類分析可根據(jù)數(shù)據(jù)庫中的相關(guān)數(shù)據(jù)計算形成模糊相似矩陣，形成相似矩陣之后，直接對相似矩陣進行處理即可，無須多次反復掃描數(shù)據(jù)庫。根據(jù)實驗要求動態(tài)設定m值，以滿足不同類型數(shù)據(jù)挖掘任務的需要，適于高維度的數(shù)據(jù)的處理，具有較好的伸縮性，便于找出異常點。但m值根據(jù)經(jīng)驗或者實驗得來，具有不確定性，可能影響實驗結(jié)果。并且，由于梯度法的搜索方向總是沿著能量減小的方向，使得算法存在易陷入局部極小值和對初始化敏感的缺點。為克服上述缺點，可在FCM算法中引入全局尋優(yōu)法來擺脫FCM聚類運算時可能陷入的局部極小點，優(yōu)化聚類效果。

3.6.2 免疫進化算法

該算法借鑒生命科學中的免疫概念和理論在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征或知識來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象。免疫算法的核心在于免疫算子的構(gòu)造，通過接種疫苗或免疫選擇兩個步驟來完成。免疫進化算法能提高個體的適應度和防止群體的退化，從而達到減輕原有進化算法后期的波動現(xiàn)象和提高收斂速度。例如IFCM、IFCL算法。它們既較大地提高了獲取全局最優(yōu)的概率，又減輕了基于遺傳聚類算法在遺傳后期的波動現(xiàn)象。進一步的工作是參數(shù)的適當選取和減小運行時間等。人對于客觀事物的識別往往只通過一些模糊信息的綜合，便可以獲得足夠精確的定論。

3.7 其它聚類算法

3.7.1 基于群的聚類方法

該法是進化計算的一個分支，模擬了生物界中蟻群、魚群等在覓食或避敵時的行為。可分為蟻群算法ACO和PSO。蟻群聚類算法的許多特性，如靈活性、健壯性、分布性和自組織性等，使其非常適合本質(zhì)上是分布、動態(tài)及又要交錯的問題求解中，能解決無人監(jiān)督的聚類問題，具有廣闊的前景。PSO模擬了魚群或鳥群的行為。在優(yōu)化領域，PSO可以與遺傳算法相媲美，并在預測精度和運行速度方面占優(yōu)勢。對ACO或PSO在數(shù)據(jù)挖掘中應用的研究仍處于早期階段，要將這些方法用到實際的大規(guī)模數(shù)據(jù)挖掘的聚類分析中還需要做大量的研究工作。

3.7.2 基于粒度的聚類方法

從粒度的角度看，我們會發(fā)現(xiàn)聚類和分類有很大的相通之處：聚類操作實際上是在一個統(tǒng)一粒度下進行計算的；分類操作是在不同粒度下進行的。所以說在粒度原理下，聚類和分類是相通的，很多分類的方法也可以用在聚類方法中。作為一個新的研究方向，雖然目前粒度計算還不成熟，尤其是對粒度計算語義的研究還相當少，但相信隨著粒度理論的不斷發(fā)展，今后幾年它必將在聚類算法及其相關(guān)領域得到廣泛的應用。

3.7.3 譜聚法

譜聚類方法建立在譜圖理論基礎之上，并利用數(shù)據(jù)的相似矩陣的特征向量進行聚類，是一種基于兩點間相似關(guān)系的方法，這使得該方法適用于非測度空間。它與數(shù)據(jù)點的維數(shù)無關(guān)，而僅與數(shù)據(jù)點的個數(shù)有關(guān)，可以避免由特征向量的過高維數(shù)所造成的奇異性問題。它又是一個判別式算法，不用對數(shù)據(jù)的全局結(jié)構(gòu)作假設，而是首先收集局部信息來表示兩點屬于同一類的可能性；然后根據(jù)某一聚類判據(jù)作全局決策，將所有數(shù)據(jù)點劃分到不同的數(shù)據(jù)集合中。通常這樣的判據(jù)可以在一個嵌入空間中得到解釋，該嵌入空間是由數(shù)據(jù)矩陣的某幾個特征向量張成的。譜聚類算法成功原因在于：通過特征分解，可以獲得聚類判據(jù)在放松了的連續(xù)域中的全局最優(yōu)解。與其他算法相比，它不僅思想簡單、易于實現(xiàn)、不易陷入局部最優(yōu)解，而且具有識別非凸分布的聚類能力，非常適合于許多實際問題。目前，該算法已應用于語音識別、VLSI設計、文本挖掘等領域。

3.7.4 多種聚類方法的融合

實際應用的復雜性和數(shù)據(jù)的多樣性往往使得單一的算法無能為力。因此，很多人對多種算法的融合進行了廣泛研究并取得了一些成果。大致可分為以下幾類：(1)基于傳統(tǒng)聚類方法的融合，如CLIQUE、CUBN等。(2)模糊理論與其他聚類法的融合，如遺傳＋模糊C2均值混合聚類法等。(3)遺傳算法與機器學習的融合。(4)傳統(tǒng)聚類法與其他學科理論的融合，如譜算法等。總之，很多新算法是以上幾類方法中兩種或兩種以上方法有機結(jié)合而得的，它們?nèi)￠L補短，優(yōu)勢明顯，這也是我們數(shù)據(jù)挖掘研究人員要努力的研究方向之一。

4 結(jié)論

綜上所述，分層聚類的突出優(yōu)點是它能夠生成比較規(guī)整的類集合，聚類結(jié)果不依賴元素的初始排列或輸入次序，與聚類過程的先后次序無關(guān)，聚類結(jié)果比較穩(wěn)定，不易導致類的重構(gòu)。但計算開銷較大，對異常數(shù)據(jù)比較脆弱。劃分聚類的優(yōu)勢是運算量小，能用于處理龐大的樣本數(shù)據(jù)，也為實時處理提供了一定的可能性。但要求用戶必須事先給出要生成的簇的數(shù)目。網(wǎng)格聚類處理速度快，處理時間與數(shù)據(jù)對象的數(shù)目無關(guān)。缺點是只能發(fā)現(xiàn)邊界是水平或垂直的聚類，而不能檢測到斜邊界。也不適用于高維情況，并存在量化尺度的問題。密度聚類的優(yōu)點是一遍掃描，并可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)形狀任意、個數(shù)不定的聚類。

通常可參考以下建議：(1)如果希望聚類算法對數(shù)據(jù)輸入的順序不敏感，可選用基于網(wǎng)格的STING算法。(2)如果目標數(shù)據(jù)庫比較大，建議使用綜合性的聚類算法，如CURE等。(3)如果聚類的形狀是球形或者凸形，BIRCH和CLARANS比較適合。(4)將不同類型的聚類算法相互結(jié)合以滿足不同的聚類要求。

5 結(jié)束語

各種聚類算法各有優(yōu)缺點，又由于實際問題的復雜性和數(shù)據(jù)的多樣性，使得無論哪一種方法都只能解決某一類問題。因此，用戶應該根據(jù)具體問題具體分析，選擇恰當?shù)倪m合自己的聚類算法。近年來，隨著數(shù)據(jù)挖掘、機器學習和人工智能等領域中傳統(tǒng)方法的不斷發(fā)展以及各種新方法和新技術(shù)的涌現(xiàn)，聚類算法得到了長足的發(fā)展。不難發(fā)現(xiàn)其新趨勢：(1)傳統(tǒng)聚類方法的融合發(fā)展。(2)新方法不斷涌現(xiàn)。(3)根據(jù)實際需要，有針對性地融合眾多領域的技術(shù)。總之，聚類算法綜合了數(shù)據(jù)挖掘、模式識別、數(shù)學等眾多領域的研究成果。隨著這些領域中相關(guān)理論的發(fā)展、完善和相互滲透，以及新技術(shù)的出現(xiàn)，聚類分析將得到更快的發(fā)展。

參考文獻：

[1] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19(1):9.

[2] 賀玲，吳玲達，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計算機應用研究，2007，(01):16-19.

[3] 陸云.聚類分析數(shù)據(jù)挖掘方法的研究與應用[D].合肥:安徽大學，2007.4.

[4] 李東琦.聚類算法的研究[D].成都:西南交通大學，2007.5.

[5] 李明華，劉全，劉忠，郗連霞.數(shù)據(jù)挖掘中聚類算法的新發(fā)展[J]. 計算機應用研究，2008，25(1):60-62.

[6] 馬帥，王騰蛟，唐世渭，等.一種基于參考點和密度的快速聚類算法[J].軟件學報，2003，14(6):61-67.

[7] 卜東波，白碩，李國杰.聚類/分類中的粒度原理[J].計算機學報，2002，25(8):810-816.

[8] 王磊，潘進，焦李成.免疫算法[J].電子學報，2000，28(7):74-78.