K-Means++ 与 K 选择

K-Means++ 是 K-Means 的改进初始化策略: 第一个质心均匀随机选取, 之后每个质心按与已选质心的最近距离平方成比例的概率采样, 其中 $D(x) = \min_{k} \Vert x - \mu_k \Vert$ 为样本 $x$ 到最近已选质心的距离: $P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}$。平方采样使初始质心大概率彼此远离, 可证期望目标满足 $\mathbb{E}[J] \le 8(\ln K + 2) \, J_{\mathrm{OPT}}$, 把随机初始化的最坏局部最优限制在最优解的 $O(\log K)$ 倍以内, 而额外开销仅一轮 $O(nKd)$ 的距离计算。K 的选择: 肘部法 (WCSS 拐点) 与轮廓系数 $s = \frac{b - a}{\max(a, b)}$ ($a$ 为簇内平均距离, $b$ 为最近邻簇平均距离, 越接近 1 越好); 对异常值敏感时改用 K-Medoids (质心取簇内实际样本点)。

所有 K-Means 训练的默认初始化 (scikit-learn 默认 k-means++), 也用于初始化 GMM 的 EM; 面试常考概率公式与“为什么用平方距离而不是均匀采样”。

均匀随机初始化可能把所有质心集中在高密度区域, 使算法收敛到很差的局部最优; K-Means++ 从概率上保证初始质心分散, 期望目标达到最优的 $O(\log K)$ 近似, 且只增加与一轮迭代相当的开销, 是时间-质量折中的经典解。

写出 K-Means++ 采样概率 $P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}$ 并解释 $D(x)$ 的含义? 为什么用距离平方而不是距离本身?

K-Means++ 相比随机初始化在期望上改善多少? 近似比 $\mathbb{E}[J] \le 8(\ln K + 2) J_{\mathrm{OPT}}$ 说明什么?

肘部法和轮廓系数如何选择 K? 轮廓系数 $s = \frac{b - a}{\max(a, b)}$ 的取值范围与解释?

K-Means 为什么对异常值敏感? K-Medoids 如何缓解? 与 K-Means 的复杂度对比?

K-Means++ 的额外时间开销是多少? 第一个质心如何选取? 与多次随机重启哪个更常用?