机器学习算法（四）：线性判别分析（LDA）

目录1LDA概念2 二分类求解w2.1 解一2.2解二3多类LDA原理4LDA算法流程5LDA算法小结1LDA概念线性分类器最简单的就是LDA，它可以看做是简化版的SVM。LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种supervised learning监督学习。LDA的原理是，将带上...

意念回复

10369人浏览 · 2018-09-01 14:08:02

意念回复 · 2018-09-01 14:08:02 发布

1 LDA概念

LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种supervised learning。有些资料上也称为是Fisher’s Linear Discriminant，因为它被Ronald Fisher发明自1936年。LDA是在目前机器学习、数据挖掘领域经典且热门的一个算法，据我所知，百度的商务搜索部里面就用了不少这方面的算法。

相比于PCA，LDA可以作为一种有监督的降维算法。在PCA中，算法没有考虑数据的标签（类别），只是把原数据映射到一些方差比较大的方向上而已。

假设用不同的颜色标注C1、C2两个不同类别的数据，如图4.4所示。根据PCA 算法，数据应该映射到方差最大的那个方向，亦即y轴方向。但是，C1，C2两个不同类别的数据就会完全混合在一起，很难区分开。所以，使用PCA算法进行降维后再进行分类的效果会非常差。但是，如果使用LDA算法，数据会映射到x轴方向。那么，LDA算法究竟是如何做到这一点的呢？

2 二分类求解w

LDA首先是为了分类服务的，因此只要找到一个投影方向ω，使得投影后的样本尽可能按照原始类别分开。我们不妨从一个简单的二分类问题出发，有C1、C2。两个类别的样本，两类的均值分别为。我们希望投影之后两类之间的距离尽可能大，距离表示为，其中，表示两类的中心在ω方向上的投影向量，，因此需要优化的问题为

（4.18）

容易发现，当ω方向与（μ1−μ2）一致的时候，该距离达到最大值，例如对图 4.5（a）的黄棕两种类别的样本点进行降维时，若按照最大化两类投影中心距离的准则，会将样本点投影到下方的黑线上。但是原本可以被线性划分的两类样本，经过投影后有了一定程度的重叠，这显然不能使我们满意。

我们希望得到的投影结果如图4.5（b）所示，虽然两类的中心在投影之后的距离有所减小，但确使投影之后样本的可区分性提高了。

仔细观察两种投影方式的区别，可以发现，在图4.5（b）中，投影后的样本点似乎在每一类中分布得更为集中了，用数学化的语言描述就是每类内部的方差比左图中更小。这就引出了LDA的中心思想——最大化类间距离和最小化类内距离。

在前文中我们已经找到了使得类间距离尽可能大的投影方式，现在只需要同时优化类内方差，使其尽可能小。我们将整个数据集的类内方差定义为各个类分别的方差之和，将目标函数定义为类间距离和类内距离的比值，于是引出我们需要最大化的目标：

其中ω为单位向量，D1，D2分别表示两类投影后的方差：

因此J(ω)可以写成：

（4.22）

我们要最大化J(ω)，只需对ω求偏导，并令导数等于零：

于是得出，

（4.25）

由于在简化的二分类问题中和是两个数，我们令，于是可以把式（4.25）写成如下形式：

整理得，

从这里我们可以看出，我们最大化的目标对应了一个矩阵的特征值，于是LDA降维变成了一个求矩阵特征向量的问题。J(ω)就对应了矩阵最大的特征值，而投影方向就是这个特征值对应的特征向量。

对于二分类这一问题，由于，因此的方向始终与（μ1−μ2）一致（对于二类的时候，的方向恒为μ0−μ1），如果只考虑ω的方向，不考虑其长度，可以得到。换句话说，我们只需要求样本的均值和类内方差，就可以马上得出最佳的投影方向ω。这便是Fisher在1936年提出的线性判别分析。

至此，我们从最大化类间距离、最小化类内距离的思想出发，推导出了LDA的优化目标以及求解方法。Fisher LDA相比PCA更善于对有类别信息的数据进行降维处理，但它对数据的分布做了一些很强的假设，例如，每个类数据都是高斯分布、各个类的协方差相等。尽管这些假设在实际中并不一定完全满足，但LDA已被证明是非常有效的一种降维方法。主要是因为线性模型对于噪声的鲁棒性比较好，但由于模型简单，表达能力有一定局限性，我们可以通过引入核函数扩展 LDA方法以处理分布较为复杂的数据。

3 多类LDA原理

假设我们的数据集D={(x1,y1),(x2,y2),...,((xm,ym))},其中任意样本xi为n维向量，yi∈{C1,C2,...,Ck}。我们定义Nj(j=1,2...k)为第j类样本的个数，Xj(j=1,2...k)为第j类样本的集合，而μj(j=1,2...k)为第j类样本的均值向量，定义Σj(j=1,2...k)为第j类样本的协方差矩阵。在二类LDA里面定义的公式可以很容易的类推到多类LDA。

由于我们是多类向低维投影，则此时投影到的低维空间就不是一条直线，而是一个d维超平面。假设我们投影到的低维空间的维度为d，对应的基向量为(w1,w2,...wd)，基向量组成的矩阵为W, 它是一个n×d的矩阵。

回顾两个散度矩阵，类内散度矩阵 在类别增加至N时仍满足定义，而之前两类问题的类间散度矩阵 在类别增加后就无法按照原始定义。图4.6是三类样本的分布情况，其中分别表示棕绿黄三类样本的中心，表示这三个中心的均值（也即全部样本的中心），表示第i类的类内散度。我们可以定义一个新的矩阵，来表示全局整体的散度，称为全局散度矩阵：

如果把全局散度定义为类内散度与类间散度之和，即，那么类间散度矩阵可表示为：

（4.29）

其中mj是第j个类别中的样本个数，N是总的类别个数。从式（4.29）可以看出，类间散度表示的就是每个类别中心到全局中心的一种加权距离。我们最大化类间散度实际上优化的是每个类别的中心经过投影后离全局中心的投影足够远。

根据LDA的原理，可以将最大化的目标定义为

其中W是需要求解的投影超平面，，根据上述部分结论，我们可以推导出最大化J(W)对应了以下广义特征值求解的问题。

求解最佳投影平面即求解矩阵特征值前d大对应的特征向量组成的矩阵，这就将原始的特征空间投影到了新的d维空间中。至此我们得到了与PCA步骤类似，但具有多个类别标签高维数据的LDA求解方法。

4 LDA算法流程

输入：数据集D={(x1,y1),(x2,y2),...,((xm,ym))}，其中任意样本xi为n维向量，yi∈{C1,C2,...,Ck}，降维到的维度d。

以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外，还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布，这样利用LDA进行投影后，可以利用极大似然估计计算各个类别投影数据的均值和方差，进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后，我们可以将它投影，然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数，计算它属于这个类别的概率，最大的概率对应的类别即为预测类别。

5 LDA算法小结

LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维。在我们进行图像识别图像识别相关的数据分析时，LDA是一个有力的工具。下面总结下LDA算法的优缺点。

　　　　LDA算法的主要优点有：

　　　　1）在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。

　　　　2）LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。

　　　　LDA算法的主要缺点有：

　　　　1）LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。

　　　　2）LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。

　　　　3）LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。

　　　　4）LDA可能过度拟合数据。

6 PCA和LDA的区别

从PCA和LDA两种降维方法的求解过程来看，它们确实有着很大的相似性，但对应的原理却有所区别。

首先从目标出发，PCA选择的是投影后数据方差最大的方向。由于它是无监督的，因此PCA假设方差越大，信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维。而LDA选择的是投影后类内方差小、类间方差大的方向。其用到了类别标签信息，为了找到数据中具有判别性的维度，使得原始数据在这些方向上投影后，不同类别尽可能区分开。

举一个简单的例子，在语音识别中，我们想从一段音频中提取出人的语音信号，这时可以使用PCA先进行降维，过滤掉一些固定频率（方差较小）的背景噪声。但如果我们的需求是从这段音频中区分出声音属于哪个人，那么我们应该使用LDA对数据进行降维，使每个人的语音信号具有区分性。

另外，在人脸识别领域中，PCA和LDA都会被频繁使用。基于PCA的人脸识别方法也称为特征脸（Eigenface）方法，该方法将人脸图像按行展开形成一个高维向量，对多个人脸特征的协方差矩阵做特征值分解，其中较大特征值对应的特征向量具有与人脸相似的形状，故称为特征脸。Eigenface for Recognition一文中将人脸用7个特征脸表示（见图4.7），于是可以把原始65536维的图像特征瞬间降到7维，人脸识别在降维后的空间上进行。然而由于其利用PCA进行降维，一般情况下保留的是最佳描述特征（主成分），而非分类特征。如果我们想要达到更好的人脸识别效果，应该用LDA方法对数据集进行降维，使得不同人脸在投影后的特征具有一定区分性。