DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN 算法基于一组“邻域”参数 $(ϵ,MinPts)$ 来刻画样本分布的紧密程度。给定数据集 $D=\{{\mathit{x}}_{\mathbf{1}},{\mathit{x}}_{\mathbf{1}},\cdots ,{\mathit{x}}_{\mathit{m}}\}$ ，定义下面这几个概念：

• $ϵ-\text{邻域}$ ：对 ${\mathit{x}}_{\mathit{j}}\in D$ ，其 $ϵ-\text{邻域}$ 包含样本集 $D$ 中与 ${\mathit{x}}_{\mathit{j}}$ 的距离不大于 $ϵ$ 的样本，即 $N_{ϵ}({\mathit{x}}_{\mathit{j}})=\{{\mathit{x}}_{\mathit{i}}\in D\mid \text{dist}({\mathit{x}}_{\mathit{i}},{\mathit{x}}_{\mathit{j}})\le ϵ\}$ ；其中 $\text{dist}(\cdot ,\cdot )$ 往往为欧式距离。
  
• 核心对象（core object）：若 ${\mathit{x}}_{\mathit{j}}$ 的 $ϵ-\text{邻域}$ 至少包含 $MinPts$ 个样本，即 $N_{ϵ}({\mathit{x}}_{\mathit{j}})\ge MinPts$ ，则 ${\mathit{x}}_{\mathit{j}}$ 是一个核心对象。
  
• 密度直达（directly density-reachable）：若 ${\mathit{x}}_{\mathit{j}}$ 位于 ${\mathit{x}}_{\mathit{i}}$ 的 $ϵ-\text{邻域}$ 中，且 ${\mathit{x}}_{\mathit{i}}$ 是核心对象，则称 ${\mathit{x}}_{\mathit{j}}$ 由 ${\mathit{x}}_{\mathit{i}}$ 密度直达。密度直达关系通常不满足对称性。
  
• 密度可达（density-reachable）：对 ${\mathit{x}}_{\mathit{i}}$ 与 ${\mathit{x}}_{\mathit{j}}$ ，若存在样本序列 ${\mathit{p}}_{\mathbf{1}},{\mathit{p}}_{\mathbf{2}},\cdots ,{\mathit{p}}_{\mathit{n}}$ ，其中 ${\mathit{p}}_{\mathbf{1}}={\mathit{x}}_{\mathit{i}},{\mathit{p}}_{\mathit{n}}={\mathit{x}}_{\mathit{j}}$ 且 ${\mathit{p}}_{\mathit{i}\mathbf{+}\mathbf{1}}$ 由 ${\mathit{p}}_{\mathit{i}}$ 密度直达，则称 ${\mathit{x}}_{\mathit{j}}$ 由 ${\mathit{x}}_{\mathit{i}}$ 密度可达。密度可达关系满足传递性，但不满足对称性。
  
• 密度相连（density-connected）：对 ${\mathit{x}}_{\mathit{i}}$ 与 ${\mathit{x}}_{\mathit{j}}$ ，若存在 ${\mathit{x}}_{\mathit{k}}$ 使得 ${\mathit{x}}_{\mathit{i}}$ 与 ${\mathit{x}}_{\mathit{j}}$ 均由 ${\mathit{x}}_{\mathit{k}}$ 密度可达，则称 ${\mathit{x}}_{\mathit{i}}$ 由 ${\mathit{x}}_{\mathit{j}}$ 密度相连。密度相连关系满足对称性。
  

图 1 给出了上述概念的直观显示。

那么，如何从数据集 $D$ 中找出满足上面定义的聚类簇（由密度可达关系导出的最大密度相连的样本集合）呢？DBSCAN 使用了如下方法：它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

DBSCAN 算法如图 2 所示。

在第 1-7 行中，算法先根据给定的邻域参数 $(ϵ,MinPts)$ 找出所有核心对象；然后在第 10-24 行中，以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。

以图 3 所示的西瓜相关数据集为例，假定邻域参数 $(ϵ,MinPts)$ 设置为 $ϵ=0.11,MinPts=5$ 。请用 DBSCAN 算法进行聚类处理。

DBSCAN 算法先找出各样本的 $ϵ-\text{邻域}$ 并确定核心对象集合：
$$\mathrm{\Omega }=\{{\mathit{x}}_{\mathbf{3}},{\mathit{x}}_{\mathbf{5}},{\mathit{x}}_{\mathbf{6}},{\mathit{x}}_{\mathbf{8}},{\mathit{x}}_{\mathbf{9}},{\mathit{x}}_{\mathbf{13}},{\mathit{x}}_{\mathbf{14}},{\mathit{x}}_{\mathbf{18}},{\mathit{x}}_{\mathbf{19}},{\mathit{x}}_{\mathbf{24}},{\mathit{x}}_{\mathbf{25}},{\mathit{x}}_{\mathbf{28}},{\mathit{x}}_{\mathbf{29}}\}$$
然后，从 $\mathrm{\Omega }$ 中随机选取一个核心对象作为种子，找出由它密度可达的所有样本，这就构成了第一个聚类簇。不失一般性，假定核心对象 ${\mathit{x}}_{\mathbf{8}}$ 被选中作为种子，则 DBSCAN 算法生成的第一个聚类簇为：
$$C_1=\{{\mathit{x}}_{\mathbf{6}},{\mathit{x}}_{\mathbf{7}},{\mathit{x}}_{\mathbf{8}},{\mathit{x}}_{\mathbf{10}},{\mathit{x}}_{\mathbf{12}},{\mathit{x}}_{\mathbf{18}},{\mathit{x}}_{\mathbf{19}},{\mathit{x}}_{\mathbf{20}},{\mathit{x}}_{\mathbf{23}}\}$$
然后，DBSCAN 算法将 $C_1$ 中包含的核心对象从 $\mathrm{\Omega }$ 中去除：
$$\mathrm{\Omega }=\mathrm{\Omega }\setminus C_1=\{{\mathit{x}}_{\mathbf{3}},{\mathit{x}}_{\mathbf{5}},{\mathit{x}}_{\mathbf{9}},{\mathit{x}}_{\mathbf{13}},{\mathit{x}}_{\mathbf{14}},{\mathit{x}}_{\mathbf{24}},{\mathit{x}}_{\mathbf{25}},{\mathit{x}}_{\mathbf{28}},{\mathit{x}}_{\mathbf{29}}\}$$
再从更新后的集合 $\mathrm{\Omega }$ 中随机选取一个核心对象作为种子来生成下一个聚类簇。上述过程不断重复，直至 $\mathrm{\Omega }$ 为空。 $C_1$ 之后生成的聚类簇为
$$\begin{array}{rl}{C}_2& =\{{\mathit{x}}_{\mathbf{3}},{\mathit{x}}_{\mathbf{4}},{\mathit{x}}_{\mathbf{5}},{\mathit{x}}_{\mathbf{9}},{\mathit{x}}_{\mathbf{13}},{\mathit{x}}_{\mathbf{14}},{\mathit{x}}_{\mathbf{16}},{\mathit{x}}_{\mathbf{17}},{\mathit{x}}_{\mathbf{21}}\}\\ C_3& =\{{\mathit{x}}_{\mathbf{1}},{\mathit{x}}_{\mathbf{2}},{\mathit{x}}_{\mathbf{22}},{\mathit{x}}_{\mathbf{26}},{\mathit{x}}_{\mathbf{29}}\}\\ C_4& =\{{\mathit{x}}_{\mathbf{24}},{\mathit{x}}_{\mathbf{25}},{\mathit{x}}_{\mathbf{27}},{\mathit{x}}_{\mathbf{28}},{\mathit{x}}_{\mathbf{30}}\}\end{array}$$
图 4 显示出 DBSCAN 算法先后生成聚类簇的情况。