OPTICS聚类算法.如何获得最好的epsilon

Question

我正在实施一个需要聚集地理点的项目.OPTICS算法似乎是一个非常好的解决方案.它只需要2个参数作为输入(MinPts和Epsilon),它们分别是将它们视为一个簇所需的最小点数,并且用于比较两个点所在的距离值是否可以放在同一个簇中.

我的问题是,由于各种各样的点,我不能设置固定的epsilon.请看下面的图片.

相同的点结构但是在不同的比例下将导致非常不同.假设设置MinPts = 2和epsilon = 1Km.在左侧,算法将创建2个群集(红色和蓝色),但在右侧,它将创建一个包含所有点(红色)的单个群集,但我想在右侧获得2个群集.

所以我的问题是:有没有办法动态计算epsilon值来得到这个结果？

编辑2012年6月5日3.15pm: 我以为我正在使用javaml库中的OPTICS算法实现,但它似乎实际上是一个DBSCAN算法实现.所以现在的问题是:有没有人知道基于java的OPTICS算法实现？

非常感谢你,请原谅我的英语不好.

马尔科

Answer 1

OPTICS 中的 epsilon 值只是为了限制使用索引结构时的运行时复杂性。如果您没有加速度索引，可以将其设置为infinity。

引用维基百科上的 OPTICS

参数 \varepsilon 严格来说是不必要的。它可以设置为最大值。然而，当空间索引可用时，它在复杂性方面确实发挥了实际作用。

你所拥有的看起来更像是 DBSCAN 而不是 OPTICS。在 OPTICS 中，您不需要选择 epsilon（它应该被作者称为 max-epsilon！），但是您的簇提取方法会处理这个问题。您是否使用 OPTICS 论文中提出的 Xi 提取？

minPts 更为重要。您应该尝试使用至少 5 或 10 的值，而不是 2。使用 2 时，您实际上是在执行单链接聚类！

一旦增加 minPts，上面给出的示例应该可以正常工作！

回复：编辑：正如您甚至可以在 Wikipedia 文章中看到的那样，ELKI 有一个正确的 OPTICS 实现，并且是用 Java 编写的。