DBSCAN 密度聚类算法

FreeGuideOnline 17阅读 2026-07-13

DBSCAN(D, eps, minPts) C = 0 # 簇编号 for each unvisited point P in dataset D mark P as visited NeighborPts = regionQuery(P, eps) if sizeof(NeighborPts) < minPts mark P as NOISE else C = next cluster expandCluster(P, NeighborPts, C, eps, minPts)


其中 `expandCluster` 负责密度扩展，将密度可达的所有点加入同一个簇。

## 关键参数的选择策略

DBSCAN 的效果极度依赖 `eps` 和 `min_samples`，参数选择不当可能导致所有点成为一个簇或全被当成噪声。

### MinPts（min_samples）的选取
- 一般规则：`min_samples` ≥ 数据维度数 + 1。
- 对于大型数据集，`min_samples` 可以取更大值，例如 10 或 20。
- 对于有噪声的数据，增大 `min_samples` 可以提升抗噪能力，但可能丢失较小的簇。
- 经验公式：`min_samples` ≈ 2 × 维度数。

### ε（eps）的选取
`eps` 控制邻域大小，是参数选择的难点。

**k-距离图**是常用的启发式方法：
1. 对每个点，计算它与第 k 个最近邻点的距离（k = `min_samples`）。
2. 将这些距离从大到小排序，并绘制成曲线。
3. 曲线中“拐点”（elbow point）对应的距离通常是合理的 `eps` 值。拐点意味着距离突然增大，标识了从簇内点到噪声点的过渡。

在 Python 中，可以使用 `sklearn` 的 `NearestNeighbors` 辅助计算 k-距离：

```python
from sklearn.neighbors import NearestNeighbors
import numpy as np
import matplotlib.pyplot as plt

k = min_samples  # 通常 k = min_samples
neigh = NearestNeighbors(n_neighbors=k)
neigh.fit(data)
distances, _ = neigh.kneighbors(data)
k_dist = np.sort(distances[:, -1])  # 第k近邻距离
plt.plot(k_dist)
plt.show()

参数调优的实践建议

  • 尝试多组参数组合，借助轮廓系数（Silhouette Coefficient）评估。但注意：DBSCAN 的噪声点不参与轮廓系数计算，因此需谨慎解读。
  • 结合业务理解：如果你知道簇的最小物理范围，可据此估计 eps。

DBSCAN 的优点与局限

优点

  • 无需预设簇数：算法自动决定簇的数量。
  • 发现任意形状的簇：不像 K-Means 仅擅长球形簇，DBSCAN 可以处理弯曲、细长的簇。
  • 天然抗噪声：能够识别并分离离群点。
  • 对数据输入顺序不敏感（整体结果确定，但边界点可能因核心点处理顺序不同而归属稍有差异）。
  • 仅需两个参数（实际调参焦点在 eps）。

局限

  • 密度不均的数据集效果差：当各簇的密度差异很大时，统一的 eps 和 min_samples 难以同时捕获稀疏簇与紧密簇。
  • 高维数据性能下降：由于“维数灾难”，距离度量失效，聚类质量急剧恶化。一般建议先降维（如 PCA，t-SNE）后再使用 DBSCAN。
  • 参数敏感：eps 的微小变化可能导致完全不同的聚类结果。
  • 对距离度量选择敏感：欧氏距离未必适合所有数据。
  • 计算复杂度：最坏情况 O(n²)，使用空间索引（如 kd-tree，ball-tree）可实现平均 O(n log n)，但高维时索引退化为 O(n²)。

算法变体与扩展

为了解决 DBSCAN 的局限性，研究者提出了若干改进版本：

  • OPTICS（Ordering Points To Identify the Clustering Structure）：通过生成一个可扩展的聚类顺序，能够处理密度不同的簇，而无需指定单一的 eps 阈值。
  • HDBSCAN（Hierarchical DBSCAN）：构建层次聚类树，自动选取最适合数据的稳定聚类，减少了参数选择的麻烦，并对密度变化有较好适应性。
  • DENCLUE：基于密度分布函数和网格的聚类。

Python 实现与实战案例

环境准备

使用 scikit-learn 库，可通过 pip install scikit-learn matplotlib numpy 安装所需包。

示例：二维合成数据聚类

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

# 生成月牙形数据（非球形簇）
X, y_true = make_moons(n_samples=300, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X)  # 标准化

# 应用 DBSCAN
db = DBSCAN(eps=0.3, min_samples=5)
labels = db.fit_predict(X)

# 结果分析
core_samples_mask = np.zeros_like(labels, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

print(f'估计的簇数: {n_clusters}')
print(f'噪声点数量: {n_noise}')

# 可视化
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))

plt.figure(figsize=(8, 6))
for label, col in zip(unique_labels, colors):
    if label == -1:
        col = 'k'  # 噪声点黑色
    class_member_mask = (labels == label)
    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col, markersize=8)
    # 边界点
    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col, markersize=4)

plt.title(f'DBSCAN: {n_clusters} 个簇, {n_noise} 个噪声点')
plt.show()

真实案例：地理位置聚类

假设我们拥有用户的位置坐标（经纬度），希望发现主要活动区域并去除异常点。由于地球是球面，应使用哈弗辛距离（Haversine distance）或直接将经纬度转换为墨卡托投影后再用欧氏距离。scikit-learn 的 DBSCAN 内置支持 metric='haversine'（需数据以弧度为单位）。

# 假设 df 包含 'lat', 'lon' 列
rads = np.deg2rad(df[['lat', 'lon']])
db = DBSCAN(eps=0.01, min_samples=3, metric='haversine')
labels = db.fit_predict(rads)