一种基于配对矩阵改进的LE分类算法

GXF360 2017-05-29

展开全文

? 一种基于配对矩阵改进的LE分类算法

一种基于配对矩阵改进的LE分类算法

陈张莉，柳先辉，赵卫东

(同济大学电子与信息工程学院，上海 201804)

摘要：拉普拉斯特征映射(LE)算法基于流形学习思想将原始数据映射到低维空间，然而其无法解决样本外点学习问题，更没有使用类别信息。针对这些实际应用问题提出了一种新的基于配对矩阵的拉普拉斯特征映射(PM-LE)算法。PM-LE的目标是使得高维空间中的“相似点”投影到本征低维空间后为近邻点，同时该算法引入类别信息帮助构建近邻图，并且利用最大化相似矩阵及其配对矩阵内积的算法来重新计算权值矩阵，从而更适合应用于分类问题。应用于人脸识别的实验结果证明，PM-LE算法能很好地完成实际的降维和分类任务。

关键词：流形学习；拉普拉斯特征映射；数据降维；分类；监督学习；人脸识别

在分类聚类、信息检索、数据可视化等领域中，发展有效的降维技术，使得高维数据在压缩过程中尽量保持本征几何结构、避免有用信息丢失，一直备受关注。相对而言，现实世界中需要处理的诸如文本、图像、视频等数据，它们的特征空间不是输入空间的一个线性子空间，principal component analysis(PCA)[1]和multidimensional scaling (MDS )等线性方法也不再适用。非线性降维方法包括引入核技术和流形学习等。其中流形学习方法假定输入数据分布或近似分布于嵌入在高维空间中的低维流形上，强调简单的算法实施和避免优化问题收敛于局部最优。

低维流形嵌入在高维输入空间的案例包括代表相同三维空间物体在不同相机视角和光条件下的图像向量，以及语料库中的用于处理特定话题的文档向量等。在这些情况下原始输入空间的维度可能非常高，但本征维度相对有限。Isometric mapping(ISOMAP)[2]和locally linear embedding(LLE)[3]的提出正式开启了非线性流形学习的方向。发展至今，非线性流形学习大致可分为全局特性保持方法和局部特性保持方法。前者在高维输入空间中直接构建代表全局几何结构的全局度量矩阵，接着利用特征分解获得低维嵌入表示，如ISOMAP和maximum variance unfolding(MVU)[4]等；后者首先构建保持局部几何结构的局部度量矩阵，再全局排列局部信息以获得唯一的低维坐标，如LLE、Laplacian Eigenmaps(LE)[5]、Hessian Eigenmaps(HLLE)[6]。

发现流形的结构是一个非常有挑战的无监督问题，其获得的结果只是对应于原始数据集的低维表示，对于解决许多实际问题仍然不够实用，因此后来又衍生出有监督学习、样本外点学习、多流形学习等问题。许多学者针对其进行了改进。YAN 等[7]提出解决流形学习泛化问题的线性化、核化和张量化思想，并给出了一个帮助设计新的降维算法的框架；LEE 等[8]给出了一个利用分布在多个流形上的多个数据集学习其联合低维表示的方法，其中每个数据集被视作通用流形的一个实例。

拉普拉斯特征映射(LE )算法是保持局部特性流形学习方法的一种，locality preserving projection(LPP)[9-10] 算法是其对应的线性版本。本文基于传统的LE 和LPP 算法，引入类别信息帮助构建近邻图，并且利用SCOTT 等[11]提出的最大化相似矩阵及其配对矩阵内积的算法来重新计算权值矩阵，提出一种用于分类的PM-LE 算法。

1 LE 和LPP

LE 的基本思想是使得原始高维空间中的近邻点投影到本征低维空间后仍为近邻点。BELKIN 等人发现流形上Laplacian-Beltrami 算子的特征函数可以实现流形的低维嵌入。作为一个几何驱动算法，LE 假设输入数据均匀分布于一个高维流形之上，该流形可由数据集的邻接图G逼近，流形的Laplacian-Beltrami 算子可由邻接图G的Laplacian 逼近，因此Laplacian-Beltrami 算子的特征函数可由图Laplacian 的特征向量来近似等价。

假设高维数据集X={x1,x2,…,xN}，xi∈RD是从流形上均匀采样而来，其中N表示样本数，D表示高维特征维度。LE 方法获得能够最好地保存该流形局部信息的低维嵌入表示Y={y1,y2,…,yN}∈Rd×N，d?D，其中yi为列向量。

该算法主要分为3 步。首先构建邻接图G，如果样本xi和样本xj是近邻点，则其在G中对应的节点i和节点j之间存在边连接(近邻点的判别规则有2 种：xi和xj之间的欧式距离小于阈值或者是彼此的k近邻)；其次设置近邻图G的权值矩阵W，一般有热核权和0-1 权两种权值设置方式；最后进行特征映射计算。为了保持局部特性LE 最小化目标函数：

∑i,j‖yi-yj‖2Wij

(1)

通过施加一些缩放性限制，原优化问题可转化为：

(2)

其中：D为对角矩阵且Dii=∑jWij;L=D-W,是Laplacian矩阵;I是单位矩阵。因此，低维嵌入表示Y=[v2,…,vd ]T，其中v2,…,vd为Laplacian矩阵L的第2到第(d+1)最小特征值对应的特征向量，并且是行向量。

针对样本外点学习问题，LPP作为LE的线性版本被提出。LPP算法假设低维嵌入表示和原始高维数据之间存在线性映射关系，即设Y=ATX，其中A是RD×N投影矩阵。紧接着将其代入式(2)即可得到LPP的优化公式，则投影矩阵A可通过求解广义特征值得到。

2 基于配对矩阵的拉普拉斯特征映射算法(PM-LE)

相比于无监督学习算法LPP，PM-LE算法引入类别信息帮助构建近邻图G，并且利用SCOTT等提出的最大化相似矩阵及其配对矩阵内积的算法来重新计算权值矩阵W，从而更适合应用于分类问题。不同于LE和LPP的目标是使得高维空间中的近邻点投影到本征低维空间后仍为近邻点，PM-LE算法的目标是使得高维空间中的“相似点”投影到本征低维空间后为近邻点，其中“相似点”指属于同一类别的数据点。为了达到这个目的，假设属于不同类别的数据点之间不存在关联，则需要计算出同类别数据点之间的关联信息。

为了获得来源于运动序列连续帧的两张相关图片特征集J1和J2的关联，SCOTT等[11]提出最大化相似矩阵U和其配对矩阵P的内积，其目标函数如下所示：

(3)

P*即为所求的相关图片特征集的软关联矩阵。这里令J1=J2，从而可以采用SCOTT等提出的算法去获得属于同一类别的数据点之间的软关联信息，并且利用谱映射方法保持低维数据点之间的软关联信息不变。

给定高维数据集X={x1,x2,…,xN }，xi∈RD；样本xi对应类别标签为ci∈{1,2,…,Nc }，其中Nc是类别数；令πc和nc分别表示属于第c类的样本下标集合和个数。据此PM-LE算法的步骤可描述如下：

步骤1,构建邻接图G。如果样本xi和xj属于相同类别，则其在G中对应的节点i和j之间存在一条边，否则没有连接。

步骤2,设置邻接图G的权值矩阵W。本文假设属于不同类别的数据点之间不存在关联，并且由于邻接图G包含Nc个连通子件，即需要分别针对每一个连通子件，应用SCOTT等提出的算法去计算对应的软关联矩阵Pc。因此权值矩阵W可定义如下：

(4)

其中Pc的求解过程可分为3步：首先对于第c类数据集πc，计算任意两点之间的欧式距离矩阵Dc={dij,i,j∈πc}，从而得到相似矩阵Uc，其中。其次对相似矩阵Uc进行奇异值分解，即令

Uc=TSVT

其中S为奇异值矩阵；T和V分别是左奇异向量和右奇异向量组成的矩阵。最后令

Pc=TEVT，

其中E是通过将S的对角元素替换成1而得到的。

步骤3，特征映射计算。PM-LE最小化目标函数：

∑c∑i,j∈πc‖

(5)

式(5)事实上和LE的目标函数式(1)一致。为了解决样本外点学习问题，可以采用和LPP相同的思想。同样假设Y=ATX，故投影矩阵A可通过求解如下广义特征值得到：

XLXTA=λXDXTA

(6)

3 实验结果分析

本次实验基于YALE人脸数据集，共有165张灰度级图像(包含15人，每人有11幅图像)。图1是来自 YALE 人脸库的某个人的11张图像。实验中用到的所有图像都被预处理成32像素×32像素，因此每张图像都对应于图像空间的一个1024维向量。为了评估PM-LE算法的降维效果和分类性能，将其与LPP、MFA[7]等算法进行比较。其中LPP是无监督学习算法，令参数k=nc-1，采用热核权方式计算权值矩阵W；MFA是有监督的基于流形学习的算法，令参数k1=nc-1，k2=nc×nc。实验数据分为训练样本和测试样本，其中训练样本用于学习到低维空间的投影矩阵。在测试样本执行降维操作后，采用1NN分类器计算识别准确率。

图1 YALE人脸库的某个人的11张图像

实验中分别随机选择3,4,5,6幅图像作为训练样本，剩下的作为测试样本,并且针对每种样本数目进行5次随机实验，结果取5次实验的平均值。图2～图5分别给出了随着投影维度变化4种样本数目的算法分类性能的比较，表1给出了每种算法的最大识别准确率，括号中的值表示相应标准差。

表1 每种算法在不同训练样本数中的最大识别准确率

算法训练样本数3456PM-LE78.8%(0.028)80.2%(0.036)82.2%(0.057)83.2%(0.050)MFA68.0%(0.042)75.4%(0.041)77.6%(0.087)80.8%(0.087)LPP69.5%(0.028)73.5%(0.037)75.3%(0.037)77.9%(0.045)

从图2～图5和表1可以看出，随着选取的投影维度的增加，PM-LE算法应用于分类中的识别率在快速增加，并且很快趋于稳定。由于PM-LE算法目标是使得高维空间中的“相似点”投影到本征低维空间后为近邻点，在人脸数据集上的识别率优于LPP和MFA，并且随着训练数目的增多识别率也有所提高。>

图2 3幅训练样本实验算法分类性能比较

图3 4幅训练样本实验算法分类性能比较

图4 5幅训练样本实验算法分类性能比较

图5 6幅训练样本实验算法分类性能比较

4 结束语

本文对传统的LE和LPP算法进行改进，提出了作为谱映射算法延伸的PM-LE算法。PM-LE算法的目标是使得高维空间中的“相似点”投影到本征低维空间后为近邻点。引入类别信息帮助构建近邻图G，并且利用最大化相似矩阵及其配对矩阵内积的算法来重新计算权值矩阵W，从而使该算法更适合应用于分类问题。在YALE人脸数据集上的实验表明，PM-LE算法具有较好的分类性能。但是PM-LE算法假设属于不同类别的数据点之间不存在关联，这可能使得原始数据在降维过程中丧失了一部分信息，并且广义特征值求解限制了样本规模和算法效率，因此对于样本较多的投影矩阵的高效计算的实现是下一步需要研究的工作。

参考文献：

[1] TURK M, PENTLAND A. Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86.

[2] TENENBAUM J B, DE SILVA V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319-2323.

[3] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326.

[4] WEINBERGER K Q, SAUL L K. Unsupervised learning of image manifolds by semidefinite programming[J]. International Journal of Computer Vision, 2004, 2(1):77-90.

[5] BELKIN M, NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation [J]. Neural Computation, 2003, 15(6): 1373-1396.

[6] DONOHO D L, GRIMES C. Hessian eigenmaps:locally linear embedding techniques for high-dimensional data[J]. Proceedings of the National Academy of Sciences of the United States of America, 2003, 100(10):5591-5596.

[7] YAN S, XU D, ZHANG B, et al. Graph embedding and extension: a general framework for dimensionality reduction[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2007, 29(1):40-51.

[8] LEE C S, ELGAMMAL A, TORKI M. Learning representations from multiple manifolds[J]. Pattern Recognition,2016,50:74-87.

[9] HE X, YAN S, HU Y, et al. Face recognition using laplacianfaces[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2005, 27(3):328-340.

[10] ZHAO H, SUN S, JING Z, et al. Local structure based supervised feature extraction[J]. Pattern Recognition, 2006, 39(8):1546-1550.

[11] SCOTT G L, LONGUET-HIGGINS H C. An algorithm for associating the features of two images.[J]. Proceedings of the Royal Society B Biological Sciences, 1991, 244(1309):21-26.

An improved LE classification algorithm based on pairing matrix

CHEN Zhangli, LIU Xianhui, ZHAO Weidong

(College of Electronics and Information Engineering, Tongji University, Shanghai, 201804, China)

Abstract：Laplacian Eigenmaps algorithm is a low-dimensional space set from the original data based on manifold learning theory. However, this algorithm is poor out-of-sample learning ability, and does not identify the class information. Aiming at the actual application problem, it proposes a new Laplacian Eigenmaps algorithm(PM-LE) based on pairing matrix. It sets LE's goal to make close points in high dimension space stay close, and projects these points to the intrinsic low dimensional space, defines PM-LE maps 'similar points' in the original space to neighbor points in the target space. This algorithm introduces class information to help build a nearest neighbor graph, recalculates the weight matrix to maximize the inner product of a given similarity matrix and corresponding pairing matrix. The experimental results on face recognition indicate that the PM-LE algorithm can effectively reduce the dimensionality and accomplish classification task.