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++ 与 K 选择」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。