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處理數據集中的每個點,在這個過程中進行 -鄰域查詢。如果保證給定空間坐標時候,鄰域查詢可以以 的複雜度完成,可以得到總時間複雜度為 。OPTICS原始論文的作者表明OPTICS算法比DBSCAN算法慢常數1.6倍。由於值過大可能會使鄰域查詢的的時間複雜度降至線性,這個數值可能會顯著變化。

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

軟件實現

編輯

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) (中文).