Stanford CS229 第 9 讲：K-Means 和高斯混合模型（2026 春季）
TL;DR
本讲座将 K‑means 呈现为硬分配聚类算法，将高斯混合模型（GMM）呈现为其软分配的概率对应物，展示了两者如何通过期望最大化（EM）循环求解，为什么初始化很重要，以及 Jensen 不等式如何为 EM 提供可求解的下界。
K‑means 算法直觉
K‑means 通过迭代地将每个点分配到最近的簇中心，然后将每个中心重新计算为其分配点的均值，来将数据划分为 K 个簇。
算法从随机初始中心 μ₁ … μ_K 开始，将每个点分配到中心最近的簇（使用欧几里得距离），将每个中心更新为其分配点的算术平均值，并重复此过程直至分配不再变化。
由于簇标签是任意的，交换所有 μ 仍可得到相同的解；重要的是中心最终位于正确的位置。
收敛、最优性和初始化
K‑means 总会终止，因为簇内平方距离之和（L₂ 目标）单调递减且有下界，因此算法会达到一个固定点，此时分配不再变化。
求此目标的全局最小值是 NP 难的，因此 K‑means 可能收敛到依赖于初始中心的次优解。
存在多个局部最小值；不同的随机初始化可能导致不同的最终聚类，这就是为什么初始化步骤至关重要。
为了改进初始化，K‑means++ 过程以一种能够保证良好近似比的方式选择初始中心；此变体是常见库（如 scikit‑learn）的默认设置。
选择簇的数量 K
选择 K 是一种建模假设：分析师必须表达对数据中存在多少 distinct 组的先验信念。
增加 K 会得到更细的划分，但较低的成本并不自动意味着更好的模型；评估更大的 K 是否真正有益需要外部知识或验证标准。
因此，选择 K 仍然是一个由问题领域引导的定性决策，而不仅仅是纯粹的算法标准。
从硬分配到软分配：高斯混合模型
GMM 用概率分配取代了 K‑means 的硬簇成员：每个点由 K 个高斯源中的一个生成，这些源的均值、协方差和混合权重未知。
前向模型假设存在一个潜在变量 Z_i，表示点 X_i 的来源；Z_i 服从 K 个来源上的多项分布，然后 X_i 从对应的高斯分布中采样。
仅给定观测点时，目标是推断出最能解释数据的高斯参数和混合权重。
高斯混合模型的期望最大化
EM 在两个步骤之间交替进行：
- E‑步：使用当前参数估计的贝叶斯法则计算点 i 来自来源 j 的后验概率 w_{ij}。
- M‑步：将每个高斯的均值、协方差和混合权重更新为点的加权平均值，其中权重为后验 w_{ij}。
当后验概率为 0 或 1 时，M‑步恰好简化为 K‑means 的更新；否则，EM 执行相同计算的软加权版本。
算法迭代直到参数估计收敛。
Jensen 不等式与 EM 下界
EM 可以看作是最大化数据对数似然的下界。
Jensen 不等式表明，对于凸函数 φ，有 𝔼[φ(X)] ≥ φ(𝔼[X])；对于凹函数则不等式方向相反。
在 E‑步中，EM 构造一个在当前参数处紧致且更易优化的代理函数；对数似然上应用 Jensen 不等式得到此代理，从而保证每次 M‑步增加（或保持不变）真实似然。
因此，EM 被保证收敛到似然的驻点，尽管不一定是全局最大值。
实际要点
- K‑means 简单且易于解释，但对初始化敏感，可能陷入劣质局部最小值。
- K‑means++ 提供了一种原则性的方法来初始化中心，具有强理论保证。
- GMM 通过建模簇成员的不确定性并利用协方差捕捉椭圆形簇，扩展了 K‑means。
- EM 为潜变量模型提供了一个通用框架；其收敛依赖于 Jensen 不等式来构造紧致的下界。
- 两种算法都要求分析师指定簇的数量 K，这是一个应由领域知识指导的建模决策。
这些概念构成了许多现代无监督学习技术的基础，并展示了算法简洁性、计算难度以及对仔细初始化和模型选择的需求之间的权衡。