我正在实施一个需要对地理点进行聚类的项目。OPTICS 算法似乎是一个非常好的解决方案。它只需要两个参数作为输入（MinPts 和 Epsilon），它们分别是将它们视为一个簇所需的最小点数，以及用于比较两个点是否在同一个簇中的距离值。
我的问题是，由于点的种类繁多，我无法设置固定的 epsilon。看看下面的图片。
相同的点结构但不同的规模会导致非常不同的结果。假设设置 MinPts=2 和 epsilon = 1Km。在左侧，该算法将创建 2 个集群（红色和蓝色），但在右侧，它将创建一个包含所有点（红色）的单个集群，但我想在右侧也获得 2 个集群。
所以我的问题是：有没有什么方法可以动态计算 epsilon 值来得到这个结果？
编辑 2012 年 6 月 5 日下午 3 点 15 分： 我以为我使用的是 javaml 库中的 OPTICS 算法实现，但它似乎实际上是一个 DBSCAN 算法实现。所以现在的问题是：有人知道基于 Java 的 OPTICS 算法实现吗？
非常感谢你，原谅我糟糕的英语。
马可
OPTICS 中的 epsilon 值仅用于限制使用索引结构时的运行时复杂性。如果您没有加速度索引，则可以将其设置为infinity。
引用 Wikipedia on OPTICS
参数 \varepsilon 严格来说是不必要的。它可以设置为最大值。然而，当空间索引可用时，它在复杂性方面确实发挥了实际作用。
你看起来更像是 DBSCAN 而不是 OPTICS。在 OPTICS 中，您不需要选择 epsilon（作者应该将其称为 max-epsilon！），但是您的集群提取方法会解决这个问题。您是否使用 OPTICS 论文中提出的 Xi 提取？
minPts 更为重要。您应该尝试至少 5 或 10 的值，而不是 2。使用 2，您实际上是在执行单链接聚类！
一旦增加 minPts，您上面给出的示例应该可以正常工作！
回复：编辑：您甚至可以在 Wikipedia 文章中看到，ELKI 有一个适当的 OPTICS 实现，并且它是用 Java 编写的。
您可以尝试通过封闭矩形的总大小来缩放 epsilon。例如，您的左侧数据约为 4km x 6km（使用我的 Mark I 眼球测量），右侧约为 2km x 2km。因此，右侧的 epsilon 应该小 2.5 倍左右。
当然，这并不可靠。如果在您的右手数据中，在右侧 4 公里处和向下 2 公里处有一个额外的单点，这将使右侧的封闭矩形与左侧的相同，并且您会得到相似（错误）的结果。
您可以尝试最小生成树，然后删除最长的边。剩下的生成树和它们的中心是 OPTICS 的最佳中心，您可以计算它周围的点数。
在您上面的解释中，是规模变化造成了不确定性。当你的规模变大时，你的 epsilon 应该相应地改变。因为它们处于两个非常不同的比例，所以您呈现的两个图像不是同一组点。如果不更改参数，它们不会对您的 OPTICS 算法做出相同的响应。
简而言之，没有。没有办法动态计算 epsilon 来得到这个结果。像这样的聚类已经是 NP-Hard，这些聚类算法（optics、k-means、veroni）只能逼近最优解。