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

層次聚類的合并算法

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

歐幾里德距離矩陣

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

以下為示例數(shù)據(jù)，我們通過歐氏距離計(jì)算下面A到G的歐式距離矩陣，并通過合并的方法將相似度最高的數(shù)據(jù)點(diǎn)進(jìn)行組合，并創(chuàng)建聚類樹。

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

數(shù)據(jù)點(diǎn)之間的距離 ???

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

經(jīng)過計(jì)算數(shù)據(jù)點(diǎn)B和數(shù)據(jù)點(diǎn)C與其他數(shù)據(jù)點(diǎn)相比有最高的相似度。因此，我們將數(shù)據(jù)點(diǎn)B和數(shù)據(jù)點(diǎn)C進(jìn)行組合。并再次計(jì)算其他數(shù)據(jù)點(diǎn)間的距離。

數(shù)據(jù)點(diǎn)與組合數(shù)據(jù)點(diǎn)間的距離

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

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

后面的工作就是不斷的重復(fù)計(jì)算數(shù)據(jù)點(diǎn)與數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)與組合數(shù)據(jù)點(diǎn)間的距離。這個(gè)步驟應(yīng)該由程序來完成。這里由于數(shù)據(jù)量較小，我們手工計(jì)算并列出每一步的距離計(jì)算和數(shù)據(jù)點(diǎn)組合的結(jié)果。

這一步中，數(shù)據(jù)點(diǎn)A和數(shù)據(jù)點(diǎn)F的距離值在所有距離值中最小，因此我們將A和F進(jìn)行組合，生成組合數(shù)據(jù)點(diǎn)（A,F）。

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

兩個(gè)組合數(shù)據(jù)點(diǎn)間的距離

計(jì)算兩個(gè)組合數(shù)據(jù)點(diǎn)間距離的方法有三種，分別為Single Linkage，Complete Linkage和Average Linkage。在開始計(jì)算之前，我們先來介紹下這三種計(jì)算方法以及各自的優(yōu)缺點(diǎn)。

Single Linkage

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

Complete Linkage

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

Average Linkage

Average Linkage的計(jì)算方法是計(jì)算兩個(gè)組合數(shù)據(jù)點(diǎn)中的每個(gè)數(shù)據(jù)點(diǎn)與其他所有數(shù)據(jù)點(diǎn)的距離。將所有距離的均值作為兩個(gè)組合數(shù)據(jù)點(diǎn)間的距離。這種方法計(jì)算量比較大，但結(jié)果比前兩種方法更合理。

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

?

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

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

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

?

層次聚類樹狀圖

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

參考原文：http://bluewhale.cc/2016-04-19/hierarchical-clustering.html

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

總結(jié)

以上是生活随笔為你收集整理的【通俗易懂】层次聚类算法的原理及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。