DBSCAN密度聚类

本文目录导读：

1. 核心思想
2. 两个关键参数
3. 三种点类型
4. 算法流程
5. 关键概念
6. 优点
7. 缺点
8. 参数选择建议
9. 与 K-Means 的对比
10. Python 示例

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种经典的基于密度的聚类算法，与 K-Means 这种基于距离的算法不同，DBSCAN 不需要事先指定聚类的数量，并且能够识别出“噪声”点（不属于任何簇的离群点）。

核心思想

DBSCAN 认为：对于一个簇内的所有点，其邻域半径内必须包含足够多的点。

算法通过寻找被低密度区域（噪声）分隔开的高密度区域来形成簇。

两个关键参数

• eps （ε，邻域半径）：定义了一个点的“邻居”范围，两个点距离小于等于 eps 才算邻居。
• minPts （最小样本数）：一个点的 eps 邻域内至少包含 minPts 个点（包括该点本身），才能被认为是“核心点”。

三种点类型

根据参数 eps 和 minPts，DBSCAN 将数据点分为三类：

算法流程

1. 标记核心点：遍历所有未访问的点，计算其 eps 半径内的邻居数，若 >= minPts，则标记为核心点。
2. 扩展簇：
   • 随机选择一个核心点作为新簇的起点。
   • 找到该核心点的所有密度可达的点（该核心点的邻居，以及邻居的邻居……），将它们加入该簇。
   • 在这个过程中,遇到的核心点会继续向外扩展，遇到的边界点被纳入簇，但不会向外延伸。
3. 重复：直到所有核心点都被访问完毕。
4. 标记噪声：剩余未被归入任何簇的点即为噪声点。

关键概念

• 密度直达：点 A 在点 B 的 eps 邻域内，且 B 是核心点。
• 密度可达：存在一条路径，路径上的每个点都是核心点，且相邻点之间密度直达，这是形成簇的核心机制。
• 密度相连：对于点 A 和点 B，存在一个核心点 C，使得 A 和 B 都能从 C 密度可达，密度相连是聚类的最终条件。

优点

1. 不需要预设簇数 K：自动发现簇的数量。
2. 能识别噪声：有效处理离群点，不受其影响。
3. 能发现任意形状的簇：可以找到“月牙形”、“S形”等非球形簇。
4. 对数据顺序不敏感（通常情况）。

缺点

1. 对参数敏感：eps 和 minPts 的设置对结果影响巨大，难以调参。
2. 密度不均匀问题：如果数据集的密度差异非常大，则很难找到一组 eps 和 minPts 同时适配所有簇。
3. 高维数据效果差：在高维空间中，“密度”的概念会失效（维数灾难）。
4. 计算复杂度：若不使用索引（如 KD-Tree），复杂度为 O（n²）。

参数选择建议

• minPts：
  • 一般取 *2 维度** （如果维度较低）。
  • 数据量大时,可适当增大（如 10-50）。
  • 对于通常的 2D/3D 数据，minPts = 5 是一个常用起点。
• eps：
  • 通常使用 k-距离图（k-distance graph）来确定。
  • 步骤：计算每个点到其第 k 个（k = minPts - 1）最近邻居的距离；将这些距离排序绘图；选择曲线“拐点”（elbow point）处的距离作为 eps。

与 K-Means 的对比

Python 示例

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
# 生成非球形数据（两个新月形状）
X, y = make_moons(n_samples=200, noise=0.05, random_state=42)
# ---- DBSCAN 聚类 ----
# eps=0.3, minPts=5
dbscan = DBSCAN（eps=0.3, min_samples=5）
labels = dbscan.fit_predict（X）
# 可视化
plt.figure（figsize=（8, 4））
# 原始数据
plt.subplot（1, 2, 1）
plt.scatter（X[:, 0], X[:, 1], c=y, cmap='viridis', s=50）"真实标签"）
# DBSCAN 结果
plt.subplot（1, 2, 2）
# 注意：label = -1 表示噪声点
unique_labels = set（labels）
colors = [plt.cm.Spectral（each） for each in np.linspace（0, 1, len（unique_labels））]
for k, col in zip（unique_labels, colors）：
    if k == -1：
        col = [0, 0, 0, 1]  # 黑色表示噪声
    class_member_mask = （labels == k）
    xy = X[class_member_mask]
    plt.scatter（xy[:, 0], xy[:, 1], c=[col], s=50, edgecolor='k'）f"DBSCAN 结果 （噪声点数：{sum（labels == -1）}）"）
plt.tight_layout（）
plt.show（）

DBSCAN 是探索性数据分析（EDA）和需要处理噪声的场景下的首选聚类算法之一。