聚類算法研究綜述

1、電腦知識(shí)與技術(shù)本欄目責(zé)任編輯:聞翔軍數(shù)據(jù)庫(kù)及信息管理1引言數(shù)據(jù)挖掘是指從從大量無序的數(shù)據(jù)中提取隱含的、有效的、可理解的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則,為用戶提供問題求解層次的決策支持能力。數(shù)據(jù)挖掘主要的算法有分類模式、關(guān)聯(lián)規(guī)則、決策樹、序列模式、聚類模式分析、神經(jīng)網(wǎng)絡(luò)算法等等。聚類算法是一種有效的非監(jiān)督機(jī)器學(xué)習(xí)算法,是數(shù)據(jù)挖掘中的一個(gè)非常重要的研究課題。當(dāng)人們使用數(shù)據(jù)挖掘工具對(duì)數(shù)據(jù)中的模型和關(guān)系進(jìn)行辨識(shí)的時(shí)候,通常第一個(gè)步驟就是聚類,其目的就是將集中的數(shù)據(jù)人為地劃分成若干類,使簇內(nèi)相似度盡可能大、簇間相似度盡可能小,以揭示這些數(shù)據(jù)分布的真實(shí)情況。但任何聚類算法都對(duì)數(shù)據(jù)集本身有一定的預(yù)先假設(shè),根

2、據(jù)文獻(xiàn)1的理論,如果數(shù)據(jù)集本身的分布并不符合預(yù)先的假設(shè),則算法的結(jié)果將毫無意義。因此,面對(duì)特定的應(yīng)用問題,如何選擇合適的聚類算法是聚類分析研究中的一個(gè)重要課題。本文比較了數(shù)據(jù)挖掘中現(xiàn)有聚類算法的性能,分析了它們各自的優(yōu)缺點(diǎn),并指出了其今后的發(fā)展趨勢(shì)。2聚類算法分類研究聚類的目的是把大量數(shù)據(jù)點(diǎn)的集合分成若干類,使得每個(gè)類中的數(shù)據(jù)之間最大程度地相似,而不同類中的數(shù)據(jù)最大程度地不同。通常聚類算法可以分為層次聚類、分割聚類、密度型聚類、網(wǎng)格型聚類和其他聚類等幾種。2.1層次聚類層次聚類算法通過將數(shù)據(jù)組織成若干組并形成一個(gè)相應(yīng)的樹狀圖來進(jìn)行聚類,它又可以分為兩類,即自底向上的聚合層次聚類和自頂向下的分裂

3、層次聚類。聚結(jié)型算法采用自底向上的策略,首先把每個(gè)對(duì)象單獨(dú)作為一個(gè)聚類,然后根據(jù)一定的規(guī)則合并成為越來越大的聚類,直到最后所有的對(duì)象都?xì)w入到一個(gè)聚類中。大多數(shù)層次聚類算法都屬于聚結(jié)型算法,它們之間的區(qū)別在于類間相似度的定義不同。與聚結(jié)型算法相反,分裂型算法采用自頂向下的方法,它先將所有的對(duì)象都看成一個(gè)聚類,然后將其不斷分解直至每個(gè)對(duì)象都獨(dú)自歸入一個(gè)聚類。一般情況下不使用分裂型方法,因?yàn)樵谳^高的層次很難進(jìn)行正確的拆分。純粹的層次聚類算法的缺點(diǎn)在于一旦進(jìn)行合并或分裂之后,就無法再進(jìn)行調(diào)整?，F(xiàn)在的一些研究側(cè)重于層次聚類算法與循環(huán)的重新分配方法的結(jié)合。主要的層次聚類算法有BIRCH ,CURE ,RO

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

5、為k 個(gè)劃分,每個(gè)劃分作為一個(gè)聚類,然后從這k 個(gè)初始劃分開始,通過重復(fù)的控制策略,使某個(gè)準(zhǔn)則最優(yōu)化,而每個(gè)聚類由其質(zhì)心來代表(k-means 算法,或者由該聚類中最靠近中心的一個(gè)對(duì)象來代表(k-medoids 算法,以達(dá)到最終的結(jié)果。分割聚類算法收斂速度快,缺點(diǎn)在于它傾向于識(shí)別凸形分布大小相近、密度相近的聚類,不能發(fā)現(xiàn)分布形狀比較復(fù)雜的聚類,它要求類別數(shù)目k 可以合理地估計(jì),并且初始中心的選擇和噪聲會(huì)對(duì)聚類結(jié)果產(chǎn)生很大影響。這類方法又可分為基于密度的聚類、基于網(wǎng)格的聚類等。很多算法中都使用距離來描述數(shù)據(jù)之間的相似性,但是,對(duì)于非凸數(shù)據(jù)集,只用距離來描述是不夠的。對(duì)于這種情況,要用密度來取代相

6、似性,這就是基于密度的聚類算法。基于密度的算法從數(shù)據(jù)對(duì)象的分布密度出發(fā),把密度足夠大的區(qū)域連接起來,從而可以發(fā)現(xiàn)任意形狀的類。此類算法除了可以發(fā)現(xiàn)任意形狀的類,還能夠有效去除噪聲。基于網(wǎng)格的聚類算法,把空間量化為有限個(gè)單元(即長(zhǎng)方體或超長(zhǎng)方體,然后對(duì)量化后的空間進(jìn)行聚類。此類算法具有很快的處理速度。缺點(diǎn)是只能發(fā)現(xiàn)邊界是水平或垂直的聚類,而不能檢測(cè)到斜邊界。此類算法具有很快的處理速度。時(shí)間復(fù)雜度一般由網(wǎng)格單元的數(shù)目決定,而與數(shù)據(jù)集的大小無關(guān)。此外,聚類的精度取決于網(wǎng)格單元的大小。此類算法不適用于高維情況,因?yàn)榫W(wǎng)格單元的數(shù)目隨著維數(shù)的增加而呈指數(shù)增長(zhǎng)。所有基于網(wǎng)格的聚類算法都存在下列問題:一是如何

7、選擇合適的單元大小和數(shù)目;二是怎樣對(duì)每個(gè)單元中對(duì)象的信息進(jìn)行匯總。主要的分割聚類算法有k -means ,EM ,k -medoids ,收稿日期:2007-06-10作者簡(jiǎn)介:項(xiàng)冰冰(1980-,女,安徽合肥人,安徽大學(xué)助教,工學(xué)學(xué)士,研究方向:數(shù)據(jù)挖掘,人工智能;錢光超(1982-,男,安徽安徽無為人,安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院05級(jí)研究生,工學(xué)學(xué)士。聚類算法研究綜述項(xiàng)冰冰1,錢光超2(1.安徽大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院安徽合肥23039;2.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院安徽合肥230039摘要:聚類是數(shù)據(jù)挖掘中用來發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的一項(xiàng)重要技術(shù)。闡述了聚類算法基本原理,總結(jié)了聚類算法

8、的研究現(xiàn)狀,按照聚類算法的分類,分析比較了幾種典型聚類的性能差異和各自存在的優(yōu)點(diǎn)及問題,并結(jié)合應(yīng)用需求指出了其今后的發(fā)展趨勢(shì)。關(guān)鍵詞:數(shù)據(jù)挖掘;聚類分析;聚類算法中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(200712-21500-02The Research of Clustering AlgorithmsXIANG Bing-bing 1,QIAN Guang-chao 2(1.School of Mathematics and Computational Science,Anhui University,Hefei,Anhui Province 230039,

9、China ;2.School of Computer Scienceand Technology ,Anhui University,Hefei,Anhui Province 230039,ChinaAbstract :Clustering is an important technique in data mining.It s used to discover the data distribution and concealed patterns.The paper elucidate the basic principle of the clustering algorithms a

10、nd sum up the contemporary research of the clustering algorithms.It also analyze a few representative clustering algorithms and compare their differences ,advantages and disadvantages.At last ,the paper indicate the development trend of clustering integrating the application demand.Key word:Data min

11、ing ;Clustering Analysis ;Clustering Algorithms1500本欄目責(zé)任編輯:聞翔軍數(shù)據(jù)庫(kù)及信息管理CLARA,CLARANS等。常見的k-medoids算法有PAM算法、CLARA算法、CLARANS算法。2.3其他聚類主要有:基于約束的聚類算法、機(jī)器學(xué)習(xí)中的聚類算法、用于高維數(shù)據(jù)的聚類算法等。基于約束的聚類算法,其約束可以是對(duì)個(gè)體對(duì)象的約束,也可以是對(duì)聚類參數(shù)的約束,它們均來自相關(guān)領(lǐng)域的經(jīng)驗(yàn)知識(shí)。該方法的一個(gè)重要應(yīng)用在于對(duì)存在障礙數(shù)據(jù)的二維空間數(shù)據(jù)進(jìn)行聚類。COD(Clustering with Obstructed Distance5就是處理這類問

12、題的典型算法,其主要思想是用兩點(diǎn)之間的障礙距離取代了一般的歐氏距離來計(jì)算其間的最小距離。機(jī)器學(xué)習(xí)中的聚類算法是指與機(jī)器學(xué)習(xí)相關(guān)、采用了某些機(jī)器學(xué)習(xí)理論的聚類方法,它主要包括人工神經(jīng)網(wǎng)絡(luò)方法以及基于進(jìn)化理論的方法。如自組織特征映射(SOM網(wǎng)絡(luò)是利用人工神經(jīng)網(wǎng)絡(luò)進(jìn)行聚類的較早嘗試,它也是向量量化方法的典型代表之一。在基于進(jìn)化理論的聚類方法中,模擬退火的應(yīng)用較為廣泛, SNICC算法6就是其中之一。遺傳算法也可以用于聚類處理,它主要通過選擇、交叉和變異這三種遺傳算子的運(yùn)算以不斷優(yōu)化可選方案從而得到最終的聚類結(jié)果。高維數(shù)據(jù)聚類是目前多媒體數(shù)據(jù)挖掘領(lǐng)域面臨的重大挑戰(zhàn)之一,除了降維這一最直接的方法之外,對(duì)

13、高維數(shù)據(jù)的聚類處理還包括子空間聚類以及聯(lián)合聚類技術(shù)等。子空間聚類算法,認(rèn)為在高維數(shù)據(jù)集中,聚類往往不是存在于整個(gè)空間中,而是存在于某些子空間中。它們針對(duì)高維空間數(shù)據(jù),尋找子空間中的聚類。主要子空間聚類算法有CLIQUE,PROCLUS等。3典型聚類算法性能比較3.1CLARANS算法CLARANS通過利用多次不同抽樣改進(jìn)了CLARA算法,是一種k-中心點(diǎn)聚類方法。它首先隨機(jī)選擇一個(gè)點(diǎn)作為當(dāng)前點(diǎn),然后隨機(jī)檢查它周圍不超過參數(shù)Maxeighbar個(gè)的一些鄰接點(diǎn)。假如找到一個(gè)比它更好的鄰接點(diǎn),則把它移入該鄰接點(diǎn),否則把該點(diǎn)作為局部最小量。然后再隨機(jī)選擇一個(gè)點(diǎn)來尋找另一個(gè)局部最小量,直至所找到的局部最

14、小量數(shù)目達(dá)到用戶要求為止。該算法要求聚類的對(duì)象必須預(yù)先調(diào)入內(nèi)存,并且需多次掃描數(shù)據(jù)集,其時(shí)空復(fù)雜度都相當(dāng)大,雖通過引入R*樹結(jié)構(gòu)對(duì)其性能進(jìn)行改善,但構(gòu)造和維護(hù)代價(jià)太大。該算法對(duì)臟數(shù)據(jù)和異常數(shù)據(jù)不敏感,但對(duì)數(shù)據(jù)輸入順序異常敏感,且只能處理凸形或球形邊界聚類,效率較高。3.2BIRCH算法BIRCH是一個(gè)綜合性的層次聚類方法,它利用層次方法的平衡迭代進(jìn)行歸約和聚類。其核心是用一個(gè)聚類特征三元組表示一個(gè)簇的有關(guān)信息,從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類特征。它通過構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹來求聚類。該算法通過聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn)算。算法具有對(duì)象數(shù)目的線

15、性易伸縮性,及良好的聚類質(zhì)量。一次掃描就可以進(jìn)行較好的聚類,其計(jì)算復(fù)雜度為O(n。BIRCH算法只適用于類的分布呈凸形及球形的情況,對(duì)不可視的高維數(shù)據(jù)則是不可行的。3.3DBSCAN算法DBSCAN是基于密度的聚類算法,可以將足夠高密度的區(qū)域劃分為簇,并可以在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。該算法利用類的密度連通性可以快速發(fā)現(xiàn)任意形狀的類。其基本思想是:對(duì)于一個(gè)類中的每個(gè)對(duì)象,在其給定半徑的領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。DBSCAN算法不進(jìn)行任何的預(yù)處理而直接對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類操作。當(dāng)數(shù)據(jù)量非常大時(shí),就必須有大量?jī)?nèi)存支持,I/O消耗也非常大。其時(shí)間復(fù)雜度為O(nl

16、ogn,聚類過程的大部分時(shí)間用在區(qū)域查詢操作上。DBSCAN算法能夠發(fā)現(xiàn)空間數(shù)據(jù)庫(kù)中任意形狀的密度連通集;在給定合適的參數(shù)條件下,能很好地處理噪聲點(diǎn);對(duì)用戶領(lǐng)域知識(shí)要求較少;對(duì)數(shù)據(jù)的輸入順序不太敏感;適用于大型數(shù)據(jù)庫(kù)。但DBSCAN算法要求事先指定領(lǐng)域和閾值,具體使用的參數(shù)依賴于應(yīng)用的目的。3.4STING算法STING是一種格的多分辨率聚類技術(shù)。它將空間區(qū)域劃分為矩形單元,針對(duì)不同級(jí)別的分辨率,通常存在多個(gè)級(jí)別的矩形單元,這些單元形成了一個(gè)層次結(jié)構(gòu):高層的每個(gè)單元被劃分為多個(gè)低一層的單元。高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從低層單元的計(jì)算得到。STING掃描數(shù)據(jù)庫(kù)一次來計(jì)算單元的統(tǒng)計(jì)信息,因此產(chǎn)

17、生聚類的時(shí)間復(fù)雜度是O(n,其中n是對(duì)象的數(shù)目。在層次結(jié)構(gòu)建立后,查詢處理時(shí)間是O(g,g是最低層風(fēng)格單元的數(shù)目,通常遠(yuǎn)遠(yuǎn)小于n。STING是獨(dú)立于查詢的,有利于并行處理和增量更新且效率較高。但由于STING采用了一個(gè)多分辨率的方法來進(jìn)行聚類分析,聚類的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)的最低層粒度。如果數(shù)據(jù)粒度比較細(xì),處理的代價(jià)會(huì)明顯增加。并且,STING在構(gòu)建一個(gè)父單元時(shí)沒有考慮子單元和其相鄰單元之間的關(guān)系,因此,盡管該技術(shù)處理速度快,但可能降低簇的質(zhì)量和精確性。4結(jié)論和展望聚類分析是數(shù)據(jù)挖掘中一種非常有用的技術(shù),它可作為特征和分類算法的預(yù)處理步驟,也可將聚類結(jié)果用于進(jìn)一步關(guān)聯(lián)分析,還可以作為一個(gè)獨(dú)立的工

18、具來獲得數(shù)據(jù)分布的情況。聚類算法的研究具有廣泛的應(yīng)用前景,其今后的發(fā)展也面臨著越來越多的挑戰(zhàn)。首先是聚類算法的選擇,建議使用者根據(jù)實(shí)際情況(例如發(fā)現(xiàn)聚類的形狀、數(shù)據(jù)輸入順序是否敏感、適用數(shù)據(jù)庫(kù)的大小或者算法效率來選擇合適的聚類算法。其次,對(duì)于特征數(shù)據(jù)本身所具備的高維性、復(fù)雜性、動(dòng)態(tài)性以及容易達(dá)到大規(guī)模的特性,聚類算法的設(shè)計(jì)還應(yīng)該更多地考慮融合不同的聚類思想形成新的聚類算法,從而綜合利用不同聚類算法的優(yōu)點(diǎn)。參考文獻(xiàn):1R O Duda,P E Hart,D G Stork.Pattern Classification(2nd EditionM.New York:Wiley,2001.4542458.2Guha S,Rastogi R,Shim K.CURE:An Efficient Clus