聚類算法總結(jié)

山也美 2015-07-27

展開全文

聚類算法總結(jié) 2013-06-06 14:17:48

分類：大數(shù)據(jù)

（本文轉(zhuǎn)自網(wǎng)上，具體出處忘了是哪里的，好像是上海一位女士在網(wǎng)上的博文，此處轉(zhuǎn)載，用以備查，請原作者見諒）

聚類算法總結(jié)：
---------------------------------------------------------
聚類算法的種類：

基于劃分聚類算法（partition clustering)

k-means：	是一種典型的劃分聚類算法，它用一個聚類的中心來代表一個簇，即在迭代過程中選擇的聚點不一定是聚類中的一個點，該算法只能處理數(shù)值型數(shù)據(jù)
k-modes：	K-Means算法的擴(kuò)展，采用簡單匹配方法來度量分類型數(shù)據(jù)的相似度
k-prototypes：	結(jié)合了K-Means和K-Modes兩種算法，能夠處理混合型數(shù)據(jù)
k-medoids：	在迭代過程中選擇簇中的某點作為聚點，PAM是典型的k-medoids算法
CLARA：	CLARA算法在PAM的基礎(chǔ)上采用了抽樣技術(shù)，能夠處理大規(guī)模數(shù)據(jù)
CLARANS：	CLARANS算法融合了PAM和CLARA兩者的優(yōu)點，是第一個用于空間數(shù)據(jù)庫的聚類算法
Focused CLARAN：	采用了空間索引技術(shù)提高了CLARANS算法的效率
PCM：	模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法

基于層次聚類算法：

CURE：	采用抽樣技術(shù)先對數(shù)據(jù)集D隨機(jī)抽取樣本，再采用分區(qū)技術(shù)對樣本進(jìn)行分區(qū)，然后對每個分區(qū)局部聚類，最后對局部聚類進(jìn)行全局聚類
ROCK：	也采用了隨機(jī)抽樣技術(shù)，該算法在計算兩個對象的相似度時，同時考慮了周圍對象的影響
CHEMALOEN（變色龍算法）：	首先由數(shù)據(jù)集構(gòu)造成一個K-最近鄰圖Gk ,再通過一個圖的劃分算法將圖Gk 劃分成大量的子圖,每個子圖代表一個初始子簇,最后用一個凝聚的層次聚類算法反復(fù)合并子簇，找到真正的結(jié)果簇
SBAC：	SBAC算法則在計算對象間相似度時，考慮了屬性特征對于體現(xiàn)對象本質(zhì)的重要程度，對于更能體現(xiàn)對象本質(zhì)的屬性賦予較高的權(quán)值
BIRCH：	BIRCH算法利用樹結(jié)構(gòu)對數(shù)據(jù)集進(jìn)行處理，葉結(jié)點存儲一個聚類，用中心和半徑表示，順序處理每一個對象，并把它劃分到距離最近的結(jié)點，該算法也可以作為其他聚類算法的預(yù)處理過程
BUBBLE：	BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間
BUBBLE-FM：	BUBBLE-FM算法通過減少距離的計算次數(shù)，提高了BUBBLE算法的效率

基于密度聚類算法：

DBSCAN：	DBSCAN算法是一種典型的基于密度的聚類算法，該算法采用空間索引技術(shù)來搜索對象的鄰域，引入了“核心對象”和“密度可達(dá)”等概念，從核心對象出發(fā)，把所有密度可達(dá)的對象組成一個簇
GDBSCAN：	算法通過泛化DBSCAN算法中鄰域的概念，以適應(yīng)空間對象的特點
DBLASD：
OPTICS：	OPTICS算法結(jié)合了聚類的自動性和交互性，先生成聚類的次序，可以對不同的聚類設(shè)置不同的參數(shù)，來得到用戶滿意的結(jié)果
FDC：	FDC算法通過構(gòu)造k-d tree把整個數(shù)據(jù)空間劃分成若干個矩形空間，當(dāng)空間維數(shù)較少時可以大大提高DBSCAN的效率

基于網(wǎng)格的聚類算法：

STING：	利用網(wǎng)格單元保存數(shù)據(jù)統(tǒng)計信息，從而實現(xiàn)多分辨率的聚類
WaveCluster：	在聚類分析中引入了小波變換的原理，主要應(yīng)用于信號處理領(lǐng)域。（備注：小波算法在信號處理，圖形圖像，加密解密等領(lǐng)域有重要應(yīng)用，是一種比較高深和牛逼的東西）
CLIQUE：	是一種結(jié)合了網(wǎng)格和密度的聚類算法
OPTIGRID：

基于神經(jīng)網(wǎng)絡(luò)的聚類算法：

自組織神經(jīng)網(wǎng)絡(luò)SOM：

該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網(wǎng)絡(luò)中，一開始時，輸入樣本引起輸出興奮細(xì)胞的位置各不相同，但自組織后會形成一些細(xì)胞群，它們分別代表了輸入樣本，反映了輸入樣本的特征

基于統(tǒng)計學(xué)的聚類算法：

COBWeb：	COBWeb是一個通用的概念聚類方法，它用分類樹的形式表現(xiàn)層次聚類
CLASSIT：
AutoClass：	是以概率混合模型為基礎(chǔ)，利用屬性的概率分布來描述聚類，該方法能夠處理混合型的數(shù)據(jù)，但要求各屬性相互獨立

---------------------------------------------------------
幾種常用的聚類算法從可伸縮性、適合的數(shù)據(jù)類型、高維性（處理高維數(shù)據(jù)的能力）、異常數(shù)據(jù)的抗干擾度、聚類形狀和算法效率6個方面進(jìn)行了綜合性能評價，評價結(jié)果如表1所示：

算法名稱	可伸縮性	適合的數(shù)據(jù)類型	高維性	異常數(shù)據(jù)的抗干擾性	聚類形狀	算法效率
WaveCluster	很高	數(shù)值型	很高	較高	任意形狀	很高
ROCK	很高	混合型	很高	很高	任意形狀	一般
BIRCH	較高	數(shù)值型	較低	較低	球形	很高
CURE	較高	數(shù)值型	一般	很高	任意形狀	較高
K-Prototypes	一般	混合型	較低	較低	任意形狀	一般
DENCLUE	較低	數(shù)值型	較高	一般	任意形狀	較高
OptiGrid	一般	數(shù)值型	較高	一般	任意形狀	一般
CLIQUE	較高	數(shù)值型	較高	較高	任意形狀	較低
DBSCAN	一般	數(shù)值型	較低	較高	任意形狀	一般
CLARANS	較低	數(shù)值型	較低	較高	球形	較低

---------------------------------------------------------
目前聚類分析研究的主要內(nèi)容：

對聚類進(jìn)行研究是數(shù)據(jù)挖掘中的一個熱門方向，由于以上所介紹的聚類方法都存在著某些缺點，因此近些年對于聚類分析的研究很多都專注于改進(jìn)現(xiàn)有的聚類方法或者是提出一種新的聚類方法。以下將對傳統(tǒng)聚類方法中存在的問題以及人們在這些問題上所做的努力做一個簡單的總結(jié)：

1 從以上對傳統(tǒng)的聚類分析方法所做的總結(jié)來看，不管是k-means方法，還是CURE方法，在進(jìn)行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目。然而在現(xiàn)實數(shù)據(jù)中，聚類的數(shù)目是未知的，通常要經(jīng)過不斷的實驗來獲得合適的聚類數(shù)目，得到較好的聚類結(jié)果。

2 傳統(tǒng)的聚類方法一般都是適合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類，比如BIRCH方法對于球狀簇有很好的聚類性能，但是對于不規(guī)則的聚類，則不能很好的工作；K-medoids方法不太受孤立點的影響，但是其計算代價又很大。因此如何解決這個問題成為當(dāng)前的一個研究熱點，有學(xué)者提出將不同的聚類思想進(jìn)行融合以形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點，在一次聚類過程中綜合利用多種聚類方法，能夠有效的緩解這個問題。

3 隨著信息時代的到來，對大量的數(shù)據(jù)進(jìn)行分析處理是一個很龐大的工作，這就關(guān)系到一個計算效率的問題。有文獻(xiàn)提出了一種基于最小生成樹的聚類算法，該算法通過逐漸丟棄最長的邊來實現(xiàn)聚類結(jié)果，當(dāng)某條邊的長度超過了某個閾值，那么更長邊就不需要計算而直接丟棄，這樣就極大地提高了計算效率，降低了計算成本。

4 處理大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的能力有待于提高。目前許多聚類方法處理小規(guī)模數(shù)據(jù)和低維數(shù)據(jù)時性能比較好，但是當(dāng)數(shù)據(jù)規(guī)模增大，維度升高時，性能就會急劇下降，比如k-medoids方法處理小規(guī)模數(shù)據(jù)時性能很好，但是隨著數(shù)據(jù)量增多，效率就逐漸下降，而現(xiàn)實生活中的數(shù)據(jù)大部分又都屬于規(guī)模比較大、維度比較高的數(shù)據(jù)集。有文獻(xiàn)提出了一種在高維空間挖掘映射聚類的方法PCKA（Projected Clustering based on the K-Means Algorithm），它從多個維度中選擇屬性相關(guān)的維度，去除不相關(guān)的維度，沿著相關(guān)維度進(jìn)行聚類，以此對高維數(shù)據(jù)進(jìn)行聚類。

5 目前的許多算法都只是理論上的，經(jīng)常處于某種假設(shè)之下，比如聚類能很好的被分離，沒有突出的孤立點等，但是現(xiàn)實數(shù)據(jù)通常是很復(fù)雜的，噪聲很大，因此如何有效的消除噪聲的影響，提高處理現(xiàn)實數(shù)據(jù)的能力還有待進(jìn)一步的提高。