機器學習_學習筆記系列(83)：沃德階層分群法(Ward Hierarchical Clustering)
上一回我們介紹了Hierarchical Clustering，其是將我們原本單獨的數據，運用single-linkage、complete-linkage和average-linkage把他們群聚起來。
而對於上述這三種方法外還有另一種linkage的方式，其是基於Ward’s Method。
Ward Hierarchical Clustering
對於上述的Ward’s Method，其是也是相當的直觀，假使我們今天有兩個cluster，分別為C_1和C_2，我們的計算方式就是
其中u代表的就是C_1和C_2裡面所有資料的平均，而我們可以看到其做的事情就是，找中心點，然後計算所有屬於C_1 U C_2的資料到中心距離的總和。
而利用Ward’s Method的好處就是在有些情況他比single和complete的方法，更能夠全觀的考慮到整個cluster中的資料分布，相對average來說也能更有指標性的選擇適合的cluster。另外利用Ward’s Method，因為我們summation所有點到質心的距離，所以最後得到的cluster也會比較平均。
Note
其實對於Ward Hierarchical Clustering，Scipy有一套自己的Hierarchical Clustering函式庫，而實際上這麼龐大的運算量如果我們直接用python寫，會花非常多時間
所以許多的機器學習和資料科學套件，底層的矩陣運算、遞迴和樹狀演算法都是由C或C++來實現一些效能上的優化。
不過其實對於這方面，就有人發明了所謂的「Cython」，其功能就是使用者可以不用在更改太多python語法的情況下撰寫C/C++，也就是說當我們用Cython寫code的時候，他會把他轉為C/C++的形式以GCC complier編譯，而且他可以在notebook裡面直接編譯、執行，節省了許多建置環境的步驟。
像知名的機器學習套件Sci-kit Learn對於一些樹資料結構的建立和搜尋演算法就使用了Cython撰寫。
Example
接下來我們以MNIST手寫辨識資料集來看其效能
我們可以看到對於使用ward演算法其相較於single、complete和average更接近原始數據分布。
Python Sample Code:
Github:
Reference:
[1] Ward Jr, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301), 236–244.
