无监督第四节:LDA(线性判别分析)及其和PCA的关系
LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。因为是由Fisher在1936年提出的,所以也叫Fisher’s Linear Discriminant。
LDA通常作为数据预处理阶段的降维技术,其目标是将数据投影到低维空间来避免维度灾难(curse of dimensionality)引起的过拟合,同时还保留着良好的可分性。
2维情况
1.组间距离最大化
比较好的投影方式就是利用不同类别的数据的中心来代表这类样本在空间中的位置,考虑1个2分类问题。两类的均值向量为:

同时保证让投影之后的中心距离尽可能的大,也就是:


是来自类别 的投影数据的均值,
是我们的投影向量。但是,通过增大w,这个表达式可以任意增大。为了解决这个问题,我们可以将w限制为单位长度,即
。
使用拉格朗日乘数法来进行有限制条件的最大化问题的求解,我们可以发现
2.组内距离最小化
这个方法有一个问题,如下图所示:

左图为最大间隔度量的降维结果,这幅图中的两个类别在原始空维空间(x1; x2)中可以完美地被分开,但是当投影到连接它们的均值的直线上时,就有了一定程度的重叠。
因此,Fisher提出的思想:最大化一个函数,这个函数能够让类均值的投影分开得较大,同时让每个类别内部的方差较小,从而最小化了类别的重叠(右图中的结果)。
这也是LDA的中心思想即:最大化类间距离,最小化类内距离。
我们假设投影结束后,样本的坐标为,即
,那么来自类别
的数据经过变换后的类内方差为:

我们可以把整个数据集的总的类内方差定义为。Fisher准则根据类间距离和类内方差的比值定义,即:

根据,以及
,对上式子进行改写,
通过:

通过下式:

(W)可以被重写为:

其中 是类间(between-class)散度矩阵,形式为

被称为类内(within-class)散度矩阵,形式为:

对公式J(W)关于w求导,并另之为0,我们发现J(w)取得最大值的条件为:

实际上恰好就是倒数的分母。由于 和
在简化的二分类问题中都是标量,因此我们可以把上式子看做:

(或者将分母限定在模为1,利用拉格朗日求解也可以得到上式,具体参考周志华《机器学习》)
将求导后的结果两边都乘以 可得:

从这里就可以看出,是一个求特征值和特征向量的问题了。
具体的,对于我们在引出中提出的简化问题,由于:

因此的方向始终为
,故可以用
来表示,因此我们可以得到:

由于对w扩大缩小任何倍不影响结果,因此我们可得:

我们只需要求出原始样本的均值和方差就可以求出最佳的方向w,这就是Fisher于1936年提出的线性判别分析。
多维情况
多维情况下类内的方差可以用同样的方式定义。但是类间的方差无法和之前一样。
考虑下图的情形,定义了一个全局散度。

即

表示全局的散度,其中n表示数据集中所有的点表示所有数据点的均值向量。
从这个式子我们可以看出,其物理意义就是定义了每个类别到全局中心的距离,我们要让类间分离的足够开,就需要让每个类别的样本再投影后,距离全局中心足够远。
LDA 求解步骤
- 计算每个类别的均值向量
- 通过均值向量,计算类间散度矩阵和类内散度矩阵
- 进行特征值求解,计算特征向量和特征值
- 按特征值大小对特征向量排序,选择前K个特征向量组成投影矩阵。
- 计算新空间的值
LDA 和PCA区别
LDA用于降维,和PCA有很多相同,也有很多不同的地方,因此值得好好的比较一下两者的降维异同点。
相同点:
1)两者均可以对数据进行降维。
2)两者在降维时均使用了矩阵特征分解的思想。
3)两者都假设数据符合高斯分布。
不同点:
1)LDA是有监督的降维方法,而PCA是无监督的降维方法
2)LDA降维最多降到类别数k-1的维数,而PCA没有这个限制。
3)LDA除了可以用于降维,还可以用于分类。
4)LDA选择分类性能最好的投影方向,而PCA选择样本点投影具有最大方差的方向。
这点可以从下图形象的看出,在某些数据分布下LDA比PCA降维较优。

当然有些情况下可能PCA会更好:
LDA算法的主要优点有:
1)在降维过程中可以使用类别的先验知识经验,而像PCA这样的无监督学习则无法使用类别先验知识。
2)LDA在样本分类信息依赖均值而不是方差的时候,比PCA之类的算法较优。
LDA算法的主要缺点有:
1)LDA不适合对非高斯分布样本进行降维,PCA也有这个问题。
2)LDA降维最多降到类别数k-1的维数,如果我们降维的维度大于k-1,则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。
3)LDA在样本分类信息依赖方差而不是均值的时候,降维效果不好。
4)LDA可能过度拟合数据。
Reference: