基于无穷范数的二值线性判别分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于无穷范数的二值线性判别分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 线性判别分析（LDA）是监督式的特征提取方法，在人脸识别等领域得到了广泛应用。为了提高特征提取速度，提出了基于无穷范数的线性判别分析方法。传统LDA方法将目标函数表示为类内散布矩阵和类间散布矩阵之差的或者商的L2范数，且通常需要涉及到矩阵求逆和特征值分解问题。与传统方法不同，这里所提方法将目标函数表示为类内散布矩阵和类间散布矩阵之差的无穷范数，而且最优解是以迭代形式得到，避免了耗时的特征值分解。无穷范数使得到的基向量实现了二值化，即元素仅在-1和1两个数字内取值，避免了特征提取时的浮点型点积运算，从而降低了测试时间，提高了效率。在ORL人脸数据库和Yale数据库上的实验表明所提算法是有效的。

关键词： 线性判别分析； 无穷范数； 二值化； 特征提取

中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2013）22?0024?04

0 引 言

线性判别分析（LDA）[1?3]是模式识别中降维和特征提取的一种非常流行的方法，该方法的大致思想是寻找一组投影基向量使得类间散布矩阵与类内散布矩阵的差或比率最大，该方法是基于L2范数完成的。

LDA最近几年在很多领域得到了广泛的应用，比如文献[4]将LDA用于雷达对目标的识别，文献[5]则将LDA用于脑电信号的提取和分类，得到良好的效果。虽然LDA解决了很多领域的问题，但该方法识别率仍然有待提高，于是，近年来研究人员提出了一些提高识别率的方法。比如，文献[6]对传统的LDA施加[p]范数，得到了[p]取不同值时的识别率，这对约束项的选取具有参考价值。文献[7]提出基于旋转不变的L1范数的判别标准，可以更好的描述类内的紧密度和类间的分离度。

上面提到的方法虽然都不同程度的提高了传统LDA的识别率，但却没有提高特征提取的速度。为此，本文提出利用无穷范数代替传统的L2范数对目标函数施加约束，同时采用类间散布矩阵和类内散布矩阵之差而非商作为目标函数，借鉴文献[8]的最优化过程，避免了传统方法训练中耗时的特征值分解，得到了基向量的元素仅为-1和1，即实现了基向量的二值化，将该算法命名为BLDA。这样的基向量在做特征提取时，避免了浮点型内积运算，从而降低了检测时间，提高了效率，同时BLDA拥有与传统LDA相近的识别率。最后，在Yale 和ORL人脸数据库上进行的实验，说明所提的算法是有效的。

1 现有LDA方法

LDA是一种有监督的特征提取方法，其基本思想是将有标签的高维样本[xi∈RD]通过变换矩阵[W=[w1，…，wd]∈RD×d]（其中[wi]和[xi]都是[D]维向量）映射为具有最佳可分离性的最佳子空间中的低维样本[yi∈Rd]：

其中[d

通常，变换矩阵[W]即其列向量[wi]（称为[d]维子空间的基向量）是在某一约束条件下，根据某最佳可区分准则求解得到的。下面具体介绍两种常见的准则：基于商的准则和基于差的准则。其中基于差的准则与本文所提方法最为相关。

1.1 基于商的LDA方法

本文所提方法正是在这种基于差的LDA上进行的。

2 所提BLDA

2.1 BLDA模型

注意到上述基于商和基于差的LDA方法得到的基向量[w]是任意实数，所以利用式从高维样本[x∈RD]中提取其低维特征向量[y∈Rd]时，需要计算该高维样本[x∈RD]和高维基向量[w∈RD]的浮点数内积[y=]。该内积的计算量较大，耗时较多。

本文所用算法得到的基向量中元素为-1或1，在进行上述内积时，只需找到基向量[w]中-1和1对应的测试数据[x]中的元素，然后相加即可得到降维后的样本[y]。而传统的LDA则是对[w]和[x]直接相乘，需要基向量[w]的每个元素与测试数据[x]对应位置的元素先分别进行乘法再将这些乘积相加，而浮点型数值乘法相对麻烦，所以本文所提算法可以大大降低测试时间，提高检测效率，下面具体讲解本文所提的算法。

于是，式（11）取最大值当且仅当[wi=?signwi]，其中[wi]表示向量[w]第[i]个元素。注意到最优解必须满足[wpp=1]，[p=∞]，因此，第[k+1]次迭代的最优值为[wk+1=wwp]。其中[p=∞]，这样就得到了式（10）的最优解。容易发现，这样得到的基向量[w]只含-1和1两个值。该算法在实现过程中需要先初始化[w]，对此本文采用随机得到，但同样必须满足[w0pp=1]。

3 实验结果

本文分别在ORL人脸数据库和Yale人脸数据库上对所提的BLDA进行验证，观察该算法与传统LDA不同基向量数目时的识别率。同时，由于本文的算法实现了基向量的二值化（-1，1），测试时只用进行加法操作而避免了浮点型数值的乘法操作，大大降低了测试时间，提高了效率，本实验将在ORL人脸数据库和Yale数据库比较两种方法的测试时间。

3.1 ORL人脸数据库

为了计算的简便，本实验将每张图像的大小缩小至56×46，随机选择每个人5张人脸图像作为训练数据，另外5张作为测试数据，这样测试数据和测试数据均为200张。图 1显示所提BLDA算法与传统LDA的识别率和基向量数之间的关系。

从图 1看到，本文所提的BLDA与传统的LDA识别率相近，当基向量数目逐渐增加时，前者的识别率在某些点甚至比后者高。

当取不同数量的基向量时，测试时的计算量也不同，传统的方法是基向量矩阵和测试数据矩阵直接相乘，例如，当取20个基向量时，测试时是一个20×2 576的矩阵和一个2 576×200的矩阵相乘，一共需要20×200×（2 576+2 575）=20 604 000次计算；当取50个基向量时，一共需要51 510 000次计算；当取[n]个基向量，需要1 030 200[n]次计算。而本文的BLDA算法由于基向量中元素仅为-1和1两个数值，所以不用进行乘法运算，计算量就会减少大约 [12]，例如，对于20个基向量，运算量为20×200×2 575=10 300 000；当取[n]个基向量，运算量为515 000[n]。表1显示了ORL人脸数据库下两种算法不同基向量的运算量。

从表 1看出，本文所提的BLDA比传统的LDA少大约一半的计算量，这将使得前者的测试时间比后者大约少一半，表 2显示两种算法的测试时间。

3.2 Yale人脸数据库

与ORL人脸数据库相同，随机选取每个人5张图像作为训练数据，另外5张作为测试数据，由于该数据库有15个人，所以训练数据和测试数据均为75张。表3和图2显示了两种算法在Yale人脸数据库下不同基向量数的识别率和测试时间。

从图 2可以看出，在Yale人脸数据库上所提算法仍然和传统的LDA识别率相近，当基向量数目增加到一定时，两种算法的识别率曲线基本重合。与ORL数据库上的结果对比，Yale数据库上有更好的识别效果，这是因为Yale数据库的人脸样本比ORL数据库少，当取相同数目的基向量做测试时，前者识别率高于后者。表3显示在Yale数据库上，所提算法测试时间仍然大约是传统的LDA的[12]。

综合以上两个在不同数据库上的实验，说明BLDA在保持识别率和传统LDA识别率相近的情况下，实现了基向量的二值化，避免了浮点数值的乘法运算，从而减少了大约[12]的测试时间，提高了测试效率。

4 结 语

本文采用基于差的LDA，对目标函数中施加无穷范数约束项，在最优化过程中利用逐次线性化技术和Holder不等式定理，得到了二值化（-1，1）的基向量，在识别率与传统LDA相近的情况下降低了运算量，减少了检测时间。

参考文献

[1] BELHUMEUR P N， HESPANHA J P， KRIEGMAN D. Eigenfaces vs. fisherfaces： recognition using class specific linear projection [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1997， 19（7）： 711?720.

[2] MARTINEZ A， KAK A. PCA versus LDA [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1997， 19（7）： 711?720.

[3] LI H F， JANG T， ZHANG K S. Efficient and robust feature extraction by maximum margin criterion [J]. IEEE Transactions on Neural Networks， 2006， 17（1）： 157?165.

[4] 吴秋荣，杨万麟.基于NMFs?LDA的雷达目标距离像识别[J].现代电子技术，2007，30（19）：63?65.

[5] 刘纪红，丁俊杰，边洪亮.一种基于FPGA的脑电分类算法实现[J].现代电子技术，2012，35（20）：107?110.

[6] JAE H O， NOJUN K. Generalization of linear discriminant analysis using Lp?norm [J]. Pattern Recognition Letters， 2013， 34（6）： 679?685.

[7] LI X， HU W， WANG H， et al. Linear discriminant analysis using rotational invariant L1 norm [J]. Neurocomputing， 2010， 73（13/15）： 2571?2579.

[8] LIANG Z Z， XIA S X， YONG Z， et al. Feature extraction based on Lp?norm generalized principal component analysis [J]. Pattern Recognition Letters， 2013， 34（9）： 1037?1045.

[9] JOURNEE M， NESTEROV Y， RICHTARIK P， et al. Gene?

ralized power method for sparse principal component analysis [J]. Journal of Machine Learning Research， 2010， 11： 517?553.

[10] YANG W H. On generalized holder inequality [J]. Nonlinear Analysis， 1991， 16（5）： 489?498.