线性判别分析(Linear Discriminant Analysis)

在之前博客中介绍到了一种非常重要的用于降维的无监督学习方法主成分分析,这篇文章我们会介绍一种主要用于分类的有监督算法,即线性判别分析(LDA)。

一、LDA的分类思想

       LDA分类的思想相当朴素,即每个类同类的样本聚集,不同类的样本相互分散,这就好比学生做早操一样,老师需要把不同班学生区分开来的一个好方法就是让每个班的学生站成一队,然后每个队伍之间保持一定距离。如果考虑一个两类问题,LDA分类的示意图如图1所示。图中红色和蓝色分别表示两个不同类的样本,LDA的目的在于寻找投影变换,比如w\方向,使同类的样本投影之后同类的点靠近,反之异类点相互发散。

图1

二、模型表达

       按照LDA思想,我们所寻找的投影矩阵需要满足两个条件,其一是同类样本相互聚集,其二是异类样本发散,这两点怎样从数学的角度进行度量呢?在前面介绍PCA的时候我们知道样本  的方差可以较好地度量样本的离散程度,而协方差矩阵是一个能反应出方差信息的变量;对于第二点,一个很直接很朴素的思想便是让不同类之间的中心值也就是均值尽量远离就可以了,如图1所示,也就是让图中的两个黑点尽量远离。

           (1)同类样本相互聚集

        现在假设我们考虑的是两类问题,需要寻求的最优投影矩阵为W\,样本集合为\left \{ x_{ij} \right \}\,其中下标i\j\表示第i\类的第j\个样本,第一类的样本集合矩阵为X_{1}\,相应的第二类样本集合矩阵为X_{2}\,那么每个类经投影之后得到的方差分别可以表示为tr(W^{T}X_{1}X_{1}^{T}W)\tr(W^{T}X_{2}X_{2}^{T}W)\,为了简便表示,使用协方差矩阵\sum _{1}\\sum _{2}\分别代替X_{1}X_{1}^{T}\X_{2}X_{2}^{T}\,LDA设法让同类聚集,可以看成让每个不同类的方差都较小,这个时候就是要求tr(W^{T}\sum _{1}W)\tr(W^{T}\sum _{2}W)\的和最小化,即

(1)tr(W^{T}\sum _{1}W)+tr(W^{T}\sum _{2}W)\ 

利用矩阵迹的性质(1)可以写成

(2)tr(W^{T}(\sum _{1}+\sum _{2})W)\  

式(2)中\sum _{1}+\sum _{2}\被称作类内散度矩阵,通常可以记为S_{W}\,因为它通过求解每个类内的协方差矩阵之和获得,每个协方差矩阵能够度量这个类的散度,因此进行这样的命名,类内散度矩阵的计算方式如下

(3)S_{W}=\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}(x_{ij}-\overline{x_{i}})(x_{ij}-\overline{x_{i}})^{T}\ 

其中m\n_{i}\分别表示类别个数以及每个类内的样本个数。最终为使同类样本相互聚集,需要最小化

(4)tr(W^{T}S_{W}W)\

        (2)异类样本相互发散

           异类样本相互发散的一个衡量方式是让两类中心远离,中心也就是两类的样本平均值。定义\overline{x_{1}}\\overline{x_{2}}\分别为两类样本的均值:

(5)\overline{x_{1}}=\sum_{i=1}^{n_{1}}\frac{1}{n_{1}}x_{1i}\\overline{x_{2}}=\sum_{i=2}^{n_{2}}\frac{1}{n_{2}}x_{2i}\

投影之后样本的均值为

(6)\overline{y_{1}}=W^{T}\overline{x_{1}}\\overline{y_{2}}=W^{T}\overline{x_{2}}\

两类中心的距离为

(7)\left \| \overline{y_{1}}-\overline{y_{2}} \right \|=\left \|W^{T}\overline{x_{1}}-W^{T}\overline{x_{2}}\right \|\

= W^{T}(\overline{x_{1}}-\overline{x_{2}})(\overline{x_{1}}-\overline{x_{2}})^{T}W\  

式(7)中令S_{B} = (\overline{x_{1}}-\overline{x_{2}})(\overline{x_{1}}-\overline{x_{2}})^{T}\S_{B}\叫作类间散度矩阵,因为其通过样本均值来衡量不同类之间的差异,这样异类样本相互发散就相当于优化

(8)tr(W^{T}S_{B}W)\

            (3)优化

            按照LDA的思想,项目需要同时最小化类内散度,也就是式(4),同时最大化类间散度,也就是式(8),因此可以考虑最大化\frac{tr(W^{T}S_{B}W)}{tr(W^{T}S_{W}W)}\,为了便于优化,可以固定分母,令其为一个固定的值t\,最终可以考虑使用拉格朗日乘子法优化

(9)\max tr(W^{T}S_{B}W)\

s.t. tr(W^{T}S_{W}W)=t\

L(W)=tr(W^{T}S_{B}W)-\lambda (tr(W^{T}S_{W}W)-t)\,并对W\求导

(10)\frac{\partial L(W)}{\partial W}=2W^{T}S_{B}-2\lambda W^{T}S_{W}\

=0\

式(10)稍微整理一下也就得到了标准的特征方程问题

(11)S_{B}W=\lambda S_{W}W\

           (4)多类问题

多类的情况与二分类类似,需要使每个类内散度值最小,S_{W}=\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}(x_{ij}-\overline{x_{i}})(x_{ij}-\overline{x_{i}})^{T}\ 相当于求解多个类内散度值的和,这一点与二分类一致;同时需要使不同类类间散度值最大,因为是多类,所以并不好直接两两比较样本中心距离,这个时候可以通过总体样本均值作为比较桥梁,即计算每个类均值减去总体均值的散度,使之最大化,这个时候类间散度矩阵可以写成

(12)S_{B}=\sum_{i=1}^{c}(\overline{x_{i}}-\overline{x})(\overline{x_{i}}-\overline{x})^{T}\

最终得到的优化方程与(11)类似。

      三、分析

式(11)是一个典型的特征方程问题,在S_{W}\可逆的情况下,方程(11)转化为

(12)S_{W}^{-1}S_{B}W=\lambda W\

对于式(12)有几个很值得关注的点:

      (1)关于LDA降维的维数。事实上对于S_{W}^{-1}S_{B}\并不是一个对称矩阵,因此不能保证其能获得多个线性无关的特征向量,事实上这里求解得到的线性无关的特征向量的个数和矩阵S_{W}^{-1}S_{B}\的秩有一个上线的关系,这里很多paper包括原文都没有给出详细的证明。就自己翻翻资料给出了证明,仅供参考。事实上,根据矩阵秩的性质

(13)r(S_{W}^{-1}S_{B})\leqslant r(S_{B})\

而矩阵S_{B}\由多个形如(\overline{x_{i}}-\overline{x})(\overline{x_{i}}-\overline{x})^{T}\矩阵相加获得,因此

(14)r(S_{B})\leqslant \sum_{i=1}^{c}r(\overline{x_{i}}-\overline{x})\leqslant c\

更为严格的是,矩阵S_{B}\可以由向量组{\overline{x_{i}}-\overline{x}}\进行线性表示,此时

(15)r(S_{B})\leqslant r(\overline{x_{1}}-\overline{x},\overline{x_{2}}-\overline{x},...\overline{x_{c}}-\overline{x})\

后者,也就是c\个向量组显然是线性相关的,因为

(16)\sum_{i=1}^{c}(\overline{x_{i}}-\overline{x})=\sum_{i=1}^{c}\overline{x_{i}}-n\cdot \overline{x}=0\

那么最终可以得到

(17)r(S_{B})\leqslant c-1\

以上分析可以得出结论,LDA降维只需降到c-1\维,即可。

      (2)关于奇异性问题。在样本维数过高的情况下,(12)中矩阵S_{W}^{-1}\很有可能是奇异的,此时可以衍生出很多很多扩展的LDA形式,其中一个很经典的方法是在进行LDA处理之前首先PCA进行降维,经PCA处理之后再进行LDA降维,此时可以避免奇异问题,还有很多其他方法,比如对S_{W}\进行改造,添加很小的扰动\lambda E + S_{W}\等等,感兴趣的话可以Google相关文献~

      (3)与PCA的比较。事实上这两种都是灰常灰常经典的投影方法,算法浅显并且都能获得解析解;不过PCA是一种无监督的降维方法,一般情况下本身不会直接用于分类;而LDA是有监督的分类方法,二者分类的思想也不一致。还有很关键的一点是,LDA最终获得的特征方程中S_{W}^{-1}S_{B}\并不是对称阵,因此获得的投影向量并不正交,从信息的角度来说充满一定的冗余性;相反PCA获得的是XX^{T}\的特征向量,特征向量之间满足相互正交,因此PCA从某种程度上说可以是一种重要的消除冗余信息的降维方法。针对LDA获得的投影向量并不正交这一点,也有很多文章进行了拓展,这里不再综述。

     (4)说句题外话,事实上早期国内模式识别学科的发展很多都是靠研究投影方法起家的,特别是线性判别分析。。翻看相关文献可以看出,国内的学者研究这方面的实在是巨多。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注