聚類算法總結(jié)

1、聚類算法的種類:基于劃分聚類算法(partition clustering)k-mea ns： 11是一種典型的劃分聚類算法，它用一個聚類的中心來代表一個簇，即在迭代過程中選擇的聚點 不一定是聚類中的一個點，該算法只能處理數(shù)值型數(shù)據(jù)k-modes:K-Mea ns算法的擴展，米用簡單匹配方法來度量分類型數(shù)據(jù)的相似度411k-prototypes結(jié)合了 K-Means和K-Modes兩種算法，能夠處理混合型數(shù)據(jù)k-medoids :在迭代過程中選擇簇中的某點作為聚點，PAM是典型的k-medoids算法CLARACLARAI法在PAM勺基礎(chǔ)_上米用了抽樣技術(shù)，能夠處理大規(guī)模數(shù)據(jù)CLARANSCL

2、ARAN算法融合了 PAM和CLARA、者的優(yōu)點，是第一個用于空間數(shù)據(jù)庫的聚類算法：Focused LARAN米用了空間索引技術(shù)提高了 CLARA N算法的效率PCM模糊集合理論引入聚類分析中并提出了 PCM莫糊聚類算法基于層次聚類算法:CURE米用抽樣技術(shù)先對數(shù)據(jù)集D隨機抽取樣本，再米用分區(qū)技術(shù)對樣本進行分區(qū)，然后對每個 分區(qū)局部聚類，最后對局部聚類進行全局聚類ROCK也米用了隨機抽樣技術(shù)，該算法在計算兩個對象的相似度時，同時考慮了周圍對象的影響CHEMALOEJ變色龍算法)：首先由數(shù)據(jù)集構(gòu)造成一個K-最近鄰圖Gk，再通過一個圖的劃分算法將圖Gk劃分成大量的 子圖，每個子圖代表一個初始子簇，

3、最后用一個凝聚的層次聚類算法反復(fù)合并子簇，找到 真正的結(jié)果簇SBACSBAC算法則在計算對象間相似度時，考慮了屬性特征對于體現(xiàn)對象本質(zhì)的重要程度，對 于更能體現(xiàn)對象本質(zhì)的屬性賦予較周的權(quán)值BIRCHBIRCH算法利用樹結(jié)構(gòu)對數(shù)據(jù)集進行處理，葉結(jié)點存儲一個聚類，用中心和半徑表示，順 序處理每一個對象，并把它劃分到距離最近的結(jié)點，該算法也可以作為其他聚類算法的預(yù)處 理過程BUBBLEBUBBLES法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間BUBBLE-FMBUBBLE-F算法通過減少距離的計算次數(shù)，提高了 BUBBLES法的效率基于密度聚類算法:DBSCANDBSCAh算法是一種典型

4、的基于密度的聚類算法，該算法米用空間索引技術(shù)來搜索對象的 鄰域，弓1入了 “核心對象”和“密度可達”等概念，從核心對象出發(fā)，把所有密度可達 的對象組成一個簇GDBSCAN算法通過泛化DBSCA算法中鄰域的概念，以適應(yīng)空間對象的特點DBLASDOPTICSOPTICS算法結(jié)合了聚類的自動性和交互性，先生成聚類的次序，可以對不同的聚類設(shè)置 不同的參數(shù)，來得到用戶滿意的結(jié)果FDCFDC算法通過構(gòu)造k-d tree把整個數(shù)據(jù)空間劃分成若干個矩形空間，當(dāng)空間維數(shù)較少時可 以大大提高DBSCAI的效率基于網(wǎng)格的聚類算法:STING利用網(wǎng)格單兀保存數(shù)據(jù)統(tǒng)計信息，從而實現(xiàn)多分辨率的聚類WaveCluster:

5、在聚類分析中引入了小波變換的原理，主要應(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é)的聚類算法:COBWebCOBWe是一個通用的概念聚類方法，它用分類樹的形式表現(xiàn)層次聚類CLASSITAutoClass :是以概率混合模型

6、為基礎(chǔ)，利用屬性的概率分布來描述聚類，該方法能夠處理混合 型的數(shù)據(jù)，但要求各屬性相互獨立幾種常用的聚類算法從可伸縮性、適合的數(shù)據(jù)類型、高維性（處理高維數(shù)據(jù)的能力）、異常數(shù)據(jù)的抗 干擾度、聚類形狀和算法效率6個方面進行了綜合性能評價，評價結(jié)果如表1所示：算法名稱 1 a f1可伸縮性適合的數(shù)據(jù)類型高維性異常數(shù)據(jù)的抗干擾性聚類形狀算法效率WaveCluster很高:數(shù)值型很高P任意形狀彳艮高ROCK很高混合型彳艮高很高任意形狀一般BIRCH較高數(shù)值型較低較低球形彳艮高F CURE較高數(shù)值型一般彳艮高任意形狀較高K-Prototypes一般：混合型較低較低任意形狀一般DENCLUE較低數(shù)值型較高一般

7、任意形狀較高OptiGrid一般數(shù)值型較高一般任意形狀一般rCLIQUE較高：數(shù)值型較高一較高任意形狀較低DBSCAN一般數(shù)值型較低較高任意形狀一般CLARANS較低數(shù)值型較低較高球形較低目前聚類分析研究的主要內(nèi)容:對聚類進行研究是數(shù)據(jù)挖掘中的一個熱門方向，由于以上所介紹的聚類方法都存在著某些缺點，因此近 些年對于聚類分析的研究很多都專注于改進現(xiàn)有的聚類方法或者是提出一種新的聚類方法。以下將對傳 統(tǒng)聚類方法中存在的問題以及人們在這些問題上所做的努力做一個簡單的總結(jié)：1從以上對傳統(tǒng)的聚類分析方法所做的總結(jié)來看，不管是k-mea ns方法，還是CURST法，在進行聚類之前都需要用戶事先確定要得到的

8、聚類的數(shù)目。然而在現(xiàn)實數(shù)據(jù)中，聚類的 數(shù)目是未知的，通常要經(jīng)過不斷的實驗來獲得合適的聚類數(shù)目，得到較好的聚類結(jié)果。2傳統(tǒng)的聚類方法一般都是適合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類，比如 BIRCH方法對于球狀簇有很好的聚類性能，但是對于不規(guī)則的聚類，則不能很好的工作；K-medoids 方法不太受孤立點的影響，但是 其計算代價又很大。因此如何解決這個問題成為當(dāng)前的一個研究熱點， 有學(xué)者提出將不同的聚類思想進行融合以形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點，在 一次聚類過程中綜合利用多種聚類方法，能夠有效的緩解這個問題。3隨著信息時代的到來，對大量的數(shù)據(jù)進行分析處理是一

9、個很龐大的工作，這就關(guā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ù)集。有文獻提出了一種在高維空間挖掘映射聚類的方法 PCKA(Projected Clusteri ng based on the K-Mea ns Algorithm)，它從多個維度中選