聚類算法研究綜述

鄭強 高群

摘要：隨著數據挖掘技術的迅速發展，作為其重要的組成部分，聚類技術已經被廣泛應用于數據分析、圖像處理、市場研究等許多領域。聚類算法研究已經成為數據挖掘研究領域中非常活躍的一個研究課題。本文分析了各類常見聚類算法的應用場景及優缺點，指出了聚類分析研究重點關注內容。

關鍵詞：聚類；劃分聚類；層次聚類

1 引言

同時，聚類作為數據挖掘的主要方法之一，越來越引起人們的關注。聚類[1]分析是一種無先驗知識的機器學習過程，是數據挖掘一個重要的分支，遵循同一個集合中的樣本相似性最大，不同集合中的樣本差異性最大的思想，把樣本集分為若干個集合，每個集合稱為一個簇。通過聚類， 人們能夠識別密集的和稀疏的區域， 發現全局的分布模式以及數據屬性之間有意義的相互關系。

聚類算法在計算機科學、生醫學、地球科學、社會科學、經濟學等領域都有廣泛的應用。已有的經典聚類算法大致可分為五種：基于劃分的、基于層次的、基于密度的、基于網格的和基于圖論的聚類。本文比較了數據挖掘中典型的聚類算法，分析了它們各自的優缺點并指出了其面臨的挑戰。

2典型聚類算法

2.1劃分聚類方法

劃分聚類[2]將數據對象劃分成不重疊的子集，使得每個數據對象都分布在不同的子集中。最經典的聚類算法是K-Means[3]，其主要思想是找出數據集的k個聚類中心，把數據集劃分為是k個類簇，使得數據集中的數據點與所屬類簇的類中心的距離平方和最小。該算法優點是算法簡單易于實現，但是需人工指定聚類數，同時受聚類中心的初始選擇影響大，易陷入局部最優解。K-modes是K-Means算法的一個延伸，主要是可處理分類屬性數據，而不像K-Means那樣只能處理數值屬性的數據。K-Means和K-modes處理離群點時候性能較差。AP是Frey等人2007年提出的一種聚類算法，該算法與K-means算法等同屬于k中心聚類方法， AP算法部分地克服了K-means對初始聚類中心的選擇敏感且容易陷入局部極值的缺陷。

2.2基于密度的聚類

基于密度的聚類算法從數據對象的分布密度出發，將密度足夠大的相鄰區域連接起來，從而可以發現具有任意形狀的聚類，并能有效處理異常數據，它主要用于對空間數據的聚類。DBSCAN[4]是一個典型的基于密度的聚類方法，它將聚類定義為一組密度連接的點集，然后通過不斷生長足夠高密度的區域來進行聚類。DENCLUE[5]則根據數據點在屬性空間中的密度來進行聚類。從本質上講，DENCLUE是基于密度的聚類算法與基于網格的預處理的結合，它受目標數據的維度影響較小。

2.3 基于網格的聚類

基于網格的聚類從對數據空間劃分的角度出發，利用屬性空間的多維網格數據結構，將空間劃分為有限數目的單元以構成一個可以進行聚類分析的網格結構。該方法的主要特點是處理時間與數據對象的數目無關，但與每維空間所劃分的單元數相關。與基于密度的聚類只能處理數值屬性的數據所不同，基于網格的聚類可以處理任意類型的數據，但以降低聚類的質量和準確性為代價。STING[6]是一個基于網格多分辨率的聚類方法，它將空間劃分為方形單元，不同層次的方形單元對應不同層次的分辨率。CLIQUE[7]也是一個基于網格的聚類算法，它結合了網格聚類與密度聚類的思想，對于處理大規模高維數據具有較好的效果。

2.4 基于圖論的聚類

基于圖論的方法是把聚類轉換為一個組合優化問題，并利用圖論和相關的啟發式算法來解決該問題。基于超圖的劃分和基于光譜的圖劃分方法是這類算法的兩個主要應用形式。該方法的一個優點在于它不需要進行一些相似度的計算，就能把聚類問題映射為圖論中的一個組合優化問題。

2.5層次聚類算法

層次聚類[8]算法通過將數據組織成若干組并形成一個相應的樹狀圖來進行聚類，它又可以分為兩類，即自底向上的聚合層次聚類和自頂向下的分解層次聚類。聚合聚類的策略是先將每個對象各自作為一個原子聚類，然后對這些原子聚類逐層進行聚合，直至滿足一定的終止條件；后者則與前者相反，它先將所有的對象都看成一個聚類，然后將其不斷分解直至滿足終止條件。

CURE[9]，ROCK[10] 和CHAMELEON[11] 算法是聚合聚類中最具代表性的三個方法。Guha 等人在1998 年提出了CURE 算法。該方法不用單個中心或對象來代表一個聚類，而是選擇數據空間中固定數目的、具有代表性的一些點共同來代表相應的類，這樣就可以識別具有復雜形狀和不同大小的聚類，從而能很好地過濾孤立點。ROCK 算法是對CURE 的改進，除了具有CURE 算法的一些優良特性之外，它還適用于類別屬性的數據。CHAMELEON算法是Karypis 等人于1999 年提出來的，它在聚合聚類的過程中利用了動態建模的技術。

結束語

本文分析了各類常見聚類算法的應用場景及優缺點，指出了聚類分析研究重點關注內容。聚類算法的研究具有廣泛的應用前景，其今后的發展也面臨著越來越多的挑戰，尤其是以下幾個方面更值得考慮：選取合適的聚類類別數；處理大規模數據和高維數據的能力；將領域知識引入聚類過程；對聚類的結果進行準確評價，以判斷是否達到最優解等。

參考文獻：

[1]孫吉貴， 劉杰， 趙連宇. 聚類算法研究[J]. 軟件學報， 2008， 19（1）：48-61.

[2]盧志茂， 馮進玫， 范冬梅，等. 面向大數據處理的劃分聚類新方法[J]. 系統工程與電子技術， 2014， 36（5）：1010-1015.

[3]Hartigan J A， Wong M A. Algorithm AS 136： A K-Means Clustering Algorithm[J]. Journal of the Royal Statistical Society， 1979， 28（1）：100-108.

[4]馮少榮， 肖榮俊. DBSCAN 聚類算法的研究與改進[D]. 中國礦業大學學報編輯部， 2008.

[5]張麗芳. 3種聚類算法性能比較分析[J]. 長江大學學報（自科版）， 2009（2）：250-251.

[6]李焱， 劉弘， 鄭向偉. 折半聚類算法在基于社會力的人群疏散仿真中的應用[J]. 計算機應用， 2017， 37（5）：1491-1495.

[7]項響琴， 李紅， 陳圣兵. CLIQUE聚類算法的分析研究[J]. 合肥學院學報（綜合版）， 2011， 21（1）：54-58.

[8]淦文燕， 李德毅， 王建民. 一種基于數據場的層次聚類方法[J]. 電子學報， 2006， 34（2）：258-262.

[9]趙妍， 趙學民. 基于CURE的用戶聚類算法研究[J]. 計算機工程與應用， 2012， 48（11）：97-101.

[10]金陽， 左萬利. 一種基于動態近鄰選擇模型的聚類算法[J]. 計算機學報， 2007， 30（5）：756-762.

[11]龍真真， 張策， 劉飛裔，等. 一種改進的Chameleon算法[J]. 計算機工程， 2009， 35（20）：189-191.