线性判别分析（Linear Discriminant Analysis，LDA）

2023-05-16

基础不牢，地动山摇。

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的线性学习方法，它既可以用于分类问题，也可以用于有监督的特征降维。它的思想非常朴素：给定训练样本，设法将样本特征投影到一个向量上，并且希望同类样本的投影点越近越好，异类样本的投影点越远越好。在对新样本进行分类时，照样将新样本的特征投影到这个向量上，再根据投影点的位置来确定新样本的类别。那怎么投影呢，这个“投影”是怎么实现的呢？让我们先用一张图了解一下“投影”。

上面这张图告诉我们，可以用向量的内积 $\dpi{150} \tiny \boldsymbol{w}^{T}\boldsymbol{x}$ 来表示特征向量 $\tiny \boldsymbol{x}$ 在向量 $\tiny \boldsymbol{w}$ 上的投影距离（这个投影距离是垂直投影距离的 $\tiny \left \| \boldsymbol{w} \right \|$ 倍），而 $\dpi{150} \tiny \boldsymbol{w}^{T}\boldsymbol{x}=w_{1}x_{1}+w_{2}x_{2}$ ，这是一个最简单的线性模型，所以我们可以理解为：这种“投影”是通过一个线性模型来实现的；实现方法为：将样本的特征向量 $\tiny \boldsymbol{x}$ 投影到线性模型的权值向量 $\tiny \boldsymbol{w}$ 上。

1. 线性判别分析用于二分类问题

假设现在有 $\tiny N$ 个训练样本，每个样本都有 $\tiny D$ 个属性（特征）和一个类别标签。由于本节仅考虑二分类问题，所以限定类别标签只能取 $\tiny C_{1}$ 或 $\tiny C_{2}$ 。那么训练数据的形式可以如下表达（ $x_{ij}$ 代表第个样本的第维特征， $y_{i}$ 代表第个样本的类别标签）：

$(x_{11},x_{12},\cdots,x_{1D},y_{1}),(x_{21},x_{22},\cdots,x_{2D},y_{2}),\cdots (x_{N1},x_{N2},\cdots,x_{ND},y_{N})$ ，其中 $y_{i}\in\left \{ C_{1},C_{2} \right \}$ 。

为了便于使用向量运算来简化表达，将样本特征和线性模型权值写成向量形式：

$\boldsymbol{x}_{i}=\begin{pmatrix} x_{i1}\\ x_{i2}\\ \cdots\\ x_{iD}\end{pmatrix}$ ， $\boldsymbol{w}=\begin{pmatrix} w_{1}\\ w_{2}\\ \cdots\\ w_{D}\end{pmatrix}$ ；

则样本在线性模型权值向量上的投影距离可以表达为： $\boldsymbol{w}^{T}\boldsymbol{x}_{i}$ ，这是一个标量。

注意一下，这里不需要考虑偏置 $b$ 哦。具体为什么不用考虑，下面会解释。

首先我们考虑如何量化异类样本投影点之间的分离程度：

最简单的方法是将两个类别的样本各自取均值，投影到权值向量上，比较两个类别均值投影点之间的距离。两类样本（ $\tiny C_{1}$ 类和 $\tiny C_{2}$ 类）的均值向量分别为：

$\boldsymbol{m}_{C_{1}}=\frac{1}{N_{1}}\sum_{n\in C_{1}}\boldsymbol{x}_{n}$ ， $\boldsymbol{m}_{C_{2}}=\frac{1}{N_{2}}\sum_{n\in C_{2}}\boldsymbol{x}_{n}$

其中， $N_{1}$ 和 $N_{2}$ 分别是 $\tiny C_{1}$ 类和 $\tiny C_{2}$ 类的样本数量。

两类样本的均值向量在权值向量上的投影距离之差为：

$m_{C_{2}}-m_{C_{1}}=\boldsymbol{w}^{T}\boldsymbol{m}_{C_{2}}-\boldsymbol{w}^{T}\boldsymbol{m}_{C_{1}}=\boldsymbol{w}^{T}(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})$

这样表达存在一个正负号的问题，所以我们用它的平方形式 $(m_{C_{2}}-m_{C_{1}})^2$ ，即类间方差来量化异类样本之间的分离程度。

接着考虑如何量化同类样本投影点之间的分离程度：

让我们仅考虑 $\tiny C_{1}$ 类， $\tiny C_{1}$ 类中的每个样本在权值向量上都有一个投影点，所以 $\tiny C_{1}$ 类样本在权值向量上共有 $N_{1}$ 个投影点。而每个投影点与 $\tiny C_{1}$ 类样本的均值向量的投影点之间会有一个距离，所以 $\tiny C_{1}$ 类样本共会产生 $N_{1}$ 个这样的距离，将这 $N_{1}$ 个距离加起来，就可以量化 $\tiny C_{1}$ 类样本投影点之间的分离程度， $\tiny C_{2}$ 类同理。我们还是用投影距离之差的平方来量化，表达式如下：

$s_{C_{1}}^2=\sum_{n\in C_{1}}(\boldsymbol{w}^{T}\boldsymbol{x}_{n}-m_{C{1}})^2$ ， $s_{C_{2}}^2=\sum_{n\in C_{2}}(\boldsymbol{w}^{T}\boldsymbol{x}_{n}-m_{C{2}})^2$

其中， $s_{C_{1}}^2$ 和 $s_{C_{2}}^2$ 分别叫做 $\tiny C_{1}$ 类和 $\tiny C_{2}$ 类的类内方差。

我们用 $s_{C_{1}}^2+s_{C_{2}}^2$ 来表示整个数据集的总的类内方差，用它来量化同类样本之间的分离程度。

最后综合考虑类间方差和类内方差：

既然我们希望异类样本离得远，同类样本尽量近，那我们将二者综合考虑，使类间方差与类内方差的比值尽可能大即可。定义想要最大化的目标函数为：

$J(\boldsymbol{w})=\frac{(m_{C_{2}}-m_{C_{1}})^2}{s_{C_{1}}^{2}+s_{C_{2}}^{2}}$

现在大家知道线性判别分析为什么不考虑偏置 $b$ 了吗，因为经过刚刚对类间方差和类内方差的计算，你会发现，就算考虑了，最后都会被消掉的呀。所以偏置 $b$ 在这里面不起作用，还不如从一开始就不考虑，还能让计算简单点。

将 $J(\boldsymbol{w})$ 如下图展开来写：

定义类间散度矩阵：

$\boldsymbol{S}_{B}=(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})^T$

定义类内散度矩阵：

$\boldsymbol{S}_{W}=\sum_{n\in C_{1}}(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{1}})(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{1}})^T+\sum_{n\in C_{2}}(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{2}})(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{2}})^T$

所以 $J(\boldsymbol{w})$ 可以简写为：

$J(\boldsymbol{w})=\frac{\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w}}{\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w}}$

这就是线性判别分析欲要最大化的目标，即 $\boldsymbol{S}_{W}$ 与 $\boldsymbol{S}_{B}$ 的“广义瑞利商”。

对 $J(\boldsymbol{w})$ 关于 $\boldsymbol{w}$ 求导，并令导数为0，计算如下：

$\tiny \frac{\partial J(\boldsymbol{w})}{\partial \boldsymbol{w}}=\frac{(\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w})'\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w}-\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w}(\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w})'}{(\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w})^2}=\frac{\boldsymbol{S}_{B}\boldsymbol{w}\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w}-\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w}\boldsymbol{S}_{W}\boldsymbol{w}}{(\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w})^2}=0$

由此可得：

$\boldsymbol{S}_{B}\boldsymbol{w}(\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w})=(\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w})\boldsymbol{S}_{W}\boldsymbol{w}$

可以有两种思路来求 $\boldsymbol{w}$ ，

思路①：

思路②：

$\boldsymbol{S}_{B}\boldsymbol{w}(\boldsymbol{w}^{T}\boldsymbol{S}_{W}\boldsymbol{w})=(\boldsymbol{w}^{T}\boldsymbol{S}_{B}\boldsymbol{w})\boldsymbol{S}_{W}\boldsymbol{w}$ 这个式子中，括号括起来的部分都是标量因子，我们可以将标量因子简化，简写为：

$\boldsymbol{S}_{B}\boldsymbol{w}=\lambda \boldsymbol{S}_{W}\boldsymbol{w}$

又根据类内散度矩阵 $\boldsymbol{S}_{B}=(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})^T$ ，可得 $\boldsymbol{S}_{B}\boldsymbol{w}=(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}}){\color{Red} (\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})^T\boldsymbol{w}}$

红色的部分是标量因子，我们也可以将标量因子简化，可得：

$\boldsymbol{S}_{B}\boldsymbol{w}=\eta (\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})$

综合 $\boldsymbol{S}_{B}\boldsymbol{w}=\eta (\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})$ 和 $\boldsymbol{S}_{B}\boldsymbol{w}=\lambda \boldsymbol{S}_{W}\boldsymbol{w}$ ，可得：

$\boldsymbol{w}=\frac{\eta }{\lambda }\boldsymbol{S}_{W}^{-1}(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})$

需要注意的是，我们并不关心 ${\color{Red} }$ $\boldsymbol{w}$ 的大小，只关心它的方向，因此我们不妨设前面的标量系数为1，则：

${\color{Red} \boldsymbol{w}=\boldsymbol{S}_{W}^{-1}(\boldsymbol{m}_{C_{2}}-\boldsymbol{m}_{C_{1}})}$

得到 $\boldsymbol{w}$ 之后，我们就可以根据输入样本 $\boldsymbol{x}$ 得到投影距离 $\boldsymbol{w}^{T}\boldsymbol{x}$ ，接着我们可以选一个阈值，将样本的投影距离进行分类。常用的阈值为两类样本的均值向量的投影距离的平均值，即：

$threshold=\frac{m_{C_{1}}+m_{C_{2}}}{2}=\frac{\boldsymbol{w}^{T}\boldsymbol{m}_{C_{1}}+\boldsymbol{w}^{T}\boldsymbol{m}_{C_{2}}}{2}$

我们还可以从特征降维的角度理解线性判别分析用于二分类时的情况：使用一个线性模型将样本的 $\tiny D$ 维特征降到一维，即降成一个标量，这个标量代表的是特征向量在权值向量上的投影距离（这个投影距离在数值上等于垂直投影距离的 $\tiny \left \| \boldsymbol{w} \right \|$ 倍）。由于线性模型是在有类别监督的条件下获得的，所以可以认为降维后得到的标量含有分类信息。

2. 线性判别分析用于多分类问题

假设现在有 $\tiny N$ 个训练样本，每个样本都有 $\tiny D$ 个属性（特征）和一个类别标签。假设样本共有 $K$ 类，那么训练数据的形式可以如下表达（ $x_{ij}$ 代表第个样本的第维特征， $y_{i}$ 代表第个样本的类别标签）：

$(x_{11},x_{12},\cdots,x_{1D},y_{1}),(x_{21},x_{22},\cdots,x_{2D},y_{2}),\cdots (x_{N1},x_{N2},\cdots,x_{ND},y_{N})$ ，其中 $y_{i}\in \left \{ C_{1},C_{2},\cdots, C_{K}\right\}$ 。

从分类角度思考：

在这里提供一个思路：我们可以对 $K$ 类样本每两类都训练一个二分类模型，故共可得到 $\frac{K(K-1)}{2}$ 个二分类模型。在对新样本进行分类时，用这 $\frac{K(K-1)}{2}$ 个模型都预测一次，共可获得 $\frac{K(K-1)}{2}$ 个结果，选择结果中最多的那个类别作为最终预测结果。

从特征降维角度思考：

在之前的二分类问题中，我们使用一个线性变换将 $\tiny D$ 维特征降到一维，现在类别数多了，投影成一维标量也许并不足以提供充足的分类信息。所以我们使用 $\tilde{D}$ 个线性变换，每个线性变换都能将特征降到一维， $\tilde{D}$ 个线性变换可以将特征降到 $\tilde{D}$ 维。为了方便计算，将 $\tilde{D}$ 个线性变换的权值向量放到一个投影矩阵 $\boldsymbol{W}$ 中：

$\boldsymbol{W}=\left \{ \boldsymbol{w}_{1},\boldsymbol{w}_{2},\cdots, \boldsymbol{w}_{\tilde{D}}\right \}=\begin{pmatrix} w_{11} & w_{21}& \cdots& w_{\tilde{D}1}\\ w_{12}& w_{22}& \cdots& w_{\tilde{D}2}\\ \vdots & \vdots& \ddots &\vdots \\ w_{1D}& w_{2D}& \cdots& w_{\tilde{D}D}\end{pmatrix}$ ；

式中， $\boldsymbol{w}_{i}$ 表示第 $i$ 个线性变换的权值向量， $w_{ij}$ 表示 $\boldsymbol{w}_{i}$ 的第 $j$ 个权值。

将样本特征写成向量形式：

$\boldsymbol{x_{i}}=\begin{pmatrix} x_{i1}\\ x_{i2}\\ \cdots\\ x_{iD}\end{pmatrix}$ ；

那么，样本在这 $\tilde{D}$ 个线性变换上投影的结果可以表达为：

$\boldsymbol{y}_{i}=\begin{pmatrix} y_{i1}\\ y_{i2}\\ \cdots\\ y_{i\tilde{D}}\end{pmatrix}=\begin{pmatrix} w_{11} & w_{21}& \cdots& w_{\tilde{D}1}\\ w_{12}& w_{22}& \cdots& w_{\tilde{D}2}\\ \vdots & \vdots& \ddots &\vdots \\ w_{1D}& w_{2D}& \cdots& w_{\tilde{D}D}\end{pmatrix}^{T}\begin{pmatrix} x_{i1}\\ x_{i2}\\ \cdots\\ x_{iD}\end{pmatrix}=\boldsymbol{W}^{T}\boldsymbol{x}_{i}$

我们的目标就是要求得这个投影矩阵 $\boldsymbol{W}$ 。

定义多分类任务的全局散度矩阵=类内散度矩阵+类间散度矩阵：

$\boldsymbol{S}_{T}=\boldsymbol{S}_{B}+\boldsymbol{S}_{W}=\sum_{i=1}^{N}(\boldsymbol{x}_{i}-\boldsymbol{m})(\boldsymbol{x}_{i}-\boldsymbol{m})^{T}$

式中， $\boldsymbol{m}=\frac{1}{N}\sum_{n=1}^{N}\boldsymbol{x}_{n}$ 代表所有样本的均值矩阵；

定义多分类任务的类内散度矩阵：

总的类内散度矩阵等于每一类的类内散度矩阵之和，即：

$\boldsymbol{S}_{W}=\sum_{k=1}^{K}\boldsymbol{S}_{k}$

式中： $\boldsymbol{S}_{k}=\sum_{n\in C_{k}}(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{k}})(\boldsymbol{x}_{n}-\boldsymbol{m}_{C_{k}})^T$ ，代表第 $k$ 类的类内散度矩阵；

式中， $\boldsymbol{m}_{C_{k}}=\frac{1}{N_{C_{k}}}\sum_{n\in C_{k}}\boldsymbol{x}_{n}$ ，代表第 $k$ 类的特征均值向量， $N_{C_{k}}$ 代表第 $k$ 类的样本数。

计算多分类任务的类间散度矩阵：

根据上图的计算，得到多分类任务的类间散度矩阵为：

$\boldsymbol{S}_{B}=\sum_{k=1}^{K}N_{C_{k}}(\boldsymbol{m}_{C_{k}}-\boldsymbol{m})(\boldsymbol{m}_{C_{k}}-\boldsymbol{m})^T$

与之前一样，我们想构造一个标量，当类间差异大且类内差异小时，这个标量会较大。构造这个标量有许多种可选择的方式，常见的一种选择是最大化目标函数：

$J(\boldsymbol{W})=\frac{tr(\boldsymbol{W}^{T}\boldsymbol{S}_{B}\boldsymbol{W})}{tr(\boldsymbol{W}^{T}\boldsymbol{S}_{W}\boldsymbol{W})}$ ；

这个欲要最大化的目标函数也可以通过对 $\boldsymbol{S}_{W}^{-1}\boldsymbol{S}_{B}$ 求特征值和特征向量来求解，得到特征值和特征向量后，将非零特征值从大到小排个序。由于我们将向量投影到 $\tilde{D}$ 维，所以按从大到小选前 $\tilde{D}$ 个非零特征值，它们对应的特征向量即可组成投影矩阵 $\boldsymbol{W}$ ，用这个投影矩阵就可以将 $\tiny D$ 维特征降到 $\tilde{D}$ 维。为什么一定要非零特征值呢，因为零特征值无法使目标函数变大，所以它对应的特征向量也起不到分类作用，放进去也没用。

在这里需要注意一下， $\tilde{D}$ 始终满足 $\tilde{D}\leq K-1$ ，即我们最多只能将特征维度降到 $K-1$ 维，即 $\boldsymbol{S}_{W}^{-1}\boldsymbol{S}_{B}$ 最多只有 $K-1$ 个非零特征值。证明如下：

参考：

https://blog.csdn.net/itplus/article/details/12038441

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)