【机器学习】DBSCAN密度聚类算法（理论 + 图解）

雨点打透心脏的1/2处 2023-09-27 14:44 112阅读 0赞

#### 文章目录 ####

*  一、前言
 *  二、DBSCAN聚类算法
 *  三、DBSCAN算法步骤
 *  四、算法的理解
 *  五、常用评估方法：轮廓系数

## 一、前言 ##

之前学聚类算法的时候，有层次聚类、系统聚类、K-means聚类、K中心聚类，最后呢，被DBSCAN聚类算法迷上了。

为什么呢，首先它可以发现任何形状的簇，其次我认为它的理论也是比较简单易懂的。接下来的文章里会详细解读一下DBSCAN密度聚类算法。

下面贴上它的官方解释：

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。

该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

## 二、DBSCAN聚类算法 ##

DBSCAN是一种基于密度的聚类算法，可以根据样本分布的紧密程度决定，同一类别的样本之间是紧密相连的，不同类别样本联系是比较少的。

DBSCAN算法需要用到参数：

*  eps( ϵ \\epsilon ϵ)：一种距离度量，用于定位任何点的邻域内的点
 *  minPts：聚类在一起的点的最小数目，超过这一阈值才算是一个族群

DBSCAN聚类完成后会产生三种类型的点：

*  核心点（Core）——该点表示至少有 m m m个点在距离n的范围内
 *  边界点（Border） ——该点表示在距离 n n n处至少有一个核心
 *  噪声点（Noise） ——它既不是核心点也不是边界点。并且它在距离自身 n n n的范围内有不到 m m m个点

![在这里插入图片描述][2f6da741e0cd41c68e2c4f1763f5eb88.png]

## 三、DBSCAN算法步骤 ##

1.  算法通过任意选取数据集中的一个点（直到所有的点都访问到）来运行
2.  如果在该点的“ε”半径范围内至少存在“minPoint”点，那么认为所有这些点都属于同一个聚类
3.  通过递归地重复步骤1、步骤2 对每个相邻点的邻域计算来扩展聚类

## 四、算法的理解 ##

![在这里插入图片描述][9c8cc1a6fe3542b4917d1f973c9d8e28.png]

上面这些点是分布在样本空间的众多样本，现在我们的目标是把这些在样本空间中距离相近的聚成一类。

我们发现 A A A点附近的点密度较大，红色的圆圈根据一定的规则在这里滚啊滚，最终收纳了 A A A附近的5个点，标记为红色也就是定为同一个簇。

其它没有被收纳的根据一样的规则成簇。

形象来说，我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。

等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如 A A A，停下来的那个点为边界点，如 B B B、 C C C，没得滚的那个点为离群点，如 N N N）。

基于密度这点有什么好处呢？

我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。

于是就思考，样本密度大的成一类呗，这就是DBSCAN聚类算法。

上面提到了红色圆圈滚啊滚的过程，这个过程就包括了DBSCAN算法的两个参数，这两个参数比较难指定，公认的指定方法简单说一下：

*  `半径：`半径是最难指定的 ，大了，圈住的就多了，簇的个数就少了；反之，簇的个数就多了，这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r，也就是要找到突变点，比如：  
    ![在这里插入图片描述][77b9b8d2e4b74edb9692a285fe8bc651.png]  
    以上虽然是一个可取的方式，但是有时候比较麻烦 ，大部分还是都试一试进行观察，用 k k k距离需要做大量实验来观察，很难一次性把这些值都选准。
 *  `MinPts：`这个参数就是圈住的点的个数，也相当于是一个密度，一般这个值都是偏小一些，然后进行多次尝试

## 五、常用评估方法：轮廓系数 ##

这里提一下聚类算法中最常用的评估方法——轮廓系数（Silhouette Coefficient）：

![在这里插入图片描述][907a5d1f568d4b62ab604b27f8713cbe.png]

*  计算样本i到同簇其它样本到平均距离 a i a\_i ai， a i a\_i ai越小，说明样本i越应该被聚类到该簇（将 a i a\_i ai称为样本i到簇内不相似度）；
 *  计算样本 i i i到其它某簇 C j C\_j Cj的所有样本的平均距离 b i j b\_\{ij\} bij，称为样本 i i i与簇 C j C\_j Cj的不相似度。定义为样本i的簇间不相似度： b i = min ⁡ ( b i 1 , b i 2 , ⋯   , b i k 2 ) b\_i=\\min(b\_\{i1\},b\_\{i2\},\\cdots,b\_\{ik2\}) bi=min(bi1,bi2,⋯,bik2)；

说明：

*   s i s\_i si接近1，则说明样本i聚类合理；
 *   s i s\_i si接近-1，则说明样本i更应该分类到另外的簇；
 *  若 s i s\_i si近似为0，则说明样本i在两个簇的边界上。

[2f6da741e0cd41c68e2c4f1763f5eb88.png]: https://img-blog.csdnimg.cn/2f6da741e0cd41c68e2c4f1763f5eb88.png
[9c8cc1a6fe3542b4917d1f973c9d8e28.png]: https://img-blog.csdnimg.cn/9c8cc1a6fe3542b4917d1f973c9d8e28.png
[77b9b8d2e4b74edb9692a285fe8bc651.png]: https://img-blog.csdnimg.cn/77b9b8d2e4b74edb9692a285fe8bc651.png
[907a5d1f568d4b62ab604b27f8713cbe.png]: https://img-blog.csdnimg.cn/907a5d1f568d4b62ab604b27f8713cbe.png