ReliefF-SVM RFE组合式特征选择人脸识别

华北电力大学 电子与通信工程系，河北 保定 071003

华北电力大学 电子与通信工程系，河北 保定 071003

1 引言

人脸识别中，由于人脸包含大量的特征信息，如何合理而有效地选择有利特征，消除冗余，加快运算速度，提高分类效率和正确率，一直是一个研究的热点问题。适当减少特征维数，保留人脸主要信息，在众多特征中寻找出最有用的特征已成为机器学习的重要研究方向。根据特征选择的过程是否独立于后续的学习算法，特征选择算法可以分为Filter和Wrapper两大类[1]。

Filter方法和分类学习算法无关，一般直接利用所有训练数据的统计性能评估特征。该方法的一个明显优势在于可以很快地排除很大数量的非关键性的噪声特征，缩小优化特征子集搜索范围，具有时间复杂度低的优点，用来作为特征的预选器非常好，但缺点是评估和后续学习算法的性能有较大偏差；Wrapper类方法直接利用分类学习算法的训练准确率评估特征子集可对不同的分类器选用相适应的特征子集，根据这个分类器在验证集上的表现来评价所选择的特征，该方法在速度上比滤波方法慢，但其所选的优化特征子集的规模相对要小得多，评估和分类算法性能偏差小，非常有利于关键特征的辨识和精简诊断决策机器的结构。ReliefF算法是公认的效果较好的Filter式评估算法[2-3]，它具有评估效率高，对数据类型没有限制，可以较好地去除无关特征的优点，但ReliefF算法的缺点是不能去除冗余特征，算法会赋予所有和类别相关性高的特征较高的权值，而不管该特征是否和其余特征冗余。SVM RFE作为基于启发式搜索策略的wrapper方法是目前研究的热点，它用支持向量机训练当前数据集，根据所得分类器获得特征的相关信息计算所有特征的排序准则分数，在当前数据集中每次移除一个对应于最小排序准则分数的特征，依次循环，直到特征集中剩余最后一个变量时结束。由于该方法采用的是贪婪搜索法[4-5]，在数据集较大的情况下，其计算的复杂度很大。基于此，本文提出了Filter和Wrapper相结合特征选择算法。即先用ReliefF算法对所得的人脸特征数据集进行特征预选择，在去除无关特征的同时把特征数据集降低成较小的数据空间，然后再用SVM RFE选择出最优特征子集。并对SVM RFE做出改进，即每次并不只是消除一个排序分数最低的特征，而是一次消去两个或多个特征，从而大大提高了运算速率。为了验证本方法的实时性及其准确性，在UMIST人脸库上做了大量的实验。结果表明，本文方法在预选后特征空间用SVM RFE特征选择的效率明显提高。对优选后的特征子集进行识别，无论在分类时间还是识别的准确率方面都有了很大的改善。

2 DWT-DCT特征提取

一副人脸图像所对应的矩阵维数一般有几千维甚至达几万维，其中不仅包含了识别所需的特征信息，更多的是对识别无用甚至干扰识别的冗余信息。这些信息不仅给识别算法本身带来很大负担，影响识别效率，更多的是因其大量冗余信息的存在，极大地影响识别率。而小波变换能够通过时域和频域的局部变换，在不同方向上子图的分辨率减少，使计算复杂度相应降低。因此，本文采用二维离散小波变换，通过对人脸图像二维信号在不同尺度上的分解，得到原始信号的低频和高频部分。信息中低频部分描述的是图像的整体信息，高频部分描述的是图像的细节信息，利用小波变换所获得的人脸低频分量就可以较好地描述对分类有用的人脸信息。但其低频子图在模糊人脸的不同表情和不同姿态等所引起的差异的同时，也模糊了不同人脸之间的差异，因此选择合适的小波分解层数对识别的效果和算法的复杂度都很重要，过度的小波分解会丢失大量对识别有用的信息。本文根据人脸图像的分辨率较小情况下选取一层变换后的人脸图像作为DCT特征提取目标。

由于本文所用UMIST人脸库尺寸均为112×92，经一层DWT降维后的图片为56×46，矩阵维数仍达2 576维，对这样一个高维的数据空间进行特征选择和训练识别显然其效率和准确率是极其低下的。于是，对DWT变换后的图像做离散余弦变换就可以很好地解决这个问题。DCT具有压缩比高、高低频信息分类能力强[6]的特性，同时又有比较大的方差分布，只需要保留少量的系数便可用于识别。一幅人脸图像可以看作矩阵或者二维数组，由向量的离散余弦变换很容易推出二维离散余弦变换。设 f(x，y)为空域中一幅分辨率为m×n的人脸图像，则其对应的DCT变换和IDCT变换公式[7]如下：

3 ReliefF算法

Kira等[2]1992年提出了Relief算法，该方法借用了最近邻学习算法的思想，该算法从训练集中随机选取m个样本实例，通过所选取的样本与属于同类和不同类的两个最近邻样本的差异，求出每个样本的各个特征与类的相关性，然后再求平均值作为每个特征的权值，就得到每个特征与类的相关性。Relief仅适用于训练样本是两类的情况。Kononenko[3]扩展了Relief算法得到ReliefF算法，ReliefF则可应用于多类样本情况。它不是从同类和不同类中各仅选出一个最近邻样本，而是选出k个最近邻样本，求平均值得到每个特征权值，从而得到每个样本实例中各个特征与类的相关性。把特征按照权值由大到小进行排序，然后可设定门限来判定特征是有效或无效，或者选择n个权值最大的特征，去除其他特征来进行特征选择。算法实现过程如下：

输入：训练实例的特征向量及类别标号，其中N为特征维数，m为迭代次数，k为最近邻样本个数

输出：对应于特征向量各个分量的权值向量W

Relief每次随机从训练样本集中取出一个样本Ri，然后从和 Ri同类的样本集中找出样本Ri的k个近邻样本（nearest hists），从每个Ri的不同类的样本中找出k个近邻样本（nearest misses），然后更新每个特征的权值。以上过程重复m次求出各个特征与类的相关性权值W后，将其排序，相关性大于某个门限值的特征就构成最后的特征子集，这样就消除了无效特征。

4 SVM RFE算法及改进

RFE是由Guyon等[8]提出的在一定的特征排列标准下逐个排除特征以获得最优特征子集的方法，SVM RFE则是RFE在SVM中的特征排列标准的推广。该方法是在一定的特征排列标准下逐个排除次优特征以获得最优特征子集的方法。SVM RFE算法是根据SVM在训练时生成的权向量W来构造排序系数，在运行之初假定整个基因集合就是所需要的优化特征集，而后在算法的每一步运行中迭代去掉一个排序系数最小的特征属性，最终得到所有特征属性的递减顺序的排序。其排序准则分数为：

算法具体过程如下：

初始化：当前特征子集指标s=[1 ，2，…，k] ，特征排序指标r=[]。

特征排序过程：

循环迭代以下过程直到s=[]

获取当前训练样本：X0=X(:，s)

训练分类器：α=SVM-train( ) X，y

计算排序标准：ci=||wi||2

寻找排序得分最小的特征属性 f=argmin(c)

更新排序特征指标：r=[s (f)，r]

消去最小得分特征属性：

输出：排序系数r

由于SVM RFE特征排列方法属于贪婪搜索法，在特征空间很大的情况下，计算复杂度很大。为了克服这种情况，本文对其做了改进，方法如下：

（1）令D为SVM的训练集，计算其训练所得特征的权系数向量W，则排序准则分数为ci。

（2）由于得出的排序准则分数最小值很多是相近的，于是可以相近一组最小排序系数一起消去。具体做法是把得到的排序准则分数ci做降序排列得到，设定一个较小的常数ε，将中排列最后一个排序系数分别与前k-n个做一阶差分得到Δci*，若Δci*＜ε，则前k-n个作为一组消去。

由以上得到的排序表定义若干个嵌套的特征子集F1⊂F2⊂…⊂Fn后，输入SVM训练以预测正确率大小评估这些子集的优劣，从而获得最优的特征子集。在选择最佳特征子集的过程中，采用训练集留一交叉检验错误识别率和独立测试集错误识别率[9]两个指标来综合判定最佳的特征子集。在SVM-RFE确定特征排序表过程和训练集留一交叉检验过程中，采用固定的参数组，在独立测试集识别过程中使用网格寻参（grid search）的方法[10]来进行参数寻优。通过以上方法选出最优特征子集输入SVM分类器进行分类识别。

5 实验结果及分析

本实验采用UMIST人脸库作为实验数据，该人脸库共有20个人，每人19～42幅图片，随机取每个人6幅作为训练集，另外13幅作为测试集。分别进行了3组实验：

（1）对人脸图像做DWT-DCT提取特征后，选取不同尺度的DCT系数后，再由ReliefF做特征初选，然后输入SVM分类器进行识别，结果如表1。

（2）对人脸图像做DWT-DCT提取特征后，选取不同尺度的DCT系数后，再由SVM RFE特征选择，然后输入SVM分类器进行识别，结果如表2。

（3）将实验（1）得到初选后的特征用SVM RFE进行特征选择，对选择的最优特征子集输入SVM进行分类识别，结果如表3。

表1 ReliefF人脸识别性能

表2 SVM RFE人脸识别性能

表3 ReliefF+SVM RFE人脸识别性能

以上每个数据取30次实验的平均值。由表1和表2知，选取的DCT系数的不同识别率也不同，但并不是选取的特征越多识别率就越高，过多的无用特征反而会干扰识别。实验结果可以看出在DCT选取400左右能有最佳的识别效果。说明采用DCT作为特征提取的方法不仅能够保存人脸识别的主要信息，还能很大程度地降维以减少进一步特征优选的时间。表2是未经初选的特征直接用SVM RFE进行特征子集的选择，其识别效果不是很理想，在特征数为选取的特征数为152时，最高识别率也只是93.67%。由表3结果看出，在识别率方面，由于使用ReliefF算法消除了类间特征的不相关性，再通过SVM RFE去除冗余特征，识别率明显提高，在选取特征数为52的情况下就达到最佳识别率98.84%；特征选择时间方面，虽然在SVM RFE特征选择前使用了ReliefF特征初选，表面上增加了算法的复杂度，但由于ReliefF算法不依赖后续学习算法，在特征空间很大的情况下能很快地起到降维作用，选取合适的子空间为SVM RFE作进一步优选。此外，本文通过对SVM RFE算法的改进，一次性消去多个特征，大大降低了特征选择的时间，实验结果来看，在达到最佳识别率98.84%时的识别时间仅为0.037 s。

6 结束语

本文将ReliefF-SVM RFE组合式特征选择的方法应用于人脸识别领域，并通过对SVM RFE的改进，很好地解决了该方法使用的瓶颈问题，即特征选择因算法复杂度高实时性差的问题。实验结果显示，该方法取得了很好的效果。如何寻找更好的特征选择算法，提高算法的效率，在较少的时间里选出最优的特征组合，进一步提高识别率，是今后研究工作的重点。

[1]Kohavi R，John G.Wrapper for feature subset selection[J]. Artificial Intelligence，1997，79（3）：273-324.

[2]Kira K，Rendell L.The feature selection problem：traditional methods and a new algorithm[C]//Proceedings of the 9th Conference on Artificial Intelligence.New Orleans：AAAI Press，1992：129-134.

[3]Kononerko I.Estimating attributes：analysis and extension of relief[C]//Proceedings of European Conference on Machine Learning，1994：171-182.

[4]李伟红，龚卫国，陈伟民，等.基于SVM RFE的人脸特征选择方法[J].光电工程，2006，33（5）：113-117.

[5]Tang Yuchun，Zhang Yanqing，Huang Zhen.Development of Two-stage SVM RFE gene selection strategy for microarray expression data analysis[J].Computational Biology and Bioinformatics，2007，4（3）：365-381．

[6]Hafed Z M，Levine M D.Face recognition using the discrete cosine transform[J].International Journal of Computer Vision，2001，43（3）：167-188.

[7]王克奇，朱金魁，白雪冰.基于小波分析和DCT的人脸特征提取[J].模式识别与仿真，2009，28（4）：65-68.

[8]Guyon I，Weston J，Barnhill S，et al.Gene selection for cancer classification using support vector machines[J].Machine Learning，2002，46（1/3）：389-422．

[9]Zhou Xin，Mao Kezhi.The ties problem resulting from counting based error estimators and its impact on gene selection algorithms[J].Bioinformations，2006，22：2507-2515.

[10]WordS，Sjöström M，ErikssonL.PLS-regression：abasic tool of chemometrics[J].Chemometrics and Intelligent Laboratory Systems，2001，58（2）：109-130.

ReliefF-SVM RFE组合式特征选择人脸识别

孔英会，张少明

KONG Yinghui,ZHANG Shaoming

Department of Electronics and Communication Engineering,North China Electric Power University,Baoding,Hebei 071003,China

To solve the problem that too much features have great effects on the instantaneity and accuracy of face recognition, a method named combined facial feature selection based on ReliefF-SVM RFE is proposed.The proposed method uses DCT extract facial feature and ReliefF select feature to reduce the feature dimension space initially,then uses improved SVM RFE to select optimal feature.This method solves the problem that the SVM REF feature selection consums long time because of training much features repeatedly.Finally,it uses leave-one-out method to select optimal feature subset from feature ranking table, and classification by SVM.Experiments are performed on UMIST facial database,accuracy of 98.84%is achieved when facial features are 52,recognition time only needs 0.037 s.

face recognition;Support Vector Machine Recursive Feature Elimination（SVM RFE）;ReliefF;discrete cosine transform;feature selection

针对人脸识别中因特征个数较多对识别的实时性和准确性影响较大的问题，提出了ReliefF-SVM RFE组合式特征选择的人脸识别方法。利用离散余弦变换提取特征和ReliefF对人脸图像特征集做特征初选，降低特征维数空间，再用改进的SVM RFE（Support Vector Machine Recursive Feature Elimination）选择最优特征，解决了利用SVM RFE特征选择时因特征数多而算法需多次训练耗时长的问题。对训练得到的特征排序表采用交叉留一验证方法选取最优子集，再由SVM分类识别。在UMIST人脸库上实验证明，可以在特征数为52时，达到98.84%的识别率，识别时间仅需0.037 s。

人脸识别；支持向量机回归特征消除（SVM RFE）；ReliefF；离散余弦变换；特征选择

A

TP391.4

10.3778/j.issn.1002-8331.1110-0106

KONG Yinghui,ZHANG Shaoming.Combined feature selection of ReliefF-SVM RFE used in face recognition.Computer Engineering and Applications,2013,49（11）：169-171.

孔英会（1964—），女，博士，教授，研究领域为信息处理、模式识别；张少明（1985—），男，硕士研究生。E-mail：zsm1015@sina.com

2011-10-09

2011-11-24

1002-8331（2013）11-0169-03

CNKI出版日期：2012-03-08 http://www.cnki.net/kcms/detail/11.2127.TP.20120308.1520.021.html