基于核理论的非线性鉴别分析方法的研究

杨旭+业宁+李勇智

摘要：人脸识别是模式识别领域中一个比较热的研究课题。人脸一般是高维数据，我们需要通过对数据降维进行特征提取，就是将原始数据对应的高维空间数据映射到低维空间中，在低维空间中进行线性的鉴别分析。由于实际问题中原始样本的分布通常是非线性的，该文运用核方法，将PCA和FDA进行了非线性推广，比较了核主成分分析（KPCA）和核Fisher判别分析（KFDA）以及核最大间距准则（KMMC）三种非线性特征提取方法。

关键词：特征提取；人脸识别；核主成分分析；核Fisher判别方法；核最大间距准则

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）04-0191-04

A Study on the Nonlinear Discriminant Analysis Method Based on the Kernel Theory

YANG Xu，YE Ning， LI Yong-zhi

（School of Information Science and Technology， Nanjing Forestry University， Nanjing 210037， China）

Abstract ： Face recognition is a hot research topic in the field of pattern recognition. Face is generally high dimensional data， so We need to extract the feature of data dimension reduction . That is to say，we should map the original data to the high dimensional data to the low dimensional space and do the linear discriminant analysis in low dimensional space. Because the distribution of the original sample is usually non-linear in the practical problems， This paper uses kernel method and carries out the PCA and FDA in a nonlinear extension.In addition，it compares the kernel principal component analysis （KPCA） and kernel Fisher discriminant analysis （KFDA） as well as the kernel maximum space criterion （KMMC） for three kinds of nonlinear feature extraction meth ods.

Key words： feature extraction； face recognition； KPCA； KFDA； KMMC

人脸识别是基于人的脸部特征信息而进行的身份识别的一种生物识别技术。在核函数还没被运用到模式识别中之前，一般都采用线性算法在低维空间中进行模式分析。但是往往遇到高维的或者非线性的运算，线性算法就会存在局限性。自从核函数出现后，人们发现了用核方法的模式识别算法可以更好地解决了非线性问题。

1 基于核方法的特征提取

核方法运用到了核映射。人脸的实际的原始数据一般都是高维的，在高维空间里是非线性的。这时就需要用核方法用非线性映射将原始数据由高维空间映射到了低维特征空间上，然后在特征空间中运用线性算法。

定义一个非线性映射：

[ f：x∈Rn→fx∈F] （1）

可得到相应的核函数为：

[ kx，y=fx，fy] （2）

其中[，]表示在特征空间F上的内积运算。

因此，常用的核函数有：

多项式核函数：

[kx，y=ax?y+bd] [d>0]且[a，b∈R] （3）

高斯核函数（径向基核函数）：

[kx，y=e-x-y2∕σ2] [σ∈R] （4）

Sigmoid核函数：

[ kx，y=tanhvx?y+c] [v，c∈R] （5）

2 核主成分分析方法（KPCA）的数学模型

现设有训练集[S：x1，x2，…，xN∈Χ]，核映射[Φ]将它们映射到核空间[F]中，核空间中的训练集为[lx1，lx2，…lxn]。记[Χ=x1，x2，…，xN，lΧ=lx1，lx2，…lxn]。

在核空间中对子空间进行降维变换，即

[y=wTlx] （6）

降维变换又称投影变换，w就是它的投影方向。降维后数据总体的离散度为

[Clt=1Ni=1Nyi-yyi-yT=wT1Ni=1Nlxi-llxi-lT w=wTSl tw] （7）

其中，[l=1Ni=1Nlxi]是核空间中的样本均值。

将核空间中的样本中心化，即令[lxi=lxi-l]，

并记[lX=lx1，lx2，…，lxN] ，则核空间中的总体样本协方差阵为

[Slt=1Ni=1Nlxi-llxi-lT=1Ni=1NlxilxiT=1NlXlXT] （8）

核空间中的PCA的最大准则函数为：

[max JKPCAw=wTSltw ] （9）

由于最大化[JKPCAw]就是对[Slt]作特征值分解，w就是[Slt]的特征向量，因此有

[ λw=Sltw=1Ni=1NlxilxiTw=i=1N1NlxiTwlxi] （10）

令

[w=i=1Nαilxi=lXα] （11）

其中[α=α1，α2，…，αNT]是线性组合系数。

首先将公式（11）代入式（6）中，有

[y=wTlx=αTlxTlx=αTlx-lxENTlx]

[=αTkX，x-ENkX，x] （12）

其中[kX，x=kx1，x，kx2，x，…，kxN，xT]，[EN]为元素[1∕N]的N阶矩阵。

将式（11）代入准则函数式（9）中，并结合式（8），有

[ JKPCAw=wTSltw=1NαTlXTSltlXα=1NαTlXTlX2α=1NαTK2α ] [（13）]

其中

[K=lXTlX=lX-lXENTlX-lXEN]

[=K-ENK-KEN+ENKEN] （14）

K为式（15）定义的核矩阵。对核空间中的总体样本协方差阵[Slt]作特征值分解：

[Sltw=λ∕Nw] （15）

其中N是样本容量。将式（11）代入式（15），并两边同时左乘[lXT]，有

[lXTSltlXα=λ∕NlXTlXα] （16）

根据式（13）和（14），可将式（16）写为

[ K2α=λKα] （17）

简化得：

[Kα=λα] （18）

即最佳组合系数[α]就是矩阵[K]的最大特征值所对应的特征向量。

一般令[wTw=1]。

由于

[wTw=αTlXTlXα=λαTα] （19）

所以组合系数应满足的条件为

[λαTα=1] （20）

其中[λ]是特征向量[α]所对应的特征值。

3 核Fisher判别分析方法（KFDA）的数学模型

训练样本集[x1，x2，…，xN ]经过非线性映射[Φ]后，训练样本为[Φxii=1，…，N]在特征空间[F]上的类间散度矩阵[Sφb]、类内散度矩阵[Sφw]，以及总体散度矩阵[Sφt]为：

[Sφb=i=1CNimφi-mφmφi-mφT] （21）

[ Sφw=i=1Cj=1NiΦxj-mφiΦxj-mφiT] （22）

[ Sφt= Sφw+Sφb=i=1NΦxi-mφΦxi-mφT] （23）

其中[mφi=1Nij=1NiΦxj]为第[Ci]类样本在特征空间[F]上的均值向量，

[mφ=1Nj=1NΦxj]为所有训练样本在特征空间[F]上的均值向量。

特征空间[F]中广义的Fisher判别准则函数为：

[maxJφw=WTSφbWWTSφtW] （24）

要使Fisher判别准则函数最大化，就要要寻找一组最优判别向量[w=w1，w2，…，wd]。

由于[maxJφw]，[w∈F]，因此，[w1，w2，…，wd]即为特征方程[Sφbw=λSφtw ]的前[d]个最大特征值所对应的单位特征向量。

任何一个最优化准则函数式（24）的解向量[w]一定位于特征空间[F]中。所以[w]在训练样本[Φx1]，[Φx2，…，ΦxN]所生成的空间内，即

[w∈spanΦx1，Φx2，…，ΦxN]，则有：

[w=i=1NαiΦxi=Qα] （25）

其中：[Q=Φx1，Φx2，…，ΦxN]，

[α=α1，α2，…，αNT∈RN]

把特征空间[F]中的样本[Φx]投影到[w]上，则有：

[wTΦx=i=1Nαikxi，x=αTkx1，x，…，kxN，xT=αTξX] （26）

其中，[ξx=kx1，x，…，kxN，xT]为核样本向量。[α]为特征空间[F]中最佳判别向量[w]的最佳核判别向量。

把特征空间[F]中的训练样本类均值向量和总体均值向量分别投影到[w]上：

[wTmφi=αT1Nij=1NiΦTx1Φxj，…，ΦTxNΦxjT=αTμi] （27）

[wTmφ=αT1Nj=1NΦTx1Φxj，…，ΦTxNΦxjT=αTμ] （28）

其中：

[μi=1Nij=1NiΦTx1Φxj，…，1Nij=1NiΦTxNΦxjT] （29）

[μ=1Nj=1NΦTx1Φxj，…，1Nj=1NΦTxNΦxjT] （30）

由（27）式和（28）式可得：

[wTSφbw=αTKbα] （31）

[wTSφWw=αTKWα] （32）

[wTSφtw=αTKtα] （33）

其中：

[Kb=Nii=1C μi-μ μi-μT] （34）

[Kw=i=1Cj=1Niξxj-μiξxj-μiT] （35）

[Kt=Kb+Kw=i=1Nξxi-μξxi-μT] （36）

式（34）、（35）、（36）中的[Kb]、[Kw]、[Kt]分别为核类间散度矩阵、核类内散度矩阵、核总体散度矩阵。

将式（31）和式（33）代入式（24）中，可以得到高维特征空间[F]中广义Fisher判别准则函数式为：

[ Jφw=wTSφbwwTSφtw=αTKbααTKtα=Jα] （37）

求出变量[α]的解，即能通过式（25）得到[w]的解。

求解核Fisher判别分析问题变成了求解[Kbα=λKwα]的最大特征值对应的特征向量。

4 核最大间距判别准则（KMMC）的数学模型

设有[C]个模式类，[Xij∈RN]表示原输入空间的第[i]类的第[j]个训练样本。训练样本集为[X=Xjii=1，2，…，C；j=1，2，…，Ni]，[Ni]为第[i]类训练样本的数目，可知[N1+N2+…+NC=N]。经过非线性映射[?]变换后，[?X11，?X12，…，?X1N1，…，?XC1，…，?XCN1]表示高维空间[F]上[N]个训练样本。

设第[i]类均值和总体均值分别为[mi]和[m]，则

[m?i=1Nij=1Ni?Xij]

[m?=1Ni=1Cj=1Ni?Xij] （38）

[S?b]为类间散度矩阵，[S?w]为类内散度矩阵，即

[S?b=i=1CNiNm?i-m?m?i-m?T] （39）

[S?w=1Ni=1Cj=1NiΦXij-m?iΦXij-m?iT] （40）

特征空间[F]上最大间距准则的判别函数为：

[maxJ?w=j=1dwTjS?b-S?wwj] （41）

其中[w=w1，w2，…，wd∈RL×d，wi∈RL]为特征空间内的任意非零向量。我们要基于最大间距准则判别函数最大的情况下，在特征空间[F]上寻找一组最优鉴别向量[w1，w2，…，wd]。式（41）的解向量[w]一定在高维空间[F]中的[N]个训练样本向量[?X1，?X2，…，?XN]所张成的空间内，即

[w∈span?X1，?X2，…，?XN]，则有：

[w=i=1Nai?Xi=Φα] （42）

其中[Φ=?X1，…，?XN]，[α=a1，a2，…，anT∈RN]。

把[?Xik]投影到[w]上，则有

[wTaXik=αTΦTaXik =αT?X1T?Xik，…，?XNT?XikT]

[=αTkX1，Xik，…，kXN，XikT=αTζik] （43）

则[ζik=kX1，Xik，…，kXN，XikT]，则称[ζik]为核样本向量，向量[α=a1，a2，…，anT∈RN]为核鉴别向量。

若把特征空间[F]上的类别均值向量[m?i]和总体均值向量[m?]分别投影到向量[w]上：

[ wTm?i=αT1Nij=1NikX1，Xij，…，kXN，XijT=αTμi] （44）

[ wTm?=αT1Ni=1Cj=1NkkX1，Xij，…，kXN，XijT=αTμ] （45）

其中： [μi=1Nij=1Niζij] ； [μ=1Ni=1Cj=1Niζij]

根据式（44）和（45），可知

[wTS?bw=αTKbα] （46）

[ wTS?ww=αTKwα] （47）

其中：

[Kb=i=1CNiNμi-μμi-μT] （48）

[Kw=1Ni=1Cj=1Niζij-μiζij-μiT] （49）

[Kt=Kb+Kw=1Ni=1CjNiζij-μζij-μT] （50）

由式（46）和（47）可知特征空间[F]上的最大间距准则函数式（41）等价于

[maxJ?w=j=1dwTjS?b-S?wwj]

[=j=1dαTjKb-Kwαj]

[maxJkα=j=1dαTjKb-Kwαj] （51）

称式（51）为核最大间距准则函数。矢量[αi∈RN]称为最优核鉴别向量。特征方程[Kb-KwX=λX]的前[d]个最大特征值所对应的特征向量为最优核鉴别向量[α1，α2，…，αd]。

5 ORL人脸库上的仿真实验

本实验所用的人脸图像的训练样本和测试样本均来自ORL（Olivetti Research Library）标准人脸库。图1是ORL人脸库中某一个人的10幅人脸图像。实验中，我们将ORL人脸库中的图像处理成为[23×28]维的形式。在本仿真实验中，在ORL人脸库上，每类分别取4、5、6个样本为训练样本。共计 160个样本（或200个样本或240个样本）为训练样本。

这里选用的核函数是高斯函数[kX，Y=exp -γX-Y2]，其中[γ=0.03125]。图2表示每类分别选取4个样本（或5个样本或6个样本）为训练样本并且在不同的特征维数下（2、4、6、…、20），KPCA、KFDA和KMMC三种方法的识别率的变化情况。图2（a）表示每类取4个训练样本；图2（b）表示每类取5个训练样本；图2（c）表示每类取6个训练样本。

（a）每类取4个训练样本

（b）每类取5个训练样本

（c）每类取6个训练样本

表1表示每类分别选取4个样本（或5、6个样本）为训练样本并且特征维数取值范围为2、4、6、8、…、20时，KPCA、KFDA和KMMC三种鉴别方法所达到的最佳的识别率和对应的特征维数的取值。

图2（a）（b）（c）可以看出，三种鉴别方法里，KMMC的识别率整体优于KPCA和KFDA。当每类分别选取5个样本（或6个样本）为训练样本时，KPCA方法和KMMC方法的最佳识别率总是高于KFDA方法的最佳识别率。因此，在规模较大的人脸数据库上，KMMC鉴别方法的识别效果也有比较好的表现。三是KFDA的识别率明显是低于KPCA的识别率的。

6 结束语

本文首先对核方法做了简单的介绍，并学习和研究了三种基于核理论的非线性鉴别分析方法，分别是核主成分分析，核Fisher判别分析以及核最大间距准则，并在ORL人脸库上进行仿真。由仿真结果可知，KMMC方法提取鉴别信息的有效性整体高于KPCA和KFDA方法，在规模较大的人脸数据库上，KMMC鉴别方法的识别效果也有比较好的表现。

参考文献：

[1] 章毓晋. 基于子空间的人脸识别[M].北京：清华大学出版社，2009.

[2] 李国栋，李勇智. 一种基于核最大间距准则改进的特征提取方法[J].江苏大学学报，2008，19（7）：1670-7775.

[3] 胡迎春. 人脸图像特征点眼睛的定位与提取[J].广西工学院学报，2003（1）.

[4] 王映辉. 人脸识别——原理、方法与技术[M].北京：科学出版社，2010.

[5] 周杰，卢春雨，张长水，等. 人脸自动识别方法综述[J].电子学报，2000，28（4）：102-106.

[6] 王振海. 融合奇异值分解和最大间距准则的人脸识别方法[J].计算机工程与应用学报，2011，47（8）：164-166.

[7] 王本超，马军伟，顾宏. 基于KPCA和SVM的人脸识别研究[D]. 大连： 大连理工大学，2008.

[8] 高秀梅，杨静宇，杨健. 一种最优的核Fisher鉴别分析与人脸识别[J].系统仿真学报，2004，16（12）：2864-2868

（下转第201页）

（上接第194页）

[9] 杨健，杨建宇，金忠. 最优鉴别特征的抽取及图像识别[J].计算机研究与发展，2001，38（11）.

[10] 郭跃飞，黄修武，杨静宇，等. 一种求解Fisher最佳鉴别矢量的新算法及人脸识别[J].中国图象图形学报，1999，4（2）：95-98

[11] 徐勇，杨静宇，金忠，等. 一种基于核的快速非线性鉴别分析方法[J].计算机研究与发展，2005，42（3）：367-374.

[12] 许建华，张学工，李衍达. 一种基于核函数的非线性感知器算法[J].计算机学报，2002，25（7）：689-695.

[13] Liu K， Cheng Y Q， Yang Y Y.A generalized optimal set of discriminant vectors，Pattern Recognition ， 1992，25 （7） ：731-739.

[14] Yang L，Gong W， Gu X，et al. Liang，Null space discriminant locality preserving projections for face recognition，Neurocomputing ， 2008（71）：3644-3649.