《二维线性判别分析》由会员分享，可在线阅读，更多相关《二维线性判别分析（11页珍藏版）》请在金锄头文库上搜索。
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。在文献中可以了解更多细节。在这些LDA的扩展方法中，PCA+LDA受到了广泛的关注，尤其实在人脸识别领域1。这个方法包括两个阶段，其中一个阶段就是在LDA方法之前使用PCA对数据进行降维。以前的LDA扩展一般是大型矩阵的特征值分解计算，
4、这不仅降低了效率，也使得它很难扩展到大型数据集。在本文中，我们提出了一种新的方法来解决此前的LDA扩展的特征分解计算的问题。新颖之处在于它采用了不同的数据表示模型。在这种模式下，每个数据被表示为一个矩阵，而不是一个向量，并且数据集被表示为矩阵的集合，而不是一个单一的大矩阵。这种模式在文献789中被用于对SVD和PCA的泛化。不同于经典的LDA，我们考虑的是数据在二维空间中的投影。在第3节中，我们将降维问题规划为一个优化问题。不同于经典的LDA，没有已有的解决优化问题的方法，于是，我们探索得到了一个新的方法，即2D-LDA。为了更进一步降低数据的维数，我们将2D-LDA和LDA进行了结合，即2D
5、-LDA+LDA。我们在三个著名的人脸数据集上对2D-LDA、2D-LDA+LDA方法进行了测试，和目前被广泛应用于人脸识别的PCA+LDA方法进行了比较。实验结果表明：1、2D-LDA方法适用于高维采样数据，如人脸图像，并且不用考虑经典LDA方法的奇异性问题。2、2D-LDA和2D-LDA+LDA相较于PCA+LDA方法在时间和空间上的消耗明显降低，而识别精度相差不多。2LDA概述在这个部分，我们对经典的LDA方法进行了简单的介绍。给定一个数据矩阵？?厂?，经典的LDA旨在找到一个变换？?7?x?，对于A的每一列?，?在N维空间中对应在L维空间的向量?。?即：?/f?=?賀？?同样的，经典L
6、DA方法旨在找到一个向量空间?包含?=?1，其中?=?,?,.,?,这样，每一个？?通过?,？?？?投射到向量空间?中。假定初始数据被分为k个类？?=ni,n?，其中n?包含了第i类的？?个数据点，并且?=?1?=?。经典LDA旨在找到这样的最佳转换G使得原始高维类的结构保存在低维空间中。一般来说，如果每个类都是紧密分组，但能够很好的与其他类分离开来，那么称这个为高质量集群。在判别分析中，定义两个矩阵来衡量集群质量：类内散列度矩阵?：类间散列度矩阵？?:其中?=?-?2?1?-?2?=1初？?表示第i类的中心点,1m=?=1?表示全局中心点。通过？?和？?可以很容易的计算出类内向量距离和类间距
7、离。在线性变换G产生的低维空间（或线性投影向量空间G）中，类内距离矩阵和类间距离矩阵是：?=?p?=?一个最佳变换G能够最大化？，最小化？誤线性判别中常见的优化方法包括（见4）:(1)max?1?andmin?1?等价于下面的广义特征值问题:?=?入工0如果?是非奇异的，则有k-1个对应的特征矩阵向量的非零特征值。因此，经典的LDA算法最多降维k-1。一个稳定的计算特征值分解的方法是应用SVD的散射矩阵，可在文献了解细节。3二维线性判别分析本文提出的2D-LDA和经典LDA最大的不同在于数据的表示模型。经典的LDA使用矢量表示数据，2D-LDA使用矩阵表示数据。在本节我们将看到，2D-LDA的
8、数据矩阵表示模型导致了更小尺寸的矩阵的特征分解。更具体地说，2D-LDA的特征分解的矩阵尺寸为？?和？泯？?它比经典LDA的矩阵尺寸更小,这大大减少了LDA算法的时间和空间复杂度。不同于经典的LDA，2D-LDA认为?1X?2维空间?是以下两个空间的张量积：2?=莒?孙?使用trace属性，即？?？?？=?2?，对于任何矩阵M，我们可以得到:?包含?1,?包含?|1。定义两个矩阵？=?,?伙?1,?,?伙?2。然后向量X?投影到空间?得到？?欣？?1X?2让？?色1,?在数据集中有n幅图像，分为k个类：叮，,n?,类n?中1有？?幅图像。让?亍玉?En?1?宾？?表示第i类的平均值，？=?-1
9、?爲?E?表示全局平均值。在2D-LDA方法中，我们认为图像是二维信号,目的是找到两个变换矩阵？E?1和？?7x?2。类似于经典LDA,2D-LDA方法旨在找到两个投影变换L和R,能够让原始高维空间类的结构在低维空间得到保留。矩阵之间的相似性度量是一个自然的Frobenius范数。在这种度量标准下，类内距离？?和类间距离？?可以按照以下方法计算：?2?=?1?en?-?，?3?=?-?-?1?尿?=?-?7?1在线性变换L和R产生的低维空间中，类内距离和类间距离可以表示为:?=?-?1?E!?=?孑?1最优的线性变换L和R可以让？?取最小值，？?取最大值。由于计算最优变换L和R的难度，我们推导
10、出一个迭代算法。更具体地说，对于一个固定的R，我们可以通过求解一个优化问题来计算最优变换Lo在计算变换L的同时，我们可以通过解决另一个优化问题来更新变换R。具体步骤如下。线性变换L的计算：对于一个固定的变换R，?和?可以改写为：?=?2?=?算法：2D-LDA?,？?,？1,?2输入：？,？勿？1,?2输出：?,.,?1.计算第i个类的平均值?=预？?厨?？2.计算全局的平均值M:=?1?en?3.?-?2,04.对于17?%?加?17.计算第?2个特征向量?2-?=1?-1?8.?-?,?9.循环迭代10.?k?-?11.?=1?，尸12.返回?,?其中?=?-?,?.?2?i?捷?=?7?
11、.?=1线性变换R的计算：接下来，计算线性变换R。对于一个固定的变换L,?和?可以改写为:?2?=?侯？?其中?=?-?-?=?7?7?=1同样，最优的R可以通过解决下面的优化问题：m?-1?来求解。该解法可以通过解决一个广义特征值问题获得：?=?象？一般来说，？?是非奇异的，所以最优的R可以通过对？?？-1?作特征值分解来获得。需要注意的是矩阵？?和？?的大小为cxc远要小于？?和？?的尺寸。Algorithm2D-LDA.给出了2D-LDA算法的伪代码。可以很清楚的看到，算法的主要计算还是集中在Algorithm2D-LDA的第4,6,11行，算法的时间复杂度为?max?h?2?,其中I代
12、表的是迭代次数。2D-LDA算法依赖于?最初的的选择。我们的实验证明选择？=?,0能够获得精确的结果，其中？?为单位矩阵。我们在整个实验中都是使用这个初始的？0由于图像的宽和高一般是近似的，即2?-?,在论文中我们将？?和？设置为同一个值d。但是这个算法只能应用在一般的情况。通过这个简化，2D-LDA算法的时间复杂度变为?2D-LDA算法的空间复杂度为？?=?。该算法的低空间复杂度的关键在于?f,?臥？和？?这4个矩阵可以通过读取矩阵？?逐步构建。3.12D丄DA+LDA如引言中所介绍的，PCA常用于在LDA之前对数据进行降维以解决经典LDA的奇异性问题。在本章节中，我们将2D-LDA和LDA方法进行了结合，即2D-LDA+LDA。由于低维数据有利于LDA的处理，那么就通过2D-LDA对数据进行进一步降维。具体地说，在通过2D-LDA+LDA方法的第一个阶段，将每一个图像？?x?降维成？?,其中？?o在第二阶段，每一个？?首先被转换成向量？?
