第 9–12 章 · 聚类、EM 与隐马尔可夫

收官四章是无监督与序列标注的领地：K-means/层次聚类、GMM 与 EM（泛化版）、隐马尔可夫模型的三大问题、以及统计学习方法的总结展望。

聚类的方法谱系

• K-means：目标 $\min\sum_n\|x_n - \mu_{c(n)}\|^2$，交替"分配-更新"直到收敛（局部最优，多初始化）；k 值用肘部法/轮廓系数/ Gap 统计量；球形簇假设的局限；
• 层次聚类：凝聚式（自底向上合并，按最大/平均/ Ward 链接度量簇间距离）产出 dendrogram，切割高度定簇数——不需要预设 k；
• 密度聚类（DBSCAN：核心点 + 可达性，找任意形状簇、抗噪）与谱聚类（相似度图 + 拉普拉斯矩阵特征向量）作为进阶工具的定位。

EM 的推广视角

第 9 章（第二版）把 EM 放进更一般的框架：观测数据的对数似然 = 完全数据似然的期望下界；E 步求后验、M 步更新参数的迭代与单调收敛证明（Jensen 不等式版）；混合模型的贝叶斯化（Dirichlet 先验）预告无限混合（非参数贝叶斯）。"隐变量 + 交替优化"是所有 EM 族的共同基因：Baum-Welch、t-SNE 的早期形式、因子分析皆是。

隐马尔可夫模型：三大问题

HMM $(\pi, A, B)$：隐藏状态链 + 观测发射。

HMM 的两大假设（马尔可夫性、观测条件独立）既是它的效率来源也是它的表达上限——现代 CRF（判别式序列标注）正是放松观测独立假设的后继。

• 概率计算（前向-后向算法）：$\alpha_t(j) = P(o_1..t, q_t = j)$ 递推，$O(TN^2)$——不用枚举 $N^T$ 条路径；
• 学习（Baum-Welch = EM）：E 步算 $\gamma_t(j)$（状态后验）与 $\xi_t(i,j)$（转移后验），M 步按计数更新 $\pi, A, B$（含平滑防零）；
• 解码（Viterbi）：动态规划找最优状态路径 $\delta_t(j) = \max_i\delta_{t-1}(i)a_{ij}b_j(o_t)$——序列标注（分词、词性标注）的标准引擎。

老师的提醒

• 聚类结果的评价没有金标准：内部指标（轮廓）+ 业务解释 + 稳定性（重抽样聚类一致度）三线合参。
• 实现 Viterbi 的两个纪律：概率全程取对数（连乘变累加防下溢）、边界初始化（$\delta_1 = \pi_i b_i(o_1)$）别写错。

自检

• K-means 的目标函数与收敛性质？
• 前向算法的递推式与复杂度？
• Baum-Welch 的 E/M 步分别更新什么？

更深一层：聚类没有"标准答案"是哲学不是缺陷

聚类（K-means/层次/DBSCAN/谱）的评价没有金标准——这不是方法缺陷而是问题的本性：没有标签就没有"正确"的划分。评估三件套（内部指标如轮廓系数 + 业务解释 + 稳定性重抽样一致性）是唯一现实的标准。K-means 的球形簇假设（球形等方差）是它的隐藏边界——簇形状不规则时立刻换 DBSCAN（密度可达找任意形状）或谱聚类（相似度图 + 拉普拉斯特征向量）。聚类方法的选择 = 对"簇的形状"的先验假设——这句话是聚类工程师的护身符。

EM 的推广视角把 K-means 与 GMM 放进同一坐标系：K-means = 球形等方差 GMM 的硬 EM——聚类结果的差异大时先怀疑数据不是球形簇。"隐变量 + 交替优化"是所有 EM 族的共同基因。

推导细读：隐马尔可夫三大问题的"分工"

HMM 三大问题的分工要刻在脑子里：概率计算（前向-后向算法——给定模型，观测序列的概率 $O(TN^2)$ 替代 $N^T$ 枚举）；学习（Baum-Welch = EM——从数据估参数）；解码（Viterbi——动态规划找最优状态路径）。三大问题 = 三个算法——前向-后向解决"评估"、EM 解决"学习"、Viterbi 解决"预测"。序列标注（分词、词性标注）的标准引擎是 Viterbi + 平滑（防零概率）。HMM 的两大假设（马尔可夫性、观测条件独立）既是效率来源也是表达上限——现代 CRF（判别式序列标注）正是放松观测独立假设的后继。

在真实世界里：HMM 与序列模型的"现代位置"

HMM 在现代的定位：被深度学习序列模型（RNN/Transformer）大幅超越，但在小数据 + 需要可解释转移结构的场景仍有位置（生物信息学的基因预测、语音识别的声学模型骨架）。学习 HMM 的价值不在工具而在概念：马尔可夫性、隐藏状态、发射概率、动态规划解码——这些概念是理解 CRF、RNN-T、甚至强化学习（部分可观测 MDP）的公共地基。HMM 是"序列建模"这门课的字母表。

专题深入：聚类的"度量危机"与 EM 完整版

第九-十章的聚类部分有两个隐藏深坑。度量危机：K-means 隐含欧氏度量 + 等方差球形簇假设——长条形簇、密度不均、非凸流形全部失败；DBSCAN 的密度语言（ε-邻域 + MinPts，核心点/边界点/噪声点三分）能挖任意形状且显式输出噪声——ε 与 MinPts 用 k-距离图拐点选；层次聚类的树状图保留全部粒度（凝聚型 + 链接准则：single 链条效应、complete 过保守、Ward 方差最小——Ward 与 K-means 的目标函数相通）。聚类的"无真值评估"哲学：内部指标（轮廓系数、CH 指数）与业务验证（簇画像可执行 = 好聚气的最终标准）。第十章 EM 已在 PRML 层深挖，李航版重点在 GMM 的具体公式与硬/软分配对照——K-means 是 EM 在 σ→0 极限的硬分配版（两章互为注脚）。

推导细读：HMM 的"三问题完整解"完整版

第十章 HMM 的三问题完整推导是本章皇冠：概率计算（前向算法 $\alpha_t(j) = [\sum_i \alpha_t(i)a_{ij}]b_j(o_t)$——动态规划把 $O(N^T T)$ 压到 $O(N^2T)$；后向算法对称补位）；学习（Baum-Welch = EM on HMM：E 步算 $\gamma_t(i)$ 与 $\xi_t(i,j)$、M 步重估 $a_{ij} = \frac{\sum_t \xi_t(i,j)}{\sum_t\gamma_t(i)}$——监督版直接计数、非监督版 EM 迭代）；解码（Viterbi 算法：$\delta_t(j) = \max_i[\delta_{t-1}(i)a_{ij}]b_j(o_t)$ + 回溯指针——最优路径的动态规划，不是贪心）。平滑的生死攸关（转移概率零元素杀死前向算法——拉普拉斯或 Good-Turing 平滑；发射概率用 GMM/高斯的连续版——GMM-HMM 的语音时代）。HMM 的局限（马尔可夫性 + 观测独立假设）引出 MEMM/CRF 的改进——判别式序列模型的登场理由。

工程案例细节：序列与聚类的产业出口工程版

九-十章的工程出口：聚类的产业用法（用户分层的 K-means + 簇画像、图像主色提取、GPS 轨迹的 DBSCAN 停留点检测——"先聚类再画像"是增长团队的月度仪式）；异常检测的三连（GMM 密度、DBSCAN 噪声点、孤立森林——无监督异常检测的组合拳）；HMM 的存量与转型（分词工具（jieba 的 HMM 模式处理未登录词）、语音的音素对齐（Kaldi 的 GMM-HMM 对齐仍是 ASR 训练管线一段）、基因序列的 CpG 岛检测——HMM 从前台退到基建）；关键词与主题的流水线（TF-IDF + GMM/LDA 的文本专题监测——舆情与情报系统的标配）；聚类的工程陷阱清单（特征标准化、K 的肘部法 + 业务上限、随机种子敏感性——无监督实验必须固定种子跑多遍）。"聚类找结构、HMM 找时序规律"是无监督世界的两大探针。