常用聚類算法有哪些？六大類聚類算法詳細(xì)介紹

　　很難對(duì)聚類方法提出一個(gè)簡(jiǎn)潔的分類，因?yàn)檫@些類別可能重疊，從而使得一種方法具有幾類的特征，盡管如此，對(duì)于各種不同的聚類方法提供一個(gè)相對(duì)有組織的描述依然是有用的，為聚類分析計(jì)算方法主要有如下幾種：劃分法、層次法、密度算法、圖論聚類法、網(wǎng)格算法和模型算法。

　　以下對(duì)劃分法和層次法等六種聚類算法種類做了詳細(xì)的介紹。

　常用聚類算法有哪些

?

　　1、劃分法

　　劃分法（partitioning methods），給定一個(gè)有N個(gè)元組或者紀(jì)錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類，K《N。而且這K個(gè)分組滿足下列條件：

　?。?） 每一個(gè)分組至少包含一個(gè)數(shù)據(jù)紀(jì)錄；

　?。?）每一個(gè)數(shù)據(jù)紀(jì)錄屬于且僅屬于一個(gè)分組（注意：這個(gè)要求在某些模糊聚類算法中可以放寬）；

　　對(duì)于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好。

　　大部分劃分方法是基于距離的。給定要構(gòu)建的分區(qū)數(shù)k，劃分方法首先創(chuàng)建一個(gè)初始化劃分。然后，它采用一種迭代的重定位技術(shù)，通過把對(duì)象從一個(gè)組移動(dòng)到另一個(gè)組來進(jìn)行劃分。一個(gè)好的劃分的一般準(zhǔn)備是：同一個(gè)簇中的對(duì)象盡可能相互接近或相關(guān)，而不同的簇中的對(duì)象盡可能遠(yuǎn)離或不同。還有許多評(píng)判劃分質(zhì)量的其他準(zhǔn)則。傳統(tǒng)的劃分方法可以擴(kuò)展到子空間聚類，而不是搜索整個(gè)數(shù)據(jù)空間。當(dāng)存在很多屬性并且數(shù)據(jù)稀疏時(shí)，這是有用的。為了達(dá)到全局最優(yōu)，基于劃分的聚類可能需要窮舉所有可能的劃分，計(jì)算量極大。實(shí)際上，大多數(shù)應(yīng)用都采用了流行的啟發(fā)式方法，如k-均值和k-中心算法，漸近的提高聚類質(zhì)量，逼近局部最優(yōu)解。這些啟發(fā)式聚類方法很適合發(fā)現(xiàn)中小規(guī)模的數(shù)據(jù)庫中小規(guī)模的數(shù)據(jù)庫中的球狀簇。為了發(fā)現(xiàn)具有復(fù)雜形狀的簇和對(duì)超大型數(shù)據(jù)集進(jìn)行聚類，需要進(jìn)一步擴(kuò)展基于劃分的方法。

　　基于這個(gè)基本思想的算法有：

　　a.k-means：是一種典型的劃分聚類算法，它用一個(gè)聚類的中心來代表一個(gè)簇，即在迭代過程中選擇的聚點(diǎn)不一定是聚類中的一個(gè)點(diǎn)，該算法只能處理數(shù)值型數(shù)據(jù)。

　　b.k-modes:K-Means：算法的擴(kuò)展，采用簡(jiǎn)單匹配方法來度量分類型數(shù)據(jù)的相似度。

　　c.k-prototypes：結(jié)合了K-Means和K-Modes兩種算法，能夠處理混合型數(shù)據(jù)。

　　d.k-medoids：在迭代過程中選擇簇中的某點(diǎn)作為聚點(diǎn)，PAM是典型的k-medoids算法。

　　e.CLARA:CLARA算法在PAM的基礎(chǔ)上采用了抽樣技術(shù)，能夠處理大規(guī)模數(shù)據(jù)。

　　f.CLARANS:CLARANS算法融合了PAM和CLARA兩者的優(yōu)點(diǎn)，是第一個(gè)用于空間數(shù)據(jù)庫的聚類算法。

　　g.Focused CLARAN：采用了空間索引技術(shù)提高了CLARANS算法的效率。

　　h.PCM：模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法。

　　2、層次法

　　層次法（hierarchical methods），這種方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

　　例如，在“自底向上”方案中，初始時(shí)每一個(gè)數(shù)據(jù)紀(jì)錄都組成一個(gè)單獨(dú)的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個(gè)組，直到所有的記錄組成一個(gè)分組或者某個(gè)條件滿足為止。

　　代表算法有：

　　a.CURE：采用抽樣技術(shù)先對(duì)數(shù)據(jù)集D隨機(jī)抽取樣本，再采用分區(qū)技術(shù)對(duì)樣本進(jìn)行分區(qū)，然后對(duì)每個(gè)分區(qū)局部聚類，最后對(duì)局部聚類進(jìn)行全局聚類。

　　b.ROCK：也采用了隨機(jī)抽樣技術(shù)，該算法在計(jì)算兩個(gè)對(duì)象的相似度時(shí)，同時(shí)考慮了周圍對(duì)象的影響。

　　c.CHEMALOEN：首先由數(shù)據(jù)集構(gòu)造成一個(gè)K-最近鄰圖Gk ，再通過一個(gè)圖的劃分算法將圖Gk 劃分成大量的子圖，每個(gè)子圖代表一個(gè)初始子簇，最后用一個(gè)凝聚的層次聚類算法反復(fù)合并子簇，找到真正的結(jié)果簇。

　　d.SBAC:SBAC算法則在計(jì)算對(duì)象間相似度時(shí)，考慮了屬性特征對(duì)于體現(xiàn)對(duì)象本質(zhì)的重要程度，對(duì)于更能體現(xiàn)對(duì)象本質(zhì)的屬性賦予較高的權(quán)值。

　　e.BIRCH:BIRCH算法利用樹結(jié)構(gòu)對(duì)數(shù)據(jù)集進(jìn)行處理，葉結(jié)點(diǎn)存儲(chǔ)一個(gè)聚類，用中心和半徑表示，順序處理每一個(gè)對(duì)象，并把它劃分到距離最近的結(jié)點(diǎn)，該算法也可以作為其他聚類算法的預(yù)處理過程。

　　f.BUBBLE:BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間。

　　g.BUBBLE-FM:BUBBLE-FM算法通過減少距離的計(jì)算次數(shù)，提高了BUBBLE算法的效率。

　　3、密度算法

　　基于密度的方法（density-based methods），基于密度的方法與其它方法的一個(gè)根本區(qū)別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)。

　　這個(gè)方法的指導(dǎo)思想就是，只要一個(gè)區(qū)域中的點(diǎn)的密度大過某個(gè)閾值，就把它加到與之相近的聚類中去。

　　代表算法有：

　　a.DBSCAN:DBSCAN算法是一種典型的基于密度的聚類算法，該算法采用空間索引技術(shù)來搜索對(duì)象的鄰域，引入了“核心對(duì)象”和“密度可達(dá)”等概念，從核心對(duì)象出發(fā)，把所有密度可達(dá)的對(duì)象組成一個(gè)簇。

　　b.GDBSCAN：算法通過泛化DBSCAN算法中鄰域的概念，以適應(yīng)空間對(duì)象的特點(diǎn)。

　　c.OPTICS:OPTICS算法結(jié)合了聚類的自動(dòng)性和交互性，先生成聚類的次序，可以對(duì)不同的聚類設(shè)置不同的參數(shù)，來得到用戶滿意的結(jié)果。

　　d.FDC:FDC算法通過構(gòu)造k-d tree把整個(gè)數(shù)據(jù)空間劃分成若干個(gè)矩形空間，當(dāng)空間維數(shù)較少時(shí)可以大大提高DBSCAN的效率。

　　e.DBLASD

　　4、圖論聚類法

　　圖論聚類方法解決的第一步是建立與問題相適應(yīng)的圖，圖的節(jié)點(diǎn)對(duì)應(yīng)于被分析數(shù)據(jù)的最小單元，圖的邊（或?。?duì)應(yīng)于最小處理單元數(shù)據(jù)之間的相似性度量。因此，每一個(gè)最小處理單元數(shù)據(jù)之間都會(huì)有一個(gè)度量表達(dá)，這就確保了數(shù)據(jù)的局部特性比較易于處理。圖論聚類法是以樣本數(shù)據(jù)的局域連接特征作為聚類的主要信息源，因而其主要優(yōu)點(diǎn)是易于處理局部數(shù)據(jù)的特性。

　　5、網(wǎng)格算法

　　基于網(wǎng)格的方法（grid-based methods），這種方法首先將數(shù)據(jù)空間劃分成為有限個(gè)單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個(gè)的單元為對(duì)象的。這么處理的一個(gè)突出的優(yōu)點(diǎn)就是處理速度很快，通常這是與目標(biāo)數(shù)據(jù)庫中記錄的個(gè)數(shù)無關(guān)的，它只與把數(shù)據(jù)空間分為多少個(gè)單元有關(guān)。

　　代表算法有：

　　a.STING：利用網(wǎng)格單元保存數(shù)據(jù)統(tǒng)計(jì)信息，從而實(shí)現(xiàn)多分辨率的聚類

　　b.WaveCluster：在聚類分析中引入了小波變換的原理，主要應(yīng)用于信號(hào)處理領(lǐng)域。（備注：小波算法在信號(hào)處理，圖形圖像，加密解密等領(lǐng)域有重要應(yīng)用。）

　　c.CLIQUE：是一種結(jié)合了網(wǎng)格和密度的聚類算法。

　　d.OPTIGRID

　　6、模型算法

　　基于模型的方法（model-based methods），基于模型的方法給每一個(gè)聚類假定一個(gè)模型，然后去尋找能夠很好的滿足這個(gè)模型的數(shù)據(jù)集。這樣一個(gè)模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。它的一個(gè)潛在的假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。

　　通常有兩種嘗試方向：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案。

　　其中基于統(tǒng)計(jì)方案的聚類算法又有如下幾種：

　　a.COBWeb:COBWeb是一個(gè)通用的概念聚類方法，它用分類樹的形式表現(xiàn)層次聚類。

　　b.AutoClass：是以概率混合模型為基礎(chǔ)，利用屬性的概率分布來描述聚類，該方法能夠處理混合型的數(shù)據(jù)，但要求各屬性相互獨(dú)立。

　　c.CLASSIT

　　而基于神經(jīng)網(wǎng)絡(luò)方案的聚類算法又有：自組織神經(jīng)網(wǎng)絡(luò)SOM（該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網(wǎng)絡(luò)中，一開始時(shí)，輸入樣本引起輸出興奮細(xì)胞的位置各不相同，但自組織后會(huì)形成一些細(xì)胞群，它們分別代表了輸入樣本，反映了輸入樣本的特征）。