本文主要参考 YouTube 视频 Clustering with DBSCAN, Clearly Explained!!!

---

介绍

说起聚类算法， 一般面试中95% 考到的都是 KMeans。 KMeans 确实是聚类算法中的workhorse， 但是他也有自身的局限。 DBSCAN 也是机器学习中的一个常用聚类算法， 因为算法和KMeans 差距较大， 往往可以解决一些 KMeans 无法解决的问题。

比如， 下面一个数据集用 KMeans 分类， 很可能结果是

KMeans 结果

而直观上， 我们期待的结果是：

DBSCAN 结果

算法

1. 发现Core 点

1. 随机选取一个点, 在半径 内发现相邻的点 , 如果半径内其他点数量 那么这个点就记为 Core 点。

• 是超参数，需要用户指定
• 是超参数，需要用户指定

如果 下图中， 红色点是 Core 点， 而黑色点不是 Core 点, 因为它们 。

找Core 点

2. 着色

1. 任意找一个点

任意找一个 Core 点，将其着色，假设将其设为绿色。

image.png

2. 附近Core 点扩散

把颜色扩散到所有周围的Core 点， 然后被染色的Core 点再继续扩散给其他Core 点，注意， 邻接的非Core 点再这步不被着色。

image.png

3. 附近非Core 点扩散

对于第二步中被染色的Core 向他们附近的所有非Core 点扩散。

非Core 点会被染色， 但是它们没有传染能力， 不能把颜色再向外扩散。

向非Core 点扩散

当所有可以染色的点都被染色以后， 这个Cluster 就完成了。如果此时还有 Core 点， 那他们就属于其他 Cluster， 重复前面的步骤， 继续分类。

完成染色

3. 完成

当所有Core 都被染色后， Cluster 就完成了。 注意， 有些点可能最终不会被染色， 那么它们就是 Outlier.

KMeans 所有点都会被归类， DBSCAN 会产生Outlier

完成所有分类