OPTICS
![]() | 此條目可參照英語維基百科相應條目來擴充。 (2018年12月) |
機器學習與資料探勘 |
---|
![]() |
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數據挖掘框架提供了OPTICS、OPTICS-OF、DeLi-Clu、HiSC、HiCO和DiSH的Java實現。
R語言中,dbscan包提供了OPTICS的C++實現。
Python中,PyClustering庫和Scikit-learn庫實現了OPTICS;hdbscan庫提供了HDBSCAN*實現。
參考資料
- ^ 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.
- ^ OPTICS聚类算法. 知乎專欄. [2018-12-09]. (原始內容存檔於2018-12-10) (中文).
![]() | 這是一篇電腦科學小作品。您可以透過編輯或修訂擴充其內容。 |