5.2.3 DBSCAN密度聚类算法
DBSCAN（density-based spatial clustering of applications with noise，具有噪声的基于密度的聚类方法）是一种典型的密度聚类算法，与K-Means、BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既适用于凸样本集，也适用于非凸样本集。
1.密度聚类原理
DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，它们之间是紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。
通过将紧密相连的样本划为一类，就可得到一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，就可得到最终的所有聚类类别结果。
2.DBSCAN密度定义
DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数（ε，MinPts）用来描述邻域的样本分布紧密程度。其中，ε描述了某一样本的邻域距离阈值，MinPts描述了与某一样本的距离为ε的邻域中包含样本个数的阈值。
假设样本集D=｛x1，x2，…，xm｝，则DBSCAN具体的密度描述定义如下。
·ε-邻域：对于xj∈D，其ε-邻域包含样本集D中与xj的距离不大于ε的子样本集，即Nε（xj）=｛xi∈D|distance（xi，xj）≤ε｝，这个子样本集的个数记为|Nε（xj）|；
·核心对象：对于任一样本xj∈D，如果其ε-邻域对应的Nε（xj）至少包含MinPts个样本，即如果|Nε（xj）|≥MinPts，则xj是核心对象；
·密度直达：如果xi位于xj的ε-邻域中，且xj是核心对象，则称xi由xj密度直达。
·密度可达：对于xi和xj，如果存在样本序列p1，p2，…，pT，满足p1=xi，pT=xj，且pT+1由pT密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1，p2，…，pT-1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意：密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
·密度相连：对于xi和xj，如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意：密度相连关系满足对称性。
3.DBSCAN密度聚类思想
DBSCAN的聚类定义为由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。这个DBSCAN的簇可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他非核心对象样本都在这个核心对象的ε-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的e-邻域中一定有一个其他核心对象，否则这两个核心对象无法密度可达。这些核心对象的ε-邻域里所有的样本的集合组成一个DBSCAN聚类簇。
那么怎样才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
4.DBSCAN聚类算法
下面介绍DBSCAN聚类算法的流程。
输入：样本集D=｛x1，x2，…，xm｝，邻域参数（ε，MinPts），样本距离度量方式；
输出：簇划分C。
（1）初始化核心对象集合Ω=∅，初始化聚类簇数k=0，初始化未访问样本集合Γ=D，簇划分C=∅。
（2）对于j=1，2，…，m，按下面的步骤找出所有的核心对象：(https://www.daowen.com)
①通过距离度量方式，找到样本xj的ε-邻域子样本集Nε（xj）；
②如果子样本集样本个数满足|Nε（xj）|≥MinPts，将样本xj加入核心对象样本集合：Ω=ΩU｛xj｝。
（3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤（4）。
（4）在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列Ωcur=｛o｝，初始化类别序号k=k+1，初始化当前簇样本集合Ck=｛o｝，更新未访问样本集合Γ=Γ-｛o｝。
（5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕，更新簇划分C=｛C1，C2，…，Ck｝，更新核心对象集合Ω=Ω-Ck，转入步骤（3）；否则更新核心对象集合Ω=Ω-Ck。
（6）在当前簇核心对象队列Ωcur中取出一个核心对象o'，通过邻域距离阈值ε找出所有的e-邻域子样本集Nε（o'），令Δ=Nε（o'）∩Γ，更新当前簇样本集合Ck=Ck∪Δ，更新未访问样本集合Γ=Γ-Δ，更新Ωcur=Ωcur ∪（Δ ∩Ω）-o'，转入步骤（5）。
输出结果为
簇划分C=｛C1，C2，…，Ck｝
5.DBSCAN小结
与传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用在凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点与BIRCH算法类似。
那么什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
下面对DBSCAN算法的优缺点做一个总结。
DBSCAN的主要优点有：
（1）可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
（2）可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
（3）聚类结果没有偏倚，相对地，K-Means之类的聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有：
（1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
（2）如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
（3）相对于传统的K-Means之类的聚类算法，调参要复杂些，主要需要对距离阈值ε、邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。