人脸识别是当今极具研究价值和应用价值的一门生物特征识别技术，目前主要应用于门禁系统、支付系统、网络应用等领域^[1]。人脸识别的关键是从人脸图像中提取出最具鉴别力的特征^[2]。

流形学习算法的核心就是找到高维数据的低维嵌入流形，实现维数约减^[3]。发现低维嵌入流形的几个较著名的非线性流形学习算法有：局部线性嵌入 (locally linear embedding, LLE)^[4]、等距映射 (Isomap)^[5]和拉普拉斯特征映射 (laplacian eigenmap, LE)^[6]。这些算法和谱图理论紧密结合，它们虽然能够得到高维数据的低维表达，但这些算法都是通过隐式映射的方法将数据从高维空间映射到低维空间，这样就面临新的数据集较难处理的问题。所以，He等^[7-10]相继提出了包括邻域保持嵌入 (neighborhood preserving embedding, NPE)、局部保留投影 (locality preserving projection, LPP) 等的线性流形学习算法，这些算法能够有效保持样本之间的局部近邻结构，还能将人脸数据映射到一个反映其本质特征的流形结构上。

上述流形学习算法，都是将不同类别的数据映射到一个统一的低维嵌入流形之上。而实际数据点可能位于不同的流形上^[11-13]，这样会影响数据之间真实空间分布的描述。多流形分布问题已被越来越这方面的学者意识到，提出了一些有监督的流形学习算法^[14-16]，尝试利用样本的类别标签方法来解决多流形分类问题。虽然取得不错的识别效果。但这些算法仍然是在单一的空间或同一个坐标系下来揭示数据的低维流形，由此得到不同类别数据形成的流形，其本质是一个单一流形的子流形，此外这些算法过多地强调辨别性能。由此可知如果对可能具有多个不连续子集的真实数据集采用单一流形假设算法是不能得到最优识别效果的。

在多人脸流形分类框架的基础上，提出了多邻域保持嵌入 (multiple neighborhood preserving embedding, M-NPE) 算法，根据算法流程，用不同类别的人脸数据表述不同的低维流形，且认为各类数据的本质特征和维数不尽相同。M-NPE算法的基本流程是：1) 使用NPE方法分别学习各类人脸数据的低维流形；2) 利用遗传算法 (GA) 优化多个流形在分类意义下的维数，得到最优维数组；3) 在多流形上对新人脸样本进行分类，所用分类器是基于最小重构误差分类器。

1 多邻域保持嵌入学习算法原理 1.1 单流形学习框架

单流形学习框架如图 1所示，利用NPE算法将不同类人脸数据映射到一个统一的低维流形上。

1.2 多邻域保持嵌入学习算法框架

图 2为算法的框架。研究算法：假设多类数据处于多个流形之上，这样保持了样本空间的局部几何结构的最优性，也学习到了各类样本的最优邻域及其相应的投影矩阵，嵌入空间的分辨能力也更强。

1.3 NPE算法

NPE算法的基本思想：任意给定一个样本点集，利用k近邻线性表述该原始空间中的样本点，并根据最小重构误差准则使得空间中的所有样本点的重构权重系数不变，以保证样本映射到低维空间前后的权重关系不改变。

X={x₁, x₂, …, x_N}，x_i∈R^D为高维空间中N个样本点，则${{x}_{1}}\approx \sum\limits_{j\in N\left( {{x}_{i}} \right)}{{{\omega }_{ij}}{{x}_{j}}}$，其中N(x_i) 表示样本x_i的邻域，ω_ij为对应的权值。ω_ij通过最小化目标函数得到

$ \varphi \left( W \right)={{\sum\limits_{i}{\left\| {{x}_{i}}-\sum\limits_{j}{{{\omega }_{ij}}{{x}_{j}}} \right\|}}^{2}}, $

(1)

使服从①若x_i和x_j互为邻域点，则ω_ij=0；② $\sum{_{j}{{\omega }_{ij}}=1}$。

寻一组d维数据点集，Y={y₁, y₂, …, y_N}(y_i∈R^d, d∈D)，y_i=a^Tx_i。Y和X具有相同的局部几何结构，则a可通过最小化目标函数得到

$ \begin{align} &\varphi \left( \boldsymbol{a} \right)=\sum\limits_{i}{{{\left\| {{y}_{i}}-\sum\limits_{j}{{{\omega }_{ij}}{{x}_{j}}} \right\|}^{2}}\text{=}} \\ &\ \ \ \ \ \ \ \ \ \ \ \sum\limits_{i}{{{\left\| \boldsymbol{{{a}}^{\text{T}}}{{x}_{i}}-\sum\limits_{j}{{{\omega }_{ij}}\boldsymbol{{{a}}^{\text{T}}}{{x}_{j}}} \right\|}^{2}}}, \\ \end{align} $

(2)

简单的代数变换后，有

$ \mathit{\boldsymbol{a}}=\underset{a}{\mathop{\rm{arg}\ \rm{min}}}\, \frac{{{\mathit{\boldsymbol{a}}}^{\rm{T}}}\mathit{\boldsymbol{XM}}{{\mathit{\boldsymbol{X}}}^{\rm{T}}}\mathit{\boldsymbol{a}}}{\mathit{\boldsymbol{aX}}{{\mathit{\boldsymbol{X}}}^{\rm{T}}}\mathit{\boldsymbol{a}}}, $

(3)

其中，X=[x₁, x₂, …, x_N]，M=(I-W)^T(I-W)。

通过Lagrange乘数法得到广义特征值

$ \mathit{\boldsymbol{XM}}{{\mathit{\boldsymbol{X}}}^{\rm{T}}}\mathit{\boldsymbol{a}}=\lambda \mathit{\boldsymbol{X}}{{\mathit{\boldsymbol{X}}}^{\rm{T}}}\mathit{\boldsymbol{a, }} $

(4)

令式 (4) 的解依据其对应特征值的升序排序为a₁, a₂, …a_d，即λ₁≤λ₂≤…≤λ_d，令A=[a₁, a₂, …a_d]∈R^m×d，则嵌入为x_i→y_i=A^Tx_i。

1.4 多流形维度选择

在维数选择步骤中直接显式地将分类准确率作为目标函数进行优化。决定所有子流形的维数是一个联合优化问题，采用穷举法获取最优维数的效率低，而遗传算法 (GA) 具有较强的全局非线性优化能力，因此采用遗传算法对维数进行优化。

设{d₁, d₂, …, d_N}分别为数据集{X₁, X₂, …, X_N}的低维流形空间维数。调谐样本集T_u是由各流形中一部分有类别标签的数据构成，它们是随机的，对各流形维数组合进行浮点数编码，且适应度用于度量群体各个体在有助优化的过程中的优良程度，因此依据选择的流形学习算法对T_u分类的识别率构建遗传算法的适应度函数

$ f\left( {{d}_{1}}, {{d}_{2}}, \cdots, {{d}_{N}} \right)=\frac{1}{\left| {{T}_{u}} \right|}\sum\limits_{{{x}_{i}}\in {{T}_{u}}}{L\left( l\left( {{x}_{i}} \right), \arg \ \min \ \text{erro}{{\text{r}}_{k}}\left( {{x}_{i}} \right) \right)}, $

(5)

其中，|T_u|表示T_u中样本的个数；l(x_i) 是数据点x_i的类别标签，x_i的类别标签$\underset{k}{\mathop{\arg \ \min }}\,\ \text{erro}{{\text{r}}_{k}}\left( {{x}_{i}} \right)$通过重构误差法得到，L(l₁, l₂) 为1表示类别标签l₁与l₂相同，否则为0。

首先根据经验设置若干组维数作为初始种群，在迭代中，依适应度函数来评判优劣性，对进化出的下一代重复搜索，得到最优的一组多流形维数。

1.5 重构误差分类器

对于某一特定流形的数据点，其低维表示与其他流形上K近邻点之间的重构误差大于该低维表示与原流形的重构误差。因此，可以将新样本在多个流形上的重构误差值作为判断其所属类别的依据。

假设新样本数据x₀低维映射坐标y₀^k=A_k^Tx₀，k=1, 2, …, N，N^k为通过k-NN或ε邻域方法得到的y₀^k在每个流形上的邻域，则x₀在第k个流形上的重构误差可表示为

$ {\text{erro}}{{\text{r}}_k}\left( {{x_0}} \right) = \mathop {\min }\limits_{w_i^k} {\mkern 1mu} {\left\| {y_0^k - \sum\limits_{y_0^k \in {N^k}} {w_i^ky_i^k} } \right\|^2}, $

(6)

约束条件为$\sum\limits_{i}{w_{i}^{k}=1}$。计算出新样本在低维流形上的重构误差，可以根据重构误差最小化准则函数判断出新样本所属的流形

$ \hat l\left( {{x_0}} \right) = \arg \;\mathop {\min }\limits_{k \in \left\{ {1,2, \cdots ,N} \right\}} {\mkern 1mu} \;\;\;{\text{error}}\left( {{x_0}} \right), $

(7)

其中$\hat{l}\left( {{x}_{0}} \right)$表示x₀所属流形的类别标签。

2 实验及分析

选择在大型的人脸数据库Extended Yale B^[17]和CMU PIE^[18]上实验并以识别率为指标来评估M-NPE算法的性能。同时对比主成分分析 (principal component analysis, PCA)、线性鉴别分析 (linear discriminant analysis, LDA)、局部线性嵌入 (LLE)、局部保持投影 (LPP)、邻域保持嵌入 (NPE) 和有监督邻域保持嵌入 (supervised neighborhood preserving embedding, SNPE)^[14]等算法的实验结果。

2.1 Extended Yale B

Extended Yale B人脸数据库收集了38个人分别在64种不同的光照条件下采集图像。在研究中，选取了2 432幅人脸图像作为实验数据集，来学习每类人脸数据所包含的流形结构。图 3所示为Extended Yale B人脸库中所收入部分人脸图像，其光照强度和表情都各不相同，将人脸图像基于眼睛位置对齐，剪裁出固定像素大小为32×32的脸部区域。

随机选取该数据库中每个个体所有64幅图像中的32幅作为训练样本集。最后的识别率取10次实验的平均值。实验结果如图 4所示，表 1列出了各类方法在最高维数80时的最高总体识别率。在M-NPE算法中，各个流形的维数是确定。因此，为了便于比较各算法的识别效果M-NPE算法的分类识别率用一条直线来表示。此数据库求得的最优维数为30。此外LDA算法降维最高只能降到类别数-1维，因此其在实验中维度与其他算法不同，之后的实验亦此原因。

2.2 CMU PIE

PIE人脸库包含68个人在不同姿态、光照、表情下的的41 368幅图像。取数据库中每人的80幅包含光照和表情变化的近似正面姿态的人脸图像作为实验样本集；将人脸图像基于眼睛位置对齐，剪裁出固定像素大小为32×32的脸部区域。图 5所示为该数据库其中一人经剪裁后的部分人脸。

在该数据库中随机选取每人40幅图像作为训练样本集。对于多流形试验，由于其流形具有一组最优维数，因此M-NPE的实验结果可用一条直线表示。此实验的最优维数为27。取10次实验的平均值作为算法的最后识别结果。实验结果如图 6所示。表 1也列出了各类方法在最高维数100时的最高识别率情况。

实验主要在Extended Yale B和CMU PIE上进行。在2个数据库的多流形实验中，将每类人脸数据随机取出50%的样本作为训练样本，用来学习相对应的低维流形；剩余数据中随机选择30%作为测试样本用来搜索多流形的最优维数组合；通过除去训练样本的50%的样本作为新样本集的方法来测试M-NPE算法的识别性能。其中数据样本的标注由人工来完成。基于单流形假设算法在2次实验中都是训练样本和测试样本各占一半，对全部训练样本学习出一个统一的低维流形，测试样本用来测试各算法的识别效果。取10次重复实验的平均值作为各个算法的识别结果。

2.3 实验结果分析

以上的实验结果清楚地证明所提出的基于多邻域保持嵌入的分类方法对于人脸识别的有效性和稳定性，它较基于单流形的方法得到了更好的分类结果。这也证明了在人脸识别中，单流形假设并不能保证得到最优的分类准确率。相反，多流形假设更加合理。研究提出的基于多邻域保持嵌入的分类方法的核心思想是学习特定类的流形，即为每一个类别学习一个流形。当使用基于单流形的方法时，所有的样本均通过一个通用的映射投影到同一个流形上，而提出的基于多邻域保持嵌入的方法中，对每一个类别的训练样本集学习一个流形及其相应的投影矩阵。M-NPE算法分类学习得到每类数据最优低维流行。而单一流形降维后样本空间的低维流形结构扭曲嵌入空间的局部表征能力降低。因此，对足够的训练样本进行学习时，较之于单一流形学习的方法基于M-NPE方法的识别率有显著提高。

M-NPE算法的计算复杂度较高。在第一步训练过程中，学习多个流形需要花费更多的计算时间。从图 2所示的算法流程图中，可知，这个问题可以通过并行计算来克服。即对不同类别的数据同时学习。而训练算法中最耗时的部分是基于GA的最优维数的求解过程。离线搜索可使这个问题得到有效解决。

3 结语

多流形假设给数据分类提供了一种新的思路，直接将数据按照类别标记进行划分，认为每一个类对应于一个流形，对数据本身的分布情况没有深入探讨。当数据本身没有标记时，即在非监督情况下，如何通过多流形聚类算法得到多流形的分布模型，是今后值得探讨的问题。