基于低秩稀疏图的结构保持投影算法*
2015-09-22杨国亮丰义琴梁礼明
杨国亮,罗 璐,丰义琴,梁礼明
(江西理工大学电气工程与自动化学院,江西 赣州 341000)
基于低秩稀疏图的结构保持投影算法*
杨国亮,罗 璐,丰义琴,梁礼明
(江西理工大学电气工程与自动化学院,江西 赣州 341000)
在图嵌入理论框架下,能够较好地揭示数据本质特性的图在一些维数约简方法中起到关键性的作用。基于稀疏表示和低秩表示方法,构建了一种低秩稀疏图,能够同时揭示数据的局部结构信息和全局结构信息。然后,利用图嵌入理论方法使这些特性在线性投影的过程中得以保持不变,从而学习出高维数据有效的低维嵌入。在标准的人脸和手写数字数据集(ORL,Yale,PIE,MNIST)上进行实验,同传统的图嵌入方法比较,结果表明了算法的有效性。
图嵌入;稀疏表示;低秩表示;低秩稀疏图;线性投影
1 引言
现今,学习高维空间的低维投影这一维数约简技术被广泛地应用在计算机视觉和模式识别领域中。投影技术的主要步骤是采用某种学习算法学习出数据的转换矩阵A,然后通过yi=ATxi将高维空间中的数据xi投影到低维子空间中。
图嵌入理论[1]为高维空间的低维投影技术提供了一个统一的学习框架。在这个框架中,不同的投影算法可以用同一个数学表达式来表示,式中具有图结构属性的相似度矩阵是区别各种算法的关键所在,不同的学习算法构建反映不同结构特性的图。图嵌入理论就是通过在学习低维投影的过程中保持这些图特性不变,从而达到数据降维的目的。典型的局部保持投影LPP(Locality Preserving Projections)[2]和邻域保持嵌入NPE(Neighborhood Preserving Embedding)[3]算法在图嵌入理论框架下的形式是通过构建反映数据局部邻域结构信息的k邻域图或ε邻域图来学习高维空间的低维投影。但是,k邻域图和ε邻域图存在如下两个缺点:(1)算法效果受邻域参数k和ε的影响很大,目前又没有一种很好的方法用于对邻域参数k和ε的选择进行指导,往往是人们通过经验设定,所以算法在数据类型上的可移植性不强。(2)k邻域图和ε邻域图反映的是数据局部结构信息,这种结构极易受到噪声数据的干扰。
为了克服邻域图存在的缺点,文献[4]提出了用稀疏表示[5]构建稀疏图反映数据的局部结构信息。基于稀疏表示的稀疏图利用除本身数据外的所有样本进行编码,可以自动地为每一个数据选择最优的邻域,通过求解l1优化问题获得邻域关系和相应的连接权值。与传统的基于k近邻或ε近邻数据编码的近邻图不同,稀疏图把这种近邻关系从局部结构拓展到半局部结构,在整个建图过程中不需要人为选择参数,能够很好地描述数据集的局部结构关系。可是稀疏表示是独立地对每个样本点进行稀疏编码,在稀疏图的构建中缺少全局约束,不能反映数据的全局结构特性,当数据点存在较大噪声干扰时,将稀疏图用于图嵌入理论框架中学习的投影表现性能不佳。数据的全局信息不仅对揭示数据属性具有一定的鲁棒性,而且在分类任务中有一定的积极作用。为了学习数据的全局结构信息,文献[6]采用低秩表示[7]构建了一种能够反映数据结构特性的低秩图用于图像的半监督学习任务中。低秩图是在全局低秩约束下对数据进行联合线性表示获得的,可以很好地揭示数据的全局结构,还能够反映出相同类别数据之间的近似关系,具有一定的鉴别能力。
基于上述描述,我们提出利用权值融合方法将数据的稀疏图和低秩图进行加权线性组合,构建一种能够同时揭示数据局部结构信息和全局结构信息、且具有一定鉴别能力的低秩稀疏图,代替原始LPP算法和NPE算法中的邻域图,完成高维数据的低维子空间学习任务。由于低秩稀疏图中既利用稀疏图描述数据集局部结构也利用了低秩图描述数据集的全局结构关系,因此在投影过程中将这些数据特性进行保持,学习出的子空间将更加准确地表示高维数据。
2 低秩稀疏图
假设有高维图像数据集X=[x1,x2,…,xn],其中xi表示一张被排成列向量的图像数据点。先利用数据集X构建一个无向图G=(V,E)和对应的权值矩阵W={wij},这里V={vi}是节点集,每一个vi对应于数据集中的一个xi,E={eij}是一个连接边界集,每一条边界eij对应于数据点xi与xj之间的权值wij。由于节点集V是给定的,所以构建数据图结构就只需要学习数据间的连接权值矩阵W。邻域图通过利用数据与k邻域中的数据点间的欧氏距离来决定数据之间的连接权值。在压缩感知领域中,认为数据点可以由其他相应的 数 据 对其进 行 线 性 重 构 表示,即 xi=。由 于 这 样的 线 性 组合 有 多 种可 能性,因此需要引入一定的条件进行约束,得到最优的线性组合系数,这些系数也能够反映数据点间的连接权值关系。本节将分别介绍在稀疏和低秩条件约束下,求解数据的连接权值 wij,构建数据的稀疏图和低秩图。然后介绍如何通过这两种组合系数构建反映数据全局结构信息和局部信息的低秩稀疏图。
2.1 稀疏图
数据集X=[x1,x2,…,xn]∈Rm×n来自k个独立的子空间,且k≪n,基于来自同一子空间的样本点具有相同属性这一假设可知,来自同一子空间的数据间具有较高的相似性;来自不同子空间数据之间的相似性较弱,在重构表示过程中发挥的作用不大。为此,样本点的线性重构表示系数具有稀疏特性,所以在线性重构表示的基础上对表示系数引入稀疏性约束,通过求解如下的优化问题构建数据的连接权值:
其中,αi是稀疏权值向量,αij表示 样本点xj对样本点xi的稀疏表示权值。式(1)是一个非凸优化问题,在压缩感知中往往用l1范数代替l0将其转化为一个存在最优解的凸优化问题。考虑到实际运用中数据往往存在一定的噪声干扰,为此将式(1)中的等式约束松弛为如下的形式:
其中,ε是一个给定的正数公差。利用式(2)对数据集中的每一个样本点进行线性重构,得到n个稀疏权值向量,组成稀疏表示系数矩阵α。稀疏表示的详细介绍和求解可以参考文献[8]。由于数据图结构中的连接权值矩阵满足对称性,因此在得到数据的稀疏表示系数之后通过式(3)使稀疏图连接权矩阵WSR满足对称性。
2.2 低秩图
低秩表示的目的是寻求数据集中每一个独立的数据向量作为数据集中所有数据向量的线性组合表示,同时这种线性组合系数满足低秩性特性。通过求解如下的优化问题得到数据的低秩表示系数,用来组成低秩图中的连接权值矩阵W:
其中,X同稀疏表示中定义的X一样,Z=[z1,z2,…,zn]是线性组合表示系数矩阵,zi代表xi在所有数据集下的线性表示系数。上式中最优解Z*称之为数据X的低秩表示系数。式(4)同样是一个非凸优化问题,很难得到最优解,在凸优化理论中可以用矩阵的核范数*代替矩阵的秩,使得优化问题存在最优解。因此,问题(4)可以变成如下的凸优化问题:
构造上述优化问题的增广拉格朗日函数:
采用交替迭代更新策略对上式中的每一个参数进行更新,更新其中的一个参数时,保持其他所有参数不变,直到满足停止迭代的条件时停止更新。
对参数J进行更新:
对参数Z进行更新:
对参数E进行更新:E*=arg min
Eλ
对拉格朗日乘子Y1、Y2进行更新:
对参数u进行更新:u*=max(ηu),η、为设定数值。
更新步骤中的设定参数值参照文献[7],在对参数J和E更新步骤中的[M]算子和[M]可参考文献[9]中的定义求解。得到数据的低秩表示系数后按低秩图构建的方法构建低秩图。
由于低秩表示得到的低秩表示系数中存在一些非常接近零的数值,这些数值会给图连接带来不必要的错误连接关系,所以通过下式对低秩表示系数进行预处理:
同时,利用式(14)使得连接权值矩阵WLR满足对称性:
2.3 构建低秩稀疏图
基于稀疏表示构建的稀疏图利用较少的连接权值表示数据间的相似度关系,能够揭示数据的局部结构信息,同时还体现出数据在高维空间中重构系数的稀疏特性。基于低秩表示构建的低秩图反映了数据联合线性表示的组合系数,利用这种系数代表低秩图中的连接权值,具有揭示数据全局结构信息的能力和一定的数据鉴别能力。为了可以在数据的一个图中同时揭示数据的局部结构信息和全局结构信息,同时图结构还具有一定的鉴别能力,我们对低秩图和稀疏图进行权值组合构建一个新的图,称之为低秩稀疏图。在对稀疏图和低秩图进行组合前分别对其进行归一化处理,对权值矩阵W中的每一列进行w'i=wi/max(wi)操作。低秩稀疏图连接权矩阵WLRS的构建表达式如下:
其中,β是平衡参数,取值范围在0~1,权衡低秩稀疏图中揭示数据局部结构特性和全局结构特性的比重。通过式(15)可以发现,当β为0时WLRS图只反映数据的全局结构信息,等同于数据的低秩图;当β为1时WLRS图只反映数据的局部结构信息,等同于数据的稀疏图。
求解低秩稀疏图时,首先利用同伦方法[10]求解凸优化函数(2)得到数据集中数据样本xi(1≤i≤n)的稀疏表示系数αi,将n个数据的稀疏表示系数向量组成稀疏表示系数矩阵α=[α1,α2,…,αn],然后通过式(3)求解数据的稀疏图。对于低秩图中的连接权值,我们采用非精确的增广拉格朗日方法求解优化问题(6)。最后,根据式(14)构建低秩稀疏图。低秩稀疏图的求解步骤见算法1。
算法1 低秩稀疏图的构建
输入:高维数据集X,参数β;
输出:数据的低秩稀疏图。
步骤1 归一化数据集X;
步骤2 求解优化问题(2),通过式(3)求解稀疏权值矩阵WSR;
步骤3 求解优化问题(6),根据式(14)求解低秩权值矩阵WLR;
步骤4 对稀疏权值矩阵和低秩权值矩阵进行归一化处理;
步骤5 通过式(15)构建低秩稀疏权值矩阵WLRS,得到数据的低秩稀疏图。
3 基于低秩稀疏图的结构保持投影
在高维图像识别任务中,假设存在一些来自C个类别、带有类别标签信息的训练图像 {xi,li},xi∈RM代表 一 张 被 表 示为列 向 量 的 二 维 图像,li∈{1,…,C} 表示图像xi的类别信息。稀疏低秩特性保持的目标是寻求一映射矩阵A,通过线性投影yi=ATxi将高维空间M中的数据用低维空间D(D≪M)表示,同时在低维空间D中保持数据在高维空间中所具有的稀疏低秩特性。LPP算法和NPE算法都是基于数据邻域图的投影算法,目的是在数据投影的过程中保持空间邻域中数据点间结构关系不变。算法有三个步骤:(1)构建k邻域或ε邻域;(2)计算邻域数据间的距离度量;(3)计算特征映射。在图嵌入理论框架下,算法的前两步被视为揭示数据结构特性的求解过程,目的是得到反映数据某种特性的图。第(3)步是通过在投影的过程中保持图所揭示的数据特性不变,完成数据降维的目的。
本节将介绍同时保持数据局部和全局特性的两种方法,利用上节的数据低秩稀疏图代替算法LPP和NPE中的邻域图,分别构建低秩稀疏保持投影LRSPP(Low Rank Sparse Preserving Projections)和低秩稀疏保持嵌入LRSPE(Low Rank Sparse Preserving Embedding)。算法的主要步骤流程如图1所示。
低秩稀疏保持投影LRSPP算法通过利用上一节中介绍的低秩稀疏图代替LPP算法中的邻域图,使得数据的全局和局部特性在进行特征提取的过程中得到保持。LRSPP中特征投影的步骤类似于LPP的方法,都是求解如下广义特征向量问题的特征向量和特征值:
其中,D是一个对角矩阵,每一个对角项是低秩稀疏图的连接权值矩阵WLRS中对应列所有项的总和,Dii=∑jWji。L=D—W是拉普拉斯矩阵,X为图像训练集,X矩阵的第i列是一张图像xi。求解式(16)得到P个特征值λi,i∈{1,…,P},和相应的特征列向量ai,i∈{1,…,P},根据特征值大小升序排列,选择前d个特征值对应的特征向量组成映射矩阵A=[a1,a2,…,ad],线性投影如下,式中yi表示数据点xi在d维空间中的表示。
Figure 1 Framework of the proposed algorithm图1 基于低秩稀疏图投影算法步骤
低秩稀疏保持嵌入(LRSPE)改进思路类似于LRSPP算法,通过利用上一节中介绍的低秩稀疏图代替NPE算法中的邻域图,使得数据低秩稀疏特性在进行图嵌入的过程中得到保持。通过求解下面广义特征向量问题完成图嵌入的过程:
其中,M=(I—W)T(I—W),I=diag(1,…,1),M是对称的半正定矩阵,W为低秩稀疏图中的连接权值矩阵WLRS。X为图像训练集,X矩阵的第i列是一张图像xi。特征列向量ai,i∈{1,…,P},是式(18)的特征值λi,i∈{1,…,P},对应的特征向量,将特征值按升序排列,选择前d个特征值对应的特征向量组成嵌入转换矩阵A=[a1,a2,…,ad],低秩稀疏特性嵌入如式(17)所示,式中yi表示数据点xi在d维空间中的表示。
4 实验与结果分析
在数字图像识别任务中,学习高维数据的低维子空间是一个重要的步骤,该步骤可以极大地降低图像的数据维数,增强后续分类器识别的能力和速度。本文将基于低秩稀疏图提出的LRSPP算法和LRSPE算法用于数字图像识别任务中的降维步骤,同基于邻域图的OLPP算法、NPE算法和基于稀疏图的SPE算法、OSPP算法进行比较,分析图在数字图像分类中的有效性。实验中图像的分类使用最近邻分类器完成。
4.1 实验数据集
实验中,用了三个标准的人脸图像数据集和一个手写体图像数据集进行算法性能的比较。实验中用到的所有数字图像尺寸都被调整为32×32像素大小,因此在图像空间中,每一张图像看成为1 024维的数据向量。
ORL人脸数据库包含了40个类别的人脸数据,每个类别含有10幅在不同条件下获取的人脸图像。每幅图像的脸部表情和外部特征都各不相同,这些图像之间存在不同程度的倾斜,角度偏移量在20°以内。在每个类别中随机选取5幅图像共200幅图像作为实验训练集,剩下的为测试集。
Yale人脸库包含15个类别共165幅人脸图像,每个类别有11幅图片,主要在脸部表情上存在较大的变化,另外采集图像的光照条件也存在微小的差异。实验中,在每类中随机选取6幅图像共90幅图像作为训练集,其余则为实验中的测试集。
PIE人脸数据集中收集了68个人的41 368幅人脸数据,包含每个人在不同光照、表情和姿态条件下的数据,来自卡内基梅隆人脸表情数据库。在本文的实验中,保持人脸的表情和姿态条件不变,选取其中20个类别,每类别的21幅不同光照下的人脸数据组成实验数据集。实验中随机选取每个类别的3幅图像作为训练集,其余为测试集。
MNIST数据集包含0~9十个数字的手写体图像,其中在训练集中有6 000幅手写体图像,测试集中包含1 000幅手写体图像。在实验中我们在每个数字的手写体图像中选取10幅共100幅图像作为训练集,用同样方法寻求100幅作为测试集。
4.2 算法结果分析
由于LRSPP算法和LRSPE算法分别是在LPP和NPE算法上改进提出的。因此,实验中,在不同图像数据集上,分别将LRSPP算法与LPP算法、LRSPE算法与NPE算法进行分类实验的比较,同时还引入了SPE算法和SPP算法进行比较。NPE算法和LPP算法中的邻域参数K设置为5,LRSPP算法和LRSPE算法中衡量低秩稀疏特性参数β设置为0.5。因为正则化可以提高算法的表现,在LPP和SPP算法进行实验时采用其正则化版本OLPP和OSPP算法。表1中显示的是不同算法在几个图像数据集上取得的最佳识别率和相应的子空间维数,括号中给出的是取得最佳识别效果的子空间维数。
从结果中可以看出:(1)在四个数据集上,相比于保持数据局部邻域距离结构的OLPP、OSPP算法,利用投影技术保持数据局部和全局结构特性的LRSPP算法取得了更好的分类表现;同样,相比于保持数据局部邻域结构重构关系的NPE、SPE算法,利用投影技术保持数据局部和全局结构特性的LRSPE算法也获得了更优的表现。这表明了所提算法的有效性。在LPP和NPE算法中,分类性能和邻域参数K的正确选择有关,目前还不存在较好的方法对邻域参数进行优化选择,往往是人为设定的,这使得算法的稳定性不高。而在本文提出的LRSPP和LRSPE算法中,反映数据局部和全局结构特性的连接权值矩阵WLRS不存在类似参数优化选择的问题。(2)同NPE、SPE算法和OLPP、OSPP算法比较,本文的LRSPP和LRSPE算法取得最佳识别效果所需的子空间维数更低。在PIE数据集上LRSPP算法仅仅只需要11维。在流形学习理论中,研究者发现人脸图像分布在嵌入于高维空间中的低维流形上,本征维数只有9维。这表明本文学习得到的能够同时揭示数据局部和全局结构信息的低秩稀疏图相比于仅仅揭示数据局部结构信息的邻域图对图像分类具有更好的帮助。(3)从实验结果中发现,在PIE数据集上取得的识别率较好,导致这一现象的原因是我们实验选择的人脸数据主要在光照强弱上存在变化,数据集的低秩特性良好,且分布的流形结构紧密,几种算法能够在降维的过程中很好地保持这些特性,使得分类效果较理想。
Table 1 The maximal recognition rates of NPE,SPE,LRSPE,OLPP,OSPP and LRSPP,and the corresponding dimensions表1 几种算法的最大识别率和相应的维数 %
图2显示了几种算法在 ORL人脸库和MNIST手写体数字库上不同维数子空间下的分类结果。在ORL数据集上的实验表明,LRSPP算法在不同的维数子空间下都取得了较OLPP和OSPP算法更好的效果;LRSPE算法在不同的维数子空间下也同样取得了较NPE和SPE算法更好的识别效果。但是,在MNIST数据集上的实验中,在某些维数子空间中,LRSPE算法稍稍低于NPE和SPE算法的分类效果。这是因为LRSPP 和LRSPE算法的思路是利用低秩性和稀疏性约束揭示数据的全局结构信息和局部结构信息在投影过程中保持不变,而MNIST数据集是手写体数字数据,由于不同的人具有不同的手写风格,使得手写图像的低秩性不是非常强,低秩模型揭示的全局结构信息不是很强。ORL是人脸数据集,人脸图像仅在光照和姿态上发生较小的改变,所以低秩性很好,能够较全面地揭示数据的全局结构信息,因此LRSPP和LRSPE算法较传统几种算法取得的效果更加明显。
Figure 2 Recognition rates of different algorithms in subspace with different numbers of dimensionality图2 几种算法在不同维数子空间中的识别率
在本文提出的算法中存在一个权衡数据低秩特性和稀疏特性的平衡参数β,我们在0~1的范围内人为地选取不同的数值设定为参数β的值,使得低秩稀疏图揭示的全局结构信息和局部结构信息的比重不同,观察参数β对识别结果的影响。当参数为0时,数据低秩稀疏图只反映数据的全局结构信息;当参数为1时,数据低秩稀疏图仅揭示数据的局部结构信息。图3显示的是参数β取不同值时的最佳识别率。从结果中发现,在 ORL和Yale数据集上,当β=0.3~0.5,低秩稀疏图中同时含有数据的局部特性和全局特性的情况下,识别效果较好;在 MNIST数据集上的结果显示,当β 为1时,取得的识别效果最好,这是因为MNIST数据集中包含的手写数字0~9,数字书写的角度和形式变化多样,数据集本身的低秩特性不强。
5 结束语
本文提出了在数据进行投影和嵌入的过程中将数据的局部结构特性和全局结构特性同时进行保持。在图嵌入理论框架的思想下,首先基于低秩表示和稀疏表示构建能够同时反映数据局部结构特性和全局结构特性的低秩稀疏图;然后分别利用LPP算法中的投影技术和NPE算法中的嵌入技术来保证数据的这些特性在降维过程中保持不变,从而提出了LRSPP算法和LRSPE算法。在实验中,同传统的特征提取算法LPP和NPE进行比较,将LRSPP算法和LRSPE算法用于图像分类识别任务中的特征提取步骤,利用获得的分类识别率高低来评价算法的有效性。实验结果显示,提出的算法较传统的方法取得了更理想的实验效果,表明了低秩稀疏图在图像分类中的有效性,较传统的邻域图也更具有优越性。但是,本文方法是对数据的低秩和稀疏特性分别通过低秩和稀疏模型进行揭示的,与流形学习中传统的构图方法比较,本文在构图过程中增加了求解低秩稀疏模型的工作,但庆幸的是整个构图过程可以离线进行。当然,如何提高求解低秩稀疏模型效率以降低构图的计算量,这是本文未来需要继续讨论的话题。
Figure 3 Impact of parameterβon experimental results图3 参数β对实验结果的影响
[1] Yan S,Xu D,Zhang B,et al.Graph embedding and extensions:A general framework for dimensionality reduction[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.
[2] Niyogi X.Locality preserving projections[C]∥Neural Information Processing Systems,2004:153.
[3] He X,Cai D,Yan S,et al.Neighborhood preserving embedding[C]∥Proc of the 10th IEEE International Conference on Computer Vision(ICCV 2005),2005:1208-1213.
[4] Cheng B,Yang J,Yan S,et al.Learning with l1-graph for image analysis[J].IEEE Transactions on Image Processing,2010,19(4):858-866.
[5] Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2):210-227.
[6] Zhuang L,Gao H,Huang J,et al.Semi-supervised classification via low rank graph[C]∥Proc of the 6th International Conference on Image and Graphics(ICIG),2011:511-516.
[7] Liu G,Lin Z,Yu Y.Robust subspace segmentation by low rank representation[C]∥Proc of the 27th International Conference on Machine Learning(ICML-10),2010:663-670.
[8] Bruckstein A M,Donoho D L,Elad M.From sparse solutions of systems of equations to sparse modeling of signals and images[J].SIAM Review,2009,51(1):34-81.
[9] Liu G,Lin Z,Yan S,et al.Robust recovery of subspace structures by low-rank representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35 (1):171-184.
[10] Donoho D L,Tsaig Y.Fast solution of l1-norm minimization problems when the solution may be sparse[J].IEEE Transactions on Information Theory,2008,54(11):4789-4812.
杨国亮(1973),男,江西丰城人,博士,副教授,研究方向为智能控制、图像处理与模式识别。E-mail:ygliang30@126. com
YANG Guo-liang,born in 1973,PhD, associate professor,his research interests include intelligent controls,image processing,and pattern recognition.
Structure preserving projection algorithm based on low rank and sparse graph
YANG Guo-liang,LUO Lu,FENG Yi-qin,LIANG Li-ming
(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology,Ganzhou 341000,China)
In the unifying frameworks like graph embedding,constructing a good graph to represent data properties is critical for dimensionality reduction technology.In this paper,we construct a low rank and sparse graph to reveal local and global structure information of the data based on sparse representation and low rank representation.We first use graph embedding technology to preserve such properties during the linear projections,and then obtain the low-dimensional embedding of the original high-dimensional data.The effectiveness of the proposed method is compared with the state-of-the-art algorithms and is verified on face and handwritten digit databases(ORL,Yale,PIE,MNIST).
graph embedding;sparse representation;low rank representation;low rank and sparse graph;linear projections
TP391.4
A
10.3969/j.issn.1007-130X.2015.08.025
1007-130X(2015)08-1584-07
2014-08-11;
2014-11-11
国家自然科学基金资助项目(51365017,61305019);江西省科技厅青年科学基金资助项目(20132bab211032)
通信地址:341000江西省赣州市红旗大道86号江西理工大学电气工程与自动化学院
Address:School of Electrical Engineering and Automation,Jiangxi University of Science and Technology,86 Hongqi Avenue,Ganzhou
341000,Jiangxi,P.R.China