模型概述

DBSCAN是一种聚类算法，首先明确几个概念：

$\epsilon$-邻域：对任一样本点$x^{(i)}$，数据集$D$中与该样本点的距离不大于$\epsilon$的其余样本点构成的集合，该集合内的样本数为该点的密度，即dense_i$=N_{\epsilon}(x^{(i)})={x^{(j)}\in{D}|dist(x^{(i)},x^{(j)})\le\epsilon}$
核心对象(core object)：若某一样本的密度不小于一个阈值，即dense_i$\ge$Min_pts，则该样本是一个核心对象
边界对象：若某一样本的密度小于Min_pts，则该样本成为边界对象；特别地，密度为$1$的样本被称为噪声样本
密度直达：核心对象直达其邻域内的样本点，直达方向由核心对象指向其邻域内的样本点
密度可达：对两个样本点$x^{(i)}$与$x^{(j)}$，若存在一条密度直达链$x^{(i)}\rightarrow…{\rightarrow}x^{(j)}$，则称$x^{(i)}$可达$x^{(j)}$，方向由$x^{(i)}$指向$x^{(j)}$，前者必须为核心对象，后者不作要求
密度相连：同一个核心对象可达的两样本点称为密度相连，即同时存在两条直达链：$x^{(i)}\rightarrow…{\rightarrow}x^{(j)}$与$x^{(i)}\rightarrow…{\rightarrow}x^{(k)}$，$x^{(j)}$与$x^{(k)}$密度相连

DBSCAN算法将所有密度相连的样本聚成一类。换个角度来说，DBSCAN会尽量多的寻找密度相连的核心对象（容易推出密度相连在核心对象上满足交换律），然后将这些核心对象及其邻域样本都归为一类。