層次聚類算法的原理及實現Hierarchical Clustering

層次聚類(Hierarchical Clustering)是聚類算法的一種，通過計算不同類別數據點間的相似度來創建一棵有層次的嵌套聚類樹。在聚類樹中，不同類別的原始數據點是樹的最低層，樹的頂層是一個聚類的根節點。創建聚類樹有自下而上合并和自上而下分裂兩種方法，本篇文章介紹合并方法。

層次聚類的合并算法

層次聚類的合并算法通過計算兩類數據點間的相似性，對所有數據點中最為相似的兩個數據點進行組合，并反復迭代這一過程。簡單的說層次聚類的合并算法是通過計算每一個類別的數據點與所有數據點之間的距離來確定它們之間的相似性，距離越小，相似度越高。并將距離最近的兩個數據點或類別進行組合，生成聚類樹。

歐幾里德距離矩陣

層次聚類使用歐式距離來計算不同類別數據點間的距離（相似度）。我們在前面的幾篇文章中都曾經介紹過歐氏距離的計算方法，本篇文章將通過創建一個歐式距離矩陣來計算和對比不同類別數據點間的距離，并對距離值最小的數據點進行組合。以下是歐式距離的計算公式。

以下為示例數據，我們通過歐氏距離計算下面A到G的歐式距離矩陣，并通過合并的方法將相似度最高的數據點進行組合，并創建聚類樹。

創建歐式距離矩陣的方法很簡單，將每個類別的數據點分別與A-G中的每個數據點計算距離值，其中A—>B表示數據點A到數據點B的距離，B—>A則代表數據點B到數據點A的距離。這兩個距離值是相同的，因此歐式距離矩陣呈對角線對稱（綠色部分和藍色部分）。其中對角線的0值是數據點與自己的距離值。我們將所有數據點間的距離結果進行對比，選擇其中距離最近的兩個數據點進行組合，并迭代這一過程。下圖顯示了歐式矩陣的邏輯和計算方法。

數據點之間的距離 ???

對于示例中的數據點，我們通過計算獲得了下面的歐式距離矩陣。其中數據點B到數據點C的距離在所有的距離值中最小，為1.00。以下為數據點間距離值的計算公式。

經過計算數據點B和數據點C與其他數據點相比有最高的相似度。因此，我們將數據點B和數據點C進行組合。并再次計算其他數據點間的距離。

數據點與組合數據點間的距離

將數據點B與數據點C進行組合后，重新計算各類別數據點間的距離矩陣。數據點間的距離計算方式與之前的方法一樣。這里需要說明的是組合數據點(B,C)與其他數據點間的計算方法。當我們計算(B,C)到A的距離時，需要分別計算B到A和C到A的距離均值。

經過計算數據點D到數據點E的距離在所有的距離值中最小，為1.20。這表示在當前的所有數據點中（包含組合數據點），D和E的相似度最高。因此我們將數據點D和數據點E進行組合。并再次計算其他數據點間的距離。

后面的工作就是不斷的重復計算數據點與數據點，數據點與組合數據點間的距離。這個步驟應該由程序來完成。這里由于數據量較小，我們手工計算并列出每一步的距離計算和數據點組合的結果。

這一步中，數據點A和數據點F的距離值在所有距離值中最小，因此我們將A和F進行組合，生成組合數據點（A,F）。

到此為止除了數據點G以外，其他的數據點都已經根據距離值（相似度）進行了組合。聚類樹的最底層已經完成。下面我們將繼續計算組合數據點間的距離，并對相似度最高的組合數據點進行合并。

兩個組合數據點間的距離

計算兩個組合數據點間距離的方法有三種，分別為Single Linkage，Complete Linkage和Average Linkage。在開始計算之前，我們先來介紹下這三種計算方法以及各自的優缺點。

Single Linkage

Single Linkage的計算方法是將兩個組合數據點中距離最近的兩個數據點間的距離作為這兩個組合數據點的距離。這種方法容易受到極端值的影響。兩個很相似的組合數據點可能由于其中的某個極端的數據點距離較近而組合在一起。

Complete Linkage

Complete Linkage的計算方法與Single Linkage相反，將兩個組合數據點中距離最遠的兩個數據點間的距離作為這兩個組合數據點的距離。Complete Linkage的問題也與Single Linkage相反，兩個不相似的組合數據點可能由于其中的極端值距離較遠而無法組合在一起。

Average Linkage

Average Linkage的計算方法是計算兩個組合數據點中的每個數據點與其他所有數據點的距離。將所有距離的均值作為兩個組合數據點間的距離。這種方法計算量比較大，但結果比前兩種方法更合理。

我們使用Average Linkage計算組合數據點間的距離。下面是計算組合數據點(A,F)到(B,C)的距離，這里分別計算了(A,F)和(B,C)兩兩間距離的均值。

?

通過計算及對比不同組合數據點間間的距離。(A,F)到(B,C)的距離在所有組合數據點間最小，為13.25。說明(A,F)到(B,C)相似度最高。因此，將(A,F)到(B,C)組合為(A,F,B,C)。

使用與之前相同的方法計算出組合數據點(D,E)和G的距離在目前所有組合數據點中最小。為34.70。將(D,E)和G組合為(D,E,G)。

最終，通過計算和合并，我們獲得了兩個組合數據點(A,F,B,C)和(D,E,G)。這也是聚類樹的最頂層的兩個數據點。下面，我們按之前的計算步驟來構建聚類樹。

?

層次聚類樹狀圖

將前面的每一步的計算結果以樹狀圖的形式展現出來就是層次聚類樹。最底層是原始A到G的7個數據點。依照7個數據點間的相似度組合為聚類樹的第二層(A,F),(B,C),(D,E)和G。以此類推生成完整的層次聚類樹狀圖。以下為簡單的示意圖。

—【所有文章及圖片版權歸 藍鯨（王彥平）所有。歡迎轉載，但請注明轉自“藍鯨網站分析博客”。】—

?

FILED UNDER:?網站數據分析?TAGGED WITH:?HIERARCHICAL CLUSTERING

Co

Read more:?http://bluewhale.cc/2016-04-19/hierarchical-clustering.html#ixzz50SsD0zfp

總結

以上是生活随笔為你收集整理的层次聚类算法的原理及实现Hierarchical Clustering的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。