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 目标函数 $J = \sum_{k} \sum_{x \in C_k} \Vert x - \mu_k \Vert^2$? 为什么分配步与更新步能保证 $J$ 单调不增、算法必收敛?

推导质心更新公式 $\mu_k = \tfrac{1}{|C_k|} \sum_{x \in C_k} x$: 固定分配后对 $\mu_k$ 求导置零得最优解; K-Means 是凸优化吗?

K-Means 与 GMM 的区别 (硬分配 vs 软分配)? K-Means 与 KNN 有什么本质不同?

K-Means 为什么只能收敛到局部最优? 初始化如何影响结果? 缓解手段有哪些 (K-Means++、多次随机重启、K-Medoids)?

K-Means 的时间复杂度是多少? 如何选 K (肘部法、轮廓系数)? 为什么对异常值敏感、对非凸簇失效?