维数约简是帮助我们理解数据特征结构的有效工具，被广泛地应用于人脸识别^[1-3]、图像检索^[4-5]、指纹认证^[6-7]、生物信息学^[8-9]、数据挖掘^[10-11]等。维数约简的目标是减少冗余、不相关的信息和噪声，同时保留数据的潜在结构和本征信息。文献[12]显示，虽然随着样本维数的增加，分类器的性能会逐步上升，但是过高的维数却会使分类器的性能急剧下降，甚至造成“维数灾难”问题。因此，维数约简对于分类具有重要的意义。在过去的几十年中，针对维数约简问题出现了各种不同的解决方案和算法，其中主成分分析^[13](principal component analysis，PCA)和线性判别分析^[14](linear discriminant analysis，LDA)是最具代表性的两个线性降维算法。PCA的思想是最大化投影空间中样本之间的差异。LDA的目标是找到一组投影轴，使得在投影空间中同类样本尽可能靠近，而不同类样本尽可能分开。LDA是一种监督算法，充分利用了样本的类别信息来发现数据的特征结构，因此在维数约简方面通常比PCA更加有效，但是LDA不能很好地处理非线性分类问题。流形学习^[15](manifold learning)是一种非线性的维数约简方法。流形算法的主要思想是学习高维空间中样本的局部邻域结构，并寻找能够保留这种流形结构的子空间，使得样本投影到子空间后有着较好的局部近邻关系。其中局部保持投影^[15](locality preserving projections，LPP)就是最常见的流形学习算法之一。LPP方法得到的投影矩阵，可以使样本在投影之后保留邻域结构。

近年来，基于表示的分类方法引起了人们的广泛关注，稀疏表示分类器^[16](sparse representation based classification，SRC)是最具代表性的基于表示的分类方法之一。SRC中测试样本用训练样本的稀疏线性组合来表示，然后计算测试样本与每类样本之间的重构误差，最终将测试样本分类到重构误差最小的类别。SRC表现出了良好的分类性能，但是由于SRC计算稀疏表示系数需要求解 ${l_1}$ 范数，所以花费的时间较多。而线性回归分类器^[17](linear regression classification，LRC)则很好地避免了这一问题。LRC假设同一类的样本处于相同的线性子空间中。因此LRC分别计算测试样本在不同类的子空间中的投影，然后通过计算最小重构误差来判别测试样本的类别。LRC利用最小二乘法估算回归系数，所以LRC是一个简单而有效的分类方法。然而，在许多现实应用中，样本通常表现出局部线性，而不是全局线性。于是Brown等^[18]提出了局部线性回归分类器(locality-regularized linear regression classification，LLRC)，将流形学习系统嵌入到LRC中，使用流形学习来扩展传统的LRC，从而提高分类精度。

为了防止过高的维数影响LLRC的分类性能并且保留数据的潜在结构，所以在使用原始数据时先进行降维处理。大多数的降维方法独立于分类器的决策准则，因此分类器往往不能有效地利用学习到的特征子空间。为了更好地将维数约简与特定的分类器相联系，根据分类器的决策准则来设计维数约简算法是很有必要的。于是，Huang等^[19]根据LLRC的决策准则提出了局部线性回归判别分析(locality-regularized linear regression discriminant analysis，LLRDA)。LLRDA根据LLRC的决策准则分别定义了类内局部重构误差和类间局部重构误差，然后使用最大特征值分解方法求解一个迹比问题以得到最优解。然而，在LLRDA算法中，线性回归系数在原始空间进行计算并且假定系数恒定，但是实际上回归系数与投影矩阵是相关的，不是独立的，在求解目标函数的过程中投影矩阵的改变会对回归系数产生影响，所以不能假定系数恒定。另外，LLRDA的目标函数是一个迹比问题，但是为了便于处理，LLRDA将迹比问题隐式地转换成了比迹问题，并用最大特征值分解方法进行求解，因而得到的结果会与原来的目标函数存在偏差。

为了克服LLRDA的缺点，本文提出了面向局部线性回归分类器的判别分析方法(locality-regularized linear regression classification based discriminant analysis，LLRC-DA)。LLRC-DA根据LLRC的决策准则设计目标函数，通过最大化类间局部重构误差并最小化类内局部重构误差来寻找最优的特征子空间。在求解目标函数的过程中，本文利用投影矩阵与线性回归系数之间的关系，使用解析解表示线性回归系数，从而消除了回归系数对求解投影矩阵产生的影响。另外，在求解目标函数过程中使用了一种新的迹比优化方法，直接解决迹比问题而不是使用广义特征值分解的方法近似求解。文献[20]的研究显示，直接解决迹比问题是可行的并且比使用广义特征值分解效果更好。在本文提出的方法中，使用了正交投影来消除冗余信息，提高性能。本文在FERET、ORL人脸库上进行了实验，实验结果验证了算法的有效性。

1 局部线性回归分类器

假设有 $n$ 个训练样本，共有 $C$ 类，其中第 $i$ 类有 ${n_i}$ 个训练样本，所以总共有 $\displaystyle\sum\limits_{i = 1}^C {{n_i}} = n$ 个样本。训练样本矩阵为 ${{X}} = \left[ {{{{X}}_1}\; {{{X}}_2} \cdots {{{X}}_C}} \right] \in {{\bf{R}}^{N \times n}}$ ，其中第 $i$ 类训练样本矩阵为 ${{{X}}_i}\; = \left[ {{{x}}_i^1 \;\;{{x}}_i^2\;\; \cdots \;\; {{x}}_i^{{n_i}}} \right] \in {{\bf{R}}^{N \times {n_i}}}$ ， $i = 1,2, \cdots ,$ $ C$ ， $N$ 表示样本维数。对于一个测试样本 ${{y}} \in {{\bf{R}}^{N \times 1}}$ ，可以通过 $k$ -最近邻算法计算出其在第 $i$ 类训练样本 ${{{X}}_i}$ 中的局部线性子集 ${{\tilde { X}}_i} = \left[ {{{x}}_i^1\; {{x}}_i^2 \cdots {{x}}_i^k} \right] \in $ $ {{\bf{R}}^{N \times k}}$ ，在 $k$ -最近邻算法中，通常使用欧氏距离作为距离度量方法，则 ${{y}}$ 的线性表示记作：

${{y}} = {{\tilde { X}}_i}{{\tilde { \beta }}_i}$

(1)

式中： ${{\tilde { \beta }}_i} \in {{\bf{R}}^{k \times 1}}$ 表示第 $i$ 类样本的线性回归系数， ${{\tilde { \beta }}_i}$ 可以使用最小二乘估计来计算：

${{\tilde { \beta }}_i} = {\left( {{\tilde { X}}_i^{\rm T}{{{\tilde { X}}}_i}} \right)^{ - 1}}{\tilde { X}}_i^{\rm T}{{y}}$

(2)

根据线性回归系数 ${{\tilde { \beta }}_i}$ ，测试样本 ${{y}}$ 在第 $i$ 类样本上的线性重构可以表示为

${{{\hat y}}_i} = {{\tilde { X}}_i}{\left( {{\tilde { X}}_i^{\rm T}{{{\tilde { X}}}_i}} \right)^{ - 1}}{\tilde { X}}_i^{\rm T}{{y}}$

(3)

根据LLRC的假设，如果重构样本 ${{{\hat y}}_i}$ 和测试样本 ${{y}}$ 的距离最近，则 ${{y}}$ 应该属于第 $i$ 类，所以LLRC的决策准则为

$l\left( {{y}} \right) = \mathop {\min }\limits_i \left\| {{{y}} - {{{\tilde { X}}}_i}{{\left( {{\tilde { X}}_i^{\rm T}{{{\tilde { X}}}_i}} \right)}^{ - 1}}{\tilde { X}}_i^{\rm T}{{y}}} \right\|_2^2$

(4)

2 LLRC-DA算法 2.1 LLRC-DA提出

LLRC-DA的目标是将样本投影到一个特征子空间，使得类内局部重构误差最小，同时类间局部重构误差最大。用 ${{A}} \in {{\bf{R}}^{N \times d}}(d < N)$ 表示优化投影矩阵，原始空间中的训练样本矩阵 ${{X}} \in {{\bf{R}}^{N \times n}}$ 投影到 $d$ 维子空间为 ${{Y}} = {{{A}}^{\rm T}}{{X}} \in {{\bf{R}}^{d \times n}}$ ，即每个训练样本 ${{x}}_i^j \in {\bf{R}^N}$ 投影为 ${{y}}_i^j = {{{A}}^{\rm T}}{{x}}_i^j \in {{\bf{R}}^d}$ ，其中 ${{x}}_i^j$ 表示第 $i$ 类的第 $j$ 个训练样本。线性回归系数 ${\tilde { \beta }}$ 是通过式(2)来计算得到的。

从式(4)可以看出，如果 ${{y}}_i^j$ 用第 $i$ 类训练样本的局部线性子集来表示，可以得到最小的重构误差，则 ${{y}}_i^j$ 可以被LLRC正确分类，所以本文希望找到一个特征子空间，在这个子空间中， ${{y}}_i^j$ 用第 $i$ 类训练样本表示时的局部重构误差尽可能地小，而用其他类训练样本表示时的局部重构误差尽可能地大。为了达到这样的目标，本文定义了类内局部重构误差和类间局部重构误差。其中，类内局部重构误差为

$\begin{aligned} & \qquad \qquad \quad \frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\left\| {{{y}}_i^j - {\tilde { Y}}_i^j{\tilde { \beta }}_i^j} \right\|_2^2} } {\rm{ = }} \\ & \quad \qquad {\rm{tr}}\left( {\frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\left( {{{y}}_i^j - {\tilde { Y}}_i^j{\tilde { \beta }}_i^j} \right){{\left( {{{y}}_i^j - {\tilde { Y}}_i^j{\tilde { \beta }}_i^j} \right)}^{\rm T}}} } } \right){\rm{ = }} \\ & \quad {\rm{tr}}\left( {\frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\left( {{{{A}}^{\rm T}}{{x}}_i^j - {{{A}}^{\rm T}}{\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right){{\left( {{{{A}}^{\rm T}}{{x}}_i^j - {{{A}}^{\rm T}}{\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right)}^{\rm T}}} } } \right){\rm{ = }} \\ & {\rm{tr}}\left( {\frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {{{{A}}^{\rm T}}\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right){{\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right)}^{\rm T}}{{A}}} } } \right) = {\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}}} \right) \\ \end{aligned} $

(5)

式中： ${{{S}}_w}{\rm{ = }}\dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^C {\displaystyle\sum\limits_{j = 1}^{{n_i}} {\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right){{\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right)}^{\rm T}}} } $ 是类内局部重构散列矩阵； ${\tilde { X}}_i^j$ 是通过 $k$ -最近邻算法计算出的 ${{x}}_i^j$ 在第 $i$ 类训练样本 ${{{X}}_i}$ 中的局部线性子集； ${\tilde { \beta }}_i^j$ 表示 ${{x}}_i^j$ 用第 $i$ 类样本的局部线性子集 ${\tilde { X}}_i^j$ 表示时的线性回归系数。

同样地，在特征子空间中，可以计算类间局部重构误差，即

$ \begin{aligned} & \qquad\qquad \frac{1}{{nK}}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {\left\| {{{y}}_i^j - {\tilde{ Y}}_{im}^j{\tilde{ \beta }}_{im}^j} \right\|_2^2} } } {\rm{ = }}\\ & \quad{\rm{tr}}\left( {\frac{1}{{nK}}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {\left( {{{y}}_i^j - {\tilde{ Y}}_{im}^j{\tilde{ \beta }}_{im}^j} \right){{\left( {{{y}}_i^j - {\tilde{ Y}}_{im}^j{\tilde{ \beta }}_{im}^j} \right)}^{\rm T}}} } } } \right) = \\ & {\rm{tr}}\left( {\frac{1}{{nK}}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {{{{A}}^{\rm T}}\left( {{{x}}_i^j - {\tilde{ X}}_{im}^j{\tilde{ \beta }}_{im}^j} \right){{\left( {{{x}}_i^j - {\tilde{ X}}_{im}^j{\tilde{ \beta }}_{im}^j} \right)}^{\rm T}}{{A}}} } } } \right) = \\ & \qquad\qquad\qquad\qquad\quad{\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_b}{{A}}} \right) \end{aligned} $

(6)

式中： ${{{S}}_b} = \dfrac{1}{{nK}}\displaystyle\sum\limits_{i = 1}^C {\displaystyle\sum\limits_{j = 1}^{{n_i}} {\displaystyle\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {\left( {{{x}}_i^j - {\tilde{ X}}_{im}^j{\tilde{ \beta }}_{im}^j} \right){{\left( {{{x}}_i^j - {\tilde{ X}}_{im}^j{\tilde{ \beta }}_{im}^j} \right)}^{\rm T}}} } }$ 是类间局部重构散列矩阵； $l({{x}}_i^j)$ 表示与 ${{x}}_i^j$ 欧氏距离最近的 $K$ 个类，其中不包括第 $i$ 类，即 $i \notin l({{x}}_i^j)$ ，而 $m \in l({{x}}_i^j)$ 则表示第 $m$ 类是 ${{x}}_i^j$ 的 $K$ 近邻类； ${\tilde { X}}_{im}^j$ 是通过 $k$ -最近邻算法计算出的 ${{x}}_i^j$ 在第 $m$ 类训练样本 ${{{X}}_m}$ 中的局部线性子集； ${\tilde { \beta }}_{im}^j$ 表示 ${{x}}_i^j$ 用第 $m$ 类样本的局部线性子集 ${\tilde { X}}_{im}^j$ 表示时的线性回归系数。

为了使LLRC-DA表现出更好的性能，本文使用正交投影，即 ${{{A}}^{\rm T}}{{A}} = {{I}}$ 。因为投影矩阵是正交的，所以可以消除大量的冗余信息，得到更简洁的特征子空间。在特征子空间最小化类内局部重构误差同时最大化类间局部重构误差，可以得到以下目标函数：

${{{A}}^ * } = \arg \mathop {\rm min}\limits_{{A}} \frac{{{\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}}} \right)}}{{{\rm{tr}}({{{A}}^{\rm T}}{{{S}}_b}{{A}})}}\;\;\;\;{\rm{s}}{\rm{.t}}{\rm{.}}\begin{array}{*{20}{c}} {} \end{array}{{{A}}^{\rm T}}{{A}} = {{I}}$

(7)

2.2 LLRC-DA优化

LLRC-DA是一个迹比最小化问题，通常此类问题可以使用广义特征值分解的方法近似求解。最近的研究显示^[20]，直接解决迹比问题是可行的并且比使用广义特征值分解效果更好。

假设目标函数存在一个最小值 $\,{\rho ^ * }$ ，当投影矩阵为 ${{{A}}^ * }$ 时可以达到这个最小值，因此对于满足式(7)的任意投影矩阵 ${{A}}$ ，有以下关系：

$\frac{{{\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}}} \right)}}{{{\rm{tr}}({{{A}}^{\rm T}}{{{S}}_b}{{A}})}} \geqslant {\rho ^ * }$

(8)

因此可以得到

${\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}}} \right) - {\rho ^ * }{\rm{tr}}({{{A}}^{\rm T}}{{{S}}_b}{{A}}) \geqslant 0$

(9)

为了优化目标函数，本文定义以下函数：

$f(\rho ) = \mathop {\min }\limits_{{A}} {\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}} - \rho {{{A}}^{\rm T}}{{{S}}_b}{{A}}} \right)$

(10)

式中 $f(\,\rho )$ 具有引理1中的属性，已经在文献[21-22]中得到证明。

引理1　1) $f$ 是关于 $\,\rho $ 的一个非增函数；2)当 $\,\rho {\rm{ = }}{\rho ^ * }$ 时， $f(\,\rho ) = 0$ 。

由上述 $f(\,\rho )$ 的属性可知， $f$ 是关于 $\,\rho $ 的一个非增函数。对于函数 $f(\,\rho )$ ，当 $\,\rho $ 为负数或者较小的正数时， $f(\,\rho ) > 0$ ；当 $\,\rho $ 为较大的正数时， $f(\,\rho ) < 0$ ，所以 $\,{\rho ^ * }$ 一定存在，因此可以通过交替迭代更新得到 $\,{\rho ^ * }$ 和相对应的 ${{{A}}^ * }$ 。

首先保持 $\,\rho $ 不变并更新 ${{A}}$ ，然后保持 ${{A}}$ 不变并更新 $\,\rho $ 。LLRDA中线性回归系数 $\,{\tilde { \beta }}$ 在更新 ${{A}}$ 之前进行计算，并且在接下来的计算过程中固定不变。但是实际上 $\,{\tilde { \beta }}$ 与 ${{A}}$ 是相关的，不是独立的， $\,{\tilde { \beta }}$ 的更新会对 ${{A}}$ 产生影响。为了解决这个问题，利用 $\,{\tilde { \beta }}$ 与 ${{A}}$ 之间的关系，使用解析解形式：

${\tilde { \beta }} = {\left( {{\tilde { X}}_i^{\rm T}{{A}}{{{A}}^{\rm T}}{{{\tilde { X}}}_i}} \right)^{ - 1}}{\tilde { X}}_i^{\rm T}{{A}}{{{A}}^{\rm T}}{{y}}$

(11)

来消除 $\,{\tilde { \beta }}$ 的影响。

1)固定 ${{A}}$ ，更新 $\,\rho $

对于一个给定的 $\,\rho $ ，用 ${{A}}(\,\rho )$ 表示式(10)的解。固定 ${{A}}$ ，对 $\,\rho $ 进行求导：

${f^{'}}(\,\rho ) = - {\rm{tr}}\left( {{{A}}{{(\,\rho )}^{\rm T}}{{{S}}_b}{{A}}(\rho )} \right)$

(12)

已知 ${{A}}(\,\rho )$ ，可以通过 $\,{\rho _{{\rm{new}}}} = \rho - {\eta _1}\dfrac{{f(\rho )}}{{{f^{'}}(\rho )}}$ 得到目标函数的根，其中 ${\eta _1}$ 表示步长。

2)固定 $\,\rho $ ，更新 ${{A}}$

存在约束条件 ${{{A}}^{\rm T}}{{A}} = {{I}}$ 的情况下，可以通过求解下面问题来求解 ${{A}}$ 。

$ \begin{aligned} & \qquad\mathop {\min }\limits_{{A}} J({{A}}) = \mathop {\min }\limits_{{A}} {\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}} - \rho {{{A}}^{\rm T}}{{{S}}_b}{{A}}} \right) = \\ & \qquad \quad \mathop {\min }\limits_{{A}} \left( {{\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_w}{{A}}} \right) - \rho {\rm{tr}}\left( {{{{A}}^{\rm T}}{{{S}}_b}{{A}}} \right)} \right) = \\ & \mathop {\min }\limits_{{A}} \left( {\frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {J_i^{{j^{({\rm{w}})}}}({{A}})} } - \frac{\rho }{{nK}}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {J_{im}^{{j^{({\rm{b}})}}}({{A}})} } } } \right)\\ & {\rm{s}}{\rm{.t}}{\rm{.}}\begin{array}{*{20}{l}} {} \end{array}{{{A}}^{\rm T}}{{A}} = {{I}} \end{aligned} $

(13)

其中：

$ \begin{aligned} & J_i^{{j^{({\rm{w}})}}}({{A}}) = {\rm{tr}}\left( {{{{A}}^{\rm T}}\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right){{\left( {{{x}}_i^j - {\tilde { X}}_i^j{\tilde { \beta }}_i^j} \right)}^{\rm T}}{{A}}} \right)\\ & J_{im}^{{j^{({\rm{b}})}}}({{A}}) = {\rm{tr}}\left( {{{{A}}^{\rm T}}\left( {{{x}}_i^j - {\tilde { X}}_{im}^j{\tilde { \beta }}_{im}^j} \right){{\left( {{{x}}_i^j - {\tilde { X}}_{im}^j{\tilde { \beta }}_{im}^j} \right)}^{\rm T}}{{A}}} \right) \end{aligned} $

因为目标函数要在正交约束条件下进行求解，所以首先要对其进行求导。 $J({{A}})$ 对 ${{A}}$ 求导得

$ \frac{{{\rm d}J({{A}})}}{{{\rm d}{{A}}}} = \frac{1}{n}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\frac{{{\rm d}J_i^{{j^{({\rm w})}}}({{A}})}}{{{\rm d}{{A}}}}} } - \frac{\rho }{{nK}}\sum\limits_{i = 1}^C {\sum\limits_{j = 1}^{{n_i}} {\sum\limits_{m \in l\left( {{{x}}_i^j} \right)} {\frac{{{\rm d}J_{im}^{{j^{({\rm b})}}}({{A}})}}{{{\rm d}{{A}}}}} } } $

(14)

对于每一个 ${{x}}_i^j$ ，可以计算 $J_i^{{j^{({\rm{w}})}}}({{A}})$ 的导数，为了方便表示，用 ${{x}}$ 来替代 ${{x}}_i^j$ ，用 ${\tilde { X}}$ 来替代 ${\tilde { X}}_i^j$ ：

$ \frac{{{\rm{d}}J_i^{{j^{({\rm{w}})}}}({{A}})}}{{\rm{d}}{{A}}} = (2{{x}}{{{x}}^{\rm T}} + 6{{G}}{{{G}}^{\rm T}}{\rm{ + }}{{R}} + {{{R}}^{\rm T}} - {{H}} - {{{H}}^{\rm T}}){{A}} $

(15)

式中： ${{G}} = {\tilde { X}}{\left( {{{{\tilde { X}}}^{\rm T}}{{A}}{{{A}}^{\rm T}}{\tilde { X}}} \right)^{ - 1}}{{\tilde { X}}^{\rm T}}{{A}}{{{A}}^{\rm T}}{{x}}$ ， ${{R}} = 2({{x}} - {{G}}){{{G}}^{\rm T}}$ ， ${{H}} = 4{{G}}{{{x}}^{\rm T}}$ 。

同样地，可以计算 $J_{im}^{{j^{({\rm{b}})}}}({{A}})$ 的导数，为了方便表示，用 ${{x}}$ 来替代 ${{x}}_i^j$ ，用 ${\tilde { X}}$ 来替代 ${\tilde { X}}_{im}^j$ ：

$\frac{{{\rm d}J_{im}^{{j^{({\rm{b}})}}}({{A}})}}{{\rm{d}}{{A}}} = (2{{x}}{{{x}}^{\rm T}} + 6{{G}}{{{G}}^{\rm T}}{\rm{ + }}{{R}} + {{{R}}^{\rm T}} - {{H}} - {{{H}}^{\rm T}}){{A}}$

(16)

式中： ${{G}} = {\tilde { X}}{\left( {{{{\tilde { X}}}^{\rm T}}{{A}}{{{A}}^{\rm T}}{\tilde { X}}} \right)^{ - 1}}{{\tilde { X}}^{\rm T}}{{A}}{{{A}}^{\rm T}}{{x}}$ ， ${{R}} = 2({{x}} - {{G}}){{{G}}^{\rm T}}$ ， ${{H}} = 4{{G}}{{{x}}^{\rm T}}$ 。

求完导数之后，定义一个斜对称矩阵 ${{M}}$ ：

${{M}} = \frac{{{\rm{d}}J({{A}})}}{{\rm{d}}{{A}}}{{{A}}^{\rm T}} - {{A}}{(\frac{{{\rm{d}}J({{A}})}}{{\rm{d}}{{A}}})^{\rm T}}$

(17)

然后，可以通过Crank-Nicolson-like方法，得到更新后的投影矩阵 ${{{A}}_{{\rm{new}}}}$ 。

${{{A}}_{{\rm{new}}}} = {{A}} - \frac{\tau }{2}{{M}}\left( {{{A}} + {{{A}}_{{\rm{new}}}}} \right)$

(18)

式中： $\tau $ 表示步长，可以通过解析解的形式得到 ${{{A}}_{{\rm{new}}}} = {\left( {{{I}} + \dfrac{\tau }{2}{{M}}} \right)^{ - 1}}\left( {{{I}} - \dfrac{\tau }{2}{{M}}} \right){{A}}$ ， ${{I}}$ 是单位矩阵，通过这种方法求得的 ${{{A}}_{{\rm{new}}}}$ 有很好的特性^[23]，即 ${{A}}_{{\rm{new}}}^{\rm T}{{{A}}_{{\rm{new}}}} = $ ${{{A}}^{\rm T}}{{A}} $ 。

通过前面对LLRC-DA的描述，可以得到LLRC-DA的算法：

输入　训练样本矩阵 ${{X}}$ ，特征子空间维数 $d$ ，最近邻个数 $k$ ，最近邻类 $K$ ，最大迭代次数 ${t_1}$ 、 ${t_2}$ ，步长 ${\eta _1}$ 、 $\tau $ ；

输出　投影矩阵 ${{{A}}_{{\rm{LLRC - DA}}}}$ 。

1)如果原始样本的维数大于样本总数，先使用PCA方法将原始样本投影到低维子空间，其中 ${{{A}}_{\rm{PCA}}}$ 是使用PCA得到的投影矩阵；

2)固定 $\,\rho $ ，对于每个样本，计算它在每个类中的 $k$ 个最近邻，使用 ${{{A}}_{{\rm{new}}}} = {\left( {{{I}} + \dfrac{\tau }{2}{{M}}} \right)^{ - 1}}\left( {{{I}} - \dfrac{\tau }{2}{{M}}} \right){{A}}$ 来更新 ${{A}}$ ，直到收敛或者达到迭代次数 ${t_1}$ ；

3)固定 ${{A}}$ ，对于每个样本，计算它在每个类中的 $k$ 个最近邻，使用 $\,{\rho _{{\rm{new}}}} = \rho - {\eta _1}\dfrac{{f(\rho )}}{{{f^{'}}(\rho )}}$ 来更新 $\,\rho $ 。

4)重复2)、3)，直到 $f(\rho ) = 0$ 或者达到迭代次数 ${t_2}$ 。

5)最终的投影矩阵为 ${{{A}}_{{\rm{LLRC - DA}}}} = {{{A}}_{{\rm{PCA}}}}{{A}}$ 。

3 实验

为了验证LLRC-DA的有效性，本文分别在FERET和ORL人脸库上进行实验，并与PCA^[13]、LDA^[14]、LPP^[15]、RDA^[24]和LLRDA^[19]等先进的维数约简算法进行比较。在维数约简之后，分别使用NNC^[25]、MDC^[26]、LRC^[17]和LLRC^[18]分类器来比较每种维数约简方法在不同分类器下的分类性能。本文中的实验通过MATLAB编程实现，硬件环境为酷睿i7处理器、主频2.6 GHz、内存8 GB。

3.1 FERET人脸库上的实验

FERET人脸库包含1 400幅人脸图像，共计200类，其中每类7幅图像，包括两张面部表情图，两张左侧图，两张右侧图和一张光照图，图1所示为一个人的7幅图像。实验中所有的图像均被裁剪为 80像素 $ \times 80$ 像素。在实验之前，首先使用PCA方法将原始图像降到180维，然后在每类中选择前4幅图像作为训练集，剩余的作为测试集，最近邻类 $K = 101$ ，每类中的最近邻个数 $k = 3$ ，在FERET上的识别率如表1所列。

通过表1可以看出：1)与PCA、LPP等非监督学习方法相比，监督学习的降维方法明显具有更好的性能，因为监督学习方法利用了类别信息，使识别率显著提高；2)同一种降维方法，在不同的分类器上的实验结果不同，甚至会有很大差异，例如LLRC-DA在MDC与LLRC这两种分类器上的识别率相差很大，这也说明选择合适的分类器对于识别性能至关重要；3)在所有的降维方法与分类器的组合中，LLRC-DA与LLRC的组合具有最高的识别率，由于使用了LLRC的决策准则，因此和其他降维方法相比，LLRC-DA学习的特征子空间与LLRC更加契合；4)LLRC-DA在LRC、LLRC上的识别率均明显高于LLRDA，证明本文提出的方法对于提高分类率是有效的。

3.2 ORL人脸库上的实验

ORL人脸库的400幅图像来自40个人，其中每人10幅图像，图像在不同条件下进行采集，如光照、面部表情、面部细节等，图2所示为一个人的10幅图像。实验中所有的图像均压缩成 56像素 $ \times 46$ 像素。在实验之前，首先使用PCA方法将原始图像降到50维，然后在每类中选择前5幅图像作为训练集，剩余的所有图像作为测试集。

在ORL人脸库上，本文对LLRC-DA在不同参数下的性能进行评估。首先，对每类中的最近邻参数 $k$ 进行实验，使用NNC、MDC、LRC、LLRC分类器，固定 $K = 21$ ， $k$ 的值为1~4，实验结果如图3所示。从图3中可以看出，在NNC、LRC、LLRC分类器下， $k$ 的取值为3时，识别率最高，这表明利用样本之间的邻域结构，选择 $k$ 而不是全部样本来表示测试样本，可以提高识别性能。

接着，对近邻类参数 $K$ 进行实验，使用NNC、MDC、LRC、LLRC分类器，选择 $k = 3$ ， $K$ 的值为3~39，实验结果如图4所示。从图4中可以看出， $K$ 为20时，各分类器均可取得较高的识别率。

最后，比较在不同分类器下LLRC-DA的性能，设置 $K = 21$ ， $k = 3$ ，在ORL上的识别率如表2。通过表2可以看出：1)在所有的降维方法与分类器的组合中，LLRC-DA与LLRC的组合具有最高的识别率，证明本文提出的方法是有效的；2) RDA与LRC这一组合也有着较高的识别率，这是因为RDA是采用LRC决策准则产生的，证明根据分类器的决策准则来设计维数约简算法是很有必要的。然而它的识别率依然比LLRC-DA与LLRC组合的低，原因是LLRC决策准则考虑了数据的邻域结构，使用 $k$ 个最近邻而不是全部样本，这对于提高识别率是有效的。

4 结束语

本文提出了面向局部线性回归分类器的判别分析方法LLRC-DA，根据LLRC的决策准则设计目标函数，通过最大化类间局部重构误差并最小化类内局部重构误差来寻找最优的特征子空间。本文利用了投影矩阵与线性回归系数之间的关系，消除了线性回归系数的影响，使得目标函数只和投影矩阵相关。LLRC-DA通过对投影矩阵添加正交约束来消除冗余信息，并得到更好的特征子空间。相比于传统算法使用最大特征值分解来求解迹比问题，本文利用了一种新的迹比优化算法来有效地求解投影矩阵。本文在FERET、ORL人脸库上进行了实验，与先进的维数约简算法进行了比较，实验结果表明，本文提出的方法具有更好的性能。对于LLRC-DA中的最近邻参数 $k$ 的选择问题，将寻找合适的参数选择技术来确定 $k$ 值。在接下来的工作中，打算引入核方法来研究改进本文的方法。