1. DBSCAN简介
- 密度聚类 （亦称基于密度的聚类算法，density-based clustering）算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本的密度的角度来考察样本之间的可连接性，并基于可连接性不断扩展聚类簇已获得最终的聚类结果。
-
DBSCAN是一种著名的密度聚类算法，它基于一组“领域”参数
来刻画样本分布的紧密程度。 和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。
- 凸样本集定义： 简单来说，数据集D中任意两点的连线上的点，也会在数据集D内，那么数据集D就是一个凸集。如下图所示就是一个非凸样本集，Kmeans效果表现非常差。
Kmeans聚类和DBSCAN聚类效果对比.png
2. DBSCAN基本概念
对于给定的数据集，定义以下几个基本概念：
-领域： 对
, 其
中与
的距离不大于
；
- 核心对象（core object）： 若
，则
- 密度直达（directly density-reachable）： 若
的
- 密度可达（density-reachable）： 对
其中
且
由
密度直达，则称
- 密度相连（density-connected）： 对
使得
-
下图中蓝色点为核心对象，假设MinPts=3
DBSCAN基本概念举例.png
3. DBSCAN核心思想
- DBSCAN将“簇”定义为：由密度可达关系导出的最大的密度相连样本集合。DBSCAN算法首先任选数据集中的一个核心对象为“种子”，再由此出发确定相应的聚类簇。首先根据领域参数
找出所有核心对象，然后以任意核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。
DBSCAN算法流程.png
- 首先找到所有的核心对象（Core Point）集合，下图的红色点为核心对象；
核心对象举例.png
所有的核心对象.png
所有的非核心对象.png
- 其次，随机挑选一个核心对象，以此对象出发由密度可达关系导出最大的密度相连样本集合。
随机选择一个核心对象.png
找到密度相连样本集合.png
非核心对象处理.png
离群点.png
特殊case的处理.png
4. sklearn中使用DBSCAN聚类算法
参考文档：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
sklean dbscan算法.png
参考资料
- Clustering with DBSCAN, Clearly Explained!!! 【视频教程】
https://www.youtube.com/watch?v=RDZUdRSDOok - 【math】凸数据集 & 非凸数据集
https://blog.csdn.net/qq_36056219/article/details/122810081 - 《机器学习》 - 周志华 9.5节 密度聚类
- DBSCAN Clustering Algorithm in Machine Learning
https://www.kdnuggets.com/2020/04/dbscan-clustering-algorithm-machine-learning.html
刘建平Pinard博客
- DBSCAN密度聚类算法 https://www.cnblogs.com/pinard/p/6208966.html
- 用scikit-learn学习DBSCAN聚类 https://www.cnblogs.com/pinard/p/6217852.html
