4.3 线性判别分析

从分类问题的决策理论（第 2.4 节）可知，最优的分类依赖于对类别的后验概率 $\operatorname{Pr}(G|X)$。假设 $f_k(x)$ 为条件于类别 $G=k$ 的变量 $X$ 的分布密度，$\pi_k$ 为类别 $k$ 的先验概率，$\sum_{k=1}^K\pi_k=1$。则根据贝叶斯公式可得：

可见从分类能力的角度而言，密度函数 $f_k(x)$ 提供的信息基本等价于条件概率 $\operatorname{Pr}(G=k|X=x)$ 可提供的信息。

很多方法都是基于对类别条件密度函数的建模，例如：

• 使用高斯密度函数的线性和二次判别分析；
• 使用更灵活的高斯混合分布，可允许非线性判别边界（第 6.8 节）；
• 最灵活的对每个类别进行一般性的非参数密度函数估计（第 6.6.2 节）；
• 朴素贝叶斯模型为上者的一个变体，假设每个类别的密度函数均为边际密度函数的乘积；即假设条件于各个类别时，输入变量之间相互独立（第 6.6.3 节）。

假设每个类别的条件概率密度为多元高斯分布：

线性判别分析（linear discriminant analysis，LDA） 就是假设所有类别都有同一个协方差矩阵 $\mathbf{\Sigma}_k=\mathbf{\Sigma},\forall k$ 的一个特例。因此在对比两个类别的密度分布时，只需要对比它们的比例的对数，即：

这是一个对 $x$ 的线性函数。其中正态分布的常数项被抵消掉；两个概率中的协方差矩阵相同，导致指数中（$x$ 的）二次项被抵消掉。这个线性的对数几率函数使类别 $k$ 和 $\ell$ 之间的判别边界对 $x$ 为线性；即满足 $\operatorname{Pr}(G=k|X=x)=\operatorname{Pr}(G=\ell|X=x)$ 的点组成了 $p$ 维空间中的一个超平面。对任意两个类别，上述结论都成立，所以所有判别边界均为线性。若将输入变量空间 $\mathbb{R}^p$ 分成不同类别的区间，那么这些区间的边界均为超平面。

图 4.5 的左图显示了三个类别两个输入变量的示例。输入变量产生于三个高斯分布，其协方差矩阵相同。椭圆形为包围了概率为 95% 的区域的等概率密度曲线，十字标记点为类别的中心点。需要注意两个类别之间的判别边界并不是其中心点连线的垂直平分线。只有当协方差矩阵 $\mathbf{\Sigma}$ 为 $\sigma^2\mathbf{I}$ 的形式，并且类别的先验概率相同时，判别边界才是其中心点连线的垂直平分线。

通过式 4.9，可见 线性判别函数（linear discriminant function）（上式）是一种模型分类规则的等价表达方式，最终的分类为 $G(x)=\arg\max_k\delta_k(x)$。

在实际操作中，高斯分布的参数为未知参数，需要用训练数据进行估计：

• $\hat{\pi}_k=N_k/N$，其中 $N_k$ 为训练样本中类别 $k$ 的观测个数；
• $\hat{\mu}_k=\sum_{g_i=k}x_i/N_k$；
• $\hat{\mathbf{\Sigma}}=\sum_{k=1}^K\sum_{g_i=k}(x_i-\hat{\mu}_k)(x_i-\hat{\mu}_k)^T/(N-K)$。

图 4.5 的右图在每个类别 30 个高斯分布样本点上的判别边界估计。图 4.1 为另一个线性判别分析的例子，不过其各个类别的条件概率分布不是高斯分布。

在两个类别的问题中，线性判别分析与线性回归分类（式 4.5）存在简单的对应关系。线性判别分析分类为类别 2 的条件为：

$$ x^T\hat{\mathbf{\Sigma}}^{-1}(\hat{\mu}_2 - \hat{\mu}_1) > \frac{1}{2} (\hat{\mu}_2 + \hat{\mu}_1)^T \hat{\mathbf{\Sigma}}^{-1} (\hat{\mu}_2 - \hat{\mu}_1) - \log (N_2 / N_1) \tag{4.11}$$

否则分类为类别 1。假设将两个类别分别编码为 +1 和 -1，则可证明最小二乘估计的系数向量与式 4.11 中的线性判别分析的方向成正比。（见练习 4.2。实际上，对两个类别任意的编码方式都会产生这种对应关系。）不过除非 $N_1=N_2$，两者的截距项不同，因此最终的判别规则也不同。

从最小二乘方法的角度来推导出的线性判别分析的方向变量并没有假设输入变量的高斯分布，所以其应用范围可延伸到非高斯分布的样本中。不过确定式 4.11 中的特定截距或判别点却是依赖于高斯分布假设的。因此不如直接根据实际样本选择最小化训练集误差的判别点。作者在实际操作中发现这种做法比较有效，但没有在学术领域中见到有人提及。

在多于两个类别时，线性判别分析与对类别的指示矩阵线性回归的方法不同，前者避免了影响后者的类别屏蔽问题（Hastie et al., 1994）。第 12.5 节中介绍的 最优评分（optimal scoring） 概念，可建立两者之间的对比关系。

回到一般的判别问题（式 4.8），如果不同类别的协方差矩阵 $\mathbf{\Sigma}_k$ 不相等，则式 4.9 中无法简化成最后的形式，即会留下无法抵消掉的 $x$ 的二次项。这便是 二次判别分析（quadratic discriminant analysis，QDA） 的判别函数：

每两个类别 $k$ 和 $l$ 之间的判别边界为一个二次函数曲线 $\{x:\delta_k(x)=\delta_\ell(x)\}$。

图 4.6 以三类别的高斯混合分布（见第 6.8 节）为例（数据与图 4.1 相同），用 $x$ 的二次函数拟合判别边界。图中展示了两种常见的二次判别边界拟合方法。右图即为上述的二次判别分析方法拟合，而左图为将原二维输入向量空间进行二次项拓展后的五维空间上的线性判别分析。通常两者的差别不大，二次判别分析为首选的方法，而扩展后的线性判别分析方法也是一个方便的替代¹。

二次判别分析的估计方法与线性判别方法类似，不过需要对每个类别分别估计协方差矩阵。当 $p$ 比较大时，这会导致参数维度大幅地增加。由于判别边界同时为密度函数中参数的函数，所以有必要清楚确定算法所用到的参数个数。线性判别分析的参数个数为 $(K-1)\times(p+1)$，因为实际上只需要先选中一个类别后（这里选择了最后一个）对比其他类别与其的判别函数大小 $\delta_k(x)-\delta_K(x)$，而其中每个差需要 $p+1$ 个参数²。与之类似的计法，二次判别分析的参数个数为 $(K-1)\times\{p(p+3)/2+1\}$。线性和二次判别分析在很多不同的分类问题中都有良好的表现。例如，STATLOG 项目³（Michie et al., 1994）的 22 个数据集中，线性判别分析在 7 个数据集上的表现列于所有方法的前三，二次判别分析在 4 个数据集上的表现列于前三，在 10 个数据集中两者至少有一个列于前三。这两个方法都被很广泛地使用，并有很多讨论线性判别分析的专著。尽管各种新的神奇的方法源源不断地出现，在实际问题中还是应尝试下这两种简单的方法。也有关于为何线性和二次判别分析的表现如此良好的讨论。实际场景中的数据不可能总会近似符合高斯分布的假设，而不同类别的密度函数中协方差矩阵相同的假设也很不可能被满足。一个可能的解释是真实的数据只能支持低复杂度的判别边界，例如线性或二次函数，而基于高斯模型的估计有比较好的稳定性。这就涉及了偏差和方差的权衡：线性判别边界的偏差换来了比其他更神奇分类方法更小的估计方差。二次判别分析中的参数个数并不少，所以这个解释的可信度不如线性判别分析，但尽管如此，其参数个数仍要比其他非参数的方法少了很多。

4.3.1 正则判别分析

Friedman (1989) 提出了一种线性和二次判别分析的折衷方法，让二次判别分析中各个类别不同的协方差矩阵向一个共同的协方差矩阵进行“收缩”。这种方法的思路与岭回归非常相似。正则化协方差矩阵的形式为：

其中 $\hat{\mathbf{\Sigma}}$ 为线性判别分析中协方差矩阵的估计。参数 $\alpha\in[0,1]$ 使得最终模型可以在线性和二次判别分析之间连续地变动，是带确认的参数。在实际应用中，可以根据在验证集上的表现或者交叉验证过程来确定 $\alpha$。

图 4.7 展示了 正则判别分析（regularized discriminant analysis，RDA） 在元音识别问题中的表现。在训练集和测试集上的错误率均随着 $\alpha$ 的增大而降低，但测试集误差在 $\alpha=0.9$ 之后迅速上升。训练集和测试集的表现差别很大，可能是由于样本中有很多重复的输出变量测量，而在训练集和测试集中的输出变量不同⁴。

另一个类似的变化是让 $\hat{\mathbf{\Sigma}}$ 向独立同方差进行“收缩”：

其中的参数 $\gamma\in[0,1]$。用 $\hat{\mathbf{\Sigma}}(\gamma)$ 替换掉式 4.13 中的 $\hat{\mathbf{\Sigma}}$，得到了一个更广义的有两个参数的协方差矩阵 $\hat{\mathbf{\Sigma}}(\alpha,\gamma)$。

第十二章会介绍其他正则化版本的线性判别分析，使之更适应于处理数字化模拟信号和图像数据。在这些场景中，存在大量的并且互相关联的特征变量，正则化可以让线性判别分析的系数在原信号的特征空间上或平滑或稀疏，从而使模型的适用性更广，系数也有更好地可解释性。第十八章会集中讨论超高维度问题，例如微阵列研究中的基因表达测量度特征变量，介绍一些基于 $\gamma=0$（式 4.14）的方法，和一些其他正则化方式的线性判别分析。

4.3.2 线性判别分析的计算

这里简要地讨论线性和二次判别分析的计算方法。通过矩阵 $\hat{\mathbf{\Sigma}}$ 或 $\hat{\mathbf{\Sigma}}_k$ 的对角线分解可以简化计算过程。假设有后者的特征值分解 $\hat{\mathbf{\Sigma}}_k=\mathbf{U}_k\mathbf{D}_k\mathbf{U}_k^T$，其中 $\mathbf{U}_k$ 为 $p\times p$ 的标准正交矩阵，$\mathbf{D}_k$ 为对角矩阵，对角线元素为正的特征值 $d_{k\ell}$。则 $\delta_k(x)$ 的项可写为（式 4.12）：

• $(x-\hat{\mu}_k)^T\hat{\mathbf{\Sigma}}_k^{-1}(x-\hat{\mu}_k)= [\mathbf{U}_k^T(x-\hat{\mu}_k)]^T \hat{\mathbf{D}}_k^{-1} [\mathbf{U}_k^T(x-\hat{\mu}_k)]$
• $\log|\hat{\mathbf{\Sigma}}_k|=\sum_\ell\log d_{k\ell}$

基于上述描述的计算过程，可以通过下面的步骤来实现线性判别分析分类算法：

• 基于共同的协方差矩阵 $\hat{\mathbf{\Sigma}}$ 对数据进行球形化（sphere）处理：$X^*\leftarrow\mathbf{D}^{-\frac{1}{2}}\mathbf{U}^TX$，其中的 $\hat{\mathbf{\Sigma}}=\mathbf{U}\mathbf{D}\mathbf{U}^T$。转化后 $X^*$ 的共同协方差矩阵就会是个单位矩阵。
• 在转化后的空间上，一个点的分类是距离其最近的类别中心点（这里忽略了类别先验概率 $\pi_k$ 的作用）。

4.3.3 降秩线性判别分析

线性判别分析是一个有约束的高斯分类器，另外它也常被用于数据的可视化，将数据中的信息投射到低维度空间上。

在 $p$ 维度的输入变量空间中，$K$ 个中心点可组成一个维度不大于 $K-1$ 的仿射子空间⁵。若 $p$ 远大于 $K$，则有可能大幅度降低问题的维度。并且在寻找距离某个点最近的中心点时，可以忽略这个点与这个子空间之间的正交距离，因为这个距离对所有中心点的距离的影响相同⁶。因此可以将这个点 $X^*$ 投影在中心点生成的子空间 $H_{K-1}$ 上，在这个子空间上比较投影点与各个中心点的距离。这便是线性判别分析中隐含的维度降低，即只需要在最高 $K-1$ 维度的空间上对数据分类。例如当 $K=3$ 时，可以将数据投射到一个二维平面上，再用颜色标记出不同的类别。投射后的图中仍然包含了线性判别分析所需要的所有信息。

对 $K>3$ 的情况，可能会在更低维度的 $L<K-1$ 子空间上投射数据，通过某种最优条件选取线性判别分析的空间 $H_L\subseteq H_{K-1}$ 。费雪（Ronald Aylmer Fisher）将“最优条件”的定义为，使中心点的投影尽可能地分散，即这几个点的方差最大。这实际上是在寻找中心点的主成分子空间（第 3.5.1 节简要地介绍了主成分分析，在第 14.5.1 节会更深入讨论）。

图 4.4 为元音识别数据在最优的二维子空间的投影图。其中的数据有十一个类别，每个类别为一个元音，输入空间为十维。这个例子中 $K-1=p$，所以中心点的子空间实际为整个输入空间，图中所示的是根据主成分选择的最优的二维子空间。维度是有序的（主成分顺序），因此可以依次地计算额外的维度。图 4.8 为另外四对坐标维度的投影图，它们也被称为 典型（canonical） 或 判别（discriminant） 变量。

综上所述，计算线性判别分析的最优子空间序列的步骤为：

• 计算 $K\times p$ 的类别中心点矩阵 $\mathbf{M}$，以及样本的共同协方差矩阵 $\mathbf{W}$（“W”取自于组内“within-class”之意）。
• 利用矩阵 $\mathbf{W}$ 的特征值分解，计算 $\mathbf{M}^*=\mathbf{M}\mathbf{W}^{-\frac{1}{2}}$。
• 计算 $\mathbf{M}^*$ 的协方差矩阵 $\mathbf{B}^*$（“B”取自于组间“between-class”之意），以及其特征值分解 $\mathbf{B}^*=\mathbf{V}^*\mathbf{D}_B{\mathbf{V}^*}^T$。矩阵 $\mathbf{V}^*$ 的列向量 $v^*_\ell$ 从左到右依次为最优子空间的坐标向量。

从中得到的第 $\ell$ 个判别变量为 $Z_\ell=v_\ell^T X$，其中 $v_\ell=\mathbf{W}^{-\frac{1}{2}}v_\ell^*$。

费雪从另一种方式得到了这个分解，而没有利用高斯分布的性质。他从下面这个问题入手：

寻找使组间方差相对于组内方差最大化的线性组合 $Z=a^TX$。

组间（between class）方差指的是类别均值 $Z$ 的方差，组内（within class）方差指的是所有类别样本混合在一起的方差。图 4.9 说明了这个最优化准则的意义。尽管两个中心点的连线方向上两个分布的均值距离最远（即最大化组间方差），但由于其协方差的性质它们的分布在这个方向的投射上有比较大的重叠。在考虑了组内协方差后，可得到使重叠区域最小的方向。

$Z$ 的组间方差为 $a^T\mathbf{B}a$，组内方差为 $a^T\mathbf{B}a$，其中的 $\mathbf{W}$ 和 $\mathbf{B}$ 分别如之前的定义。两者的和为 $\mathbf{B}+\mathbf{W}=\mathbf{T}$，$X$ 的忽略类别先验信息的整体协方差函数。

因此费雪问题可视为对 瑞利商（Rayleigh quotient） 的最大化问题：

或等价为：

这是一个广义的特征值求解问题，$a$ 的解为 $\mathbf{W}^{-1}\mathbf{B}$ 的第一个特征向量⁷。可证明（练习 4.1）最优解 $a_1$ 与第一个特征向量 $v_1$ 相等。类似地，通过在 $\mathbf{W}$ 空间上与 $a_1$ 正交的方向中对 $a_2^T\mathbf{B}a_2/a_2^T\mathbf{W}a_2$ 进行最大化，可以得到第二个方向向量 $a_2$；它的解同样为 $a_2=v_2$。以此类推。向量 $a_\ell$ 被称为 判别坐标（discriminant coordinate），注意这是与判别函数不同的概念；它也被称为 典型变量（canonical variate），因为也可通过对指示输出变量矩阵 $\mathbf{Y}$ 与 自变量矩阵 $\mathbf{X}$ 的典型相关分析推导得出。第 12.5 节会详细介绍。

本节的讨论大致可总结如下：

• 在同协方差矩阵的高斯分布假设下，分类问题可推导出线性的判别边界。分类时先将原始数据根据 $\mathbf{W}$ 球形化，再将球形空间上的点分类到与其最近（忽略 $\log\pi_k$）的中心点。
• 因为在分类时只需要对比这个点与各个类别中心点的相对距离，所以可以将这个点投射到类别中心点生成的子空间上进行对比。
• 这个子空间可以进一步降低维度，根据中心点的分散程度而选择最优的降维方向。这种维度分解与费雪提出的分解是等价的。

降维子空间的最初是作为数据降维（可视化）的工具，但也可用于解决分类问题。在上述的分类问题解决步骤中，可将与类别中心点之间距离的比较限制在指定的子空间中。可证明这实际上等同于将类别中心点限制在$\mathbb{R}^p$ 上的 $L$ 维度子空间的额外假设下的高斯分类规则。用最大似然估计拟合这个模型，再用贝叶斯公式计算后验概率，则可得到上述的分类规则（练习 4.8）。

高斯分类规则决定了在距离计算中对 $\log\pi_k$ 的修正因子。图 4.9 显示了这个修正的作用。分类的误判率决定于两个密度函数的重叠区域大小。当 $\pi_k$ 都相等时（即图中的情况），则最优的判定点为两个均值投影点的中间。当 $\pi_k$ 不同时，将判定点向较小的类别移动会降低误判率。类似于之前对两个类别的讨论，可以先用线性判别分析或其他方法得到线性的判别规则，然后再通过对训练集的误分类误差率最小化来选择判定点。

以元音识别数据为例，可说明降维限制对分类问题的作用。数据中有 11 个类别和 10 个输入变量，因此分类分析的空间有 10 个维度。在这些维度组成的子空间序列上计算训练集和测试集的误判率，图 4.10 为结果曲线。图 4.11 展示了在二维线性判别分析中的判别边界。

费雪降秩判别分析与指示输出向量的回归模型有紧密的联系。线性判别分析可看作是回归之后对 $\hat{\mathbf{Y}}^T\mathbf{Y}$ 的特征值分解。在两个类别的问题中，会存在一个判别变量，它与 $\hat{\mathbf{Y}}$ 的某一列向量完全成比例。第十二章会推导两者的关系。另外，如果用回归生成的拟合结果 $\hat{\mathbf{Y}}$ 来进行线性判别分析，其结果与在原数据中的线性判别分析一致（练习 4.3）。

本节练习

练习 4.1

广义特征值问题 $\max a^T\mathbf{B}a,\text{ s.t. }a^T\mathbf{W}a=1$ 的求解可以通过转换后成为一个标准特征值问题，说明这个过程。

练习 4.2

(Fisher, 1936; Ripley, 1996)

假设特征向量 $x\in\mathbb{R}^p$，输出变量为二分类，类别的样本量分别为 $N_1$ 和 $N_2$，并且将类别分别编码为 $-N/N_1$ 和 $N/N_2$。

1. 证明线性判别分析的规则为，当满足下式时为类别 2，否则为类别 1： $$x^T\hat{\mathbf{\Sigma}}^{-1}(\hat{\mu}_2-\hat{\mu}_1) > \frac{1}{2}(\hat{\mu}_2+\hat{\mu}_1) \hat{\mathbf{\Sigma}}^{-1} (\hat{\mu}_2-\hat{\mu}_1) - \log(N_2/N_1)$$

2. 对最小二乘准则进行最小化： $$\sum_{i=1}^N (y_i - \beta_0 - x_i^T\beta)^2 \tag{4.55}$$ 证明它的解 $\hat{\beta}$ （经过简化后）满足： $$\left[ (N-2)\hat{\mathbf{\Sigma}} + N \hat{\mathbf{\Sigma}}_B \right] \beta = N (\hat{\mu}_2-\hat{\mu}_1) \tag{4.56}$$ 其中的 $\hat{\mathbf{\Sigma}}_B=\frac{N_1N_2}{N^2}(\hat{\mu}_2-\hat{\mu}_1)(\hat{\mu}_2-\hat{\mu}_1)^T$
3. 证明 $\hat{\mathbf{\Sigma}}_B\beta$ 与 $(\hat{\mu}_2-\hat{\mu}_1)$ 的方向相同，因此： $$\hat{\beta} \propto \hat{\mathbf{\Sigma}}^{-1} (\hat{\mu}_2-\hat{\mu}_1) \tag{4.57}$$ 所以最小二乘回归的系数与线性判别分析的系数相同（只相差一个常量倍数）。
4. 证明这个结果对任意的两个类别（不同）编码方式都成立。
5. Find the solution $\hat{\beta}_0$ (up to the same scalar multiple as in (c), and hence the predicted value $\hat{f}(x)=\hat{\beta}_0+x^T\hat{\beta}$ Consider the following rule: classify to class 2 if $\hat{f}(x)>0$ and class 1 otherwise. Show this is not the same as the LDA rule unless the classes have equal numbers of observations.

练习 4.3

通过线性回归将原始的自变量 $\mathbf{X}$ 转换为 $\hat{\mathbf{Y}}$。也就是令 $\mathbf{Y}$ 为（类别）指示变量输出矩阵，$\hat{\mathbf{Y}}=\mathbf{X}(\mathbf{X}^{-1}\mathbf{X})^{-1}\mathbf{X}^T\mathbf{Y}=\mathbf{X}\hat{\mathbf{B}}$。所以对任意的输入向量 $x\in\mathbb{R}^p$，可以得到一个转换（预测）向量 $\hat{y}=\hat{\mathbf{B}}^Tx\in\mathbb{R}^K$。证明：基于 $\hat{\mathbf{Y}}$ 的线性判别分析（LDA）与在原特征空间上进行线性判别分析，结果是一样的。

练习 4.8

(Hastie and Tibshirani, 1996b)

Consider the multivariate Gaussian model X|G = k ∼ N (µ k , Σ), with the additional restriction that rank{µ k } K 1 = L < max(K − 1, p). Derive the constrained MLEs for the µ k and Σ. Show that the Bayes clas- sification rule is equivalent to classifying in the reduced subspace computed by LDA .