狗都能看懂的DBSCAN算法详解

DBSCAN简介

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种典型的无监督聚类算法。和K-means相比，不需要指定簇的个数，可以应用于各种非凸形状的数据，能够有效分离异常点，因此也常用于异常检测。

DBSCAN算法流程

DBSCAN通过检查数据集中的点的邻域来形成簇。其核心思想是密度可达性，即如果一个点在某个密度阈值内有足够多的邻居，它就会与这些邻居形成一个簇。具体地，DBSCAN依赖于两个主要参数：

1. $ϵ$：定义一个点的邻域的半径。
2. MinPts：一个点在其邻域内必须包含的最少点数（包括点本身），以便被视为一个核心点

运行机制

DBSCAN算法的运行步骤如下：

1. 标记所有点为未访问。
2. 随机选择一个未访问的点P，并将其标记为已访问。
3. 检查P的ε邻域：
   • 如果P的$ϵ$邻域内的点数大于或等于MinPts，则P被视为核心点，并以P为中心创建一个新簇。然后递归地将P的所有邻居也加入该簇。
   • 如果P的$ϵ$邻域内的点数小于MinPts，则P被标记为噪声点（后续可能会被归入其他簇）。
4. 重复步骤2和3，直到所有点都被访问过。

举个实例

现设$ϵ=1$，$MinPts=3$，即半径为1的情况下，需要有3个点在领域内才算是核心点。

1. 任意选择一个点A，其半径圈内有3个符合条件的点，所以A是核心点，并标记为已访问的状态
2. 在A的半径范围内任意选择一个点，继续进行半径圈扫描，即重复1的操作
3. 经过n轮迭代之后，到达了B点，B点为圆心的范围内只有一个符合条件的点，虽然它和其他红色的点都是分到一个类里，但它是属于边界点而非核心点
4. 再经过m轮迭代之后，红色点和黄色点都遍历完成后，我们只剩下N点没有访问过了
5. 此时选择N点，它的半径圈内并没有任何点，它将被我们标记为异常点/噪声点

这时候我们提出几个点的名称定义：

• 核心点：若点P的$ϵ$半径内至少包含$MinPts$个样本（包括样本P)，那么点P称核心点
• 边界点：若点P在某个核心点P的半径范围内，但其半径范围内没有$MinPts$个样本（包括样本P)，则称为边界点
• 噪声点：若点P既不属于核心点，也不属于边界点，则称该点位噪声点

根据点的分布情况，我们还可以给出几个概念：

• 密度直达：一个点P1处在点P2的领域内，且P2为核心点，则称P1由P2密度直达
• 密度可达：一个点P1处在点P2的领域内，且P1和P2均为核心点，则称P1的领域点由P2密度可达
• 密度相连：如果P1和P2都不是核心点，且P1和P2都在一个簇内，则称P1和P2密度相连

DBSCAN算法特点

优点

• 可以对任意形状的数据进行聚类，不需要指定分类的数量
• 对异常点不敏感，可以找出独立的点
• 聚类结果稳定，即算法选择哪个点都可以，最终聚类的结果一定是一致的

缺点

• 样本数量较多时，时间消耗会变多，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进
• 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合

DBSCAN参数选取技巧

$ϵ$的选取：找突变点

给定一组点集P(P1、P2…Pn)，计算P1到其他所有点的距离，从小到大排序，例如P1到其他点的距离为：

1. 0.1
2. 0.11
3. 0.12
4. 0.3
5. 0.35

那么由此可看出，从0.12之后就是比较大的距离变动，因此可以选0.12作为距离阈值。当然实际的选取需要结合多个点集的距离结果

MinPts的选取

视业务情况而定，但一般从小的开始选取，但不要小过2，如果MinPts=1的情况，那么就找不到异常点了