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