DBSCAN

DBSCAN（英语：Density-based spatial clustering of applications with noise），是1996年由马丁·爱胥特（英语：Martin Ester）、汉斯-彼得·克里戈尔、约尔格·桑德（Jörg Sander）及Xiaowei Xu提出的集群分析算法， 这个算法是以密度为本的：给定某空间里的一个点集合，这算法能把附近的点分成一组（有很多相邻点的点），并标记出位于低密度区域的局外点（最接近它的点也十分远），DBSCAN是其中一个最常用的集群分析算法，也是其中一个科学文章中最常引用的。

在2014年，这个算法在领头数据挖掘会议KDD上获颁发了Test of Time award，该奖项是颁发给一些于理论及实际层面均获得持续性的关注的算法。

基础知识

考虑在某空间里将被集群的点集合，为了进行 DBSCAN 集群，所有的点被分为核心点、(密度)可达点及局外点，详请如下：

• 如果一个点 p 在距离 ε 范围内有至少 minPts 个点(包括自己)，则这个点被称为核心点，那些 ε 范围内的则被称为由 p 直接可达的。根据定义，没有任何点是由非核心点直接可达的。
• 如果存在一条道路 p₁, ..., p_n ，有 p₁ = p和p_n = q， 且每个 p_i+1 都是由 p_i 直接可达的(道路上除了 q 以外所有点都一定是核心点)，则称 q 是由 p 可达的。
• 所有不由任何点可达的点都被称为局外点。

如果 p 是核心点，则它与所有由它可达的点(包括核心点和非核心点)形成一个集群，每个集群拥有最少一个核心点，非核心点也可以是集群的一部分，但它是在集群的“边缘”位置，因为它不能达至更多的点。

在这幅图里，minPts = 4，点 A 和其他红色点是核心点，因为它们的 ε-邻域（图中红色圆圈）里包含最少 4 个点（包括自己），由于它们之间相互相可达，它们形成了一个集群。点 B 和点 C 不是核心点，但它们可由 A 经其他核心点可达，所以也属于同一个集群。点 N 是局外点，它既不是核心点，又不由其他点可达。

“可达性”（英文：Reachability ）不是一个对称关系，因为根据定义，没有点是由非核心点可达的，但非核心点可以是由其他点可达的。所以为了正式地界定 DBSCAN 找出的集群，进一步定义两点之间的“连结性”（英文：Connectedness） ：如果存在一个点 o 使得点 p 和点 q 都是由 o 可达的，则点 p 和点 q 被称为(密度)连结的，而连结性是一个对称关系。

定义了连结性之后，每个集群都符合两个性质：

1. 一个集群里的每两个点都是互相连结的；
2. 如果一个点 p 是由一个在集群里的点 q 可达的，那么 p 也在 q 所属的集群里。

算法

DBSCAN 需要两个参数：ε (eps) 和形成高密度区域所需要的最少点数 (minPts)，它由一个任意未被访问的点开始，然后探索这个点的 ε-邻域，如果 ε-邻域里有足够的点，则建立一个新的集群，否则这个点被标签为杂音。注意这个点之后可能被发现在其它点的 ε-邻域里，而该 ε-邻域可能有足够的点，届时这个点会被加入该集群中。

如果一个点位于一个集群的密集区域里，它的 ε-邻域里的点也属于该集群，当这些新的点被加进集群后，如果它(们)也在密集区域里，它(们)的 ε-邻域里的点也会被加进集群里。这个过程将一直重复，直至不能再加进更多的点为止，这样，一个密度连结的集群被完整地找出来。然后，一个未曾被访问的点将被探索，从而发现一个新的集群或杂音。

算法可以以下伪代码表达，当中变数根据原本刊登时的命名：

DBSCAN(D, eps, MinPts) {
   C = 0
   for each point P in dataset D {
      if P is visited
         continue next point
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else {
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)
      }
   }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts { 
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster
         add P' to cluster C
   }
}

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

注意这个算法可以以下方式简化：其一，"has been visited" 和 "belongs to cluster C" 可被结合起来，另外 "expandCluster" 副程式不必被抽出来，因为它只在一个位置被调用。以上算法没有以简化方式呈现，以反映原本出版的版本。另外，regionQuery 是否包含 P 并不重要，它等价于改变 MinPts 的值。

复杂度

DBSCAN对数据库里的每一点进行访问，可能多于一次（例如作为不同集群的候选者），但在现实的考虑中，时间复杂度主要受regionQuery的调用次数影响，DBSCAN对每点都进行刚好一次调用，且如果使用了特别的编号结构，则总平均时间复杂度为${\displaystyle O(n\log {n})}$，最差时间复杂度则为${\displaystyle O(n^{2})}$。可以使用${\displaystyle O(n^{2})}$空间复杂度的距离矩阵以避免重复计算距离，但若不使用距离矩阵，DBSCAN的空间复杂度为${\displaystyle O(n)}$。

上图展示 DBSCAN 分辨非线性可分集群的能力，上图所示的资料点不能被 K-平均算法 或 Gaussian Mixture EM clustering 正确或足够好地分类。

优点

1. 相比 K-平均算法，DBSCAN 不需要预先声明集群数量。
2. DBSCAN 可以找出任何形状的集群，甚至能找出一个集群，它包围但不连接另一个集群，另外，由于 MinPts 参数，single-link effect （不同集群以一点或极幼的线相连而被当成一个集群）能有效地被避免。
3. DBSCAN 能分辨噪音（局外点）。
4. DBSCAN 只需两个参数，且对数据库内的点的次序几乎不敏感（两个集群之间边缘的点有机会受次序的影响被分到不同的集群，另外集群的次序会受点的次序的影响）。
5. DBSCAN 被设计成能配合可加速范围访问的数据库结构，例如 R*树。
6. 如果对资料有足够的了解，可以选择适当的参数以获得最佳的分类。

缺点

1. DBSCAN 并不完全是确定性的：从多个簇可到达的边界点可以是任一簇的一部分，具体取决于数据处理的顺序。对于大多数数据集和领域来说，这种情况并不经常出现，并且对聚类结果影响很小：因为核心点和噪声点都是确定性的。 DBSCAN* 是一种将边界点视为噪声的变体算法，这种方式实现了完全确定性的结果以及密度连通分量的更一致的统计解释。
2. DBSCAN 的质量取决于区域查询函数 regionQuery(P,ε) 中使用的距离度量。最常用的距离度量是欧氏距离。但是对于高维数据，由于维数灾难(Curse of dimensionality)，这个度量几乎没有用武之地，很难找到一个合适的邻域范围ε。
3. DBSCAN 无法很好地对密度差异较大的数据集进行聚类，因为此时无法为所有聚类选择合适的 minPts-ε 组合。
4. 如果对数据和规模不了解，可能很难选择合适的邻域范围ε。

有关文章

• OPTICS算法：一个DBSCAN的一般化，有效地以“最大搜寻半径”代替ε参数。
• Connected component
• 并查集

注意

参考文献

延伸阅读

• Arlia, Domenica; Coppola, Massimo. "Experiments in Parallel Clustering with DBSCAN". Euro-Par 2001: Parallel Processing: 7th International Euro-Par Conference Manchester, UK August 28–31, 2001, Proceedings. Springer Berlin.
• Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "Density-based Clustering"（页面存档备份，存于互联网档案馆）. WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30.