局部保持

局部保持（精选三篇）

局部保持 篇1

随着网络技术的迅速发展以及普遍应用,信息的产生和获取变得轻而易举,这一方面大大地提高了人们的生活效率,另一方面,大量的高维度、非线性数据又给信息处理领域带来了挑战,如数字图像、基因微阵列、金融事件序列、网络文本等[1]。因此,维数约简成为高维数据分析的重要预处理步骤之一,同时也是高维数据实现可视化或分类的前提。

维数约简是将样本从高维空间通过线性或非线性映射到一个低维空间[2],在获得最佳、最显著特征的同时减少无关信息,从而提高分类效率。维数约简方法通常分为线性维数约简法和非线性维数约简法。线性维数约简法主要包括主成分分析PCA(principal component analysis)[3]、Fisher判别分析FDA(Fisher discriminant analysis)[4]、局部投影保持LPP[5]以及基于神经网络的自组织映射SOM(self-organizing map)[6]等。非线性约简法主要包括基于核的方法和基于流形的方法。基于核的方法是利用Mercer核及其对应的再生核空间RKHS(reproduction kernel Hilbert space),不用创建复杂的假设空间,通过定义Mercer核隐式地定义特征空间。大部分线性维数约简方法都有其对应的基于核的非线性维数约简方法[2]。在基于流形的方法中比较著名的有局部线性嵌入LLE(Local Linear Embedding)[7]、等距映射Isomap[8]、拉普拉斯特征映射[9]等。

局部投影保持LPP是近年来提出的一种新的维数约简方法。当数据集采样于一个嵌入在高维空间中的低维流形上时,该算法可以较好地保留数据集的局部结构。同时,LPP作出的投影也是线性的,因此在增加新的数据时,该算法也可以找到对应的低维空间的表示。然而从本质上讲LPP只是一种无监督的维数约简方法,当两类数据靠得较近或部分重合时,由于局部保留结构的特性,LPP将把两个不同的类投影到一起,从而得到不理想的结果[10]。UDLPP[11]在LPP的基础上考虑了类别信息,通过在保持类内几何结构的同时最大化类间距离,此外,在利用UDLPP进行特征抽取时,在基向量的计算上加入了不相关的约束条件,从而获得了良好的鉴别性能。但是UDLPP只利用了类别信息,没有考虑近邻信息,不能很好地反映数据集的局部结构。

基于上述分析,本文结合模式数据局部结构信息和类别标签信息,提出了一种局部结构保持的模式分类新方法PCLSP。该方法在保持类间结构相对稳定的前提下,最小化同类近邻散度的同时最大化异类近邻散度,因而所获得的投影样本能更好地反映原有的分类信息以及数据集的局部特征,并在降维后的特征空间中,进一步提高了数据的可分性。

1UDLPP算法介绍

设有N个D维空间的训练样本X=[x1,x2,…,xN],每一个数据点xi属于C个类别w1,w2,…,wC中的一个,每一类包含nc(c=1,2,…,C)个样本。找出一个线性变换矩阵V∈RD×d来将这些样本点映射到一个d维的新空间Y=[y1,y2,…,yN]=VTX,其中,yi=VTxi。

UDLPP的目标是保持同类样本在低维空间中的几何结构,同时最大化不同类样本的映射距离。

首先,通过最小化表达式(1)找到一个能够保持数据集X同类几何结构的映射变换V。$J{}_1(V)={\displaystyle \sum _{i,j=1}^{{\rm N}}\parallel }y{}_i-y{}_j\parallel {}^{2}S{}_{ij}$

$=tr\left\{{\displaystyle \sum _{i,j=1}^{{\rm N}}(}y{}_i-y{}_j)(y{}_i-y{}_j){}^{{\rm T}}S\right\}$

=2tr{VTXLXTV} (1)

其中L=D-S,D是一个对角矩阵,其对角元素$D{}_{ii}={\displaystyle \sum _{j}S}{}_{ij}‚S$是一个相似矩阵,其定义为:

式中t是一个大于0的常数,其值可由经验选定。

其次,由于UDLPP的目标是解决分类问题,因此下面最大化类间距离。

其中,$m{}_i=(1/n{}_i){\displaystyle \sum _{y\in w{}_i}y}‚u{}_i=(1/n{}_i){\displaystyle \sum _{x\in w{}_i}x}$。Sb是类间离散度矩阵。

Sb=X(G-W)XT=XBXT (4)

结合式(1),式(3),式(4),则问题化简为最小化下面目标方程:

$J(V)=\frac{tr\{V{}^{{\rm T}}XLX{}^{{\rm T}}V\}}{tr\{V{}^{{\rm T}}XBX{}^{{\rm T}}V\}}$ (5)

2局部结构保持的鉴别分析方法PCLSP

从上一节的介绍可以看出,UDLPP虽然考虑了数据集类别信息,但是没有利用数据之间的近邻信息,因此不能很好地反映数据集的局部结构。综合考虑UDLPP的优缺点,本文对UDLPP算法作出了进一步的改进,提出了一种局部结构保持的鉴别分析方法。该方法在UDLPP的基础上考虑了先验的类别信息,同时为了进一步反映数据集的局部特性,该方法结合类别信息和近邻信息构造了同类近邻点和异类近邻点,通过最小化同类近邻散度和最大化异类近邻散度来进行模式分类。

与UDLPP算法相比,本文方法在构造相似矩阵时结合了类别标签信息与类内近邻信息,这使得同类模式的分布结构更紧凑。另外,UDLPP算法是通过最大化类间均值距离来进行模式分类的,而本文方法构造了异类近邻点,其目的是最大化每个样本点与其异类近邻均值的距离,从而使得不同类模式能更好地相互分离。

设X={x1,x2,…,xN}是D维空间的数据集,N是样本点的总个数。每一个样本点xi属于类集{w1,w2,…,wC}中的一个,C是总的类别数,每一类都包含nC(c=1,2,…,C)个样本点。我们的目标是找到一个线性的变换矩阵V∈RD×d,将数据集X映射到一个低维空间Rd(d<<D)中。数据集在Rd中的表示为Y={y1,y2,…,yN},且yi=VTxi。

首先,通过最小化下面的代价方程来寻找变换投影矩阵V,从而在利用近邻信息保持数据集X类内几何结构的同时,利用类别信息进一步保持其局部性。

$\begin{array}{l}J{}_1(V)={\displaystyle \sum _{i,j=1}^{{\rm N}}\parallel }y{}_i-y{}_j\parallel {}^2{S}^{\prime }{}_{ij}=tr\left\{{\displaystyle \sum _{i,j=1}^{{\rm N}}(}y{}_i-y{}_j)(y{}_i-y{}_j){}^{{\rm T}}{S}^{\prime }\right\}\\ =tr\left\{{\displaystyle \sum _{i,j=1}^{{\rm N}}(}y{}_{i}y{}_i^{{\rm T}}-y{}_{j}y{}_i^{{\rm T}}-y{}_{i}y{}_j^{{\rm T}}+y{}_{j}y{}_j^{{\rm T}})S^{\prime }{}_{ij}\right\}\\ =2tr\{Y{D}^{\prime }Y{}^{{\rm T}}-Y{S}^{\prime }Y{}^{{\rm T}}\}=2tr\{V{}^{{\rm T}}X{L}^{\prime }X{}^{{\rm T}}V\}(6)\end{array}$

其中,L′是拉普拉斯矩阵,L′=D′-S′,D′是一个对角矩阵,其对角元素$D^{\prime }{}_{ii}={\displaystyle \sum _j{S}^{\prime }}{}_{ij}$,S′是结合近邻信息和类别信息的相似矩阵,其定义为:

然后,通过最大化下面的表达式使得每个数据点与其异类k个近邻均值的距离最大,从而能有效地分离不同的类别。

$\begin{array}{l}J{}_2(V)={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^{n{}_i}\parallel }}y{}_i^{(j)}-m{}_i^{(j)}\parallel {}^2={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^{n{}_i}\parallel }}V{}^{{\rm T}}(x{}_i^{(j)}-u{}_i^{(j)})\parallel {}^2\\ =tr\left\{V{}^{{\rm T}}{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^{n{}_i}(}}x{}_i^{(j)}-u{}_i^{(j)})(x{}_i^{(j)}-u{}_i^{(j)}){}^{{\rm T}}V\right\}\\ =tr\{V{}^{{\rm T}}{S}^{\prime }{}_{t}V\}(8)\end{array}$

其中x${}_i^{(j)}$、y${}_i^{(j)}$分别表示在D维和d维空间中第i个类的第j个向量,u${}_i^{(j)}$是与x${}_i^{(j)}$不同类的k个近邻的均值,即$u{}_i^{(j)}=(1/k){\displaystyle \sum _{x\in {\rm K}{\rm N}{\rm N}(x{}_i^{(j)})}x}‚{\rm K}{\rm N}{\rm N}(x{}_i^{(j)})$表示的是与x${}_i^{(j)}$不同类的k个近邻的集合。m${}_i^{(j)}$是与y${}_i^{(j)}$不同类的k个近邻的均值,即$m{}_i^{(j)}=V{}^{{\rm T}}u{}_i^{(j)}=(1/k){\displaystyle \sum _{y\in {\rm K}{\rm N}{\rm N}(y{}_i^{(j)})}y}$。

$\begin{array}{l}{S}^{\prime }{}_t={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^{n{}_i}(}}x{}_i^{(j)}-u{}_i^{(j)})(x{}_i^{(j)}-u{}_i^{(j)}){}^{{\rm T}}\\ ={\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^{n{}_i}(}}x{}_i{}^{(j)}x{}_i{}^{(j)}{}^{{\rm T}}-x{}_i{}^{(j)}u{}_i{}^{(j)}{}^{{\rm T}}-u{}_i{}^{(j)}x{}_i{}^{(j)}{}^{{\rm T}}+u{}_i{}^{(j)}u{}_i{}^{(j)}{}^{{\rm T}})\\ =X({\rm I}-\frac{2}{k}{\rm H}+\frac{1}{k{}^2}{\rm H}{}^{{\rm T}}{\rm H})X{}^{{\rm T}}\\ =X{\rm M}X{}^{{\rm T}}(9)\end{array}$

其中,H=[H1,H2,…,Hc]T∈RN×N,Hi=[h${}_i^{(1)}$,h${}_i^{(2)}$,…,h${}_i^{(ni)}$]T,h${}_i^{(j)}$是N维行向量,它反映的是与x${}_i^{(j)}$异类近邻的情况,其定义为:

$h{}_{i(m)}^{(j)}=\{\begin{array}{l}1X\text{中}\text{第}m\text{个}\text{样}\text{本}\text{点}\text{是}x{}_i^{(j)}\text{的}\text{异}\text{类}\text{近}\text{邻}\\ 0\text{其}\text{它}\end{array}(10)$

${\rm M}={\rm I}-\frac{2}{k}{\rm H}+\frac{1}{k{}^2}{\rm H}{}^{{\rm T}}{\rm H}$ (11)

结合式(6),式(8)和式(11),最小化下面的目标方程来求得投影变换矩阵V。

$J(V)=\frac{tr\{V{}^{{\rm T}}XLX{}^{{\rm T}}V\}}{tr\{V{}^{{\rm T}}X{\rm M}X{}^{{\rm T}}V\}}$ (12)

算法步骤:

步骤1:构造每个训练样本xi同类的K1个近邻,由式(7)建立同类相似矩阵S′。

步骤2:构造每个训练样本xi异类的K2个近邻,由式(10)建立异类离散矩阵H。

步骤3:计算拉普拉斯矩阵L′,并根据式(11)计算矩阵M。

步骤4:取特征方程XLXTV=λXMXTV的d个最大的特征值所对应的特征向量作为投影轴。

步骤5:将样本向量投影到该投影轴上,再分类识别。

相似矩阵S′反映同类模式的局部分布结构,离散矩阵H反映异类模式的局部散布结构。步骤4选取d个最大特征值对应的特征向量,使得判据公式(12)取最大值。

3实验结果与分析

3.1实验1与分析

实验1采用的人脸图像来源于ORL。ORL库包含40个人,每个人10幅图像,图像的分辨率为112×92,这些图像有些拍摄于不同时期;人脸脸部表情与脸部细节有变化,例如:笑或不笑,睁眼或闭眼,戴与不戴眼镜;人脸姿态有变化,旋转可达20度;人脸尺度也有最多10%的变化。

在本实验中,训练样本均从人脸库中随机产生,每次随机抽取每类人脸的m(m=4,5)个样本组成训练样本集,并将剩余的数据作为测试数据。在固定训练样本数目的情况下,每次试验均随机产生10组不同的训练样本集,并统一采用最近邻分类器进行分类识别,试验结果取10次试验的平均值。另外,在实验过程中同类近邻K1取为m-1, 异类近邻K2取为50, 然后我们选取5到40个投影轴进行特征抽取,最后我们比较PCA,LPP,UDLPP和本文方法在最小距离分类器下分类识别效果。图1和图2描述了m(m=4,5)个训练样本下这四种方法在ORL人脸库上的识别效果。表1描述了不同训练样本下四种方法在ORL人脸库上的最佳识别率。

由图1可以看到,当训练样本数选为4时,本文方法在最近邻分类器下的识别性能均优于PCA、LPP以及UDLPP。当投影轴数达到25到40的阶段时识别率达到最大值且逐渐趋于稳定。

由图2可以看到,当训练样本数选为5时,本文方法在最近邻分类器下的识别性能均优于PCA、LPP以及UDLPP。当投影轴数达到20到40的阶段时识别率达到最大值且逐渐趋于稳定。

由表1可以看到,在训练样本为4和5时本文方法的最佳识别率分别达到了92.46%和96.35%,且都超过了其他三种方法的最佳识别率。

3.2实验2与分析

本实验采用的人脸图像来源于Yale Center for Computational Vision and Control,其中包括15个人,每人11幅图像构成。这11幅图像分别为正常光照条件下,是否戴眼镜,不同光源,不同表情下的图像。每幅图像的分辨率为100×80。

在本实验中,训练样本均从人脸库中随机产生,每次随机抽取每类人脸的m(m=4,5)个样本组成训练样本集,并将剩余的数据作为测试数据。在固定训练样本的情况下,每次试验均随机产生10组不同的训练样本集,并统一采用最近邻分类器进行分类识别,试验结果取10次试验的平均值。另外,在实验过程中同类近邻K1取为m-1, 异类近邻K2取为50, 然后我们选取5到50个投影轴进行特征抽取,最后我们比较PCA、LPP、UDLPP和本文方法在最小距离分类器下分类识别效果。图3和图4描述了m(m=4,5)个训练样本下这四种方法在YALE人脸库上的识别效果。表2描述了不同训练样本下四种方法在YALE人脸库上的最佳识别率。

由图3可以看到,当训练样本数选为4时,本文方法在最近邻分类器下的识别性能均优于PCA, LPP以及UDLPP。当投影轴数达到15到30的阶段时识别率达到最大值且逐渐趋于稳定。

由图4可以看到,当训练样本数选为5时,本文方法在最近邻分类器下的识别性能均优于PCA, LPP以及UDLPP。当投影轴数达到15到50的阶段时识别率达到最大值且逐渐趋于稳定。

由表2可以看到,在训练样本为4和5时本文方法的最佳识别率分别达到了91.33%和94.67%,且都超过了其他三种方法的最佳识别率。

4结语

在UDLPP算法的基础上提出了一种局部结构保持的鉴别分析方法,并将其应用于人脸识别。与UDLPP方法相比,本文结合模式数据局部结构信息和类别标签信息构造了同类近邻散度和异类近邻散度,从而使求解的特征更具有判别性。该方法在人脸识别应用中识别效果优于主成分分析(PCA),局部投影保持(LPP)以及不相关保局投影鉴别UDLPP,提高了识别性能。ORL和YALE人脸库上的实验证明了该算法的有效性。

本文提出的PCLSP算法属于线性方法,怎样将该算法拓展为非线性方法,并进一步提高其分类性能,将是我们今后进一步研究和探索的工作。

摘要：局部投影保持LPP(Locality Preserving Projections)是一种局部特征提取算法,它能够有效地保留数据集的局部结构。不相关保局投影鉴别UDLPP(Uncorrelated Discriminant Locality Preserving Projections)在LPP的基础上考虑了类别信息,通过保留类内几何结构并最大化类间距离获得了良好的鉴别性能。结合UDLPP的思想,在UDLPP的基础上提出了一种局部结构保持的鉴别分析方法PCLSP(Pattern Classification based on Local Structure Preserving)。该方法结合了数据集的类别信息以及数据集的局部结构信息,通过最小化类内近邻分离度以及最大化类间近邻分离度来提高鉴别性能,从而进一步反映了数据的局部结构,提高了识别率。通过在ORL(Olivetti-Oracle Research Lab)和YALE两个标准人脸库上实验验证了该算法的有效性。

关键词：LPP,UDLPP流形,人脸识别

参考文献

[1]马千驰,余国先,钟鸿鹏.一种增强的局部投影保持方法[J].计算机工程与应用,2010,46(10).

[2]黄启宏,刘钊.流形学习中非线性维数约简方法概述[J].计算机应用研究,2007,24(11).

[3]JOLL IFFE I T.Principal component analysis[M].New York:Springer-Verlag,1986.

[4]Gordon A D.Classification:methods for the exploratory analysis ofmultivariate dsta[M].New York:Wiley,1977.

[5]He X,Yan S,Hu Y,et al.Face recognition using Laplacian faces[J].IEEE Trans.On Pattern Anal.Machine Intelli.,2005,27(3):328-340.

[6]Kohnone T.Self-organizing map s[M].3rd ed.Berlin:Springer-Ver-lag,2001.

[7]Sam T Roweis,Lawrence K Saul.Nonlinear Dimensionality Reductionby Locally Linear Embedding[J].Science,2000,290:2323-2326.

[8]Tenenbaum J,silva D D,Langford J.A global geometric framework fornonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[9]Belkin M,Niyogi P.Laplicain Eigenmaps for Dimensionality Reduction andData Representation[J].Neural Computation,2003:1373-1396.

[10]Sugiyama M.Local Fisher Discriminant Analysis for Supervised Di-mensionality Reduction[C]//Proc of the 23rd International Conferenceon Machine Learning.Pittsburgh,USA,2006:905-912.

局部保持 篇2

He等人提出的局部保持投影[1,2](Locality Preserving Projection,LPP)是一种新的特征提取算法,该算法根据样本之间的空间距离来构造相似矩阵,以保留数据内在的几何特性和局部结构为目标,在人脸识别中取得了较好的识别结果,因而受到了学者们的关注。如文献[3]给出了LPP在应用于高维小样本时的具体求解框架;文献[4]则针对LPP数值解的稳定性进行了研究,给出了一种稳定的求解模型;文献[5]则针对LPP中的相似矩阵进行了研究,给出了一种优化相似矩阵的LPP。但这些改进方法从准则函数上看,并没有和分类问题直接联系起来。不同于上述几种改进的LPP方法,最近文献[6]提出了一种无监督的判别投影(Unsupervised Discriminant Projection,UDP)算法,该算法认为同类样本相互靠近,而非同类样本是远离的,因此投影后同类样本保持近邻关系,非同类样本仍是远离的,其目标函类似于经典的LDA的目标函数[7,8],因此比上述几种改进的LPP更适合于分类问题。但UDP没有用到样本的类别信息,也不能够有效地解决人脸识别中的小样本问题,另外其所求得的投影矩阵也不具有正交性。而已有研究表明[9,10,11,12],具有正交性的特征提取算法由于可以消除样本间的信息冗余,因此能够明显提高算法的识别性能。故此本文以UDP为理论基础,提出一种基于极小准则的完备正交判别局部保持算法(Complete Orthogonal Discriminant Locality Preserving Method,CODLPM),该算法给出了一种有监督的基于极小准则的目标函数,由于采用了极小准则目标函数,因此可有效地解决人脸识别问题中的小样本问题。对于如何求解具有正交性的投影矩阵,本文给出了基于QR分解的求解方法,并给出了相应的证明。

1 无监督判别投影UDP

UDP是对LPP的进一步发展,其目标函数类似于经典的LDA,因此比LPP更加适合分类问题,但是仍没有用到样本的类别信息,为了方便后面的讨论,首先给出关于文献[6]中几个基本定义:局部散度矩阵SL和总体散度矩阵St,定义如下

式(1)中的hij按下式计算

上式(3)中的t是可调参数,其取值范围为0

显然式(1)与式(4)之和为总体散度矩阵St,即

局部散度矩阵SL与非局部散度矩阵SNL的其含义类似于LDA中的类内散度矩阵和类间散度矩阵,但并没有用到样本的类别信息。UDP准则函数为

或者

上面二式是等价的。在求解过程中,UDP给出首先要将目标函数投影到St非零特征值所对应的特征向量构成的空间P中,而在这样一个低维的子空间中并不损失任何有效的判别信息,并给出了具体的证明,最后求解可转换为下面的特征值求解问题,即

其中:,假设把求得的特征值按降序排列,选择对应前d(通常d

2 完备的正交判别局部保持投影算法

UDP并没有用到样本的类别信息,因此从分类角度来讲,该算法并不是最优的;另一方面UDP所求的投影矩阵不具有正交性,并且将其应用于人脸识别中,并不能保证SLP是可逆的,仍存在着小样本问题,而为了解决这一问题,按照已有的理论可知,还需要再次投影变换以保证SLP是非奇异的。但是根据UDP的准则函数可知,若有x使得xTSLPx=0,但有xTSPNLx>0,则此时x使得UDP的准则函数最大化,也就是SLP的零特征值对应的特征向量仍可能是准则函数的最优解,因此这种做法将损失一部分有效的判别信息,因此该方法是不完备的。

为了解决上述的问题,本文以UDP为理论基础,提出一种基于极小准则的完备正交判别局部保持算法(CODLPM)。首先给出CODLPM的目标函数。

2.1 基于极小准则的CODLPM目标函数

为了有效地解决小样本问题,且不损失判别信息,提出CODLPM采用极小准则目标函数。在UDP中局部散度矩阵SL和非局部散度矩阵SNL均用到了相似系数hij,但hij的计算并不考虑样本的类别信息,在此给出按类别计算的相似系数sij,sij由下式求出[10,11]

此时计算出的sij充分地利用了样本的类别信息,因此将更适合模式识别问题。将式(1)和式(4)的hij替换为sij,将式(1)SL记为称为类内局部保持散度矩阵,同理SNL记为称之为类间局部保持散度矩阵。把式(6)UDP的目标函数中的相应项换成,则有监督的UDP的目标函数为

根据式(1)和式(4)的定义,此时仍有,因此式(10)可等价为

显然式(10)又可等价为下面的极小准则

加上正交约束条件,可得本文的基于极小准则的CODLPM目标函数

2.2 CODLPM的求解及算法的实现

对于CODLPM目标函数的求解,借鉴于文献[6],可先将式(12)的求解转化成为下面广义线性方程特征值与特征向量的问题

对于上式,要保证St可逆才能进行求解,因此要对CODLPM目标函数进行预处理。根据UDP及文献[13,14]可知,首先将准则函数投影到St非零特征值所对应的特征向量构成的空间P中,而在空间P中并不损失任何有效的判别信息,因此投影到空间P中并不损失任何有效的判别信息。故式(13)的求解应转化成为下式

式中StP=PTStP,显然StP是可逆的。假设把求得的特征值按升序排列λi≤λi+1,选择对应前d(通常d

假设Rank(St)=N-1,V=[v 1,v2,…,vd],V=QR是V的QR分解,其中Q∈R(N-)1×d是正交阵,RT∈R(N-)1×d是上三角阵,有下面定理。

定理1:令V=QR是V的QR分解,则有。

证明:由于

又根据矩阵论有tr(AB)=tr(BA),因此有

证毕。

根据定理1可知,要求出正交矩阵Q,可先求出式(15)的特征向量V=[v 1,v2,,vd],再对V进行QR分解得到正交矩阵Q,Q即是最小化准则函数的正交阵。

关于CODLPM的具体求解步骤如下:

1)根据式(1)、(2)和(9)分别计算出ˆSL和St;

2)求出St非零特征值所对应的特征向量所构成的矩阵P;

3)将准则函数投影到P空间,也就是计算出;

4)求出式(15)广义线性方程的特征值与特征向量,选择对应前d(通常d

5)对V=[v 1,v2,…,vd]进行QR分解,则最终得到W=PQ就是所求的最优正交投影矩阵。

3 实验结果与讨论

本文为了验证提出CODLPM的性能,分别在FERET和AR人脸库上进行了实验。实验中为了能最大限度地排除分类器对算法优劣的影响,采用简单的最近邻方法进行分类。

FERET人脸图库[15]是由美国国防部建立的,目前已经成为对人脸识别算法进行评估的一个标准数据库。本文选择其中一个子集来进行测试,该子集包括70人,每人6幅图像,每幅人脸图像的尺寸为92×112。AR人脸库[16]由120人的4 000多幅图像组成,实验中选择其中一个子集来进行测试。该子集包括100人,每人15幅图像,每幅人脸图像的尺寸为100×100。分别进行了如下两组实验。

1)对CODLPM提取的特征个数变化时的性能测试

分别选择两个人脸库的前5幅图像作为训练样本,剩余作为测试样本,将CODLPM和其它几种算法[9,10,11]在提取不同特征个数时的识别性能进行了比较,如图1和图2所示。

由于ODLDA和ODLPP最大特征数为C-1(C样本类别数),故此本文将CODLPM、ODLDA和ODLPP的提取的最大特征数都取为C-1。本文的CODLPM并不受类别数目限制,但在实验中发现每次提取出C-1个特征时就达到了最好效果,继续增加并不能提高识别效果。UDP提取的特征也不受类别数目限制,由于UDP在提取出C-1个特征时并没有好的效果,因此实验中提取了较多的特征,结果如图1和图2所示。从图1和图2结果可以看出,随着特征数目的增多,几种算法的识别率都明显升高,CODLPM在超过40个特征时,其识别结果明显好于ODLDA和ODLPP,并取得了最好的识别结果。

2)对CODLPM在两个人脸库上选择不同训练样本的性能测试

为了消除CODLPM识别结果的偶然性,在每次实验中,每人随机选择T幅图像作为训练样本,在FERET和AR人脸库T的取值为3∼5,剩余6-T(或者15-T)幅图像作为测试样本,如此对每种算法重复进行10次的实验,取10次平均识别结果作为每种算法的识别结果,实验结果如表1与表2所示。

从表1和表2识别结果可以看出CODLPM明显优于UDP,这是因为CODLPM采用了样本的类别信息,是一种有监督的特征提取方法,因而可获得有助于分类的特征,因此获得较好的识别结果;同时CODLPM也优于OLDA和ODLPP,这是因为CODLPM以保留同类样本的局部结构为目标,并采用了极小准则函数,有效地解决小样本问题,保证了在求解过程中不损失任何有效的判别信息,因此其识别性能也优于OLDA和ODLPP。

4 结论

本文提出一种新的特征提取算法—CODLPM。本文利用新的散度矩阵定义形式,推导出一种基于极小准则的目标函数,对于该目标函数由于采用极小准则及总体散度矩阵作为分母,因此按照已有理论可将CODLPM的目标函数投影到总体散度矩阵的非零特征值所对应特征向量构成的空间,而在这样的子空间并不损失任何有效的判别信息,从而有效地解决了人脸识别中的小样本问题,保证了算法的完备性,而对于正交投影矩阵的求解,本文给出了基于QR分解的求解方法,并给出了相应的证明,从而为正交投影算法提供了一种新的思路。

摘要：以无监督判别投影算法为理论基础,提出了一种基于极小准则的完备正交判别局部保持投影算法。算法首先根据同类样本的空间信息重新定义了类内局部保持散度矩阵与类间局部保持散度矩阵,然后借鉴无监督判别投影算法的目标函数,推导出一个基于极小准则的目标函数,该目标函数通过投影到总体散度矩阵的非零空间中有效地解决小样本问题,最后给出了该算法基于QR分解的正交投影矩阵的求解方法。人脸库上的实验结果表明了所提方法的有效性。

局部保持 篇3

作为生物识别技术的重要研究方向,人脸识别技术在近年来引起了世界范围内专家学者的研究兴趣。特征提取[1,2,3,4,5]是人脸识别技术的关键环节,为获得有效的判别特征,已有许多的特征提取算法被相继提出。

目前广泛应用的特征提取算法主要是统计分析方法,如主成分分析(Principal Component Analysis,PCA)[6]、线性判别分析(Linear Discriminant Analysis,LDA)[7]等,这些算法大都是基于方差贡献率,通过计算样本相关矩阵的特征值以确定所要提取的特征维数,衡量数据特征的提取质量,并不能真正从信息的角度来评价提取的效果,也不能保证降维后的分类性能。局部保持映射(Locality Preserving Projections,LPP)[8]是最近提出的一种基于流形学习的局部线性特征提取方法。该算法通过保持降维前后数据集近邻点之间的距离不变,从而保持了数据的局部信息,虽然较传统的特征提取方法考虑了局部特性,但其仍然没有考虑类别信息,因此不适合分类问题。近年来人们对LPP 提出了很多改进的算法,如描述性更强,计算代价小的二维局部流形特征提取算法(2DLPP)[9,10],以及将PCA与LPP 结合的基于局部和全局的特征提取算法(LP-PCA)[11]等,但依然没有弥补它们在分类性能上的不足。

美国电气工程师Shannon C E在1948年首次提出信息熵[12]的概念,作为随机事件的“不确定性”或者信息量的量度。本文的总体熵基于信息熵的概念,用于度量特征提取中类均值向量代表同类各样本的不确定性,在特征提取中的运用具有优化分类的性能。

本文利用总体熵在分类方面的作用,对LPP进行改进,弥补了LPP在分类上的不足,提出基于熵的局部保持特征提取算法S-LPP。新算法不仅能保持数据的局部信息,而且具有分类性能和更好的识别率。通过在ORL和Yale人脸库上的实验证明了新算法的有效性。

1局部保持特征提取算法

LPP基本原理是在降维前后保持数据间的相似性不变,具体做法:数据集X={x1,x2,…,xn}含有n个样本点,每个样本点属于D维欧式空间,即xi∈RD,LPP通过定义两近邻数据点xi,xj间的相似性Sij:

$S{}_{ij}=\{\begin{array}{cc}\frac{\exp (-\parallel x{}_i-x{}_j\parallel {}^2/\beta )}{t},& x{}_{i,}x{}_j\text{为}\text{近}\text{邻}\text{点}\\ 0‚& \text{其}\text{他}\end{array}(1)$

保持原空间相邻数据点在投影空间上近邻关系不变。数学形式表示为寻找一投影矩阵W,使得y=WTx,通过求解以下最小化问题得到最佳的投影:

$\begin{array}{l}\underset{\mathit{W}}{{\displaystyle \min }}{\displaystyle \sum _{ij}(}y{}_i-y{}_j){}^{2}S{}_{ij}=\underset{\mathit{W}}{{\displaystyle \min }}{\displaystyle \sum _{ij}(}\mathit{W}{}^{\text{Τ}}x{}_i-\mathit{W}{}^{\text{Τ}}x{}_j){}^2\\ S{}_{ij}=\underset{\mathit{W}}{{\displaystyle \min }}\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\mathit{W}(2)\end{array}$

附加约束条件WTXDXTW=1。拉普拉斯算子L=D-S,S为Sij构成的对称权值矩阵,D为S行向量(或列向量)元素之和,即$D{}_{ii}={\displaystyle \sum _{j}S}{}_{ij}$。最后通过以下广义特征方程解:

$\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\omega =\lambda \mathit{X}\mathit{D}\mathit{X}{}^{\text{Τ}}\omega (3)$

取其前d个最小特征值所对应的特征向量组成投影矩阵W,通过y=WTx将数据集投影到d维空间。

LPP在各类识别任务中得到了广泛的应用,但它是一种非监督学习,没有考虑数据的类别信息,所以在分类方面的结果并不理想。为解决这一问题,本文利用基于信息熵的总体熵对其进行了改进,提出了基于总体熵的LPP特征提取算法。

2基于Shannon熵的局部保持特征提取算法

2.1 总体熵

考虑到样本各类均值包含有很多的判别信息,若属于同一类特征向量偏离它的均值向量很大,会造成各类所占的子空间互相重叠,导致分类困难。因此所选择的特征量应当具备这样的优点,当用同一类的这些特征量的均值所组成的向量代表该类样本进行分类时,所引起的分类不确定性度量为最小。这里采用总体熵来度量这种分类的不确定性,定义:

${\rm H}{}_p=-E[\log p(x)](4)$

作为类均值向量代表同类各样本不确定性的一种度量。

用两个极端情况说明总体熵定义的合理性。样本分布为p(x)=δ(x-μ)。此时该类样本可用样本均值μ代表,总体熵Hp→-∞。p(x)=1/ν(ν是样本集合所占特征空间体积)。此时p(x)完全均匀分布在ν中,μ不能很好地代表该类应该的样本。Hp=log ν,ν越大Hp越大,由此可见,找到的变换矩阵W(D×d)应该使D维空间变换到d维空间后,同一类样本所占据的体积最小,即使总体熵Hp最小。经过变换后的总体熵为:

${\rm H}{}_p(\mathit{W})=-E[\log p(\mathit{W}{}^{\text{Τ}}x)](5)$

采用高斯分布ps(WTx)来逼近p(WTx),以求出使Hp(W)为最小的变换矩阵。即:

$\begin{array}{l}p{}_{\text{s}}(\mathit{W}{}^{\text{Τ}}x)=(2\text{π}){}^{\frac{-d}{2}}|\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}|{}^{\frac{-1}{2}}\cdot \\ \exp \left\{-\frac{1}{2}\mathit{x}{}^{\text{Τ}}\mathit{W}(\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W})\mathit{W}{}^{\text{Τ}}\mathit{x}\right\}(6)\end{array}$

式中Σ=E[xxT]是样本集的协方差。因此:

$\begin{array}{l}{\rm H}{}_p(\mathit{W})=\log [(2\text{π}){}^d|\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}|]{}^{\frac{1}{2}}+\frac{1}{2}\text{t}\text{r}(\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}){}^{-1}\cdot \\ (\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W})=\frac{1}{2}\log |\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}|+\text{C}(7)\end{array}$

式中C为常数。

基于总体熵的特征提取,以最小化总体熵求最佳变换矩阵,其目标函数为:

$\underset{\mathit{W}}{{\displaystyle \min }}{\rm H}{}_p(\mathit{W})=\underset{\mathit{W}}{{\displaystyle \min }}\frac{1}{2}\log |\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}|+\text{C}(8)$

可简化为:

$\underset{\mathit{W}}{{\displaystyle \min }}\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}(9)$

投影矩阵的列向量由Σ的前d个最小特征值对应的特征向量组成,通过y=WTx将数据集投影到d维空间。

2.2 基于总体熵的LPP

总体熵利用了类均值所包含的判别信息,在特征提取中具有利于分类的优点,本文将其用于不利于分类的LPP 中,提出改进的基于总体熵的LPP 特征提取,使降维后的数据即保持了原数据的局部性又有利于分类。

综合两个方面的目标函数:

$\begin{array}{l}\underset{\mathit{W}}{{\displaystyle \min }}\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\mathit{W}\\ \underset{\mathit{W}}{{\displaystyle \min }}\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W}\\ \text{C}\text{o}\text{n}\text{s}\text{t}\text{r}\text{a}\text{i}\text{n}\text{t}:\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{D}\mathit{X}{}^{\text{Τ}}\mathit{W}=1(10)\end{array}$

化为单一目标函数:

$\begin{array}{l}\underset{\mathit{W}}{{\displaystyle \min }}(\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\mathit{W}+\mathit{W}{}^{\text{Τ}}\Sigma \mathit{W})\\ \text{s}.\text{t}:\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{D}\mathit{X}{}^{\text{Τ}}\mathit{W}=1(11)\end{array}$

最终转化为求解以下广义特征值方程问题:

$(\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}+\Sigma )\mathit{W}=\lambda \mathit{X}\mathit{D}\mathit{X}{}^{\text{Τ}}\mathit{W}(12)$

求解此特征方程d个最小特征值对应的广义特征向量作为列向量构成投影矩阵W,则图像X就能通过Y=WTX嵌入到低维子空间。

利用S-LPP提取特征之后,采用最近邻分类。定义经过投影后的两个图像特征矩阵yi=[yi1,yi2,…,yid]与yj=[yj1,yj2,…,yjd]之间的距离为:

$d(\mathit{y}{}_i,\mathit{y}{}_j)={\displaystyle \sum _{m=1}^d\parallel }y{}_{im}-y{}_{jm}\parallel {}_2(13)$

利用新算法S-LPP进行人脸识别的基本步骤:

(1) 写出由n个训练样本构成的训练样本集矩阵X={x1,x2,…,xn}。

(2) 根据式(1)计算权值矩阵S。

(3) 根据式(13)做本征值分解,求出投影矩阵W。

(4) 将训练样本图像向W做投影,得到其特征矩阵yi=[yi1,yi2,…,yid]。

(5) 将测试样本图像向W做投影,得到其特征矩阵yj=[yj1,yj2,…,yjd]。

(6) 根据式(13)计算yi和yj的欧式距离,根据最近邻分类进行分类。

3实验结果及分析

在ORL和Yale标准人脸库上进行实验,ORL人脸库有40个人,每人包含了不同时期不同光照强度下拍摄的姿态、光照和表情变化下的10张图像,一共400张。Yale人脸库包含了15人,每人11张图像,一共165张,也受表情、光照等因素的变化。图1与图2分别是来自于ORL一个人的样本与Yale人脸库一个人的样本。

将所有的图像都缩放成32×32像素,即每一图像可用维向量。每人分别随机选择其中的3,4,5,6,7 幅图像作为训练样本,其他的图像作为测试样本,重复50次,最后计算平均识别率作为识别结果,采用NN(最近邻近)分类器进行分类。将本文的算法S-LPP与传统LPP进行了比较,实验结果如表1、表2所示。

%

根据实验结果可以看出,两类算法在ORL人脸库中的结果更为理想,这是由于此人脸库中图像的表情、光照等因素变化较少,更适合关键特征的提取。由表中实验数据可知,LPP与S-LPP在人脸实验中的识别率都随着训练样本数目的增加而增高,在两组实验中LPP的识别率分别从82.3%增加到94.2%,从73.2%增加到79.6%,而S-LPP则分别从85.6%增加到97.9%,从79.4%增加到87.3%。可见,虽然识别率都有所增加,但S-LPP在不同训练样本数目下都比LPP有更高的识别率。由此可以看出,本文提出的改进算法比传统的LPP算法有更好的识别率,不仅保持了数据的局部信息,还考虑了类别信息,更利于分类,从而获得了更好的识别效果。

%

4结语

本文基于熵提出的描述类均值向量代表同类各样本不确定性的总体熵,借助于最小化总体熵,从分类的角度进行特征提取,并将此方法针对LPP不利于分类的缺点进行了改进,使其更有利于分类,并应用于人脸识别。通过实验证明了本文算法的有效性,提高了识别率。

参考文献

[1]MAO Yong,SUN You-xian,XIA Zheng,et al.A surveyfor study of feature selection algorithms[J].Pattern Re-cognition and Artificial Intelligence,2007,20(2):211-218.

[2]DING Shi-fei,JIA Wei-kuan,SU Chun-yang,et al.A sur-vey on statistical pattern feature extraction[C]//Proc ofthe 4th International Conference on Intelligent Computing.Shanghai,China:ICIC,2008:701-708.

[3]FOMAN G.An extensive empirical study of feature selec-tion metrics for text classsification[J].Journal of MachineLearning Research,2003,3:1289-1305.

[4]SONG Feng-xi,GAO Xiu-mei,YANG Jing-yu,et al.Di-mensionality reduction in statistical pattern recognition andlow loss dimensionality reduction[J].Chinese Journal ofComputers,2005,28(11):1915-1922.

[5]DING Shi-fei,JIA Wei-kuan,SU Chun-yang,et al.Re-search of pattern feature extraction and selection[C]//Proc of the 7th International Conference on Machine Lear-ning and Cybernetics.Kunming,China:ICMLC,2008:466-471.

[6]TURK M,PENTLAND A.Eigenfaces for recognition[J].Cognitive Neurosci,1991,3(1):71-86.

[7]KWON O W,LEE T W.Phoneme recognition using ICA-based feature extraction and transformation[J].Signal Pro-cessing,2004,84(6):1005-1019.

[8]HE X,NIYOGI P.Locality preserving projections:ad-vances in neural information processing systems[M].Cam-bridge:MIT Press,2004.

[9]HU Den-wen,FENG Gui-yu,ZHOU Zong-tan.Two-dimensional locality preserving projections(2DLPP)with its application to palmprint recogition[J].Pattern Re-cognition,2007,40(1):339-342.

[10]YU Wei-wei.Two-dimensional discriminant locality pre-serving projections for face recognition[J].Pattern Re-cognition,2009,50(15):1378-1383.

[11]王庆刚,李见为.具有局部结构保留性质的PCA改进算法[J].模式识别与人工智能,2009,22(3):387-392.