四种FLD准则函数的最优鉴别向量集.doc

1、1四种 FLD 准则函数的最优鉴别向量集摘要本文在最优Fisher线性鉴别(FLD)算法的基础上讨论了FLD准则下的最优正交鉴别(OD)向量集与最优不相关鉴别(UD) 向量集的性质与求解问题，证明了类内协方差阵的零空间中的最优 OD向量集与最优UD向量集的等价性，给出了求取FLD 准则下的最优OD向量集与最优UD向量集的简洁算法和求取更多鉴别向量方法。在ORL人脸库与JEFFE人脸表情库上进行实验，实验结果表明适当增加鉴别向量的个数有利于识别率的提高。关键词FLD准则 最优FLD算法 最优OD 向量集 最优UD 向量集1引言 Fisher线性鉴别（FLD）分析是基于FLD准则的一种传统模式特征

2、提取方法，在模式识别与计算机视觉等方面有着广泛的应用。FLD准则就是寻找一个或多个投影方向，对原始数据进行投影，使投影后新数据的类间离散度达到最大而类内离散度达到最小，而投影后的新数据就是所需的模式特征。用以描述FLD准则的准则函数有很多种，其中最为典型也最为常见的四种FLD准则函数为： (a) (b) 1()TbwSJ 12()()()TTwbJWtrSW(c) (d) 3()()TbWtr4()bTwtr其中 分别表示原始数据的类间协方差阵与类内协方差阵。准则函数 最早是由R. ,wbS 1(JFisher针对两分类问题提出的， 和 是它在多分类问题中的推广，尽管它也适2()J4()用于多

3、分类问题。2006年Li提出了最大间距准则(MMC)， 就是MMC函数，显然3()JW也描述了FLD准则，因此它也可看作是FLD准则函数，实际上早在1990文献已提到3()J过 。W最大化准则函数 可得多个投影向量 ，最大化准则函数 、1()Jw12,kw 2()J或 可得由多个投影向量组成的投影矩阵 。投影向量3()4() 12(,)kw也称为鉴别向量，在实际应用中一般要求鉴别向量单位化，即 ( )，iw Ti1,ik单位化向量集合 常称为鉴别向量集 4。12,k在最大化准则函数求取鉴别向量集时，通常需附加一定的条件，目前人们使用的附加条件主要有两种：一种是附加正交条件 ( )，相应的向量集

4、称为正交鉴别T0ijwij(Orthogonal Discriminant，OD)向量集；另一种是附加不相关条件 ( )，它T0itjwSij可使由不同鉴别向量投影所得的模式特征具有统计不相关性，由此得到的鉴别向量集称为不相关鉴别 (Uncorrelated Discriminant Vectors，UD) 向量集，其中 是样本总tbw体协方差阵。更一般的附加条件为( ) (1)T0ijwGij其中 为正定阵。不同的 可得到不同的鉴别向量集，因此每一个准则函数都可得无穷多G种鉴别向量集。现在的问题是，在这么多种鉴别向量集中，哪种鉴别向量集是最优的？本2文以准则函数值为标准，研究上述四种准则函数

5、的最优鉴别向量集。由于UD 向量集中鉴别向量集最多只有 个，所以以下均假定 ，其中 是样本类别数。1c1kc2 非奇异情形wS2.1 基于 的最优鉴别向量集1()J准则函数 满足附加条件(1)的鉴别向量集 可由Foley-sammon变121,GGkw换(FST) 得到：记 ， ，则第 个鉴别向量 是广义特0DI12(,)Gi iw i1,iw征方程 的最大广义特征值所对应的单位广义特征向量( )，其ibwPS 2ik中(2)11()TTiiwiiwPIDSS当 时，得到的就是基于 的OD向量集；当 时，得到就是基于 的GI1)Jt 1()JUD向量集。文献证明了基于 的UD向量集就是 相对于

6、 的非零广义特征值对应b的单位广义特征向量。本文未能得到基于 的最优鉴别向量集1()w2.2 基于 的最优鉴别向量集2()JW先讨论准则函数 的UD向量集 ，它们是 相对于 的非零广2212,uukw bSw义特征值 对应的单位广义特征向量。令 ，则其函1k 212(,)uukW数值(3)21()kuiJ文献有一个结论，应用到准则函数 中可描述为定理1 对任意的 矩阵 ， ，都有nkW()rank(4)121( ()kTTuwbitrSJW由引理1知， 就是基于 的最优鉴别向量集。由于函数212,uuk 2()J对可逆矩阵具有不变性，所以基于 的最优鉴别向量集并不唯一。例如，对2()JW实施Q

7、R分解，即令 ，其中 是列正交矩阵， 是上u oR12,)ookw R三角阵，则 也是最优鉴别向量集，同时也是基于 的OD 向量集。212,okw 2(J3.3 基于 的最优鉴别向量集3()J准则函数 满足附加条件(1)的鉴别向量集 就是 相对3123,GGk )bwS于 的前 个最大广义特征值所对应的单位广义特征向量。特别地， 基于 的OD向Gk 3(JW量集 就是 的前 个最大特征值所对应的单位特征向量， 基于3123,ook ()bwSk的UD向量集 就是 相对于 的非零广义特征值对应的单位广义()JW123,uu bSw特征向量。下面的一些引理可以帮助我们找到基于 的最优鉴别向量集。3

8、()JW引理1 设 为两个 阶实对称方阵， ， ， 是 相对于,ABn0AB12,nu A的广义特征值所对应的单位广义特征向量，广义特征值从大到小排列，则B，1TU2TU其中 ， 为对角阵。12(,)nu 2,3引理 2 设 为 阶对称阵， 为其前 个最大特征值所对应的单位正交特征向量矩AnUk阵，则对于任意 列正交矩阵 ，有kVTT()max()trtrVA引理3 设 为 阶正定阵， ，则()ija1ijii,2n定理2 令 ， ，则3132(,)GGkWw 313(,)ookWw()J证明：由题意， ，其中 是3312()(,)oTobwkSdiag 12,k的前 个最大特征值。于是()b

9、wSk(5)3331()ooTobwiJtrS设 是 相对于 的所有广义特征值所对应的单位广义特征向312,GGn )bwSG量，特征值从大到小排列，记 ，由引理 1知3123(,)nW， ()Tb3(TGbwSW(6)其中对角阵 ， 。需注意的是，对角元12,)n 12(,)k并非是 相对于 的广义特征值。对 实施QR分解，即 ，12,n (bwSGGGQR其中 是列正交矩阵， 是上三角阵。对 进行分块，则QRR， (7)1201120R其中 为 阶方阵。由于 都是单位向量，所以 的对角1Rk3123,GGn ()TGTW元全为1，从而 的对角元也全为1。由引理2和引理3，可得T 113 3

10、3 3()()()ooTooTGobwJWtrSWtr113QR3(oTTtQR10() )00TIIItrtr (8)1 1113()()TGt ttrJW证毕。 由定理2知，基于 的最优鉴别向量集就是OD向量集，它们是 的前 个3()JW()bwSk最大特征值所对应的单位特征向量。3.4 基于 的最优鉴别向量集4定理1 四种准则函数的最优UDVs是同一个向量集。定理2 (1) ，11()()uojjJw,21c4(2) ，2212()()()ooujjjJwJw1,2c证明： (1) 由准则函数 对可逆矩阵的不变性即得。W(2) 由广义特征值分解的性质，存在 相对于 的广义特征向量 ，相b

11、Sw121,cp应特征值分别为 ，使得 ( )，121c 1c 0TTitjibjpSij， ，则 ， （ ）。TjtjpSTjbjjpS2/ujjjwp22()()uJ,令 ， ， ，则(,)cP 21(,c 12,1uucWw。对矩阵 实施 QR 分解，则 ，其中 ，从2uW2uuoR,)oo而有 ， 。1oR11oP用 表示 的元素，由于 为上三角阵，则有 ( )，并且ijd()1()0ijdj( ) (3)1, 1ojiiiiwdpdp ,21c1, , 1211 11() )() (T Tjbjiiiibiiiiojot tSSpdpJvd 222222, 1,1 11iiiiiii

12、idd . (4)22()()uiijJpw由于 是 的最优ODVs，所以 。 1,1,ooc 2J221()()oojjJw基于 的UDVs可由类似于FST的Jin 变换求得。()FJw为便于理论分析，下面给出三个引理：引理1 17：设 为非负定阵， 为同阶正定阵，准则函数为 ,则AB()/TJwAB满足附加条件 ( )的最优鉴别向量集 可由下述递推算法求得：0TijGij12,k记 ， ，则第 个最优鉴别向量 是广义特征方程0DI12,iw i1i(3)iPAw的最大广义特征值所对应的单位广义特征向量，其中, 。 11()TTii iiPIBD2,k引理2：在引理1中，当 时，满足附加条件

13、 ( )的最优鉴别向量集0TijBij是 相对于 的前 个最大广义特征值所对应的单位广义特征向量。 （证,kw Ak明方法类似于文献20中的定理2。 ）推论1：准则函数为 的最优OD向量集就是 的前 个最大特征值()/TJAk所对应的单位特征向量。引理3：在引理1中，设 是 维线性空间 的一个 维子空间， 是 的nnRd12,dz 5一组标准正交基，记 ，则 在 中满足附加条件 ( )的12(,)dZz ()Jw0TijwGij最优鉴别向量集为 ，其中 是 满足附 12,d ()/zJAB加条件 ( )的最优鉴别向量集，0TijGij， ， 。 （易证，略）AZTBTGZ基于 的最优OD向量集

14、 可由Foley-sammon变换(FST)求得，基1()Jw121,ookw于 的最优UD向量集 可由类似于 FST的Jin方法求得，后来Yang证明,uu了 就是 相对于 的非零广义特征值所对应的单位广义特征向量，因而2,uuk bS可由广义特征值分解求得，并且最优UD 向量的个数最多只有11个，其中 是类别数。为使讨论方便，以下都假定 。()brankScc 1kc基于 的最优UD向量集 可由广义特征分解求得，它与基于2JW212,uukw的最优UD向量集 是同一个向量集。准则函数 具有可逆矩1w1,uk 2()JW阵不变性，基于 的最优OD向量集 可由对 实施(),ookw 12,uu

15、kwSchimitd正交化即QR分解得到， Song曾使用过此向量集，但他是用Schur分解得到的。基于 的最优OD向量集 可由对 进行特征分解求得；3J3123,k ()bwS基于 的最优UD向量集()oow它与基于 的最优UD向量集 是同一个向量集。准则函数1()Jw121,uukw具有可逆矩阵不变性，因此基于 的最优OD 向量集 可由对2()JW()JW212,ookw实施Schimitd 正交化即QR分解得到，Song曾使用过此向量集，但他是用12,uukSchur分解得到的。由每个FLD准则函数都可得到两种鉴别向量集：一种是不相关鉴别向量集(Uncorrelated Discrimi

16、nant Vectors, UDVs)，满足 （ ） ，其中 是样本总体协0TitjwSijtbwS方差阵；另一种是正交鉴别向量集(Orthogonal Discriminant Vectors, ODVs )，满足（ ） 。本文试图对这四种准则的鉴别向量集进行分析和比较。0Tijwij在求取鉴别向量集时，不同的准则函数最大化方法也不同。最大化 的方法是1()JFoley-sammon变换 (FST)；最大化 的方法是广义特征值分解；最大化 的方法2()JW3W是特征值分解或广义特征值分解；最大化 的方法是迭代法。42 相关工作与本文的贡献准则函数 最早由Fisher于1936年针对两分类问题

17、提出的，后由C. R. Rao推广到多1()Jw分类问题，采用广义特征值分解(GEVD)来计算鉴别向量，得到的是最优UDVs，最优UDVs最多只有 个鉴别向量。由于对于两分类问题只有一个鉴别向量，往往不能满足实际需c6要，因此Foley-sammon 于1970s 提出了Foley-sammon 变换(FST)，得到了最优ODVs ，它最多有 个鉴别向量。后由Dauce将FST推广到多分类问题。1N准则函数 最早出现在1962年的书中，最优求解方法是GEVD方法，它既是两分2()JW类问题中的 在多分类中的推广，也是准则函数 的一种简化形式。1w4()JW准则函数 早在1990年就在书中出现过

18、，后由Geri在人脸识别中最大化边缘准则3(MMC)得到，它得到的最优解就是准则 的最优UDVs ，后han对此提出了异议，认为2()J最优解就是 的前若干个最大特征值所对应的特征向量。()bwS准则函数 最早由huang提出，但一直未能得到最佳的求解方法，不得不将其简4J化为准则函数 ，直到2007年由Yan给出了最佳的求解算法。2W本文的工作主要是比较各个准则函数下的最优鉴别向量集的函数值的大小，并由此阐述在实际问题中最优解的选取问题。分两种情况进行讨论：一是 非奇异，另一是 奇wSwS异但 非奇异。tS4最优鉴别向量集的简洁算法在零空间 中得到 个最优 OD 向量之后，要得到更多最优 O

19、D 向量，需从1(0)wd的正交补空间 中求取，这需要先得到 的1()wS1|0,TrdSxWxR1(0)wS一组基。 由于准则函数 在零空间 的补集合 中与 有相同的最优()tJ1()wS1()wS)FJ鉴别向量集，因此最优 OD 向量集 可由如下简洁算法得到： 2,k 在 中用 Yang14的算法得到前 个最优 OD 向量 ；1(0)w 12,dZ 假定已经获得前 ( )个最优 OD 向量，则第 个最优 OD 鉴别向量 是广idi1i义特征方程 的最大广义特征值所对应的单位广义特征向量，其中ibtPS(6)11()TTiitiitPIWS， 。最后得到的矩阵 的各个列1(,)idiW 1,

20、k k就是所求的最优OD向量集。12kw由于 的维数 ，由上述算法最多可以得到 个最优OD 向量。但Hughes 21指0SNcr出，鉴别向量的个数不能太多，因此 的取值通常在 与 之间。1c5()类似地，在 中得到 个最优 UD 向量之后，要得到更多的 最优 UD 向量，需从1()wd的不相关补空间 中求取。由引理 2，最优 UD1()w10|0,UTrdtSxWSxR向量集 可由如下简洁算法得到：2,k 在 中用 Yang14的算法得到前 个最优 UD 向量 ；1(0)S 12,dZ 计算广义特征方程 的非零广义特征值（从大到小排列）所对应的单位btw广义特征向量，后 个单位广义特征向量记

21、为 ，则最优 UD 向量cd12,dc集为 ，最优 UD 向量只有 个。12121,cZ 5更多具有不相关性的鉴别向量记 ， ，由于 的不相12121(,)c ddcWZ 1cspanW关补空间 恰好就是 的零空间 ，因此不可能找到更多与UbS(0)b不相关的鉴别向量。但退而求其次，可以在21,dZ 2,c7的正交补空间 中求取 个 OD 向量，虽然这 个 UD 向量与1c1c只是正交，不是不相关，但在 内它们是不相关122,ddcZ 的。由引理 3，要在 中求取 UD 向量集需要先得到 的一组基标准正交基。计算广义 特征方程 的所有广义特征值（从大到小排列）所对应的单位广义特征向量btSw，

22、记 ，对 实施 Schmit 正交化即 QR 分解，使得12,r 12(,)rH H，其中 为正交阵， 为上三角阵。不难看出QRq R，从而 。令 ，记12(,)cspan 1(,)crspanq 1(,)crVq相对于 的非 零广义特征值所对应的单位广义特征向量为TbVSTtSV，则 中的最优 UD 向量集为 。12(,)c 21,c进一步，可在子空间的正交补空间中求取 UD2,spanZ121,ddccV 向量，依此下去，最多可取 个具有一定不相关性的鉴别向量。r6 实验与分析下面分别在ORL人脸库和JEFFE人脸表情库上进行实验，并对结果进行分析。采用最近邻分类器，以 范数作为距离的度量

23、。2L6.1 ORL 人脸库ORL人脸库由40个人组成，每人10幅图像，图像之间存在一定的光照，表情，饰物等的变化。每人随机取5幅共200幅图像作为训练集，余下200幅图像作为训练集，共进行10轮，取10轮结果的平均作为最后的结果。先用PCA降维分别将每幅图像降成 维向量，再由文r中所述方法求取最优OD向量集和最优UD向量集。首先取 ，分别是由Yang 14的算19r法与Zheng 17的算法求取 中最优OD向量集和最优UD向量集 ，并以1(0)wS 239,w准则函数 计算它们的鉴别值，结果见表1。由表1可见， 中最优OD 向量集与()bJ (0)S最优UD向量集的确是一样的。表1 中最优O

24、D向量和最优UD 向量的鉴别值( )1(0)wS 51b12345678910wOD 196.23 107.90 92.247 71.550 57.652 52.734 45.039 39.367 35.289 32.883UD 196.23 107.90 92.247 71.550 57.652 52.734 45.039 39.367 35.289 32.883bJ1w1213141516w17181920OD 28.636 27.185 24.523 23.474 22.466 20.693 18.898 17.675 17.037 15.579UD 28.636 27.185 24.5

25、23 23.474 22.466 20.693 18.898 17.675 17.037 15.579b21223242526272829w30OD 15.203 13.971 13.931 12.598 12.416 12.186 11.533 11.086 10.183 9.7622UD 15.203 13.971 13.931 12.598 12.416 12.186 11.533 11.086 10.183 9.7622bJ31w32334w3536373839OD 8.8645 8.6304 8.2483 7.5796 6.9622 6.6124 6.0582 5.2203 4.97

26、77UD 8.8645 8.6304 8.2483 7.5796 6.9622 6.6124 6.0582 5.2203 4.9777再取 共10种情形，最优OD向量集与 UD向量集 ，90,r,19 12,kw8，最后将10种情形下得到的识别率进行平均，图1给出了平均识别率随40,78k增加的变化趋势。显见随着 的增加无论是最优OD向量集还是最优 UD向量集其平均识k别率先呈上升趋势，然后当 达到一定程度后开始下降，这与Hughes结论一样。表1给出是的最佳识别率和 在39与78之间的最佳识别率（括号中的第一个数字表示降维数39，第二个数字表示投影轴个数 ） ，最佳识别率平均提高0.725%

27、。r40 45 50 55 60 65 70 75 809696.59797.5个个个个个个k 个个个个个ODUD图2 ORL库中平均识别率随 增加的变化趋势方法 最优OD 最优UD最佳识别率(k=39) 96.80（ 198/39） 96.7（ 199/39）最佳识别率（k=3978 ）97.25（ 198/45） 97.70（ 199/63）表2 和 在39与78之间的最佳识别率39k6.2 JEFFE 人脸表情库JEFFE人脸表情库由10位日本女性组成，有生气、厌恶、害怕、高兴、中性、悲伤和惊奇7种表情，每人每种表情若干幅，共213幅图像。手工校正人的两眼，并将图像大小裁剪成 。取9人的

28、表情图像作为训练集，余下1人的图像作为测试集，共进行10轮，28每轮换1人，取10轮结果的平均作为最后的结果。先用PCA降维分别将每幅图像降成维向量， 共6种情形；再由文中所述的方法求取最优OD 向量集与rNl,2l最优UD向量集 ， ，最后将 6种情形下得到的识别率进行平均，1,kw ,730图2给出了平均识别率随 增加的变化趋势。显见随着 的增加无论是最优OD 向量集还是k最优UD向量集其平均识别率先呈上升趋势，然后当 达到一定程度后开始下降，这与Hughes的结论一致。 表3给出 时的最佳识别率和 在 6与30之间的最佳识别率，最佳6识别率平均提高7.40%。95 10 15 20 25

29、 30585960616263646566个个个个个个k 个个个个个ODUD图2 JEFFE库平均识别率随 增加的变化趋势方法 最优OD 最优UD最佳识别率(k=6) 60.1925（64/6） 59.7164（69/6）最佳识别率(k=630) 67.6465（69/27） 67.0578（67/24）表3 和 在6与30之间的最佳识别率k7 总结本文给出了 FLD 准则下最优 OD 向量集与最优 UD 向量集的简洁算法，并通过实验说明了适当增加鉴别向量的个数会提高识别率。参考文献1 R. A. Fisher. The use of multiple measurements in taxo

30、nomic problems. Annu. Eugenics. 7, 1936. pp: 179-188.2 J. Duchene, S. Leclercq. An optimal transformation for discriminant and principal component analysis. IEEE Trans on Pattern Analysis and Machine Intelligence. 10 (6), 1988. pp: 978-983.3 Sammon J W. An optimal discriminant plane. IEEE Trans on C

31、omputers. 19 (9), 1970. pp: 826- 829.4 D. H. Foley, J. W. Sammon. An optimal set of discriminant vectors. IEEE Trans on Computers. 24 (3), 1975. pp: 281-289.5 Z. Jin, J.Y. Yang, Z.S. Hu, Z. Lou. Face recognition based on uncorrelated discriminant transformation. Pattern Recognition. 34 (7), 2001. pp

32、: 1405-1416.6 Jian Yang, Jing-yuYang. Why can LDA be performed in PCA transformed space? Pattern Recognition. 36 , 2003. pp: 563-566.7 H. Yu and J. Yang, “A direct LDA algorithm for high-dimensional data with application to face recognition,” Pattern Recognition., 34(10), 2001. pp: 20672070.8 J. Yan

33、g, A. F. Frangi, J.Y. Yang, D. Zhang, Z. Jin. KPCA Plus LDA: A Complete Kernel Fisher Discriminant Framework for Feature Extraction and Recognition. IEEE Transactions on Pattern Anlysis and Machine Intellig- ence. 27(2), 2005. pp: 230-244.9 K. Liu, Y.Q. Cheng, J.Y. Yang, X. Liu. An efficient algorit

34、hm for Foley-Sammon optimal set of discriminant vectors by algebraic method, Int. J. Pattern Recog. Artif. Intell. 6 (5), 1992. pp: 817-829.10 Z.-Q. Hong and J.-Y. Yang, “Optimal discriminant plane for a small number of samples and design method of classifier on the plane,” Pattern Recognition. 24(4

35、), 1991. pp: 31732411 Peter N. Belhumeur, Joao P. Hespanha, and David J. Kriegman. Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection. IEEE Transactions on PAMI. 19(7), 1997. pp: 71172012 Q.Tian et al, Comparison of statistica1 pattern-recognition algorithms for hybrid pr

36、ocessing. I: Linear map- 10ing algorith, J.opt.Soc. Am . A. 5(10), 1988. pp:1655-166913 Jun Liu, Songcan Chen and Xiaoyang Tan. A study on three linear discriminant analysis based methods in small sample size problem. Pattern Recognition. 41(1), 2008. pp: 102-11614 Jian Yang, J.Y. Yang. An Optimal F

37、LD algorithm for facial feature extraction. SPIE Proceedings of the Intell- igent Robots and Computer Vision: Algorithms, Techniques, and Active Vision. 4572, 2001. pp: 438-44415 L.F. Chen, H.Y. M. Liao, M.T. Ko, J.C. Lin, and G.J. Yu. A new LDA-based face recognition system which can solve the smal

38、l sample size problem. Pattern Recognition. 33, 2000. pp: 1713-1726.16 Yue-Fei Guo, LideWu, Hong Lu, Zhe Feng, Xiangyang Xue. Null FoleySammon transform. Pattern Recog- nition. 39,2006. pp: 2248-2251.17 W.M. Zheng, L. Zhao, C.R. Zou. An efficient algorithm to solve the small sample size problem for

39、LDA. Pattern Recogn. 37 (5), 2004. pp: 1077-1079.18 A.K. Qin, P.N. Suganthan, M. Loog. Generalized null space uncorrelated Fisher discriminant analysis for lin- ear dimensionality reduction. Pattern Recognition. 39, 2006. pp: 1805-1808.19 杨静宇. 具有统计不相关性的最佳鉴别特征空间的维数定理. 计算机学报. 26(1),2003. pp: 110-115.20 杨健. 统计不相关最优鉴别分析的理论与算法. 南京理工大学学报 . 26(2), 2002. pp: 179-18221 Hughes G F. On the mean accuracy of statistical pattern recognizers. IEEE Transactions on Information Theory, 14 (1), 1968. pp: 55-63.