輕鬆聊之Hierarchical Clustering

上一次我們介紹了K-means分群演算法，今天來介紹另外一個分群(Clustering)演算法-Hierarchical Clustering，中文好像叫階層分群法。

一般Hierarchical Clustering有兩個方式來產生最後的樹狀結構，

• 聚積(Agglomerative)，Bottom-up
• 分裂(Divisive)，Top-down

今天介紹的是比較常用的bottom-up的方式，直接來看圖說故事吧。

圖片來源: Statistical Learning (Stanford Online Course )

大概演算法流程如下，

1. 把每一個點都當成一個叢集(Cluster)

2. 把最接近的兩個Cluster合併成一個

3. 重複以上步驟

4. 直到所有的點都已經合併成一個Cluster

你可以發現Hierarchical Clustering最後可以表示成一個Tree。

有了樹(Tree )之後，我們就可以開始做砍樹的動作。ㄟ…好不容易把樹種起來了，為什麼要砍掉呢？因為我們的目的不是種樹，是要將資料分群啊。來看一下下面的圖就知道了，左圖是種出來的樹，如果我們在高度9的地方把樹砍掉(中圖)，就會得到兩個Cluster。如果刀子從高度5下去(右圖)，就會得到3個Culster。所以你要得到K個Culster就自己找下刀點吧。

圖片來源: Statistical Learning (Stanford Online Course )

我們在上面的演算法流程2的地方有說到把最近的兩個Cluster給合併起來，眼尖的人可能會發現，既然它是一個Culster的話，那我要怎麼計算兩個Culster的距離呢?大概有以下4個方法。

1. Complete-linkage: 取兩個Cluster中最遠的兩個點

2. Single-linkage: 取兩個Cluster中最近的兩個點

3. Average-linkage: 兩個Cluster之間各點距離總和的平均

4. Centriod-linkage: 取各Cluster的中心點

至於什麼樣的情況該選擇哪一個計算方式，這也是實際使用上需要克服的一個問題。怎麼測量”距離”(相近程度)，也是實務上的一個挑戰。最後就是老問題，到底要切多少塊Culster，我的K應該選擇多少才合理，這個等我有心得後再跟大家分享囉。