二维线性判别分析

1、二维线性判别分析摘要线性判别分析（LDA）是一个常用的进行特征提取和降维的方法。在许多涉及到高维数据，如人脸识别和图像检索的应用中被广泛使用。经典的LDA方法固有的限制就是所谓的奇异性问题，即当所有的散列矩阵是奇异的时，它就不再适用了。比较有名的解决奇异性问题的方法是在使用LDA方法之前先用主成分分析（PCA）对数据进行降维。这个方法就叫做PCA+LDA，在人脸识别领域被广泛应用。然而，由于涉及到散列矩阵的特征值分解，这个方法在时间和空间上都需要很高的成本。在本文中，我们提出了一种新的LDA算法，叫做2D-LDA，即二维线性判别分析方法。2D-LDA方法彻底解决了奇异性问题，并且具有很高的效率

2、。2D-LDA和经典LDA之间主要的区别在于数据表示模型。经典LDA采用矢量表示数据，而2D-LDA使用矩阵表示数据。我们对2D-LDA+LDA，即如何结合2D-LDA和经典LDA，在经典LDA之前使用2D-LDA进一步降维的问题进行了研究。将本文提出的算法应用于人脸识别，并与PCA+LDA进行了比较。实验表明：2D-LDA+LDA的方法识别更精确，并且效率更高。1概述线性判别分析24是一个著名的特征提取和降维的方法。已经被广泛应用于人脸识别、图像检索限微列阵数据分类等应用中。经典的LDA算法就是将数据投影到低维的向量空间，使类间距离和类内距离的比值最大化，从而得到最佳的分类效果。最佳的投影方

3、向可以通过散列矩阵的特征值分解计算得到。经典LDA算法的一个限制是其目标函数的散列矩阵必须是奇异的。对于许多应用了，如人脸识别，所有散列矩阵的问题都可以是奇异的，因为其数据都是高维的，并且通常矩阵的尺寸超过了数据点的额数目。这就是所谓的“欠采样或奇异性问题5”。近年来，许多用于解决这种高维、欠采样问题的方法被提出，包括伪逆LDA、PCA+LDA和正则LDA。在文献中可以了解更多细节。在这些LDA的扩展方法中，PCA+LDA受到了广泛的关注，尤其实在人脸识别领域。这个方法包括两个阶段，其中一个阶段就是在LDA方法之前使用PCA对数据进行降维。以前的LDA扩展一般是大型矩阵的特征值分解计算，这不仅

4、降低了效率，也使得它很难扩展到大型数据集。在本文中，我们提出了一种新的方法来解决此前的LDA扩展的特征分解计算的问题。新颖之处在于它采用了不同的数据表示模型。在这种模式下，每个数据被表示为一个矩阵，而不是一个向量，并且数据集被表示为矩阵的集合，而不是一个单一的大矩阵。这种模式在文献789中被用于对SVD和PCA的泛化。不同于经典的LDA，我们考虑的是数据在二维空间中的投影。在第3节中，我们将降维问题规划为一个优化问题。不同于经典的LDA，没有已有的解决优化问题的方法，于是，我们探索得到了一个新的方法，即2D-LDA。为了更进一步降低数据的维数，我们将2D-LDA和LDA进行了结合，即2D-LD

5、A+LDA。我们在三个著名的人脸数据集上对2D-LDA、2D-LDA+LDA方法进行了测试，和目前被广泛应用于人脸识别的PCA+LDA方法进行了比较。实验结果表明：1、2D-LDA方法适用于高维采样数据，如人脸图像，并且不用考虑经典LDA方法的奇异性问题。2、2D-LDA和2D-LDA+LDA相较于PCA+LDA方法在时间和空间上的消耗明显降低，而识别精度相差不多。2LDA概述在这个部分，我们对经典的LDA方法进行了简单的介绍。给定一个数据矩阵4GRE，经典的LDA旨在找到一个变换G6RN曲，对于A的每一列，在N维空间中对应在L维空间的向量。即：G:a6Rntb=GTa6Ri(I<N)i

6、ii同样的，经典lda方法旨在找到一个向量空间g包含gt1=1，其中G=9,g2,.,gl，这样，每一个a.通过9Ta.,gTa.tgRl投射到向量空间g中。假定初始数据被分为k个类z=厲，,n，其中几包含了第i类的®个数据点，并且kn.=no经典LDA旨在找到这样的最佳转换G使得原始高维类I=1I的结构保存在低维空间中。一般来说，如果每个类都是紧密分组，但能够很好的与其他类分离开来，那么称这个为高质量集群。在判别分析中，定义两个矩阵来衡量集群质量：类内散列度矩阵Sw:S=kxmxmtwi=1兀印：ii类间散列度矩阵Sb:kn.ii=1mim2叫-叮其中表示第i类的中心点，表示全局中

7、心点。通过和Sb可以很容易的计算出类内向量距离和类间距离。在线性变换G产生的低维空间（或线性投影向量空间G）中，类内距离矩阵和类间距离矩阵是：Sl=GtSG，Sl=GtSG.一个最佳变换G能够最大化Sf,括（见4）：最小化S俟线性判别中常见的优化方法包max&traceSl-1SfandmintraceSl-1SlGbw(1)等价于下面的广义特征值问题：Sx=ASbi如果Sb是非奇异的，则有k-1个对应的特征矩阵向量的非零特征值。因此,经典的LDA算法最多降维k-1。一个稳定的计算特征值分解的方法是应用SVD的散射矩阵，可在文献6了解细节。3二维线性判别分析本文提出的2D-LDA和经典

8、LDA最大的不同在于数据的表示模型。经典的LDA使用矢量表示数据，2D-LDA使用矩阵表示数据。在本节我们将看到，2D-LDA的数据矩阵表示模型导致了更小尺寸的矩阵的特征分解。更具体地说，2D-LDA的特征分解的矩阵尺寸为rXr和cXc,它比经典LDA的矩阵尺寸更小,这大大减少了LDA算法的时间和空间复杂度。不同于经典的LDA，2D-LDA认为l1X右维空间论只是以下两个空间的张量积：£包含叫l=i，只包含v.1=1。定义两个矩阵£=咛,乜wR曲i,只=%,乜wRc4。然后向量XwRrxc投影到空间£©只得到£TXeR2。让舍wdxc,i=1,

9、.,血在数据集中有n幅图像，分为k个类:n1,n，类口中有几幅图像。让M.=2X,1<i<k表示第i类的平均值,11n.Awni；匚冋表示全局平均值。在2D-LDA方去中，我们认为图像是二维信号,目的是找到两个变换矩阵£wRrxli和冗wRcxl2。类似于经典LDA,2D-LDA方法旨在找到两个投影变换L和R,能够让原始高维空间类的结构在低维空间得到保留。矩阵之间的相似性度量是一个自然的Frobenius范数8。在这种度量标准下，类内距离几和类间距离0,可以按照以下方法计算:i=1xwmX-MiDb使用trace属性，即traceMMTM；，对于任何矩阵“我们可以得到:D

10、=tracewki=1xwntXMiXMtiD1=tracekn.MMMMtbii=1Ii在线性变换L和R产生的低维空间中，类内距离和类间距离可以表示为:D=tracewkLTXMRRTXMTLiii=1xwntD=tracebknLtMMRRtMMtLiiii=1最优的线性变换L和R可以让取最小值，Db取最大值。由于计算最优变换L和R的难度，我们推导出一个迭代算法。更具体地说，对于一个固定的R，我们可以通过求解一个优化问题来计算最优变换L。在计算变换L的同时，我们可以通过解决另一个优化问题来更新变换R。具体步骤如下。线性变换L的计算：对于一个固定的变换R，Dw和$可以改写为：D=traceL

11、tSrL,D=traceLtSLwwbb算法：2D-LDA坷,An,J,l2输入：坷,An,件,l2输出1234计算第i个类的平均值=丄xm%；1n.XEni计算全局的平均值M=1kJX;n片1X印：心辽l2,0*对于1<j<lni=1Eni'kSrX-M.RRTX-M.twij-1j-1ii=1ntkSrnM-MTRRTM-Mbiij-1j-1ii=1计算第£个特征向量01l=1ofSR-1SRLjY0,0l156789kS厶X-MTLLTXMwiJjii=1乂印：kS厶nMMTLLTMMbii/ii=1计算第l2个特征向量0曙l=1OfSL-1SLRj即一隣2

12、循环迭代10厶厶/,RR11. BlLTAlR,I=1,.,n;12. 返回L,R,片,Bn其中SR=wi=1XEniX-MRRTX-Mtiii=1nM-MtRRtM-Miii线性变换R的计算:接下来，计算线性变换R。对于一个固定的变换L,Dw和$可以改写为:=traceRtSlRWDb=traceRtSlRb其中kSL=wX-MTLLTX-Miisb=nM-MtLLtM-Miii同样，最优的R可以通过解决下面的优化问题：maxtraceRtSlR-1RtSlRRWb来求解。该解法可以通过解决一个广义特征值问题获得：SLX=ASLX。一般来说，SL是非奇异的，所以最优的R可以通过对SL-1SL

13、作特征值分解来获得。需要注意的是矩阵七和S*的大小为cxc，远要小于和为的尺寸。Algorithm2D-LDA.给出了2D-LDA算法的伪代码。可以很清楚的看到，算法的主要计算还是集中在Algorithm2D-LDA的第4,6,11行,算法的时间复杂度为0nmaxI"厂+c2/，其中I代表的是迭代次数。2D-LDA算法依赖于最初的的选择。我们的实验证明选择R0=姑0丁能够获得精确的结果，其中如为单位矩阵。我们在整个实验中都是使用这个初始的心。由于图像的宽和高一般是近似的，即心帀，在论文中我们将儿和/2设置为同一个值d。但是这个算法只能应用在一般的情况。通过这个简化，2D-LDA算法的

14、时间复杂度变为0ndNI。2D-LDA算法的空间复杂度为0rc=0N。该算法的低空间复杂度的关键在于選，S$，S匕和S彳这4个矩阵可以通过读取矩阵令逐步构建。3.12D-LDA+LDA如引言中所介绍的，PCA常用于在LDA之前对数据进行降维以解决经典LDA的奇异性问题。在本章节中，我们将2D-LDA和LDA方法进行了结合，即2D-LDA+LDA。由于低维数据有利于LDA的处理，那么就通过2D-LDA对数据进行进一步降维。具体地说，在通过2D-LDA+LDA方法的第一个阶段，将每一个图像令ERrxc降维成耳eRdxd，其中d<minr,c。在第二阶段，每一个巧首先被转换成向量-eRd2（矩

15、阵向量对齐），然后-通过LDA进一步降维bfeRk-1，其中k1<d2，k是类的个数。2D-LDA+LDA方法第一阶段的时间复杂度为0ndNI，第二阶段的时间复杂度为0nd22。假设n<d2，则总的时间复杂度为0,n（NI+d3。4实验在本章节，我们对2D-LDA方法和2D-LDA+LDA方法的人脸图像识别性能进行了评估，并和广泛应用于人脸识别的PCA+LDA方法进行了比较。所有实验都是在1GB内存、1.80GHz的Linux机器上进行。对于所有实验都是使用最邻近算法计算分类精度。数据集：在实验中，我们使用了三组人脸数据集：PIX，ORL，PIE，PIX包括30个人的300幅图像，

16、图像尺寸是512x512，我们归一化到100x100。ORL包括40个人的400幅图像，图像尺寸是92x112。PIE是CMUPIE人脸图像集的子集，包括63个人的6615幅图像，图像尺寸是640x480,统一到220x175。24ga10112H1624G810H214讪诃却24G810惟141G询33NumoerofMefKgri*huntwolriaraacrNuTtKr出riarabcns图1迭代次数对结果的影响（从左至右:PIX,Orl,PIE）实验1.研究迭代次数I对结果的影响在该实验中，我们研究了2D-LDA方法中迭代次数对于算法的影响。结果如图1所示,X轴表示迭代次数,Y轴表示

17、分类精度。在算法中，我们通常取d=10。很显然，对于迭代次数的变换，两个方法的分类精度曲线都是稳定的，不随迭代次数变化而变化。一般情况下，2D-LDA+LDA方法的精度曲线比2D-LDA更加稳定。因此，我们只需要在2D-LDA算法中进行一次循环，即取/=1,两个算法的运行时间明显减少。实验2.研究降维度d对于结果的影响在本次实验中，我们研究了2D-LDA方法的变换空间中降维度数对于2D-LDA和2D-LDA+LDA算法的影响。我们做了大量的实验，对人脸数据集采用不同的降维度数d进行实验。结果如图2所示,X轴代表降维度数（1到15），Y轴代表使用最邻近方法进行分类的分类精度。如图中所示，所有数据

18、集的分类精度曲线都稳定在4到6之间。实验3.比较两种算法的分类精度和效率在本次实验中，我们就该算法的分类精度和效率和PCA+LDA算法进行了比较,结果如表1。我们可以看到,2D-LDA+LDA算法在分类精度方面和PCA+LDA算法效果差不多，略优于2D-LDA算法。这说明2D-LDA+LDA算法的LDA阶段不仅对数据进行可降维，还提高了整个算法的分类精度。表1中另一个重要结果是2D-LDA算法比PCA+LDA快了将近一个数量级，和2D-LDA+LDA相同。通过上述实验，我们可以得出，2D-LDA+LDA算法比PCA+LDA算法效率更高。虽然两种方法在分类精度方面一致，但2D-LDA+LDA算法

19、的时间和空间复杂度明显更低。5总结本文提出了一个高效的降维算法，即2D-LDA。2D-LDA是LDA算法的扩展。2D-LDA和LDA最主要的不同在于2D-LDA使用矩阵模型表示图像数据，而LDA算法使用向量表示数据。相比于LDA方法,2D-LDA对内存的需求更小，并且时间复杂度也更低，处理大型人脸数据集更加理想，同时也避免了经典LDA算法的奇异性问题。我们也将2D-LDA和LDA进行了结合，即2D-LDA+LDA，通过2D-LDA方法进一步降维数据，效果比LDA更好。实验表明2D-LDA方法和2D-LDA+LDA方法在分类精度方面和PCA+LDA方法相差无几，而且时间和DatasetPCA+L

20、DA2DLDA2DLDA+LDAAccuracyTime(Sec)AccuracyTime(Se)AccuracyTime(Scc)P1X98.00%7.7397.33%1.6998.50%1.73ORL9775%12.597.50%2449S.00%2.19PIE9932%153100%157参考文献1 P.N.Belhumeour,J.P.Hespanha,andD.J.Kriegman.Eigenfacesvs.Fisherfaces:Recognitionusingclassspecificlinearprojection.IEEETransactionsonPatternAnalys

21、isandMachineIntelligence,19(7):711-720,1997.2 R.O.Duda,P.E.Hart,andD.Stork.PatternClassification.Wiley,2000.3 S.Dudoit,J.Fridlyand,andT.P.Speed.Comparisonofdiscriminationmethodsfortheclassificationoftumorsusinggeneexpressiondata.JournaloftheAmericanStatisticalAssociation,97(457):77-87,2002.4 K.Fukunaga.IntroductiontoStatisticalPatternClassification.AcademicPress,SanDiego,California,USA,1990.5 W.J.Krzanowski,P.Jonathan,W.VMcCarthy,andM.R.Thomas.Discr