1.介绍

DBSCAN即Density - Based Spatial Clustering of Applications with Noise（具有噪声的基于密度的空间聚类应用）

它是一种重要的聚类算法，主要依据数据点的密度来进行聚类，并且能够有效处理数据集中的噪声点。

2.概念

需要指定的参数

• **领域半径$\epsilon$：**距离数据点的距离小于等于领域半径的数据点，都属于其领域内
• 最小点数$MinPts$: 领域内需要的点数的阈值

其他

• 直接密度可达（Directly Density - Reachable）：如果点$q$在点$p$的领域半径内，并且点p领域内至少包含$MinPts$个点，那么$q$是从$p$直接密度可达的。
• 密度可达/密度相连（Density - Reachable）: 如果存在一个点链$p_1, p_2,\cdots, p_n$，其中$p_1 = p$，$p_n = q$，且对于$1\leq i\leq n - 1$，$p_{i + 1}$是从$p_i$直接密度可达的，那么称$q$是从$p$密度可达的。
• 边界点
• 噪声点/离群点

3.算法步骤

步骤一：确定参数

首先需要确定两个关键参数，即邻域半径$\epsilon$（Eps）和最小点数$MinPts$。这两个参数的选择会对聚类结果产生重要影响。

步骤二：标记点的类型

对于数据集中的每个点$p$，计算其$\epsilon$邻域内的点的数量。

如果点$p$的$\epsilon$邻域内的点数小于$MinPts$，则将$p$标记为噪声点。

如果点$p$的$\epsilon$邻域内的点数大于等于$MinPts$，则将$p$标记为核心点。

步骤三：扩展聚类

随机选择一个未处理的核心点$p$，创建一个新的聚类$C$，并将$p$放入$C$中。

对于从$p$密度可达的所有点$q$，将$q$也放入聚类$C$中。这个过程可以通过递归地寻找密度可达的点来实现。（这个过程可以把一些噪声点重新归到某个簇当中）

重复这个过程，直到所有的核心点都被处理过。

4.如何确定$\epsilon$和$MinPts$的值

半径$\epsilon$

可以通过K距离（有点像k-means的肘方法）来确定，找突变点

• k - 近邻距离图（k - NN graph）：计算每个数据点到其第 k 个最近邻点的距离，然后绘制这些距离的排序后的曲线。通常选择一个合适的 k 值（如 k = 4 或 k = 5），观察距离曲线的 “膝盖点”（knee - point）。这个膝盖点对应的距离值可以作为领域半径的一个合理估计。在距离曲线开始急剧上升之前的平缓部分对应的距离，大致就是数据点开始形成不同密度区域的边界，这个边界距离可作为 Eps 的参考。

MinPts

取之前计算用的k值，一般取的小一些

5.优缺点

优点

• 能够发现任意形状的簇：与K - means等算法不同，DBSCAN不受限于发现球形的簇，它可以有效地发现各种形状（如线性、环形、凹形等）的聚类结构。
• 对噪声点有较好的识别能力：能够自然地将噪声点识别出来，而不需要像其他一些算法那样预先设定噪声的比例或者手动去除噪声。
• 不需要预先指定聚类的数量：聚类的数量是由数据本身的密度分布决定的，而不是像K - means算法那样需要预先确定聚类个数。

缺点

• 对参数敏感：参数$\epsilon$和$MinPts$的选择对聚类结果影响很大。如果参数选择不当，可能会导致聚类结果过度合并（$\epsilon$过大或$MinPts$过小）或者产生过多的小聚类（$\epsilon$过小或$MinPts$过大）。
• 计算复杂度较高：在计算点之间的密度关系时，特别是对于大规模数据集，需要计算每个点的邻域内的点数，计算量较大，可能会导致算法效率较低。
• 高维数据处理比较困难：可以降维处理

6.应用场景

空间数据分析：例如在地理信息系统（GIS）中，分析城市、森林等地理对象的分布模式，识别不同的区域或群体。

图像分割：可以用于将图像中的像素点根据其密度特征进行聚类，从而实现图像分割，将图像划分为不同的区域。

异常检测：通过识别数据集中的噪声点来发现异常数据，在网络安全、金融风险监测等领域有广泛应用。