凝聚式層次聚類演算法的初步理解

05-20

凝聚式層次聚類演算法的初步理解

層次聚類

層次聚類，是一種很直觀的演算法。顧名思義就是要一層一層地進行聚類，可以從下而上地把小的cluster合併聚集，也可以從上而下地將大的cluster進行分割。自下而上地進行聚類稱為凝聚式層次聚類，自上而下地進行聚類稱為分裂式層次聚類。似乎一般用得比較多的是從下而上地聚集。

凝聚式：從點作為個體簇開始，每一步合併兩個最接近的簇。

分裂式：從包含所有點的某個簇開始，每一步分裂一個簇，直到僅剩下單點簇。

基本凝聚層次聚類演算法步驟

1：如果需要，計算鄰近度矩陣

2：repeat

3：合併最接近的兩個簇

4：更新鄰近度矩陣，以反映新的簇與原來的簇之間的鄰近性

5：until 僅剩下一個簇/達到某個終止條件

在這個演算法中，有幾個重要的地方要拎出來點一下。

鄰近度矩陣

鄰近度有許多種定義方式，比如歐氏距離，曼哈頓距離，馬氏距離，餘弦相似度，Jaccard係數，Bregman散度等等。種類豐富，樣品奇多，根據不同的需求來選擇最適合的鄰近度，計算得到相應的鄰近度矩陣。

簇與簇之間鄰近度的定義

每個簇中的點數不一定相等，如何計算兩個不同簇之間的鄰近度呢？

常用的有三種方法：單鏈（MIN準則），全鏈（MAX準則），組平均技術。

單鏈

單鏈（MIN）定義簇的鄰近度為不同簇的兩個最近的點之間的鄰近度。在圖中，即不同結點子集中兩個節點之間的最短邊。下圖中的虛線，就是左右兩個簇的鄰近度。

全鏈

全鏈（MAX）定義簇的鄰近度為不同簇中兩個最遠的點之間的鄰近度作為簇的鄰近度。在圖中，即不同結點子集中兩個結點之間的最長邊。下圖中的虛線，就是左右兩個簇的鄰近度。

組平均

組平均是一種基於圖的方法。它定義簇鄰近度為取自不同簇的所有點對鄰近度的平均值（平均長度）。它的計算公式為 $proximity(C_{i} ,C_{j})=frac{sum_{xepsilon C_{i},yepsilon C_{j}}^{}{proximity(x,y)} }{m_{i}*m_{j}}$ 。

舉個例子

如圖的6個樣本點，它們的坐標按標記依次如下

它們各點到其他點的鄰近度矩陣如下

使用單鏈計算鄰近度如下：

Dist（{3,6}，{2,5}）=min（Dist（3,2），Dist（6,2），Dist（3,5），Dist（6,5））=min（0.1483,0.2540,0.2843,0.3921）=0.1483

使用單鏈的層次聚類如下：

（在代碼中，需要將每次形成的新簇做上新的標記，比如例中6個點，某兩個點合併後就給合併後的簇標記為7，依次為每個合併後的新簇做上標記。標記結果如下，前兩列表示的是合併的簇的標記數，第三列是合併後形成的新簇的標記數。）

於是單鏈的最後結果為

樹狀結構圖顯示為

如上圖，首先是紅色圈圈合併，再是藍色圈圈合併，再是紫色圈圈合併，最後是黑色圈圈合併。

使用全鏈計算鄰近度如下：

Dist（{3,6}，{2,5}）=max（Dist（3,2），Dist（6,2），Dist（3,5），Dist（6,5））=max（0.1513,0.2540,0.2843,0.3921）=0.3921；

Dist（{3,6}，{4}）=max（Dist（3,4），Dist（6,4））=max（0.1513,0.2216）=0.2216；

Dist（{3,6}，{1}）=max（Dist（3,1），Dist（6,1））=max（0.2219,0.2348）=0.2348；

所以簇{3,6}與{4}合併，而不是和單鏈一樣與{2,5}合併。

使用全鏈的層次聚類如下：

形成新簇的標記數如下：

全鏈聚類的順序為：

樹狀結構圖如下：

首先點3和點6合併，其次點5和點2合併，接著{3,6}和點4合併，{{3,6}，4}和點1合併，最後與{2,5}合併為一個大簇。

以上是我寫的代碼的輸出結果，然而書上包括matlab自帶的凝聚式層次聚類的輸出結果是醬嬸兒的：

他的聚類順序是：

目前我還沒有看出是哪裡的問題，我得好好想想，希望我能夠早點想通……不，希望我能先早點複習完概率論……

使用組平均計算鄰近度

這裡偷了個小懶，還沒有寫組平均計算鄰近度的代碼，因為下周二有個概率論的考試，大二這一年過的太混賬，沒好好學，導致要在最後幾天突擊一波，在過的基礎上爭取保80+望90+。到假期我再把組平均的代碼補上吧。（下周日之前一定補上）

Dist（{2,5}，{1}）=（Dist（2,1）+Dist（5,1））/（2*1）=（0.2357+0.3421）/（2*1）=0.2889；

Dist（{3,6,4}，{1}）=（Dist（3,1）+Dist（6,1）+Dist（4,1））/（3*1）=（0.2357+0.3421）/（3*1）=0.2889；

Dist（{3,6,4}，{2,5}）=（Dist（3,2）+Dist（6,2）+Dist（4,2）+Dist（3,5）+Dist（6,5）+Dist（4,5））/（3*2）=（0.1483+0.1100+0.1513+0.2843+0.3921+0.2932）/（3*2）=0.2300；

用了一下matlab自帶的凝聚式層次聚類

y=pdist(x,euclidean);%計算鄰近度矩陣z=linkage(y,average);%選擇組平均技術進行聚類[H,T]=dendrogram(z);%繪製樹狀結構圖set(H,LineWidth,2);%加粗圖中線條

組平均的聚類順序為：

按照這個順序，新簇的標記依次為{3,6}-7；{2,5}-8；{4,7}-9；{8,9}-10；{1,10}-11

組平均聚類的樹狀結構圖為：

定義兩簇之間的鄰近度還有其他方法，比如ward法和質心方法。

ward方法就是把兩個簇的鄰近度定義為兩個簇合併時導致的平方誤差的增量。該方法使用的目標函數與K均值相同，且當兩點之間的鄰近度取它們之間距離的平方時，Ward方法與組平均非常相似。

而質心方法，是通過計算簇質心之間的距離來計算兩個簇之間的鄰近度。看上去與K均值也類似。而且質心方法有可能導致倒置的可能，也就是合併的兩個簇可能比前一步合併的簇對更加相似。

Lance-Williams公式

上面提到的五種定義簇與簇之間鄰近度的方式其實可以規整到一個公式里來，然後通過不同的係數來體現他們的不同，這個公式就是Lance-Williams公式。

$p(R,Q)=alpha _{A} p(A,Q)+alpha _{B} p(B,Q)+eta p(A,B)+gamma |p(A,Q)-P(B,Q)|$

式中，p(·,·)表示為鄰近度函數，簇R是通過合併簇A和B形成的，Q是A、B以外的原簇， $m_{A},m_{B},m_{Q}$ 分別是原簇A、B和Q的大小（點數）。

我們可以看到，合併簇A和B形成新簇R之後，新簇R與原簇Q的鄰近度是Q與原來的簇A和B的鄰近度的線性函數。

凝聚式層次聚類的主要問題

1、缺乏全局目標函數

凝聚層次聚類不能視為全局優化目標函數，因為在每一步合併時僅僅局部地確定哪些簇應當合併（或分裂，對於分裂式）。但是避開了解決困難的組合優化問題，並且這樣的方法沒有局部極小問題或難選擇初始點的問題。

2、處理不同大小簇的能力

關於如何處理待合併的簇對的相對大小這個問題，解決的方法有兩種：一是加權，就是不同簇中的點具有不同的權值；二是非加權，需要考慮每個簇的點數。

比如組平均技術，上面說的組平均實際上是組平均技術的非加權版，全稱為「使用算術平均的非加權的對組方法」（UPGMA），Lance-Williams公式的係數也涉及每個被合併簇的大小。而對於加權版本（WPGMA），它的係數是常數： $alpha _{A}$ =1/2， $alpha _{B}$ =1/2，β=0，γ=0。通常非加權方法更可取，除非出於某種原因個體點具有不同的權值，如對象類非均勻的抽樣。

3、合併決策是最終的

對於合併兩個簇，凝聚層次聚類可以使用所有點的逐對相似度信息趨向於作出好的局部決策。然而，一旦做出合併兩個簇的決策，以後就不能撤銷，這阻礙了局部最優標準變成全局最優標準。

一些方法試圖克服「合併是最終的」這一限制，如移動樹的分支以改善全局目標；使用劃分聚類方法（K均值）來創建許多小簇，然後從這些小簇出發進行層次聚類。

優點與缺點

層次聚類能產生較高質量的聚類；有些使用這種演算法是因為基本應用需要層次結構。但就計算量和存儲需求而言，凝聚式層次聚類演算法是昂貴的。

基本凝聚式層次聚類演算法使用鄰近度矩陣，這需要存儲 $frac{m^{2} }{2}$ 個鄰近度（假定鄰近度矩陣式對稱的），其中m是數據點的個數。記錄簇所需要的空間正比於簇的個數為m-1，不包括單點簇。因此總的空間複雜度為 $O(m^{2})$ 。層次聚類所需要的總時間為 $O(m_{2}log m)$ 。

以上的知識點大部分來自於《數據挖掘導論》的學習，還包括網上查閱的一些博客，初步總結一些東西。

代碼都是自己琢磨敲出來的，因為找代碼的能力實在是有限，我想關鍵還是英語水平不高，高中把老本吃完了= =，英語還是很重要的能力啊。不過我的代碼比較粗糙，我覺得假期需要嘗試著優化它，讓它的可讀性變高一些，等成熟了我再發到知乎上來，希望路過的大牛不要噴的太狠……

大致的基本凝聚式層次聚類演算法的初步介紹就到這裡結束。我就靜靜地等待概率論考完，容納後開始新一輪的學習了！不要浪費自己的時間啊！想想人工智慧的衝擊就後怕，我不想成為被淘汰掉的那一個。