LDA算法详解

线性鉴别分析法线性鉴别分析(LinearDiscriminantAnalysis,LDA)，有时也称Fisher线性判别(FisherLinearDiscriminant,FLD)，这种算法是RonaldFisher于1936年发明的，是模式识别的经典算法[i]。在1996年由Belhumeur引入模式识别和人工智能领域的。性鉴别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。就是说，它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性。3.2.1Fisher线性判别准则假设有一组属于两个类的n个d维样本x1，．．．，xn，其中前n1个样本属于类1，后面n2个样本属于类2，均服从同协方差矩阵的高斯分布。各类样本均值向量mi（i=1，2）如式（3-15）：mi=ni1tXxXi=1，2（3-15）样本类内离散度矩阵si和总的类内离散度矩阵sw如式(3-16)、式（3-17）：TiXxiiimxmxmSt)()(i=1，2（3-16）sw=s1+s2（3-17）t样本类间离散度矩阵sb如式(3-18)：TbmmmmS))((2121（3-18）现寻找一最佳超平面将两类分开，则只需将所有样本投影到此超平面的法线方向上Rd，||w||=1:xwyiTii=1,…,n（3-19）得到n个标量y1,．．．，yn∈R，这n个标量相应的属于集合Y1和Y2，并且Y1和Y2能很好的分开。为了能找到这样的能达到最好分类效果的投影方向w，Fisher规定了一个准则函数:要求选择的投影方向W能使降维后Y1和Y2两类具有最大的类间距离与类内距离比:ssmmJwF2121)(222)(（3-20）其中类间距离用两类均值m1和m2之间的距离表示，类内距离用每类样本距其类均值距离的和表示，在式中为s12+s22。其中mi(i=1，2)为降维后各类样本均值：mi=ni1Yyiyi=1，2（3-21）si2（i=1，2)为降维后每类样本类内离散度，s12+s22为总的类内离散度sw：)(22mysii，i=1，2（3-22）sw=s12+s22（3-23）类间离散度表示为)(212mm。但式(3-20)Fisher准则函数并不是w的显示函数，无法根据此准则求解W，因此需要对Fisher准则函数形式进行修改：因xwyiTii=1,…,n，则mi=ni1Yyiy=ni1XTXxTw=wTmii=1,2（3-24）)(212mm=)(212mwmwTT=wmmmmwTT)(21)(21（3-25）=wswbT同样si2（i=1，2）也可推出与w的关系：tYymysii)(22=tXxmwxwiTT)(2=wixtXxTiTmxmw])([)(=wSwiT（3-26）因此s12+s22=wwswsswwTT)(21（3-27）则最终可表示为：ssmmJwF2121)(222)(=wwswswwTbT（3-28）根据式(3-28)Fisher准则函数，要寻找一投影向量W，使)(wJF最大化，则需对)(wJF按变量W求导并使之为零：0)()()()()(2wswswsswsswswJwT（3-29）则需wsb（wswwT）wsw(wswbT)=0wsb=)(wJFwsw（3-30）令)(wJF，则SWWSWb（3-31）这是一个广义特征值问题，若sw非奇异，则WSWSbw1（3-32）因此可以通过对sw1sb进行特征值分解，将最大特征值对应的特征向量作为最佳投影方向W。以上Fisher准则只能用于解决两类分类问题，为了解决多类分类问题，Dudal提出了判别矢量集的概念，被称为经典的Fisher线性判别分析方法。Duda指出，对于c类问题，则需要c-1个上节的用于两类分类的Fisher线性判别函数，即需要由c-1个投影向量W组成一个投影矩阵W∈Rcd1，将样本投影到此投影矩阵上，从而可以提取c-1维的特征矢量。针对c类问题，则样本的统计特性需要推广到c类上。样本的总体均值向量：mniciixnxnm111i=1,…,c（3-33）样本的类内离散度矩阵：CIXTiwtmxmSix1x)()(（3-34）样本的类间离散度矩阵：)(()1mmmnSimTiciib（3-35）将样本空间投影到投影矩阵W上，得到C-1维的特征矢量y：xWTy（3-36）其中RWcd1，y∈Rc1。投影后的样本统计特性也相应的推广到c类：投影后总样本均值向量：mniciiynynm111i=1,…c（3-37）样本的类内离散度矩阵：ciyTiWYiyimymS1)()(（3-38）样本的类间离散度矩阵：ciTiibmmmnSim1)()(（3-39）Fisher准则也推广到c类问题：)(（3-40）为使Fisher准则取得最大值，类似两类分类问题，W需满足：WWSSWb（3-41）若SW非奇异，则，则W的每一列为SSbW1的前c-1个较大特征值对应的特征向量。3.2.2基于LDA的人脸特征提取线性判别式分析[ii](LinearDiscriminantAnalysis,LDA)，也叫做Fisher线性判别(FisherLinearDiscriminant,FLD)，是模式识别的经典算法，它是在1996年由Belhumeur引入模式识别和人工智能领域的。性鉴别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。就是说，它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性。LDA算法的思想如下：假设对于一个nR空间有m个样本分别为mxxx,...,,21即每个x是一个n行的矩阵，其中in表示属于i类的样本个数，假设有一个有c个类，则mnnnnci......21。bS是类间离散度矩阵，wS是类内离散度矩阵，in是属于i类的样本个数，ix是第i个样本，u是所有样本的均值，iu是类i的样本均值。那么类i的样本均值为classixiixnu1（3-42）同理我们也可以得到总体样本均值为miixmu11（3-43）根据类间离散度矩阵和类内离散度矩阵定义，可以得到如下式子ciTiiibuuuunS1))((（3-44）ciclassixTkikiwkxuxuS1))((（3-45）当然还有另一种类间类内的离散度矩阵表达方式ciTiibuuuuiPS1))()((（3-46）}|))({()())(()(11classixxuxuEiPxuxuniPSciTiiciclassixTkikiiwk（3-47）其中)(iP是指i类样本的先验概率，即样本中属于i类的概率（mniPi)(）。LDA作为一个分类的算法，我们当然希望它所分的类之间耦合度低，类内的聚合度高，即类内离散度矩阵的中的数值要小，而类间离散度矩阵中的数值要大，这样的分类的效果才好。这里我们引入Fisher鉴别准则表达式：wTbTfisherSSJ)(（3-48）通过最优化下面的准则函数找到有一组最优鉴别矢量构成的投影矩阵optW，],...,,[||||maxarg21nwTbTopt（3-49）可以证明，当wS为非奇异（一般在实现LDA算法时，都会对样本做一次PCA算法的降维，消除样本的冗余度，从而保证wS是非奇异阵，当然即使wS为奇异阵也是可以解的，可以把wS或bS对角化，这里不做讨论，假设都是非奇异的情况）时，最佳投影矩阵optW的列向量恰为下来广义特征方程wbSS（3-50）由（3-50）式可以推导出iwiibSS（3-51）又由于],...,,[21dW,再结合以上两式可以求出iiwTiiwTiiiwTiiwTiwTiibTiSSSSSS||||||||||||max（3-52）根据公式意义来看，要使得max最大，则只要取i即可，所以可得出结论：投影矩阵optW的列向量为d个最大特征值所对应的特征向量，其中1cd。3.3Fisherface人脸识别方法Fisherface方法也称为Fisher线性判别分析(FisherLinearDiscriminantAnalysis，FLDA)，是由P.N．Belhumeur等人在1997年提出的。研究者注意到特征值大的特征向量(即特征脸)并不一定是分类性能最好的方向，Fisherface方法的目的就是要从高维特征空间里提取出最具有判别能力的低维特征，这些特征能帮助将同一个类别的所有样本聚集在一起，而不同类别的样本尽量的分开，也就是说，它选择使得样本类间离散度和样本类内离散度的比值最大的特征。Fisherface方法的实现是在PCA数据重构的基础上完成的，首先利用PCA将高维数据投影到低维特征脸子空间，然后再在这个低维特征脸子空间上用LDA特征提取方法得到相关特征参数[iii]。程序中使用参数寻优的方法来寻找最佳投影维数，以达到比较理想的识别效果。Fisherface采用PCA和LDA相结合的方法，实验证明此方法识别率比较高。由于PCA方法存在着缺陷，图像中所有的像素都被赋予了同等的地位，角度、光照、尺寸及表情等会导致识别率下降。LDA的计算过程要反复做矩阵操作，计算量非常的大，而且计算复杂，容易引起累计误差，影响计算的精度，并且由于在正常的情况下人脸识别问题总是一个小样本问题，训练样本数比图像向量的维数要小很多，所以类内散布矩阵总为奇异阵而使此方法的求解变得很困难。因此，我们采用将PCA和LDA算法相结合的Fisherface人脸识别方法[iv]。对于上节介绍的Fisher准则，当SW非奇异，可以通过对SSbW1进行特征值分解，从而求出最佳投影方向W。但是当LDA用于人脸特征提取时，因图像转换为列向量维数太大，往往远大于样本数，造成SW奇异，则很难根据WWSSWb求解最佳投影方向，即小样本问题。如一幅168×192的人脸图像，转换为列向量变为168×192=32256维，则SW为32256×32256的矩阵，但是因SW由样本计算而来，秩最大为CN(N为总样本数，C为类别数)，因cN32256，造成SW奇异。因为SW的秩为N-C，为使SW非奇异，Fisherfaces首先利用PCA技术将样本降到N-c维，这样经PCA降维后样本的类内离散度矩阵SW可逆。此时可以对经PCA降维后的样本直接利用标准的LDA技术将维数降到c-1维。算法具体步骤如下：(1)将所有的axb的训练图像转换为列向量)(,...1badxxn，并对其中心化：均减去总训练图像的均值。计算其类内离散度矩阵RSddw，类间离散度矩阵RSddb。(2)计算样本的协方差矩阵RSddt，并对其特征值分解，将特征向量按照其特征值的大小进行降序排列。取前N-c个特征向量组成dx(N-c)的投影矩阵Wpca。(3)计算投影到Wpca投影矩阵上的样本的类内离散度矩RScNcNw)()(和类间离散度矩阵RScNcNb)()