Density-based spatial clustering of applications with noise

https://static.hlt.bme.hu/semantics/external/pages/deep_learning/en.wikipedia.org/wiki/DBSCAN.html

理论

考虑某个空间中的一组要聚类的点。设 \(\varepsilon\) 是一个参数，指定邻域相对于某个点的半径。出于DBSCAN聚类的目的，这些点被分类为核心点、（密度）可达点和异常值，如下所示：

  • 核心点：如果至少minPts点在 \(p\) 的距离 \(\varepsilon\) （包括 \(p\) ）内，则点 \(p\) 是核心点。
  • 如果 \(q\) 点与核心点p的距离在 \(\varepsilon\) 范围内，则 \(q\) 点可从 \(p\) 点直接到达。
  • 如果存在一条 \(p_1，\cdots，p_n\) 的路径，且 \(p_1 = p，p_n = q\) ，其中每个 \(p_{i+1}\) 都可以从 \(p_i\) 直接到达，则点 q 可以从 p 到达。请注意，这意味着路径上的所有点都必须是核心点，\(q\) 可能除外。
  • 从任何其他点都无法到达的所有点都是离群点或噪声点。

现在，如果 \(p\) 是一个核心点，那么它就和所有可以到达的点（核心点或非核心点）组成了一个群集(cluster)。每个群集至少包含一个核心点；非核心点可以是群集的一部分，但它们构成了群集的 “边”，因为它们不能用来到达更多的点。

image/svg+xml A C B N

在本图中，minPts = 4。点 A 和其他红色点是核心点，因为这些点周围半径为 \(\varepsilon\) 的区域至少包含 4 个点（包括点本身）。由于这些点之间都可以相互到达，因此它们组成了一个群集。B 点和 C 点不是核心点，但可以从 A 点（通过其他核心点）到达，因此也属于该簇。点 N 是一个噪声点，既不是核心点，也无法直接到达。

可到达性并不是一个对称关系，因为根据定义，无论距离多远，没有一个点可以从一个非核心点到达（所以一个非核心点可能是可到达的，但没有任何东西可以从它到达）。因此，需要进一步的连通性概念来正式定义 DBSCAN 所发现的聚类的范围。如果存在一个点 \(o\) ，使得 \(p\) 和 \(q\) 都可以从 o 到达，那么两个点 p 和 q 就是密度连接的。

这样，一个簇就满足了两个属性：

  1. 簇内的所有点都是相互密度连接的。
  2. 如果一个点可以从簇中的任何一点通过密度到达，那么它也是簇的一部分。

算法

基于查询的原始算法

DBSCAN 需要两个参数：\(\varepsilon\)（eps）和形成密集区域[a]所需的最小点数（minPts）。它从一个未被访问过的任意起点开始。检索该点的 \(\varepsilon\) 邻域，如果该邻域包含足够多的点，则启动一个聚类。否则，该点将被标记为噪声。需要注意的是，这个点以后可能会出现在另一个点的足够大的 \(\varepsilon\)-环境中，从而成为聚类的一部分。

如果发现一个点是一个聚类的密集部分，那么它的 \(\varepsilon\)-邻域也是该聚类的一部分。因此，在 \(\varepsilon\)-邻域内发现的所有点都会被添加进来，如果它们自己的 \(\varepsilon\)-邻域也是密集的，也会被添加进来。这个过程一直持续到完全找到密度连接的簇为止。然后，检索并处理一个新的未访问点，从而发现更多的聚类或噪声。

DBSCAN 可用于任何距离函数（以及相似性函数或其他谓词）

该算法的伪代码如下：

DBSCAN(DB, distFunc, eps, minPts) {
   C = 0                                                  /* Cluster counter */
   for each point P in database DB {
      if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
      Neighbors N = RangeQuery(DB, distFunc, P, eps)      /* Find neighbors */
      if |N| < minPts then {                              /* Density check */
         label(P) = Noise                                 /* Label as Noise */
         continue
      }
      C = C + 1                                           /* next cluster label */
      label(P) = C                                        /* Label initial point */
      Seed set S = N \ {P}                                /* Neighbors to expand */
      for each point Q in S {                             /* Process every seed point */
         if label(Q) = Noise then label(Q) = C            /* Change Noise to border point */
         if label(Q) ≠ undefined then continue            /* Previously processed */
         label(Q) = C                                     /* Label neighbor */
         Neighbors N = RangeQuery(DB, distFunc, Q, eps)   /* Find neighbors */
         if |N| ≥ minPts then {                           /* Density check */
            S = S ∪ N                                     /* Add new neighbors to seed set */
         }
      }
   }
}

其中RangeQuery可以使用数据库索引来实现，以提高性能，也可以使用慢速线性扫描来实现：

RangeQuery(DB, distFunc, Q, eps) {
   Neighbors = empty list
   for each point P in database DB {                      /* Scan all points in the database */
      if distFunc(Q, P) ≤ eps then {                      /* Compute distance and check varepsilon */
         Neighbors = Neighbors ∪ {P}                      /* Add to result */
      }
   }
   return Neighbors
}

抽象算法

DBSCAN 算法可抽象为以下步骤：

  1. 查找每个点的 \(\varepsilon\) 邻域中的点，并找出邻域超过 minPts 的核心点。
  2. 在邻域图上找到核心点的连接部分，忽略所有非核心点。
  3. 如果簇是 \(\varepsilon\) 邻居，则将每个非核心点分配给附近的簇，否则将其分配给噪声。

这种算法的简单实现需要在步骤1中存储邻域，因此需要大量内存。而最初的 DBSCAN 算法不需要这样做，它一次只对一个点执行这些步骤。

复杂度

DBSCAN 会访问数据库中的每个点，可能会访问多次（例如，作为不同簇的候选点）。但从实际考虑，时间复杂度主要受 regionQuery 调用次数的影响。DBSCAN 对每个点执行一次这样的查询，如果使用的索引结构能以 O(log n) 的速度执行邻域查询，则总体平均运行复杂度为 O(n log n)（如果参数 \(\varepsilon\) 的选择是有意义的，即平均只返回 O(log n) 个点）。如果不使用加速索引结构，或使用退化数据（例如距离小于 \(\varepsilon\) 的所有点），最坏情况下的运行时间复杂度仍为 O(n²)。可以将大小为 (n²-n)/2 的距离矩阵实体化，以避免距离的重新计算，但这需要 O(n²) 内存，而基于非矩阵的 DBSCAN 实现只需要 O(n) 内存。

优点

  1. 与 K-means不同，DBSCAN 不需要事先指定数据中的簇个数。
  2. DBSCAN 可以找到任意形状的簇。它甚至可以找到一个完全被另一个簇包围（但不相连）的簇。由于有了 MinPts 参数，所谓的单链效应（不同的簇之间由一条细线连接）就会减少。
  3. DBSCAN 具有噪声概念，对异常值具有鲁棒性。
  4. DBSCAN 只需要两个参数，而且对数据库中点的排序基本不敏感。(然而，如果点的排序发生变化，位于两个不同簇边缘的点可能会交换簇成员身份，而簇分配只有在同构时才是唯一的）。
  5. DBSCAN 设计用于可以加速区域查询的数据库，例如使用 R* 树。
  6. 如果对数据非常了解，参数 minPts 和 \(\varepsilon\) 可由领域专家设置。

缺点

  1. DBSCAN 并不完全是确定性的：根据数据处理的顺序，从一个以上的聚类可以到达的边界点可以是任一聚类的一部分。对于大多数数据集和领域来说，这种情况并不常见，对聚类结果的影响也不大：无论是核心点还是噪声点，DBSCAN 都是确定性的。DBSCAN*是一种将边界点视为噪声的变体，这种方法不仅能得到完全确定的结果，还能对密度连接成分做出更一致的统计解释。
  2. DBSCAN 的质量取决于函数 regionQuery(P,\(\varepsilon\)) 中使用的距离度量。最常用的距离度量是欧氏距离。特别是对于高维数据，由于所谓的 “维度诅咒”，这个度量几乎没有用武之地，很难找到一个合适的 \(\varepsilon\) 值。
  3. DBSCAN 无法很好地对密度差异较大的数据集进行聚类，因为此时无法为所有聚类选择合适的 minPts-\(\varepsilon\) 组合。
  4. 如果对数据和规模不甚了解，选择一个有意义的距离阈值 \(\varepsilon\) 可能会很困难。

扩展

DBSCAN*, Generalized DBSCAN (GDBSCAN), PreDeCon, SUBCLU, HDBSCAN