聚类分析算法——DBSCAN（密度聚类）算法详解

本文要全面、深入地介绍理解 DBSCAN（Density-Based Spatial Clustering of Applications with Noise），我们需要从 算法的核心思想、步骤、底层原理、参数选择，以及 代码实现细节 上进行详细剖析。

1. DBSCAN 算法核心思想

DBSCAN 是一种基于密度的聚类算法，旨在发现任意形状的簇，并且对噪声点（outliers）具有鲁棒性（健壮性）。它通过在数据空间中找到高密度区域，将这些区域作为簇，同时把孤立点（密度低的点）归为噪声。

DBSCAN 的基本思想是：

在某个点的 邻域半径（ε，epsilon） 内，如果有足够多的点（超过一个阈值 minPts），就认为这个区域是一个 高密度区域，可以扩展成一个簇。
一个簇通过密度相连（density-connected） 的点进行扩展。
无法归属于任何簇的点被认为是噪声点。

2. DBSCAN 的基本概念

ε-邻域（Epsilon-neighborhood）：
对于某个点 pp，以半径 εε 为边界的区域内所有的点称为该点的 ε-邻域。
核心点（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 visitedNeighbors = 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 Cfor each point Q in Neighbors:if Q is not visited:mark Q as visitedNeighborsQ = getNeighbors(Q, ε)if size(NeighborsQ) >= minPts:Neighbors = Neighbors ∪ NeighborsQif Q is not yet assigned to any cluster:add Q to cluster C

5. DBSCAN 的时间复杂度分析

邻域查询：在每次扩展时，需要查找一个点的 εε 邻域。如果使用 KD-Tree 或 Ball-Tree 等空间索引结构，这个操作的复杂度为 O(log⁡n)O(logn)。
总体复杂度：如果对每个点进行邻域查询，算法的时间复杂度为 O(n⋅log⁡n)O(n⋅logn)。如果不使用索引结构，最坏情况下是 O(n2)O(n2)。

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 npdef 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] = Ci = 0while i < len(neighbors):Q = neighbors[i]if labels[Q] == -1:  # 如果 Q 是噪声点，重新标记为簇点labels[Q] = Celif labels[Q] == -1:  # 如果 Q 还未分类labels[Q] = CQ_neighbors = region_query(X[Q])if len(Q_neighbors) >= minPts:neighbors += Q_neighbors  # 扩展邻域i += 1for 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）：
- ε 决定了邻域的大小。如果太小，簇会分散；太大，簇会合并。
- 可以通过 k距离图（k-distance graph）来选择合适的 ε。
minPts：
- 一般来说，minPts ≥ 数据维度的两倍。例如对于二维数据，可以设置 minPts = 4。