聚类（2）DBSCAN

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 7 分钟

一、DBSCAN算法【基于密度】

（3）聚类算法之DBSCAN算法 - GISer.Wang的文章 - 知乎 https://zhuanlan.zhihu.com/p/77043965

密度聚类方法的指导思想是，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。这类算法能克服基于距离的算法只能发现“类圆”（凸）的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。其代表算法为DBSCAN算法和密度最大值算法。

2.1 DBSCAN算法原理

DBCSAN（Density-Based Spatial Clustering of Applications with Noise）是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的数据中发现任意形状的聚类。

2.2 若干概念

DBSCAN是基于一组邻域来描述样本集的紧密程度的, 参数 \((\epsilon, M i n P t s)\) 用来描述邻域的样本分布紧密程度。其 中, \(\epsilon\) 描述了某一数据点的邻域距离阈值 (半径), MinPts 描述了数据点半径为 \(\epsilon\) 的邻域中数据点个数的最 小个数。下面是与密度聚类相关的定义 (假设我的样本集是 \(D=\left\{x_1, x_2, \ldots, x_m\right\}\) ):

  • 对象的 \(\varepsilon\) 领域：给定对象在半径 \(\varepsilon\) 内的区域; 对于 \(x_j \in D\), 其 \(\epsilon\)-邻域包含样本集 \(D\) 中与 \(x_j\) 的距离不大于 \(\epsilon\) 的子样本集。即 \(N_\epsilon\left(x_j\right)=\left\{x_i \in D \mid \operatorname{distance}\left(x_i, x_j\right) \leq \epsilon\right\}\) ，这个子样本集的个数记为 \(\left|N_\epsilon\left(x_j\right)\right|\) 。 \(\epsilon\)-邻域是 一个集合

  • 核心对象: 对于任一样本 \(x_j \in D\), 如果其 \(\epsilon\)-邻域对应的 \(N_\epsilon\left(x_j\right)\) 至少包含 MinPts 个样本, 即如果 \(\left|N_\epsilon\left(x_j\right)\right| \geq\) MinPts ，则 \(x_j\) 是核心对象。

  • 直接密度可达: 如果 \(x_i\) 位于 \(x_j\) 的 \(\epsilon\)-邻域中, 且 \(x_j\) 是核心对象, 则称 \(x_i\) 由 \(x_j\) 密度直达。反之不一定成 立, 即此时不能说 \(x_j\) 由 \(x_i\) 密度直达，除非 \(x_i\) 也是核心对象, 即密度直达不满足对称性。如图 \(\varepsilon=1, \mathrm{~m}=5, \mathrm{q}\) 是一个核心对象, 从对象q出发到对象p是直接密度可达的。

2019-05-18-061126.jpg

  • *密度可达: 对于 \(x_i\) 和 \(x_j\) ，如果存在样本样本序列 \(p_1, p_2, \ldots, p_T\) ，满足 \(p 1=x_i, p_T=x_j\) ，且 \(p_{t+1}\) 由 \(p_t\) 密度 直达, 则称 \(x_j\) 由 \(x_i\) 密度可达。也就是说, 密度可达满足传递性。此时序列中的传递样本 \(p_1, p_2, \ldots, p_{T-1}\) 均 为核心对象, 因为只有核心对象才能使其他样本密度直达。密度可达也不满足对称性**, 这个可以由密度直达的 不对称性得出。

2019-05-18-061154.jpg

  • 密度相连：对于 \(x_i\) 和 \(x_j\) ，如果存在核心对象样本 \(x_k\), 使 \(x_i\) 和 \(x_j\) 均由 \(x_k\) 密度可达, 则称 \(x_i\) 和 \(x_j\) 密度 相连。密度相连关系满足对称性。

2019-05-18-061202.jpg

  • 簇：一个基于密度的簇是最大的密度相连对象的集合。

  • 噪声：不包含在任何簇中的对象称为噪声。

从下图可以很容易看出理解上述定义，图中 MinPts \(=5\) ，红色的点都是核心对象, 因为其 \(\epsilon\)-邻域至少有 5 个 样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的圆内, 如果不在圆内, 则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列，此序列是一个簇集。在这些密度 可达的样本序列的 \(\epsilon\)-邻域内所有的样本相互都是密度相连的 (注意, 此图中有两个簇集)。

img

2.3 DBSCAN密度聚类思想

DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合, 即为我们最终聚类的一个类别, 或者说一个簇。（注意是密度相连的集合）, 簇里面可以有一个或者多个核心对象。如果只有一个核心对象, 则簇里其他的非核心对象样本都在这个核心对象的 \(\epsilon\)-邻域里; 如果有多个核心对象, 则簇里的任意一个核心对象的 \(\epsilon\) -邻域中一定有一个其他的核心对象, 否则这两个核心对象无法密度可达。这些核心对象的 \(\epsilon\)-邻域里所有的样本的 集合组成的一个DBSCAN聚类笶。

那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇 （这样的得到都肯定是密度相连的）。一直运行到所有核心对象都有类别为止。

基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

  • 异常点问题：一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。
  • 距离度量问题： 即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离、曼哈顿距离等。
  • 数据点优先级分配问题：例如某些样本可能到两个核心对象的距离都小于 \(\epsilon\), 但是这两个核心对象由于不是 密度直达, 又不属于同一个聚类笶, 那么如果界定这个样本的类别呢? 一般来说, 此时 DBSCAN采用先来后 到, 先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。

2.4 算法步骤

输入: 样本集 \(D=\left\{x_1, x_2, \ldots, x_m\right\}\), 邻域参数 \((\epsilon\), MinPts \()\)

  1. 初始化核心对象集合 \(\Omega=\emptyset\), 初始化类别 \(k=0\)
  2. 遍历 \(D\) 的元素, 如果是核心对象, 则将其加入到核心对象集合 \(\Omega\) 中
  3. 如果核心对象集合 \(\Omega\) 中元素都已经被访问, 则算法结束, 否则转入步骤4.
  4. 在核心对象集合 \(\Omega\) 中, 随机选择一个末访问的核心对象 \(o\), 首先将 \(o\) 标记为已访问, 然后将 \(o\) 标记类别 \(k\) , 最后将 \(o\) 的 \(\epsilon\)-邻域中末访问的数据，存放到种子集合 Seeds 中。
  5. 如果种子集合 \(S e e d s=\emptyset\), 则当前聚类簇 \(C_k\) 生成完毕，且 \(k=k+1\), 跳转到3。否则, 从种子集合 \(S e e d s\) 中挑选一个种子点 seed, 首先将其标记为已访问、标记类别 \(k\), 然后判断 seed 是否为核心对象, 如果是将 seed 中末访问的种子点加入到种子集合中, 跳转到 5 。

从上述算法可知：

  • 每个簇至少包含一个核心对象；
  • 非核心对象可以是簇的一部分，构成了簇的边缘（edge）；
  • 包含过少对象的簇被认为是噪声；

2.5 总结

优点
  1. 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
  2. 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
  3. 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
缺点
  1. 不能处理密度差异过大（密度不均匀）的聚类：如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
  2. 如果样本集较大时，聚类收敛时间较长;此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进；
  3. 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。【OPTICS算法】
  4. 边界点不完全确定性

2.6 OPTICS算法

OPTICS主要针对输入参数 \(\epsilon\) 过敏感做的改进, OPTICS和DBSCNA的输入参数一样 ( \(\epsilon\) 和 MinPts ), 虽然 OPTICS算法中也需要两个输入参数, 但该算法对 \(\epsilon\) 输入不敏感（一般将 \(\epsilon\) 固定为无穷大）, 同时该算法中并不显式的生成数据聚类, 只是对数据集合中的对象进行排序, 得到一个有序的对象列表, 通过该有序列表, 可以得到 一个决策图, 通过决策图可以不同 \(\epsilon\) 参数的数据集中检测笶集, 即: 先通过固定的 MinPts 和无穷大的 \(\epsilon\) 得到有序列表，然后得到决策图，通过决策图可以知道当 \(\epsilon\) 取特定值时（比如 \(\epsilon=3\) ) 数据的聚类情况。