Fischer线性判别分析（LDA）的求解算法
题目描述
线性判别分析（Linear Discriminant Analysis, LDA）是一种经典的监督降维和分类算法。它的核心思想是：对于一个包含多个类别的数据集，寻找一个最优的线性投影方向（或投影子空间），使得投影后，同类样本尽可能聚集（类内散度小），不同类样本尽可能分离（类间散度大）。在分类问题中，这个投影方向可用于构建线性分类器；在降维中，它用于提取最有判别力的特征。Fischer的LDA通常特指二分类情况，其目标是找到一个一维投影向量 \(\mathbf{w}\)，最大化一个称为“广义Rayleigh商”的准则函数 \(J(\mathbf{w})\)。
给定两个类别的样本集 \(C_1\) 和 \(C_2\)，每个样本是一个 \(n\) 维向量。设两个类别的样本数分别为 \(N_1, N_2\)，总样本数 \(N = N_1 + N_2\)。它们的均值向量为 \(\mathbf{\mu}_1, \mathbf{\mu}_2\)，类内散度矩阵（within-class scatter matrix）定义为 \(\mathbf{S}_W = \sum_{i=1}^2 \sum_{\mathbf{x} \in C_i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T\)。类间散度矩阵（between-class scatter matrix）定义为 \(\mathbf{S}_B = (\mathbf{\mu}_1 - \mathbf{\mu}_2)(\mathbf{\mu}_1 - \mathbf{\mu}_2)^T\)。Fischer准则函数为：
\[J(\mathbf{w}) = \frac{\mathbf{w}^T \mathbf{S}_B \mathbf{w}}{\mathbf{w}^T \mathbf{S}_W \mathbf{w}} \]
我们的目标是求解使 \(J(\mathbf{w})\) 最大的投影向量 \(\mathbf{w}\)。
解题过程详解
步骤1：理解优化问题的数学形式
我们要最大化广义Rayleigh商 \(J(\mathbf{w})\)。注意，\(J(\mathbf{w})\) 的值与 \(\mathbf{w}\) 的缩放无关，即对于任意非零标量 \(k\)，\(J(k\mathbf{w}) = J(\mathbf{w})\)。因此，我们可以固定分母（例如，令 \(\mathbf{w}^T \mathbf{S}_W \mathbf{w} = 1\)），将问题转化为一个带约束的优化问题：
\[\max_{\mathbf{w}} \mathbf{w}^T \mathbf{S}_B \mathbf{w} \quad \text{s.t.} \quad \mathbf{w}^T \mathbf{S}_W \mathbf{w} = 1 \]
这是一个典型的广义特征值问题的等价形式。
步骤2：构建拉格朗日函数
引入拉格朗日乘子 \(\lambda\)，构建拉格朗日函数：
\[L(\mathbf{w}, \lambda) = \mathbf{w}^T \mathbf{S}_B \mathbf{w} - \lambda (\mathbf{w}^T \mathbf{S}_W \mathbf{w} - 1) \]
步骤3：求解极值条件
对 \(\mathbf{w}\) 求梯度并令其为零：
\[\frac{\partial L}{\partial \mathbf{w}} = 2\mathbf{S}_B \mathbf{w} - 2\lambda \mathbf{S}_W \mathbf{w} = 0 \]
这给出了关键方程：
\[\mathbf{S}_B \mathbf{w} = \lambda \mathbf{S}_W \mathbf{w} \quad \text{或} \quad \mathbf{S}_W^{-1} \mathbf{S}_B \mathbf{w} = \lambda \mathbf{w} \]
注意，这个方程形如广义特征值问题 \(\mathbf{S}_B \mathbf{w} = \lambda \mathbf{S}_W \mathbf{w}\)。如果 \(\mathbf{S}_W\) 非奇异（通常是可逆的，除非样本维度远大于样本数或样本共线），它可以转化为标准特征值问题 \(\mathbf{S}_W^{-1} \mathbf{S}_B \mathbf{w} = \lambda \mathbf{w}\)。
步骤4：分析矩阵 \(\mathbf{S}_B\) 的特殊结构，简化求解
观察类间散度矩阵 \(\mathbf{S}_B = (\mathbf{\mu}_1 - \mathbf{\mu}_2)(\mathbf{\mu}_1 - \mathbf{\mu}_2)^T\)。这是一个秩为1的矩阵，由向量 \(\mathbf{d} = \mathbf{\mu}_1 - \mathbf{\mu}_2\) 的外积构成。
因此，对于任意向量 \(\mathbf{w}\)，有 \(\mathbf{S}_B \mathbf{w} = (\mathbf{d}^T \mathbf{w}) \mathbf{d}\)。即，\(\mathbf{S}_B\) 作用在 \(\mathbf{w}\) 上，结果总是与 \(\mathbf{d}\) 共线。
将 \(\mathbf{S}_B \mathbf{w} = (\mathbf{d}^T \mathbf{w}) \mathbf{d}\) 代入广义特征值方程 \(\mathbf{S}_B \mathbf{w} = \lambda \mathbf{S}_W \mathbf{w}\)：
\[(\mathbf{d}^T \mathbf{w}) \mathbf{d} = \lambda \mathbf{S}_W \mathbf{w} \]
这表明，解向量 \(\mathbf{w}\) 满足 \(\mathbf{S}_W \mathbf{w}\) 与 \(\mathbf{d}\) 共线。因此，\(\mathbf{w}\) 必然与 \(\mathbf{S}_W^{-1} \mathbf{d}\) 共线（前提 \(\mathbf{S}_W\) 可逆）。我们可以直接写出解的形式：
\[\mathbf{w} \propto \mathbf{S}_W^{-1} \mathbf{d} = \mathbf{S}_W^{-1} (\mathbf{\mu}_1 - \mathbf{\mu}_2) \]
比例系数（即 \(\mathbf{w}\) 的长度或正负号）不影响投影后的分类决策（可通过调整分类阈值处理），所以通常取 \(\mathbf{w} = \mathbf{S}_W^{-1} (\mathbf{\mu}_1 - \mathbf{\mu}_2)\) 作为最优投影方向。
步骤5：算法实现步骤
- 计算各类均值：分别计算两个类别的样本均值向量 \(\mathbf{\mu}_1, \mathbf{\mu}_2\)。
- 计算类内散度矩阵 \(\mathbf{S}_W\)：
\[ \mathbf{S}_W = \sum_{i=1}^2 \sum_{\mathbf{x} \in C_i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T \]
在实际计算中，为了避免遍历所有样本，可以提前对每个类别计算其协方差矩阵（未除以样本数的散布矩阵）。设类别 $ C_i $ 的散布矩阵为 $ \mathbf{S}_i = \sum_{\mathbf{x} \in C_i} (\mathbf{x} - \mathbf{\mu}_i)(\mathbf{x} - \mathbf{\mu}_i)^T $，则 $ \mathbf{S}_W = \mathbf{S}_1 + \mathbf{S}_2 $。
- 计算均值差向量：\(\mathbf{d} = \mathbf{\mu}_1 - \mathbf{\mu}_2\)。
- 求解线性方程组：计算 \(\mathbf{w} = \mathbf{S}_W^{-1} \mathbf{d}\)。在数值计算中，这通常通过求解线性方程组 \(\mathbf{S}_W \mathbf{w} = \mathbf{d}\) 来完成，而不是显式求逆。可以使用稳定高效的线性方程组求解器，如Cholesky分解（因为 \(\mathbf{S}_W\) 是对称正定的，只要样本不共线）、LU分解等。
- （可选）投影与分类：对于一个新样本 \(\mathbf{x}_{\text{new}}\)，计算其投影值 \(y = \mathbf{w}^T \mathbf{x}_{\text{new}}\)。可以设定一个阈值（例如，使用两类投影均值的平均值或通过优化确定）来进行分类。
步骤6：深入理解解的几何与统计意义
- 几何意义：最优投影方向 \(\mathbf{w} = \mathbf{S}_W^{-1} (\mathbf{\mu}_1 - \mathbf{\mu}_2)\) 可以看作是对均值差向量 \(\mathbf{d}\) 进行了一个“白化”变换。\(\mathbf{S}_W^{-1}\) 起到的作用是消除不同特征维度之间的相关性以及尺度差异，使得在新的度量下，两类均值之间的距离（马氏距离）最大化。
- 与贝叶斯决策的联系：在假设两类数据都服从相同协方差矩阵的高斯分布时，LDA的最优投影方向与贝叶斯最优分类器（线性判别函数）是一致的。
- 多类扩展：对于类别数 \(C > 2\) 的情况，LDA的目标是寻找一个 \((C-1)\) 维的子空间。此时需要求解广义特征值问题 \(\mathbf{S}_B \mathbf{v} = \lambda \mathbf{S}_W \mathbf{v}\)，选取对应于前 \((C-1)\) 个最大广义特征值的广义特征向量作为投影矩阵的列。其中 \(\mathbf{S}_B\) 变为所有类相对于总体均值的散布矩阵之和。
总结
Fischer LDA的核心是通过最大化类间散度与类内散度的比值，导出了一个简洁的解析解 \(\mathbf{w} \propto \mathbf{S}_W^{-1}(\mathbf{\mu}_1 - \mathbf{\mu}_2)\)。其算法步骤清晰，主要计算量在于计算 \(\mathbf{S}_W\) 和求解一个线性方程组。它是连接统计、代数和优化理论的经典范例。