聚类分析算法——DBSCAN（密度聚类）算法详解
本文要全面、深入地介绍理解 DBSCAN（Density-Based Spatial Clustering of Applications with Noise），我们需要从 算法的核心思想、步骤、底层原理、参数选择，以及 代码实现细节 上进行详细剖析。
1. DBSCAN 算法核心思想
DBSCAN 是一种基于密度的聚类算法，旨在发现任意形状的簇，并且对 噪声点（outliers）具有鲁棒性（健壮性）。它通过在数据空间中找到高密度区域，将这些区域作为簇，同时把孤立点（密度低的点）归为噪声。
DBSCAN 的基本思想是：
- 在某个点的 邻域半径（ε，epsilon） 内，如果有足够多的点（超过一个阈值 minPts），就认为这个区域是一个 高密度区域，可以扩展成一个簇。
- 一个簇通过密度相连（density-connected） 的点进行扩展。
- 无法归属于任何簇的点被认为是噪声点。
数据可视化
可以试试DBSCAN可视化网址来直接了解执行的流程
执行过程：
示例：
① 数据处理前：
参数解释：epsilon指的为半径，minPoints指的是在半径为1的空间里有四个小球即可扩散
② 数据处理后：
2. DBSCAN 的基本概念
- ε-邻域（Epsilon-neighborhood）：
对于某个点 p，以半径 ε 为边界的区域内所有的点称为该点的 ε-邻域。 - 核心点（Core Point）：
如果一个点 p 的 ε-邻域内至少有 minPts 个点（包括 p 自己），那么它被称为核心点。 - 边界点（Border Point）：
如果一个点 p 在某个核心点的 ε-邻域内，但自身不是核心点，它被称为边界点。 - 噪声点（Noise Point）：
如果一个点既不是核心点，也不属于任何核心点的邻域，它被认为是噪声点。 - 密度直达（Directly Density-Reachable）：
如果点 p 是核心点，并且点 q 在 p 的 ε-邻域内，那么 q 被称为从 p 密度直达。 - 密度可达（Density-Reachable）：
如果存在一条核心点链表（p1→p2→...→pn），使得每个点从前一个点密度直达，且 p1=p，pn=q，则 q 是从 p 密度可达 的。 - 密度相连（Density-Connected）：
如果存在一个点 o，使得 p 和 q 都从 o 密度可达，则称 p 和 q 是密度相连的。
3. DBSCAN 算法步骤
- 初始化：
从数据集中任意选择一个点 p，判断它是否为核心点（即 ε 邻域内是否包含至少 minPts 个点）。 - 扩展簇：
如果 p 是核心点，则开始一个新簇，将 p 及其邻域中的点加入簇中，并不断对新的核心点的邻域进行扩展。 - 处理噪声点：
如果一个点既不在任何簇中，也不满足成为核心点的条件，则将其标记为噪声点。 - 重复处理：
继续检查所有未访问的点，直到所有点都被访问为止。
4. DBSCAN 伪代码
DBSCAN(D, ε, minPts): C = 0 # 初始化簇标签 for each unvisited point P in dataset D: mark P as visited Neighbors = getNeighbors(P, ε) # 获取邻域内的所有点 if size(Neighbors) < minPts: mark P as NOISE # 认为该点是噪声 else: C = C + 1 # 创建新簇 expandCluster(P, Neighbors, C, ε, minPts) expandCluster(P, Neighbors, C, ε, minPts): add P to cluster C for each point Q in Neighbors: if Q is not visited: mark Q as visited NeighborsQ = getNeighbors(Q, ε) if size(NeighborsQ) >= minPts: Neighbors = Neighbors ∪ NeighborsQ if Q is not yet assigned to any cluster: add Q to cluster C 5. DBSCAN 的时间复杂度分析
- 邻域查询：在每次扩展时，需要查找一个点的 ε 邻域。如果使用 KD-Tree 或 Ball-Tree 等空间索引结构，这个操作的复杂度为 O(logn)。
总体复杂度：如果对每个点进行邻域查询，算法的时间复杂度为 O(n⋅logn)。如果不使用索引结构，最坏情况下是
。
6. DBSCAN 的 Python 实现
我们使用 scikit-learn 中的 DBSCAN 实现，并演示如何手动实现核心逻辑。
6.1 使用 scikit-learn 的 DBSCAN
from sklearn.cluster import DBSCAN import numpy as np # 生成示例数据 X = np.array([[1, 2], [2, 2], [2, 3], [8, 7], [8, 8], [25, 80]]) # 初始化 DBSCAN 模型 db = DBSCAN(eps=3, min_samples=2).fit(X) # 获取聚类标签 labels = db.labels_ print("Cluster labels:", labels) 输出：
Cluster labels: [ 0 0 0 1 1 -1]解释：
- 标签为
-1的点表示噪声点。 - 其他标签表示该点属于的簇。
6.2 手动实现 DBSCAN 的核心逻辑
import numpy as np def dbscan(X, eps, minPts): labels = [-1] * len(X) # 初始化所有点为未分类（-1 表示噪声） C = 0 # 当前簇标签 def region_query(P): return [i for i, Q in enumerate(X) if np.linalg.norm(P - Q) <= eps] def expand_cluster(P, neighbors): labels[P] = C i = 0 while i < len(neighbors): Q = neighbors[i] if labels[Q] == -1: # 如果 Q 是噪声点，重新标记为簇点 labels[Q] = C elif labels[Q] == -1: # 如果 Q 还未分类 labels[Q] = C Q_neighbors = region_query(X[Q]) if len(Q_neighbors) >= minPts: neighbors += Q_neighbors # 扩展邻域 i += 1 for P in range(len(X)): if labels[P] == -1: neighbors = region_query(X[P]) if len(neighbors) < minPts: labels[P] = -1 # 标记为噪声 else: C += 1 # 创建新簇 expand_cluster(P, neighbors) return labels # 示例数据 X = np.array([[1, 2], [2, 2], [2, 3], [8, 7], [8, 8], [25, 80]]) # 运行 DBSCAN labels = dbscan(X, eps=3, minPts=2) print("Cluster labels:", labels) 7. 参数选择与调优
- ε（eps）：
- ε 决定了邻域的大小。如果太小，簇会分散；太大，簇会合并。
- minPts：
- 一般来说，
minPts≥ 数据维度的两倍。例如对于二维数据，可以设置minPts = 4。
- 一般来说，
- 调参思路
ε（eps）小，minPts大：一般是半径ε小一点，minPts 大一点
可以通过 k距离图（k-distance graph）来选择合适的 ε。
8. DBSCAN 的优缺点
优点：
- 可以发现任意形状的簇。
- 不需要预先指定簇的数量。
- 对噪声有鲁棒性。
缺点：
- 当簇的密度差异较大时，效果不佳。
- 高维数据中的性能较差，非常消耗CPU和GPU以及内存性能。
- 需要合理选择 ε 和
minPts参数。
9. 总结
DBSCAN 是一种基于密度的聚类算法，特别适用于发现任意形状的簇，并且具有处理噪声点的能力。通过合理选择参数 ε 和 minPts，它可以在空间数据分析、图像处理、异常检测等领域发挥重要作用。
