OPTICS - 維基百科，自由的百科全書

此條目可參照英語維基百科相應條目來擴充。 (2018年12月)
若您熟悉來源語言和主題，請協助參考外語維基百科擴充條目。請勿直接提交機械翻譯，也不要翻譯不可靠、低品質內容。依版權協議，譯文需在編輯摘要註明來源，或於討論頁頂部標記{{Translated page}}標籤。

機器學習與資料探勘

範式監督學習無監督學習線上機器學習元學習（英語：Meta-learning (computer science)）半監督學習自監督學習強化學習基於規則的機器學習（英語：Rule-based machine learning）量子機器學習
問題統計分類生成模型迴歸分析聚類分析降維密度估計（英語：density estimation）異常檢測數據清洗自動機器學習關聯規則學習語意分析結構預測（英語：Structured prediction）特徵工程表徵學習排序學習（英語：Learning to rank）語法歸納（英語：Grammar induction）本體學習（英語：Ontology learning）多模態學習
監督學習 (分類 · 回歸) 學徒學習（英語：Apprenticeship learning）決策樹學習集成學習 Bagging 提升方法隨機森林 k-NN 線性回歸樸素貝葉斯人工神經網絡邏輯斯諦迴歸感知器相關向量機（RVM）支持向量機（SVM）遷移學習微調
聚類分析 BIRCH CURE算法（英語：CURE algorithm）層次 k-平均 Fuzzy 期望最大化（EM） DBSCAN OPTICS 均值飄移（英語：Mean shift）
降維因素分析 CCA ICA LDA NMF（英語：Non-negative matrix factorization） PCA PGD（英語：Proper generalized decomposition） t-SNE（英語：t-distributed stochastic neighbor embedding） SDL
結構預測（英語：Structured prediction）圖模式貝氏網絡條件隨機域隱馬爾可夫模型
異常檢測 RANSAC k-NN 局部異常因子（英語：Local outlier factor）孤立森林（英語：Isolation forest）
人工神經網絡自編碼器認知計算深度學習 DeepDream（英語：DeepDream）多層感知器 RNN LSTM GRU（英語：Gated recurrent unit） ESN（英語：Echo state network）儲備池計算（英語：reservoir computing）受限玻爾茲曼機 GAN SOM CNN U-Net Transformer Vision transformer（英語：Vision transformer）脈衝神經網絡（英語：Spiking neural network） Memtransistor（英語：Memtransistor）電化學RAM（英語：Electrochemical RAM）（ECRAM）
強化學習 Q學習 SARSA 時序差分（TD）多智能體（英語：Multi-agent reinforcement learning） Self-play（英語：Self-play (reinforcement learning technique)） RLHF
與人類學習主動學習（英語：Active learning (machine learning)）眾包 Human-in-the-loop（英語：Human-in-the-loop）
模型診斷學習曲線（英語：Learning curve (machine learning)）
數學基礎內核機器（英語：Kernel machines）偏差–方差困境（英語：Bias–variance tradeoff）計算學習理論（英語：Computational learning theory）經驗風險最小化奧卡姆學習（英語：Occam learning） PAC學習（英語：Probably approximately correct learning）統計學習 VC理論
大會與出版物 NeurIPS ICML（英語：International Conference on Machine Learning） ICLR ML（英語：Machine Learning (journal)） JMLR（英語：Journal of Machine Learning Research）
相關條目人工智能術語（英語：Glossary of artificial intelligence）機器學習研究數據集列表（英語：List of datasets for machine-learning research）機器學習概要（英語：Outline of machine learning）
閱論編

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

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

軟件實現

[編輯]

ELKI數據挖掘框架（英語：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）（中文）.

這是一篇電腦科學小作品。您可以透過編輯或修訂擴充其內容。