機器學習_學習筆記系列(82)：聚合式階層分群法(Agglomerative Hierarchical Clustering)
前幾回我們初步介紹了一些有關clustering的演算法，今天我們就要繼續延續下去clustering的內容，而這篇所要介紹的就是「Agglomerative Hierarchical Clustering」。
Agglomerative Hierarchical Clustering
關於AHC演算法，其是屬於Hierarchical Clustering的其中一個種類，而會叫Hierarchical Clustering主要是因為我們分群的時候是按照像decision tree那樣一層一層的方式將數據做切分。
而對於Hierarchical Clustering主要有分成兩種方式。
Agglomerative Hierarchical Clustering
把各個資料視為一個各體，然後慢慢往上合併其他資料，直到最後所有資料合併成一個cluster。
Divisive Hierarchical Clustering
把全部的資料視為一個個體，然後慢慢往下細分資料群，直到最後每一群都只剩下一筆資料。
而合併的方式最直觀的方式有三種，分別是single-linkage agglomerative algorithm、complete-linkage agglomerative algorithm和average-linkage agglomerative algorithm。
single-linkage agglomerative algorithm
計算兩個cluster的最近距離
complete-linkage agglomerative algorithm
計算兩個cluster的最遠距離
average-linkage agglomerative algorithm
計算兩個cluster的平均距離
以圖示呈現地化如下圖所示
所以我們可以用這樣的方法不斷合併我們的資料，直到達到我們想要的分群數量為止。
Algorithms
對於Hierarchical Clustering，因為網路上蠻少step by step的演算法介紹，大部分都是介紹理論然後import個scikit learn就結束，而網路上的open source code有些引入了一些平行計算和優化的packages讓初學者不是那麼容易理解，所以這裡我就放上我自己寫的演算法，雖然效能不是最佳，但希望能讓大家參考參考。
Example
接下來我們以MNIST手寫辨識資料集為例子看single、complete和average三種演算法的效能如何(P.S.為了視覺化，我們將其用PCA降到2維)
我們可以看到因為我們的資料屬於比較緊密(dense)，所以運用single的方法，比較接近我們的原始數據。
Python Sample Code:
Github:
Reference:
[1] Rokach, Lior, and Oded Maimon. “Clustering methods.” Data mining and knowledge discovery handbook. Springer US, 2005. 321–352.
