DBSCAN是一种典型的基于密度的聚类方法。该方法由两个参数确定，∈表示半径，MinPts表示点的数目阈值，通常参数使用一个二元组（∈，MinPts）表示。

DBSCAN方法和基于网格法十分相似。然而，和基于网格法不同的是，它使用数据点的密度特性来将数据点合并成簇。因此，DBSCAN方法在基于密度进行数据点分类后，需要将密集区域内的各个数据点作为基础模块。DBSCAN方法能够发现任意形状的簇且不要求将簇的数目作为一个输入参数；基于网格法很容易受局部簇密度变化的影响。

概念

DBSCAN中的几个定义：

Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；

核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；

直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。

密度可达：对于样本集合D，给定一串样本点p,p….p，p= p,q= p,假如对象p从p直接密度可达，那么对象q从对象p密度可达。

密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。

Eg: 假设半径Ε=3，MinPts=3，点p的E邻域中有点{m,p,p1,p2,o}, 点m的E邻域中有点{m,q,p,m1,m2},点q的E邻域中有点{q,m},点o的E邻域中有点{o,p,s},点s的E邻域中有点{o,s,s1}.

那么核心对象有p,m,o,s(q不是核心对象，因为它对应的E邻域中点数量等于2，小于MinPts=3)；

点m从点p直接密度可达，因为m在p的E邻域内，并且p为核心对象；

点q从点p密度可达，因为点q从点m直接密度可达，并且点m从点p直接密度可达；

点q到点s密度相连，因为点q从点p密度可达，并且s从点p密度可达。

描述

DBSCAN算法描述:

输入: 包含n个对象的数据库，半径e，最少数目MinPts;

输出：所有生成的簇，达到密度要求。

(1)Repeat

(2)从数据库中抽出一个未处理的点；

(3)IF抽出的点是核心点 THEN 找出所有从该点密度可达的对象，形成一个簇；

(4)ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点；

(5)UNTIL 所有的点都被处理。

DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而参数的选择无规律可循，只能靠经验确定。

步骤

DBScan需要二个参数：扫描半径 (eps)和最小包含点数(minPts)。任选一个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。

如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。然后递归，以相同的方法处理该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展。

如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。

如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。

伪码

具体算法描述如下：

（1）检测数据库中尚未检查过的对象 p，如果 p未被处理(归为某个簇或者标记为噪声)，则检查其邻域，若包含的对象数不小于minPts，建立新簇 C，将其中的所有点加入候选集 N；

（2）对候选集 N 中所有尚未被处理的对象 q，检查其邻域，若至少包含minPts个对象，则将这些对象加入N；如果 q 未归入任何一个簇，则将 q 加入 C；

（3）重复步骤2)，继续检查 N 中未处理的对象，当前候选集 N为空；

（4）重复步骤1)~3)，直到所有对象都归入了某个簇或标记为噪声。

其伪代码描述如下：

输入：数据对象集合 D，半径Eps，密度阈值MinPts

输出：聚类C

DBSCAN（D, Eps, MinPts）

Begin

init C=0; //初始化簇的个数为0

for each unvisited point p in D

mark p as visited; //将p标记为已访问

N = getNeighbours (p, Eps);

if sizeOf(N) < MinPts then

mark p as Noise; //如果满足sizeOf(N) < MinPts，则将p标记为噪声

else

C= next cluster; //建立新簇 C

ExpandCluster (p, N, C, Eps, MinPts);

end if

end for

End

其中ExpandCluster算法伪码如下：

ExpandCluster(p, N, C, Eps, MinPts)

add p to cluster C; //首先将核心点加入 C

for each point p’ in N

mark p' as visited;

N’ = getNeighbours (p’, Eps); //对N邻域内的所有点在进行半径检查

if sizeOf(N’) >= MinPts then

N = N+N’; //如果大于MinPts，就扩展N的数目

end if

if p’ is not member of any cluster

add p’ to cluster C; //将p' 加入簇 C

end if

end for

End ExpandCluster

好处

1. 与K-means方法相比，DBSCAN不需要事先知道要形成的簇类的数量。

2. 与K-means方法相比，DBSCAN可以发现任意形状的簇类。

3. 同时，DBSCAN能够识别出噪声点。

4.DBSCAN对于数据库中样本的顺序不敏感，即Pattern的输入顺序对结果的影响不大。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。

缺点

1. DBScan不能很好反映高维数据。

2. DBScan不能很好反映数据集以变化的密度。

3.如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差。

参考

“一种基于密度的算法为在大空间数据库发现群以噪声”。第2次国际会议记录关于KDD的AAAI Press。检索2007-10-15，“实验在平行成群与DBSCAN”。欧洲同水准2001年：并行处理：第7国际欧洲同水准会议曼彻斯特，英国2001年8月28-31，行动Springer柏林。检索2004-02-19。