《二维线性判别分析概要》由会员分享，可在线阅读，更多相关《二维线性判别分析概要（10页珍藏版）》请在金锄头文库上搜索。
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是一个著名的特征提取和降维的方法。已经被广泛应用于人脸识别1、图像检索6、微列阵数据分类3等应用中。经典的LDA算法就是将数据投影到低维的向量空间，使类间距离和类内距离的比值最大化，从而得到最佳的分类效果。最佳
3、的投影方向可以通过散列矩阵的特征值分解计算得到。经典LDA算法的一个限制是其目标函数的散列矩阵必须是奇异的。对于许多应用了，如人脸识别，所有散列矩阵的问题都可以是奇异的，因为其数据都是高维的，并且通常矩阵的尺寸超过了数据点的额数目。这就是所谓的“欠采样或奇异性问题5”。近年来，许多用于解决这种高维、欠采样问题的方法被提出，包括伪逆LDA、PCA+LDA和正则LDA。在文献5中可以了解更多细节。在这些LDA的扩展方法中，PCA+LDA受到了广泛的关注，尤其实在人脸识别领域1。这个方法包括两个阶段，其中一个阶段就是在LDA方法之前使用PCA对数据进行降维。以前的LDA扩展一般是大型矩阵的特征值分解
4、计算，这不仅降低了效率，也使得它很难扩展到大型数据集。在本文中，我们提出了一种新的方法来解决此前的LDA扩展的特征分解计算的问题。新颖之处在于它采用了不同的数据表示模型。在这种模式下，每个数据被表示为一个矩阵，而不是一个向量，并且数据集被表示为矩阵的集合，而不是一个单一的大矩阵。这种模式在文献789中被用于对SVD和PCA的泛化。不同于经典的LDA，我们考虑的是数据在二维空间中的投影。在第3节中，我们将降维问题规划为一个优化问题。不同于经典的LDA，没有已有的解决优化问题的方法，于是，我们探索得到了一个新的方法，即2D-LDA。为了更进一步降低数据的维数，我们将2D-LDA和LDA进行了结合，
5、即2D-LDA+LDA。我们在三个著名的人脸数据集上对2D-LDA、2D-LDA+LDA方法进行了测试，和目前被广泛应用于人脸识别的PCA+LDA方法进行了比较。实验结果表明：1、2D-LDA方法适用于高维采样数据，如人脸图像，并且不用考虑经典LDA方法的奇异性问题。2、2D-LDA和2D-LDA+LDA相较于PCA+LDA方法在时间和空间上的消耗明显降低，而识别精度相差不多。2 LDA概述在这个部分，我们对经典的LDA方法进行了简单的介绍。给定一个数据矩阵ARNn，经典的LDA旨在找到一个变换GRNl，对于A的每一列ai，在N维空间中对应在L维空间的向量bi。即：G:aiRNbi=GTaiR
6、l(lN)同样的，经典LDA方法旨在找到一个向量空间G包含gii=1l，其中G=g1,g2,.,gl，这样，每一个ai通过g1Tai,glTaiTRl投射到向量空间G中。假定初始数据被分为k个类A=1,k，其中i包含了第i类的ni个数据点，并且i=1kni=n。经典LDA旨在找到这样的最佳转换G使得原始高维类的结构保存在低维空间中。一般来说，如果每个类都是紧密分组，但能够很好的与其他类分离开来，那么称这个为高质量集群。在判别分析中，定义两个矩阵来衡量集群质量：类内散列度矩阵Sw：Sw=i=1kxix-mix-miT类间散列度矩阵Sb：Sb=i=1knim1-m2m1-m2T其中mi=1nixi
7、x表示第i类的中心点，m=1ni=1kxix表示全局中心点。通过Sw和Sb可以很容易的计算出类内向量距离和类间距离。在线性变换G产生的低维空间（或线性投影向量空间G）中，类内距离矩阵和类间距离矩阵是：SbL=GTSbG， SwL=GTSwG.一个最佳变换G能够最大化SbL，最小化SwL。线性判别中常见的优化方法包括（见4）：maxGtraceS2L-1SbL and minGtraceSbL-1SwL (1)等价于下面的广义特征值问题：Sbx=Swx，0如果Sb是非奇异的，则有k-1个对应的特征矩阵向量的非零特征值。因此，经典的LDA算法最多降维k-1。一个稳定的计算特征值分解的方法是应用SV
8、D的散射矩阵，可在文献6了解细节。3 二维线性判别分析本文提出的2D-LDA和经典LDA最大的不同在于数据的表示模型。经典的LDA使用矢量表示数据，2D-LDA使用矩阵表示数据。在本节我们将看到，2D-LDA的数据矩阵表示模型导致了更小尺寸的矩阵的特征分解。更具体地说，2D-LDA的特征分解的矩阵尺寸为rr和cc，它比经典LDA的矩阵尺寸更小，这大大减少了LDA算法的时间和空间复杂度。不同于经典的LDA，2D-LDA认为l1l2维空间LR是以下两个空间的张量积：L包含uii=1l1，R包含vii=1l2。定义两个矩阵L=u1,ul1Rrl1，R=v1,vl2Rcl2。然后向量XRrc投影到空间
9、LR得到LTXRRl1l2。让AiRrc, i=1,n，在数据集中有n幅图像，分为k个类：1,k，类i中有ni幅图像。让Mi=1niXiX, 1ik表示第i类的平均值，M=1ni=1kXiX表示全局平均值。在2D-LDA方法中，我们认为图像是二维信号，目的是找到两个变换矩阵LRrl1和RRcl2 。类似于经典LDA，2D-LDA方法旨在找到两个投影变换L和R，能够让原始高维空间类的结构在低维空间得到保留。矩阵之间的相似性度量是一个自然的Frobenius范数8。在这种度量标准下，类内距离Dw和类间距离Db可以按照以下方法计算：Dw=i=1kXiX-MiF2，Db=i=1kniMi-MF2使用t
10、race属性，即traceMMT=MF2，对于任何矩阵M，我们可以得到：Dw=tracei=1kXiX-MiX-MiTDb=tracei=1kniMi-MMi-MT在线性变换L和R产生的低维空间中，类内距离和类间距离可以表示为：Dw=tracei=1kXiLTX-MiRRTX-MiTLDb=tracei=1kniLTMi-MRRTMi-MTL最优的线性变换L和R可以让Dw取最小值，Db取最大值。由于计算最优变换L和R的难度，我们推导出一个迭代算法。更具体地说，对于一个固定的R，我们可以通过求解一个优化问题来计算最优变换L。在计算变换L的同时，我们可以通过解决另一个优化问题来更新变换R。具体步骤
11、如下。线性变换L的计算：对于一个固定的变换R，Dw和Db可以改写为：Dw=traceLTSwRL, Db=traceLTSbRL算法：2D-LDAA1,An,l1,l2输入：A1,An,l1,l2输出：L,R,B1,.,Bn1 计算第i个类的平均值Mi=1niXiX;2 计算全局的平均值M=1ni=1kXiX;3 R0Il2,0T4 对于1jISwRi=1kXiX-MiRj-1Rj-1TX-MiTSbRi=1kniMi-MTRj-1Rj-1TMi-M5 计算第l1个特征向量lLl=1l1ofSwR-1SbR6 Lj1L,l1LSwLi=1kXiX-MiTLjLjTX-MiSbLi=1kniMi
12、-MTLjLjTMi-M7 计算第l2个特征向量lRl=1l2ofSwL-1SbL8 Rj1R,l2R9 循环迭代10 LLI，RRI11 BlLTAlR，l=1,.,n;12 返回L,R,B1,Bn其中SwR=i=1kXiX-MiRRTX-MiTSbR=i=1kniMi-MTRRTMi-M线性变换R的计算：接下来，计算线性变换R。对于一个固定的变换L，Dw和Db可以改写为：Dw=traceRTSwLR Db=traceRTSbLR其中SwL=i=1kXiX-MiTLLTX-MiSbL=i=1kniMi-MTLLTMi-M同样，最优的R可以通过解决下面的优化问题：maxRtraceRTSwLR
13、-1RTSbLR来求解。该解法可以通过解决一个广义特征值问题获得：SwLx=SbLx。一般来说，SbL是非奇异的，所以最优的R可以通过对SwL-1SbL作特征值分解来获得。需要注意的是矩阵SwL和SbL的大小为cc ，远要小于Sw和Sb的尺寸。Algorithm 2D-LDA.给出了2D-LDA算法的伪代码。可以很清楚的看到，算法的主要计算还是集中在Algorithm 2D-LDA的第4，6，11行，算法的时间复杂度为OnmaxI1,I2r+c2I，其中I代表的是迭代次数。2D-LDA算法依赖于最初的 的选择。我们的实验证明选择R0=Il2,0T能够获得精确的结果，其中Il2 为单位矩阵。我们
14、在整个实验中都是使用这个初始的R0。由于图像的宽和高一般是近似的，即rcN，在论文中我们将I1和I2设置为同一个值d。但是这个算法只能应用在一般的情况。通过这个简化，2D-LDA算法的时间复杂度变为OndNI。2D-LDA算法的空间复杂度为Orc=ON。该算法的低空间复杂度的关键在于SwR，SbR，SwL和SbL这4个矩阵可以通过读取矩阵Ai逐步构建。3.1 2D-LDA+LDA如引言中所介绍的，PCA常用于在LDA之前对数据进行降维以解决经典LDA的奇异性问题。在本章节中，我们将2D-LDA和LDA方法进行了结合，即2D-LDA+LDA。由于低维数据有利于LDA的处理，那么就通过2D-LDA
15、对数据进行进一步降维。具体地说，在通过2D-LDA+LDA方法的第一个阶段，将每一个图像AiRrc降维成BiRdd，其中dminr,c。在第二阶段，每一个Bi首先被转换成向量biRd2(矩阵向量对齐)，然后bi通过LDA进一步降维biLRk-1，其中k-1d2，k是类的个数。2D-LDA+LDA方法第一阶段的时间复杂度为OndNI，第二阶段的时间复杂度为Ond22。假设nd2，则总的时间复杂度为OndNI+d3。4 实验在本章节，我们对2D-LDA方法和2D-LDA+LDA方法的人脸图像识别性能进行了评估，并和广泛应用于人脸识别的PCA+LDA方法进行了比较。所有实验都是在1GB内存、1.80GHz的Linux机器上进行。对于所有实验都是使用最邻近算法计算分类精度。数据集：在实验中，我们使用了三组人脸数据集：PIX，ORL，PIE，PIX包括30个人的300幅图像，图像尺寸是512512，我们归一化到100100
