DBSCAN聚类算法 — 理论 + 图解 + 代码

谁践踏了优雅 2023-02-11 08:49 12阅读 0赞

**前期回顾**

[K-Means算法 — 算法原理、质心计算、距离度量、聚类效果评价及优缺点][K-Means_ _]

--------------------

一、前言  
二、DBSCAN聚类算法  
三、参数选择  
四、DBSCAN算法迭代可视化展示  
五、常用的评估方法：轮廓系数  
六、用Python实现DBSCAN聚类算法

## 一、前言 ##

**DBSCAN**（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种**基于密度**的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

# 二、DBSCAN聚类算法 #

文字看不懂看下面这个图。下面这些点是分布在样本空间的众多样本，现在我们的目标是把这些在样本空间中距离相近的聚成一类。我们发现A点附近的点密度较大，红色的圆圈根据**一定的规则在这里滚啊滚**，最终收纳了A附近的5个点，标记为红色也就是定为同一个簇。其它没有被收纳的根据一样的规则成簇。**（形象来说，我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N）。**

![70][]

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

![70 1][]

# 三、参数选择 #

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

*  **半径：**半径是最难指定的 ，大了，圈住的就多了，簇的个数就少了；反之，簇的个数就多了，这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r，也就是要**找到突变点**，比如：

![70 2][]

以上虽然是一个可取的方式，但是有时候比较麻烦 ，大部分还是都试一试进行观察，用k距离需要做大量实验来观察，很难一次性把这些值都选准。

*  MinPts:这个参数就是圈住的点的个数，也相当于是一个密度，一般这个值都是偏小一些，然后进行多次尝试

# 四、DBSCAN算法迭代可视化展示 #

国外有一个特别有意思的网站：[https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/][https_www.naftaliharris.com_blog_visualizing-dbscan-clustering]

![70 3][]

它可以把我们DBSCAN的迭代过程**动态图**画出来

![70 4][]

设置好参数，点击GO! 就开始聚类了！

![70 5][]

直接跳到最后看一下DBSCAN的聚类结果，如下：

![70 6][]

如果minPoints参数设置再大一点，那么这个笑脸可能会更好看。没有颜色标注的就是圈不到的样本点，也就是离群点，DBSCAN聚类算法在检测离群点的任务上也有较好的效果。如果是传统的Kmeans聚类，我们也来看一下效果：

![70 7][]

是不是好丑，这完美的体现出来DBSCAN算法基于密度聚类的优势了啊.

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

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

![70 8][]**ji**

1.  计算样本i到同簇其它样本的平均距离ai。ai越小，说明样本i越应该被聚类到该簇（将ai称为样本i到簇内不相似度）。
2.  计算样本i到其它某簇Cj的所有样本的平均距离bij，称为样本i与簇Cj的不相似度。定义为样本i的簇间不相似度：bi=min(bi1,bi2,...,bik2)

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

#  #

# 六、用Python实现DBSCAN聚类算法 #

import pandas as pd
    # 导入数据
    beer = pd.read_csv('data.txt', sep=' ')
    print(beer)

输出结果：

![70 9][]

from sklearn.cluster import DBSCAN
     
    X = beer[["calories","sodium","alcohol","cost"]]
    # 设置半径为10，最小样本量为2，建模
    db = DBSCAN(eps=10, min_samples=2).fit(X)
     
    labels = db.labels_ 
    beer['cluster_db'] = labels  # 在数据集最后一列加上经过DBSCAN聚类后的结果
    beer.sort_values('cluster_db')
     
    # 注：cluster列是kmeans聚成3类的结果；cluster2列是kmeans聚类成2类的结果；scaled_cluster列是kmeans聚类成3类的结果（经过了数据标准化）

![70 10][]

# 查看根据DBSCAN聚类后的分组统计结果（均值）
    print(beer.groupby('cluster_db').mean())

![70 11][]

# 画出在不同两个指标下样本的分布情况
    print(pd.scatter_matrix(X, c=colors[beer.cluster_db], figsize=(10,10), s=100))

![70 12][]

# 我们可以从上面这个图里观察聚类效果的好坏，但是当数据量很大，或者指标很多的时候，观察起来就会非常麻烦。
    from sklearn import metrics  
    # 就是下面这个函数可以计算轮廓系数（sklearn真是一个强大的包）
    score = metrics.silhouette_score(X,beer.cluster_db) 
    print(score)

**转载自博客**[DBSCAN聚类算法——机器学习（理论+图解+python代码）][DBSCAN_python]

**相关博客**

\[1\]. [理解DBSCAN密度聚类算法][DBSCAN]  
\[2\]. [TfidfTransformer和 CountVectorizer的使用][TfidfTransformer_ CountVectorizer]

[K-Means_ _]: https://blog.csdn.net/weixin_43283397/article/details/105241340
[70]: https://img-blog.csdn.net/2018072516361747?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180718113640485?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180725171205576?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[https_www.naftaliharris.com_blog_visualizing-dbscan-clustering]: https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
[70 3]: https://img-blog.csdn.net/20180725172352525?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: https://img-blog.csdn.net/20180725172828684?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 5]: https://img-blog.csdn.net/20180725173044386?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 6]: https://img-blog.csdn.net/20180725173312977?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 7]: https://img-blog.csdn.net/20180725174037783?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 8]: https://img-blog.csdn.net/20180726102042552?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 9]: https://img-blog.csdn.net/20180726095536459?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 10]: https://img-blog.csdn.net/2018072609505040?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 11]: https://img-blog.csdn.net/20180726100826602?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 12]: https://img-blog.csdn.net/2018072611251564?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWNoYV9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[DBSCAN_python]: https://blog.csdn.net/huacha__/article/details/81094891?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159013261319195239848128%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=159013261319195239848128&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v28-2-81094891.first_rank_v2_rank_v28&utm_term=dbscan%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95
[DBSCAN]: https://blog.csdn.net/weixin_42280517/article/details/81389347?ops_request_misc=%7B%22request_id%22:%22158166938119725222416025%22,%22scm%22:%2220140713.130056874..%22%7D&request_id=158166938119725222416025&biz_id=0&utm_source=distribute.pc_search_result.none-task
[TfidfTransformer_ CountVectorizer]: https://blog.csdn.net/a857553315/article/details/103828413?ops_request_misc=%7B%22request_id%22:%22158167329519725256756972%22,%22scm%22:%2220140713.130056874..%22%7D&request_id=158167329519725256756972&biz_id=0&utm_source=distribute.pc_search_result.none-task