聚類算法整理

文章目錄

• 有效性名額
• 原型聚類
• • k-means 算法
  • • k值的選擇
    • k-means的變種
  • 學習向量量化
  • 高斯混合聚類
• 密度聚類
• • DBSCAN算法
  • Mean-Shift 算法
• 層次聚類
• • AGNES 算法
  • DIANA 算法
  • BIRCH 算法
• 譜聚類

無監督學習希望通過對無标記訓練樣本的學習來揭露資料的内在性質以及規律，而其中應用最廣泛的就是聚類算法（clustering）：給定資料集，聚類試圖将資料集中的樣本劃分為 K 個不相交的子集，每個子集稱為一個簇（cluster），每個簇可能對應于一個潛在的概念，這些概念對于聚類算法而言，事先可能是未知的。

聚類可以作為一個單獨的過程，用于尋找資料内在的分布結構，也可以作為其他學習任務的前驅過程。需要注意的是，聚類并沒有唯一的評價标準，可能很多不同的聚類都很好地對應了現實世界的某些屬性，它們都是合理的。如：在圖檔識别中包含的圖檔有：紅色卡車、紅色汽車、灰色卡車、灰色汽車。可以聚類成：紅色一類、灰色一類；也可以聚類成：卡車一類、汽車一類。

有效性名額

對于聚類任務，希望同一簇的樣本盡可能彼此相似，不同簇的樣本之間盡可能不同，即簇内相似度高，簇間相似度低。聚類的有效性名額分為兩類：聚類結果與某個參考模型(reference model)進行比較，稱作外部名額(external index)；直接考察聚類結果而不利用任何參考模型，稱作内部名額(internal index)。

常用的外部名額有：Jaccard系數、FM指數、Rand指數、ARI指數；

常用的内部名額有：DB指數、Dunn指數；

原型聚類

原型聚類算法假設聚類結構可以通過一組原型刻畫，通常算法選會對原型進行初始化，然後對原型進行疊代更新求解，不同的原型表示和不同的求解方式會産生不同的算法。

k-means 算法

k-means算法的目标是通過設立 k 個原型，将訓練集劃分成 k 簇，然後最小化簇中執行個體和對應原型的歐氏距離，即：

上式是一個 NP-hard 問題，是以 k-means 算法采用了一種“貪心”政策，通過疊代優化來求近似解(EM算法)。

算法步驟

輸入： 訓練集 D，聚類簇數量 k

輸出： k 個均值向量

(1) 初始化均值向量：從訓練集 D 中随機抽取 k 個樣本作為初始化均值向量；

(2) 聚類劃分：對訓練集 D 中每個樣本分别計算其離各個均值向量的歐氏距離，将樣本劃分到距離最小的那一簇；

(3) 重置均值向量：對每個簇，按照極大似然估計的思想，計算其均值向量，作為該簇的新的均值向量；

(4) 疊代求解：疊代 (2)、(3) 直至均值向量未發生變化或者疊代次數到達上限為止，傳回均值向量。

k-means的優點： 計算複雜度低，為 O(N x K x q) ，其中 N 為樣本數量，q 為疊代次數，通常 K 和 q 要遠遠小于 N，此時複雜度相當于 O(N)；當資料集是密集的、球狀或團狀的簇群，且簇與簇之間差別明顯時，聚類效果很好。

k-means的缺點： 需要首先确定聚類的數量K；分類結果嚴重依賴于分類中心的初始化；對噪聲敏感。因為簇的中心是取平均，是以聚類簇很遠地方的噪音會導緻簇的中心點偏移；無法解決不規則形狀的聚類；

k值的選擇

手肘法： 核心名額是SSE(sum of the squared errors，誤差平方和)，

其中Ci是第i個簇，p是Ci中的樣本點，mi是Ci的質心，SSE是所有樣本的聚類誤差，代表了聚類效果的好壞。

手肘法的核心思想是：随着聚類數k的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那麼誤差平方和SSE自然會逐漸變小。并且，當k小于真實聚類數時，由于k的增大會大幅增加每個簇的聚合程度，故SSE的下降幅度會很大，而當k到達真實聚類數時，再增加k所得到的聚合程度回報會迅速變小，是以SSE的下降幅度會驟減，然後随着k值的繼續增大而趨于平緩，也就是說SSE和k的關系圖是一個手肘的形狀，而這個肘部對應的k值就是資料的真實聚類數，如下圖所示：

輪廓系數法： 某個樣本點Xi的輪廓系數定義如下，

其中，a是Xi與同簇的其他樣本的平均距離，稱為凝聚度，b是Xi與最近簇中所有樣本的平均距離，稱為分離度。而最近簇的定義是：

其中p是某個簇Ck中的樣本。事實上，簡單點講，就是用Xi到某個簇所有樣本平均距離作為衡量該點到該簇的距離後，選擇離Xi最近的一個簇作為最近簇。

求出所有樣本的輪廓系數後再求平均值就得到了平均輪廓系數。平均輪廓系數的取值範圍為[-1,1]，且簇内樣本的距離越近，簇間樣本距離越遠，平均輪廓系數越大，聚類效果越好。那麼，很自然地，平均輪廓系數最大的k便是最佳聚類數。

k-means的變種

1、k-means++ 屬于 k-means 的變種，它主要解決 k-means 嚴重依賴于分類中心初始化的問題。在選擇初始均值向量時，盡量安排這些初始均值向量之間的距離盡可能的遠。

2、k-modes 屬于 k-means 的變種，它主要解決 k-means 無法處理離散特征的問題。主要差別在于重新定義了距離函數以及簇中心的更新規則。

3、k-medoids 屬于 k-means 的變種，它主要解決 k-means 對噪聲敏感的問題。在計算新的簇心時，不再通過簇内樣本的均值來實作，而是挑選簇内距離其它所有點都最近的樣本來實作，這就減少了孤立噪聲帶來的影響，但也增加了算法的複雜度。

學習向量量化

與 k 均值算法不同，學習向量量化（LVQ）的學習過程中會利用樣本的類别資訊，是以 LVQ 是一種監督式的聚類算法。其目标是學得一組原型向量，每一個原型向量代表一個聚類簇标記。

算法步驟

輸入： 訓練集 D，聚類簇數量 p

輸出： p 個原型向量

(1) 初始化原型向量；

(2) 計算距離：在訓練集 D 中随機抽取一個樣本 xj，分别計算該樣本與各個原型向量間的距離，然後找出最近的原型向量 pi；

(3) 重置均值向量：如果樣本 xj 與原型向量 pi 的類别相同，則讓原型向量靠近樣本xj ，否則遠離，更新規則如下圖：

(4) 疊代求解：疊代 (2)、(3) 直至原型向量更新很小或者疊代次數到達上限為止，傳回原型向量。

高斯混合聚類

高斯混合聚類的步驟：首先假設樣本集具有一些規律，包括可以以 α α α 參數作為比例分為 k 類且每類内符合高斯分布。然後根據貝葉斯原理利用極大似然法同時求出決定分類比例的 α α α 和決定類内高斯分布的 μ μ μ、 Σ Σ Σ。最後将樣本根據 α α α、 μ μ μ、 Σ Σ Σ 再次通過貝葉斯原理求出樣本該分在哪個簇。

整個步驟下來，這種做法其實就是一種原型聚類：通過找到可以刻畫樣本的原型（ α α α、 μ μ μ、 Σ Σ Σ參數），疊代得到 α α α、 μ μ μ、 Σ Σ Σ參數的最優解。

密度聚類

基于密度的聚類算法假設聚類結構能夠通過樣本分布的緊密程度确定，以資料集在空間分布上的稠密程度為依據進行聚類，即隻要一個區域中的樣本密度大于某個門檻值，就把它劃入與之相近的簇中。

密度聚類從樣本密度的角度進行考察樣本之間的可連接配接性，并由可連接配接樣本不斷擴充直到獲得最終的聚類結果。這類算法可以克服K-means、BIRCH等隻适用于凸樣本集的情況。

DBSCAN算法

DBSCAN算法的優點： 不需要事先給定簇的數目k；适于稠密的非凸資料集，可以發現任意形狀的簇；可以在聚類時發現噪音點、對資料集中的異常點不敏感。

DBSCAN算法的缺點： 對于高維資料效果不好；不适于資料集中樣本密度差異很小的情況；資料量很大時算法收斂的時間較長；不易調參。

Mean-Shift 算法

Mean-Shift 是基于核密度估計的爬山算法，可以用于聚類、圖像分割、跟蹤等領域。Mean Shift 算法的關鍵操作是通過感興趣區域内的資料密度變化計算中心點的漂移向量，進而移動中心點進行下一次疊代，直到到達密度最大處（中心點不變）。從每個資料點出發都可以進行該操作，在這個過程，統計出現在感興趣區域内的資料的次數，該參數将在最後作為分類的依據。

算法步驟

1、在未被标記的資料點中随機選擇一個點作為起始中心點center；

2、找出以center為中心半徑為radius的區域中出現的所有資料點，認為這些點同屬于一個聚類C。同時在該聚類中記錄資料點出現的次數加1。

3、以center為中心點，計算從center開始到集合M中每個元素的向量，将這些向量相加，得到向量shift。

4、center = center + shift。即center沿着shift的方向移動，移動距離是||shift||。

5、重複步驟2、3、4，直到shift的很小（就是疊代到收斂），記住此時的center。注意，這個疊代過程中遇到的點都應該歸類到簇C。

6、如果收斂時目前簇C的center與其它已經存在的簇C2中心的距離小于門檻值，那麼把C2和C合并，資料點出現次數也對應合并。否則，把C作為新的聚類。

7、重複1、2、3、4、5直到所有的點都被标記為已通路。

8、分類：根據每個類，對每個點的通路頻率，取通路頻率最大的那個類，作為目前點集的所屬類。

Mean-Shift算法的優點： 簇的數量由算法自動确定，無需人工指定；基于密度定義，能夠對抗噪音；可以處理任意形狀和大小的簇。

Mean-Shift算法的缺點： 無法控制簇的數量；無法區分有意義的簇和無意義的簇，即異常點也會形成它們自己的簇。

層次聚類

層次聚類(Hierarchical Clustering)是聚類算法的一種，通過計算不同類别資料點間的相似度來建立一棵有層次的嵌套聚類樹。在聚類樹中，不同類别的原始資料點是樹的最低層，樹的頂層是一個聚類的根節點。建立聚類樹有自下而上合并和自上而下分裂兩種方法。

AGNES 算法

AGNES 算法是一種常用的采用自底向上聚合政策的層次聚類算法。

AGNES首先将資料集中的每個樣本看作一個初始的聚類簇，然後在算法運作的每一步中，找出距離最近的兩個聚類簇進行合并，合并過程不斷重複，直到達到預設的聚類簇的個數。

聚類簇之間的距離有三種計算方法： 最小距離由兩個簇的最近樣本決定；最大距離由兩個簇的最遠樣本決定；平均距離由兩個簇的所有樣本決定。

AGNES 算法的優點： 距離容易定義，使用限制較少；可以發現聚類的層次關系。

AGNES 算法的缺點： 計算複雜度較高；算法容易聚成鍊狀；不适合大資料集。

DIANA 算法

DIANA 算法是一種常用的采用自頂向下政策的層次聚類算法。

DIANA首先将所有對象置于一個簇中，然後按照某種既定的規則逐漸細分為越來越小的簇(比如最大的歐式距離)，直到達到某個終結條件(簇數目或者簇距離達到門檻值)。

優缺點與AGNES類似。

BIRCH 算法

BIRCH算法(平衡疊代削減聚類法)：聚類特征使用3元組進行一個簇的相關資訊，通過建構滿足分枝因子和簇直徑限制的聚類特征樹(CF-Tree)來求聚類，聚類特征樹其實是一個具有兩個參數分枝因子(B、L)和類直徑(T)的高度平衡樹；分枝因子規定了樹的每個節點的子女的最多個數，而類直徑展現了對這一類點的距離範圍；非葉子節點為它子女的最大特征值；聚類特征樹的建構可以是動态過程的，可以随時根據資料對模型進行更新操作。對應生成的結果就是一個簇(聚類特征 - CF)；BIRCH算法的過程就是建立CF-Tree的過程。

BIRCH 算法的優點： 節省記憶體，所有樣本都存放在磁盤上，記憶體中僅僅存放CF結構，适合大資料集；計算速度快，隻需要掃描一遍就可以建立CF樹；可以識别噪聲點。

BIRCH 算法的缺點： 結果依賴于資料點的插入順序；對非球狀的簇聚類效果不好；每個結點隻能包含規定數目的子結點，最後聚類的簇可能和真實的簇差距很大。

譜聚類

譜聚類(spectral clustering) 是一種基于圖論的聚類方法。

主要思想：基于資料集 D 來建構圖 G = ( V,E )，頂點V由資料集中的資料點組成；任意一對頂點V之間存在邊E，距離越近的一對頂點，邊的權重越高，距離越遠的一對頂點，邊的權重越低；通過對圖 G 進行切割，使得切割之後：不同子圖之間的邊的權重盡可能的低、各子圖内的邊的權重盡可能的高，這樣就完成了聚類。

常用的譜聚類算法有：最小切圖、RatioCut 算法、Ncut 算法。

譜聚類算法的優點： 隻需要資料之間的相似度矩陣，是以處理稀疏資料時很有效；由于使用了降維，是以在處理高維資料聚類時效果較好。

譜聚類算法的缺點： 如果最終聚類的次元非常高，則由于降維的幅度不夠，則譜聚類的運作速度和最後聚類的效果均不好；聚類效果依賴于相似度矩陣，不同相似度矩陣得到的最終聚類效果可能不同。

參考部落格：https://blog.csdn.net/qq_15738501/article/details/79036255