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

四种FLD准则函数的最优鉴别向量集摘要本文在最优Fisher线性鉴别(FLD)算法的基础上讨论了FLD准则下的最优正交鉴别(OD)向量集与最优不相关鉴别(UD)向量集的性质与求解问题，证明了类内协方差阵的零空间中的最优OD向量集与最优UD向量集的等价性，给出了求取FLD准则下的最优OD向量集与最优UD向量集的简洁算法和求取更多鉴别向量方法。在ORL人脸库与JEFFE人脸表情库上进行实验，实验结果表明适当增加鉴别向量的个数有利于识别率的提高。关键词FLD准则最优FLD算法最优OD向量集最优UD向量集1引言 Fisher线性鉴别（FLD）分析是基于FLD准则的一种传统模式特征提取方法，在模式识别与计算机视觉等方面有着广泛的应用。FLD准则就是寻找一个或多个投影方向，对原始数据进行投影，使投影后新数据的类间离散度达到最大而类内离散度达到最小，而投影后的新数据就是所需的模式特征。用以描述FLD准则的准则函数有很多种，其中最为典型也最为常见的四种FLD准则函数为： (a) (b) (c) (d) 其中分别表示原始数据的类间协方差阵与类内协方差阵。准则函数最早是由R. Fisher针对两分类问题提出的，和是它在多分类问题中的推广，尽管它也适用于多分类问题。2006年Li提出了最大间距准则(MMC)，就是MMC函数，显然也描述了FLD准则，因此它也可看作是FLD准则函数，实际上早在1990文献已提到过。最大化准则函数可得多个投影向量，最大化准则函数、或可得由多个投影向量组成的投影矩阵。投影向量也称为鉴别向量，在实际应用中一般要求鉴别向量单位化，即 ()，单位化向量集合常称为鉴别向量集4。在最大化准则函数求取鉴别向量集时，通常需附加一定的条件，目前人们使用的附加条件主要有两种：一种是附加正交条件 ()，相应的向量集称为正交鉴别(Orthogonal Discriminant，OD)向量集；另一种是附加不相关条件 ()，它可使由不同鉴别向量投影所得的模式特征具有统计不相关性，由此得到的鉴别向量集称为不相关鉴别 (Uncorrelated Discriminant Vectors，UD) 向量集，其中是样本总体协方差阵。更一般的附加条件为() (1)其中为正定阵。不同的可得到不同的鉴别向量集，因此每一个准则函数都可得无穷多种鉴别向量集。现在的问题是，在这么多种鉴别向量集中，哪种鉴别向量集是最优的？本文以准则函数值为标准，研究上述四种准则函数的最优鉴别向量集。由于UD向量集中鉴别向量集最多只有个，所以以下均假定，其中是样本类别数。2非奇异情形2.1基于的最优鉴别向量集准则函数满足附加条件(1)的鉴别向量集可由Foley-sammon变换(FST)得到：记，则第个鉴别向量是广义特征方程的最大广义特征值所对应的单位广义特征向量()，其中 (2)当时，得到的就是基于的OD向量集；当时，得到就是基于的UD向量集。文献证明了基于的UD向量集就是相对于的非零广义特征值对应的单位广义特征向量。本文未能得到基于的最优鉴别向量集2.2基于的最优鉴别向量集先讨论准则函数的UD向量集，它们是相对于的非零广义特征值对应的单位广义特征向量。令，则其函数值 (3)文献有一个结论，应用到准则函数中可描述为定理1对任意的矩阵，都有 (4)由引理1知，就是基于的最优鉴别向量集。由于函数对可逆矩阵具有不变性，所以基于的最优鉴别向量集并不唯一。例如，对实施QR分解，即令，其中是列正交矩阵，是上三角阵，则也是最优鉴别向量集，同时也是基于的OD向量集。3.3基于的最优鉴别向量集准则函数满足附加条件(1)的鉴别向量集就是相对于的前个最大广义特征值所对应的单位广义特征向量。特别地，基于的OD向量集就是的前个最大特征值所对应的单位特征向量，基于的UD向量集就是相对于的非零广义特征值对应的单位广义特征向量。下面的一些引理可以帮助我们找到基于的最优鉴别向量集。引理1设为两个阶实对称方阵，是相对于的广义特征值所对应的单位广义特征向量，广义特征值从大到小排列，则，其中，为对角阵。引理2设为阶对称阵，为其前个最大特征值所对应的单位正交特征向量矩阵，则对于任意列正交矩阵，有引理3设为阶正定阵，则定理2令，则证明：由题意，其中是的前个最大特征值。于是 (5)设是相对于的所有广义特征值所对应的单位广义特征向量，特征值从大到小排列，记，由引理1知， (6)其中对角阵，。需注意的是，对角元并非是相对于的广义特征值。对实施QR分解，即，其中是列正交矩阵，是上三角阵。对进行分块，则，(7)其中为阶方阵。由于都是单位向量，所以的对角元全为1，从而的对角元也全为1。由引理2和引理3，可得 (8) 证毕。由定理2知，基于的最优鉴别向量集就是OD向量集，它们是的前个最大特征值所对应的单位特征向量。3.4基于的最优鉴别向量集定理1四种准则函数的最优UDVs是同一个向量集。定理2(1) ，(2) ，证明： (1) 由准则函数对可逆矩阵的不变性即得。(2) 由广义特征值分解的性质，存在相对于的广义特征向量，相应特征值分别为，使得()，则，（）。令，则。对矩阵实施QR分解，则，其中，从而有，。用表示的元素，由于为上三角阵，则有()，并且 () (3) . (4) 由于是的最优ODVs，所以。基于的UDVs可由类似于FST的Jin变换求得。为便于理论分析，下面给出三个引理：引理117：设为非负定阵，为同阶正定阵，准则函数为,则满足附加条件()的最优鉴别向量集可由下述递推算法求得：记，则第个最优鉴别向量是广义特征方程 (3)的最大广义特征值所对应的单位广义特征向量，其中, 。引理2：在引理1中，当时，满足附加条件()的最优鉴别向量集是相对于的前个最大广义特征值所对应的单位广义特征向量。（证明方法类似于文献20中的定理2。）推论1：准则函数为的最优OD向量集就是的前个最大特征值所对应的单位特征向量。引理3：在引理1中，设是维线性空间的一个维子空间，是的一组标准正交基，记，则在中满足附加条件 ()的最优鉴别向量集为，其中是满足附加条件()的最优鉴别向量集，。（易证，略）基于的最优OD向量集可由Foley-sammon变换(FST)求得，基于的最优UD向量集可由类似于FST的Jin方法求得，后来Yang证明了就是相对于的非零广义特征值所对应的单位广义特征向量，因而可由广义特征值分解求得，并且最优UD向量的个数最多只有个，其中是类别数。为使讨论方便，以下都假定。基于的最优UD向量集可由广义特征分解求得，它与基于的最优UD向量集是同一个向量集。准则函数具有可逆矩阵不变性，基于的最优OD向量集可由对实施Schimitd正交化即QR分解得到，Song曾使用过此向量集，但他是用Schur分解得到的。基于的最优OD向量集可由对进行特征分解求得；基于的最优UD向量集它与基于的最优UD向量集是同一个向量集。准则函数具有可逆矩阵不变性，因此基于的最优OD向量集可由对实施Schimitd正交化即QR分解得到，Song曾使用过此向量集，但他是用Schur分解得到的。由每个FLD准则函数都可得到两种鉴别向量集：一种是不相关鉴别向量集(Uncorrelated Discriminant Vectors, UDVs)，满足（），其中是样本总体协方差阵；另一种是正交鉴别向量集(Orthogonal Discriminant Vectors, ODVs )，满足（）。本文试图对这四种准则的鉴别向量集进行分析和比较。在求取鉴别向量集时，不同的准则函数最大化方法也不同。最大化的方法是Foley-sammon变换(FST)；最大化的方法是广义特征值分解；最大化的方法是特征值分解或广义特征值分解；最大化的方法是迭代法。2相关工作与本文的贡献准则函数最早由Fisher于1936年针对两分类问题提出的，后由C. R. Rao推广到多分类问题，采用广义特征值分解(GEVD)来计算鉴别向量，得到的是最优UDVs，最优UDVs最多只有个鉴别向量。由于对于两分类问题只有一个鉴别向量，往往不能满足实际需要，因此Foley-sammon于1970s提出了Foley-sammon变换(FST)，得到了最优ODVs，它最多有个鉴别向量。后由Dauce将FST推广到多分类问题。准则函数最早出现在1962年的书中，最优求解方法是GEVD方法，它既是两分类问题中的在多分类中的推广，也是准则函数的一种简化形式。准则函数早在1990年就在书中出现过，后由Geri在人脸识别中最大化边缘准则(MMC)得到，它得到的最优解就是准则的最优UDVs，后han对此提出了异议，认为最优解就是的前若干个最大特征值所对应的特征向量。准则函数最早由huang提出，但一直未能得到最佳的求解方法，不得不将其简化为准则函数，直到2007年由Yan给出了最佳的求解算法。本文的工作主要是比较各个准则函数下的最优鉴别向量集的函数值的大小，并由此阐述在实际问题中最优解的选取问题。分两种情况进行讨论：一是非奇异，另一是奇异但非奇异。4最优鉴别向量集的简洁算法在零空间中得到个最优OD向量之后，要得到更多最优OD向量，需从的正交补空间中求取，这需要先得到的一组基。 由于准则函数在零空间的补集合中与有相同的最优鉴别向量集，因此最优OD向量集可由如下简洁算法得到： 在中用Yang14的算法得到前个最优OD向量； 假定已经获得前()个最优OD向量，则第个最优OD鉴别向量是广义特征方程的最大广义特征值所对应的单位广义特征向量，其中 (6)，。最后得到的矩阵的各个列就是所求的最优OD向量集。由于的维数，由上述算法最多可以得到个最优OD向量。但Hughes21指出，鉴别向量的个数不能太多，因此的取值通常在与之间。类似地，在中得到个最优UD向量之后，要得到更多的最优UD向量，需从的不相关补空间中求取。由引理2，最优UD向量集可由如下简洁算法得到： 在中用Yang14的算法得到前个最优UD向量； 计算广义特征方程的非零广义特征值（从大到小排列）所对应的单位广义特征向量，后个单位广义特征向量记为，则最优UD向量集为，最优UD向量只有个。5更多具有不相关性的鉴别向量记，由于的不相关补空间恰好就是的零空间，因此不可能找到更多与不相关的鉴别向量。但退而求其次，可以在的正交补空间中求取个OD向量，虽然这个UD向量与只是正交，不是不相关，但在内它们是不相关的。由引理3，要在中求取UD向量集需要先得到的一组基标准正交基。计算广义特征方程的所有广义特征值（从大到小排列）所对应的单位广义特征向量，记，对实施Schmit正交化即QR分解，使得，其中为正交阵，为上三角阵。不难看出，从而。令，记相对于的非零广义特征值所对应的单位广义特征向量为，则中的最优UD向量集为。进一步，可在子空间的正交补空间中求取UD向量，依此下去，最多可取个具有一定不相关性的鉴别向量。6实验与分析下面分别在ORL人脸库和JEFFE人脸表情库上进行实验，并对结果进行分析。采用最近邻分类器，以范数作为距离的度量。6.1ORL人脸库ORL人脸库由40个人组成，每人10幅图像，图像之间存在一定的光照，表情，饰物等的变化。每人随机取5幅共200幅图像作为训练集，余下200幅图像作为训练集，共进行10轮，取10轮结果的平均作为最后的结果。先用PCA降维分别将每幅图像降成维向量，再由文中所述方法求取最优OD向量集和最优UD向量集。首先取，分别是由Yang14的算法与Zheng17的算法求取中最优OD向量集和最优UD向量集，并以准则函数计算它们的鉴别值，结果见表1。由表1可见，中最优OD向量集与最优UD向量集的确是一样的。表1中最优OD向量和最优UD向量的鉴别值()OD196.23107.9092.24771.55057.65252.73445.03939.36735.28932.883UD196.23107.9092.24771.55057.65252.73445.03939.36735.28932.883OD28.63627.18524.52323.47422.46620.69318.89817.67517.03715.579UD28.63627.18524.52323.47422.46620.69318.89817.67517.03715.579OD15.20313.97113.93112.59812.41612.18611.53311.08610.1839.7622UD15.20313.97113.93112.59812.41612.18611.53311.08610.1839.7622OD8.86458.63048.24837.57966.96226.61246.05825.22034.9777UD8.86458.63048.24837.57966.96226.61246.05825.22034.9777再取共10种情形，最优OD向量集与UD向量集，最后将10种情形下得到的识别率进行平均，图1给出了平均识别率随增加的变化趋势。显见随着的增加无论是最优OD向量集还是最优UD向量集其平均识别率先呈上升趋势，然后当达到一定程度后开始下降，这与Hughes结论一样。表1给出是的最佳识别率和在39与78之间的最佳识别率（括号中的第一个数字表示降维数，第二个数字表示投影轴个数），最佳识别率平均提高0.725%。图2ORL库中平均识别率随增加的变化趋势方法最优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之间的最佳识别率6.2JEFFE人脸表情库JEFFE人脸表情库由10位日本女性组成，有生气、厌恶、害怕、高兴、中性、悲伤和惊奇7种表情，每人每种表情若干幅，共213幅图像。手工校正人的两眼，并将图像大小裁剪成。取9人的表情图像作为训练集，余下1人的图像作为测试集，共进行10轮，每轮换1人，取10轮结果的平均作为最后的结果。先用PCA降维分别将每幅图像降成维向量，共6种情形；再由文中所述的方法求取最优OD向量集与最优UD向量集，最后将6种情形下得到的识别率进行平均，图2给出了平均识别率随增加的变化趋势。显见随着的增加无论是最优OD向量集还是最优UD向量集其平均识别率先呈上升趋势，然后当达到一定程度后开始下降，这与Hughes的结论一致。表3给出时的最佳识别率和在6与30之间的最佳识别率，最佳识别率平均提高7.40%。图2JEFFE库平均识别率随增加的变化趋势方法最优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之间的最佳识别率7总结本文给出了FLD准则下最优OD向量集与最优UD向量集的简洁算法，并通过实验说明了适当增加鉴别向量的个数会提高识别率。参考文献1 R. A. Fisher. The use of multiple measurements in taxonomic 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 Computers. 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: 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. Yang, 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 algorithm 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), 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 processing. I: Linear map- ing 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 FLD algorithm for facial feature extraction. SPIE Proceedings of the Intell- igent Robots and Computer Vision: Algorithms, Techniques, and Active Vision. 4