DBSCAN密度聚类 | 彩潭有鲤的札记

type

status

date

slug

summary

原理

密度聚类原理

DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。

通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，就得到了最终的所有聚类类别结果。

DBSCAN密度定义

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数( ，MinPts)用来描述邻域的样本分布紧密程度。其中描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为的邻域中样本个数的阈值。

假设样本集是，则DBSCAN具体的密度描述定义如下：

-邻域：对于，其 -邻域包含样本集中与的距离不大于的子样本集，即，这个子样本集的个数记为

核心对象：对于任一样本，如果其 -邻域对应的至少包含MinPts个样本，即如果，则是核心对象

密度直达：如果位于的 -邻域中，且是核心对象，则称由密度直达。注意反之不一定成立，即此时不能说由密度直达,，除非且也是核心对象

密度可达：对于和，如果存在样本样本序列，满足，且由密度直达，则称由密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。

密度相连：对于和，如果存在核心对象样本，使和均由密度可达，则称和密度相连。注意密度相连关系是满足对称性的。

从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 -邻域内所有的样本相互都是密度相连的

DBSCAN密度聚类思想

DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为最终聚类的一个类别，或者说一个簇

这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的 -邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的 -邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

基本上这就是DBSCAN算法的主要内容了，但是还是有三个问题没有考虑：

一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中一般将这些样本点标记为噪音点

距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻

某些样本可能到两个核心对象的距离都小于，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法

DBSCAN聚类算法

输入：样本集，邻域参数，样本距离度量方式

输出：簇划分

初始化核心对象集合，初始化聚类簇数，初始化未访问样本集合，簇划分

对于，按下面的步骤找出所有的核心对象：

通过距离度量方式，找到样本的 -邻域子样本集

如果子样本集样本个数满足，将样本加入核心对象样本集合：

如果核心对象集合，则算法结束，否则转入步骤4

在核心对象集合中，随机选择一个核心对象，初始化当前簇核心对象队列 , 初始化类别序号k=k+1，初始化当前簇样本集合 , 更新未访问样本集合

如果当前簇核心对象队列，则当前聚类簇生成完毕, 更新簇划分，更新核心对象集合，转入步骤3。否则更新核心对象集合

在当前簇核心对象队列中取出一个核心对象，通过邻域距离阈值找出所有的 -邻域子样本集，令 , 更新当前簇样本集合，更新未访问样本集合，更新，转入步骤5

输出结果为：簇划分

DBSCAN小结

和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似

什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。

DBSCAN的主要优点有：

可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集

可以在聚类的同时发现异常点，对数据集中的异常点不敏感

这里异常点不敏感的原因主要是大多数异常点都是离群点，由于我们有邻域参数的限制，会让这些异常点自己独立成为单独的一个簇。因此样本数极少的簇我们可以认定为是异常点将其排除。当然也有一些很特殊的情况，比如邻域参数选择的原因，导致异常点和正常点的距离不是足够远，可能会导致判断错误，将其加入正常簇。但大多数时候，只要邻域参数选择适当，是可以排除异常点的。

聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响

DBSCAN的主要缺点有：

如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合

如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进

调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响

代码

在scikit-learn中，DBSCAN算法类为sklearn.cluster.DBSCAN

DBSCAN类的重要参数也分为两类，一类是DBSCAN算法本身的参数，一类是最近邻度量的参数：

eps： DBSCAN算法参数，即 -邻域的距离阈值，和样本距离超过的样本点不在 -邻域内。默认值是0.5，一般需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的 -邻域，此时类别数可能会减少，反之则类别数可能会增大。

min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的 -邻域的样本数阈值。默认值是5。一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。

metric：最近邻距离度量参数。可以使用的距离度量较多，一般来说DBSCAN使用默认的欧式距离（即p=2的闵可夫斯基距离）就可以满足需求，可以使用的距离度量参数有：

欧式距离 “euclidean”:

曼哈顿距离 “manhattan”：
切比雪夫距离“chebyshev”:
闵可夫斯基距离 “minkowski”(默认参数):
带权重闵可夫斯基距离 “wminkowski”: 为特征权重
标准化欧式距离 “seuclidean”: 对各特征维度做了归一化以后的欧式距离。此时各样本特征维度的均值为0，方差为1
马氏距离“mahalanobis”：其中，为样本协方差矩阵的逆矩阵。当样本分布独立时， S为单位矩阵，此时马氏距离等同于欧式距离

algorithm：最近邻搜索算法参数，一共有4种可选输入，‘brute’对应蛮力实现，‘kd_tree’对应KD树实现，‘ball_tree’对应球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。

需要注意：如果输入样本特征是稀疏的时候，无论选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。一般情况使用默认的 ‘auto’就够了。如果数据量很大或者特征也很多，用"auto"建树时间可能会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论选择哪个算法最后实际运行的都是‘brute’

leaf_size：最近邻搜索算法参数，为使用KD树或者球树时，停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大，层数越深，建树时间越长，反之，则生成的KD树或者球树会小，层数较浅，建树时间较短。默认是30，因为这个值一般只影响算法的运行速度和使用内存大小，因此一般情况下可以不管它

p: 最近邻距离度量参数，只用于闵可夫斯基距离和带权重闵可夫斯基距离中值的选择，为曼哈顿距离，为欧式距离。