cluster-analysis - 解释 OPTICSxi 聚类的结果

Question

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

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

对我来说很清楚，如何解释 DBSCAN 的结果(虽然不是那么容易，设置“有意义”的全局参数)； DBSCAN 检测集群的“原型(prototype)”，以密度为特征，表示为每个区域的点数 (minpts/epsilon)。 OPTICSxi 的结果似乎更难以解释。

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



我无法解释的另一个现象是 有时会有相同层级的“重叠”集群 . OPTICSxi 基于数据库的 OPTICS 排序(例如树状图)，并且该图中没有重复的点。

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



最后，我想留给您的最重要的想法/问题是:我们期望在 OPTICSxi 聚类分类中看到什么？ 这个问题与参数化 OPTICSxi 的任务密切相关。

由于我几乎没有看到针对特定集群问题运行 OPTICSxi 的任何研究，因此我很难找到最佳的聚类分类是什么；即:可以提供一些有意义/有用的结果，并为 DBSCAN 聚类增加一些值(value)。为了帮助我回答这个问题，我使用不同的参数组合执行了多次 OPTICSxi，我选择了三个，我将在下面讨论。



在这次运行中，我使用了很大的 epsilon (2Km) 值；该值的含义是我们接受大型集群(最多 2 公里)；由于算法“合并”了集群，我们最终会得到一些非常大的集群，这些集群几乎肯定是低密度的。我喜欢这个输出，因为它暴露了分类的层次结构，它实际上让我想起了几次运行 DBSCAN 使用不同的参数组合(针对不同的密度)，这就是 OPTICS 所宣传的“强度”。正如前面提到的，较小的集群对应于层次尺度中的更高级别和更高的密度。



在这次运行中，我们看到大量集群，即使“对比度”参数与上一次运行相同。这主要是因为我选择了少量的 minpt，这表明我们接受点数较少的集群。由于这种情况下的 epsilon 较短，我们没有看到这些大集群占据了 map 的很大一部分。我发现这个输出没有前一个有趣，主要是因为，即使我们有一个层次结构，在同一级别上也有许多集群，而且其中许多是相交的。在解释上，我可以看到一个与前一个相似的整体“形状”，但它实际上被离散为许多容易被忽略为“噪声”的小簇。



这次运行的参数选择与上一次类似，只是 minpts 更大；结果是，我们不仅发现了更少的集群，它们的重叠也更少，而且它们大多处于同一级别。

从为 DBSCAN 增加值(value)的角度来看，我会选择参数的第一种组合，因为它提供了数据的分层图片，清楚地展示了哪些区域更密集。恕我直言，最后一个参数组合无法提供密度的全局分布的概念，因为它在整个研究区域都发现了类似的集群。我有兴趣阅读其他意见。

Answer 1

从 OPTICS 图中提取集群的问题是集群的第一个和最后一个元素。仅从情节来看，您无法(以我的理解)决定最后一个元素是否应该属于前一个集群。

考虑这样的情节

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

这可以是一个簇，其中 A 就在中间，B-E 在附近，而 F 是完全不同的簇中最近的元素。例如，数据集可能如下所示:

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

或者，A 位于第一个簇的边缘，B-D 是簇的一部分，而 E 是一个离群元素，将间隙连接到簇 F-H。
导致这种影响的数据集可能如下所示:

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

OpticsXi 以视觉方式运行。 F 是要拆分的“陡峭”点，因此 E 在每种情况下都将成为第一个集群的一部分。从字面上看，这是 OpticsXi 在不查看数据点的情况下所能做出的最佳猜测。

这很可能是导致您一直观察到的尖峰的效应。

我看到四个选项:

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

实现其他提取方法之一，例如拐点(但它们可能会受到相同的影响，因为它们在情节 AFAICT 中)

使用 HDBSCAN(抱歉，尚未包含在 ELKI 中，尽管我们有一个似乎可以运行的版本)- 可能在 0.7.0

对集群应用后处理。特别是按簇顺序测试前几个和最后几个点，如果要将它们包含在簇中，则将它们移至下一个，或将它们移至父簇。也许只是通过与集群的平均距离...