👇点击关注公众号👇
第一时间获取人工智能干货内容
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
具有噪声的基于密度的聚类方法是一种很典型的密度聚类算法。
和K-Means这种一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。
密度聚类原理
DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。
通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。
DBSCAN密度定义
我们已经定性描述了密度聚类的基本思想，我们看看DBSCAN是如何描述密度聚类的。DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。
其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
假设我的样本集是D=(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下：
1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|。
2）核心点：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心点。
如果判断A点是否为核心点，若设置的MinPts=6，因为A点的半径Eps内的点为7个大于了MinPts（包括A本身），|Nϵ(xj)|此时等于7。
所以A为核心点！没错，举个栗子之后发现：就是这么简单~
3）密度直达：如果xi位于xj的ϵ-邻域中，且xj是核心点，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达, 除非且xi也是核心点。
如下图，A点为核心点（因为B点在A点的Eps半径范围内（ϵ-邻域中），所以B点由A点密度直达。
思考：为何反之不一定呢？举个栗子？
4）密度可达：对于xi和xj,如果存在样本序列p1,p2,...,pT,满足p1=xi,pT=xj, 且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。
此时序列中的传递样本p1,p2,...,pT−1均为核心点，因为只有核心点才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
5）密度相连：对于xi和xj,如果存在核心点xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。
从下图中可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心点，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心点。所有核心点密度直达的样本在以红色核心点为中心的超球体（n维）内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心点组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。
有了上述定义，DBSCAN的聚类定义就简单了。
DBSCAN密度聚类思想
DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心点作为种子，然后找到所有这个核心点能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心点去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心点都有类别为止。
某些样本可能到两个核心点的距离都小于ϵ，但是这两个核心点由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？
一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。
DBSCAN聚类算法
输入：数据集D={x1，x2，x3，...，xN}，邻域参数（ϵ，MinPts）
输出：簇划分C={C1,C2,...,Ck}
算法步骤如下：
（1）初始化核心点集合为空集：Ω=空集
（2）寻找核心点：遍历所有的样本点xi, i=1,2,...,N，计算Nϵ(xi)，如果
|N(xi)|≥MinPts，则Ω=Ω ⋃{xi}
（3）迭代：以任一未访问过的核心点为出发点，找出有其密度可达的样本生成的聚类簇，直到所有的核心点都被访问为止。
sklearn中的DBSCAN主要参数：
eps：ϵ参数，用于确定邻域大小。
min_samples：MinPts参数，用于判断核心点。
DBSCAN小结
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。
那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
DBSCAN的主要优点
1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有
1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2） 如果样本集较大时，聚类收敛时间较长。
3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ
，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。
DBSCAN 的原理，你学会了么？
