DBSCAN是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications with Noise，意即：一种基于密度，对噪声鲁棒的空间聚类算法。直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

简单来讲，给定一组点，DBSCAN将彼此距离（欧几里得距离）很近的点聚成一类，同时它还将低密度区域中的点标记为异常值（outlier）。

DBSCAN使用了两个参数:半径eps和密度阈值Minpts。DBSCAN需要由用户主观来选择参数,参数的选择决定了最终的聚类结果。在计算复杂度方面,如果采用空间索引,DBSCAN的计算复杂度是O(nlog(n)),其中n是对象数,否则计算复杂度为O(n2)。

DBSCAN聚类算法

　　　　下面我们对DBSCAN聚类算法的流程做一个总结。

　　　　输入：样本集D=(x1,x2,…,xm)(x1,x2,…,xm)，邻域参数(ϵ,MinPts)(ϵ,MinPts), 样本距离度量方式

　　　　输出： 簇划分C.　

　　　　1）初始化核心对象集合Ω=∅Ω=∅, 初始化聚类簇数k=0，初始化未访问样本集合ΓΓ = D,  簇划分C = ∅∅

　　　　2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象：

　　　　　　a) 通过距离度量方式，找到样本xjxj的ϵϵ-邻域子样本集Nϵ(xj)Nϵ(xj)

　　　　　　b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts， 将样本xjxj加入核心对象样本集合：Ω=Ω∪{xj}Ω=Ω∪{xj}

　　　　3）如果核心对象集合Ω=∅Ω=∅，则算法结束，否则转入步骤4.

　　　　4）在核心对象集合ΩΩ中，随机选择一个核心对象oo，初始化当前簇核心对象队列Ωcur={o}Ωcur={o}, 初始化类别序号k=k+1，初始化当前簇样本集合Ck={o}Ck={o}, 更新未访问样本集合Γ=Γ−{o}Γ=Γ−{o}

　　　　5）如果当前簇核心对象队列Ωcur=∅Ωcur=∅，则当前聚类簇CkCk生成完毕, 更新簇划分C={C1,C2,…,Ck}{C1,C2,…,Ck}, 更新核心对象集合Ω=Ω−CkΩ=Ω−Ck， 转入步骤3。

　　　　6）在当前簇核心对象队列ΩcurΩcur中取出一个核心对象o′o′,通过邻域距离阈值ϵϵ找出所有的ϵϵ-邻域子样本集Nϵ(o′)Nϵ(o′)，令Δ=Nϵ(o′)∩ΓΔ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪ΔCk=Ck∪Δ, 更新未访问样本集合Γ=Γ−ΔΓ=Γ−Δ, 转入步骤5.

　　　　输出结果为： 簇划分C={C1,C2,…,Ck}{C1,C2,…,Ck}

DBSCAN 算法最初有 Ester 等人在1996年最初提出，DBSCAN 自发表后受到了学界的一直推崇，众多科学文献引用该算法，同时DBSCAN 算法也是 PreDeCon 和 SUBCLU 等聚类算法中的一部分，1998年，Sander 和 Ester 提出了适用性更加广泛的 GDBSCAN 算法。 2014年的时候，DBSCAN 算法获得了2014 SIGKDD Test of Time Award， 2007年 Birant 提出了一种名为 ST-DBSCAN 的算法，该算法最显著的优势在于可以用于时空数据的处理。2010年，Kisilevich 等人提出了通过地理标记照片数据从而挖掘地点和事件的算法 P-DBSCAN。

DBSCAN 作为密度聚类最常见的方法之一，其应用也越来越多，很多其他的算法与之结合是未来该算法甚至整个聚类研究的一个方向，目前已知的 DBSCAN 和层次聚类有很多的交叉应用。其次，对于 MinPts 和 e 的选择一直是 DBSCAN 研究的关键。