线性判别分析（LDA）的类内散度与类间散度优化过程
题目描述
线性判别分析（Linear Discriminant Analysis, LDA）是一种经典的监督降维与分类算法，其核心思想是：寻找一个投影方向（或投影子空间），使得同类样本的投影尽可能聚集（类内散度小），不同类样本的投影尽可能分离（类间散度大）。本题将详细讲解如何通过数学定义类内散度矩阵（Within-class scatter matrix）与类间散度矩阵（Between-class scatter matrix），并推导如何优化投影方向以最大化类间散度与类内散度的比值。
解题过程
第一步：问题形式化
假设有 \(N\) 个样本，属于 \(C\) 个类别。第 \(i\) 类有 \(N_i\) 个样本，总样本数为 \(N = \sum_{i=1}^{C} N_i\)。每个样本是 \(d\) 维特征向量 \(\mathbf{x} \in \mathbb{R}^d\)。
目标：寻找一个投影向量 \(\mathbf{w} \in \mathbb{R}^d\)（暂时先考虑投影到一维），将样本投影到一维空间 \(y = \mathbf{w}^T \mathbf{x}\)，使得投影后类间差异最大、类内差异最小。
第二步：定义类内散度矩阵 \(S_W\)
类内散度衡量同一类别内样本的离散程度。
- 第 \(i\) 类样本的均值向量：
\[ \mathbf{\mu}_i = \frac{1}{N_i} \sum_{\mathbf{x} \in \text{Class } i} \mathbf{x} \]
- 第 \(i\) 类的散度矩阵（协方差矩阵的 \(N_i\) 倍）：
\[ S_i = \sum_{\mathbf{x} \in \text{Class } i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T \]
- 类内散度矩阵 \(S_W\)：将所有类的散度矩阵相加：
\[ S_W = \sum_{i=1}^{C} S_i = \sum_{i=1}^{C} \sum_{\mathbf{x} \in \text{Class } i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T \]
\(S_W\) 是 \(d \times d\) 对称半正定矩阵。
第三步：定义类间散度矩阵 \(S_B\)
类间散度衡量不同类别均值之间的差异。
- 全体样本的全局均值向量：
\[ \mathbf{\mu} = \frac{1}{N} \sum_{i=1}^{C} \sum_{\mathbf{x} \in \text{Class } i} \mathbf{x} = \frac{1}{N} \sum_{i=1}^{C} N_i \mathbf{\mu}_i \]
- 第 \(i\) 类均值与全局均值的偏差：\(\mathbf{\mu}_i - \mathbf{\mu}\)。
- 类间散度矩阵 \(S_B\)：用每个类别的样本数加权偏差的外积和：
\[ S_B = \sum_{i=1}^{C} N_i (\mathbf{\mu}_i - \mathbf{\mu})(\mathbf{\mu}_i - \mathbf{\mu})^T \]
\(S_B\) 也是 \(d \times d\) 对称半正定矩阵。
第四步：投影后的散度度量
样本 \(\mathbf{x}\) 投影后为 \(y = \mathbf{w}^T \mathbf{x}\)。
- 投影后的类内散度（方差之和）：
第 \(i\) 类投影后的方差为：
\[ \sum_{y \in \text{Class } i} (y - \tilde{\mu}_i)^2 = \sum_{\mathbf{x} \in \text{Class } i} (\mathbf{w}^T \mathbf{x} - \mathbf{w}^T \mathbf{\mu}_i)^2 = \mathbf{w}^T \left[ \sum_{\mathbf{x} \in \text{Class } i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T \right] \mathbf{w} = \mathbf{w}^T S_i \mathbf{w} \]
所有类投影后的类内散度总和为：
\[ \sum_{i=1}^{C} \mathbf{w}^T S_i \mathbf{w} = \mathbf{w}^T S_W \mathbf{w} \]
- 投影后的类间散度：
投影后第 \(i\) 类的均值 \(\tilde{\mu}_i = \mathbf{w}^T \mathbf{\mu}_i\)，全局均值 \(\tilde{\mu} = \mathbf{w}^T \mathbf{\mu}\)。
类间散度（加权平方和）为：
\[ \sum_{i=1}^{C} N_i (\tilde{\mu}_i - \tilde{\mu})^2 = \sum_{i=1}^{C} N_i [\mathbf{w}^T (\mathbf{\mu}_i - \mathbf{\mu})]^2 = \mathbf{w}^T \left[ \sum_{i=1}^{C} N_i (\mathbf{\mu}_i - \mathbf{\mu})(\mathbf{\mu}_i - \mathbf{\mu})^T \right] \mathbf{w} = \mathbf{w}^T S_B \mathbf{w} \]
第五步：构建优化目标（Fisher准则）
我们希望最大化类间散度与类内散度的比值：
\[J(\mathbf{w}) = \frac{\mathbf{w}^T S_B \mathbf{w}}{\mathbf{w}^T S_W \mathbf{w}} \]
这是一个广义瑞利商（Rayleigh quotient）。优化该比值等价于求解：
\[\max_{\mathbf{w}} \mathbf{w}^T S_B \mathbf{w} \quad \text{s.t.} \quad \mathbf{w}^T S_W \mathbf{w} = 1 \]
约束是为了避免缩放不影响比值。
第六步：求解最优投影方向
使用拉格朗日乘子法，构造拉格朗日函数：
\[L(\mathbf{w}, \lambda) = \mathbf{w}^T S_B \mathbf{w} - \lambda (\mathbf{w}^T S_W \mathbf{w} - 1) \]
对 \(\mathbf{w}\) 求梯度并令为零：
\[\frac{\partial L}{\partial \mathbf{w}} = 2 S_B \mathbf{w} - 2 \lambda S_W \mathbf{w} = 0 \]
得到广义特征值问题：
\[S_B \mathbf{w} = \lambda S_W \mathbf{w} \]
如果 \(S_W\) 可逆，两边左乘 \(S_W^{-1}\)：
\[S_W^{-1} S_B \mathbf{w} = \lambda \mathbf{w} \]
最优投影方向 \(\mathbf{w}\) 是矩阵 \(S_W^{-1} S_B\) 的最大特征值对应的特征向量。
第七步：扩展到多类降维（C > 2）
当类别数 \(C > 2\) 时，我们寻找一个投影矩阵 \(W \in \mathbb{R}^{d \times (C-1)}\)，将样本投影到 \(C-1\) 维空间（因为类间散度矩阵 \(S_B\) 的秩最大为 \(C-1\)）。
优化目标变为：
\[J(W) = \frac{\operatorname{tr}(W^T S_B W)}{\operatorname{tr}(W^T S_W W)} \]
最优投影矩阵 \(W\) 的列由 \(S_W^{-1} S_B\) 的前 \(C-1\) 个最大特征值对应的特征向量组成。
第八步：算法步骤总结
- 计算每个类别的均值向量 \(\mathbf{\mu}_i\) 和全局均值 \(\mathbf{\mu}\)。
- 计算类内散度矩阵 \(S_W\) 和类间散度矩阵 \(S_B\)。
- 计算矩阵 \(S_W^{-1} S_B\) 的特征值和特征向量。
- 选取前 \(C-1\) 个最大特征值对应的特征向量，构成投影矩阵 \(W\)。
- 将原始数据投影：\(\mathbf{Y} = \mathbf{X} W\)，得到降维后的数据。
核心要点
- LDA 通过最大化类间散度与类内散度的比值，寻找最优投影方向，实现监督降维。
- 类内散度矩阵 \(S_W\) 度量同类样本的紧凑性，类间散度矩阵 \(S_B\) 度量不同类中心的分离性。
- 最终的优化问题归结为求解广义特征值问题 \(S_B \mathbf{w} = \lambda S_W \mathbf{w}\)。
- LDA 假设各类样本服从同协方差的高斯分布，且在小样本或类内散度矩阵奇异时需正则化（如添加小扰动 \(S_W + \epsilon I\)）。