text: OPTICS是由Mihael Ankerst，Markus M. Breunig，Hans-Peter Kriegel和Jörg Sander提出的基於密度的聚類分析演算法。OPTICS並不依賴全域性變數來確定聚類，而是將空間上最接近的點相鄰排列，以得到資料集合中的物件的線性排序。排序後生成的序列儲存了與相鄰點之間的距離，並最終生成了一個 dendrogram 。OPTICS演算法的思路與DBSCAN類似，但是解決了DBSCAN的一個主要弱點，即如何在密度變化的資料中取得有效的聚類。同時 OPTICS也避免了多數聚類演算法中對輸入引數敏感的問題。複雜度.類似於DBSCAN，OPTICS處理資料集中的每個點，在這個過程中進行formula_1-鄰域查詢。如果保證給定空間座標時候，鄰域查詢可以以formula_2的複雜度完成，可以得到總時間複雜度為formula_3。OPTICS原始論文的作者表明OPTICS演算法比DBSCAN演算法慢常數1.6倍。由於值過大可能會使鄰域查詢的的時間複雜度降至線性，這個數值可能會顯著變化。實踐中，選擇formula_4是可能的，但由於每此領域查詢會在整個資料集中進行，時間複雜度會降至平方。即使沒有可用的空間索引，也會產生額外的堆管理成本。 因此formula_1應當被仔細選擇。軟體實現.提供了OPTICS、OPTICS-OF、DeLi-Clu、HiSC、HiCO和DiSH的Java實現。R語言中，dbscan包提供了OPTICS的C++實現。Python中，PyClustering庫和Scikit-learn庫實現了OPTICS；hdbscan庫提供了HDBSCAN*實現。
metadata: erhwenkuo/wikipedia-zhtw
metadata: OPTICS
metadata: https://zh.wikipedia.org/wiki?curid=6391884