DL、ML筆記(八): Clustering Algorithm(OPTICS)
OPTICS是一種基於密度的聚類方法，與DBSCAN算法相類似，算是DBSCAN之延伸算法，但改進了DBSCAN容易受參數影響的缺點。
OPTICS的概念為將所有資料進行排序，計算各資料對於核心點的距離，並依此距離排序(各核心點間的距離也加入排序)，排序完成後，再利用距離為條件，將資料分群。
OPTICS定義:
OPTICS用到與DBSCAN相類似的概念，因此其中有一些參數定義相同，像是:核心點、epsilonε、minPts及直接可達。而OPTICS中還有新的定義，核心距離(core-distance)及可達距離(reachablity-distance)
epsilon ε
為計算密度範圍之半徑
minPts
ε範圍內所需之最少資料點數量
核心點
一個點 p 在距離 ε 範圍內有至少 minPts 個點(包括自己)，這個點則為核心點
核心距離(core-distance)
核心距離只有核心點有此定義。核心距離為最小能包含minPts個資料點的距離，可表示為:
可達距離(reachablity-distance)
可達距離的對象只能是核心點，其計算核內所有點之可達距離，可達距離在核心距離內的點皆為核心距離，若介於核心距離與 ε 間，則可達距離為該點到核心點的距離，超出 ε 則無定義，可表示為:
OPTICS演算法
分別建立兩個陣列，有序陣列及結果序列。有序陣列為佔存陣列，用來存放核心點及該核心點的直接可達點。結果序列則是存放排序後的資料點。
1. 從資料集中選取一未被處理之核心點，將其放入結果序列，並將其相關之所有直接可達點放入有序陣列，已在結果序列中的點則忽略，並按照可達距離(reachability-distance)排序(升幂排序)
2. 從有序陣列中取出第一個點，即為可達距離最短的點，將其放入結果序列中，並且判斷該點是否為核心點，假如為核心點，則重複步驟一；為非則重複此步驟
3. 重複以上步驟直到有序陣列為空及排序完所有資料點
步驟如下圖:
按照以上步驟，可以得到按照可達距離排序後之結果陣列，之後可依照可達距離、核心距離及密度半徑對資料點進行分類，得到聚類結果。
其判斷條件為:
1. 當可達距離(ReachDist)小於密度半徑ε時，可以視為與先前類別同類，距離較近，視為同類
2. 而當可達距離大於密度半徑ε，可以分為兩種狀況: 核心距離小於密度半徑ε，建立新群，其意思為已經達到一群的條件，但與其他群距離過遠，因此建立新群；而核心距離大於密度半徑ε時，不滿足群之條件，且與其他群距離過遠，判斷為雜訊點
步驟圖如下:
其聚類效果如圖:
OPTICS中密度距離ε之影響
OPTICS解決了DBSCAN中對ε及minPts較為敏感的狀況，但依然需要這兩個參數，需要確定哪些為核心點，哪些為雜訊點，並用以建立結果序列。但ε及minPts的些微變化並不太會影響到排序結果(結果序列)，因為算法輸出的資料點順序並不會因不同的ε而有所改變，ε用於輔助資料排序。
OPTICS優點
1. 與DBSCAN擁有相同特性(不須指定分群數量、可以應用於任意形狀之分群、能分辨出雜訊點)
2. 此算法相對 DBSCAN 而言，對參數的選定較不敏感
