聚類算法研究綜述

鄭強(qiáng) 高群

摘要：隨著數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展，作為其重要的組成部分，聚類技術(shù)已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)分析、圖像處理、市場研究等許多領(lǐng)域。聚類算法研究已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中非常活躍的一個(gè)研究課題。本文分析了各類常見聚類算法的應(yīng)用場景及優(yōu)缺點(diǎn)，指出了聚類分析研究重點(diǎn)關(guān)注內(nèi)容。

關(guān)鍵詞：聚類；劃分聚類；層次聚類

1 引言

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

聚類算法在計(jì)算機(jī)科學(xué)、生醫(yī)學(xué)、地球科學(xué)、社會科學(xué)、經(jīng)濟(jì)學(xué)等領(lǐng)域都有廣泛的應(yīng)用。已有的經(jīng)典聚類算法大致可分為五種：基于劃分的、基于層次的、基于密度的、基于網(wǎng)格的和基于圖論的聚類。本文比較了數(shù)據(jù)挖掘中典型的聚類算法，分析了它們各自的優(yōu)缺點(diǎn)并指出了其面臨的挑戰(zhàn)。

2典型聚類算法

2.1劃分聚類方法

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

2.2基于密度的聚類

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

2.3 基于網(wǎng)格的聚類

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

2.4 基于圖論的聚類

基于圖論的方法是把聚類轉(zhuǎn)換為一個(gè)組合優(yōu)化問題，并利用圖論和相關(guān)的啟發(fā)式算法來解決該問題?；诔瑘D的劃分和基于光譜的圖劃分方法是這類算法的兩個(gè)主要應(yīng)用形式。該方法的一個(gè)優(yōu)點(diǎn)在于它不需要進(jìn)行一些相似度的計(jì)算，就能把聚類問題映射為圖論中的一個(gè)組合優(yōu)化問題。

2.5層次聚類算法

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

CURE[9]，ROCK[10] 和CHAMELEON[11] 算法是聚合聚類中最具代表性的三個(gè)方法。Guha 等人在1998 年提出了CURE 算法。該方法不用單個(gè)中心或?qū)ο髞泶硪粋€(gè)聚類，而是選擇數(shù)據(jù)空間中固定數(shù)目的、具有代表性的一些點(diǎn)共同來代表相應(yīng)的類，這樣就可以識別具有復(fù)雜形狀和不同大小的聚類，從而能很好地過濾孤立點(diǎn)。ROCK 算法是對CURE 的改進(jìn)，除了具有CURE 算法的一些優(yōu)良特性之外，它還適用于類別屬性的數(shù)據(jù)。CHAMELEON算法是Karypis 等人于1999 年提出來的，它在聚合聚類的過程中利用了動態(tài)建模的技術(shù)。

結(jié)束語

本文分析了各類常見聚類算法的應(yīng)用場景及優(yōu)缺點(diǎn)，指出了聚類分析研究重點(diǎn)關(guān)注內(nèi)容。聚類算法的研究具有廣泛的應(yīng)用前景，其今后的發(fā)展也面臨著越來越多的挑戰(zhàn)，尤其是以下幾個(gè)方面更值得考慮：選取合適的聚類類別數(shù)；處理大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的能力；將領(lǐng)域知識引入聚類過程；對聚類的結(jié)果進(jìn)行準(zhǔn)確評價(jià)，以判斷是否達(dá)到最優(yōu)解等。

參考文獻(xiàn)：

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

[2]盧志茂， 馮進(jìn)玫， 范冬梅，等. 面向大數(shù)據(jù)處理的劃分聚類新方法[J]. 系統(tǒng)工程與電子技術(shù)， 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 聚類算法的研究與改進(jìn)[D]. 中國礦業(yè)大學(xué)學(xué)報(bào)編輯部， 2008.

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

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

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

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

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

[10]金陽， 左萬利. 一種基于動態(tài)近鄰選擇模型的聚類算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2007， 30（5）：756-762.

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