在数据分析中，传统的聚类算法如 K-means 被广泛使用，但它存在几个明显的不足：
- 必须预先指定簇的数量：在实际场景中，簇的数量往往未知，预设值可能导致结果失真
- 对噪声和异常点敏感：极端值会显著影响簇中心，进而扭曲聚类效果
- 容易受到簇形状限制：K-means 假设簇呈均匀、凸状分布，对于弯月形、环形或相互交错的簇，可能无法正确分出簇
为了解决这些问题，DBSCAN（Density-Based Spatial Clustering of Applications with Noise） 被提出。它是一种 基于密度的聚类方法，无需预先指定簇数，能够发现任意形状的簇，并自动识别噪声点，从而避免噪声干扰结果。凭借这些优势，DBSCAN 在 地理信息分析、图像处理、数据挖掘 等领域得到了广泛应用。
1. 算法原理
在理解 DBSCAN 聚类原理之前，先要明确一点，在聚类的过程中，DBSCAN 会把所有数据点分成三类：
- 核心点：在半径 epsilon 范围内至少有 min_samples 个点（算上自己）
- 边界点：自己周围点数不够 min_samples，但落在某个核心点的 epsilon 范围内
- 噪声点：既不是核心点，也不在任何核心点的 epsilon 范围内
| A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|
| (1,1) | (1,2) | (2,1) | (2,2) | (0.5,2.5) | (8,8) | (8,9) | (9,8) | (7.5,9.5) | (5,5) |
假设：epsilon = 1.5、min_samples = 3
接下来，我们看看具体的聚类过程。计算每个数据点点到其他数据点的距离：
| A | B | C | D | E | F | G | H | I | J | |
|---|---|---|---|---|---|---|---|---|---|---|
| A | 0.000 | 1.000 | 1.000 | 1.414 | 1.581 | 9.899 | 10.630 | 10.630 | 10.700 | 5.657 |
| B | 1.000 | 0.000 | 1.414 | 1.000 | 0.707 | 9.220 | 9.899 | 10.000 | 9.925 | 5.000 |
| C | 1.000 | 1.414 | 0.000 | 1.000 | 2.121 | 9.220 | 10.000 | 9.899 | 10.124 | 5.000 |
| D | 1.414 | 1.000 | 1.000 | 0.000 | 1.581 | 8.485 | 9.220 | 9.220 | 9.301 | 4.243 |
| E | 1.581 | 0.707 | 2.121 | 1.581 | 0.000 | 9.301 | 9.925 | 10.124 | 9.899 | 5.148 |
| F | 9.899 | 9.220 | 9.220 | 8.485 | 9.301 | 0.000 | 1.000 | 1.000 | 1.581 | 4.243 |
| G | 10.630 | 9.899 | 10.000 | 9.220 | 9.925 | 1.000 | 0.000 | 1.414 | 0.707 | 5.000 |
| H | 10.630 | 10.000 | 9.899 | 9.220 | 10.124 | 1.000 | 1.414 | 0.000 | 2.121 | 5.000 |
| I | 10.700 | 9.925 | 10.124 | 9.301 | 9.899 | 1.581 | 0.707 | 2.121 | 0.000 | 5.148 |
| J | 5.657 | 5.000 | 5.000 | 4.243 | 5.148 | 4.243 | 5.000 | 5.000 | 5.148 | 0.000 |
统计每个数据点的邻域
| 数据点 | 邻域点集合 | 邻域点数量 | 数据点类型 |
|---|---|---|---|
| A(1,1) | A, B, C, D | 4 | 核心点 |
| B(1,2) | A, B, C, D, E | 5 | 核心点 |
| C(2,1) | A, B, C, D | 4 | 核心点 |
| D(2,2) | A, B, C, D | 4 | 核心点 |
| E(0.5,2.5) | B, E | 2 | 非核心 |
| F(8,8) | F, G, H | 3 | 核心点 |
| G(8,9) | F, G, H, I | 4 | 核心点 |
| H(9,8) | F, G, H | 3 | 核心点 |
| I(7.5,9.5) | G, I | 2 | 非核心 |
| J(5,5) | J | 1 | 非核心 |
开始聚类：
第一步：外层循环遍历数据点
- 访问 A：A 未访问且为核心点 → 创建簇 C1
- 将 A 的邻域 {A, B, C, D} 全部加入簇
- 核心邻居 B、C、D 入队列等待扩展 → 队列状态 [B, C, D]
第二步：内层队列扩展簇 C1
- 出队 B：邻域 {B, E, A, D, C}
- E 不是核心点，但在 B 的邻域内 → 加入簇作为边界点，不入队
- 队列更新为 [C, D]
- 出队 C：邻域 {C, A, D, B} 已全部在簇中 → 无新增，队列 [D]
- 出队 D：邻域 {D, B, C, A} 已全部在簇中 → 队列清空，C1 扩展完成
第三步：外层循环继续遍历
- 遇到 B、C、D、E 已访问 → 跳过
- 下一个未访问核心点 F → 创建簇 C2
- 将 F 的邻域 {F, G, H} 加入簇
- 核心邻居 G、H 入队列 → 队列状态 [G, H]
第四步：内层队列扩展簇 C2
- 出队 G：邻域 {G, I, F, H}
- I 不是核心点，但在 G 的邻域内 → 加入簇作为边界点，不入队
- 队列更新为 [H]
- 出队 H：邻域 {H, F, G} 已全部在簇中 → 队列清空，C2 扩展完成
第五步：外层循环继续遍历剩余数据点
- I 已访问 → 跳过
- J 未访问且邻域点数 < min_samples，且不在任何核心点邻域 → 判定为噪声点
第六步：最终聚类结果
- 簇 C1：核心点 A、B、C、D；边界点 E
- 簇 C2：核心点 F、G、H；边界点 I
- 噪声点：J
通过对 DBSCAN 聚类过程的了解，我们可以发现，簇的形成和扩展是依靠核心点推动的，而边界点会被吸收进簇，噪声点则不属于任何簇。
另外，我们也发现 DBSCAN 聚类过程中，寻找邻域需要大量的计算。例如：要对 1000 条数据进行聚类，则会进行 100 万次的距离计算，如果数据维度较高，则会需要更多的计算时间。所以，DBSCAN 的聚类优化，主要是通过对邻域计算的优化来提升聚类效率。常见的是，使用 KD TREE 或者 BALL TREE，KD Tree 适合低维数据（通常 20 维），BALL tree 适合较高维数据（20 维以上）。
3. 预测过程
DBSCAN 不提供预测函数。在许多聚类算法中，比如 K-Means 或 GMM，训练完成后会得到一些关键参数：
- K-Means 得到的是各簇的质心；
- GMM 得到的是每个高斯分布的均值、方差和混合系数。
这些参数相当于对簇进行了数学描述，因此我们可以在训练结束后，直接用这些参数来计算新样本属于哪个簇。但 DBSCAN 的情况完全不同。
- 它的聚类是通过 邻域密度 来决定的：某个点是否属于某个簇，依赖于周围是否存在足够多的数据点
- 聚类完成后，DBSCAN 并不会生成类似质心或概率分布这样的参数，只是标记了哪些点属于哪个簇
这就导致一个问题：
如果来一个新样本点，我们没办法直接通过参数来判断它属于哪个簇。唯一稳妥的方法是把新点和旧数据混在一起，重新运行 DBSCAN。但因为 DBSCAN 的结果依赖于样本的分布情况，新点的加入可能改变邻域密度，从而导致原本的聚类结果发生变化
所以，DBSCAN 本质上是一种 非参数化的、依赖训练数据分布的聚类方法，它不提供像 predict 那样稳定的预测接口。
3. 参数调优
在使用 DBSCAN 聚类时，虽然不像 KMeans 需要预先指定簇的数量，但算法仍然依赖于两个重要的超参数：epsilon（邻域半径）和 min_samples（核心点的最少邻居数）。
- epsilon 太小：邻域里点很少，很难形成核心点。簇会分得很多，小簇多，很多点被标记为噪声
- epsilon 太大：邻域里点很多，不同簇可能合并。簇变少甚至整个数据被认为是一个簇
- min_samples 太小：容易形成核心点，簇会很多，可能把噪声也当簇
- min_samples 太大：很难形成核心点，簇会减少，更多点被当作噪声
简言之：min_samples 决定一个点成为核心点所需的最少邻居数，从而影响簇的形成。epsilon 决定搜索邻居的范围，两者共同决定簇的生成和最终的聚类结果。
这俩重要的超参数很难设置。虽然确定 DBSCAN 的 epsilon 和 min_samples 没有绝对公式，但有一些常用的经验方法和可视化技巧可以帮助选择。
在调 DBSCAN 参数时，一般建议 先确定 min_samples，再确定 epsilon.
min_samples 在选择时，一般会根据数据的维度来设置，即：min_samples ≈ 数据维度 + 1。因为数据维度较低，数据通常比较密集，较小的 min_samples 就能把邻域内的点正确聚成簇；如果此时设置过大的 min_samples ，很多本应属于簇的点可能达不到核心点条件，导致簇数量减少甚至无法形成簇。如果数据维度较高，数据在空间中通常更加分散，同样半径 epsilon 的邻域内点数会减少。此时需要增大 min_samples，保证只有真正密集的点群才能成为核心点，避免把稀疏区域误判为簇。
当 min_samples 确定后，epsilon 就是要选择一个合适的邻域半径，使得每个核心点的邻域内能够包含足够的点（≥ min_samples），从而形成核心点并生成簇，对于 epsilon 的搜索，常用的方法是：k 距离图，在该方法中 k=min_samples 设置的值。步骤：
- 对每个点计算到其他点的距离
- 找到每个点的第 k 个最近邻距离
- 将所有点按第 k 个距离升序排列，并绘制折线图
- 曲线中斜率突然变陡的点（拐点）对应密度明显变化的阈值，可作为 epsilon 的参考
下面举个例子，假设有 5 个数据点，k = 2（min_samples = 2）
A(1,1), B(2,2), C(2,0), D(5,5), E(8,8)
计算每个点到其他点的距离：
| 点对 | 距离 |
|---|---|
| A-B | 1.41 |
| A-C | 1.41 |
| A-D | 5.66 |
| A-E | 9.90 |
| B-C | 2.00 |
| B-D | 4.24 |
| B-E | 8.49 |
| C-D | 5.83 |
| C-E | 10.0 |
| D-E | 4.24 |
对每个点，把距离排序，取第 2 个最近邻距离（k = 2）
| 点 | 距离排序 | 第 2 个最近邻距离 |
|---|---|---|
| A | 1.41, 1.41, 5.66, 9.90 | 1.41 |
| B | 1.41, 2.00, 4.24, 8.49 | 2.00 |
| C | 1.41, 2.00, 5.83,10.0 | 2.00 |
| D | 4.24, 4.24, 5.66, 5.83 | 4.24 |
| E | 4.24, 8.49, 9.90,10.0 | 8.49 |
排序第 2 个最近邻距离：1.41、2.00、2.00、4.24、8.49，生成 K 距离图：
在 DBSCAN 的 K 距离折线图中，epsilon 在 2.00 → 4.24 出现了明显的变化，这被称作拐点，对应密度变化明显的阈值。拐点提示了一个合理的 epsilon 取值范围，DBSCAN 可以较好地识别簇，同时控制噪声点数量。
如果此时，仍然觉得聚类效果不太好，可以在此基础上，调整 min_samples 和 eps。
4. 接口使用
import numpy as np
from sklearn.cluster import DBSCAN
import pandas as pd
def demo():
points = np.array([[1, 1], [1, 2], [2, 1], [2, 2], [0.5, 2.5], [8, 8], [8, 9], [9, 8], [7.5, 9.5], [5, 5]])
columns = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
dbscan = DBSCAN(eps=1.5, min_samples=3, metric='manhattan1')
result = dbscan.fit_predict(points)
# 聚类结果
# [ 0 0 0 0 0 1 1 1 1 -1]
# 0 表示第一个簇
# 1 表示第二个簇
# -1 表示噪声点
print(result)
# 核心样本
print(dbscan.core_sample_indices_) # 数据点索引
print(dbscan.components_) # 数据点
if __name__ == '__main__':
demo()
冀公网安备13050302001966号