大间距无监督正交特征提取算法*

林玉娥，李敬兆，梁兴柱，林玉荣

(1.安徽理工大学计算机科学与工程学院，安徽淮南232001;2.哈尔滨工业大学航天学院，黑龙江哈尔滨150001)

0 引言

主成分分析(principal component analysis，PCA)［1］以投影矩阵能够使得投影后的图像达到最小重构误差为目标，是一种全局的无监督特征提取算法，PCA所有的样本数据点采取相同的处理方式，目的是使高维的样本数据在投影空间中都被尽可能地分开，目前该算法已得到广泛的应用.但是从识别的角度来讲，比较靠近的数据样本有可能是同一类，因此，降维后也应保持近邻关系，局部保持投影［2，3］(locality preserving projection，LPP)就是基于这一思想的一种特征提取算法，其目的是使得投影后的图像样本在低维空间保持原有的近邻结构，人脸库上的实验结果表明了该算法的有效性.能否将二者结合起来使得所求取的投影矩阵更为有效，对此本文进行了研究，提出了一种大间距无监督正交特征提取算法(maximum margin unsupervised orthogonal feature extraction algorithm，MMUOFEA)，该算法以PCA和LPP为理论基础，其目标函数同时考虑全局与局部信息，其意义是尽可能重构原样本的同时保持投影后的样本原有的近邻关系，并且由于目标函数采用了大间距的鉴别准则［4～6］，避免了矩阵求逆，因此，解决了人脸识别中的小样本问题，同时为了增强算法的识别性能对鉴别矢量集进行了正交性的限制。仿真实验表明:本文方法不但是有效的，而且适应性更强。

1 主成分分析与保局投影

在模式识别中特征提取就是要找到一个投影矩阵W，然后对高维样本xi进行投影

式中 yi为图像xi的投影特征系数向量，W是按照某种准则求得的最佳投影矩阵，W 应能够使得投影后的图像具有较低的维数和较好的可分性。下面将简要地介绍2个与本文讨论密切相关的目标函数。

主成份分析的目的是要求所求取投影矩阵能够使得投影后的图像达到最小重构误差或最小均方意义下的最优表达，其准则函数为

式中 St称之为总体散布矩阵，St的定义为

其中，mi为第i类样本的均值向量，m为样本的总体均值向量。

对于上式中的W求解，实际上就是求解下式广义线性方程特征值与特征向量的问题

假设把求得的特征值按升序排列，选择对应前d(通常d＜l)个最大的特征值所对应的特征向量 w1，w2，…，wd，即是所求的最优投影方向矩阵W。

LPP以保持样本固有的局部流形结构为目标，其目标函数为

约束条件为

式(7)中的sij可按下式求得

式中 L=D－S为拉普拉斯矩阵，S是由sij构成表示位置相似矩阵，D为对角阵，其对角元素dii=，ε 是一个较小的正数。通过代数运算，式(7)可以转换成下面的特征值求解问题，即

假设把求得的特征值按降序排列λi≤λi+1，选择对应前d(通常d＜l)个最小特征值所对应的特征向量w1，w2，…，wd即是所求的最优投影方向矩阵W。

2 大间距无监督正交特征提取算法

PCA是一种全局算法，而LPP则是一种局部算法，2种算法基于不同的几何思想，因此，只可以发现数据集某一方面的特性。为了使算法能够在揭示数据集全局结构的同时又可以有效保持它的局部结构，本文将二者联系起来，提出MMUOFEA。其目标函数同时考虑全局与局部信息，其意义是尽可能重构原样本的同时要保证在低维空间保持原有样本的近邻结构。因此，MMUOFEA的目标函数应同时满足下面二式，即

上面二式可转化为一式，在这里为了避免了矩阵求逆，采用大间距的鉴别准则，同时加上正交约束条件，故MMUOFEA的目标函数定义为

对于上式的求解，根据Lagrange乘子法构造函数

对 wi求偏导并，可以得到式(10)的求解实际上就是下面广义特征值问题

最后选择对应前d(通常d＜l)个最大特征值所对应的特征向量 w1，w2，…，wd即是所求的正交投影矩阵。MMUMFA的具体实现步骤总结如下:

1)分别根据式(2)和式(7)分别求出St和S;

2)再根据L=D－S计算出L;

3)对式(11)进行特征值分解，选前d个最大特征值所对应的特征向量w1，w2，…，wd即求出W。

3 实验结果与讨论

本文为了验证提出MMUOFEA的性能，在ORL人脸库上进行了实验，采用简单的最近邻方法进行分类。ORL人脸库有40个人，每人10幅，共400幅图像，每幅图像的分辨率为112×92.对MMUOFEA与LPP及PCA的识别性能进行了比较，分别选择ORL人脸库前5幅图像作为训练样本，剩余作为测试样本，对MMUOFEA与LPP及PCA在提取不同特征数目时的识别性能进行了比较，实验结果如图1所示。图2为选用前3—8幅图像作为训练样本数目时，后7—2幅作为测试样本，2种算法识别率的比较。终都优于其他2种算法的识别率，当提取到大于40个特征时，MMUOFEA稳定在最高识别率92.5%，而且随着特征个数的增加算法的识别率一直稳定在92.5%;从图2可看出:无论训练样本如何变化，MMUOFEA都优于LPP和PCA的识别率，这也说明了本文的目标函数提取出的特征更加有利于分类，这是因为本文算法综合了LPP和PCA二者的优点，不但能够发现数据样本的全局结构更能有效地保持样本原有的近邻结构，因此，能够取得更好的识别效果。

图1 ORL人脸库识别率随维数变化的结果Fig 1 Change of recognition rate of ORL face database with different dimension

图2 训练样本个数变化时3种方法的性能比较Fig 2 Performance comparison of three methods while number of training samples change

4 结论

本文提出一种新的特征提取算法—MMUOFEA，其目标函数同时考虑数据样本的全局与局部信息，因此，MMUOFEA获得了更好的识别效果。MMUOFEA利用矩阵之差作为准则函数，解决了小样本问题，在人脸库上的实验结果验证了本文算法的正确性和有效性。

［1］Turk M，Pentland A.Eigenfaces for recognition［J］.Journal of Cognitive Neuroscience，1991，3(1):71－86.

［2］He X F，Yan SC，Hu Y，et al.Face recognition using Laplacianfaces［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(3):328－340.

［3］He X，Niyogi F.Locality preserving projections［C］∥Proceedings of Advances in Neural Information Processing Systems，Cambridge，MA，2004:153－160.

［4］Li H F，Jiang T，Zhang K S.Efficient and robust feature extraction by maximum margin criterion［J］.IEEE Transactions on Neura1 Networks，2006，17(1):1157－1165.

［5］林克正，王慧鑫，卜雪娜，等.基于局部保持投影的鉴别最大间距准则［J］.模式识别与人工智能，2010，23(2):178－185.

［6］Lu G F，Lin Z，Jin Z.Face recognition using discriminant locality preserving projections based on maximum margin criterion［J］.Pattern Recognition，2010，43(3):3572－3579.