LDA算法详解

线性鉴别分析法

线性鉴别分析(Linear Discriminant Analysis, LDA)，有时也称Fisher线性判别(Fisher Linear Discriminant ,FLD)， 这种算法是Ronald Fisher 于 1936年发明的，是模式识别的经典算法[i]。在1996年由Belhumeur引入模式识别和人工智能领域的。性鉴别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。就是说，它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性。 3.2.1 Fisher线性判别准则

假设有一组属于两个类的n个d维样本于类?1 ，后面

22．．．，xx，

1n，其中前

n个样本属

1n个样本属于类?，均服从同协方差矩阵的高斯分布。各类样

mi=

1本均值向量mi（i=1，2）如式（3-15）：

nix?Xt?X i=1，2 （3-15）

样本类内离散度矩阵si和总的类内离散度矩阵sw如式(3-16)、式（3-17）：

Si?mi?(x?mi)(x?mi)T i=1，2 （3-16）

x?Xts=s+sw12 （3-17）

t样本类间离散度矩阵sb如式(3-18)：

Sb?(m1?m2)(m1?m2)T （3-18）

现寻找一最佳超平面将两类分开，则只需将所有样本投影到此超平面的法线

方向上??R，||

Tiid

y?wx i=1,…,n （3-19）

得到n个标量

．．，yy,．

1n∈R，这n个标量相应的属于集合Y1和Y2，并

且Y1和Y2能很好的分开。

为了能找到这样的能达到最好分类效果的投影方向w，Fisher规定了一个准则函数:要求与类内距离比:

W能使降维后Y1和Y2两类具有最大的类间距离

JF(w)?(m1?m2)s1?s2222 （3-20）

其中类间距离用两类均值m1和m2之间的距离表示，类内距离用每类样本距其类均值距离的和表示，在式中为

s1+s2。

22其中mi(i=1，2)为降维后各类样本均值：

mi=

21niy??y i=1，2 （3-21）

Yi222)为降维后每类样本类内离散度，+si（i=1，s1s2为总的类内离散度sw：

si??(y?mi)， i=1，2 （3-22）

sw=s1+s2 （3-23）

类间离散度表示为(m?m)。但式(3-20)Fisher准则函数并不是w的显

12示函数，无法根据此准则求解W，因此需要对Fisher准则函数形式进行修改：

因y?wiT22222x i=1,…,n ，则

imi=

1ni1=y?y?Yini2x?XT?wTTX=wT m i=1,2 （3-24）

i(m1?m2)=(wm1?wm2)=w(m?m)(m1?m2)T12T2Tw

（3-25）

=w2Tsbw

同样si（i=1，2）也可推出与w的关系：

si??(y?mi)=?(wx?wmi)y?Ytx?Xt22TT2

=w[?(x?mi)(x?mi)]w=wTx?XtTTSiw

（3-26）

因此

s1s22+

2 =w(s1?s2)w?wTTsww （3-27）

则最终可表示为：

(m1?m2)(w)?Js1?s2F222 = wswsTTbww （3-28）

w根据式(3-28)Fisher准则函数，要寻找一投影向量W，使JF(w)最大化，则需对JF(w)按变量W求导并使之为零：

?(wT??JF(w)?wsws?wTbwww)?sbw(wTsww)?sww(w(wTsww)2Tsbw)?0

（3-29）

则需

sbw（wsw=JbTsww）?sww(wswTsw)=0

bF(w)w （3-30）

令JF(w)??，则

WS?W?SbW （3-31）

这是一个广义特征值问题，若sw非奇异，则

WSwSb??1?W （3-32）

因此可以通过对sw为最佳投影方向W。

?1sb进行特征值分解，将最大特征值对应的特征向量作

以上Fisher准则只能用于解决两类分类问题，为了解决多类分类问题，Dudal提出了判别矢量集的概念，被称为经典的Fisher线性判别分析方法。

Duda指出，对于c类问题，则需要c-1个上节的用于两类分类的Fisher线性判别函数，即需要由c-1个投影向量W组成一个投影矩阵W∈Rd?c?1，将样本

投影到此投影矩阵上，从而可以提取c-1维的特征矢量。针对c类问题，则样本的统计特性需要推广到c类上。

样本的总体均值向量：

11cm??x??nimi i=1,…,c （3-33）

nxni?1样本的类内离散度矩阵：

T?(x?)Sw??mi(x?mi) （3-34）

I?1x?XtC样本的类间离散度矩阵：

S??n(m?m)(mi?m)bi?1iicT （3-35）

将样本空间投影到投影矩阵W上，得到C-1维的特征矢量y：

y?xWc?1T （3-36）

其中W?Rd?c?1，y∈R。投影后的样本统计特性也相应的推广到c类：

投影后总样本均值向量：

11cm??y??nimi i=1,…c （3-37）

nyni?1样本的类内离散度矩阵：

SW （3-38） ???(y?mi)(y?)mii?1y?YicT样本的类间离散度矩阵：

(?m)(m?m) （3-39） Sb??nimiii?1cTFisher准则也推广到c类问题：

SJ(W)?SFbw?WSWSTTbWW （3-40）

W为使Fisher准则取得最大值，类似两类分类问题，W需满足：

SW??SbWW （3-41）

?1若SW非奇异，则，则W的每一列为SWSb的前c-1个较大特征值对应的特征向量。

3.2.2 基于LDA的人脸特征提取

线性判别式分析[ii](Linear Discriminant Analysis, LDA)，也叫做Fisher线性判别(Fisher Linear Discriminant ,FLD)，是模式识别的经典算法，它是在1996年由Belhumeur引入模式识别和人工智能领域的。性鉴别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。就是说，它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性。LDA算法的思想如下：

假设对于一个Rn空间有m个样本分别为x1,x2,...,xm 即每个x是一个n行的矩阵，其中ni表示属于i类的样本个数，假设有一个有c个类，则

n1?n2?...?ni?...?nc?m。Sb是类间离散度矩阵，Sw是类内离散度矩阵，ni是属于i类的样本个数，xi是第i个样本，u是所有样本的均值，ui是类i的样本均值。那么类i的样本均值为

ui?1nix?classi?x （3-42）

同理我们也可以得到总体样本均值为

1mu??xi （3-43）

mi?1根据类间离散度矩阵和类内离散度矩阵定义，可以得到如下式子

Sb??ni(ui?u)(ui?u)Ti?1c （3-44）

Sw??ci?1xk?classi?(ui?xk)(ui?xk)T （3-45）

当然还有另一种类间类内的离散度矩阵表达方式

Sb??P(i)(ui?u)(ui?u)Ti?1c （3-46）

cP(i)T Sw??(ui?xk)(ui?xk)??P(i)E{(ui?x)(ui?x)T|x?classi}（3-47）?ni?1i?1ixk?classic其中P(i)是指i类样本的先验概率，即样本中属于i类的概率（ P(i)?ni）。 mLDA作为一个分类的算法，我们当然希望它所分的类之间耦合度低，类内的聚合度高，即类内离散度矩阵的中的数值要小，而类间离散度矩阵中的数值要大，这样的分类的效果才好。这里我们引入Fisher鉴别准则表达式：

?TSb? （3-48） Jfisher(?)?T?Sw?通过最优化下面的准则函数找到有一组最优鉴别矢量构成的投影矩阵Wopt，

Wopt|WTSbW|?argmaxT?[w1,w2,...,wn] （3-49）

|WSwW|可以证明，当Sw为非奇异（一般在实现LDA算法时，都会对样本做一次PCA算法的降维，消除样本的冗余度，从而保证Sw是非奇异阵，当然即使Sw为奇异阵也是可以解的，可以把Sw或Sb对角化，这里不做讨论，假设都是非奇异的情况）时，最佳投影矩阵Wopt的列向量恰为下来广义特征方程

Sb???Sw? （3-50）

由（3-50）式可以推导出

Sb?i??iSw?i （3-51）

又由于W?[?1,?2,...,?d],再结合以上两式可以求出

?i|?iTSw?i|max?????i （3-52） TTT|?iSw?||?iSw?i||?iSw?i||?iSb?i|T|?i?Sw?i|T根据公式意义来看，要使得max最大，则只要取?i即可，所以可得出结论：投影矩阵Wopt的列向量为d个最大特征值所对应的特征向量，其中d?c?1。

3.3 Fisherface人脸识别方法

Fisherface方法也称为Fisher线性判别分析(Fisher Linear Discriminant Analysis，FLDA)，是由P.N．Belhumeur等人在1997年提出的。研究者注意到特征值大的特征向量(即特征脸)并不一定是分类性能最好的方向， Fisherface方法的目的就是要从高维特征空间里提取出最具有判别能力的低维特征，这些特征能帮助将同一个类别的所有样本聚集在一起，而不同类别的样本尽量的分开，也就是说，它选择使得样本类间离散度和样本类内离散度的比值最大的特征。

Fisherface方法的实现是在PCA数据重构的基础上完成的，首先利用PCA将高维数据投影到低维特征脸子空间，然后再在这个低维特征脸子空间上用LDA特征提取方法得到相关特征参数[iii]。程序中使用参数寻优的方法来寻找最佳投影维数，以达到比较理想的识别效果。

Fisherface采用PCA 和LDA 相结合的方法，实验证明此方法识别率比较高。由于PCA 方法存在着缺陷，图像中所有的像素都被赋予了同等的地位，角度、光照、尺寸及表情等会导致识别率下降。LDA 的计算过程要反复做矩阵操作，计算量非常的大，而且计算复杂，容易引起累计误差，影响计算的精度，并且由于在正常的情况下人脸识别问题总是一个小样本问题，训练样本数比图像向量的维数要小很多，所以类内散布矩阵总为奇异阵而使此方法的求解变得很困难。因此，我们采用将PCA 和LDA 算法相结合的Fisherface人脸识别方法[iv]。

对于上节介绍的Fisher准则，当S非奇异，可以通过对SWSb进行特征值

W?1分解，从而求出最佳投影方向W。但是当LDA用于人脸特征提取时，因图像转换为列向量维数太大，往往远大于样本数，造成SW奇异，则很难根据SbW??SWW求解最佳投影方向，即小样本问题。如一幅168×192的人脸图像，转换为列向量变为168×192=32256维，则SW为32256×32256的矩阵，但是因SW由样本计算而来，秩最大为N?C(N为总样本数，C为类别数)，因N?c<<32256，造成

S奇异。

W因为SW的秩为N-C，为使SW非奇异，Fisherfaces 首先利用PCA技术将样本降到N-c维，这样经PCA降维后样本的类内离散度矩阵SW可逆。此时可以对经PCA降维后的样本直接利用标准的LDA技术将维数降到c-1维。算法具体步骤如下：

(1)将所有的axb的训练图像转换为列向量x1,...xn?(d?a?b)?Rwd?d，并对其中心

化：均减去总训练图像的均值。计算其类内离散度矩阵S阵S?Rbd?d，类间离散度矩

。

(2)计算样本的协方差矩阵

St?Rd?d，并对其特征值分解，将特征向量按照

其特征值的大小进行降序排列。取前N-c个特征向量组成dx(N-c)的投影矩阵

Wpca。

(3)计算投影到Wpca投影矩阵上的样本的类内离散度矩类间离散度矩阵

wS?w?R(N?c)?(N?c)和

S?b?RTw(N?c)?(N?c)：

pcaS??WpcaSW?WpcaSW?S

bbTpca （3-52）

?1b(4)此时因S?w非奇异，可逆，所以可以按照标准LDA，通过对(S?w)S?行特征值分解，寻找最佳投影子空间。

(5)将(S?w)?1进

S?b的特征向量按其特征值进行降序排列。根据矩阵论：

rank((S?w)?1S?b)?minrank(S?w),rank(S?b)??1? （3-54）

因S?b的秩最大为c-1，S?w的秩最大为c-1。取影矩阵W(6)将

?Rfld()?1的秩为N-c，而一般N-c>c-1，则

(S?w)S??1b(S?w)S?。

?1b的前c-1个较大特征值对应的特征向量组成投

(c?1)?(c?1)W?WpcaWfld作为最终投影矩阵

d(7)将所有样本

x1,...,xn?R(d?a?b)中心化后，经投影变换全部投影到W

上，从而为每个样本提取了c-1个特征得到

x?1,x?2,...,x?n?Rc?1:

x??W(x?m)?WiiTTfldWpca(x?m) （3-55）

iT(8)将测试图像y?R经中心化，同样投影到W上，提取到c-1个特征得

dy??R:

y??W(y?m)?WfldTTc?1Wpca(y?m) （3-56）

T(9)选择合适的分类器，利用提取的特征对测试图像进行分类。

本文来源：https://www.bwwdw.com/article/l482.html