解释OPTICSxi聚类的结果

Question

我对检测密度变化的区域中的集群感兴趣，例如用户在城市中生成的数据，为此，我采用了OPTICS算法。

与DBSCAN不同，OPTICS算法不会产生严格的集群分区，而是会增加数据库的顺序。为了产生群集分区，我使用OPTICSxi，这是另一种基于OPTICS输出产生分类的算法。几乎没有能够从OPTICS输出中提取集群分区的库，而ELKI的OPTICSxi实现就是其中之一。

对我来说很清楚，如何解释DBSCAN的结果（尽管设置“有意义的”全局参数不是那么容易）。DBSCAN检测到簇的“原型”，其特征是密度，表示为每个区域的点数（分钟/ε）。OPTICSxi的结果似乎很难解释。

我有时会在OPTICSxi的输出中检测到两种现象，而我无法解释。一种是“尖峰”簇的外观，它们链接了地图的各个部分。我无法解释它们，因为它们似乎由很少的点组成，而且我不理解算法是如何决定将它们分组在同一群集中的。它们真的代表密度变化的“走廊”吗？查看基础数据，看起来不是那样。您可以在下面的图像中看到这些“尖峰”。

我无法解释的另一个现象是，有时存在相同层次级别的“重叠”集群。OPTICSxi基于数据库的OPTICS排序（例如树状图），该图中没有重复的点。

由于这是分层聚类，因此我们认为较低级别的群集包含较高级别的群集，并且在构建凸包时会强制执行该想法。但是，我看不出有在同一个层次上与其他集群相交的集群的任何理由，这实际上意味着某些点将具有双重集群“成员资格”。在下面的图像中，我们可以看到一些具有相同层次级别（0）的相交群集。

最后，我想让您留下的最重要的想法/问题是：我们希望在OPTICSxi聚类分类中看到什么？这个问题与参数OPTICSxi的任务紧密相关。

由于我几乎看不到针对特定聚类问题进行OPTICSxi的研究，因此我很难找到最佳聚类分类。即：可以提供一些有意义/有用的结果，并为DBSCAN集群增加一些价值的方法。为了帮助我回答这个问题，我使用不同的参数组合进行了多次OPTICSxi运行，并选择了三个参数进行讨论。

在此运行中，我使用了较大的epsilon（2Km）。该值的含义是我们接受大型群集（最大2Km）；由于算法“合并”了簇，因此我们最终会得到一些非常大的簇，这些簇几乎肯定具有低密度。我喜欢此输出，因为它公开了分类的层次结构，并且实际上使我想起了DBSCAN的多个运行，它们具有不同的参数组合（针对不同的密度），这是OPTICS的广告“强度”。如前所述，较小的群集对应于层次结构级别中的较高级别和较高的密度。

在此运行中，即使“ contrast”参数与上一次运行相同，我们也会看到大量的簇。这主要是因为我选择的Minpts数量较少，这表明我们接受的点数较少的聚类。由于这种情况下的epsilon较短，因此我们看不到这些大簇占据了地图的很大一部分。我发现此输出不如前一个有趣，这主要是因为，即使我们具有分层结构，在同一级别上也有许多聚类，并且其中许多相交。在解释方面，我可以看到一个与上一个相似的整体“形状”，但实际上在许多小簇中却离散了，这些簇很容易被忽略为“噪音”。

此运行具有一个与上一个相似的参数选择，不同之处在于分钟数更大。结果是，不仅我们发现了更少的集群，而且它们的重叠较少，而且它们大多处于同一水平。

从为DBSCAN增加价值的角度来看，我将选择第一个参数组合，因为它提供了数据的层次结构图，清楚地显示了哪些区域更密集。恕我直言，最后一个参数组合无法提供密度的整体分布的概念，因为它在整个研究区域内都发现了相似的簇。我有兴趣阅读其他意见。

Answer 1

从 OPTICS 图中提取簇的问题是簇的第一个和最后一个元素。仅从图中，您无法（据我理解）决定最后一个元素是否应该属于前一个簇。

考虑这样的情节

*
*        *
*        *
*       **
**************
A B C D EF G H

这可以是一个簇，其中 A 位于中间，BE 位于附近，F 是完全不同的簇中最近的元素。例如，数据集可能如下所示：

  *   D           *
B   A     E     F   G 
  *   C           H   *

或者，A 位于第一个簇的边缘，BD 是簇的一部分，而 E 是桥接簇 FH 间隙的离群元素。导致这种效果的数据集可能如下所示：

  D   *                 *
*   C   B  A    E     F   G 
  E   *                 H   *

OpticsXi可视化操作。F 是要分裂的“更陡”点，因此 E在每种情况下都将成为第一个簇的一部分。这实际上是 OpticsXi 在不查看数据点的情况下可以做出的最佳猜测。

这可能是导致您观察到的峰值的影响。

我看到四个选项：

1. 自己改进 OpticsXi。如果您有兴趣，我们可以讨论一些可能区分上述两种情况的启发式方法。

2. 实现其他提取方法之一，例如拐点（但它们可能会受到相同的影响，因为它们位于AFAICT 图中）

3. 使用 HDBSCAN（抱歉，尚未包含在 ELKI 中，尽管我们有一个似乎可以工作的版本） - 可能在 0.7.0 中

4. 对集群应用后处理。特别是，按簇顺序测试第一个和最后几个点，如果您想将它们包含在簇中，将它们移动到下一个，或将它们移动到父簇。也许只是简单地通过距集群的平均距离......