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) (中文).
![]() | 这是一篇计算机科学小作品。您可以通过编辑或修订扩充其内容。 |