5

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

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

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

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

ε=1000； xi=0.05； minpts=100；

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

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

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

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

ε=2000； xi=0.025； minpts=100；

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

ε=250； xi=0.035； minpts=10

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

ε=250； xi=0.035； minpts=100

本次运行有一个参数选择，与上一次类似，只是minpts更大；结果是，我们不仅发现更少的集群并且它们重叠更少，而且它们大多处于同一水平。

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

4

1 回答 1

2

从 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. 对集群应用后处理。特别是按集群顺序测试前几个点和最后几个点，如果要将它们包含在集群中，请将它们移动到下一个，或者将它们移动到父集群。也许只是通过与集群的平均距离......

于 2014-06-23T17:49:45.417 回答