【第二章:机器学习与神经网络概述】01.聚类算法理论与实践-(3)DBSCAN 聚类算法

第二章: 机器学习与神经网络概述

第一部分：聚类算法理论与实践

第二节：DBSCAN 聚类算法（Density-Based Spatial Clustering of Applications with Noise）

内容：密度聚类原理、参数选择及边界点处理。

---

一、DBSCAN 简介

DBSCAN 是一种基于密度的聚类算法，不依赖于聚类数量的预设，能自动识别任意形状的簇，并能识别离群点（噪声）。它是处理噪声数据和不规则聚类结构的经典算法。

---

二、核心概念

1. ε 邻域（ε-neighborhood）
   给定一个样本点 pp，以半径 ε 为范围画一个圆（或高维球体），该区域内的所有点称为 p 的 ε 邻域。

2. 核心点（Core Point）
   如果某点的 ε 邻域内至少包含 MinPts 个点（包括它自身），它就是核心点。

3. 密度直达（Directly Density-Reachable）
   如果点 q 在点 p 的 ε 邻域内，且 p 是核心点，则称 q 密度直达于 p。

4. 密度可达（Density-Reachable）
   若存在一个点序列 ，使得 , ，且序列中的点两两密度直达，则称 q 密度可达于 p。

5. 边界点（Border Point）
   自身不是核心点，但在某个核心点的 ε 邻域内的点。

6. 噪声点（Noise Point）
   既不是核心点，也不是任何核心点 ε 邻域内的点。

---

三、DBSCAN 聚类步骤

输入：数据集 D，参数 ε 和 MinPts
输出：簇集合与噪声点1. 对每个未访问的点 p：a. 标记为已访问；b. 获取 p 的 ε 邻域 N；c. 若 N 中点数 < MinPts，则标记为噪声；d. 否则，以 p 为核心点扩展新簇：- 将 N 中所有点加入簇；- 对每个新加入点 q：- 若 q 未访问，标记为已访问；- 若 q 的 ε 邻域中点数 ≥ MinPts，则将其邻域也加入当前簇。

---

四、参数选择

1. ε（邻域半径）：

   • 太小：大部分点被当作噪声；

   • 太大：不同簇可能合并。

   • 通常使用 k-距离图 寻找拐点作为 ε 的经验值。

2. MinPts（最小密度）：

   • 一般经验：MinPts ≥ 数据维度数 + 1；

   • 通常在 4～10 之间调试。

---

五、优缺点

优点	缺点
自动决定簇数量	对参数 ε 和 MinPts 较敏感
可识别任意形状簇	高维数据中距离不再可靠（“维数灾难”）
可识别噪声点	核心点密度不均时效果差

---

六、示例代码（使用 sklearn）

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt# 生成数据
X, _ = make_moons(n_samples=300, noise=0.05)# DBSCAN 聚类
db = DBSCAN(eps=0.2, min_samples=5)
labels = db.fit_predict(X)# 可视化
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='rainbow')
plt.title("DBSCAN Clustering")
plt.show()

 

---

七、DBSCAN 关键图示建议

1. ε 邻域示意图：展示核心点、边界点、噪声点的空间分布。

2. 聚类结果图：展示任意形状聚类结果。

3. k-距离图：帮助选取 ε。

4. 算法流程图：以核心点扩展簇的过程。

---

总结

• DBSCAN 是一种无需指定簇数、可识别任意形状聚类结构的密度聚类算法；

• 关键在于 ε 与 MinPts 参数选择；

• 与 K-means 相比，更适合有噪声、不规则形状的实际场景。