查看“︁OPTICS”︁的源代码

{{Expand English|date=2018年12月}}
{{机器学习导航栏}}
'''OPTICS'''（{{lang-en|Ordering points to identify the clustering structure}}）是由米哈伊爾·安克斯特（Mihael Ankerst）、馬庫斯·M·布呂尼希（Markus M. Breunig）、[[漢斯-彼得·克里戈爾]]和約爾格·桑德（Jörg Sander）提出的基于密度的[[聚类分析]][[算法]]。<ref>{{Cite journal|title=OPTICS|url=http://dx.doi.org/10.1145/304181.304187|last=Ankerst|first=Mihael|last2=Breunig|first2=Markus M.|date=1999-06-01|journal=ACM SIGMOD Record|issue=2|doi=10.1145/304181.304187|volume=28|pages=49–60|issn=0163-5808|last3=Kriegel|first3=Hans-Peter|last4=Sander|first4=Jörg}}</ref>OPTICS并不依赖全局变量来确定聚类，而是将空间上最接近的点相邻排列，以得到数据集合中的对象的线性排序。<ref>{{Cite web|url=https://zhuanlan.zhihu.com/p/41930932|title=OPTICS聚类算法|accessdate=2018-12-09|work=知乎专栏|language=zh|archive-date=2018-12-10|archive-url=https://web.archive.org/web/20181210063317/https://zhuanlan.zhihu.com/p/41930932|dead-url=no}}</ref>排序后生成的序列存储了与相邻点之间的距离，并最终生成了一个 dendrogram 。OPTICS算法的思路与[[DBSCAN]]类似，但是解决了DBSCAN的一个主要弱点，即如何在密度变化的数据中取得有效的聚类。同时 OPTICS也避免了多数聚类算法中对输入参数敏感的问题。

== 复杂度 ==
类似于[[DBSCAN]]，OPTICS处理数据集中的每个点，在这个过程中进行<math>\varepsilon</math>-邻域查询。如果保证给定空间坐标时候，邻域查询可以以<math>O(\log n)</math>的复杂度完成，可以得到总时间复杂度为<math>O(n\cdot \log n)</math>。OPTICS原始论文的作者表明OPTICS算法比DBSCAN算法慢常数1.6倍。由于值过大可能会使邻域查询的的时间复杂度降至线性，这个数值可能会显著变化。

实践中，选择<math>\varepsilon > \max_{x, y} d(x,y)</math>（大于数据集中的最大距离）是可能的，但由于每此领域查询会在整个数据集中进行，时间复杂度会降至平方。即使没有可用的空间索引，也会产生额外的堆管理成本。 因此<math>\varepsilon</math>应当被仔细选择。

== 软件实现 ==
{{Link-en|ELKI数据挖掘框架|ELKI}}提供了OPTICS、OPTICS-OF、DeLi-Clu、HiSC、HiCO和DiSH的Java实现。

[[R语言]]中，dbscan包提供了OPTICS的C++实现。

Python中，PyClustering库和[[Scikit-learn]]库实现了OPTICS；hdbscan库提供了HDBSCAN*实现。

== 参考资料 ==
{{reflist}}

[[Category:数据挖掘]]
[[Category:聚类分析]]
[[Category:机器学习]]
{{Compsci-stub}}