面向局部线性回归分类器的判别分析方法

朱换荣，郑智超，孙怀江

（南京理工大学 计算机科学与工程学院，江苏 南京 210094）

维数约简是帮助我们理解数据特征结构的有效工具，被广泛地应用于人脸识别[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计算稀疏表示系数需要求解范数，所以花费的时间较多。而线性回归分类器[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的缺点，本文提出了面向局部线性回归分类器的判别分析方法(localityregularized linear regression classification based discriminant analysis，LLRC-DA)。LLRC-DA 根据LLRC的决策准则设计目标函数，通过最大化类间局部重构误差并最小化类内局部重构误差来寻找最优的特征子空间。在求解目标函数的过程中，本文利用投影矩阵与线性回归系数之间的关系，使用解析解表示线性回归系数，从而消除了回归系数对求解投影矩阵产生的影响。另外，在求解目标函数过程中使用了一种新的迹比优化方法，直接解决迹比问题而不是使用广义特征值分解的方法近似求解。文献[20]的研究显示，直接解决迹比问题是可行的并且比使用广义特征值分解效果更好。在本文提出的方法中，使用了正交投影来消除冗余信息，提高性能。本文在FERET、ORL人脸库上进行了实验，实验结果验证了算法的有效性。

1 局部线性回归分类器

2 LLRC-DA算法

2.1 LLRC-DA提出

LLRC-DA的目标是将样本投影到一个特征子空间，使得类内局部重构误差最小，同时类间局部重构误差最大。用表示优化投影矩阵，原始空间中的训练样本矩阵投影到维子空间为，即每个训练样本投影为，其中表示第i类的第个训练样本。线性回归系数是通过式(2)来计算得到的。

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

2.2 LLRC-DA优化

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

其中：

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

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像素像素。在实验之前，首先使用PCA方法将原始图像降到180维，然后在每类中选择前4幅图像作为训练集，剩余的作为测试集，最近邻类，每类中的最近邻个数，在FERET上的识别率如表1所列。

图1 FERET库中一个人的7幅图像Fig. 1 Seven images of a person from the FERET database

表1 FERET库上的识别率Table 1 Recognition accuracy when using the FERET database

通过表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像素像素。在实验之前，首先使用PCA方法将原始图像降到50维，然后在每类中选择前5幅图像作为训练集，剩余的所有图像作为测试集。

图2 ORL库中一个人的10幅图像Fig. 2 Ten images of a person from the ORL database

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

图3 LLRC-DA在不同k下的识别率Fig. 3 Recognition rate of LLRC-DA with varied k

图4 LLRC-DA在不同K下的识别率Fig. 4 Recognition rate of LLRC-DA with varied K

表2 ORL库上的识别率Table 2 Recognition accuracy when using the ORL database

4 结束语

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