LDA算法详解.docx

《LDA算法详解.docx》由会员分享，可在线阅读，更多相关《LDA算法详解.docx（15页珍藏版）》请在三一文库上搜索。

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

2、取方法。 使用这种方法能够使投影后模式样本的类间散布矩阵最大， 并且同时类内散布矩阵最小。 就是说，它能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离， 即模式在该空间中有最佳的可分离性。3.2.1 Fisher线性判别准则假设有一组属于两个类的 n 个 d 维样本 x1 ， xn ，其中前 n1 个样本属于类 1 ，后面 n2 个样本属于类 2 ，均服从同协方差矩阵的高斯分布。各类样本均值向量 m （i=1 ， 2）如式（ 3-15 ）：imi = 1Xi=1 ， 2（3-15 ）nix X t样本类内离散度矩阵 si 和总的类内离散度矩阵 sw 如式 (3-16)、式（

3、3-17 ）：Si mi ( x mi )( x mi )Ti=1 ，2x X tsw = s1 +s2t 样本类间离散度矩阵s 如式 (3-18) ：b（3-16 ）（3-17 ）Sb (m1 m2 )(m1 m2 )T（3-18 ）现寻找一最佳超平面将两类分开， 则只需将所有样本投影到此超平面的法线。1欢迎下载精品文档d方向上R ， |w|=1:yiTw xii=1,n（3-19 ）得到 n 个标量y1, ， yn R，这 n 个标量相应的属于集合1 和Y2 ，并Y且 Y1 和 Y2 能很好的分开。为了能找到这样的能达到最好分类效果的投影方向w，Fisher规定了一个准则函数 :要求选择的

4、投影方向W能使降维后 Y1 和Y 2 两类具有最大的类间距离与类内距离比 :2J F(m1m2)（3-20 ）(w)22s1s2其中类间距离用两类均值m1 和 m2 之间的距离表示，类内距离用每类样本22距其类均值距离的和表示，在式中为s1 + s2 。其中 m (i=1 ， 2) 为降维后各类样本均值：i1y Yi ymi= nii=1， 2（3-21 ）222为总的类内离散度 sw ：si （ i=1 ，2) 为降维后每类样本类内离散度， s1 + s222si( ymi) ，i=1， 2（3-22 ）22sw = s1 + s2（3-23 ）类间离散度表示为 (2准则函数并不是 w 的显

5、m1) 。但式 (3-20)Fisherm2示函数，无法根据此准则求解W，因此需要对 Fisher 准则函数形式进行修改：因 yiTw xii=1, ,n，则mi= 1y = 1w X = w mii=1,2（ 3-24 ）niniTTyYixX T2TT2TT( 12)=()=w(12) (12) ww m1w m2m m m mm m（3-25 ）。2欢迎下载精品文档T= w sb w同样2i （i=1 ，2）也可推出与 w的关系：s222siy Yt( y mi) = x X t (wT x wT mi)TTT= w x X t ( x mi ) (x mi) w = w Si w（3-

6、26 ）因此22TTs1 + s2 = w ( s1 s2)w w sw w（3-27 ）则最终可表示为：(m1m2)2TJ F( w)=w sb w（3-28 ）22Tssw sw w12根据式 (3-28)Fisher准则函数，要寻找一投影向量W，使 J F (w) 最大化，则需对 J F (w) 按变量 W求导并使之为零：T(w sbwT)w(Tw)w(Tw)J F( w)w swwsbw swsww sb20ww( wT sw w)则需令 J F (w)TTsb w （ w sw w ）sw w ( w sb w )=0sb w = JF (w) sw w，则（3-29 ）（3-30

7、）WSb W SW（3-31 ）这是一个广义特征值问题，若s 非奇异，则wWS w 1 S bW（3-32 ）。3欢迎下载精品文档1因此可以通过对 s s 进行特征值分解，将最大特征值对应的特征向量作 w b为最佳投影方向W。以上 Fisher准则只能用于解决两类分类问题，为了解决多类分类问题，Dudal 提出了判别矢量集的概念，被称为经典的Fisher 线性判别分析方法。Duda指出，对于 c 类问题，则需要 c-1 个上节的用于两类分类的Fisher 线d c 1性判别函数，即需要由c-1 个投影向量 W组成一个投影矩阵W R，将样本投影到此投影矩阵上， 从而可以提取 c-1 维的特征矢量

8、。 针对 c 类问题，则样本的统计特性需要推广到c 类上。样本的总体均值向量：m11ci=1,c（3-33 ）xn i 1 nimin x样本的类内离散度矩阵：CT（3-34 ）S w( xm i ) ( x m i )I 1 x X t样本的类间离散度矩阵：bciiTm)m)（3-35 ）Sn (m(mii 1将样本空间投影到投影矩阵W上，得到 C-1 维的特征矢量 y：TyxW（3-36 ）d c1c 1其中 W R， y R。投影后的样本统计特性也相应的推广到c 类：投影后总样本均值向量：m1y1cni mii=1,c（3-37 ）nn i 1y样本的类内离散度矩阵：cTSW( ymi

9、) ( ymi )（3-38 ）i 1 yY i样本的类间离散度矩阵：Scni (mm )( mi m)T（3-39 ）bii 1。4欢迎下载精品文档Fisher 准则也推广到 c 类问题：Tb WJF (W )SbW S（3-40 ）S wTW SW W为使 Fisher准则取得最大值，类似两类分类问题，W需满足：Sb WSW W（3-41 ）若 SW 非奇异，则，则 W的每一列为1的前 c-1SW Sb个较大特征值对应的特征向量。3.2.2基于 LDA的人脸特征提取线性判别式分析 ii (Linear Discriminant Analysis, LDA)，也叫做 Fisher线性判别 (

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

11、。 LDA算法的思想如下：假设对于一个 Rn 空间有 m个样本分别为 x1, x2 ,., xm 即每个 x 是一个 n 行的矩阵， 其中 ni 表 示属 于i类的 样本 个数 ，假 设有一 个有c个类 ，则n1n2.ni.ncm 。Sb 是类间离散度矩阵， Sw 是类内离散度矩阵， ni 是属于 i 类的样本个数， xi 是第 i 个样本， u 是所有样本的均值， ui 是类 i 的样本均值。那么类 i 的样本均值为ui1x（ 3-42 ）nix classi同理我们也可以得到总体样本均值为。5欢迎下载精品文档1m（ 3-43 ）uxim i 1根据类间离散度矩阵和类内离散度矩阵定义，可以得

12、到如下式子cSbni (uiu)(uiu) Ti1（ 3-44 ）cxk ) TSw(uixk )(ui（ 3-45 ）i 1 xk classi当然还有另一种类间类内的离散度矩阵表达方式cu) TSbP(i)(uiu)(ui（ 3-46 ）i1SwcP(i )(ui xk )(ui xk )TcP(i)E( uix)(ui x) T | xclassi （3-47 ）i 1ni xkclassii1其中 P(i ) 是指 i 类样本的先验概率，即样本中属于i 类的概率（P(i )ni ）。mLDA作为一个分类的算法，我们当然希望它所分的类之间耦合度低，类内的聚合度高，即类内离散度矩阵的中的数

13、值要小， 而类间离散度矩阵中的数值要大，这样的分类的效果才好。这里我们引入Fisher 鉴别准则表达式：J fisher ( )T Sb（ 3-48）TSw通过最优化下面的准则函数找到有一组最优鉴别矢量构成的投影矩阵Wopt ，Wopt|W T SbW | w1 , w2 ,., wn （ 3-49 ）arg max|W T SwW |可以证明，当 Sw 为非奇异（一般在实现 LDA算法时，都会对样本做一次 PCA算法的降维，消除样本的冗余度，从而保证Sw 是非奇异阵，当然即使 Sw 为奇异阵也是可以解的，可以把Sw 或 Sb 对角化，这里不做讨论，假设都是非奇异的情况）时，最佳投影矩阵Wop

14、t 的列向量恰为下来广义特征方程SbSw（ 3-50 ）。6欢迎下载精品文档由（ 3-50 ）式可以推导出Sbii Swi又由于 W 1 ,2 ,.,d , 再结合以上两式可以求出|Ti |TSwi|Ti |i Sbii | i SwmaxT|TTi| i Sw| i Sw i | i Swi |（ 3-51 ）（ 3-52 ）根据公式意义来看，要使得max 最大，则只要取i 即可，所以可得出结论：投影矩阵 Wopt 的列向量为 d 个最大特征值所对应的特征向量，其中dc1 。3.3 Fisherface人脸识别方法Fisherface方法也称为 Fisher 线性判别分析 (FisherLi

15、near DiscriminantAnalysis ，FLDA)，是由 P.N Belhumeur 等人在 1997 年提出的。研究者注意到特征值大的特征向量 ( 即特征脸 ) 并不一定是分类性能最好的方向，Fisherface方法的目的就是要从高维特征空间里提取出最具有判别能力的低维特征，这些特征能帮助将同一个类别的所有样本聚集在一起，而不同类别的样本尽量的分开，也就是说，它选择使得样本类间离散度和样本类内离散度的比值最大的特征。Fisherface方法的实现是在PCA数据重构的基础上完成的，首先利用PCA将高维数据投影到低维特征脸子空间，然后再在这个低维特征脸子空间上用LDA特征提取方法得

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

17、ace人脸识别方法 iv。对于上节介绍的 Fisher准则，当 S1非奇异，可以通过对 S S 进行特征值WWb。7欢迎下载精品文档分解，从而求出最佳投影方向W。但是当 LDA用于人脸特征提取时，因图像转换为列向量维数太大， 往往远大于样本数， 造成 SW 奇异，则很难根据 Sb WSW W求解最佳投影方向，即小样本问题。如一幅168192 的人脸图像，转换为列向量变为 168192=32256维，则 SW 为 3225632256 的矩阵，但是因 SW 由样本计算而来，秩最大为 NC (N 为总样本数， C 为类别数 ) ，因 N c c-1 ，则 (S w)的秩最大为 c-1 。取 (S

18、w)1S b 的前 c-1 个较大特征值对应的特征向量组成投影矩阵 W fld( c 1) (c 1)R。(6) 将 WW pcaW fld 作为最终投影矩阵(7) 将所有样本 x1,., xnda b) 中心化后，经投影变换全部投影到R (dWc1上，从而为每个样本提取了c-1个特征得到 x 1, x 2 ,.,x nR:TTTx i W ( xi m)W fldW pca ( xi m)（ 3-55 ）(8) 将测试图像 ydR 经中心化，同样投影到W 上，提取到 c-1 个特征得c 1y R :TTTy W ( y m)W fld W pca ( y m)（3-56 ）(9) 选择合适的分类器，利用提取的特征对测试图像进行分类。9欢迎下载