機器學習_學習筆記系列(85)：排序點來識別聚類結構(Ordering Points to Identify the Clustering Structure)
上一回我們介紹了DBSCAN，我們會藉由我們所設定的半徑𝜀和Radius Neighbor最小值MinPt，來拓展我們cluster的分布。
但是顯然我們在使用DBSCAN的時候出現了一個很大的問題，就是
我們分群的時候，我們沒辦法知道哪個點比較重要，也就是說因為在DBSCAN中，我們每次都只有看Radius Neighbor數量有沒有超過MinPt而已。
如下圖，我們MinPt設5的時候，p點他的Radius Neighbor是8，q點只有5個。顯然p點更適合作為我們cluster的中心位置，但是在DBSCAN我們會將p和q一視同仁，所以就會造成我們很難去確定資料真實分布的情況。
所以為了解決這方面的問題，就有人提出所謂的「Ordering Points to Identify the Clustering Structure」
Ordering Points to Identify the Clustering Structure
對於這個演算法，其簡稱為OPTICS (P.S.有研究NLP/NLU的朋友應該都知道models簡稱能湊成一個單字才夠炫吧XD)
提出這個演算法的人和前一篇DBSCAN的人一樣，由慕尼黑大學的Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander提出，其論文名稱叫做：
OPTICS: Ordering Points To Identify the Clustering Structure
而對於OPTICS的出現，就是為了改進上述原本DBSCAN的問題，其在這邊引入了所謂的core distance, reach distance和priority queue的概念。
core distance & reach distance
在DBSCAN的時候，我們會依據半徑𝜀找出我們的Radius Neighbor，接下來再假查Radius Neighbor的數量，是否超過MinPt。
OPTICS在這邊會多做一個步驟，就是計算core distance和reach distance，而這裡我們假設我們第i筆資料的radius neighbor有N_i個
Core distance:
Neigh_dist_i為第i筆資料其各個radius neighbors到i的距離，所以這裡的意思就是：
如果N_i小於MinPt我們的core_distance設為undefined，若大於等於MinPt，我們就把neighbors到第i筆資料的距離排序，然後第MinPt小的距離，即為core-distance
Reach-distance:
其中p為第i筆資料的neighbor。所以這裡的意思就是：
如果N_i小於MinPt我們的reach_distance設為undefined，若大於等於MinPt，我們就比較第i筆資料到p點距離和core-distance，取最大的那個值，即為reach distance。
如上圖所示，我們的MinPt=5，所以core_distance=distance(o,p)，而p點的reach_distance= distance(o,b)，a點的reach_distance= distance(o,p)。
而我們會引入core_distance和reach_distance最主要的原因，就是我們可以依據core_distance和reach_distance排序，並把依照各neighbor的距離排序，再下一次尋找新的neighbor前，我們就選擇那個距離比較近的，其也就是用到所謂的priority queue的概念。
Algorithms
對於OPTICS其整體演算法，在wikipedia上也有很詳盡的步驟：
其在一開始的時候，會把所有點的reach_distance初始化為undefined。接著用迴圈跑每一個資料點，而這邊我們會確認資料點p是否被處理過了，如果沒有才會進入迴圈，但處理過了我們就會繼續挑下一個資料點。
接下來的步驟，我們就是找p的radius neighbor，並把p標記為處理過的資料，然後output p to order list的意思就是，我們創建一個新的cluster把p加進去。
再下個步驟中，我們就會開始看p的core_distance是否為undefined，也就是說p的neighbor數量是否小於MinPt。如果不是undefined才可以繼續執行以下步驟。
接下來我們會創建seeds，然後呼叫update方程式，其就是我們上面所說的方式，利用reach_distance，距離越小的排到越前面。
而對於update方程式，其運作原理就是檢查每個neighbor裡面的資料，看其有沒有處理過，如果沒處理過，就計算new_reach_distance。而下一步中，如果先前reach_distance為undefined我們就把new_reach_distance存入這個neighbor的reach_distance，但如果此neighbor的reach_distance在先前就有數值(前面以不同資料為圓心計算出來的)，我們比較舊的reach_distance和new_reach_distance，如果新的比較小，就取代此neighbor的reach_distance。
另外這裡我們可以看到有insert和move up兩個動作，
Insert:
其指的就是我們會根據此neighbor的reach_distance插入seeds裡面。
例如原本seeds裡面的資料index為，[3,8,10,2,9]，其對應的reach_distance為[1,1.5,1.8,2,2.3]，如果這筆neighbor的index為4，reach_distance為1.7，seeds就會變成：[3,8,4,10,2,9]
Move up:
其指的就是把原本neighbor在seeds裡面排序，依據reach_distance往前移。
例如原本seeds裡面的資料index為，[3,8,10,2,9]，其對應的reach_distance為[1,1.5,1.8,2,2.3]，這筆neighbor的index為2，更新後的reach_index為1.3，seeds就會變成：[3,2,8,10,9]
回到OPTCIS方程式，當我們使用update後，就會開始進入for迴圈，而迴圈停止的條件是我們把seeds裡面所有的資料都處理完了。而對於for迴圈，我們會把seeds裡面的資料全部跑過一次，並一樣找出其radius neighbor，計算q的core_distance、標記此資料處理過、把此筆資料q加入cluster中。
接下來做的事情就一樣了，確認q的core_distance是不是undefined，也就是q的neighbor數量有沒有大於等於MinPt，有的話就是執行update方程式，把新發現的資料加入seeds裡面。
所以我們就會用這樣的方式把所有資料跑過一次，最後我們就可以得數個分好類的cluster。
Example
接著我們一樣以MNIST資料集為例子來看，
我們可以發現因為其分類的效果和原始數據算是蠻接近的，不過在重疊較多的地方就開始出現錯誤了。
Python Sample Code:
Github:
Reference:
[1] Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999). OPTICS: Ordering points to identify the clustering structure. ACM Sigmod record, 28(2), 49–60.
[2] wikipedia OPTICS Clustering Algorithms: https://en.wikipedia.org/wiki/OPTICS_algorithm
