很難對聚類方法提出一個簡潔的分類,因為這些類別可能重疊,從而使得一種方法具有幾類的特征,盡管如此,對于各種不同的聚類方法提供一個相對有組織的描述依然是有用的,為聚類分析計算方法主要有如下幾種:劃分法、層次法、密度算法、圖論聚類法、網(wǎng)格算法和模型算法。
以下對劃分法和層次法等六種聚類算法種類做了詳細的介紹。
常用聚類算法有哪些
?
1、劃分法
劃分法(partitioning methods),給定一個有N個元組或者紀錄的數(shù)據(jù)集,分裂法將構(gòu)造K個分組,每一個分組就代表一個聚類,K《N。而且這K個分組滿足下列條件:
?。?) 每一個分組至少包含一個數(shù)據(jù)紀錄;
?。?)每一個數(shù)據(jù)紀錄屬于且僅屬于一個分組(注意:這個要求在某些模糊聚類算法中可以放寬);
對于給定的K,算法首先給出一個初始的分組方法,以后通過反復迭代的方法改變分組,使得每一次改進之后的分組方案都較前一次好,而所謂好的標準就是:同一分組中的記錄越近越好,而不同分組中的紀錄越遠越好。
大部分劃分方法是基于距離的。給定要構(gòu)建的分區(qū)數(shù)k,劃分方法首先創(chuàng)建一個初始化劃分。然后,它采用一種迭代的重定位技術(shù),通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般準備是:同一個簇中的對象盡可能相互接近或相關(guān),而不同的簇中的對象盡可能遠離或不同。還有許多評判劃分質(zhì)量的其他準則。傳統(tǒng)的劃分方法可以擴展到子空間聚類,而不是搜索整個數(shù)據(jù)空間。當存在很多屬性并且數(shù)據(jù)稀疏時,這是有用的。為了達到全局最優(yōu),基于劃分的聚類可能需要窮舉所有可能的劃分,計算量極大。實際上,大多數(shù)應(yīng)用都采用了流行的啟發(fā)式方法,如k-均值和k-中心算法,漸近的提高聚類質(zhì)量,逼近局部最優(yōu)解。這些啟發(fā)式聚類方法很適合發(fā)現(xiàn)中小規(guī)模的數(shù)據(jù)庫中小規(guī)模的數(shù)據(jù)庫中的球狀簇。為了發(fā)現(xiàn)具有復雜形狀的簇和對超大型數(shù)據(jù)集進行聚類,需要進一步擴展基于劃分的方法。
基于這個基本思想的算法有:
a.k-means:是一種典型的劃分聚類算法,它用一個聚類的中心來代表一個簇,即在迭代過程中選擇的聚點不一定是聚類中的一個點,該算法只能處理數(shù)值型數(shù)據(jù)。
b.k-modes:K-Means:算法的擴展,采用簡單匹配方法來度量分類型數(shù)據(jù)的相似度。
c.k-prototypes:結(jié)合了K-Means和K-Modes兩種算法,能夠處理混合型數(shù)據(jù)。
d.k-medoids:在迭代過程中選擇簇中的某點作為聚點,PAM是典型的k-medoids算法。
e.CLARA:CLARA算法在PAM的基礎(chǔ)上采用了抽樣技術(shù),能夠處理大規(guī)模數(shù)據(jù)。
f.CLARANS:CLARANS算法融合了PAM和CLARA兩者的優(yōu)點,是第一個用于空間數(shù)據(jù)庫的聚類算法。
g.Focused CLARAN:采用了空間索引技術(shù)提高了CLARANS算法的效率。
h.PCM:模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法。
2、層次法
層次法(hierarchical methods),這種方法對給定的數(shù)據(jù)集進行層次似的分解,直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。
例如,在“自底向上”方案中,初始時每一個數(shù)據(jù)紀錄都組成一個單獨的組,在接下來的迭代中,它把那些相互鄰近的組合并成一個組,直到所有的記錄組成一個分組或者某個條件滿足為止。
代表算法有:
a.CURE:采用抽樣技術(shù)先對數(shù)據(jù)集D隨機抽取樣本,再采用分區(qū)技術(shù)對樣本進行分區(qū),然后對每個分區(qū)局部聚類,最后對局部聚類進行全局聚類。
b.ROCK:也采用了隨機抽樣技術(shù),該算法在計算兩個對象的相似度時,同時考慮了周圍對象的影響。
c.CHEMALOEN:首先由數(shù)據(jù)集構(gòu)造成一個K-最近鄰圖Gk ,再通過一個圖的劃分算法將圖Gk 劃分成大量的子圖,每個子圖代表一個初始子簇,最后用一個凝聚的層次聚類算法反復合并子簇,找到真正的結(jié)果簇。
d.SBAC:SBAC算法則在計算對象間相似度時,考慮了屬性特征對于體現(xiàn)對象本質(zhì)的重要程度,對于更能體現(xiàn)對象本質(zhì)的屬性賦予較高的權(quán)值。
e.BIRCH:BIRCH算法利用樹結(jié)構(gòu)對數(shù)據(jù)集進行處理,葉結(jié)點存儲一個聚類,用中心和半徑表示,順序處理每一個對象,并把它劃分到距離最近的結(jié)點,該算法也可以作為其他聚類算法的預處理過程。
f.BUBBLE:BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間。
g.BUBBLE-FM:BUBBLE-FM算法通過減少距離的計算次數(shù),提高了BUBBLE算法的效率。
3、密度算法
基于密度的方法(density-based methods),基于密度的方法與其它方法的一個根本區(qū)別是:它不是基于各種各樣的距離的,而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。
這個方法的指導思想就是,只要一個區(qū)域中的點的密度大過某個閾值,就把它加到與之相近的聚類中去。
代表算法有:
a.DBSCAN:DBSCAN算法是一種典型的基于密度的聚類算法,該算法采用空間索引技術(shù)來搜索對象的鄰域,引入了“核心對象”和“密度可達”等概念,從核心對象出發(fā),把所有密度可達的對象組成一個簇。
b.GDBSCAN:算法通過泛化DBSCAN算法中鄰域的概念,以適應(yīng)空間對象的特點。
c.OPTICS:OPTICS算法結(jié)合了聚類的自動性和交互性,先生成聚類的次序,可以對不同的聚類設(shè)置不同的參數(shù),來得到用戶滿意的結(jié)果。
d.FDC:FDC算法通過構(gòu)造k-d tree把整個數(shù)據(jù)空間劃分成若干個矩形空間,當空間維數(shù)較少時可以大大提高DBSCAN的效率。
e.DBLASD
4、圖論聚類法
圖論聚類方法解決的第一步是建立與問題相適應(yīng)的圖,圖的節(jié)點對應(yīng)于被分析數(shù)據(jù)的最小單元,圖的邊(或?。?yīng)于最小處理單元數(shù)據(jù)之間的相似性度量。因此,每一個最小處理單元數(shù)據(jù)之間都會有一個度量表達,這就確保了數(shù)據(jù)的局部特性比較易于處理。圖論聚類法是以樣本數(shù)據(jù)的局域連接特征作為聚類的主要信息源,因而其主要優(yōu)點是易于處理局部數(shù)據(jù)的特性。
5、網(wǎng)格算法
基于網(wǎng)格的方法(grid-based methods),這種方法首先將數(shù)據(jù)空間劃分成為有限個單元(cell)的網(wǎng)格結(jié)構(gòu),所有的處理都是以單個的單元為對象的。這么處理的一個突出的優(yōu)點就是處理速度很快,通常這是與目標數(shù)據(jù)庫中記錄的個數(shù)無關(guān)的,它只與把數(shù)據(jù)空間分為多少個單元有關(guān)。
代表算法有:
a.STING:利用網(wǎng)格單元保存數(shù)據(jù)統(tǒng)計信息,從而實現(xiàn)多分辨率的聚類
b.WaveCluster:在聚類分析中引入了小波變換的原理,主要應(yīng)用于信號處理領(lǐng)域。(備注:小波算法在信號處理,圖形圖像,加密解密等領(lǐng)域有重要應(yīng)用。)
c.CLIQUE:是一種結(jié)合了網(wǎng)格和密度的聚類算法。
d.OPTIGRID
6、模型算法
基于模型的方法(model-based methods),基于模型的方法給每一個聚類假定一個模型,然后去尋找能夠很好的滿足這個模型的數(shù)據(jù)集。這樣一個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。它的一個潛在的假定就是:目標數(shù)據(jù)集是由一系列的概率分布所決定的。
通常有兩種嘗試方向:統(tǒng)計的方案和神經(jīng)網(wǎng)絡(luò)的方案。
其中基于統(tǒng)計方案的聚類算法又有如下幾種:
a.COBWeb:COBWeb是一個通用的概念聚類方法,它用分類樹的形式表現(xiàn)層次聚類。
b.AutoClass:是以概率混合模型為基礎(chǔ),利用屬性的概率分布來描述聚類,該方法能夠處理混合型的數(shù)據(jù),但要求各屬性相互獨立。
c.CLASSIT
而基于神經(jīng)網(wǎng)絡(luò)方案的聚類算法又有:自組織神經(jīng)網(wǎng)絡(luò)SOM(該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網(wǎng)絡(luò)中,一開始時,輸入樣本引起輸出興奮細胞的位置各不相同,但自組織后會形成一些細胞群,它們分別代表了輸入樣本,反映了輸入樣本的特征)。
評論
查看更多