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

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

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

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

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

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

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

8、的研究現狀,按照聚類算法的分類,分析比較了幾種典型聚類的性能差異和各自存在的優點及問題,并結合應用需求指出了其今后的發展趨勢。關鍵詞:數據挖掘;聚類分析;聚類算法中圖分類號:TP301.6文獻標識碼: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本欄目責任編輯:聞翔軍數據庫及信息管理CLARA,CLARANS等。常見的k-medoids算法有PAM算法、CLARA算法、CLARANS算法。2.3其他聚類主要有:基于約束的聚類算法、機器學習中的聚類算法、用于高維數據的聚類算法等。基于約束的聚類算法,其約束可以是對個體對象的約束,也可以是對聚類參數的約束,它們均來自相關領域的經驗知識。該方法的一個重要應用在于對存在障礙數據的二維空間數據進行聚類。COD(Clustering with Obstructed Distance5就是處理這類問

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

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

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

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

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

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

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