2022年2022年流形学习算法分析及在人脸数据库上的应用 .pdf

25卷 第9期2008年9月微 电 子 学 与 计 算 机M ICROEL ECTRON ICS & COMPU TERVol. 25No. 9September 2008收稿日期: 2008 - 03 - 13基金项目:国家自然科学基金资助项目(60435010 ) ;河北省教育厅科研计划项目(Z2006303 ) ;东北大学“985工程”项目流形学习算法分析及在人脸数据库上的应用宋 欣1,王 娟1,张 斌1,叶世伟2(1东北大学秦皇岛分校计算中心,河北 秦皇岛066004 ; 2中国科学院研究生院信息科学与工程学院,北京100049 )摘 要:为了更高效的处理高维数、 高复杂性的非线性数据,发现其嵌入在源数据空间中的本维特征,提出了基于局部光滑逼近思想的流形学习算法,通过局部线性误差逼近最小化,实现将高维数据映射到低维空间.在FREY人脸数据库上进行降维实验,证明了该方法的可行性和有效性.关键词:流形学习;局部光滑逼近;维数约简;人脸图像处理中图分类号: TP181 文献标识码: A 文章编号: 1000 - 7180 (2008)09 - 0091 - 04ManifoldLearningAlgorithmAnalysis andApplicationin Face DatabaseSONG Xin1 ,2, WAN GJuan1, ZHAN G Bin1, YE Shi2wei2(1 Computer Center , NortheasternUniversityat Qinhuangdao , Hebei Qinhuangdao 066004 , China ; 2 School ofInformation Scienceand Engineering, the Graduate Schoolof the ChineseAcademy of Sciences , Beijing 100049 , China)Abstract : In order to process the nonlinear data withhigh - dimensional and high complexityefficiently, and found the di2mensional characteristicembedded in the source data s pace , the manifold learning algorithmbasedon Locallysmooth ap2proximatingwas proposed on the basis of the analysis of the typical manifoldlearning algorithm.The dimensionalityre2duction of the high - dimensional nonlinear data is achieved by locally linear error approximatingminimum.Through theexperiments on dimensionalityreduction in the FREY face database , the results show that the feasibility and effectivenessof manifold learning method applying to face image data processing.Key words : manifoldlearning ; Locallysmooth approximating; dimensionalityreduction ; face image processing1引言计算机信息处理中要面对大量高维数、 高复杂度的数据 ,数据之间也存在着大量的冗余的线性或者是非线性相关,如何对这些海量数据进行有效的挖掘处理 ,成为当今计算机技术研究领域广泛关注的热点问题 .文中在详细分析了典型的流形学习算法的原理基础上,提出了基于流形学习思想的局部光滑逼近的数据降维算法,在人工数据集上实验证明了其有效性后,进一步将流形学习算法应用到FREY 人脸数据库上进行测试分析,比较各算法在人脸数据集上的降维效果,说明流形学习算法应用于人脸图像这样高维数、 高复杂性的非线性数据处理问题上的可行性.2 典型流形学习算法分析2. 1流形与流形学习流形1是拓扑学中的概念,可以定义为:设M是一个豪斯多夫拓扑空间,若对每一点PM ,都有P的一个开领域U和Rn的一个开子集同胚,则称M为n维拓扑流形,简称为n维流形.流形学习方法其主要目标是发现嵌入在高维数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 据空间的低维光滑流形.设Yd.数据集 yi是随机生成的,且经过f映射为观察空间的数据 xi= f ( yi) ,流形学习就是在给定观察样本集 xi的条件下重构f和 yi.2. 2 等距映射算法等距映射算法(Isometric Mapping , Isomap)核心是估计两点间的测地距离223,力求样本在从高维空间降到低维空间的过程中能得到最大程度上的重构和恢复.算法的实现步骤为: (1)设输入空间X中所有数据点xi处于相对光滑的流形M中, i =1,2, N ,根据这些数据点的邻接关系构建加权无向邻接图G ,邻接关系定义为样本点的邻接点处于固定的 邻域内或选取样本点的K个近邻,邻接点的权重为样本点之间的欧式距离dx( i , j ) . (2)估计流形M上两点之间的测地线距离,根据图G上两点的最短 路 径 作为 近 似 估 计,得 到 距 离 矩 阵DG= dG( i , j) . (3)应用 MDS 算法构造低维嵌入Y ,对于最短距离矩阵DG= dG( i , j ) 有计算代价函数E = ( DG)-( DY)L2, DY= dY( i , j)=yi-yj ,令S =(Sij)=(D2ij), H =(Hij)=(ij-1/ N ) ,推导出( D)= -HSH/2,则低维嵌入是( D)的第 2小到第d +1小的特征值所对应的特征向量.2. 3 局部线性嵌入算法局 部 线 性 嵌 入 (LocallyLinearEmbedding ,LL E)4 处理的源数据大多数是非线性数据,如果在源数据点稠密分布的情况下,可以将源数据空间采样点邻域内的点近似的分布于一个超平面上. 算法首先要求设D维空间中有N个数据属于同一流形,记做: Xi=( xi1, xi2,. . . , xiD) , i(1,2, N ) .假设有足够的数据点,并且认为空间中的每一个数据点可以用它的K个近邻线性表示.求近邻点,一般采用K近邻或者 邻域.接着计算权值Wij,代价函数为: E( W)=ni =1|Xi-kj =1WijXij| .由于权值体现了数据间内在的几何关系,所以L L E算法中权值要满足两个约束条件: (1)要求每一个数据点Xi都只能由它的邻近点来表示,若Xj不是近邻点,则Wij=0; (2)要求权值矩阵的每一行的和为 1.最后算法保持权值Wij不变,求Xi在低维空间的象Yi,使得低维重构误差最小.2.4 拉普拉斯特征映射拉普拉斯特征映射(Laplacian Eigenmaps)算法首先根据采样点的k个近邻关系或根据采样点的邻域的方法构建一带权图G( V , E) ,其中V表示选择采样点的集合, E表示两点如果是邻近点则在两点间有一条边相连,为讨论方便,假定图是连通的.那么,就需要对这个邻接图中的每条边赋予权值Wij,规定如果两个点是邻近点则Wij=1,否则Wij=0.考虑带权邻接图映射到低维空间时使得相连的点之间距离尽可能的离得近,所以先假设该映射为y = ( y1, y2, yn)T,如果要确保采样点Xi与Xj是邻近点,也就是使得其映射Yi和Yj的距离尽可能的小,所以对于任意的Y,可以最小化经过局部均化的目标函数:12i , j(yi-yj)2wij=yTL y令D为对角矩阵, Dii=jwij, L=D -W为Laplacian 矩阵,所以就可以计算图拉普拉斯算子的广义特征向量,求得低维嵌入.2. 5 Hessian特征映射Hessian特征映射( Hessian Eigenmaps)5 试图恢复出局部等距于低维欧氏空间中开连通子集的流形的生成坐标 .假设MRm是一个光滑的流形, Tx( M )是流形中每个点xM处的切空间.将Tx( M)考虑成Rm中的一个仿射子空间,且由于xM而有 0 Tx(M).记Nx为x的邻域,则对每个点xNx有Tx( M)上的唯一的逼近点yTx( M)且映射xy是光滑的.很显然,这些点的坐标可以通过选择Tx( M )的正交基来获得.这样,可以得到x的邻域Nx的局部坐标,记为(x)1,(x)d,需要注意的是这些局部坐标依赖于切空间Tx( M )中正交基的选取.HLL E用这些局部坐标来定义函数f : MR在x处的海赛矩阵.用g()= f ( x)定义函数g : UR ,其中表示xNx的局部坐标, U是Rd上0的邻域.由于映射x是光滑的,可以定义f在点x的海赛矩阵:( Htanf( x) )ij=55i55jg() |=0式中 tan 表示这样的海赛矩阵的建立依赖于切空间Tx( M) .简单说来,在每个点x处,HLL E采用切空间中的坐标和f在这样的坐标系统下的导数来建立海赛矩阵.需要特别强调的是,海赛矩阵依赖于切空间Tx( M )中坐标系统的选取.29微电子学与计算机2008年名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 定义H ( f )=MHtanf( x)2Fdx ,其中dx代表了M上的概率测度,那么H ( f )就表示f在流形M上的平均弯曲度. H(f)的d +1维零空间由一个常函数和等距坐标函数张成的d维空间组成.对于H ( f )的一个适当的基,都可以恢复其参数空间.Hessian特征映射要求估计局部邻域内的二阶导,而这对于高维数据样本来说是非常困难的6.3局部光滑逼近的流形学习方法局部光滑逼近(Locally smooth Approximating,L SA) 算法在处理过程中使局部线性误差逼近最小化 ,使得低维嵌入空间数据点的延伸方向与源流形基本相同 ,达到良好的降维效果. 算法的具体原理:如果记Ni表示xi的邻域的下标,记Nij=1, jNi, gi为梯度,对于每一点xi的邻域的下标为j1,j2, ji,定义下列矩阵:Ui= xj1-xi, xj2-xi, xji-xi ,U = U1, U2, Un21 ,Di=diag Nij1, Nij2, Niji ,Yi= yj1-yi, yj2-yi, yji-yiT,令Ci=?I + UiDiUTi, Bi= UiDi,最小化的能量方程为:E =12ni =1 YTiDiYi-2gTiUiDiYi+gTiUiDiUTigi +2ni =1gTigi式中,对每一个固定的i求gi的最小化,可写为:ni =1gi2=ni =1 YTi(?I + UTiUiDi)-1DiYi-?YTi(?I + DiUTiUi)-2DiYi =YTB Y/2同时能量方程经过矩阵代换推导可写成:E =2ni =1YTi(?I + DiUTiUi)-1DiYi若 比较小,那么最小化ni =1gi2和最小化E应该是差不多的.E =(ni =1gi2) /2+ (2/2)ni =1YTi(?I +DiUTiUi)-2DiYi=YTA Y/2因此,最小化E就是求A的最小特征值对应的特征向量.显然y = (1,1,1)T特征值为 0对应的特征向量,应该被删除.所以最后的低维嵌入就是求得A最小的第 2 个到第d +1 个最小特征值对应的特征向量.4 实验测试结果分析为测试 L SA 方法在高维数据降维处理的有效性 ,选取 S曲线作为源数据集,取近邻点数K =8,采样 1500 个数据点时的实验结果如图1所示 .图1局部光滑逼近方法在S曲线采样1500点结果在人脸数据这样的高维的,复杂的信息处理过程中,如能有效提取其主要特征信息,将为进一步的识别 ,比对等处理提高了效率,使后续运算量降低.Laplacian Eigenmaps算法在 FREY 人脸数据库降维结果可参阅文献 7 ,文中分别应用ISOMAP 、LL E、 L SA 方法在 FER Y 人脸数据库上进行测试分析 ,该数据库包含1965 幅在一段视频中截取的同一人的不同表情图像,每幅图片20 28 像素 ,每像素256灰度级,所以,每幅人脸图像为560维灰度图像 .算法选取近邻数K =12,ISOMAP 、 LL E 将其降维到 20 20 大小的范围内,L SA 方法其降维到30 30 大小的范围内. 结果图中红色点表示1965幅人脸图像降维处理后分布情况. 图 2 实验结果显示 Isomap算法在处理人脸数据集时能发现其本征维数 ,将人脸图像按表情和姿态分布到相应位置,图中左边分布笑脸图像,右边分布苦脸图像,图3结果显示人脸数据集中的人脸图像根据相近表情和姿态分布在相近位置,左边分布苦脸图像,右边分布笑脸图像 .图 4 结果显示左下方分布苦脸图像,右边分布笑脸图像 .三种算法体现了其有效性和数据集的本质流形结构 .5 结束语现实中的视频图像序列中的人脸表现为一个连续的运动状态,每种状态之间体现了一种几何结构关系 ,而人脸流形学习的目的就是在人脸图像空间中提取内在的几何结构及其规律性,将高维图像空间降维到低维特征空间,并寻找内在低维结构与高维观测数据间的联系. 在对人脸图像进行非线性降维后,使得类似的人脸图像数据尽量接近,然后就可以通过K均值聚类 ,将聚类中心作为系统的代表性人脸图像 ,用作构建人脸特征库.但对于人脸库中近39第9期宋欣,等:流形学习算法分析及在人脸数据库上的应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 图4应用L SA算法在FREY人脸数据库的降维结果图3应用LL E算法在FREY人脸数据库的降维结果图2应用Isomap算法在FREY人脸数据库的降维结果邻图像数的选取不同,将影响降维效果,如何找到一种具有自适应性近邻选取方法应用于人脸数据库有待进一步的研究和探讨,局部光滑逼近的流形学习方法对于类似于S曲线这种数据集比文献4中提出的 LL E方法更具有鲁棒性,降维后源数据的延展性更好 .参考文献 : 1 Chen Xingshen , Chen Weihuan.Lecturenotes in differen2tiablemanifold M .Beijing :PekingUniversitypress ,1983.2 Tenenbaum J B , Silva de V , Langford J C. A global geo2metricframeworkfornonlineardimensionalityreductionJ .Science, 2000 ,290(12):2319 - 2323. 3 BalasubramanianM , SchwartzE L.The isomap algorithmand topological stability J .Science, 2002 , 295 ( 5552) :7. 4 Sam T , Roweis LawrenceK , Saul. Nonlineardimensional2ityreductionby locallylinearembedding J .Science,2000 ,290 (5500) :2323 - 2326. 5 Donoho D , Grimes C.Hessian eigenmaps: new locally lin2ear embedding techniques forhigh - dimensionaldata J .NationalAcademy of Sciences, 2003 , 100(10): 5591 -5596. 6罗四维,赵连伟.基于谱图理论的流形学习算法J .计算机研究与发展,2006 ,43 (7) :1173 - 1179. 7 Belkin M , Niyogi P. Laplacian eigenmaps for dimensionali2ty reductionand data representation J . NeuralComputa2tion , 2003 (15) :1373 - 1396.作者简介 :宋 欣 女, (1978 - ) ,硕士,讲师.研究方向为数据挖掘、 图像处理 、 智能信息处理.王 娟 女, (1956 - ) ,副教授,研究生导师.研究方向为数据挖掘 、 数据库技术等.张 斌 男, (1980 - ) ,硕士研究生.研究方向为数据挖掘、计算机网络技术等.叶世伟 男, (1968 - ) ,博士,副教授,硕士生导师.研究方向为智能信息处理、 机器学习 、 神经计算 、 认知科学等.49微电子学与计算机2008年名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -