DBSCAN 密度聚类 · 深度手册
分类：聚类分类 ｜ 难度：★★☆ 进阶 ｜ 编号：
dbscan
📊 数据视角：它到底有多常用？
本资料站收录 343 篇 优秀范文，DBSCAN 共出现约 25 次，排名靠前。其中：
- 美赛（MCM/ICM）：18 次，主要用于异常检测和空间聚类；
- 国赛（CUMCM）：5 次，用于数据分组；
- 电工杯 / 泰迪杯：约 2~3 次。
关键词覆盖："DBSCAN"、"密度聚类"、"核心点"、"边界点"、"噪声"、"eps"、"MinPts" 等。
一句话：DBSCAN 不需要预先指定簇数，而是根据点的密度自动发现任意形状的簇——还能顺带把离群点识别出来，是 K-Means 的天然互补。
一、这是什么（一句话用途）
基于密度的聚类（任意形状簇 / 异常检测 / 无需预设簇数）
二、核心思想
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）的核心直觉很简单：好的簇应该是高密度区域，被低密度区域隔开。它把数据点分为三类：
| 类型 | 定义 | 含义 |
|---|---|---|
| 核心点 | 在 ε 邻域内至少有 MinPts 个点 | 簇的内部点 |
| 边界点 | 在核心点的 ε 邻域内，但自身不满足核心点条件 | 簇的边缘 |
| 噪声点 | 既不是核心点也不是边界点 | 离群点 |
关键优势：
- 自动发现任意形状的簇（不限于球形）
- 不需要预先指定簇数 k
- 能识别并标记噪声点
- 对数据中的离群点鲁棒
三、数学原理与推导
3.1 基本定义
给定数据集 ，两个参数 ：
- ε-邻域：
- 核心点：
- 直接密度可达：若 是核心点且 ，则
- 密度可达：存在点链 ，，且 直接密度可达于
- 密度相连：存在点 使得 和 都密度可达于
簇：满足最大密度相连性的点集合。
3.2 算法流程
输入: 数据集 D, 半径 ε, 最小点数 MinPts
输出: 簇标签
1. 初始化所有点为"未访问"
2. 对每个未访问点 p:
a. 标记 p 为已访问
b. 找到 p 的 ε-邻域 Nε(p)
c. 如果 |Nε(p)| < MinPts:
标记 p 为噪声（暂时）
d. 否则:
创建新簇 C
从 Nε(p) 中扩展簇 C:
对 Nε(p) 中每个点 q:
如果 q 未访问:
标记 q 为已访问
找到 q 的 ε-邻域
如果 |Nε(q)| >= MinPts:
将 Nε(q) 加入扩展队列
如果 q 不属于任何簇:
将 q 加入簇 C
3. 返回所有簇和噪声点
四、建模 / 求解步骤
- 数据标准化
- 选择距离度量（通常欧氏）
- 确定 ε 和 MinPts（见下文）
- 运行 DBSCAN 聚类
- 评估聚类质量 + 分析噪声点
五、参数选择指南
5.1 K-距离图法（选 ε）
对每个点计算到第 K 个最近邻居的距离（K≈MinPts），排序后画 K-距离图。曲线上的"拐点"对应的距离值即为合适的 ε。
5.2 MinPts 经验规则
一般取 （d 为特征维度）。
5.3 交叉验证
在 ε 的候选范围内搜索，使轮廓系数（对密度簇）或 Calinski-Harabasz 指数最大。
六、Python 实现示例
6.1 从零手写 DBSCAN
import numpy as np
class DBSCAN:
def __init__(self, eps=0.5, min_samples=5):
self.eps = eps
self.min_samples = min_samples
def _distance(self, x1, x2):
return np.sqrt(np.sum((x1 - x2)**2))
def _get_neighbors(self, point_idx, X):
neighbors = []
for i, x in enumerate(X):
if self._distance(X[point_idx], x) <= self.eps:
neighbors.append(i)
return neighbors
def fit(self, X):
n = len(X)
labels = np.full(n, -1, dtype=int) # -1 表示噪声
visited = np.zeros(n, dtype=bool)
for i in range(n):
if visited[i]:
continue
visited[i] = True
neighbors = self._get_neighbors(i, X)
if len(neighbors) < self.min_samples:
labels[i] = -1 # 噪声点
else:
# 新建簇
cluster_id = np.max(labels) + 1 if -1 in labels else 0
labels[i] = cluster_id
# 扩展簇
seed_set = neighbors[:]
j = 0
while j < len(seed_set):
q = seed_set[j]
if not visited[q]:
visited[q] = True
q_neighbors = self._get_neighbors(q, X)
if len(q_neighbors) >= self.min_samples:
seed_set.extend([x for x in q_neighbors if x not in seed_set])
if labels[q] == -1:
labels[q] = cluster_id # 边界点分配簇
j += 1
self.labels_ = labels
return self
# 测试
np.random.seed(42)
# 三簇数据 + 噪声
X = np.vstack([
np.random.randn(50, 2) * 0.5 + [0, 0],
np.random.randn(50, 2) * 0.5 + [5, 5],
np.random.randn(50, 2) * 0.3 + [10, 0],
np.random.randn(10, 2) * 0.2 + [2.5, 7.5], # 噪声
])
model = DBSCAN(eps=1.0, min_samples=5).fit(X)
print(f"发现 {len(set(model.labels_)) - (1 if -1 in model.labels_ else 0)} 个簇")
print(f"噪声点数: {np.sum(model.labels_ == -1)}")
6.2 使用 sklearn
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
np.random.seed(42)
# 模拟不规则形状的簇（螺旋形）
theta = np.linspace(0, 4*np.pi, 200)
X1 = np.column_stack([theta*np.cos(theta), theta*np.sin(theta)]) + np.random.randn(200, 2)*0.3
X2 = np.column_stack([theta*np.cos(theta)+5, theta*np.sin(theta)+5]) + np.random.randn(200, 2)*0.3
X = np.vstack([X1, X2])
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# 用 K-距离图选 eps
k = 5
distances = np.sort(np.linalg.norm(X_scaled[:, None] - X_scaled[None, :], axis=2)[:, k])
plt.plot(distances)
plt.xlabel('Point index'); plt.ylabel(f'{k}-th nearest distance')
plt.title('K-Distance Graph for DBSCAN eps selection')
plt.tight_layout()
plt.show()
# 聚类
dbscan = DBSCAN(eps=0.8, min_samples=5)
labels = dbscan.fit_predict(X_scaled)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f'Clusters: {n_clusters}, Noise: {n_noise}')
七、MATLAB 实现示例
%% DBSCAN 聚类（MATLAB/Octave）
rng(42);
% 生成数据
X1 = randn(50,2)*0.5 + [0,0];
X2 = randn(50,2)*0.5 + [5,5];
X3 = randn(50,2)*0.3 + [10,0];
X = [X1; X2; X3];
% 添加噪声
X = [X; randn(10,2)*0.2 + [2.5, 7.5]];
% DBSCAN
eps = 1.0; minPts = 5;
n = size(X,1);
labels = -ones(n,1);
visited = false(n,1);
clusterId = 0;
for i = 1:n
if visited(i), continue; end
visited(i) = true;
% 找邻居
dists = sqrt(sum((X - X(i,:)).^2, 2));
neighbors = find(dists <= eps);
if length(neighbors) < minPts
labels(i) = -1; % 噪声
else
clusterId = clusterId + 1;
labels(i) = clusterId;
seedSet = neighbors';
j = 1;
while j <= length(seedSet)
q = seedSet(j);
if ~visited(q)
visited(q) = true;
dists_q = sqrt(sum((X - X(q,:)).^2, 2));
neighbors_q = find(dists_q <= eps);
if length(neighbors_q) >= minPts
seedSet = [seedSet; neighbors_q'];
end
end
if labels(q) == -1
labels(q) = clusterId; % 边界点
end
j = j + 1;
end
end
end
fprintf('发现 %d 个簇, 噪声点 %d 个\n', max(labels(labels>0)), sum(labels==-1));
八、常见问题与改进
| 问题 | 解决方案 |
|---|---|
| 高维数据效果差（维度灾难） | 先用 PCA 降维 |
| 簇密度差异大时效果不佳 | 用 OPTICS 算法（自适应 ε） |
| 参数选择困难 | 用 K-距离图 + 交叉验证 |
| 大数据集慢（O(n²)） | 用球树/KD-tree 加速近邻查询 |
九、K-Means vs DBSCAN 对比
| 特性 | K-Means | DBSCAN |
|---|---|---|
| 需要预设簇数 | ✅ 是 | ❌ 否 |
| 任意形状簇 | ❌ 只适合球形 | ✅ 可以 |
| 噪声处理 | ❌ 强制分配 | ✅ 自动识别 |
| 密度不均 | ❌ 效果差 | ✅ 鲁棒 |
| 计算复杂度 | O(nkt) | O(n²)（可优化到 O(nlogn)） |
| 参数 | 只需 k | 需 ε 和 MinPts |
十、论文写作技巧
1. 动机怎么写
由于数据分布具有任意形状且存在噪声点，K-Means 等传统聚类算法难以适用。本文采用 DBSCAN 密度聚类算法，该算法能够自动发现簇的数量和形状，同时识别噪声点，更适合本问题的数据特征。
2. 结果怎么写
必须包含：
- 聚类散点图：不同颜色标注各簇，黑色标注噪声
- 参数选择依据：K-距离图 + 参数说明
- 噪声分析：噪声点占比及业务含义
十一、相关手册（延伸阅读）
- K-Means 聚类 · 聚类分类
- 高斯混合模型 GMM · 聚类分类
完整算例（数字演示，照着算一遍）
场景：12 个点 2 维，eps=2, MinPts=3。
过程：核心点（邻域内点数≥3）彼此密度可达则连成簇；边界点归入相邻核心点所在簇；无足够邻域的点标为噪声。
结论：得到 2 个簇 + 1 个噪声点，无需预设簇数 K，能发现任意形状簇。
十二、本手册导航
- 上一篇：K-Means 聚类 · 聚类分类
- 下一篇：朴素贝叶斯 · 机器学习
- 返回：算法深度手册库 ｜ 资料站首页
本手册由「算法深度手册生成器」自动产出。