学文网摘要：非线性降维作为当前流行的机器学习算法，是研究人员的研究热点。局部线性嵌套和等距流形映射是两个基本非线性降维方式，局部线性嵌套的优点和不足在人脸识别上值得做出深入的研究，因此测试这种降维方式在不同参数下的执行效率，分析和总结这种降维方式的适用特点和范围，选择局部线性嵌套和主成分分析，通过应用于人脸识别中，并总结人脸识别的识别率。
关键词：非线性降维算法；局部线性嵌套；人脸识别
中***分类号：TP18 文献标识码：A文章编号：1009-3044(2011)23-5714-03
Facerecognition Method Based on LLE Algorithm
LIU He-an
(Center of Network information, Hunan City University, Yiyang 413000, China)
Abstract: The algorithm of nonlinear dimensionality reduction is popular in the manifold learning,It's one of focus in the research during the researchers.locally linear embedding and isometric mapping are the basic algorithms of nonlinear dimensionality reduction. This paper analyzed and argued locally linear embedding(LLE) algorithm．Proposed face recognition method based on LLE algorithm．The method was tested against two face data bases:PIE&YALE.
Key words: nonlinear dimensionality reduction; locally linear embedding; face recognition.
1 数据降维及算法
随着信息时代的到来，数据集增长更快、数据维度更高、非结构化性更突出。如何在保持数据信息足够完整的意义下从海量数据集中提取出有效而又合理的约简数据，满足存储需求和人的感知需要是亟需解决的问题。
在高维数据中进行各种处理需要样本的数量会成指数增加，样本间距离的价值也越来越小，这样就面临维数灾难问题。 对于实际中很多问题来说，大部分高维观测数据变量可以用少量几个影响因素来表示，这说明其中包含着大量冗余信息，各成分之间通常也有着较强的相关性，这种现象几何学上表现为数据分布在低维流形上，或者是在低维流形附近。
因此，要有效揭示高维观测数据潜在的结构，需要学习和发现嵌入在高维空间中的低维特性。即进行维数约简。在研究维数约简的方法过程中，主要的方法是选取高维数据中尽可能多的，有用的特征，根据一定方法获取最突出的特征，即进行特征的约简。特征约简分为线性与非线性两种。
线性降维方法是通过线性的特征组合来降维的，本质上是把数据投影到低维的线性子空间。
非线性方法的研究主要是基于：许多高维采样数据都是由少数几个隐含变量所决定的，如人脸采样由光线亮度，人离相机的距离, 人的头部姿势，人的脸部肌肉等因素决定。近年来，非线性降维算法的研究与应用取得了丰硕的成果，著名的非线性降维算法有；局部线形嵌套(Locally Linear Embedding,LLE)、等距流形映射(Isomeitric Mapping, ISOMAP)、拉普拉斯特征映射(Laplacian eigenmaps)、局部保持投影(Local Preserving Projection,LPP)等。这些方法均能保持原始数据的拓扑结构不变，并能较好解决数据处理中的“维数灾难”问题。
2 LLE算法原理
假设给定数据集合X={x1,x2,…,xN}，包括N个实值向量，向量的维数为D，且这些数据采样于某个潜在的光滑流形。采样数据点要求足够多，并且每个采样数据点及其邻点都落在该潜在流形的一个局部线性块上或该块附近。用每个数据点的邻点集重构该点会得到一组线性系数，然后用这组线性系数就可以刻画流形的局部线性几何性质。
最简单的方法是采用欧氏距离来确定每个数据点的K个邻点。总的重构误差由如下的代价函数确定：
式中，权值矩阵W为一个N×N维的对称矩阵，权值Wij表示第j个数据点对第i个数据点的重构所具有的贡献。
要求出权值Wij，需要最小化具有如下两个约束条件的代价函数：
1) 每个数据点只能由它的K个邻点重构，即若第j个数据点不是第i个数据点的邻点，则Wij=0；
2) 权值矩阵各列的元素之和为1，即Wij=1。具有这两个约束的最优权值可以通过解一个最小二乘问题得到。
由上面的约束条件1，重构代价函数可以写为：
然后，LLE算法构建邻域保留映射把高维观测向量xi映射成某流形上的低维向量yi。这一映射过程首先选择d维坐标yi，然后保持Wij不变，通过优化yi使下面的嵌入代价函数目标值达到最小：
算法步骤如下 ：
1）使用K近邻方法为每一个数据点xi,i=1,2,…,N,xi∈RD分配近邻；
2）计算根据xi近邻线性重构xi的权值Wij，使得；
3）通过求稀疏对称阵M=(I-W)T(I-W)的最小特征值，低维嵌入是 M 的最小的第 到第d+1个特征向量。
3 LLE算法的降维效果与效率
算法效率主要是该算法处理数据集所花费的时间，合理的时间需进行多次测量取平均。
瑞士卷(Swiss Roll)数据集
实验使用的数据集是采样于瑞士卷(Swiss Roll)***形是三维数据集。
1) 数据点个数为800，即X=800；降维后的目标维数均为2维，即d=2；在使用 近邻构造邻域***时，K=8,12。
(a) 原始数据集(b) K=8 (c) 原始数据集 (d) K=12
***1瑞士卷数据集降维效果***(邻居不同)
从***1和表1中可以看出，选取的邻居点数不同，降维后的低维空间数据点关系会有所不同，并且邻居点数越多，计算的时间越长。
2)数据点个数为800、1600和3200，即X=800，1600，3200；降维后的目标维数均为2维，即d=2；在使用K近邻构造邻域***时，K=8。
表2中，处理1600个数据点的时间是处理800数据点的时间的3.601倍，处理3200个数据点的时间是处理800数据点的时间的3.807倍。
双峰(twin peaks)数据集
实验使用的数据集是采样于双峰(twin peaks)***形，也为三维数据集。
1)数据点个数为800，即X=800；降维后的目标维数均为2维，即d=2；在使用 近邻构造邻域***时，K=8,12。
2) 数据点个数为800、1600和3200，即X=800，1600，3200；降维后的目标维数均为2维，即d=2；在使用K近邻构造邻域***时，K=8。
对比表3和表1，表4和表2可以看出，在条件相同的前提下，LLE处理不同的数据集的效率相近。
4 LLE算法在人脸识别上应用
非线性降维算法可以应用于各种科学计算中，为解决大量高维数据的处理问题提供了方案。本文将局部线性嵌套算法应用到人脸识别项目中，为解决人脸识别提供一种方法。人脸识别的过程包含人脸的训练和人脸的分类，使用支持向量机分类器或k阶邻近分类器实现。实验中，同时采用线性算法PCA和非线性算法LLE降维人脸数据，对计算出的识别率进行比较，探讨LLE算法的降维特点。
5 基于二类分类的脸部识别
实验的头像数据采用PIE数据库，头像的分辨率是32×32，选取2个人的头像，每个人有170个不同姿势和亮度的头像。用SVM算法对降维后的数据进行分类得到***5。
***5 基于SVM二类分类的人脸识别
如***5可知，PCA算法的降维效果明显好于LLE算法，这是由于PCA算法已经比较成熟，而LLE算法还比较新，设计的还不够完善，降维效果比较差。
6 不同条件下LLE算法的人脸识别比较
采用实验一的人脸数据库，改变LLE算法的邻居数，分别设为8、15和30个，重复人脸识别试验。得到的识别率如***6。
如***6所示，LLE(K=8)和LLE(K=15)的降维效果要优于LLE(k=30)，这表明LLE算法采用的邻居数必须适当，邻居数过多将会极大的影响LLE算法的降维效果。
参考文献：
[1] 王泽杰.两类非线性降维流形学习算法的比较分析[J].上海工程技术大学学报,2008,22(1):54-59.
[2] 王自强,钱旭,孔敏.流形学习算法综述[J]．计算机工程与应用,2008,44(35):9-12.
[3] 刘庆.半监督的手写体识别[D].中国科学技术大学,2008.
[4] 杨剑.流形学习问题[D].北京：中国科学院自动化研究所,2005.
[5] Varini C,Degenhard A,Tim W.Nattkemper.ISOLLE:LLE with geodesic distance[J].Neurocomputing,2006:1768-1771.
注：本文中所涉及到的***表、注解、公式等内容请以PDF格式阅读原文
转载请注明出处学文网 » 基于LLE算法的人脸识别方法研究