OPTICS

OPTICS（英语：Ordering points to identify the clustering structure）是由Mihael Ankerst，Markus M. Breunig，Hans-Peter Kriegel和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）（中文）.

[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）（中文）.

[1]

[2]