重加权稀疏主成分分析算法及其在人脸识别中的应用

李东博，黄铝文

（西北农林科技大学信息工程学院，陕西杨凌712100）

（*通信作者电子邮箱huanglvwen@nwsuaf.edu.cn）

0 引言

随着现代科学技术的不断发展，尤其是互联网技术的飞速发展，生物特征数据［1］、基因表达数据［2］、多媒体数据［3］等数据的维数越来越高，海量数据的产生为生活带来了诸多便利，但是也为如何处理海量数据，挖掘其中的主要信息，寻找数据的主要特征带来了困难［4］。主成分分析（Principal Component Analysis，PCA）算法是处理高维数据，提取其主要特征的一个重要方法，该算法通过使用特征值分解、保留原始数据最大方差的方式实现原始数据的维度降低，从而达到提取原始数据特征的目的［5］。但是主成分分析算法存在一个重要的问题:主成分分析算法所得到的主成分不够稀疏，拥有较多的非零元，主成分向量可以保留原始高维数据中的主要特征，但是所提取的主成分向量通常是稠密的，即大部分分量是非零值［6］。在最优化领域之中，Xu等［7］提出了一个重加权ℓ1最优化框架，此框架使用重加权方法处理ℓ1最优化问题，其与传统ℓ1最优化框架相比，可以获得更加稀疏的解，有着更好的性能效果，证明了重加权方法的有效性。

本文针对主成分分析算法所获得的主成分不够稀疏的问题，将重加权方法引入到主成分分析问题的解决之中，对主成分分析算法进行优化，得到了一个新的提取高维数据特征的方法，即重加权稀疏主成分分析算法，本文提出的方法有以下几项创新:

1）通过将重加权的思想引入主成分分析算法的处理之中，通过使用交替最小化算法、奇异值分解算法、最小角回归算法等方式实现了对所提出方法的求解，以实现提取高维数据特征时可以获取更多的稀疏解。

2）本文通过使用基于K折交叉验证的人脸检测实验比较了主成分分析算法和重加权稀疏主成分分析算法性能差异，并针对手写数字识别这一问题使用本文方法进行求解，获得了良好的实验效果，证明了该方法的优异性。

1 相关工作

主成分分析是一个高效、便捷的高维数据降维算法，为得到更加稀疏的解，国内外学者都进行了广泛的研究。Jolliffe等［8］引入了稀疏主成分分析算法，并提供了一个简单的基于LASSO（Least Absolute Shrinkage and Selection Operator）的方法来获得稀疏向量。Zou 等［9］在2006 年将稀疏主成分分析（Sparse Principal Component Analysis，SPCA）作为一个回归问题并与Elastic Net 回归模型相结合，然后对之进行了求解。然而，这两种方法都涉及直接求解非凸问题，因此遭遇到局部最小值问题。Moghaddam等［10］采用组合方法求解SPCA问题，同时采用贪婪策略获得稀疏解。D'Aspremont 等［11］提出了稀疏PCA 问题的半定规划（Semi-Definite Programming，SDP）松弛，由于稀疏主成分分析是一个难以解决的非凸优化问题，因此难以有效的求解。

Jolliffe使用LASSO算法对PCA算法进一步优化，提出了主成分分析算法的一个优化算法，即SCoTLASSO（Simplified Component Technique LASSO）算法，在该算法中增加ℓ1约束来提高稀疏性。但是SCoTLASSO是非凸的，Jolliffe等［8］提出了一种简单的投影梯度下降方法来解决这个问题，即将“ℓ1约束”作为惩罚函数移入目标。尽管SCoTLASSO 成功找到稀疏向量，但就其解释的方差量而言，其性能已经被发现比其他方法差。

SCoTLASSO 算法还有一个缺点就是可能会陷入局部最佳状态，这将会导致需要重新计算以获得更适合的解决方案。为获取更加优异的解，Zou 等［12］首次将PCA 表示为回归类型问题，然后可以通过适当的ℓ1惩罚来获取稀疏解，提出了一种新的解决算法，即稀疏主成分分析（Sparse Principal Component Analysis，SPCA）算 法。SPCA 的 目 标 函 数 比SCoTLASSO 更加复杂，但其结果也更加稀疏，因此SPCA 算法被认为比SCoTLASSO 算法更加有效。在Pitprops 数据集中，SPCA 得到的最终结果比SCoTLASSO 更稀疏（总共分别为18个非零解和47 个非零解），并且在更大数据集中的方差超过了SCoTLASSO的方差（分别为75.8%和69.3%）。

SPCA 算法中存在的一个问题是其所提取的主成分对初始参数及主成分的个数敏感，且主成分之间存在线性相关关系。因此，Moghaddam 等［10］采用组合方法来处理稀疏PCA，并提出了一种新的算法GSPCA（Greedy Sparse PCA）。该算法采用贪婪策略来获取稀疏解，贪婪策略获得的解决方案可能不是全局最优的，但将是局部最优的，即对于其支持集合最优。

D'Aspremont 等［11］提出了一个通过SDP 方法的凸松弛来获取稀疏解，其稀疏性比SPCA 算法和SCoTLASSO 好，但是其存在一个明显的缺点，即该算法只能解决维数小于100 的情况。从经验上看，该方法被认为比SPCA 表现更好，可以与GSPCA 相媲美。在Pitprops 数据集上，它产生的解决方案比SPCA 更稀疏（分别总共有12 个非零解和18 个非零解），并且其数据的变化略大于SPCA的数据变化。

SPCA算法中通常使用ℓ2范数实现方差最大化，但却很少有学者特意研究该算法的鲁棒性问题。因此，Meng等［13］将传统SPCA算法之中的ℓ2范数用ℓ1范数进行替换，对SPCA算法进行优化处理，以期获得更加稀疏的解。该算法从理论上证实了与传统的一些稀疏主成分分析算法相比，该算法的运行速度更快，更易于实现并且可以实现局部最优收敛的效果。通过使用人工合成数据与人脸重建实验验证了新算法对原始数据中存在的异常值和噪声数据的鲁棒性，从而证明了该算法的有效性。但是该算法仍存在一个较大的缺点，即该算法的解只是近似最优解而非严格的最优解，因此该算法还需要进一步完善。

2013 年，Luss 等［14］对常见的稀疏主成分分析算法进行归纳总结，按所采用优化方法的不同将之分为五种形式:基于ℓ1约束的PCA 优化问题；基于ℓ0惩罚的PCA 优化问题；基于ℓ1惩罚的PCA 优化问题；基于ℓ0惩罚近似的PCA 优化问题；凸松弛问题。这五种形式又都可转化为凸函数最大化问题，根据这些性质Luss 等提出了一个名为ConGradU（Conditional Gradient Union）的算法框架，该框架统一了各种不同的算法，并且可以使用其推导出新的算法。在具体的实验中使用了美国国情咨文数据验证该算法，实验结果表明该算法可以通过数据内容来辨别出不同的总统并可提取出相应的关键词［15］。

Papailiopoulos 等［16］在不完全-秩矩阵的稀疏主成分研究的基础之上提出了通过低秩近似的新的稀疏主成分分析算法，即通过使用扫描协方差矩阵的低维特征子空间的方法来提取主成分。该算法首先计算原始数据矩阵的特征向量，然后在其子空间中寻找前k级具有最大解释方差的稀疏向量。该算法的一大特点是若矩阵特征值衰减的速度越快，则算法的效果越好；若实验中的协方差矩阵特征值根据幂律衰减，则可在多项式时间内使用近似算法实现任意精度的实验结果。

Qi 等［17］通过使用ℓ1范数与ℓ2范数的凸组合来代替传统特征提取方法中的ℓ2范数，构建了一个迭代算法框架来处理优化问题。该算法可以成功地获取原始数据中的不相关的主成分，并可以提取相互正交的载荷，最终可实现使用较为稀疏的主成分获得高解释方差的目标。实验中使用Pitprops 数据集与美国国立癌症研究所（National Cancer Institute，NCI）细胞系数据集，并与常见的SPCA 算法、SCoTLASSO 算法以及sPCA-rSVD（sparse PCA via regularized SVD）等稀疏PCA 算法的实验效果进行了对比分析，实验结果表明新算法的性能与其他算法相比有所提高。

2 重加权稀疏主成分分析算法

2.1 重加权ℓ1最优化框架

ℓ1最优化问题的使用最早可以追溯到1973 年［18］，其在反射地震学、信号恢复和图像处理等领域中都有着广泛的应用。ℓ1最优化问题起源于ℓ0最优化问题，ℓ0最优化问题可表述为:假设给定一个m×n矩阵A和一个非零向量b，其中m≤n，求解Ax=b的最稀疏解，其数学形式如下所示:

步骤1 首先根据式（4）所示主成分分析算法模型使用奇异值分解方法计算矩阵X的前d个主成分向量[α1，α2，…，αk]，X为原始数据所构成的矩阵，d为求解时所设置的一个常量值。

步骤2 将矩阵P初始化为步骤1 中所计算出来的主成分向量，P=[α1，α2，…，αk]。

步骤3 根据所给定的矩阵P，使用LARS-EN 算法求解式（11），得到矩阵P=[β1，β2，…，βk]。

步骤4 根据计算出的矩阵Q=[α1，α2，…，αk]，根据式（12）使用奇异值分解更新矩阵P。

步骤5 重复步骤3、4直至终止条件满足，将最终得到的结果。

3 实验设计与分析

3.1 人脸识别

本次实验中使用的人脸数据集为OLR（Olivetti Research Laboratory）数据集，该数据集由剑桥大学计算机实验室所采集，共包含40个不同的人脸，每人有10张不同的图像，图像大小为92×112像素，共400张图像。数据集包含不同时间段、不同光照、不同面部表情（开/闭眼，微笑/不微笑）和不同面部细节（眼镜/没有眼镜）下的人脸图像。实验中使用K 折交叉验证进行实验，将每个人的10 张图像划分为五组，每组数据分别做一次测试集，其余四组作为训练集，使用所获得的五组数据的平均值最终的结果，划分示意图如图1所示。

主成分分析算法遵循最大方差理论，将方差作为衡量降维后数据蕴含原始信息量多少的指标，本文算法同样遵循该理论，因此为测试本文所提出算法和主成分分析算法之间的性能差异，研究稀疏优化后算法的性能变化，实验中以识别准确率和降维后数据总方差作为观测指标，使用控制变量法分别控制零元的个数和降维维数，以此观测不同条件下识别准确率和方差的变化情况。

图1 K折交叉验证示意图Fig. 1 K-fold cross-validation diagram

实验中首先选取每个人物的8张照片作为匹配集，匹配集中共320张图片，将匹配集中的图片使用重加权稀疏主成分算法和主成分分析算法进行降维处理，并获取数据降维之后的方差，之后选取需要识别的人脸照片，将待识别照片使用同样的方法进行降维，最后将降维后的照片在匹配集中通过最小距离法进行匹配，从而实现人脸识别的目的。其中识别准确率按照测试集中所有被正确识别的图片数目占比进行计算，实验中分别将图片维数控制在10，20，30，40，50，60，70，80，90和100，在每一维度下分别控制零元的个数为0，10，20，30，40，50，100，150，以此观察对应的识别准确率和总方差，如表1和表2所示。

从表1和表2中可以观察出，本文所采用的方法在OLR人脸数据集中取得了不错的实验结果，最高识别率达到了95.6%，平均识别准确率达到95.1%，同时从表2中可以看出当维数控制在100维时，使用本文方法进行降维后的数据中总方差达到了90.2%左右，说明降维后的数据中已经包含了原始数据中的大部分信息，从而也证明了本文方法的有效性。

表1 不同维度不同零元下识别准确率 单位：%Tab. 1 Recognition accuracy under different dimensions and different zero elements unit:%

表2 不同维度不同零元下降维方差 单位：%Tab. 2 Dimensionality reduction variance under different dimensions and different zero elements unit:%

为更加清晰地观察本文算法，即重加权稀疏主成分分析（Reweighted Sparse Principal Component Analysis，RSPCA）算法与传统主成分分析（PCA）算法的差别，分别选取了10 维、20 维、50 维、100 维四个维度下，重加权稀疏主成分分析算法和传统主成分分析算法在不同零元个数下的识别准确率对比，如图2所示。

图2 不同维数下PCA算法与RSPCA算法识别准确率对比Fig. 2 Recognition accuracy comparison of PCA algorithm and RSPCA algorithm under different dimensions

从图2 中可以观察到，本文所使用的方法拥有着不弱于传统方法的表现。如图2（a）所示，当零元个数在200以内时，本文所使用方法在获得了更稀疏解的基础上仍然拥有着和传统方法相近的识别效果，当零元个数超过400 时，识别效果开始慢慢下降，最差的识别效果也达到近80%的识别准确率。当维数逐渐上升时，如图2（b），2（c），2（d）所示，零元的个数达到300甚至近400时仍有着与传统方法相同的识别效果，总体识别效果也更加接近于传统方法所得到的结果。

从实验中可以看出，随着数据稀疏性的提高，原始数据信息不断损失，数据总方差无可避免地开始逐渐降低，其识别准确率也逐渐降低，但每一维度下使用重加权稀疏主成分分析算法与传统PCA相比识别准确率相差较小，说明对数据进行稀疏化处理之后，降维后数据仍保持着原始数据独有的特征。

3.2 对比实验

为了进一步验证本文算法的优异性，对3.1 节中实验进行拓展，使用人脸识别准确率、实验耗时与GSPCA 算法［11］、ScotLASS算法［12］和sPCA-rSVD算法［16］进行对比分析。

实验中使用三个人脸数据集，分别为ORL 人脸数据集、AR（A.M. Martinez-R. Benavente）人脸数据集、Yale B 人脸数据集（Yale Face Database B）。AR 人脸数据集中包含120 人，每人有14张不同的面部图像，本文选取了每个人物的前10张照片作为数据集，共计1 200 张图片，每张图片的大小为40×50 像素。Yale B 人脸数据集中包含38 人，每人64 张照片，实验中选取每个人物的前10 张照片作为数据集，共计380 张照片，每张图片大小为168×192像素。

实验中将三个人脸数据集按照1∶1比例分别划分为匹配集和测试集，三个数据集匹配集与测试集中图片数量分别为200 张、600 张、190 张。实验中分别将维数控制在10 维、30维、50 维、100 维，比较四个算法的识别准确率和实验耗时，识别准确率按照测试集中识别正确的图片个数占据测试集比例计算，实验结果如表3所示。

从表3中可以观察到三个数据集中使用RSPCA算法所获得识别效果都要好于其他三种算法，在ORL 人脸数据集中最高识别率达到95.5%，而其余三种算法最高识别率仅为89.3%，识别准确率在原有基础上提高了6.2 个百分点。在AR 数据集与Yale B 数据集中，人脸识别效果与其余三种算法相比有所提升。在表3 中可以观察到RSPCA 的实验耗时最少，在ORL 数据集中平均耗时为1.1 s，AR 数据集中平均耗时为1.45 s，Yale B 数据集中平均耗时为1.17 s，与其他三种算法相比，耗时均有所减少。

表3 三种算法识别准确率及耗时对比Tab. 3 Recognition accuracy and time consumption comparison of three algorithms

图3 中展示了RSPCA 算法、GSPCA 算法、ScotLASS 算法和sPCA-rSVD 算法在ORL 人脸数据集、AR 人脸数据集和Yale B 人脸数据集上的平均识别准确率。从图3 中可以清晰地观察到RSPCA 算法在三个数据集中始终拥有着良好的识别准确率，在ORL 人脸数据集中的表现明显好于其他三种算法，在AR 数据集高于其余三种算法中识别率最高的sPCArSVD算法，在Yale B数据集中与GSPCA算法相差无几。

图3 四种算法平均识别准确率Fig. 3 Average recognition accuracy of four algorithms

图4 中展示了实验中四种算法的平均耗时情况，从图中可以发现RSPCA 算法耗时明显少于其余三种算法，平均耗时仅为1.24 s，从算法效率方面来看要优于其余三种算法。

图4 四种算法实验耗时Fig. 4 Average experimental time consumption of four algorithms

3.3 手写数字识别

重加权稀疏主成分分析算法同样可以应用于数字识别领域，数字识别在现实生活中有着许多重要的应用，如车牌检测、手写输入等。实验中使用重加权稀疏主成分分析算法+K近邻算法的方式，首先对训练集中的42 000 张图片进行数据降维，训练集中每张图片大小为28×28 像素。之后输入一张待识别图片，使用重加权稀疏主成分分析算法进行数据降维，最后利用K近邻算法寻找待识别图片在特征空间中的k张最相似样本中出现类别最多的类别，该类别即为待识别图片所属类别。实验中使用100 张图片作为测试集，并测试了在近邻数目不同情况下识别准确率的变化情况，实验中近邻数目分布k=1，2，…，50，实验结果如图5所示。

图5 不同近邻数量对识别准确率的影响Fig.5 Influence of different neighbors on recognition accuracy

从实验结果中可以发现，使用重加权稀疏主成分分析算法和K近邻算法的数字识别准确率达到93%以上，平均识别率达96.4%，重加权主成分分析算法在数字识别实验中获得了良好的实验效果。

4 结语

本文中针对主成分分析算法进行降维后获取到的主成分稀疏性不强问题进行研究，通过使用重加权的方法对其进行稀疏处理，提出了一个新的稀疏优化模型，即重加权稀疏主成分分析算法。文中使用数学方法对该算法进行了详尽的理论证明，并给出了该算法的求解方法。实验部分表明使用重加权稀疏主成分分析算法在进行人脸识别实验中获得了更加稀疏的结果且有着不弱于传统主成分分析算法的实验效果，数字识别实验中重加权稀疏主成分分析算法更是有着平均识别率96.4%的良好实验结果。本文所研究算法为解决主成分分析算法所得结果不够稀疏的问题提供了一个新的解决方案，同时可以尝试将此算法应用于更多的实验场景中。