K-Means 算法

K-Means (K 均值) 是将 $n$ 个样本划分为 $K$ 个互斥硬簇的经典聚类算法, 通过坐标下降最小化簇内平方和 (WCSS) 目标 $J = \sum_{k=1}^{K} \sum_{x \in C_k} \Vert x - \mu_k \Vert^2$。每轮交替两步: ① 分配步 — 固定质心, 每个样本 $x$ 指派给最近质心 $c(x) = \arg\min_k \Vert x - \mu_k \Vert$; ② 更新步 — 固定分配, 质心取簇内均值 $\mu_k = \tfrac{1}{|C_k|} \sum_{x \in C_k} x$。两步都只减不增 $J$, 故必收敛, 但只能收敛到局部最优; 每轮复杂度 $O(nKd)$, 总复杂度 $O(nKdT)$ ($T$ 为迭代轮数)。

无标签数据的探索性分群 (用户/商品聚类、画像)、图像颜色量化、向量量化、作为 GMM 硬分配的特例对照; 面试常考目标函数手推、收敛性、初始化与 K 的选择。

相比层次聚类需 $O(n^2)$ 的相似度矩阵内存, K-Means 线性时间可扩展至百万级样本; 相比 GMM 无需估计协方差, 简单、快、易实现。代价是只能产出凸形 (球形) 硬簇, 对非凸簇与密度不均数据效果差, 且结果强依赖初始化 (见 K-Means++)。

检验攻克程度：针对「K-Means 算法」专属刷题排雷

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