半监督局部线性嵌入算法在人脸识别中的应用

沈 杰，杨月全，王正群，唐拥政，王明辉

(1.盐城工学院 现代教育技术中心，江苏 盐城 224051;2.扬州大学 信息工程学院，江苏 扬州 225009)

流形学习(Manifold Learning，ML)［1，2］是近几年兴起的一种新型机器学习思想，在模式识别、数据挖掘和计算机视觉等领域受到了广泛的关注和应用。随着信息技术的飞速发展，人们获得的数据呈现出海量、高维和不确定性等特点，如何对高维数据采用某种维数约简方法进行降维处理就显得尤为迫切，也是目前的研究热点。传统的降维方法如主成分分析［3］(Principal Component Analysis，PCA)和线性判别分析［4］(Linear Discriminant Analysis，LDA)在高维数据集具有线性结构和高斯分布时能有比较好的效果，但是当数据集在高维空间呈现高度扭曲时，它们很难发现嵌入在数据集中的非线性结构和恢复内在的结构。流形学习方法提供了一种新的研究途径［5］。

流形学习的目标是对训练集中的高维数据空间进行非线性降维，揭示其流形分布，从而找出隐藏在高维观测数据中的有意义的低维结构，以便从中提取易于识别的特征。2000年Seung、Tenenbaum和Roweis等人在《Science》上发表了3篇论文［6－8］，从认知的角度探讨了流形学习，不仅首次使用了“Manifold Learning”这一术语，而且还给出了可行性算法，为维数约简提供了一个新的研究方向，从而引起了流形学习的研究热潮。著名的流形学习算法有:等距映射［7］(Isometrical Mapping，ISOMAP)、局部线性嵌入［8］(Locally Linear Embedding，LLE)、拉普拉斯特征映射［9］(Laplacian Eigenmap，LE)、局部切空间排列［10］(Local Tangent Space Alignment，LTSA)等。这些算法均能较好的保持原始数据的拓扑结构，并有效的解决数据处理中的维数灾难问题。

局部线性嵌入算法是流形学习中的经典方法，是一种借助局部线性关系描述全局非线性结构的降维思想。针对LLE算法非监督学习的缺陷，Ridder等人提出了一种监督局部线性嵌入［11］(Supervised Locally Linear Embedding，SLLE)算法，但监督学习算法需要所有样本具有标签信息，在机器学习相关问题中，所获取的大多是不带标签的数据，带标签的数据则相对有限，因此半监督流形学习成为模式识别和机器学习领域研究的一个新的热点。本文引入半监督思想，提出了一种基于半监督局部线性嵌入［12］(Semi－Supervised Locally Linear Embedding，SSLLE)的人脸图像识别方法，对经典LLE算法进行了改进，增加了部分样本的标签信息，使之能适应半监督流形学习［13］，最后使用最近邻分类器进行分类识别，在Yale和ORL人脸库上进行了实验比较，验证了本文提出的算法具有较高的识别率。

1 局部线性嵌入(LLE)

局部线性嵌入算法是由Roweis和Saul提出的一种非线性流形学习方法［8］。LLE算法的基本假设是:①流形上的任意一个样本点都能由其邻域点线性重构而成，并且重构权值可以保证样本点与邻域点的线性重构误差最小;②在映射过程中保持这种线性关系不变，即在低维空间中保持每个邻域中的重构权值不变，这样可以得到高维数据在低维空间的嵌入。

设数据集中有 N 个样本点 xi，xi∈RD，i∈［1，N］，降维后的 N 个样本点为 yi，yi∈Rd，i∈［1，N］，d≪D。LLE 算法步骤如下［14］:

步骤1:选取邻域。一般使用K近邻法，即对数据集中的每个样本点xi，寻找欧氏距离与其最近的k个点作为它的近邻。另外也可采用ε邻域方法来确定邻域。

步骤2:计算重构权值矩阵W。由上步确定的邻域关系，每一个样本点xi都可以由它的k个近邻点通过权值Wij线性加权表示。最小化如下定义的代价函数，可以得到约束的权值矩阵W。

步骤3:计算低维嵌入。构造代价函数

其中，yi是xi的低维映射矢量，yj是xi的近邻xj的低维映射矢量。最小化代价函数ε(y)，使得低维重构误差最小，则yT(y是由所有yi为列向量所组成的矩阵)取M的最小d个非零特征值所对应的特征向量，M=(I－W)T(I－W)。在实际处理过程中，由于M的最小非零特征值几乎接近于零，所以yT通常取M最小的第2个到第d+1个非零特征值所对应的特征向量。

2 监督局部线性嵌入(SLLE)

LLE算法是一种非监督的算法，没有利用样本的类别信息，针对此缺点，Ridder等人提出了一种监督局部线性嵌入［11］(Supervised Locally Linear Embedding，SLLE)算法。SLLE算法与传统LLE算法的主要区别在于第1步邻域的构造:LLE算法在构造邻域时是根据样本点间的欧氏距离来寻找k个近邻点，而SLLE算法在处理这一步时，增加了样本点的类别信息。SLLE算法的其余步骤同LLE算法一致。

在计算样本点之间的距离时，SLLE算法采用如下公式:

其中D'是计算后的距离;D定义为样本点之间的距离;max(D)表示类与类之间的最大距离;△取0或1，当两个样本点属于同类时，△取0，否则取1;α是控制点集之间的距离参数，当α取0时，此时的SLLE算法和LLE算法相同。

3 半监督局部线性嵌入(SSLLE)

本文将半监督思想引入LLE算法，提出了一种基于半监督局部线性嵌入［12］(Semi－Supervised Locally Linear Embedding，SSLLE)算法，通过部分带标签的样本来重新调整距离矩阵，使得LLE算法能够更准确的构造样本点的邻域。

其中r(0＜r＜1)是调节系数，一般取经验值，可以用来判定带标签样本和不带标签样本是否可以被选为近邻点。

在确定了每个样本点的k个近邻点后，SSLLE算法的其余步骤与LLE算法相同。SSLLE算法可以有效的学习非线性流形结构，考虑了样本的类别信息，利用部分样本的标签信息来重新调整距离矩阵，实现了不同类别标签样本之间的良好可分，并取得了较好的降维效果。

4 实验结果及分析

实验是在Yale和ORL人脸库上完成的(实验环境:Intel酷睿2双核E84003.0 GHz;Matlab 7.0)，分别用LLE算法和本文SSLLE算法来提取人脸有效特征，最后通过最近邻分类器测试了这两种算法的识别效果(经过多次重复实验，取其平均值)，并进行了综合比较和分析。Yale人脸库15个人每人随机取5幅图像共75幅进行训练，剩余每人6幅图像共90幅进行测试。ORL人脸库40个人每人随机取5幅图像共200幅进行训练，剩余每人5幅图像共200幅进行测试。对于本文SSLLE算法而言，Yale和ORL人脸库都是每人取5幅图像具有类别标签，另调节系数r取经验值 0.5。

图1～图2是LLE算法与本文SSLLE算法在Yale和ORL人脸库中识别率随着邻域数目k变化的对比曲线图。对LLE算法而言，Yale人脸库在k=10和k=12时识别率达到最大，ORL人脸库在k=6时识别率达到最大;对本文SSLLE算法而言，Yale人脸库在k=8时识别率达到最大;ORL人脸库在k=6时识别率达到最大。所以后续实验里，LLE算法在Yale和ORL人脸库中邻域数目k分别取值为10和6，本文SSLLE算法在Yale和ORL人脸库中邻域数目k分别取值为8和6。另外k值对识别率有着一定的影响，一定范围内随着k值的增大，识别率会有所提高，但是当k取值较大以后，识别率将有所回落并趋于稳定。

图1 LLE算法与本文SSLLE算法在Yale人脸库中邻域数目k与识别率的关系Fig.1 The relations between neighborhood number k and recognition rate of LLE algorithm and SSLLE algorithm on Yale face database

图2 LLE算法与本文SSLLE算法在ORL人脸库中邻域数目k与识别率的关系Fig.2 The relations between neighborhood number k and recognition rate of LLE algorithm and SSLLE algorithm on ORL face database

图3～图4是LLE算法与本文SSLLE算法在Yale和ORL人脸库中对应不同特征维数d时，所取得的识别率的对比曲线图。对LLE算法而言，Yale人脸库在d=25和d=60时获得最高识别率(91.6%)，ORL人脸库在d=30时获得最高识别率(91.2%);对本文SSLLE算法而言，Yale人脸库在d=55时获得最高识别率(95.6%)，ORL人脸库在d=40时获得最高识别率(94.5%)。另外d值对识别率有着明显的影响，最初随着d值的增加，识别率会迅速上升(有时会有波动，比如Yale人脸库SSLLE算法)然后中间出现一个峰值(Yale人脸库LLE算法比较特殊，出现两次峰值)，以后随着d值的增加，识别率将有所回落并趋向于稳定。从图3和图4可以看出，在对应不同特征维数d时，本文SSLLE算法取得的识别率整体上要比LLE算法高。

图3 LLE算法与本文SSLLE算法在Yale人脸库中识别率与特征维数的关系Fig.3 The relations between recognition rate and feature dimension of LLE algorithm and SSLLE algorithm on Yale face database

图4 LLE算法与本文SSLLE算法在ORL人脸库中识别率与特征维数的关系Fig.4 The relations between recognition rate and feature dimension of LLE algorithm and SSLLE algorithm on ORL face database

表1给出本文SSLLE算法和其它算法在Yale和ORL人脸库上所获得的平均识别率的实验数据。从表中可看出，本文SSLLE算法在Yale和ORL人脸库上都获得了较高的识别率。

表1 各算法在Yale和ORL人脸库上的平均识别率Table 1 The average recognition rate of each algorithm on Yale and ORL face database %

表2给出本文SSLLE算法和其它算法在Yale和ORL人脸库上对一幅测试图像进行分类识别所需时间的比较。从表中可看出，本文SSLLE算法以较小的时间代价提高了识别率，完全满足人脸识别系统的实时性要求。

表2 各算法在Yale和ORL人脸库上的分类识别时间(ms)Table 2 The recognition time of each algorithm on Yale and ORL face database

5 结论

本文在对局部线性嵌入(LLE)算法分析的基础上提出了一种半监督局部线性嵌入(SSLLE)算法，并将该算法应用于人脸识别。针对LLE算法非监督的缺陷，对其进行了改进，增加了部分样本的标签信息，使之能适应半监督流形学习。在Yale和ORL人脸库上的实验结果表明，本文SSLLE算法具有良好的降维效果和较高的识别率，利用较少的标签信息有效的提高了人脸识别的性能，符合现代工程应用的实时性要求。

［1］周波.2种基于谱方法的流形学习算法研究［J］.云南民族大学学报，2008，17(4):370－373.

［2］解洪胜，王连国.流形学习中三种非线性降维算法的比较研究［J］.云南民族大学学报:自然科学版，2009，18(2):151－156.

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

［4］Belhumeur P N，Hespanha J P，Kriegman D J.Eigenface vs.fisherfaces:recognition using class specific linear projection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19:711－720.

［5］王珏，周志华，周傲英.机器学习及其应用［M］.北京:清华大学出版社，2006.

［6］Seung H S，Lee D D.The manifold ways of perception［J］.Science，2000，290(5500):2268－2269.

［7］Tenenbaum J B，de Silva V，Langford J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290(5500):2319－2323.

［8］Roweis S T，Saul L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290(5500):2323－2326.

［9］Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003，15(6):1373－1396.

［10］Zhang Z Y，Zha H Y.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment［J］.SIAM Journal of Scientific Computing，2004，26(1):313－338.

［11］De Ridder D，Kouropteva O，Okun O，et al.Supervised locally linear embedding［C］.Artificial Neural Networks and Neural Information Processing－ICANN/ICONIP 2003 Lecture Notes in Computer Science，2003，2714:333－341.

［12］张长帅，周大可，杨欣.一种基于核的半监督局部线性嵌入方法［J］.计算机工程，2011，37(20):157－159.

［13］Yang X，Fu H Y，Zha H Y，et al.Semi－supervised nonlinear dimensionality reduction［C］.Proceedings of the 23th International Conference on Machine Learning，2006:1065－1072.

［14］王朝.基于流形学习的人脸识别算法的研究［D］.大连:大连理工大学，2009.

［15］李见为，樊超，王玮.监督局部线性嵌入在人脸识别中的应用［J］.重庆大学学报，2010，33(2):92－97.