機器學習_學習筆記系列(87)：基於密度之含噪空間階層聚類法(Hierarchical Density-Based Spatial Clustering of Applications with Noise)
在先前的章節我們介紹了DBSCAN演算法，其是利用我們所設定的radius neighbor半徑𝜀和radius neighbor數量下限MinPt來達到clustering的效果。
然而在先前OPTICS的章節也提到過DBSCAN雖然在clustering上有不受distribution function限制的優勢，但是有用過這個演算法的朋友都知道DBSCAN有些嚴重的問題
- DBSCAN的𝜀和MinPt兩個參數，對於最後分群的結果非常靈敏，導致我們try and error時間大幅增加。
- DBSCAN假設每個cluster的空間密度相同，導致我們忽略掉更適合作為中心點的位置。
而對於這方面的問題就有人提出了Hierarchical版的DBSCAN，簡稱HDBSCAN解決這方面的問題。
Hierarchical Density-Based Spatial Clustering of Applications with Noise
對於HDBSCAN其是由加拿大University of Alberta的Ricardo J.G.B. Campello、Davoud Moulavi和Joerg Sander，論文名稱叫做
Density-based clustering based on hierarchical density estimates
另外大家有注意到其中有一個作者Joerg Sander，他也是DBSCAN和OPTICS的作者，而這兩篇是他在德國慕尼黑大學讀博班的時候發的。
回歸正題，對於HDBSCAN，其演算法是基於原本的DBSCAN和OPTICS去做優化，而在這篇論文中，也引入了一個新的觀念「Mutual Reachability Graph」
Mutual Reachability Graph
還記得我們在OPTICS章節定義了一個東西
Core distance:
其就是我們給定一個數據點x_i，然後我們計算每一個點到x_i的距離，並將這些距離排序，而數據點x_i到第MinPt近的數據點的距離，就是我們的core distance。
不過這裡與OPTICS不同的是，OPTICS是直接規範neighbor半徑𝜀，如果在𝜀裡面的數據點數量小於MinPt，core distance為undefined，但是HDBSCAN，這裡就是很直接的計算i到離i第MinPt近的點的距離，不會用到𝜀。
回到HDBSCAN，在這邊作者定義了一個東西叫做「Mutual Reachability Distance」，寫成式子為
其意思就是我們有兩個點x_p和x_q，我們比較x_p的core distance、x_q的core distance和x_p到x_q的距離，三者中最大的那個就是x_p和x_q的Mutual Reachability Distance。
而所謂的Mutual Reachability Graph就是我們數據間每個點和點之間的距離，都用Mutual Reachability Distance來建立。
此外這邊得注意的是，關於數據點到自己的距離，在歐幾里得中為0，但在Mutual Reachability Graph，我們會把他設成自己的core distance。
最後當我們建立Mutual Reachability Graph後，下一個階段就是使用Hierarchical 來分群，而在這之前，我們使用的資料結構為Minimum Spanning Tree。
Minimum Spanning Tree
相信有學過演算法的朋友應該都知道MST，簡單來說就是把原本的graph做簡化，而這個簡化的Graph中，其滿足
任兩個vertex是互通的，且所有的edge加起來是最小的
而對於如何從graph建構MST，我們使用的演算法為Prim’s algorithm，而說道這個演算法又有一個故事，當初這個演算法由Vojtěch Jarník在1930最先發現，後來Robert C. Prim在沒有看過Jarník論文的情況下，在1957也發現這個演算法，同樣的在1959年也被Edsger Dijkstra獨立發現。雖然這個演算法最初是由Jarník發現，但是大部分的人還是用Prim’s Algorithms這個詞。
而對於Prim’s Algorithms其想法和概念和Dijkstra’s Algorithm非常像，而且也可以用fibonacci heap優化來降低time complexity。
而Prim’s Algorithms，他做的事情就是我們每次找下一個點的時候，都選擇距離最短的那個，所以整體流程如下
原圖：
而其MST建構流程如下
而關於Prim’s Algorithms有個很有趣的事情，就是若所有edge長度都不一樣，則不管我們選擇從哪個點開始，最後都會得到一樣的圖，不信的話大家可以試試看上面的例子，而嚴謹的證明過程，這裡就不描述了。
OK所以回到上面，我們現在就可以把Mutual Reachability Graph以Prim’s Algorithms搭配fibonacci heap資料結構計算出其MST。
Hierarchical Method
接下來當我們拿到MST後，就是對進行clustering，這邊稍微比較複雜一點，而具體的方法就是，我們會從MST中依照edge的距離由大到小移除
而這邊我們會設兩個參數
- C_min：形成cluster的最小數量
- C_max：形成cluster的最大數量
當我們把edge移除後，我們之後整個MST就會變成兩個subgraph，而我們再看這兩個subgraph的數量有沒有都大於C_min，沒有的話，我們就不拆掉這個edge，並檢查下一個edge，如果都大於，我們就拆掉這個edge，然後我們可以看兩個subgraph，有沒有其中一個數量小於C_max，有的話，代表可以形成一個cluster，沒有的話我們就以當前的subgraph繼續看下一個edges，就這樣依此類推執行演算法到不能再分出cluster為止。
Example
接下來我們來看MNIST的表現
我們可以看到HDBSCAN的效果，相較於DBSCAN和OPTICS明顯的好非常多。
Python Sample Code:
Github:
Reference:
[1] Campello, R. J., Moulavi, D., & Sander, J. (2013, April). Density-based clustering based on hierarchical density estimates. In Pacific-Asia conference on knowledge discovery and data mining (pp. 160–172). Springer, Berlin, Heidelberg.
[2] Prim’s Algorithms: https://en.wikipedia.org/wiki/Prim%27s_algorithm
