摘要：聚類分析是多元統(tǒng)計(jì)分析的重要方法之一，該方法在許多領(lǐng)域都有廣泛的應(yīng)用。本文首先對(duì)聚類的分類做簡(jiǎn)要的介紹，然后給出了常用的聚類分析方法的基本思想和優(yōu)缺點(diǎn)，并對(duì)常用的聚類方法作比較分析，以便人們根據(jù)實(shí)際的問(wèn)題選擇合適的聚類方法。

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

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)12-20ppp-0c

Cluster Anlaysis Methods of Data Mining

HUANG Li-wen

(School of Science， Quanzhou Normal University， Quanzhou 362000， China)

Abstract: Cluster analysis is one of the important methods of multivariate statistical analysis， and this method has a wide range of applications in many fields. In this paper， the classification of the cluster is introduced briefly， and then gives some common methods of cluster analysis and the advantages and disadvantages of these methods，and these clustering method were compared and anslyzed so that people can chose suitable clustering methods according to the actual issues.

Key words: Cluster Analysis; Data Mining?

1 引言

聚類分析是數(shù)據(jù)挖掘中的重要方法之一，它把一個(gè)沒有類別標(biāo)記的樣本集按某種準(zhǔn)則劃分成若干個(gè)子類，使相似的樣品盡可能歸為一類，而不相似的樣品盡量劃分到不同的類中。目前，該方法已經(jīng)被廣泛地應(yīng)用于生物、氣候?qū)W、經(jīng)濟(jì)學(xué)和遙感等許多領(lǐng)域，其目的在于區(qū)別不同事物并認(rèn)識(shí)事物間的相似性。因此，聚類分析的研究具有重要的意義。

本文主要介紹常用的一些聚類方法，并從聚類的可伸縮性、類的形狀識(shí)別、抗“噪聲”能力、處理高維能力和算法效率五個(gè)方面對(duì)其進(jìn)行比較分析，以便人們根據(jù)實(shí)際的問(wèn)題選擇合適的聚類方法。

2 聚類的分類

聚類分析給人們提供了豐富多彩的分類方法，這些方法大致可歸納為以下幾種[1，2，3，4]：劃分方法、層次方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法和基于模型的聚類方法。

2.1 劃分法(partitionging methods)

給定一個(gè)含有n個(gè)對(duì)象（或元組）的數(shù)據(jù)庫(kù)，采用一個(gè)劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)聚簇，且k≤n。在聚類的過(guò)程中，需預(yù)先給定劃分的數(shù)目k，并初始化k個(gè)劃分，然后采用迭代的方法進(jìn)行改進(jìn)劃分，使得在同一類中的對(duì)象之間盡可能地相似，而不同類的中的對(duì)象之間盡可能地相異。這種聚類方法適用于中小數(shù)據(jù)集，對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類時(shí)需要作進(jìn)一步的改進(jìn)。

2.2 層次法(hietarchical methods)

層次法對(duì)給定數(shù)據(jù)對(duì)象集合按層次進(jìn)行分解，分解的結(jié)果形成一顆以數(shù)據(jù)子集為節(jié)點(diǎn)的聚類樹，它表明類與類之間的相互關(guān)系。根據(jù)層次分解是自低向上還是自頂向下，可分為凝聚聚類法和分解聚類法：凝聚聚類法的主要思想是將每個(gè)對(duì)象作為一個(gè)單獨(dú)的一個(gè)類，然后相繼地合并相近的對(duì)象和類，直到所有的類合并為一個(gè)，或者符合預(yù)先給定的終止條件；分裂聚類法的主要思想是將所有的對(duì)象置于一個(gè)簇中，在迭代的每一步中，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對(duì)象在單獨(dú)的一個(gè)簇中，或者符合預(yù)先給定的終止條件。在層次聚類法中，當(dāng)數(shù)據(jù)對(duì)象集很大，且劃分的類別數(shù)較少時(shí)，其速度較快，但是，該方法常常有這樣的缺點(diǎn)：一個(gè)步驟（合并或分裂）完成，它就不能被取消，也就是說(shuō)，開始錯(cuò)分的對(duì)象，以后無(wú)法再改變，從而使錯(cuò)分的對(duì)象不斷增加，影響聚類的精度，此外，其抗“噪聲”的能力也較弱，但是若把層次聚類和其他的聚類技術(shù)集成，形成多階段聚類，聚類的效果有很大的提高。

2.3 基于密度的方法(density-based methods)

該方法的主要思想是只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過(guò)某個(gè)閾值，就繼續(xù)聚類。也就是說(shuō)，對(duì)于給定的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目的點(diǎn)。這樣的方法就可以用來(lái)濾處＂噪聲＂孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。

2.4 基于網(wǎng)格的方法(grid-based methods)

這種方法是把對(duì)象空間量化為有限數(shù)目的單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。用這種方法進(jìn)行聚類處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。

2.5 基于模型的方法(model-based method)

基于模型的方法為每個(gè)簇假定一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。該方法經(jīng)常基于這樣的假設(shè)：數(shù)據(jù)是根據(jù)潛在的概率分布生成的。該方法主要有兩類：統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。

3 常用的聚類算法

目前，已經(jīng)提出的聚類算法很多，常用的聚類算法主要有以下幾種：系統(tǒng)聚類法、動(dòng)態(tài)聚類法、CLARANS、CURE、DBSCAN、STING和模糊聚類法（FCM）。

3.1 系統(tǒng)聚類法

系統(tǒng)聚類法[5]是將n個(gè)樣品看成n類，即一類包含一個(gè)樣品；然后將性質(zhì)最接近的兩類合并成一個(gè)新類，這樣就得到n-1類，再?gòu)倪@n-1類中找出性質(zhì)最接近的兩類加以合并，成了n-2類；如此下去，最后所有的樣品均成一類；將上述類的合并過(guò)程畫成一張圖（這圖常稱為聚類圖），這樣便可決定分多少類，每類各有什么樣品。

系統(tǒng)聚類法的計(jì)算簡(jiǎn)單，而且其聚類結(jié)果給出一個(gè)譜系圖，因此，可以根據(jù)該圖選擇所需要的聚類結(jié)果。但是，它也有不足之處，其主要表現(xiàn)在以下幾個(gè)方面：1）當(dāng)樣品數(shù)量很多時(shí)，而且只需要?jiǎng)澐譃檩^少的類別時(shí)，這種聚類方法的重復(fù)計(jì)算量很大；2）當(dāng)某一樣品劃歸某一個(gè)類后，其屬性不變，若分類方法的選擇不當(dāng)，對(duì)聚類的精度影響很大；3）對(duì)大數(shù)據(jù)量進(jìn)行處理時(shí)，計(jì)算機(jī)內(nèi)存開銷很大，有時(shí)，計(jì)算機(jī)受此限制而無(wú)法進(jìn)行聚類分析，而且其速度很慢；4）抗干擾的能力很弱。

3.2 動(dòng)態(tài)聚類算法

動(dòng)態(tài)聚類法[5]就是在開始時(shí)先建立一批初始中心，而讓待分的各個(gè)樣品依據(jù)某種判別準(zhǔn)則向初始中心凝聚，然后再逐步修改調(diào)整中心，重新分類；并根據(jù)各類離散性統(tǒng)計(jì)量（如均方差）和兩類間可分離性的統(tǒng)計(jì)量（如類間標(biāo)準(zhǔn)化距離、J-M距離等）再進(jìn)行合并和分裂。此后在修改調(diào)整中心，這樣不斷繼續(xù)下去，直到分類比較合適為止。

動(dòng)態(tài)聚類法使用隨機(jī)方式選擇 作為初始聚類中心，按照算法的迭代執(zhí)行，整個(gè)算法的結(jié)束條件是類的重心（或凝聚點(diǎn)）不再改變，它的計(jì)算復(fù)雜性是O(nkt)，其中，n為樣本數(shù)量，k為聚類數(shù)，t為迭代次數(shù)。與系統(tǒng)聚類法相比，動(dòng)態(tài)聚類法明顯的優(yōu)勢(shì)是運(yùn)算量小，能用于處理龐大的樣本數(shù)據(jù)，也為實(shí)時(shí)處理提供了一定的可能性，但其也存在一些缺點(diǎn)，主要表現(xiàn)在以下幾個(gè)方面:（1）動(dòng)態(tài)聚類法要求用戶必須事先給出聚類的數(shù)目，選擇初始劃分的最佳方向、更新分區(qū)和停止準(zhǔn)則，且其結(jié)果與數(shù)據(jù)輸入順序有關(guān)，不同的初始值可能會(huì)導(dǎo)致不同的結(jié)果；（2）對(duì)于噪聲和孤立點(diǎn)敏感，很容易受例外情況的影響，適用于發(fā)現(xiàn)球狀類，但不適合發(fā)現(xiàn)非凸面狀的簇，不適合大小差別較大的簇；（3）一個(gè)對(duì)象只能屬于一個(gè)類中，不能多維揭示其多重屬性。

3.3 CLARANS算法

CLARANS[2，6，9]也叫隨機(jī)搜索聚類算法，是一種分割聚類方法。該算法是基于CLARA算法的改進(jìn)，與CLARA算法不同的是：CLARA算法在每個(gè)階段都選取一個(gè)固定樣本，而CLARANS在搜索的每一步都帶一定的隨機(jī)性選取一個(gè)樣本，在替換了一個(gè)中心點(diǎn)后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居，搜索的鄰居點(diǎn)數(shù)目被用戶定義的一個(gè)參數(shù)加以限制。如果找到一個(gè)比它更好的鄰居，則把中心點(diǎn)移到該鄰居節(jié)點(diǎn)上，否則把該點(diǎn)作為局部最小量，然后再隨機(jī)選擇一個(gè)點(diǎn)來(lái)尋找另一個(gè)局部最小量。

該算法能夠探測(cè)孤立點(diǎn)，并適用于大型數(shù)據(jù)庫(kù)，但其計(jì)算復(fù)雜度復(fù)雜度較高，大約為O(n2)；此外，該算法對(duì)數(shù)據(jù)輸入的順序敏感，適用于凸形或球形數(shù)據(jù)。

3.4 CURE算法

CURE[6，7，8]算法是一種使用代表點(diǎn)的聚類算法。該方法首先把每個(gè)數(shù)據(jù)點(diǎn)看成一簇，然后再以一個(gè)特定的收縮因子向中心“收縮”，即合并兩個(gè)距離最近的代表點(diǎn)的簇，直至達(dá)到預(yù)先給定的聚類個(gè)數(shù)為止。它回避了用所有點(diǎn)或單個(gè)質(zhì)心來(lái)表示一個(gè)簇的傳統(tǒng)方法，將一個(gè)簇用多個(gè)代表點(diǎn)來(lái)表示，使CURE可以適應(yīng)非球形的幾何形狀。另外，收縮因子降底了噪音對(duì)聚類的影響，從而使CURE對(duì)孤立點(diǎn)的處理更加健壯，而且能識(shí)別非球形和大小變化比較大的簇。

該算法采用隨機(jī)抽樣與分割相結(jié)合的方法來(lái)提高聚類效率，對(duì)于大型數(shù)據(jù)庫(kù)，它也具有良好的伸縮性，運(yùn)行速度很快，而且有較好的聚類效果，其計(jì)算復(fù)雜度為O(n)。

3.5 DBSCAN算法

DBSCAN算法[6，7，8，9]是一種基于高密度連接區(qū)域密度的聚類算法。該方法將密度足夠高的區(qū)域劃分為簇，并可以在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。其主要的思想是通過(guò)檢查數(shù)據(jù)庫(kù)中每個(gè)點(diǎn)的ε-鄰域來(lái)尋找聚類。如果第一個(gè)點(diǎn)p的ε-鄰域包含多于MinPts個(gè)點(diǎn)，則創(chuàng)建一個(gè)以P作為核心對(duì)象的新簇，否則先把它暫時(shí)標(biāo)為噪聲點(diǎn)，跳到下一個(gè)點(diǎn)，并判斷它是否為核心點(diǎn)。然后反復(fù)地尋找從這些核心點(diǎn)直接密度可達(dá)的對(duì)象，當(dāng)沒有新的點(diǎn)可以被添加到任何簇時(shí)，該過(guò)程結(jié)束。

該算法可以數(shù)據(jù)集中的所有簇和噪聲，但其不對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理而直接進(jìn)行聚類操作，當(dāng)數(shù)據(jù)集很大時(shí)，占用內(nèi)存很大，而且I/O消耗也很大，如果采用空間索引，其計(jì)算復(fù)雜度為O(nlogn)，否則，其計(jì)算復(fù)雜度為O(n2)。

3.6 STING算法

STING算法[2，3，8]是一種基于風(fēng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)，高層的每個(gè)單元被劃分為多個(gè)低一層的單元，高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從低層單元計(jì)算得到，而統(tǒng)計(jì)信息的查詢則采用自頂向下的基于網(wǎng)格的方法。這些參數(shù)包括：屬性無(wú)關(guān)的參數(shù)count;屬性相關(guān)的參數(shù)m(平均值)、s(標(biāo)準(zhǔn)偏差)、min(最小值)、max(最大值)以及該單元中屬性值遵循的分布(distribution)類型。該算法預(yù)先計(jì)算和存儲(chǔ)每個(gè)單元的統(tǒng)計(jì)信息，它不依賴于查詢的匯總信息。

該算法主要優(yōu)點(diǎn)是效率高，有利于并行處理和增量更新；它通過(guò)掃描數(shù)據(jù)庫(kù)一次來(lái)計(jì)算單元的統(tǒng)計(jì)信息，因而其計(jì)算復(fù)雜度為O(n)。在層次結(jié)構(gòu)建立后，其查詢處理的計(jì)算復(fù)雜度為O(m)，其中m為最低層網(wǎng)格單元的數(shù)目。其缺點(diǎn)是聚類質(zhì)量取決于網(wǎng)格結(jié)構(gòu)最低層的粒度，粒度的大小會(huì)明顯影響處理代價(jià)，特別是當(dāng)數(shù)據(jù)集的維數(shù)較高時(shí)，由于生成網(wǎng)格層次及每一層的單元數(shù)較多，算法的效率會(huì)降低。

3.7 模糊聚類算法（FCM）

傳統(tǒng)的聚類分析是一種硬劃分，它把每個(gè)待識(shí)別的對(duì)象嚴(yán)格地劃分到某類中，具有“非此即彼”的性質(zhì)；而在實(shí)際中，大多數(shù)對(duì)象并沒有嚴(yán)格的屬性，它們?cè)谛詰B(tài)和類屬方面存在著中介性，具有“亦此亦彼”的性質(zhì)；鑒于此，人們開始用模糊的方法來(lái)處理這類問(wèn)題，從而產(chǎn)生了模糊聚類的方法，也就是說(shuō)，模糊聚類法[5]是將模糊數(shù)學(xué)的思想觀點(diǎn)用到聚類分析中產(chǎn)生的方法，其關(guān)鍵是隸屬函數(shù)的確定。該方法多用于定性變量的分類。其主要算法如下：

（1）選擇一個(gè)初始模糊分類方案，將n個(gè)樣本分成k個(gè)模糊類，得到一個(gè)模糊隸屬度矩陣U={uij，i=1，2，…，n;j=1，2，…，k}，其中uij表示樣本Xi對(duì)模糊集Cj的隸屬度，uij∈[0，1]；

（2）利用矩陣 計(jì)算模糊評(píng)判函數(shù)的值，模糊評(píng)判函數(shù)通常是一個(gè)與對(duì)應(yīng)的分類相聯(lián)系的加權(quán)平方誤差和

是第k個(gè)模糊集的中心，重新分配樣本到各模糊集以減少評(píng)判函數(shù)的值并重新計(jì)算U；

（3）重復(fù)（2），直到矩陣U不再有較大的變動(dòng)。

模糊聚類解決了一些混合對(duì)象的歸類問(wèn)題，同時(shí)，當(dāng)樣本數(shù)較少的時(shí)候，應(yīng)用該方法的優(yōu)越性也比較明顯，另外，其抗干擾的能力也較強(qiáng)；但是，它對(duì)一些隱含類的提取能力還有待于進(jìn)一步的改進(jìn)，除此之外，預(yù)定的分類數(shù)目一般也是人為決定的，同動(dòng)態(tài)聚類一樣，就可能出現(xiàn)人為預(yù)定的分類數(shù)與實(shí)際存在的類數(shù)不相符這種情況，從而影響分類的結(jié)果。

4 聚類的性能比較

基于上述的分析，現(xiàn)從可伸縮性、類的形狀識(shí)別、抗噪聲能力、處理高維能力和算法效率五個(gè)方面對(duì)常用聚類算法的性能進(jìn)行了比較，結(jié)果如下表。通過(guò)這些比較，可以給聚類算法研究和應(yīng)用的選擇提供參考。

5 結(jié)束語(yǔ)

目前，已經(jīng)提出的聚類算法很多，每種方法都有其優(yōu)缺點(diǎn)和不同的適用領(lǐng)域，可以根據(jù)上述的分析，選擇適合特定問(wèn)題的聚類方法；但是，在實(shí)際應(yīng)用中，由于數(shù)據(jù)的復(fù)雜性，往往用某種聚類算法進(jìn)行聚類劃分得到的效果不佳，可能要綜合多種聚類方法才能得到較好的聚類效果。因此，在將來(lái)的研究中，需要做好對(duì)現(xiàn)有聚類算法的改進(jìn)和融合，以便得到更好的聚類方法。

參考文獻(xiàn)：

[1] 孫孝萍.基于聚類分析的數(shù)據(jù)挖掘算法研究[D].碩士學(xué)位論文，2002.4.

[2] 覃擁軍，劉先鋒.數(shù)據(jù)挖掘中的聚類研究[J].科技咨詢導(dǎo)報(bào)，2007(16):28-30.

[3] 梁志榮.數(shù)據(jù)挖掘中聚類分析的技術(shù)方法[J]. 電腦開發(fā)與應(yīng)用，2007，20(6):37-39.

[4] 谷淑化，呂維先，馬于濤.關(guān)于數(shù)據(jù)挖掘中聚類分析算法的比較[J].現(xiàn)代計(jì)算機(jī)，2005(3):26-29.

[5] 黃利文.基于幾何概率的聚類分析[D]. 碩士學(xué)位論文，2006(1).

[6] 張紅云，劉向東，段曉東等.數(shù)據(jù)挖掘中聚類算法比較[J].計(jì)算機(jī)應(yīng)用與軟件，2003(2):5-6.

[7] 王勁波，翁偉，許華榮.數(shù)據(jù)挖掘中基于密度的聚類分析方法[J].統(tǒng)計(jì)與決策，2005(10):139-141.

[8] 劉泉鳳，陸蓓. 數(shù)據(jù)挖掘中聚類算法的比較研究[J].浙江水利水電專科學(xué)校學(xué)報(bào)，2005，17(2):55-58.

[9] 丁學(xué)鈞，楊克儉，李虹等.數(shù)據(jù)挖掘中聚類算法的比較研究[J].河北建筑工程學(xué)院學(xué)報(bào)，2004，22(3):125-127.

收稿日期：2008-02-17

作者簡(jiǎn)介：黃利文（1979-），男，助教。

注：在表1中，n為樣本數(shù)量，k為聚類數(shù)目，t為迭代次數(shù)。