DBSCAN算法理解

1.DBSCAN简介

DBSCAN（Density-Based Special Clustering of Application with Noise），它是基于密度聚类算法，密度可以理解为样本点的紧密程度，而紧密度的衡量则需要使用半径和最小样本量进行评估，如果在指定的半径内，实际样本量超过给定的最小样本量阈值，则认为是密度高的对象。DBSCAN密度聚类算法可以非常方便的发现样本集中的异常点，故通常可以使用该算法实现异常点的检测。它可以发现任何形状的样本簇，并且具有很强的抗噪声能力。

1.1 密度聚类相关的概念

• 点的 ϵ \epsilon ϵ领域：在某点 p p p处，给定其半径 ϵ \epsilon ϵ后，所得到的覆盖区域。

• 核心对象：对于给定的最少样本量 M i n P t s MinPts MinPts而言，如果某点 p p p的 ϵ \epsilon ϵ领域内至少包括 M i n P t s MinPts MinPts个样本点，则点 p p p就为核心对象。

• 直接密度可达：假设点 p p p为核心对象，且在点 p p p的 ϵ \epsilon ϵ领域内存在点 q q q，则从点 p p p出发到点 q q q是直接密度可达的。

• 密度可达：假设存在一系列的对象链 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1​,p2​,...,pn​，如果 p i p_i pi​是关于半径 ϵ \epsilon ϵ和最少样本点 M i n P t s MinPts MinPts的直接密度可达 p i + 1 ( i = 1 , 2 , . . . , n ) p_{i+1}(i=1,2,...,n) pi+1​(i=1,2,...,n)，则 p 1 p_1 p1​密度可达 p n p_n pn​。意思就是，p1、p2、p3、p4都是核心对象且它们是直接密度可达的，这时候p4的领域内的直接密度可达的点p5，对p1、p2、p3来说都是密度可达的。

• 密度相连：假设点o为核心对象，从点o出发得到两个密度可达点p和点q，则称点p和点q是密度相连的。

• 聚类的簇：簇包含了最大的密度相连所构成的样本点。

• 边界点：假设点p为核心对象，在其领域内包含了点b，如果点b为非核心对象，则称其为点p的边界点。

• 异常点：不属于任何簇的样本点。

1.2 密度聚类的步骤

密度聚类的过程有点像“贪吃蛇”，从某个点出发，不停地向外扩张，直到获得一个最大的密度相连，进而形成一个样本簇。详细步骤如下：

（1）为密度聚类算法设置一个合理的半径 ϵ \epsilon ϵ以及 ϵ \epsilon ϵ领域内所包含的最少样本量 M i n P t s MinPts MinPts。

（2）从数据集中随机挑选一个样本点 p p p，检验其在 ϵ \epsilon ϵ领域内是否包含指定的最少样本量，如果包含就将其定性为核心对象，并构成一个簇 C C C；否则，重现挑选一个样本点。

（3）对于核心对象 p p p所覆盖的其他样本点 q q q，如果点 q q q对应的 ϵ \epsilon ϵ领域内仍然包含最少样本量 M i n P t s MinPts MinPts，就将其覆盖的样本点统统归于簇 C C C。

（4）重复步骤（3），将最大的密度相连所包含的样本点聚为一类，形成一个大簇。

（5）完成步骤（4）后，重现回到步骤（2），并重复步骤（3）和（4），直到没有新的样本点可以生成新簇时算法结束。

1.3 算法实现

在Python中可以直接调用sklearn子模块cluster中的DBSCAN类实现，该类的语法和参数意义如下：

cluster.DBSCAN(eps=0.5,min_samples=5,metric='educlidean',metric_params=None,algorithm='auto',leaf_size=30,
				p=None,n_jobs=1)

• eps:用于设置密度聚类中的 ϵ \epsilon ϵ领域，即半径，默认为0.5。
• min_samples:用于设置 ϵ \epsilon ϵ领域内最少的样本量，默认为5。
• metirc:用于指定计算点之间距离的方法，默认为欧式距离。
• metric_params:用于指定metirc所对应的其他参数值。
• algorithm:在计算点之间距离的过程中，用于指定搜寻最近邻样本点的算法。默认为’auto’，表示密度聚类谁自动选择一个合适的搜寻方法。如果为’ball_tree’，则表示使用球树搜寻最近邻。如果为’kd_tree’，则表示使用K-D树搜寻最近邻。
• leaf_size:当参数algorithm为”ball_tree“或”kd_tree“时，用于指定书的叶子节点中所包含的最多样本量，默认为30；该参数会影响搜寻树的构建和搜寻最近邻的速度。
• p:当参数"metric"为闵可夫斯基距离时，p=1，表示计算点之间的曼哈顿距离；p=2，表示计算点之间的欧氏距离；该参数的默认值为2。
• n_jobs:用于设置密度聚类算法并行计算所需的CPU数量，默认为1，表示仅使用1个CPU运行参数，即不使用并行运算功能。

在DBSCAN类中，参数eps和min_samples需要同时调参，即通常会指定几个候选值，并从候选值中挑选出合理的阈值。在参数eps固定的情况下，参数min_samples越大，所形成的核心对象越少，往往会误判出许多异常点，聚成的簇数目也会增加。反之，会产生大量的核心对象，导致聚成的簇数据减少。在参数min_samples固定的情况下，参数eps越大，就会导致越多的点落入到 ϵ \epsilon ϵ领域内，进而使得核心对象越多，最终使得据称的簇数目减少；反之，会导致核心对象大量减少、最终聚成的簇数目增多。在参数eps和min_samples不合理的情况下，簇数目的增加或减少往往都是错误的。

Kmeans和密度聚类对比：

Kmeans聚类的短板是无法对非球形的簇进行聚类，同时也非常容易受到极端值的影响，而密度聚类则可以弥补它的缺点。

1.4 最近邻搜寻算法

1.4.1 KD树

1.4.2 球形树

1.5 相关知识点总结

1.什么是DBSCAN

DBSCAN是一种基于密度的空间聚类算法，它不需要定义簇的个数，而是将具有足够高密度的区域分为簇，并在有噪声的数据中发现任意形状的簇，在此算法中将簇定义为密度相连的点的最大集合。

这类密度算法一般假定类型可以通过样本分布的紧密程度决定，同一类别的样本，他们之间是紧密相连，也就是说在该类别任意样本的周围不远处一定有同类别的样本存在。通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们最终就得到了所有聚类类别的结果。

2. 优缺点

优点：

可以对任意形状的稠密数据集进行聚类，而Kmeans一般只适用于凸（球形）数据集。

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

聚类效果不像Kmeans受初始值的影响。

缺点：

不适用于样本集的密度不均匀，聚类间距相差很大，这时聚类效果较差。

样本集数据量大时，聚类收敛的时间长，此时可以对搜素最近邻时建立的KD树或者球形树进行规模限制。

调参相对Kmeans相对复杂，需要对距离阈值和领域最少样本数阈值进行联合调参，不同的参数组合对最后的聚类效果影响很大。

3. Kmeans和OPTICS的区别

参考链接

DBSCAN密度聚类算法