摘要：聚類(lèi)分析在數(shù)據(jù)挖掘領(lǐng)域中是一個(gè)非常重要的研究課題，該文闡述了聚類(lèi)算法的基本原理和性能要求，并依據(jù)算法思想的不同把聚類(lèi)算法分為五類(lèi)，詳細(xì)介紹了每一類(lèi)的算法思想、優(yōu)缺點(diǎn)及典型算法，有利于用戶(hù)對(duì)聚類(lèi)算法的選擇和研究者對(duì)聚類(lèi)算法的改進(jìn)研究，最后探討了聚類(lèi)算法今后的發(fā)展趨勢(shì)。

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

中圖分類(lèi)號(hào)：TP391.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 21-0000-02

1 引言

信息科學(xué)技術(shù)的高速發(fā)展使得各行各業(yè)中人們面臨的數(shù)據(jù)越來(lái)越多，聚類(lèi)分析能夠幫助人們從海量的數(shù)據(jù)中提取能夠?yàn)槿藗兯玫男畔⒑椭R(shí)，目前聚類(lèi)分析已經(jīng)被廣泛地運(yùn)用于計(jì)算機(jī)的圖像處理、經(jīng)濟(jì)學(xué)的市場(chǎng)分析、分子生物學(xué)的基因監(jiān)測(cè)、web技術(shù)領(lǐng)域的信息檢索等各個(gè)領(lǐng)域并取得一定成就，因此聚類(lèi)分析已成為數(shù)據(jù)挖掘研究領(lǐng)域中很熱門(mén)的研究課題之一。

2 聚類(lèi)基本原理及性能要求

聚類(lèi)簡(jiǎn)單來(lái)講就是依據(jù)數(shù)據(jù)其自身的特征將數(shù)據(jù)集進(jìn)行劃分成若干類(lèi)的過(guò)程，劃分的結(jié)果是相同類(lèi)內(nèi)數(shù)據(jù)相似度盡可能大、不同類(lèi)間數(shù)據(jù)相似度盡可能小，從而發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)。

聚類(lèi)在不同的應(yīng)用領(lǐng)域有不同的特殊要求，聚類(lèi)算法的典型性能要求有一下幾個(gè)方面：

（1）伸縮性；

（2）兼容性；

（3）有效處理噪聲數(shù)據(jù)；

（4）能處理基于約束的聚類(lèi)；

（5）可解釋性和可用性。

3 聚類(lèi)算法的分類(lèi)研究

隨著人們對(duì)聚類(lèi)算法的深入研究和應(yīng)用實(shí)踐，很多聚類(lèi)算法被先后提出不同的聚類(lèi)算法是基于不同的思想而開(kāi)發(fā)出的，而且具有不同的優(yōu)缺點(diǎn)，針對(duì)各種聚類(lèi)算法的研究現(xiàn)狀與構(gòu)造思想，可以把目前的聚類(lèi)算法大致如下幾類(lèi)：基于劃分的方法（partitioning method），基于層次的方法（hierachical method），基于密度的方法（density-based method），基于網(wǎng)格的方法（grid-based method）和基于模型的方法（model-based method）。

3.1 劃分方法

基于劃分方法的聚類(lèi)算法的基本思想是：給出要進(jìn)行聚類(lèi)的數(shù)據(jù)集（假設(shè)含有n個(gè)數(shù)據(jù)）和要生成的類(lèi)的個(gè)數(shù)（假設(shè)為K，k<=n），首先把數(shù)據(jù)集按照一定的規(guī)則構(gòu)建成k個(gè)初始劃分，一個(gè)劃分就代表一個(gè)聚類(lèi)，每一個(gè)類(lèi)中應(yīng)至少含有一個(gè)數(shù)據(jù)對(duì)象，并且同一個(gè)數(shù)據(jù)對(duì)象只能隸屬于一個(gè)類(lèi)。然后利用迭代重定位技術(shù)，不斷移動(dòng)初始類(lèi)內(nèi)的數(shù)據(jù)對(duì)象來(lái)改變劃分內(nèi)容，每次重定位都會(huì)使得同一類(lèi)內(nèi)的數(shù)據(jù)對(duì)象相似度有所提高，這種迭代重定位操作直到各類(lèi)劃分中的數(shù)據(jù)滿(mǎn)足一定的準(zhǔn)則停止。操作的結(jié)果是同一類(lèi)內(nèi)的數(shù)據(jù)具有很高的相似度，而不同類(lèi)內(nèi)數(shù)據(jù)相似度盡可能低?；趧澐址椒ǖ牡湫途垲?lèi)算法有：K-means、K-medoids、PAM等算法。K-means算法是由MacQueen于1967年首次提出的，K-means算法是在平均值被定義的情況下才能使用的，因此該算法突出的一個(gè)缺點(diǎn)就是易受孤立點(diǎn)的影響。K-medoids算法是在K-means算法基礎(chǔ)上進(jìn)行改進(jìn)的聚類(lèi)算法，選用聚類(lèi)中位置最中心的數(shù)據(jù)對(duì)象作為代表點(diǎn)，所以K-medoids算法不像K-means算法那樣易受孤立點(diǎn)或極端數(shù)據(jù)的影響，而且它能處理任意類(lèi)型的數(shù)據(jù)，收斂速度比K-means算法更快?；趧澐值木垲?lèi)算法具有收斂速度快，適合發(fā)現(xiàn)球狀類(lèi)的優(yōu)點(diǎn)。不足之處是它要求用戶(hù)預(yù)先給出聚類(lèi)個(gè)數(shù)k，而用戶(hù)輸入的K值是一個(gè)估計(jì)值，不一定符合實(shí)際中的聚類(lèi)個(gè)數(shù)，并且不能發(fā)現(xiàn)任意形狀的聚類(lèi)，另外聚類(lèi)結(jié)果受噪聲數(shù)據(jù)和初始中心點(diǎn)的選擇的影響很大。PAM 算法中心點(diǎn)的選擇是這樣的，首先把數(shù)據(jù)對(duì)象兩兩成對(duì)，然后通過(guò)對(duì)所有的數(shù)據(jù)對(duì)象對(duì)進(jìn)行分析后從每個(gè)數(shù)據(jù)對(duì)中選擇一個(gè)數(shù)據(jù)對(duì)象作為中心點(diǎn)，綜合衡量各種數(shù)據(jù)對(duì)的組合，估算出聚類(lèi)結(jié)果的好壞，最終選擇出較優(yōu)的數(shù)據(jù)對(duì)象作為聚類(lèi)中心點(diǎn)。

3.2 層次方法

層次聚類(lèi)方法是把給定的數(shù)據(jù)對(duì)象集合進(jìn)行逐層的分解， 每次迭代分解過(guò)程中，類(lèi)的個(gè)數(shù)及類(lèi)內(nèi)的數(shù)據(jù)成員都會(huì)發(fā)生變化。層次聚類(lèi)算法又可分成凝聚聚類(lèi)方法和分裂聚類(lèi)方法，凝聚聚類(lèi)方法的基本思想是：首先每個(gè)數(shù)據(jù)單獨(dú)成類(lèi)，然后把相距最近的兩個(gè)聚類(lèi)合并，重復(fù)這個(gè)過(guò)程，這樣就會(huì)逐步形成越來(lái)越大的類(lèi)，直到所有的數(shù)據(jù)對(duì)象都屬于同一個(gè)類(lèi)或符合某一設(shè)定的結(jié)束條件。分裂聚類(lèi)算法與凝聚型算法相反，首先將所有數(shù)據(jù)對(duì)象存放于一個(gè)類(lèi)中，然后逐漸細(xì)分為越來(lái)越小的類(lèi)，直到所有數(shù)據(jù)對(duì)象單獨(dú)成類(lèi)或符合某個(gè)設(shè)定的結(jié)束條件。典型的層次聚類(lèi)算法有BIRCH、CURE、ROCK等算法。BIRCH算法是一種綜合的層次聚類(lèi)方法，其思想是首先將所有的數(shù)據(jù)對(duì)象按照一定的標(biāo)準(zhǔn)化成很多小的子聚類(lèi)，然后再在子類(lèi)上利用其它合適的聚類(lèi)算法進(jìn)行聚類(lèi)。BIRCH算法伸縮性好并且適用于動(dòng)態(tài)聚類(lèi)。但是BIRCH算法不適應(yīng)于非球狀的聚類(lèi)，對(duì)輸入?yún)?shù)也有些特定要求。CURE算法在開(kāi)始執(zhí)行的時(shí)候是選擇多個(gè)數(shù)據(jù)對(duì)象表示相應(yīng)的類(lèi)，這些數(shù)據(jù)對(duì)象在數(shù)據(jù)庫(kù)中具有一定的代表性。然后根據(jù)規(guī)定的條件向聚類(lèi)中心收縮。該算法受孤立點(diǎn)的影響比較小。但是該算法中由于初始中心數(shù)據(jù)的選擇而受主觀(guān)因素的影響比較突出。ROCK算法是基于CURE算法上的改進(jìn)的算法，它是利用聚類(lèi)間的連接進(jìn)行聚類(lèi)合并，ROCK算法比CURE算法更適用于類(lèi)別屬性的數(shù)據(jù)?；趯哟蔚木垲?lèi)在實(shí)際的操作過(guò)程中，每一步一旦執(zhí)行不能被退回，而且各類(lèi)之間的數(shù)據(jù)對(duì)象也不能任意交換，這樣容易形成質(zhì)量較差的聚類(lèi)結(jié)果。但層次聚類(lèi)算法實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單，所以在實(shí)際應(yīng)用中廣受用戶(hù)歡迎。

3.3 密度方法

基于密度的聚類(lèi)的主要思想是依據(jù)數(shù)據(jù)對(duì)象的分布密度進(jìn)行聚類(lèi)，首先該算法將含有超過(guò)一定數(shù)目的數(shù)據(jù)對(duì)象的區(qū)域連接起來(lái)聚集成一類(lèi)，然后對(duì)沒(méi)有歸類(lèi)的區(qū)域進(jìn)行聚類(lèi)，只要一個(gè)區(qū)域內(nèi)的數(shù)據(jù)對(duì)象的密度大過(guò)事先設(shè)定的閾值，就把該區(qū)域的數(shù)據(jù)對(duì)象和它最近的聚類(lèi)合并為同一類(lèi)?；诿芏鹊木垲?lèi)算法克服了基于距離聚類(lèi)算法不能發(fā)現(xiàn)復(fù)雜形狀聚類(lèi)的弱點(diǎn)，而且基于密度的聚類(lèi)算法不需要預(yù)先輸入聚類(lèi)的數(shù)目，并可用來(lái)過(guò)濾“噪聲”數(shù)據(jù)。典型的基于密度的聚類(lèi)算法有：DBSCAN算法、PTICS算法、DENCLUE算法等。DBSCAN聚類(lèi)算法主要是通過(guò)檢測(cè)數(shù)據(jù)庫(kù)中每個(gè)數(shù)據(jù)點(diǎn)的臨域來(lái)進(jìn)行聚類(lèi)。若一個(gè)點(diǎn)p的鄰域中包含數(shù)據(jù)對(duì)象的密度大于最小閥值，就會(huì)創(chuàng)建一個(gè)以p作為中心點(diǎn)的新聚類(lèi)，然后搜尋與中心數(shù)據(jù)點(diǎn)直接密度可達(dá)的數(shù)據(jù)點(diǎn)加入到相應(yīng)聚類(lèi)中，重復(fù)這個(gè)過(guò)程，直到所有聚類(lèi)不在變化時(shí)，該算法結(jié)束。該算法的優(yōu)點(diǎn)是可以發(fā)現(xiàn)任意形狀的聚類(lèi)并且能很好的處理噪聲數(shù)據(jù)，缺點(diǎn)是對(duì)用戶(hù)定義的參數(shù)敏感、算法效率不高。PTICS很好的處理了參數(shù)選擇的問(wèn)題，其算法思想是為自動(dòng)交互的聚類(lèi)分析計(jì)算出一個(gè)增強(qiáng)聚類(lèi)順序，而并不像其他聚類(lèi)方法一樣明確產(chǎn)生一個(gè)聚類(lèi)。DENCLUE算法是一種基于一組密度分布函數(shù)的聚類(lèi)算法，主要思想是首先用某種數(shù)學(xué)函數(shù)來(lái)刻畫(huà)每個(gè)數(shù)據(jù)點(diǎn)的影響，所有數(shù)據(jù)點(diǎn)的影響函數(shù)的總和構(gòu)成空間數(shù)據(jù)的整體密度，聚類(lèi)通過(guò)確定全局密度函數(shù)的局部最大來(lái)得到。該聚類(lèi)算法可以發(fā)現(xiàn)任意形狀聚類(lèi)，受孤立點(diǎn)的影響小。

3.4 網(wǎng)格方法

基于網(wǎng)格的聚類(lèi)算法使用了一種多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，該類(lèi)算法首先將數(shù)據(jù)空間劃分為有限數(shù)目的單元（看似是由正方體或長(zhǎng)方體組成的網(wǎng)格），然后以網(wǎng)格上的單元為對(duì)象進(jìn)行聚類(lèi)操作。基于網(wǎng)絡(luò)的聚類(lèi)算法的優(yōu)點(diǎn)是處理速度快，因?yàn)樵撍惴ǖ奶幚頃r(shí)間不依賴(lài)于數(shù)據(jù)對(duì)象的個(gè)數(shù)，僅僅與劃分的單元個(gè)數(shù)有關(guān)。另外該方法的聚類(lèi)結(jié)果與數(shù)據(jù)的輸入順序無(wú)關(guān)，兼容性比較好，可以處理多種類(lèi)型的數(shù)據(jù)，但這樣操作卻會(huì)帶來(lái)一定的代價(jià)，使得聚類(lèi)的質(zhì)量和準(zhǔn)確性有所降低?；诰W(wǎng)格的聚類(lèi)算法的缺點(diǎn)是只能尋找到邊緣是垂直或水平的聚類(lèi)，而無(wú)法發(fā)現(xiàn)斜邊緣的聚類(lèi)。典型的基于網(wǎng)格的聚類(lèi)方法有STING、WaveCluster 和CLIQUE等算法。STING算法將空間劃分為許多方形單元，再根據(jù)方形單元分辨率的級(jí)別不同把方形單元?jiǎng)澐譃椴煌募?jí)別，然后這些方形單元再根據(jù)級(jí)別的不同構(gòu)成一個(gè)層次結(jié)構(gòu)。該算法有益于增量更新與并行處理，但聚類(lèi)的質(zhì)量往往受網(wǎng)格結(jié)構(gòu)最底層的粒度大小的影響。Wavecluster算法以信號(hào)處理思想為基礎(chǔ)網(wǎng)格聚類(lèi)算法，該算法采用數(shù)據(jù)空間上強(qiáng)加的一個(gè)多維網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行匯總數(shù)據(jù)。LIQUE 算法融合了基于密度和基于網(wǎng)格的聚類(lèi)思想，即使對(duì)于大規(guī)模高維數(shù)據(jù)也能取得較好的聚類(lèi)效果。

3.5 模型方法

基于模型的聚類(lèi)方法的基本思想是：首先對(duì)要進(jìn)行聚類(lèi)的數(shù)據(jù)集設(shè)定多個(gè)數(shù)據(jù)模型，然后嘗試尋找數(shù)據(jù)集與這些數(shù)學(xué)模型的最佳匹配，此方法操作的基礎(chǔ)是假定數(shù)據(jù)集都有一個(gè)內(nèi)在的混合概率分布。當(dāng)前多數(shù)基于模型的算法主要應(yīng)用于仿生學(xué)方面?；谀Ｐ偷牡湫途垲?lèi)方法有兩種：統(tǒng)計(jì)學(xué)方法（例如COBWEB、CLASSIT和AutoClass）和神經(jīng)網(wǎng)絡(luò)方法（例如SOM、ART、LVQ）。COBWEB算法是一種非常有代表性的簡(jiǎn)單增量概念聚類(lèi)算法，該算法使用分類(lèi)屬性-值對(duì)來(lái)描述輸入對(duì)象，采用分類(lèi)樹(shù)的形式創(chuàng)建層次聚類(lèi)。COBWEB 算法的優(yōu)勢(shì)是在不需要任何參數(shù)下可以自動(dòng)更改劃分中類(lèi)的個(gè)數(shù)，這種操作是在每個(gè)屬性上的概率分布是相互沒(méi)有聯(lián)系的基礎(chǔ)上操作的，但COBWEB算法基于的假設(shè)條件不一定總是正確的，這在一定程度上會(huì)影響聚類(lèi)結(jié)果，且該聚類(lèi)算法不適合應(yīng)用于數(shù)據(jù)量很大的數(shù)據(jù)集。CLASSIT算法是在COBWEB算法基礎(chǔ)上改進(jìn)的算法，該算法利用一個(gè)改進(jìn)的分類(lèi)描述方法，允許對(duì)連續(xù)取值屬性進(jìn)行增量式聚類(lèi)操作，聚類(lèi)過(guò)程中為每個(gè)結(jié)點(diǎn)中的所有屬性存儲(chǔ)相應(yīng)的連續(xù)正態(tài)分布。CLASSIT算法同樣也不適合應(yīng)用于數(shù)據(jù)量很大的數(shù)據(jù)集。AutoClass 聚類(lèi)算法類(lèi)的個(gè)數(shù)由貝葉斯統(tǒng)計(jì)分析來(lái)估算獲得。SOM[9]（Self-Organizing Maps ）算法效仿人腦處理信號(hào)的特點(diǎn)開(kāi)發(fā)出的一種人工神經(jīng)網(wǎng)絡(luò)聚類(lèi)算法，該算法是可視的、高緯的、無(wú)監(jiān)督的，在信息處理領(lǐng)域（如圖像處理、語(yǔ)音識(shí)別等）應(yīng)用的比較廣。

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

本文分析了基于不同思想的各類(lèi)聚類(lèi)算法，用戶(hù)應(yīng)該根據(jù)實(shí)際應(yīng)用中的具體問(wèn)題具體分析，選擇恰當(dāng)?shù)木垲?lèi)算法。聚類(lèi)算法具有非常廣泛的應(yīng)用，改進(jìn)聚類(lèi)算法或者開(kāi)發(fā)新的聚類(lèi)算法是一件非常有意義工作，相信在不久的將來(lái)，聚類(lèi)算法將隨著新技術(shù)的出現(xiàn)和應(yīng)用的需求而得到蓬勃的發(fā)展。

參考文獻(xiàn)：

[1]陳良維.數(shù)據(jù)挖掘中聚類(lèi)算法研究[J].載《微計(jì)算機(jī)信息》，2006，21.

[2]Anil K.Jain.Data clustering：50 years beyond K-means[J].Parrern Recognition Letters.2009（31）

[3]孫吉貴，劉杰，趙連宇.聚類(lèi)算法研究[J].軟件學(xué)報(bào)，2008，19（1）：9.

[4]胡慶林，葉念渝，朱明富.數(shù)據(jù)挖掘中聚類(lèi)算法研究[J].載《計(jì)算機(jī)與數(shù)字工程》，2007，2.

[作者簡(jiǎn)介]

劉鳳芹（1984- ），女，山東濟(jì)南人，山東師范大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究方向?yàn)樗惴◤?fù)雜性理論、計(jì)算生物學(xué)。