一种基于局部和判别特性的降维算法

减小字体 增大字体 作者:张国印 楼宋江 王庆军 程慧杰  来源:www.zhonghualunwen.com  发布时间:2009-10-12 23:37:32

  0 引言
  
  在生物特征识别系统中,人脸识别由于具有成本较低、不侵犯使用者的隐私权、应用前景广阔等特点,受到了极大的关注,是当前模式识别、图像处理和计算机视觉等学科非常活跃的研究热点[1]之一。
  正是因为人脸识别的这些特点,在过去的几年时间里,出现了很多人脸识别算法。其中,基于子空间的算法起到了主导作用,最著名的是主成分分析[2](principal component analysis)和线性判别分析[3](linear discriminant analysis)。主成分分析算法的主要思想是通过估计数据的二阶统计性质来发现数据的本征线性维数,它是在全局最小重构误差的条件下把高维观察数据投影到低维空间上,通过求解数据点协方差矩阵的最大几个特征值所对应的特征向量张成的子空间而得到。线性判别分析算法就是求出一个线性子空间,使得所有样本在这个子空间中,类内样本散度最小,类间样本的散度最大,用它降维后的低维嵌入坐标非常有利于进行样本的分类。
  上述两种方法是线性算法,但人脸空间更可能存在于非线性子空间中。最近相关人员提出了几种流形学习算法,主要用于非线性降维,如等距映射(ISOMAP)[4]、局部线性嵌入算法(LLE)[5]、拉普拉斯特征映射(LE)[6]等。但是它们都不能解决out of sample问题,即不能直接映射新数据,因此不能直接用于人脸识别。基于以上问题,He等人[7]提出了一种线性算法LPP,该算法是拉普拉斯特征映射的线性版本,能保持数据集的局部邻近关系,又能较容易地映射新样本。
  LPP虽然能保持数据的局部结构,但是没有利用数据集的类别信息,从而不利于分类问题。本文基于LPP和LDA的优点,既考虑LPP的局部保持特性,同时又利用LDA的易于分类问题这一特点,提出了一种基于局部特性和判别特性的降维算法。
  
  1 基于局部特性和判别特性降维算法
  
  1.1 LPP简介
  LPP目标是保持数据之间的相似性,即原始空间上相邻的数据点在投影空间上也保持相应的邻近关系。假定数据集X={x1,x2,…,xn}含有n个样本点,每个样本点xi属于D维欧式空间,即xi∈RD,且样本数据来自一本征维数为d(d<  Wopt=argminW∑ij(yi-yj)2Sij=argminW∑ij(W Txi-W Txj)2Sij=argminW WTXLXTW(1)
  其中:Sij刻画了两数据xi、xj之间的相似性。
  Sij=exp(-xi-xj2)/txi,xj为邻近点0其他
  附加约束条件W TXDX TW=1,拉普拉斯算子L=D-S。其中:D为对角矩阵,其元素为对称矩阵S的列向量(或行向量)元素之和,即Dij=∑jSij。最后可以通过以下特征方程求解:
  XLXTw=λXDXTw(2)
  假定w0,w1,…,wd-1为特征方程式(2)的d个解,它们所对应的特征值分别为λ0,λ1,…,λd-1,那么可以得到如下映射:xi→yi=W Txi。其中:yi为d维向量;W为变换矩阵。
  1.2 LDA简介
  对于分类问题,希望能找到某个投影方向,使得不同类的数据在投影后能尽量分开。LDA算法就是找到这样一投影方向,使得数据在低维空间中同类数据尽量靠近,不同类数据尽量分离,从而保留丰富的辨别信息,使数据具有最大的可分性。
  给定分别属于J类的n个数据样本X={x1,x2,…,xn},Cj表示第j类元素构成的集合,nj表示属于第j类元素的个数,μj=(1/n)j∑xi∈Cjxi表示第j类的均值,μ表示样本的总体均值。
  令Sb、Sw分别为类间散度矩阵和类内散度矩阵,即
  Sb=(1/n)∑Ji=1ni(μi-μ)(μi-μ)T(3)
  Sw=(1/n)∑Jj=1∑xi∈Cj(xi-μj)(xi-μj)T(4)
  问题归结为求以下特征方程:
  Sbw=λSww(5)
  设w1,w2,…,wd是对应于矩阵Sw-1Sb的前d个最大特征值的特征向量,则令W=[w1,w2,…,wd],投影后的数据为yi=WTxi,i∈n。
     1.3 基于局部和判别特性的降维算法
  基于以上的简单介绍可以看出LPP能有效降低数据维数,并能保持数据间的邻近关系,LDA能找到一投影,使得投影后的数据更加有利于分类。本节将LPP和LDA的这两个特性结合起来,形成既保持数据点之间的关系又有利于分类的新颖降维算法。
  找到一投影,使得目标函数W T(Sw+σXLX T)W/(WTSbW)最小(Sw、Sb、L定义同上),并受到一限制条件WTXDXTW=1。所以问题最后归结为以下优化问题:
  Wopt=argminW W T(Sw+σXLX T)W/(W TSbW))s.t. W  TXDX TW=1(6)
  这里假设Sb可逆,即假设Sb非奇异,则该优化问题可以简化成
  Wopt=argminW W TSb-1(Sw+σXLXT)Ws.t.W TXDXTW=1(7)
  通过Lagrange乘数法,令
  L(W)=W TSb-1(Sw+σXLX T)W-λ(W TXDX TW-1)(8)
  对W求偏导,得到
  L(W)/W=2Sb-1(Sw+σXLXT)W-2λXDXTW(9)
  令L(W)/W=0,即
  Sb-1(Sw+σXLXT)W-λXDXTW=0(10)
  最后求解以下广义特征方程
  Sb-1(Sw+σXLXT)w=λXDXTw(11)

[1] [2]  下一页

Tags:

作者:张国印 楼宋江 王庆军 程慧杰
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论