OPTICS

OPTICS（英語：Ordering points to identify the clustering structure）是由米哈伊爾·安克斯特（Mihael Ankerst）、馬庫斯·M·布呂尼希（Markus M. Breunig）、漢斯-彼得·克里戈爾和約爾格·桑德（Jörg Sander）提出的基於密度的聚類分析算法。^[1]OPTICS並不依賴全局變量來確定聚類，而是將空間上最接近的點相鄰排列，以得到數據集合中的對象的線性排序。^[2]排序後生成的序列存儲了與相鄰點之間的距離，並最終生成了一個 dendrogram 。OPTICS算法的思路與DBSCAN類似，但是解決了DBSCAN的一個主要弱點，即如何在密度變化的數據中取得有效的聚類。同時 OPTICS也避免了多數聚類算法中對輸入參數敏感的問題。

複雜度

類似於DBSCAN，OPTICS處理數據集中的每個點，在這個過程中進行${\displaystyle \varepsilon }$-鄰域查詢。如果保證給定空間坐標時候，鄰域查詢可以以${\displaystyle O(\log n)}$的複雜度完成，可以得到總時間複雜度為${\displaystyle O(n\cdot \log n)}$。OPTICS原始論文的作者表明OPTICS算法比DBSCAN算法慢常數1.6倍。由於值過大可能會使鄰域查詢的的時間複雜度降至線性，這個數值可能會顯著變化。

實踐中，選擇${\displaystyle \varepsilon >\max _{x,y}d(x,y)}$（大於數據集中的最大距離）是可能的，但由於每此領域查詢會在整個數據集中進行，時間複雜度會降至平方。即使沒有可用的空間索引，也會產生額外的堆管理成本。 因此${\displaystyle \varepsilon }$應當被仔細選擇。

軟體實現

ELKI數據挖掘框架（英語：ELKI）提供了OPTICS、OPTICS-OF、DeLi-Clu、HiSC、HiCO和DiSH的Java實現。

R語言中，dbscan包提供了OPTICS的C++實現。

Python中，PyClustering庫和Scikit-learn庫實現了OPTICS；hdbscan庫提供了HDBSCAN*實現。

參考資料

1. Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter; Sander, Jörg. OPTICS. ACM SIGMOD Record. 1999-06-01, 28 (2): 49–60. ISSN 0163-5808. doi:10.1145/304181.304187.
2. OPTICS聚类算法. 知乎專欄. [2018-12-09]. （原始內容存檔於2018-12-10） （中文）.