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

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

　常用聚類算法有哪些

?

　　1、劃分法

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

　　（1） 每一個分組至少包含一個數據紀錄；

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

　　對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。

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

　　基于這個基本思想的算法有：

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

　　b.k-modes:K-Means：算法的擴展，采用簡單匹配方法來度量分類型數據的相似度。

　　c.k-prototypes：結合了K-Means和K-Modes兩種算法，能夠處理混合型數據。

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

　　e.CLARA:CLARA算法在PAM的基礎上采用了抽樣技術，能夠處理大規模數據。

　　f.CLARANS:CLARANS算法融合了PAM和CLARA兩者的優點，是第一個用于空間數據庫的聚類算法。

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

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

　　2、層次法

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

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

　　代表算法有：

　　a.CURE：采用抽樣技術先對數據集D隨機抽取樣本，再采用分區技術對樣本進行分區，然后對每個分區局部聚類，最后對局部聚類進行全局聚類。

　　b.ROCK：也采用了隨機抽樣技術，該算法在計算兩個對象的相似度時，同時考慮了周圍對象的影響。

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

　　d.SBAC:SBAC算法則在計算對象間相似度時，考慮了屬性特征對于體現對象本質的重要程度，對于更能體現對象本質的屬性賦予較高的權值。

　　e.BIRCH:BIRCH算法利用樹結構對數據集進行處理，葉結點存儲一個聚類，用中心和半徑表示，順序處理每一個對象，并把它劃分到距離最近的結點，該算法也可以作為其他聚類算法的預處理過程。

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

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

　　3、密度算法

　　基于密度的方法（density-based methods），基于密度的方法與其它方法的一個根本區別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發現“類圓形”的聚類的缺點。

　　這個方法的指導思想就是，只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。

　　代表算法有：

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

　　b.GDBSCAN：算法通過泛化DBSCAN算法中鄰域的概念，以適應空間對象的特點。

　　c.OPTICS:OPTICS算法結合了聚類的自動性和交互性，先生成聚類的次序，可以對不同的聚類設置不同的參數，來得到用戶滿意的結果。

　　d.FDC:FDC算法通過構造k-d tree把整個數據空間劃分成若干個矩形空間，當空間維數較少時可以大大提高DBSCAN的效率。

　　e.DBLASD

　　4、圖論聚類法

　　圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應于被分析數據的最小單元，圖的邊（或?。谧钚√幚韱卧獢祿g的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易于處理。圖論聚類法是以樣本數據的局域連接特征作為聚類的主要信息源，因而其主要優點是易于處理局部數據的特性。

　　5、網格算法

　　基于網格的方法（grid-based methods），這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構，所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標數據庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

　　代表算法有：

　　a.STING：利用網格單元保存數據統計信息，從而實現多分辨率的聚類

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

　　c.CLIQUE：是一種結合了網格和密度的聚類算法。

　　d.OPTIGRID

　　6、模型算法

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

　　通常有兩種嘗試方向：統計的方案和神經網絡的方案。

　　其中基于統計方案的聚類算法又有如下幾種：

　　a.COBWeb:COBWeb是一個通用的概念聚類方法，它用分類樹的形式表現層次聚類。

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

　　c.CLASSIT

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