熟悉CMT的都知道，作者在聚類部分使用了層次凝聚聚類算法（Hierarchical Agglomerative Clustering）并且使用的是單鍊（Single-link），今天我們就來學習下這個算法。
前面學習了幾種聚類算法，K-Means，EM，AP等都屬于平面聚類（Flat Clustering），因為這些算法的輸出都是傳回一個平面的無結構的聚類集合，是以叫做Flat clustering；平面聚類有一個缺陷就是要選擇聚類的數目以及初始點，這對于沒有經驗的人員來說是一件很棘手的工作，因為聚類結果的好壞完全依賴于這一參數的選擇，是以很多時候可以考慮下層次聚類算法，避免了聚類數量和初始點的選擇。層次聚類算法有多種形式，本篇介紹的這個叫做層次凝聚聚類算法（Hierarchical Agglomerative Clustering），簡稱HAC，其主要思想就是，先把每一個樣本點當做一個聚類，然後不斷重複的将其中最近的兩個聚類合并（就是凝聚的含義），直到滿足疊代終止條件。
HAC具體實作步驟：
1）将訓練樣本集中的每個資料點都當做一個聚類；
2）計算每兩個聚類之間的距離，将距離最近的或最相似的兩個聚類進行合并；
3）重複上述步驟，直到得到的目前聚類數是合并前聚類數的10%，即90%的聚類都被合并了；當然還可以設定其他終止條件，這樣設定是為了防止過度合并。
很明顯，還是一樣的老套路，唯一的新鮮處在于第二步中，如何度量兩個聚類間的相似度，關于這個主要有三種定義：
1）單鍊（Single-link）：不同兩個聚類中離得最近的兩個點之間的距離，即MIN；
2）全鍊（Complete-link）：不同兩個聚類中離得最遠的兩個點之間的距離，即MAX；
3）平均鍊（Average-link）：不同兩個聚類中所有點對距離的平均值，即AVERAGE；
不難發現，其中前兩種定義的出發點是那些點集中的特殊點或外點，如噪點；而最後一種定義相對來說就不那麼穩定了，是以又有人提出了使用距離的中值，這樣可以排除一些個别點的幹擾。
可以看下圖效果（基于單鍊），黑色點是噪聲點：
這是一種自下而上（bottom-up）的層次聚類，是以叫做層次凝聚聚類（Hierarchical Agglomerative Clustering），由于其計算點對距離時需要多次周遊，是以計算量可想而知，并且每次疊代隻能合并兩個聚類，時間複雜度上同樣缺乏優勢，是以實際應用中沒有Flat clustering那麼受歡迎，但是由于其避免了聚類數以及初始點的選擇，而且不會陷入局部最優，在一些二次複雜度的問題中還是應該考慮的；在最早的CBIR系統中，HAC被應用到詞袋技術中，如下圖：
另外還有一種層次聚類算法，叫做自上而下的，這種形式的聚類主要是使用了一種分離聚類的方法，這裡就不打算深入了，需要的可參考http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html#sec:hac，裡面有很詳細的關于層次聚類的東西。