4 模式識别-層次聚類法（概念介紹+執行個體示範）

武漢理工大學資源 郭志強

層次聚類算法：首先每個樣本自成一類，然後再讓樣本與樣本之間通過它的相似度進行合并，減少類别數目，最終使分類模型達到一個比較穩定的狀态。

基于門檻值的門檻值聚類法：首先找出聚類中心， 然後再把各個樣本，根據與各個聚類中心的歐式距離進行歸類的。

這個矩陣類似多點的圖的鄰接矩陣，記錄每兩個點之間的距離關系。

D(0)表示初始分類情況，D(1)表示第一次減少類别後的分類狀态，以此類推。

那麼D(n)怎麼得到下一個D(n+1)狀态呢？D(n)每個樣本類将會找到兩類之間歐式距離最小（距離最近）的那個類進行合并，進而得到D(n+1) 。

注意此時結束條件非常重要，如果沒有結束條件可以預見最後的結果将是所有的樣本點将變成一類。

算法計算實際過程舉例

以斜線0線為分割線，下三角形的資料和以0線鏡面對稱的上三角形的資料是相等的，是以我們隻列出下三角形資料。

在上圖D(0)表中，可知

最小，那麼我們就可以把D(0)狀态中的G1類和G2類合并成一個類G12，進而得到新的分類狀态D(1) 。新的類G12（5X5的矩陣）與其他類（還是5X1矩陣）之間的距離是不能再使用歐式距離來計算的，是以我們需要一個距離選擇新法則，就是選擇類G12原來的組成部分類G1和類G2與其他類之間的最小歐氏距離作為新的類G12與其他類的距離。

那麼如何由分類狀态D(1)得到下一個分來狀态D(2)呢？同理，重複D(0)到D(1)的過程即可。由上圖所示，類間最小值是根号4，那麼表示類G5和類G6合并成新的類G56，得到新的分類狀态D(2)，就從最初D(0)的6個類别變成了D(2)的4個類别，是的樣本分類類别得以減少。之後過程若沒有達到結束條件則以此類推即可。以上方法實作了層次聚類法的“聚類”核心思想。

若達到 最後即結束條件，得到結果。