DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种很典型的聚类算法，该算法是基于簇是可以通过样本分布的紧密程度决定的这样的假设，将簇定义为密度相连的样本点的最大集合。该算法能够把具有足够高密度的区域划分为簇，可在有噪声样本的样本集中发现任意形状的簇。
密度定义
如何来定义样本分布的紧密程度？实际上简单理解为样本的密度，也就是样本点在一定范围内所包含的样本的个数。在这里我们用参数$(\varepsilon,S)$来描述邻域内样本分布的紧密程度，其中,$\varepsilon$代表的是某一样本的邻域范围，而$S$代表的是某一样本在邻域范围$\varepsilon$内所包含的样本的个数。首先安利一些基本概念：
基本概念
- $\varepsilon$ 邻域
给定样本在半径$\varepsilon$内的区域。 - 核心对象
对于给定的样本数目$n$，如果某一个对象(一个样本)在$\varepsilon$邻域内至少包含$n$个对象，则该对象被称为核心对象。图中$M$、$N$均是核心对象。
- 直接密度可达
在图中$M$是一个核心对象，$Q$在$M$的$\varepsilon$邻域内，则$Q$从对象$M$出发是直接密度可达的。 - 密度可达
如果对象$N$从对象$M$出发是直接密度可达的，对象$P$从对象$N$出发是直接密度可达的，则对象$M$和$P$是密度可达的。 - 密度相连
如果对象$M$从对象$N$出发是直接密度可达的，对象$P$从对象$N$出发也是直接密度可达的，则$M$和$P$是密度相连的。 - 对象的分类
对于数据集中的任意一个点，它要么是核心对象，要么是噪声对象，要么是边缘对象。
噪声对象：样本点不是核心对象，并且不再任何一个核心对象的$\varepsilon$邻域内。
边缘对象:不同簇的边缘点，不是核心对象，可能由在两个核心对象的$\varepsilon$邻域内密度聚类
DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
在DBSCAN的一个聚类簇里面可以只有一个核心对象，也可以有多个核心对象。
问题1：如何找到一个样本簇的集合？
首先任意选择一个核心对象，然后找到所有这个核心对象能够密度可达的样本集合，即为一个样本簇。接着任意选择没有类别的另一个核心对象找到所有这个核心对象能够密度可达的样本集合。一直运行到所有核心对象都有类别为止。
算法描述
输入：样本集$D=(x_1,x_2,…,x_n)$,邻域参数$(\varepsilon,S)$,样本的距离度量方式
输出：簇划分
- 初始化核心对象集合$\Omega=\emptyset$，初始化聚类的簇数$k=0$,初始化样本未访问集合$\Gamma=D$
- 找出所有核心对象
$for j=1,2,…,n:$
(1)通过距离度量方式，找出样本$x_j$在邻域$\varepsilon$内样本集$N_{\varepsilon}(x_j)$
(2)如果子样本集样本个数满足:$|N_{\varepsilon}(x_j)|\ge S$,则样本$x_j$加入核心对象集合:$\Omega=\Omega \cup x_j$ - 如果核心对象集合$\Omega=\emptyset$，则算法结束，否则，转入步骤4
- 在核心对象集合$\Omega$中，随机选择一个核心对象$o$，初始化当前核心对象队列$\Omega_{cur}={o}$，初始化类别序号$k=k+1$，初始化当前簇样本集$C_k={o}$,更新未访问集合$\Gamma=\Gamma-{o}$
- 如果当前簇核心对象队列$\Omega_{cur}=\emptyset$，则当前聚类簇$C_k$生成完毕，更新簇划分$C={C_1,C_2,…,C_k}$，更新核心对象集合$\Omega=\Omega-C_k$，转入步骤3，否则转入步骤6
- 在当前簇核心对象队列$\Omega_{cur}$中取出一个核心对象$o’$,找到直接密度可达的样本子集$N_{\varepsilon}(o’)$，令$\Delta=N_{\varepsilon}(o’)\cap \Gamma$，更新当前簇样本集合$C_k=C_k \cup \Delta$，更新未访问的样本集合$\Gamma=\Gamma-\Delta$,更新$\Omega_{cur}=\Omega_{cur} \cup (N_{\varepsilon}(o^{‘}) \cap \Omega)$,转入步骤5。
程序实现
参考资料
