二维线性判别分析
摘要
线性判别分析（LDA ）是一个常用的进行特征提取和降维的方法。在许多涉及到高维数据，如人脸识别和图像检索的应用中被广泛使用。经典的LDA 方法固有的限制就是所谓的奇异性问题，即当所有的散列矩阵是奇异的时，它就不再适用了。比较有名的解决奇异性问题的方法是在使用LDA 方法之前先用主成分分析（PCA ）对数据进行降维。这个方法就叫做PCA+LDA，在人脸识别领域被广泛应用。然而，由于涉及到散列矩阵的特征值分解，这个方法在时间和空间上都需要很高的成本。
在本文中，我们提出了一种新的LDA 算法，叫做2D-LDA ，即二维线性判别分析方法。2D-LDA 方法彻底解决了奇异性问题，并且具有很高的效率。2D-LDA 和经典LDA 之间主要的区别在于数据表示模型。经典LDA 采用矢量表示数据，而2D-LDA 使用矩阵表示数据。我们对2D-LDA+LDA，即如何结合2D-LDA 和经典LDA ，在经典LDA 之前使用2D-LDA 进一步降维的问题进行了研究。将本文提出的算法应用于人脸识别，并与PCA+LDA进行了比较。实验表明：2D-LDA+LDA的方法识别更精确，并且效率更高。
1概述
线性判别分析[2][4]是一个著名的特征提取和降维的方法。已经被广泛应用于人脸识别[1]、图像检索[6]、微列阵数据分类[3]等应用中。经典的LDA 算法就是将数据投影到低维的向量空间，使类间距离和类内距离的比值最大化，从而得到最佳的分类效果。最佳的投影方向可以通过散列矩阵的特征值分解计算得到。经典LDA 算法的一个限制是其目标函数的散列矩阵必须是奇异的。对于许多应用了，如人脸识别，所有散列矩阵的问题都可以是奇异的，因为其数据都是高维的，并且通常矩阵的尺寸超过了数据点的额数目。这就是所谓的“欠采样或奇异性问题
[5]”。
近年来，许多用于解决这种高维、欠采样问题的方法被提出，包括伪逆LDA 、PCA+LDA和正则LDA 。在文献[5]中可以了解更多细节。在这些LDA 的扩展方法中，PCA+LDA受到了广泛的关注，尤其实在人脸识别领域[1]。这个方法包括两个阶段，其中一个阶段就是在LDA 方法之前使用PCA 对数据进行降维。以前
的LDA 扩展一般是大型矩阵的特征值分解计算，这不仅降低了效率，也使得它很难扩展到大型数据集。
在本文中，我们提出了一种新的方法来解决此前的LDA 扩展的特征分解计算的问题。新颖之处在于它采用了不同的数据表示模型。在这种模式下，每个数据被表示为一个矩阵，而不是一个向量，并且数据集被表示为矩阵的集合，而不是一个单一的大矩阵。这种模式在文献[7][8][9]中被用于对SVD 和PCA 的泛化。不同于经典的LDA ，我们考虑的是数据在二维空间中的投影。在第3节中，我们将降维问题规划为一个优化问题。不同于经典的LDA ，没有已有的解决优化问题的方法，于是，我们探索得到了一个新的方法，即2D-LDA 。为了更进一步降低数据的维数，我们将2D-LDA 和LDA 进行了结合，即2D-LDA+LDA。
我们在三个著名的人脸数据集上对2D-LDA 、2D-LDA+LDA方法进行了测试，和目前被广泛应用于人脸识别的PCA+LDA方法进行了比较。
实验结果表明：
1、2D-LDA 方法适用于高维采样数据，如人脸图像，并且不用考虑经典LDA 方法的奇异性问题。
2、2D-LDA 和2D-LDA+LDA相较于PCA+LDA方法在时间和空间上的消耗明显降低，而识别精度相差不多。
2LDA 概述
在这个部分，我们对经典的LDA 方法进行了简单的介绍。
给定一个数据矩阵A∈RN×n，经典的LDA 旨在找到一个变换G∈RN×ℓ，对于A 的每一列ai，在N 维空间中对应在L 维空间的向量bi。即：
G:ai∈RN→bi=GTai∈Rℓ(ℓ
同样的，经典LDA 方法旨在找到一个向量空间G包含 gi ℓi=1，其中G= g1, g2, …. , gℓ ，这样，每一个ai通过 g1T∙ai, …, gℓT∙ai T∈Rℓ投射到向量空间G中。
假定初始数据被分为k 个类A= ∏1, …, ∏k ，其中∏i包含了第i 类的ni个数据点，并且 ki=1ni=n。经典LDA 旨在找到这样的最佳转换G 使得原始高维类的结构保存在低维空间中。
一般来说，如果每个类都是紧密分组，但能够很好的与其他类分离开来，那么称这个为高质量集群。在判别分析中，定义两个矩阵来衡量集群质量：
类内散列度矩阵Sw：
TSw= ki=1 x∈∏i x−mi x−mi
类间散列度矩阵Sb：
Sb=
其中 ki=1ni m1−m2 m1−m2 T
1mi= x ix∈∏i
表示第i 类的中心点，
表示全局中心点。 k1m = x i=1x∈∏i
通过Sw和Sb可以很容易的计算出类内向量距离和类间距离。在线性变换G 产生的低维空间（或线性投影向量空间G ）中，类内距离矩阵和类间距离矩阵是：
LLSb=GTSbG，Sw=GTSwG.
LL一个最佳变换G 能够最大化Sb，最小化Sw。线性判别中常见的优化方法包
括（见[4]）：
L−1LL −1L Sw max G trace S2Sb and min G trace Sb (1)
等价于下面的广义特征值问题：
Sbx=λSwx，λ≠0
如果Sb是非奇异的，则有k-1个对应的特征矩阵向量的非零特征值。因此，经典的LDA 算法最多降维k-1。一个稳定的计算特征值分解的方法是应用SVD 的散射矩阵，可在文献[6]了解细节。
3二维线性判别分析
本文提出的2D-LDA 和经典LDA 最大的不同在于数据的表示模型。经典的LDA 使用矢量表示数据，2D-LDA 使用矩阵表示数据。在本节我们将看到，2D-LDA 的数据矩阵表示模型导致了更小尺寸的矩阵的特征分解。更具体地说，2D-LDA 的特征分解的矩阵尺寸为r×r和c×c，它比经典LDA 的矩阵尺寸更小，这大大减少了LDA 算法的时间和空间复杂度。
不同于经典的LDA ，2D-LDA 认为 ℓ1×ℓ2 维空间ℒ⨂ℛ是以下两个空间的张量积：
12ℒ包含 ui i=1，ℛ包含 vi i=1。定义两个矩阵ℒ= u1, …, uℓ1 ∈Rr×ℓ1，ℓℓ
ℛ= v1, …, vℓ2 ∈Rc×ℓ2。然后向量X ∈Rr×c投影到空间ℒ⨂ℛ得到ℒTXℛ∈Rℓ1×ℓ2。 让Ai∈Rr×c, i=1, …, n，在数据集中有n 幅图像，分为k 个类：∏1, …, ∏k，类∏i中有ni幅图像。让Mi=n X∈∏iX, 1≤i≤k表示第i 类的平均值，M=i1
1n k在2D-LDA 方法中，我们认为图像是二维信号，i=1 X∈∏iX表示全局平均值。
目的是找到两个变换矩阵ℒ∈Rr×ℓ1和ℛ∈Rc×ℓ2。
类似于经典LDA ，2D-LDA 方法旨在找到两个投影变换L 和R ，能够让原始
高维空间类的结构在低维空间得到保留。
矩阵之间的相似性度量是一个自然的Frobenius 范数[8]。在这种度量标准下，
类内距离Dw和类间距离Db可以按照以下方法计算：
Dw= ki=1 X∈∏i X−Mi F，
2
k2Db= ki=1ni Mi−M F 2使用trace 属性，即trace MMT = M F，对于任何矩阵M ，我们可以得到：
Dw=trace X−Mi X−Mi T
i=1X∈∏i
k
i=1Db=trace ni Mi−M Mi−M T
在线性变换L 和R 产生的低维空间中，类内距离和类间距离可以表示为：
k
w=trace LT X−Mi RRT X−Mi TL D
i=1X∈∏i
b=trace Dk
i=1niLT Mi−M RRT Mi−M TL
w取最小值，D b取最大值。由于计算最优变最优的线性变换L 和R 可以让D
换L 和R 的难度，我们推导出一个迭代算法。更具体地说，对于一个固定的R ，我们可以通过求解一个优化问题来计算最优变换L 。在计算变换L 的同时，我们可以通过解决另一个优化问题来更新变换R 。具体步骤如下。
线性变换L 的计算：
w和D b可以改写为： 对于一个固定的变换R ，D
R R w=trace LTSwDL, Db=trace LTSbL
算法：2D-LDA A1, …, An, ℓ1, ℓ2
输入：A1, …, An, ℓ1, ℓ2
输出：L, R, B1, …. , Bn
1．
2．
3．
4． 计算第i 个类的平均值Mi=n X∈∏iX; 计算全局的平均值M =R0← Iℓ2, 0
对于1≤j≤I
RSwki=1
k
i=1T1 k ni=1X∈∏i1iX; ← X∈∏iT X−Mi Rj−1RjT−1 X−Mi RSb← ni Mi−M TRj−1RjT−1 Mi−M
ℓ5．
6． 1R−1R计算第ℓ1个特征向量 ∅Lℓ ℓ=1of Sw Sb LLj← ∅1, …, ∅Lℓ1
LSw←
LSbki=1k X∈∏iT X−Mi TLjLj X−Mi ← i=1T Mi−M ni Mi−M TLjLj
ℓ7．
8．
9． 2L−1L计算第ℓ2个特征向量 ∅Rℓ ℓ=1of Sw Sb RRj← ∅1, …, ∅Rℓ2
循环迭代
10． L←LI，R←RI
11． Bℓ←LTAℓR，ℓ=1,.. , n;
12． 返回 L, R, B1, …, Bn
其中
RSwki=1= X∈∏i X−Mi RRT X−Mi T
RSb= k
i=1ni Mi−M TRRT Mi−M
线性变换R 的计算：
w和D b可以改写为： 接下来，计算线性变换R 。对于一个固定的变换L ，D
L w=trace RTSwDR
L b=trace RTSbDR
其中
k
LSw= X−Mi TLLT X−Mi
i=1X∈∏i
k
LSb= ni Mi−M TLLT Mi−M
i=1
同样，最优的R 可以通过解决下面的优化问题：
L −1 TL max trace RTSwRRSbR R
LL来求解。该解法可以通过解决一个广义特征值问题获得：Swx=λSbx。一般来
LL −1L说，Sb是非奇异的，所以最优的R 可以通过对 SwSb作特征值分解来获得。需
LL要注意的是矩阵Sw和Sb的大小为c×c，远要小于Sw和Sb的尺寸。
Algorithm 2D-LDA . 给出了2D-LDA 算法的伪代码。可以很清楚的看到，算法的主要计算还是集中在Algorithm 2D-LDA的第4，6，11行，算法的时间复杂度为O nmax I1, I2 r+c 2I ，其中I 代表的是迭代次数。2D-LDA 算法依赖于最初的的选择。我们的实验证明选择R0= Iℓ2, 0 能够获得精确的结果，其中Iℓ2为单位矩阵。我们在整个实验中都是使用这个初始的R0。
由于图像的宽和高一般是近似的，即r≈c≈ ，在论文中我们将I1和I2设置为同一个值d 。但是这个算法只能应用在一般的情况。通过这个简化，2D-LDA 算法的时间复杂度变为O ndNI 。
2D-LDA 算法的空间复杂度为O rc =O N 。该算法的低空间复杂度的关键
RLRL在于Sw，Sb，Sw和Sb这4个矩阵可以通过读取矩阵Ai逐步构建。 T
3.1 2D-LDA+LDA
如引言中所介绍的，PCA 常用于在LDA 之前对数据进行降维以解决经典LDA 的奇异性问题。在本章节中，我们将2D-LDA 和LDA 方法进行了结合，即2D-LDA+LDA。由于低维数据有利于LDA 的处理，那么就通过2D-LDA 对数据进行进一步降维。具体地说，在通过2D-LDA+LDA方法的第一个阶段，将每一个图像Ai∈Rr×c降维成Bi∈Rd×d，其中d
k−1先被转换成向量bi∈Rd(矩阵向量对齐) ，然后bi通过LDA 进一步降维b L，i∈R2
其中k−1
2D-LDA+LDA方法第一阶段的时间复杂度为O ndNI ，第二阶段的时间复杂度为O n d2 2 。假设n
4实验
在本章节，我们对2D-LDA 方法和2D-LDA+LDA方法的人脸图像识别性能进行了评估，并和广泛应用于人脸识别的PCA+LDA方法进行了比较。所有实验都是在1GB 内存、1.80GHz 的Linux 机器上进行。对于所有实验都是使用最邻近算法计算分类精度。
数据集：在实验中，我们使用了三组人脸数据集：PIX ，ORL ，PIE ，PIX 包括30个人的300幅图像，图像尺寸是512×512，我们归一化到100×100。ORL 包括40个人的400幅图像，图像尺寸是92×112。PIE 是CMU —PIE 人脸图像集的子集，包括63个人的6615幅图像，图像尺寸是640×480，统一到220×175。
图1 迭代次数对结果的影响(从左至右:PIX,Orl,PIE)
实验1. 研究迭代次数I 对结果的影响
在该实验中，我们研究了2D-LDA 方法中迭代次数对于算法的影响。结果如图1所示，X 轴表示迭代次数，Y 轴表示分类精度。在算法中，我们通常取d=10。很显然，对于迭代次数的变换，两个方法的分类精度曲线都是稳定的，不随迭代次数变化而变化。一般情况下，2D-LDA+LDA方法的精度曲线比2D-LDA 更加稳定。因此，我们只需要在2D-LDA 算法中进行一次循环，即取I=1，两个算法的运行时间明显减少。
实验2. 研究降维度d 对于结果的影响
在本次实验中，我们研究了2D-LDA 方法的变换空间中降维度数对于2D-LDA 和2D-LDA+LDA算法的影响。我们做了大量的实验，对人脸数据集采用不同的降维度数d 进行实验。结果如图2所示，X 轴代表降维度数d （1到15），Y 轴代表使用最邻近方法进行分类的分类精度。如图中所示，所有数据集的分类精度曲线都稳定在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算法的时间和空间复杂度明显更低。
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方法相差无几，而且时间和空间复杂度更低。
图2降维度数对结果的影响(从左至右:PIX,ORL,PIE)
表1几种算法分类精度和效率比较
参考文献
[1] P.N. Belhumeour, J.P. Hespanha, and D.J. Kriegman. Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):711–720, 1997.
[2] R.O. Duda, P.E. Hart, and D. Stork. Pattern Classification. Wiley, 2000.
[3] S. Dudoit, J. Fridlyand, and T. P. Speed. Comparison of discrimination methods for the classification of tumors using gene expression data. Journal of the American Statistical Association, 97(457):77–87, 2002.
[4] K. Fukunaga. Introduction to Statistical Pattern Classification. Academic Press, San Diego, California, USA, 1990.
[5] W.J. Krzanowski, P. Jonathan, W.V McCarthy, and M.R. Thomas. Discriminant analysis with singular covariance matrices: methods and applications to spectroscopic data. Applied Statistics, 44:101–115, 1995.
[6] Daniel L. Swets and Juyang Weng. Using discriminant eigenfeatures for image retrieval. IEEETransactions on Pattern Analysis and Machine Intelligence, 18(8):831–836, 1996.
[7] J. Yang, D. Zhang, A.F. Frangi, and J.Y . Yang. Two-dimensional PCA: a new approach to appearance-based face representation and recognition. IEEE Transactions on Pattern Analysisand Machine Intelligence, 26(1):131–137, 2004.
[8] J. Ye. Generalized low rank approximations of matrices. In ICML Conference Proceedings, pages 887–894, 2004.
[9] J. Ye, R. Janardan, and Q. Li. GPCA: An efficient dimension reduction scheme for image compression and retrieval. In ACM SIGKDD Conference Proceedings, pages 354–363, 2004.