OPTICS

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

複雜度

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

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

軟件實現

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

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

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