局部线性嵌入算法

局部线性嵌入算法（精选三篇）

局部线性嵌入算法 篇1

关键词：监督分类,局部线性重构,重构误差,降维

0引言

K近邻分类器[1]是由Cover和Hart提出的,它是根据K个最近邻居的投票来决定某个样本的标签的。这种分类算法虽然设计简单,但有着广泛的应用背景,且准确性较高。然而,在K近邻分类器中,长期存在着一个未解决好的问题,即“平局问题”。它指的是投票出现均衡时,无法决定测试样本的标签的问题。通常的做法是当出现平局时随机决定,然而这种方式在设计上不够精细。另外,对于两类问题,可以将K取成奇数值来避免平局问题,但是对于多类问题,这种方法是行不通的。当然,在经典的K近邻分类器基础上,研究者已经做了大量的改进工作[2,3,4,5,6,7],这些工作从不同角度提升了近邻分类算法的性能。

近年来,随着基于流形的机器学习算法崛起,Kang和Cho提出了一种基于非负局部线性重构的分类算法[7],它可以理解为运用K邻域的重构系数来实施投票,也就是投票数可以不是整数,这就很好地解决了平局问题,同时还得到了总体上更好的分类性能。然而,值得强调的是,KangCho算法限制重构稀疏为非负,给问题的求解带来了更大的时间代价,并且在部分数据集上的分类性能有所退化。

针对上述问题,本文对基于KangCho算法的分类器进行两个方面的调整:(1) 运用重构误差来决定分类;理论上来讲,利用重构误差的大小来决定分类更加自然。(2) 去除非负约束,相当于允许投票数为负,这样可以减小算法的计算开销。本文用一组公开数据对改进的算法进行了测试,得到了比K近邻分类器和KangCho算法更好的效果。

1基本概念与相关工作

1.1监督分类

监督分类是指在训练样本的指导下,对测试样本进行分类的算法,它运用的是训练集和测试样本之间的关系,这一点是与半监督分类算法相区别的,因为半监督分类算法除了运用训练集和测试样本之间的关系,还会运用测试集的分布或者流形结构。这里的训练样本指的是类标签已知的样本,而测试样本指的是待分类的样本,它们通常被表达成d维的向量数据。向量与向量之间的近邻关系可以用一个距离函数来度量,对于不同的应用背景,这个度量标准通常有所不同。本文探讨的方法属于监督分类算法。

1.2局部线性重构

文献[9]提出的局部线性嵌入(LLE)是一种基于流形的维数约简算法,从几何的意义上来讲,高维空间中邻近的数据点在降维之后依然保持邻近。局部线性重构(LLR)是LLE的最基本的一个步骤,它被用来建立高维空间中的数据点之间近邻关系和流形结构。下面介绍LLR的数学表达及相关特性。

令X ={xi}${}_{i=1}^n$表示由一组列向量组成的矩阵,其中,xi∈Rd表示位于矩阵X的第i列的实向量。令wj表示数据点j对点i的重构系数,则局部线性重构可以表达为求解如下的最优化问题:

$\begin{array}{l}w{}^{*}=\arg \min {}_w\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2(1)\\ \text{s}.\text{t}.\\ {\displaystyle \sum _{j}w}{}_j=1\end{array}$

式中:

$\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2=e(w)$ (2)

称作重构误差。所谓重构,这里指的是用一组线性无关的向量的线性组合来近似地表达一个给定的向量。在上述表达中,这个线性组合无疑就是${\displaystyle \sum _{j}w}{}_{j}x{}_j$,而被重构的向量即xi。这样,重构误差可以认为是重构项与被重构向量之间的欧氏距离。另外,这里的局部指的是参与重构的向量xj应当是来自xi的某个邻域,例如一定半径内的数据点或者K个最近的数据点。本文采用的是后者,即K近邻邻域的方式,它的使用范围较为广泛。

1.3相关工作

与本文的方法紧密相关的工作主要有两个:其一是经典的K近邻分类算法,其二是Kang和Cho提出的基于非负局部线性重构的分类算法。

K近邻分类器是根据多数原则投票的一种算法。为了直观,举一个简单例子来阐明其工作原理,如图1所示的两类问题,圈和方块分别代表类1和类2,点p是测试样本。若令K=4,则来自类1的投票数为3,来自方块的投票数为1,因此样本点p应该归入类1。

然而,如果来自各类的投票数出现相等的情况,就难以正确决定测试样本的类别了。数学上造成这种情况的直接原因是投票数为整数。从统计学的角度而言,若投票为实数,则出现平局的概率相当小。因此,更精细的方法应当用实数来投票。

Kang和Cho提出了基于非负局部线性重构的分类算法,其实质就是利用正实数来投票的,可以表示为求解如下优化问题:

$\begin{array}{l}w{}^{*}=\arg \min {}_w\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2(3)\\ \text{s}.\text{t}.\\ {\displaystyle \sum _{j}w}{}_j=1w{}_j\ge 0\end{array}$

式中,xi看成是测试样本,而xj是来自训练数据集,求解该优化问题得出的wj即可以理解为点xj对xi的投票数。设类别数为c,令L是一个K行c列的矩阵,若邻居点i属于第h类,则Lih=1,否则Lih=0。则测试样本的标签为:

h*=arg maxwTL·h (4)

式中,L·h表示L的第h列。

2本文算法

下面首先描述提出的分类算法,然后详细分析算法的细节并给出其计算复杂性,以及与相关工作之间的比较。

2.1局部线性重构分类算法

令y(·)表示一个函数,它可以返回一个训练样本的标签。令δl(wj) 返回一个标量值,即:

本文算法如下:

算法1 局部线性重构分类算法(LLRC)

输入:训练样本和测试样本集以及参数K

步骤1 将所有样本按维度归一化为方差1。

步骤2 对于测试样本xi,找到它的K个最近的邻居K-NN(xi)。

步骤3 根据下式计算重构系数向量w:

$\begin{array}{l}w{}^{*}=\arg \min {}_w\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2(6)\\ \text{s}.\text{t}.\\ {\displaystyle \sum _{j}w}{}_j=1\end{array}$

其中xj∈K-NN(xi)。

步骤4 计算每一类的重构误差:

$e{}_l=\left|x{}_i-{\displaystyle \sum _j\delta }{}_l(x{}_{ij})x{}_j\right|{}_2$ (7)

其中,l=1,2,…,c。

步骤5 将xi的标签输出为:

l*=arg minl(el) (8)

步骤6 取下一个样本,返回步骤3。

上述算法中,步骤4计算每一类对于xi的重构误差,它意味着重构误差最小的类的标签应该估计为测试样本的标签。

2.2算法分析

下面将从理论上分析本文算法和Kangcho算法的计算代价和几何意义。

就计算代价方面而言,式(1)所示的局部线性重构问题等价于求解一个小的线性方程,而式(3)所示的非负局部线性重构问题,等价于在满足非负约束的前提下,求解一个非线性方程。求解非线性方程通常要付出更多的计算代价。

快速求解式(1)的方法可以借助线性代数的基本知识完成。首先,由于重构系数和为1,于是可得:

$\begin{array}{l}e{}^2(w)=\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2^2=\left|{\displaystyle \sum _{j}w}{}_j(x{}_i-x{}_j)\right|{}_2^2\\ ={\displaystyle \sum _{jk}w}{}_{j}w{}_{k}G{}_{jk}(9)\end{array}$

式中, Gjk表示的是局部格拉姆矩阵,即:

Gjk=(xi-xj)·(xi-xk)T (10)

于是,最优重构系数可以根据下式计算:

$w{}_j=\frac{{\displaystyle \sum _{k}G}{}_{jk}^{-1}}{{\displaystyle \sum _{uv}G}{}_{uv}^{-1}}$ (11)

这里的G-1为格拉姆矩阵的逆。另外,还有一种更快的解决方法,即解如下的线性方程:

${\displaystyle \sum _{k}G}{}_{jk}w{}_k=1$ (12)

然后将得到的重构系数归一化处理。这种解法的时间复杂性是O(dK3),其中,d表示数据的维度,K通常较小,因此这种解法的时间消耗较小。

下面分析加入非负约束的式(3)的求解方法,阐明非负约束导致问题变成了解非线性方程。令A表示距离x最近的k个向量所组成的矩阵,式(3)的优化目标部分便可重写为如下形式:

$f(w)=\left|x{}_i-{\displaystyle \sum _{j}w}{}_{j}x{}_j\right|{}_2^2=\left|x-Aw\right|{}_2^2$ (13)

问题式(3)重写为:

minf(w) (14)

s.t.

1Tw=1 w≥0

求解问题式(14)需要运用局部解的必要条件(KKT条件),当然由于该问题是凸优化,因此局部解也就是全局解。其KKT条件如下:

1Tw=1 w≥0 (15)

ᐁf(w)≥0 (16)

ᐁf(w)Tw=0 (17)

因此,问题式(3)转换为求解一个非负的向量w的形式,即联立求解式(15)的归一化条件和式(17)的非线性方程。由于求解非线性方程需要运用数值优化方法,如梯度下降法或内点法等,其时间耗费较大。具体的计算代价在实验部分给出对比。

另外,还有必要解释去留非负约束对几何意义有什么影响。本文算法中去掉了非负约束,采用式(1)来计算重构系数,它允许重构系数取负值。从几何意义上而言,式(1)的重构结果位于邻域点扩张成的子空间中,而式(3)的重构结果是强迫重构结果落在邻域点的凸壳中。后者虽然更加鲁棒,但可能出现性能上的退化,而且计算代价大。从统计学的角度而言,数据被假设是从光滑流形上抽样而来的,并且抽样的密度较大。在这一假设下,直接采用式(1)的重构方法在理论上是合理的。

3实验与结果

3.1实验数据及硬件配置

本文从UCI机器学习库[8]中选择6个常用的基准数据集对提出的算法进行测试,它们分别是:Iris、Wine、 Heart、Pima、Haberman和Pendigits。 这些数据的具体信息如表1所示,它们的维度从3到17不等,数据集的大小从150到10992不等。对于前五个小数据集,将它们随 机地划分成10个尽量等大的子集,运用10倍交叉验证来计算一次的分类准确率,重复这样的交叉验证100次,取平均准确率作为最终的分类结果。对于较大的数据集Pendigits,按照UCI发布的训练集和测试集进行,即7494个训练样本,3498个测试样本,无需交叉验证,只需要分类一次即可。本文实验采用的硬件环境为:Intel T2130处理器,1GB内存,LINUX系统。

3.2实验结果

将K近邻分类器[1]和非负局部线性分类[7]的结果列出作为比较。表2是分类结果的比较情况,它们分别描述K= 30、40、50和60的结果对比情况。可以清楚地看出,本文算法较之两个最相关的工作有着总体的优势。此外,在Pendigits数据集上对算法的运行时间进行了比较,在求解式(1)和式(3)时,均采用Matlab中标准的二次规划函数,其结果如图2所示,可见LLRC算法的计算速度受K的影响较小。

4结语

本文提出了一种新的监督分类算法LLRC,它充分运用训练数据对测试数据的线性重构误差来实施分类。在一组实验数据集上的测试结果表明,提出的方法较之经典的K近邻分类器有着更高的分类准确率,较之KangCho算法有着一定的准确性优势和更快地计算速度,可以用于处理较大的数据集。

参考文献

[1]Cover T,Hart P.Nearest neighbor pattern classification[J].IEEE Transac-tions on Information Theory,1967,IT-IS:21-27.

[2]Chopra S,Hadsell R,Lecun Y.Learning a similiarty metric discrimina-tively,with application to face verification[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,San Di-ego,CA,2005.

[3]Domeniconi C,Gunopulos D,Peng J.Large margin nearest neighbor classi-fiers[J].IEEE Transactions on Neural Networks,2005,16(4):899-909.

[4]Goldberger J,Roweis S,Hinton G,et al.Neighborhood components a-nalysis[C].Advances in Neural Information Processing Systems,2005:513-520.

[5]Shalev-Shwartz S,Singer Y,Ng A Y.Online and batch learning of pseu-do-metrics[C]//Proceedings of the International Conference on Ma-chine Learning,2004.

[6]Shental N,Hertz T,Wwinshall D,et al.Adjustment learning and rele-vant component analysis[C]//Proceedings of the European Conference on Computer Vision,2002,4:776-792.

[7] Kang P,Cho S.Locally linear reconstruction for instance-based learning[J].Pattern Recognition,2008,41(11):3507-3518.

[8]Frank A,Asuncion A.UCI Machine Learning Repository[DB/OL].Ir-vine,CA:University of California,School of Information and Computer Science,2010.http://archive.ics.uci.edu/ml.

局部线性嵌入算法 篇2

考虑基于Facchinei F等(1997)提出的解决非线性互补问题的非光滑牛顿算法的收敛性质.对该算法我们在较弱的条件下给出了一般性的全局收敛结果,改进了Facchinei F(1997)和Dan H(2002)文中的相关结果,作为这个定理的`推论,我们得到的迭代序列的每一个聚点x*或者是非线性互补问题的解或者是稳定点.最后,在局部误差界的条件下给出了超线性(二阶)收敛速度的证明.

作 者：马骋 阴志民 王长钰 MA Cheng YIN Zhi-min WANG Chang-yu 作者单位：马骋,王长钰,MA Cheng,WANG Chang-yu(曲阜师范大学运筹与管理学院,276826,日照市)

阴志民,YIN Zhi-min(济南市第五职业中专学校,250001,山东省济南市)

局部线性嵌入算法 篇3

关键词：线性图嵌入,最佳鉴别矢量,降维,QR分解

0 引言

人脸识别由于在科学上的挑战性及其潜在的应用已成为计算机视觉和模式识别领域中的热门课题。对于人脸识别,其样本维数往往非常高。当样本维数较高时,往往会导致“维数灾难”[1],因此对高维样本进行降维就显得十分必要。主分量分析(PCA)[2]和基于Fisher准则线性鉴别分析(LDA)[2,3]是应用最广泛的两个线性降维方法。PCA是一种无监督学习算法,其目的是寻找在最小均方差意义下最能代表原始数据的投影方向。LDA作为一种有监督学习算法,其原理是使得降维后同类样本之间的距离最小,而异类样本之间的距离最大。受流形学习算法的启发,很多基于局部二阶统计量的线性降维方法被提出来,它们不是以类中心来衡量异类或同类样本的距离,而是用每个样本与它邻近的样本之间的距离来衡量的,较为典型的有局部保持投影(Locality Preserving Projection,LPP)[4]、无监督鉴别投影(Unsupervised Discriminant Projection,UDP)[5]、边界费希尔分析(Marginal Fisher Analysis,MFA)[6]、局部鉴别嵌入(Local Discriminant Embedding,LDE)[7]、邻域保持嵌入(Neighborhood Preserving Embedding,NPE)[8]。LPP算法能保持数据的局部结构信息,而UDP算法是LPP算法在数据为均匀分布时的一种特殊情况[9]。MFA和LDE算法本质上是一样的[10],MFA(LDE)算法的可分性准则是将同类样本中邻近的样本拉近,同时将异类样本间邻近的样本推远。NPE算法能够保持数据的局部流形结构。虽然上述各种线性降维方法的动机不同,但可以用线性图嵌入(Linear extension of Graph Embedding,LGE)的框架把这些算法统一起来[6,10]。

上述这些算法都会面临所谓的小样本问题(Small Sample Size Problem)。现有的一个解决思路是采用PCA+LGE的方法:首先对原始数据进行PCA降维,然后在降维后的空间用LGE算法进行二次特征抽取。PCA实际上是利用奇异值分解[2]实现的,其数值稳定性并不好,且算法的计算效率也不高。本文提出了一种基于QR分解的线性图嵌入求解算法,在本文算法中,利用QR分解而不是PCA对原始数据进行降维,提高了算法的稳定性和效率。另外,还从理论上证明了利用本文算法框架求得的鉴别矢量等价于利用伪逆的方法求得的鉴别矢量,同时也分析比较了本文算法框架PCA+LGE、LDA/QR[11]算法。最后,在Yale和PIE人脸数据库上的实验表明,本文提出的算法框架对人脸识别是有效的,可以显著的提高人脸识别精度。

1 线性图嵌入框架

在这一小节中简单的回顾线性图嵌入(LGE)框架。设X={x 1,x2,...,xn}∈Rm×n为训练样本集,其中m为样本的维数,n为样本数,G={X,W}为无向有权图,每个样本点xi为图中的一个顶点,W为相似度矩阵,Wij表示样本i和j的相似度。一个图的拉普拉斯矩阵L和对角矩阵D定义为

图嵌入的目标是找到一个原数据的低维表示y={y1,y2,...,yn}T,在y中保持原高维空间中顶点间的相似性。y可通过最小化式(2)得到:

为了防止求出没意义的解,给式(2)加入约束:yTDy=1,则式(2)变为

由于L=D-W,则式(3)可以变为

其解y为式(5)各个最大特征值所对应的特征向量:

假设从低维空间到高维空间是一个线性映射,即y=XTa,则式(4)可变为

如果需要d个投影矢量A=[a1,...,ad],则式(6)变为

A*可通过求解式(8)各个最大特征值所对应的特征向量得到:

上述方法就称为线性图嵌入(LGE),它为各种线性降维方法提供了一个统一的框架。通过选择不同的W和D,就可以得到常见的线性降维算法如LDA,LPP,NPE,MFA(LDE)等。值得注意的是,XWXT和XDXT都是对称的,且是半正定的矩阵。在后面的叙述中,我们用记号GE(W,D)来表示式(7)。

LDA算法:

设数据为c类并且第t类有mt个样本,m1+…+mc=n。定义:

DLDA=I,则LDA算法可表示为GE(WLDA,I)[10]。

LPP算法

设Nk(xi)表示xi的k近邻集合,定义:

LPP算法可以表示为GE(WLPP,DLPP)[10]。

NPE算法

设M为m×m矩阵,其定义为:对于M的第i行,Mij=0,如果xj∉Nk(xi);其它的Mij可通过最小化下式得到:

定义WNPE=M+MT-MTM,DNPE=I。则NPE算法可表示为GE(WNPE,I)[10]。

MFA(LDE)算法

设Nkc(xi)表示与xi同类的k个最近邻样本,Nkp(xi)表示与xi异类的k个最近邻样本。定义:

则MFA(LDE)算法可表示为GE(Lp,Lc)[10]。

2 基于QR分解的线性图嵌入求解算法

矩阵XWXT和XDXT的大小为m×m,对于人脸识别其维数常常有上万维,并且在求解式(8)时,要求解(XDXT)-1,即要求XDXT为非奇异矩阵,而对于人脸识别这样典型的3S问题,XDXT往往是奇异的。故一般应先对原始数据进行降维使得XDXT变为非奇异矩阵。在这里,我们不采用传统的PCA对数据进行降维,而是利用QR分解对数据进行降维。不失一般性,在后面的讨论中,假设数据是零均值的。

定理1:rank(X)≤n-1,n表示样本数。

证明:易知rank(X)≤min(m,n),m为样本的维数。对于像人脸识别这样的小样本问题有n≤m,故rank(X)≤n。由于X是零均值的,故其线性相关,即rank(X)≤n-1。证毕。

由于rank(X)≤n-1,故可设X的QR分解为

其中:Q∈Rm×t,Q~∈Rm×(m-t),矩阵[Q,Q~]为正交矩阵,R∈Rt×n为一上三角矩阵且t=rank(X)。设投影矩阵A可表示为A=QT,T∈Rt×d,则式(7)可写为

其中最后一个等式成立是因为QTQ=It。实际上,有如下定理:

定理2:设X=QR为X的QR分解,则式argmaxtr[(TTRDRTT)-1(TTRWRTT)]和式(7)的特征值相同,且T和QT分别为此两式的特征矢量矩阵。

证明:设r为矩阵T的一个列向量,则存在λ,使得式(11)成立

由于QTQ=It,则

与式(8)比较可知,λ和Qr为式(13)的特征值和特征矢量。因此,定理2成立。证毕。

由定理2可知,可首先通过式(11)求得最佳鉴别矢量矩阵T,然后求得最终的最佳鉴别矢量为矩阵A=QT。注意到矩阵RWRT和RDRT的大小是t×t,一般而言t<

对于LDA和NPE算法,由于D=I,故RDRT变为RRT,易知RRT为非奇异的,对于LPP算法,由于∀Dii>0,因此RDRT也是非奇异的。所以对于LDA,LPP和NPE算法,可直接利用式(11)求解其特征值和特征矢量矩阵T,从而求得最终的最佳鉴别矢量矩阵A*=QT。

而对于MFA算法,RDRT变为RLcRT,一般而言RLcRT还是奇异的,因此仍然不能利用式(11)求解。为清楚起见,把MFA的准则函数重新写在这里:

设LMFA=Lc+Lp,则可对MFA的准则函数进行修改,定义为

对于修改后的MFA准则函数式(15),一方面,当矩阵XLcXT非奇异时,式(15)和式(14)等价(其证明类似于文献[6]定理2的证明);另一方面,当矩阵XLcXT奇异时,利用式(15)可以有不损失鉴别信息的求最佳鉴别矢量的算法。

把用QR分解降维后的修改的MFA准则函数表示为

为使RLMFART变为非奇异,需去掉RLMFART的零空间。由于RLcRT和RLpRT都是半正定矩阵,易知RLMFART也是半正定矩阵,且RLMFART的零空间是RLcRT和RLpRT的零空间的交集,也就是说RLMFART的零空间包含在RLpRT的零空间之内,因此去掉RLMFART的零空间并不会损失其鉴别信息。设RLMFART的特征值分解为

其中:Λ=diag(λ1,...,λd′),λk>0,k=,12,...,d′,d′是RLMFART非零特征值的个数,U为非零特征值对应的特征向量。则式(16)变为

其中:MMFA=UTRLMFARTU=Λ,Mp=UTRLpRTU,B=UTT。很明显,此时MMFA非奇异,B*可通过求解式(19)各个最大特征值所对应的特征向量得到:

即通过求解式(20)得到:

则通过求解式(16)得到的鉴别矢量矩阵为T=UB,因此对于修改后的MFA准则函数式(15),其最终的最佳鉴别矢量矩阵为A*=QUB。

由上面求解过程可知,在求解修改后的MFA准则函数式(15)的过程中,并没有损失鉴别信息。而对于原来的MFA准则函数式(14),为了使RLcRT非奇异,则需去掉RLcRT的零空间。但是RLcRT的零空间并不包含在RLpRT的零空间之内,因此去掉RLpRT的零空间,就有可能损失鉴别信息。

3 与相关算法的比较

在求解式(8)时,可以用XDXT的伪逆(XDXT)+来代替(XDXT)-1,也就是求解(XDXT)+XWXT的特征向量。那么,通过本文算法求得的鉴别矢量与通过求解(XDXT)+XWXT得到的鉴别矢量这两者之间又有什么关系呢?下面的定理3回答了这个问题。

定理3:设A为通过本文算法求得的最佳鉴别矢量矩阵,则A为(XDXT)+XWXT的特征向量矩阵。

证明:首先考虑RDRT是非奇异的情况,也就是考虑LDA,LPP和NPE算法。设r为求解式(11)得到的特征向量,即

由于QTQ=It,则可得到式(22):

也即Qr是(XDXT)+(XWX)T的特征向量。由于A=QT,故对于RDRT是非奇异的情况,也就是LDA,LPP和NPE算法定理成立。

接下来考虑RDRT是奇异的情况,也就是考虑MFA算法(此时RDRT变为RLMFART)。对于MFA算法,只要用(RLMFART)+和RLPRT分别代替(RDRT)-和RWRT,则前面整个推导过程依然成立。由于通过我们的算法解得的式(16)的鉴别矢量为T=UB,而式(16)如果通过伪逆的方式求解,即是求矩阵(RLMFART)+RLpRT的特征向量。因此接下来只需证明T=UB是(RLMFART)+RLpRT的特征向量矩阵。由于

而由式(19)可知:

因此,T=UB是(RLMFART)+RLpRT的特征向量矩阵。证毕。

由定理3可知,通过本文算法求得的最佳鉴别矢量矩阵A和利用伪逆的方法来求鉴别矢量是等价的。但是,直接求解(XDXT)+(XWX)T是不可行的,因为矩阵(XDXT)+(XWX)T的大小是m×m。

另一种使XDXT为非奇异的方法是使用PCA对数据进行降维,然后再利用LGE框架内的算法进行二次特征提取,即形成了PCA+LGE。但这种算法框架存在两个问题:一方面在PCA降维的过程中会损失鉴别信息,另外一方面也很难确定PCA降维后的最佳维数。而本文算法是先对数据进行QR分解,根据式(10)的推导过程和定理2,在降维的过程中没有损失鉴别信息,并且其降维后的维数利用QR分解可直接计算出来。

在文献[11]中提出了求解LDA的LDA/QR算法。设

其中:Sw为类内散布矩阵,Sb为类间散布矩阵,c为类别数,ni为每类的样本数,mi为每类的均值,m为总体样本的均值。Hb为

LDA/QR算法是先对Hb进行QR分解,然后计算 各个最小特征值所对应的特征矢量为最佳鉴别矢量。由于LDA/QR算法是对Hb进行QR分解使Sb变为非奇异矩阵,其实质是抛弃Sb的零空间,这样做就有可能损失鉴别信息,另外此算法只能针对LDA算法而不能直接推广到LPP、NPE、MFA等其它算法。

而本文算法是对数据X进行QR分解,这样做并不会损失鉴别信息。另外,由于本文算法是基于图嵌入框架的,因此本文算法不仅仅适用于LDA算法,也适用于任意一种能纳入图嵌入框架的算法。

4 仿真实验及分析

在本文的实验中,基于QR分解的算法分别描述为QR+LDA,QR+LPP,QR+NPE和QR+MFA,而原始算法描述为PCA+LDA,PCA+LPP,PCA+NPE和PCA+MFA,在对数据进行PCA时,保留98%的能量。另外,实验中我们分别采用不同的训练样本数,并用剩余的样本作为测试。使用最近邻分类器。

4.1 在Yale人脸数据库上的实验

Yale人脸库包括15个人的165幅灰度人脸图像。每个人由11幅照片构成。这些照片在不同的表情和光照等条件下拍摄。实验中,图像被处理成32×32维的形式,图1为Yale数据库中的11幅人脸图像。随机在Yale库中选择i(i=2,3,4)幅图像作为训练样本,剩余的图像作为测试样本。每组实验均重复了20次,实验结果见表1,表中给出了20次实验的平均识别率和标准方差。

4.2 在PIE人脸数据库上的实验

PIE人脸库是个大规模人脸数据库,包含了68个人的41 368张人脸图像,这些图像由不同光照,不同姿势,不同表情下的图像组成。我们在实验中选择了POSE C29这个子集图像来验证各种算法的性能。POSE C29包含了68个人,每人24幅图像,共1 632幅图像。图2为POSE C29中某个人的24幅人脸图像,在实验中,图像被处理成64×64维的形式。随机在POSE C29中选择i(i=2,3,4)幅图像作为训练样本,剩余的图像作为测试样本。每组实验均重复了20次,实验结果见表2,表中给出了20次实验的平均识别率和标准方差。

由表1和表2可以看出,由于本文算法框架采用QR分解对数据进行降维,在降维的过程中并没有损失鉴别信息,且更具有数值稳定性,因此本文算法框架比传统的PCA+LGE框架具有更高的人脸识别率。

结束语

本文基于线性图嵌入,提出一种利用QR分解来求解LGE的鲁棒的算法框架。由于采用QR分解而不是PCA对数据进行降维,在降维的过程中不损失鉴别信息,提高了算法数值稳定性和识别率。在Yale和PIE人脸数据库上的实验表明:本文的QR+LGE算法框架在识别性能上优于传统PCA+LGE算法框架。

参考文献

[1]Fukunaga K.Introduction to Statistical Pattern Recognition(second edition)[M].Boston,USA:Academic Press,1990.

[2]Duda R O,Hart P E,Stork D G.Pattern Classification[M].New York:John Wiley&Sons,2000.

[3]Belhumeur P N,Hespanha Joao P,Kriegman David J.Eigenfaces vs.Fisherfaces:Recognition using class specific linear projection[J].IEEE Trans.Pattern Analysis and Machine Intelligence(S0162-8828),1997,19(7):711-720.

[4]HE Xiao-fei,YAN Shui-cheng,HU Yu-xiao,et al.Face Recognition Using Laplacianfaces[J].IEEE Trans on Pattern Analysis and Machine Intelligence(S0162-8828),2005,27(3):328-340.

[5]YANG Jian,ZHANG David,YANG Jing-yu,et al.Globally Maximizing,Locally Minimizing:Unsupervised Discriminant Projection with Applications to Face and Palm Biometrics[J].IEEE Trans.Pattern Analysis and Machine Intelligence(S0162-8828),2007,29(4):650-664.

[6]YAN Shui-cheng,XU Dong,ZHANG Ben-yu,et al.Graph embedding and extensions:A general framework for dimensionality reduction[J].IEEE Trans.Pattern Analysis and Machine Intelligence(S0162-8828),2007,29(1):40-51.

[7]CHEN Hwann-Tzong,CHANG Huang-Wei,LIU Tyng-Luh.Local discriminant embedding and its variants[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,San Diego,USA,June20-26,2005:846-853.

[8]HE Xiao-fei,CAI Deng,YAN Shui-cheng,et al.Neighborhood preserving embedding[C]//Tenth IEEE International Conference on Computer Vision,Beijing,China,2005:1208-1213.

[9]DENG Wei-hong,HU Jia-ni,GUO Jun,et al.Comments on“Globally Maximizing,Locally Minimizing:Unsupervised Discriminant Projection with Applications to Face and Palm Biometrics”[J].IEEE Trans.Pattern Analysis and Machine Intelligence(S0162-8828),2008,30(8):1503-1504.

[10]CAI Deng,HE Xiao-fei,HU Yu-xiao,et al.Learning a Spatially Smooth Subspace for Face Recognition[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Minneapolis,Minnesota,USA,June18-23,2007:1-7.