DBSCAN 与层次聚类

DBSCAN 是基于密度的聚类算法, 不需预设簇数 $K$, 只需 ε 与 minPts 两个参数。ε-邻域 $N_\varepsilon(p) = \{ q \in D \mid \text{dist}(p, q) \le \varepsilon \}$; 核心点: $|N_\varepsilon(p)| \ge \text{minPts}$; 边界点: 非核心但在某核心点的 ε-邻域内; 噪声点: 两者皆非。密度直达: $p$ 为核心点且 $q \in N_\varepsilon(p)$; 密度可达: 存在核心点链 $p_1, \ldots, p_m$ 使相邻两点密度直达; 密度相连: 存在 $o$ 使 $p$、$q$ 均从 $o$ 密度可达。簇 = 密度相连的最大点集, 噪声点被显式标出。复杂度 $O(n \log n)$ (KD-Tree 加速) 或朴素 $O(n^2)$。层次聚类 (AGNES): 自底向上合并最近簇, 连接准则——单链接 (最近点距离, 易链式效应)、全链接 (最远点距离, 抗噪声)、Ward (合并后方差增量最小, 最常用), 朴素复杂度 $O(n^3)$。

地理空间聚类、图像分割、异常检测 (噪声点即离群点)、形状不规则的簇; 面试常考与 K-Means 的对比和 ε/minPts 调参。

K-Means 需预设 K、只认凸形簇且把噪声硬拉进簇; DBSCAN 无需 K, 可发现任意形状簇并自动分离噪声。代价是 ε 对密度不均的数据难以全局设定 (minPts ≈ 2×维度 是常用启发式), 高维下邻域计数退化 (维度灾难), 层次聚类则需维护 $O(n^2)$ 距离矩阵, 不适合大样本。

给出 DBSCAN 中核心点、边界点、噪声点的判定条件? ε 和 minPts 增大/减小如何改变聚类结果?

区分密度直达、密度可达、密度相连; 为什么密度可达不具备对称性而密度相连具备?

DBSCAN 与 K-Means 的核心区别? 各自适用什么数据形态? DBSCAN 对密度不均数据为何失效?

层次聚类的单链接、全链接、Ward 准则分别用什么距离? 链式效应指什么?

DBSCAN 的时间复杂度与索引加速? 高维数据下为什么 ε 难选?