一、DBSCAN算法

1.介绍

DBSCAN是一种著名的密度聚类算法，它基于一组邻域参数$(\epsilon,MinPts)$来刻画样本分布的紧密程度。

2.密度直达/可达/相连

给定数据集$D=\{X_1,X_2,...,X_N\}$，定义：

$\epsilon$-邻域：$N_{\epsilon}\left({\mathbf{x}}_{i}\right)=\left\{{\mathbf{x}}_{j} \in \mathbb{D} | \operatorname{distance}\left({\mathbf{x}}_{i}, {\mathbf{x}}_{j}\right) \leq \epsilon\right\}$
核心对象core object：若$|N_{\epsilon}(X_i)| \ge MinPts$，则称$X_i$是一个核心对象。即：若$X_i$的$\epsilon$-邻域中至少包含$MinPts$个样本，则$X_i$是一个核心对象。
密度直达directly density-reachable：若$X_i$是一个核心对象，且$X_j \in N_{\epsilon} (X_i)$，则称$X_j$由$X_i$密度直达，记作$X_i \rightarrow X_j$
密度可达density-reachable：对于$X_i$和$X_j$，若存在样本序列$(P_0,P_1,...,P_m,P_{m+1})$，其中$P_0=X_i,P_{m+1}=X_j,P_s \in D$，如果$P_{s+1}$由$P_s$密度直达，则称$X_j$由$X_i$密度可达，记作$X_i \leadsto X_j$
密度相连density-connected：对于$X_i$和$X_j$，若存在$X_k$，使得$X_i$与$X_j$均由$X_k$密度可达，则称$X_i$与$X_j$密度相连，记作：$X_i \sim X_j$

3.簇

给定邻域参数$(\epsilon,MinPts)$，一个簇$C \subseteq D$是满足下列性质的非空样本子集：

连接性connectivity：若$X_i \in C,X_j \in C$，则$X_i \sim X_j$
最大性maximality：若$X_i \in C$，且$X_i \leadsto X_j$，则$X_j \in C$

即一个簇是由密度可达关系导出的最大的密度相连样本集合。

4.算法的思想

若$X$为核心对象，则$X$密度可达的所有样本组成的集合记作$\mathbb{X}=\left\{\overrightarrow{\mathrm{x}}^{\prime} \in \mathbb{D} | \overrightarrow{\mathrm{x}} \leadsto \overrightarrow{\mathrm{x}}^{\prime}\right\}$。可以证明：$\mathbb{X}$就是满足连接性与最大性的簇。

于是DBSCAN算法首先任选数据集中的一个核心对象作为种子seed，再由此出发确定相应的聚类簇。

5.DBSCAN算法

输入：数据集$D={X_1,X_2,...,X_N}$，邻域参数$(\epsilon,MinPts)$

输出：簇划分$C=\{C_1,C_2,...,C_K\}$

算法步骤：

初始化核心对象集合为空集：$\Omega=\phi$
寻找核心对象：
1. 遍历所有的样本点$X_i,i=1,2,...,N$，计算$N_{\epsilon}(X_i)$
2. 如果$|N_{\epsilon}(X_i)| \ge MinPts$，则$\Omega = \Omega \cup \{X_i\}$
迭代：以任一未访问过的核心对象为出发点，找出有其密度可达的样本生成的聚类簇，直到所有核心对象都被访问为止。

6.注意

若在核心对象$o_1$的寻找密度可达的样本的过程中，发现核心对象$o_2$是由$o_1$密度可达的，且$o_2$尚未被访问，则将$o_2$加入$o_1$所属的簇，并且标记$o_2$为已访问。

对于$D$中的样本点，它只可能属于某一个聚类簇，因此在核心对象$o_i$的寻找密度可达的样本的过程中，它只能在标记为未访问的样本中寻找（标记为已访问的样本已经属于某个聚类簇了）。

7.优点

簇的数量由算法自动确定，无需人工指定。
基于密度定义，能够对抗噪音。
可以处理任意形状和大小的簇。

8.缺点

若样本集的密度不均匀，聚类间距差相差很大时，聚类质量较差。因为此时参数$\epsilon$和$MinPts$的选择比较困难。
无法应用于密度不断变化的数据集中。

密度

31(1).密度聚类---DBSCAN算法