时间：2021-07-01 10:21:17 帮助过：13人阅读
假设我的样本集是D=(x1,x2,...,xm)(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下：
1） ??-邻域：对于xj∈Dxj∈D，其??-邻域包含样本集D中与xjxj的距离不大于??的子样本集，即N?(xj)={xi∈D|distance(xi,xj)≤?}N?(xj)={xi∈D|distance(xi,xj)≤?}, 这个子样本集的个数记为|N?(xj)||N?(xj)|
2) 核心对象：对于任一样本xj∈Dxj∈D，如果其??-邻域对应的N?(xj)N?(xj)至少包含MinPts个样本，即如果|N?(xj)|≥MinPts|N?(xj)|≥MinPts，则xjxj是核心对象。
3）密度直达：如果xixi位于xjxj的??-邻域中，且xjxj是核心对象，则称xixi由xjxj密度直达。注意反之不一定成立，即此时不能说xjxj由xixi密度直达, 除非且xixi也是核心对象。
4）密度可达：对于xixi和xjxj,如果存在样本样本序列p1,p2,...,pTp1,p2,...,pT,满足p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直达，则称xjxj由xixi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT?1p1,p2,...,pT?1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
5）密度相连：对于xixi和xjxj,如果存在核心对象样本xkxk，使xixi和xjxj均由xkxk密度可达，则称xixi和xjxj密度相连。注意密度相连关系是满足对称性的。
从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其??-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的??-邻域内所有的样本相互都是密度相连的。
有了上述定义，DBSCAN的聚类定义就简单了。
DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的??-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的??-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的??-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。
第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。
第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。如果大家对于最近邻的思想，距离度量，KD树和球树不熟悉，建议参考之前写的另一篇文章K近邻法(KNN)原理小结。
第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于??，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。
下面我们对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′)∩Γ, 更新当前簇样本集合