論文摘要：該文詳細(xì)闡述了數(shù)據(jù)挖掘領(lǐng)域的常用聚類算法及改進(jìn)算法，并比較分析了其優(yōu)缺點(diǎn)，提出了數(shù)據(jù)挖掘?qū)垲惖牡湫鸵?，指出各自的特點(diǎn)，以便于人們更快、更容易地選擇一種聚類算法解決特定問題和對(duì)聚類算法作進(jìn)一步的研究。并給出了相應(yīng)的算法評(píng)價(jià)標(biāo)準(zhǔn)、改進(jìn)建議和聚類分析研究的熱點(diǎn)、難點(diǎn)。上述工作將為聚類分析和數(shù)據(jù)挖掘等研究提供有益的參考。
　　1 引言
　　隨著經(jīng)濟(jì)社會(huì)和科學(xué)技術(shù)的高速發(fā)展，各行各業(yè)積累的數(shù)據(jù)量急劇增長(zhǎng)，如何從海量的數(shù)據(jù)中提取有用的信息成為當(dāng)務(wù)之急。聚類是將數(shù)據(jù)劃分成群組的過程，即把數(shù)據(jù)對(duì)象分成多個(gè)類或簇，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。它對(duì)未知數(shù)據(jù)的劃分和分析起著非常有效的作用。通過聚類，能夠識(shí)別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。為了找到效率高、通用性強(qiáng)的聚類方法人們從不同角度提出了許多種聚類算法，一般可分為基于層次的，基于劃分的，基于密度的，基于網(wǎng)格的和基于模型的五大類。
　　2 數(shù)據(jù)挖掘?qū)垲愃惴ǖ囊?
　　(1)可兼容性：要求聚類算法能夠適應(yīng)并處理屬性不同類型的數(shù)據(jù)。(2)可伸縮性：要求聚類算法對(duì)大型數(shù)據(jù)集和小數(shù)據(jù)集都適用。(3)對(duì)用戶專業(yè)知識(shí)要求最小化。(4)對(duì)數(shù)據(jù)類別簇的包容性：即聚類算法不僅能在用基本幾何形式表達(dá)的數(shù)據(jù)上運(yùn)行得很好，還要在以其他更高維度形式表現(xiàn)的數(shù)據(jù)上同樣也能實(shí)現(xiàn)。(5)能有效識(shí)別并處理數(shù)據(jù)庫(kù)的大量數(shù)據(jù)中普遍包含的異常值，空缺值或錯(cuò)誤的不符合現(xiàn)實(shí)的數(shù)據(jù)。(6)聚類結(jié)果既要滿足特定約束條件，又要具有良好聚類特性，且不丟失數(shù)據(jù)的真實(shí)信息。(7)可讀性和可視性：能利用各種屬性如顏色等以直觀形式向用戶顯示數(shù)據(jù)挖掘的結(jié)果。(8)處理噪聲數(shù)據(jù)的能力。(9)算法能否與輸入順序無關(guān)。
　　3 各種聚類算法介紹
　　隨著人們對(duì)數(shù)據(jù)挖掘的深入研究和了解，各種聚類算法的改進(jìn)算法也相繼提出，很多新算法在前人提出的算法中做了某些方面的提高和改進(jìn)，且很多算法是有針對(duì)性地為特定的領(lǐng)域而設(shè)計(jì)。某些算法可能對(duì)某類數(shù)據(jù)在可行性、效率、精度或簡(jiǎn)單性上具有一定的優(yōu)越性，但對(duì)其它類型的數(shù)據(jù)或在其他領(lǐng)域應(yīng)用中則不一定還有優(yōu)勢(shì)。所以，我們必須清楚地了解各種算法的優(yōu)缺點(diǎn)和應(yīng)用范圍，根據(jù)實(shí)際問題選擇合適的算法。
　　3.1 基于層次的聚類算法
　　基于層次的聚類算法對(duì)給定數(shù)據(jù)對(duì)象進(jìn)行層次上的分解，可分為凝聚算法和分裂算法。
　　(1)自底向上的凝聚聚類方法。這種策略是以數(shù)據(jù)對(duì)象作為原子類，然后將這些原子類進(jìn)行聚合。逐步聚合成越來越大的類，直到滿足終止條件。凝聚算法的過程為：在初始時(shí)，每一個(gè)成員都組成一個(gè)單獨(dú)的簇，在以后的迭代過程中，再把那些相互鄰近的簇合并成一個(gè)簇，直到所有的成員組成一個(gè)簇為止。其時(shí)間和空間復(fù)雜性均為O(n2)。通過凝聚式的方法將兩簇合并后，無法再將其分離到之前的狀態(tài)。在凝聚聚類時(shí)，選擇合適的類的個(gè)數(shù)和畫出原始數(shù)據(jù)的圖像很重要。
　　(2)自頂向下分裂聚類方法。與凝聚法相反，該法先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件。其主要思想是將那些成員之間不是非常緊密的簇進(jìn)行分裂。跟凝聚式方法的方向相反，從一個(gè)簇出發(fā)，一步一步細(xì)化。它的優(yōu)點(diǎn)在于研究者可以把注意力集中在數(shù)據(jù)的結(jié)構(gòu)上面。一般情況下不使用分裂型方法，因?yàn)樵谳^高的層很難進(jìn)行正確的拆分。
　　3.2 基于密度的聚類算法
　　很多算法都使用距離來描述數(shù)據(jù)之間的相似性，但對(duì)于非凸數(shù)據(jù)集，只用距離來描述是不夠的。此時(shí)可用密度來取代距離描述相似性，即基于密度的聚類算法。它不是基于各種各樣的距離，所以能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)。其指導(dǎo)思想是：只要一個(gè)區(qū)域中的點(diǎn)的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）大過某個(gè)閾值，就把它加到與之相近的聚類中去。該法從數(shù)據(jù)對(duì)象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來，從而可發(fā)現(xiàn)任意形狀的簇，并可用來過濾“噪聲”數(shù)據(jù)。常見算法有DBSCAN，DENCLUE等。

　　3.3 基于劃分的聚類算法
　　給定一個(gè)N個(gè)對(duì)象的元組或數(shù)據(jù)庫(kù)，根據(jù)給定要?jiǎng)?chuàng)建的劃分的數(shù)目k，將數(shù)據(jù)劃分為k個(gè)組，每個(gè)組表示一個(gè)簇類（=N）時(shí)滿足如下兩點(diǎn)：(1)每個(gè)組至少包含一個(gè)對(duì)象；(2)每個(gè)對(duì)象必須屬于且只屬于一個(gè)組。算法先隨機(jī)創(chuàng)建一個(gè)初始劃分，然后采用一種迭代的重定位技術(shù)，通過將對(duì)象根據(jù)簇類之間的差異從一個(gè)劃分移到另一個(gè)劃分來提高簇類內(nèi)數(shù)據(jù)之間的相似程度。一種好的劃分的一般準(zhǔn)則是：在同一個(gè)類中的對(duì)象盡可能“接近”或相似，而不同類中的對(duì)象盡可能“遠(yuǎn)離”或不同。為了達(dá)到全局最優(yōu)，基于劃分的聚類會(huì)要求窮舉所有可能的劃分。典型的劃包括：K-means，PAM，EM等。劃分法收斂速度快，在對(duì)中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用。缺點(diǎn)是它傾向于識(shí)別凸形分布大小相近、密度相近的聚類，不能發(fā)現(xiàn)分布形狀比較復(fù)雜的聚類，它要求類別數(shù)目k可以合理地估計(jì)，且初始中心的選擇和噪聲會(huì)對(duì)聚類結(jié)果產(chǎn)生很大影響。還要求用戶預(yù)先指定聚類個(gè)數(shù)。
　　3.4 基于網(wǎng)格的聚類算法
　　首先將數(shù)據(jù)空間量化為有限個(gè)單元的網(wǎng)格結(jié)構(gòu)，然后對(duì)量化后的單個(gè)的單元為對(duì)象進(jìn)行聚類。典型的算法有STING，CLIQUE等。網(wǎng)格聚類法處理速度快，處理時(shí)間與數(shù)據(jù)對(duì)象的數(shù)目無關(guān)，一般由網(wǎng)格單元的數(shù)目決定。缺點(diǎn)是只能發(fā)現(xiàn)邊界是水平或垂直的聚類，不能檢測(cè)到斜邊界。該類算法也不適用于高維情況，因?yàn)榫W(wǎng)格單元的數(shù)目隨著維數(shù)的增加而呈指數(shù)增長(zhǎng)。另外還有下列問題： 一是如何選擇合適的單元大小和數(shù)目，二是怎樣對(duì)每個(gè)單元中對(duì)象的信息進(jìn)行匯總，三是存在量化尺度的問題。
　　3.5 基于模型的聚類算法
　　基于模型的方法給每一個(gè)聚簇假定了一個(gè)模型，然后去尋找能夠很好滿足這個(gè)模型的數(shù)據(jù)集。這個(gè)模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)，它由一系列的概率分布決定，也可能通過基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)字自動(dòng)決定聚類的數(shù)目。它的一個(gè)潛在假定是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。一般有2種嘗試方向：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案。COBWEB是一種流行的簡(jiǎn)單增量概念聚類算法，以一個(gè)分類樹的形式來創(chuàng)建層次聚類，它的輸入對(duì)象用分類屬性-值對(duì)來描述。COBWEB的優(yōu)點(diǎn)為：可以自動(dòng)修正劃分中類的數(shù)目；不需要用戶提供輸入?yún)?shù)。缺點(diǎn)為：COBWEB基于這樣一個(gè)假設(shè)：在每個(gè)屬性上的概率分布是彼此獨(dú)立的。但這個(gè)假設(shè)并不總是成立。且對(duì)于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導(dǎo)致時(shí)間和空間復(fù)雜性的劇烈變化，不適用于聚類大型數(shù)據(jù)庫(kù)的數(shù)據(jù)。
　　3.6 模糊聚類算法
　　現(xiàn)實(shí)中很多對(duì)象沒有嚴(yán)格的屬性，其類屬和形態(tài)存在著中介性，適合軟劃分。恰好模糊聚類具有描述樣本類屬中間性的優(yōu)點(diǎn)，因此成為當(dāng)今聚類分析研究的主流。常用的模糊聚類有動(dòng)態(tài)直接聚類法、最大樹法、FCM等?；驹頌椋杭僭O(shè)有N個(gè)要分析的樣本，每個(gè)樣本有M個(gè)可量化的指標(biāo)，一般步驟為：(1)標(biāo)準(zhǔn)化數(shù)據(jù)：常用的數(shù)據(jù)標(biāo)準(zhǔn)化方法有：小數(shù)定標(biāo)規(guī)范化，最大最小值規(guī)范化，標(biāo)準(zhǔn)差規(guī)范化等。(2)建立模糊相似矩陣，標(biāo)定相似系數(shù)。(3)計(jì)算多極相似矩陣，計(jì)算整體相似關(guān)系矩陣，有傳遞閉包法，動(dòng)態(tài)直接聚類法，最大樹法等。(4)給定一個(gè)聚類水平，計(jì)算絕對(duì)相似矩陣。按行列調(diào)整絕對(duì)相似矩陣，每個(gè)分塊即為一個(gè)分類。 6.1 模糊C-均值聚類算法
　　FCM算法用隸屬度確定每個(gè)樣本屬于某個(gè)聚類的程度。它與K平均算法和中心點(diǎn)算法等相比，計(jì)算量可大大減少，因?yàn)樗∪チ硕嘀氐姆磸?fù)計(jì)算過程，效率將大大提高。同時(shí)，模糊聚類分析可根據(jù)數(shù)據(jù)庫(kù)中的相關(guān)數(shù)據(jù)計(jì)算形成模糊相似矩陣，形成相似矩陣之后，直接對(duì)相似矩陣進(jìn)行處理即可，無須多次反復(fù)掃描數(shù)據(jù)庫(kù)。根據(jù)實(shí)驗(yàn)要求動(dòng)態(tài)設(shè)定m值，以滿足不同類型數(shù)據(jù)挖掘任務(wù)的需要，適于高維度的數(shù)據(jù)的處理，具有較好的伸縮性，便于找出異常點(diǎn)。但m值根據(jù)經(jīng)驗(yàn)或者實(shí)驗(yàn)得來，具有不確定性，可能影響實(shí)驗(yàn)結(jié)果。并且，由于梯度法的搜索方向總是沿著能量減小的方向，使得算法存在易陷入局部極小值和對(duì)初始化敏感的缺點(diǎn)。為克服上述缺點(diǎn)，可在FCM算法中引入全局尋優(yōu)法來擺脫FCM聚類運(yùn)算時(shí)可能陷入的局部極小點(diǎn)，優(yōu)化聚類效果。 6.2 免疫進(jìn)化算法
　　該算法借鑒生命科學(xué)中的免疫概念和理論在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征或知識(shí)來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象。免疫算法的核心在于免疫算子的構(gòu)造，通過接種疫苗或免疫選擇兩個(gè)步驟來完成。免疫進(jìn)化算法能提高個(gè)體的適應(yīng)度和防止群體的退化，從而達(dá)到減輕原有進(jìn)化算法后期的波動(dòng)現(xiàn)象和提高收斂速度。例如IFCM、IFCL算法。它們既較大地提高了獲取全局最優(yōu)的概率，又減輕了基于遺傳聚類算法在遺傳后期的波動(dòng)現(xiàn)象。進(jìn)一步的工作是參數(shù)的適當(dāng)選取和減小運(yùn)行時(shí)間等。人對(duì)于客觀事物的識(shí)別往往只通過一些模糊信息的綜合，便可以獲得足夠精確的定論。

　　3.7 其它聚類算法
　　3.7.1 基于群的聚類方法
　　該法是進(jìn)化計(jì)算的一個(gè)分支，模擬了生物界中蟻群、魚群等在覓食或避敵時(shí)的行為?？煞譃橄伻核惴ˋCO和PSO。蟻群聚類算法的許多特性，如靈活性、健壯性、分布性和自組織性等，使其非常適合本質(zhì)上是分布、動(dòng)態(tài)及又要交錯(cuò)的問題求解中，能解決無人監(jiān)督的聚類問題，具有廣闊的前景。PSO模擬了魚群或鳥群的行為。在優(yōu)化領(lǐng)域，PSO可以與遺傳算法相媲美，并在預(yù)測(cè)精度和運(yùn)行速度方面占優(yōu)勢(shì)。對(duì)ACO或PSO在數(shù)據(jù)挖掘中應(yīng)用的研究仍處于早期階段，要將這些方法用到實(shí)際的大規(guī)模數(shù)據(jù)挖掘的聚類分析中還需要做大量的研究工作。 7.2 基于粒度的聚類方法
　　從粒度的角度看，我們會(huì)發(fā)現(xiàn)聚類和分類有很大的相通之處：聚類操作實(shí)際上是在一個(gè)統(tǒng)一粒度下進(jìn)行計(jì)算的；分類操作是在不同粒度下進(jìn)行的。所以說在粒度原理下，聚類和分類是相通的，很多分類的方法也可以用在聚類方法中。作為一個(gè)新的研究方向，雖然目前粒度計(jì)算還不成熟，尤其是對(duì)粒度計(jì)算語義的研究還相當(dāng)少，但相信隨著粒度理論的不斷發(fā)展，今后幾年它必將在聚類算法及其相關(guān)領(lǐng)域得到廣泛的應(yīng)用。 7.3 譜聚法
　　譜聚類方法建立在譜圖理論基礎(chǔ)之上，并利用數(shù)據(jù)的相似矩陣的特征向量進(jìn)行聚類，是一種基于兩點(diǎn)間相似關(guān)系的方法，這使得該方法適用于非測(cè)度空間。它與數(shù)據(jù)點(diǎn)的維數(shù)無關(guān)，而僅與數(shù)據(jù)點(diǎn)的個(gè)數(shù)有關(guān)，可以避免由特征向量的過高維數(shù)所造成的奇異性問題。它又是一個(gè)判別式算法，不用對(duì)數(shù)據(jù)的全局結(jié)構(gòu)作假設(shè)，而是首先收集局部信息來表示兩點(diǎn)屬于同一類的可能性；然后根據(jù)某一聚類判據(jù)作全局決策，將所有數(shù)據(jù)點(diǎn)劃分到不同的數(shù)據(jù)集合中。通常這樣的判據(jù)可以在一個(gè)嵌入空間中得到解釋，該嵌入空間是由數(shù)據(jù)矩陣的某幾個(gè)特征向量張成的。譜聚類算法成功原因在于：通過特征分解，可以獲得聚類判據(jù)在放松了的連續(xù)域中的全局最優(yōu)解。與其他算法相比，它不僅思想簡(jiǎn)單、易于實(shí)現(xiàn)、不易陷入局部最優(yōu)解，而且具有識(shí)別非凸分布的聚類能力，非常適合于許多實(shí)際問題。目前，該算法已應(yīng)用于語音識(shí)別、VLSI設(shè)計(jì)、文本挖掘等領(lǐng)域。 7.4 多種聚類方法的融合
　　實(shí)際應(yīng)用的復(fù)雜性和數(shù)據(jù)的多樣性往往使得單一的算法無能為力。因此，很多人對(duì)多種算法的融合進(jìn)行了廣泛研究并取得了一些成果。大致可分為以下幾類：(1)基于傳統(tǒng)聚類方法的融合，如CLIQUE、CUBN等。(2)模糊理論與其他聚類法的融合，如遺傳＋模糊C2均值混合聚類法等。(3)遺傳算法與機(jī)器學(xué)習(xí)的融合。(4)傳統(tǒng)聚類法與其他學(xué)科理論的融合，如譜算法等?？傊?，很多新算法是以上幾類方法中兩種或兩種以上方法有機(jī)結(jié)合而得的，它們?nèi)￠L(zhǎng)補(bǔ)短，優(yōu)勢(shì)明顯，這也是我們數(shù)據(jù)挖掘研究人員要努力的研究方向之一。
　　4 結(jié)論
　　綜上所述，分層聚類的突出優(yōu)點(diǎn)是它能夠生成比較規(guī)整的類集合，聚類結(jié)果不依賴元素的初始排列或輸入次序，與聚類過程的先后次序無關(guān)，聚類結(jié)果比較穩(wěn)定，不易導(dǎo)致類的重構(gòu)。但計(jì)算開銷較大，對(duì)異常數(shù)據(jù)比較脆弱。劃分聚類的優(yōu)勢(shì)是運(yùn)算量小，能用于處理龐大的樣本數(shù)據(jù)，也為實(shí)時(shí)處理提供了一定的可能性。但要求用戶必須事先給出要生成的簇的數(shù)目。網(wǎng)格聚類處理速度快，處理時(shí)間與數(shù)據(jù)對(duì)象的數(shù)目無關(guān)。缺點(diǎn)是只能發(fā)現(xiàn)邊界是水平或垂直的聚類，而不能檢測(cè)到斜邊界。也不適用于高維情況，并存在量化尺度的問題。密度聚類的優(yōu)點(diǎn)是一遍掃描，并可以在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)形狀任意、個(gè)數(shù)不定的聚類。
　　通常可參考以下建議：(1)如果希望聚類算法對(duì)數(shù)據(jù)輸入的順序不敏感，可選用基于網(wǎng)格的STING算法。(2)如果目標(biāo)數(shù)據(jù)庫(kù)比較大，建議使用綜合性的聚類算法，如CURE等。(3)如果聚類的形狀是球形或者凸形，BIRCH和CLARANS比較適合。(4)將不同類型的聚類算法相互結(jié)合以滿足不同的聚類要求。
　　5 結(jié)束語
　　各種聚類算法各有優(yōu)缺點(diǎn)，又由于實(shí)際問題的復(fù)雜性和數(shù)據(jù)的多樣性，使得無論哪一種方法都只能解決某一類問題。因此，用戶應(yīng)該根據(jù)具體問題具體分析，選擇恰當(dāng)?shù)倪m合自己的聚類算法。近年來，隨著數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和人工智能等領(lǐng)域中傳統(tǒng)方法的不斷發(fā)展以及各種新方法和新技術(shù)的涌現(xiàn)，聚類算法得到了長(zhǎng)足的發(fā)展。不難發(fā)現(xiàn)其新趨勢(shì)：(1)傳統(tǒng)聚類方法的融合發(fā)展。(2)新方法不斷涌現(xiàn)。(3)根據(jù)實(shí)際需要，有針對(duì)性地融合眾多領(lǐng)域的技術(shù)?？傊?，聚類算法綜合了數(shù)據(jù)挖掘、模式識(shí)別、數(shù)學(xué)等眾多領(lǐng)域的研究成果。隨著這些領(lǐng)域中相關(guān)理論的發(fā)展、完善和相互滲透，以及新技術(shù)的出現(xiàn)，聚類分析將得到更快的發(fā)展。