【机器学习】讲透一个强大算法模型，DBSCAN ！！

今儿给大家整理的是，聚类算法之DBSCAN。

简单来说，DBSCAN（Density-Based Spatial Clustering of Applications with Noise，基于密度的聚类）是一类典型的密度聚类算法，它通过“局部密度阈值”来识别簇与离群点。

与K-Means这类基于均值、通过最优化全局目标函数（如平方误差）求解的算法不同，DBSCAN并不显式优化一个传统意义上的全局目标函数，而是将聚类问题表述为：在一个具有邻近关系的空间中，寻找满足密度约束的最大密度连接分量。

直观地说，DBSCAN企图优化以下性质：

• 最大化被识别为簇的点的覆盖数量（在给定密度阈值下）。
• 最小化误把离群点归为某个簇的风险（通过对低密度区域进行抑制）。
• 在全局参数固定的情况下，寻找所有满足密度连通的最大子集（保证簇具有“最大性”）。

因此，在算法学与几何图论的范式中，DBSCAN等价于在一个由邻接关系（-邻域）构造的图上，寻找满足核心点阈值约束的最大连通分量集合。

这一视角天然满足一种“约束最大化”优化表述（后文将详述该等价性与形式化目标）。

在异常检测、非球形聚类、含离群噪声的数据场景中，DBSCAN因其形状不敏感（能识别任意形状的簇）与对噪声鲁棒的特性，长期被实践界采用。

基本定义

咱们设  为样本集合，定义度量空间，其中是度量（默认欧氏距离）。

给定参数与整数（简称）。

咱们提前用以下记号定义DBSCAN的核心概念：

• -邻域：

• 核心点：若，则点为核心点，记为。

• 直接密度可达：若且，则可由直接密度可达，记为。

• 密度可达：若存在序列使得，，且对每个，，则称由密度可达。记为。

• 密度连通：若存在点，使得且，则称与密度连通。

• 边界点：若点不是核心点，但存在核心点 使，并且属于某个簇的边界（可由某核心点密度可达而归入该簇，但本身不满足核心点条件）。

• 噪声点：既不属于任何簇也不是边界点（或更严格地，簇外的点，常在算法输出中标记为）。

DBSCAN的簇定义为所有彼此密度连通的点所构成的最大集合。

形式化地，一个簇满足：

1. 非空；
2. 最大性（若与中任一点密度连通，则）；
3. 连通（对任意，存在点使均密度可达于）。

进一步记号：

• 核心点集。
• 簇集合，其中每个是密度连通的最大子集。

算法原理

算法流程

输入：数据集，距离度量，参数与。

输出：簇标签。

步骤：

1. 对每个点，计算与其大小；若，标记为核心点。
2. 初始化簇标签，全部设为未访问。
3. 对每个未访问点：

• 若不是核心点：若其可由某核心点密度可达则设为边界点并加入对应簇，否则标记为噪声（-1）。
• 若是核心点：发起“扩展”过程，基于密度可达关系寻找所有与密度连通的点，形成一个新簇。

直观机制：DBSCAN利用核心点连接的相邻核心点链路，以及边界点的邻接，将连通结构扩展为簇的最大密度连通分量。

图论与连通分量视角

构造邻接图，其中，当时建立无向边。

定义核心点子图，其中，。

DBSCAN的簇可以描述为：

• 首先，核心点子图的每个连通分量会成为一个初始簇的骨架。
• 然后，将所有与中任意核心点邻接的非核心点（边界点）吸入该簇。
• 所得集合即为簇。

该视角下的“优化性”体现在：在给定与的约束下，簇是满足密度连通的最大集合。

任何添加点都必须保持密度连通性，否则破坏簇的定义。

等价优化目标的形式化表述（约束最大化）

尽管DBSCAN不是通过最小化某个损失函数进行优化，但可构造一个“约束最大化”问题来刻画其解的性质。

定义指示变量，表示点是否被分配到某个簇中（不含噪声），以及簇划分变量（更复杂的组合优化结构）。

为了简化，聚焦最大覆盖思想：

• 目标：在满足密度连通约束的前提下，最大化被聚类点的数量：
• 约束1（密度连通与最大性）：对每个，其为上的密度连通最大集合（可由核心点链路扩展得到）。
• 约束2（核心点阈值）：每个簇都必须包含至少一个核心点（否则不能扩展），并且核心点需满足。

上述问题的解正是DBSCAN的簇集合。

换言之，DBSCAN通过确定核心点子图的连通分量后，包含所有可加入的边界点，达到“最大覆盖”的约束最优解。

这给了DBSCAN一个优化视角：在密度约束下求最大连通覆盖。

3.4 关键性质与推理

单调性（对或）：

• 若，则，因此核心点集合对单调递增。联通分量可合并但不可能“裂解”；噪声点可能减少。
• 若，则核心点集合对单调递减；簇可能分裂、噪声可能增多。 这些性质为参数调优提供了理论依据。

最大性性质：

• 设是一个簇，若存在点使与中任一点密度连通，则。证明要点：密度连通是由核心点链路的可达性定义，若可由簇中的任一点密度可达，说明存在核心点路径将连接到簇骨架，按照簇扩展规则必须将吸入，否则不满足最大性。

边界点归属唯一性（在给定参数下）：

• 若边界点同时邻接多个簇的核心点，会产生冲突。DBSCAN的实现通常按遍历顺序选择归属，或遵循“先访问优先”。理论上，对于恰当选择与互不重叠的簇骨架，该类冲突概率较低，但在高密度交汇区域可能存在，需要在实现中进行一致性处理。

核心点链路引导的簇结构：

• 由于簇骨架由核心点连通分量决定，DBSCAN对非球形簇的识别能力来源于邻近图的几何连通性，而非中心点或均值距离。

参数选择

（min_samples）的经验法则》：

• 一般建议，其中为数据维度。这是避免退化的最小建议。
• 实务中常用（低维），维度较高时适当增大（如，可用），以提升抗噪性。

 的选取与  距离图（k-dist plot）：

定义（或），对每个点计算其近邻中最远近邻距离（即距离）：

将所有排序绘制曲线，寻找拐点（“膝点”/“肘部”）作为的候选值。拐点反映从密集区到稀疏区的过渡。

理论上，若数据近似服从均匀泊松过程，单位体积密度为，则期望在半径内的点数为：

其中为维单位球体积（如二维，三维）。希望核心点满足，则：

尽管真实数据并非均匀分布，但此公式提供粗略尺度估计，与距离图配合可提高选择质量。

度量与缩放：

标准化（Z-score）或单位方差缩放是必要的：不同量纲的特征会严重影响与。

若使用余弦距离或马氏距离，则需要对应的标准化或协方差估计步骤。

完整案例

代码中，我们构造一个二维虚拟数据集，包含形状复杂（半月形、非均匀伸缩椭圆）、多密度簇，以及背景噪声。

目标是：

• 通过DBSCAN识别簇及噪声；
• 使用距离图辅助选择；
• 对不同与进行网格搜索，分析聚类质量（如轮廓系数）；
• 在栅格上估计局部密度分布，观察DBSCAN输出与密度背景的关系；

模型训练

• 数据生成：混合多个模式（blobs、moons、anisotropic）+ 噪声。
• 预处理：标准化（StandardScaler）。
• 参数估计：使用距离图估计候选。
• 模型拟合：DBSCAN（sklearn）。
• 评估：轮廓系数（对非噪声点）。

完整代码：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors
from sklearn.metrics import silhouette_score
from matplotlib.colors import ListedColormap
import warnings
warnings.filterwarnings("ignore")

# 1) 数据集
def generate_complex_dataset


    
(random_state=42):
    rng = np.random.RandomState(random_state)
    # Blob簇（圆形簇）
    X_blob1, _ = make_blobs(n_samples=1600, centers=[(5, 5)], cluster_std=0.8, random_state=rng)
    X_blob2, _ = make_blobs(n_samples=1500, centers=[(-6, 3)], cluster_std=1.2, random_state=rng)
    
    # 半月形簇
    X_moons, y_moons = make_moons(n_samples=1600, noise=0.08, random_state=rng)
    X_moons = X_moons * [5, 3] + [0, -8]  # 放缩和平移，制造非均匀形状
    
    # 各向异性簇（线性变换）
    X_blob3, _ = make_blobs(n_samples=1700, centers=[(0, 10)], cluster_std=1.0, random_state=rng)
    # 施加线性拉伸变换
    M = np.array([[2.5, 1.2],
                  [0.3, 1.8]])
    X_aniso = X_blob3 @ M.T + [10, -5]  # 非球形
    
    # 均匀噪声
    X_noise = rng.uniform(low=-15, high=18, size=(600, 2))
    
    # 合并
    X = np.vstack([X_blob1, X_blob2, X_moons, X_aniso, X_noise])
    rng.shuffle(X)
    return X

# 2) 标准化
X = generate_complex_dataset(random_state=7)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 3) k距离图（k = min_samples）
def k_distance_plot(X, k):
    nn = NearestNeighbors(n_neighbors=k)
    nn.fit(X)
    distances, indices = nn.kneighbors(X)
    # k-距离是第k近邻的距离（含自己时需取k-1或处理，sklearn默认包含自身作为第一个邻居）
    # 由于NearestNeighbors返回含自身，k-距离取distances[:, -1]
    k_dist = np.sort(distances[:, -1])
    return k_dist

def knee_point_index(y):
    # 简易膝点检测：最大二阶差分位置
    # 更精确可用Kneedle算法，这里用较简单稳定的方法
    dy = np.gradient(y)
    d2y = np.gradient(dy)
    idx = np.argmax(d2y)
    return idx

# 4) 基于k距离图估计eps候选
m_default = 10# 初始min_samples
k_dist = k_distance_plot(X_scaled, k=m_default)
knee_idx = knee_point_index(k_dist)
eps_suggest = k_dist[knee_idx]




    
# 5) 训练DBSCAN
db = DBSCAN(eps=eps_suggest, min_samples=m_default, metric='euclidean', n_jobs=-1)
labels = db.fit_predict(X_scaled)
core_samples_mask = np.zeros_like(labels, dtype=bool)
if hasattr(db, 'core_sample_indices_'):
    core_samples_mask[db.core_sample_indices_] = True
else:
    # 在较新版本中也能取到core_sample_indices_
    pass

# 边界点与噪声点
is_noise = (labels == -1)
is_core = core_samples_mask
is_border = (~is_noise) & (~is_core)

# 6) 评估：对非噪声点计算轮廓系数
def safe_silhouette(X, labels):
    mask = labels != -1
    X_in = X[mask]
    y_in = labels[mask]
    # 至少需2个簇才能计算轮廓系数
    if len(np.unique(y_in)) 2or X_in.shape[0] 2:
        return np.nan
    try:
        return silhouette_score(X_in, y_in, metric='euclidean')
    except:
        return np.nan

sil_score = safe_silhouette(X_scaled, labels)

# 7) 参数网格搜索
eps_values = np.linspace(eps_suggest * 0.6, eps_suggest * 1.8, 20)
min_samples_values = np.arange(4, 20, 2)
S = np.zeros((len(min_samples_values), len(eps_values)))
S[:] = np.nan

for i, m in enumerate(min_samples_values):
    for j, eps in enumerate(eps_values):
        mdl = DBSCAN(eps=eps, min_samples=m, metric='euclidean', n_jobs=-1)
        yhat = mdl.fit_predict(X_scaled)
        S[i, j] = safe_silhouette(X_scaled, yhat)

# 8) 局部密度栅格图：计算每个栅格点的邻域计数（基于选择的eps）
def density_grid(X, eps, grid_size=200):
    x_min, y_min = X.min(axis=0) - 0.5
    x_max, y_max = X.max(axis=0) + 0.5
    xs = np.linspace(x_min, x_max, grid_size)
    ys = np.linspace(y_min, y_max, grid_size)
    XX, YY = np.meshgrid(xs, ys)
    grid_points = np.c_[XX.ravel(), YY.ravel()]
    nn = NearestNeighbors(radius=eps)
    nn.fit(X)
    # radius_neighbors返回每个栅格点内的邻居索引
    neighbors = nn.radius_neighbors(grid_points, return_distance=False)
    counts = np.array([len(idx) for idx in neighbors]).reshape(XX.shape)
    return XX, YY, counts

XX, YY, counts = density_grid(X_scaled, eps=eps_suggest, grid_size=250)




    
# 9) 可视化
plt.figure(figsize=(16, 12))
colors = ListedColormap([
    "#FF0054", "#00D1FF", "#00E676", "#FFD600", "#AA00FF",
    "#FF6D00", "#00BFA5", "#2962FF", "#F50057", "#00C853",
    "#D50000", "#6200EA", "#C51162", "#00B8D4", "#AEEA00",
    "#FFAB00", "#BF360C", "#1DE9B6", "#76FF03", "#304FFE"
])

# 子图1：聚类结果（核心/边界/噪声）
ax1 = plt.subplot(2, 2, 1)
unique_labels = np.unique(labels)
# 噪声颜色
noise_color = "#212121"
for lb in unique_labels:
    mask = labels == lb
    if lb == -1:
        ax1.scatter(X_scaled[mask, 0], X_scaled[mask, 1],
                    s=20, c=noise_color, marker='x', label='Noise (-1)', alpha=0.9)
    else:
        col = colors(lb % colors.N)
        ax1.scatter(X_scaled[mask & is_core, 0], X_scaled[mask & is_core, 1],
                    s=30, c=col, marker='o', edgecolor='white', linewidth=0.6, label=f'Cluster {lb} (core)', alpha=0.9)
        ax1.scatter(X_scaled[mask & is_border, 0], X_scaled[mask & is_border, 1],
                    s=25, c=col, marker='^', edgecolor='black'


    
, linewidth=0.6, label=f'Cluster {lb} (border)', alpha=0.9)

ax1.set_title(f'DBSCAN Clusters (eps={eps_suggest:.3f}, min_samples={m_default})\nSilhouette={sil_score:.3f}', fontsize=12)
ax1.set_xlabel('Feature 1 (scaled)')
ax1.set_ylabel('Feature 2 (scaled)')
ax1.grid(alpha=0.25, color='#BDBDBD', linestyle='--')
ax1.legend(loc='best', fontsize=8, ncol=2, frameon=True)

# 子图2：k距离图与膝点
ax2 = plt.subplot(2, 2, 2)
ax2.plot(k_dist, color='#D50000', linewidth=2.0, label=f'k-dist (k={m_default})')
ax2.axvline(knee_idx, color='#2962FF', linestyle='--', linewidth=1.5, label='Knee idx')
ax2.axhline(eps_suggest, color='#00C853', linestyle='--', linewidth=1.5, label=f'eps≈{eps_suggest:.3f}')
ax2.scatter([knee_idx], [eps_suggest], c='#FFD600', s=80, zorder=5, edgecolor='black', label='Suggest point')
ax2.set_title('k-Distance Plot and Knee Detection', fontsize=12)
ax2.set_xlabel('Sorted points')
ax2.set_ylabel('k-distance')
ax2.grid(alpha=0.3, color='#BDBDBD', linestyle='--')
ax2.legend(loc='best', fontsize=9)

# 子图3：参数网格热图（轮廓系数）
ax3 = plt.subplot(2, 2, 3)
im = ax3.imshow(S, aspect='auto', cmap='Spectral', origin='lower',
                extent=[eps_values[0], eps_values[-1], min_samples_values[0], min_samples_values[-1]])
# 标出当前选择
ax3.scatter([eps_suggest], [m_default], c='#FFFFFF'


    
, s=70, edgecolor='black', label='Current choice', zorder=5)
cbar = plt.colorbar(im, ax=ax3, fraction=0.046, pad=0.04)
cbar.set_label('Silhouette (non-noise)', fontsize=10)
ax3.set_title('Silhouette Heatmap over (eps, min_samples)', fontsize=12)
ax3.set_xlabel('eps')
ax3.set_ylabel('min_samples')
ax3.grid(alpha=0.2, color='#E0E0E0', linestyle=':')
ax3.legend(loc='best', fontsize=9)

# 子图4：局部密度栅格图+簇叠加
ax4 = plt.subplot(2, 2, 4)
# 背景密度
bg = ax4.contourf(XX, YY, counts, levels=15, cmap='inferno')
plt.colorbar(bg, ax=ax4, fraction=0.046, pad=0.04, label='Neighborhood count (radius=eps)')
# 叠加簇点（透明度略高）
for lb in unique_labels:
    mask = labels == lb
    if lb == -1:
        ax4.scatter(X_scaled[mask, 0], X_scaled[mask, 1], s=10, c="#00E5FF", marker='x', alpha=0.7, label='Noise overlay')
    else:
        col = colors(lb % colors.N)
        ax4.scatter(X_scaled[mask, 0], X_scaled[mask, 1], s=15, c=col, marker='o', alpha=0.6)

ax4.set_title('Local Density Field (eps-neighborhood) with Clusters Overlay', fontsize=12)
ax4.set_xlabel('Feature 1 (scaled)')
ax4.set_ylabel('Feature 2 (scaled)')
ax4.grid(alpha=0.25, color='#BDBDBD', linestyle='--')
ax4.legend(loc='best', fontsize=8)

plt.suptitle('DBSCAN Comprehensive Analysis: Clusters, k-dist, Parameter Heatmap, and Density Field', fontsize=14)
plt.tight_layout(rect=[0, 0.03, 1, 0.96])
plt.show()

图1，DBSCAN聚类结果，核心/边界/噪声：

展示了DBSCAN输出的簇结构，并区分核心点与边界点。核心点呈现为簇的骨架，边界点是附着在核心点邻域中的点；噪声点用x标记。

若观察到簇中的边界点占比很高或核心点稀少，可能说明偏小或偏大，导致簇结构过于脆弱。反之，几乎所有点都是核心点可能导致簇粘连、分辨率不足。

图2，距离图与膝点：

通过对距离排序曲线，识别拐点作为的候选值。拐点处对应从高密度到低密度的过渡。

若曲线没有清晰拐点，说明数据密度分布连续且无明显边界，可能需要借助其他方法（如OPTICS或HDBSCAN）或引入领域知识进行参数选择。

图3，参数网格热图：轮廓系数：

展示不同组合对聚类质量（轮廓系数）的影响。热图帮助我们选择改善簇间分离与簇内紧致的参数。

若热图中的高值区域十分狭窄，说明参数敏感；若高值区域较为广阔，说明DBSCAN对参数具有一定鲁棒性。注意轮廓系数只对非噪声点计算，因此结果需结合噪声占比综合评估。

图4，局部密度栅格图 + 簇叠加：

在连续空间背景中显示局部密度（以为半径计算邻域计数），并叠加簇点。能直观看到簇与密度峰谷的对应关系。

若某些簇覆盖在非常高密度区域之外（或跨越密度谷），说明过大，导致不同密度峰被连接；若密度峰未形成簇，可能是过高或过小。

总结

总的来说，DBSCAN将聚类问题转化为密度约束下的最大密度连通分量识别，即一种具有“约束最大化”意义的优化过程。

其核心点与边界点的定义使算法对噪声鲁棒且能识别非球形簇。参数选择上，与 至关重要，距离图与轮廓系数热图有助于选参。实际部署中，应关注距离度量与标准化、邻域查询加速、以及对多密度场景的策略（如自适应或层次密度方法）。

最后

感谢大家点赞或者转发本文