聚類算法研究綜述

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

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

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

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

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

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

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

8、的研究現(xiàn)狀,按照聚類算法的分類,分析比較了幾種典型聚類的性能差異和各自存在的優(yōu)點及問題,并結(jié)合應(yīng)用需求指出了其今后的發(fā)展趨勢。關(guān)鍵詞:數(shù)據(jù)挖掘;聚類分析;聚類算法中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:A 文章編號: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ù)庫及信息管理CLARA,CLARANS等。常見的k-medoids算法有PAM算法、CLARA算法、CLARANS算法。2.3其他聚類主要有:基于約束的聚類算法、機器學(xué)習(xí)中的聚類算法、用于高維數(shù)據(jù)的聚類算法等?；诩s束的聚類算法,其約束可以是對個體對象的約束,也可以是對聚類參數(shù)的約束,它們均來自相關(guān)領(lǐng)域的經(jīng)驗知識。該方法的一個重要應(yīng)用在于對存在障礙數(shù)據(jù)的二維空間數(shù)據(jù)進(jìn)行聚類。COD(Clustering with Obstructed Distance5就是處理這類問

12、題的典型算法,其主要思想是用兩點之間的障礙距離取代了一般的歐氏距離來計算其間的最小距離。機器學(xué)習(xí)中的聚類算法是指與機器學(xué)習(xí)相關(guān)、采用了某些機器學(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ōu)化可選方案從而得到最終的聚類結(jié)果。高維數(shù)據(jù)聚類是目前多媒體數(shù)據(jù)挖掘領(lǐng)域面臨的重大挑戰(zhàn)之一,除了降維這一最直接的方法之外,對

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

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

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

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

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

18、具來獲得數(shù)據(jù)分布的情況。聚類算法的研究具有廣泛的應(yīng)用前景,其今后的發(fā)展也面臨著越來越多的挑戰(zhàn)。首先是聚類算法的選擇,建議使用者根據(jù)實際情況(例如發(fā)現(xiàn)聚類的形狀、數(shù)據(jù)輸入順序是否敏感、適用數(shù)據(jù)庫的大小或者算法效率來選擇合適的聚類算法。其次,對于特征數(shù)據(jù)本身所具備的高維性、復(fù)雜性、動態(tài)性以及容易達(dá)到大規(guī)模的特性,聚類算法的設(shè)計還應(yīng)該更多地考慮融合不同的聚類思想形成新的聚類算法,從而綜合利用不同聚類算法的優(yōu)點。參考文獻(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