華北電力大學(xué) 電子與通信工程系，河北 保定 071003

華北電力大學(xué) 電子與通信工程系，河北 保定 071003

1 引言

人臉識別中，由于人臉包含大量的特征信息，如何合理而有效地選擇有利特征，消除冗余，加快運(yùn)算速度，提高分類效率和正確率，一直是一個研究的熱點(diǎn)問題。適當(dāng)減少特征維數(shù)，保留人臉主要信息，在眾多特征中尋找出最有用的特征已成為機(jī)器學(xué)習(xí)的重要研究方向。根據(jù)特征選擇的過程是否獨(dú)立于后續(xù)的學(xué)習(xí)算法，特征選擇算法可以分為Filter和Wrapper兩大類[1]。

Filter方法和分類學(xué)習(xí)算法無關(guān)，一般直接利用所有訓(xùn)練數(shù)據(jù)的統(tǒng)計(jì)性能評估特征。該方法的一個明顯優(yōu)勢在于可以很快地排除很大數(shù)量的非關(guān)鍵性的噪聲特征，縮小優(yōu)化特征子集搜索范圍，具有時(shí)間復(fù)雜度低的優(yōu)點(diǎn)，用來作為特征的預(yù)選器非常好，但缺點(diǎn)是評估和后續(xù)學(xué)習(xí)算法的性能有較大偏差；Wrapper類方法直接利用分類學(xué)習(xí)算法的訓(xùn)練準(zhǔn)確率評估特征子集可對不同的分類器選用相適應(yīng)的特征子集，根據(jù)這個分類器在驗(yàn)證集上的表現(xiàn)來評價(jià)所選擇的特征，該方法在速度上比濾波方法慢，但其所選的優(yōu)化特征子集的規(guī)模相對要小得多，評估和分類算法性能偏差小，非常有利于關(guān)鍵特征的辨識和精簡診斷決策機(jī)器的結(jié)構(gòu)。ReliefF算法是公認(rèn)的效果較好的Filter式評估算法[2-3]，它具有評估效率高，對數(shù)據(jù)類型沒有限制，可以較好地去除無關(guān)特征的優(yōu)點(diǎn)，但ReliefF算法的缺點(diǎn)是不能去除冗余特征，算法會賦予所有和類別相關(guān)性高的特征較高的權(quán)值，而不管該特征是否和其余特征冗余。SVM RFE作為基于啟發(fā)式搜索策略的wrapper方法是目前研究的熱點(diǎn)，它用支持向量機(jī)訓(xùn)練當(dāng)前數(shù)據(jù)集，根據(jù)所得分類器獲得特征的相關(guān)信息計(jì)算所有特征的排序準(zhǔn)則分?jǐn)?shù)，在當(dāng)前數(shù)據(jù)集中每次移除一個對應(yīng)于最小排序準(zhǔn)則分?jǐn)?shù)的特征，依次循環(huán)，直到特征集中剩余最后一個變量時(shí)結(jié)束。由于該方法采用的是貪婪搜索法[4-5]，在數(shù)據(jù)集較大的情況下，其計(jì)算的復(fù)雜度很大?；诖?，本文提出了Filter和Wrapper相結(jié)合特征選擇算法。即先用ReliefF算法對所得的人臉特征數(shù)據(jù)集進(jìn)行特征預(yù)選擇，在去除無關(guān)特征的同時(shí)把特征數(shù)據(jù)集降低成較小的數(shù)據(jù)空間，然后再用SVM RFE選擇出最優(yōu)特征子集。并對SVM RFE做出改進(jìn)，即每次并不只是消除一個排序分?jǐn)?shù)最低的特征，而是一次消去兩個或多個特征，從而大大提高了運(yùn)算速率。為了驗(yàn)證本方法的實(shí)時(shí)性及其準(zhǔn)確性，在UMIST人臉庫上做了大量的實(shí)驗(yàn)。結(jié)果表明，本文方法在預(yù)選后特征空間用SVM RFE特征選擇的效率明顯提高。對優(yōu)選后的特征子集進(jìn)行識別，無論在分類時(shí)間還是識別的準(zhǔn)確率方面都有了很大的改善。

2 DWT-DCT特征提取

一副人臉圖像所對應(yīng)的矩陣維數(shù)一般有幾千維甚至達(dá)幾萬維，其中不僅包含了識別所需的特征信息，更多的是對識別無用甚至干擾識別的冗余信息。這些信息不僅給識別算法本身帶來很大負(fù)擔(dān)，影響識別效率，更多的是因其大量冗余信息的存在，極大地影響識別率。而小波變換能夠通過時(shí)域和頻域的局部變換，在不同方向上子圖的分辨率減少，使計(jì)算復(fù)雜度相應(yīng)降低。因此，本文采用二維離散小波變換，通過對人臉圖像二維信號在不同尺度上的分解，得到原始信號的低頻和高頻部分。信息中低頻部分描述的是圖像的整體信息，高頻部分描述的是圖像的細(xì)節(jié)信息，利用小波變換所獲得的人臉低頻分量就可以較好地描述對分類有用的人臉信息。但其低頻子圖在模糊人臉的不同表情和不同姿態(tài)等所引起的差異的同時(shí)，也模糊了不同人臉之間的差異，因此選擇合適的小波分解層數(shù)對識別的效果和算法的復(fù)雜度都很重要，過度的小波分解會丟失大量對識別有用的信息。本文根據(jù)人臉圖像的分辨率較小情況下選取一層變換后的人臉圖像作為DCT特征提取目標(biāo)。

由于本文所用UMIST人臉庫尺寸均為112×92，經(jīng)一層DWT降維后的圖片為56×46，矩陣維數(shù)仍達(dá)2 576維，對這樣一個高維的數(shù)據(jù)空間進(jìn)行特征選擇和訓(xùn)練識別顯然其效率和準(zhǔn)確率是極其低下的。于是，對DWT變換后的圖像做離散余弦變換就可以很好地解決這個問題。DCT具有壓縮比高、高低頻信息分類能力強(qiáng)[6]的特性，同時(shí)又有比較大的方差分布，只需要保留少量的系數(shù)便可用于識別。一幅人臉圖像可以看作矩陣或者二維數(shù)組，由向量的離散余弦變換很容易推出二維離散余弦變換。設(shè) f(x，y)為空域中一幅分辨率為m×n的人臉圖像，則其對應(yīng)的DCT變換和IDCT變換公式[7]如下：

3 ReliefF算法

Kira等[2]1992年提出了Relief算法，該方法借用了最近鄰學(xué)習(xí)算法的思想，該算法從訓(xùn)練集中隨機(jī)選取m個樣本實(shí)例，通過所選取的樣本與屬于同類和不同類的兩個最近鄰樣本的差異，求出每個樣本的各個特征與類的相關(guān)性，然后再求平均值作為每個特征的權(quán)值，就得到每個特征與類的相關(guān)性。Relief僅適用于訓(xùn)練樣本是兩類的情況。Kononenko[3]擴(kuò)展了Relief算法得到ReliefF算法，ReliefF則可應(yīng)用于多類樣本情況。它不是從同類和不同類中各僅選出一個最近鄰樣本，而是選出k個最近鄰樣本，求平均值得到每個特征權(quán)值，從而得到每個樣本實(shí)例中各個特征與類的相關(guān)性。把特征按照權(quán)值由大到小進(jìn)行排序，然后可設(shè)定門限來判定特征是有效或無效，或者選擇n個權(quán)值最大的特征，去除其他特征來進(jìn)行特征選擇。算法實(shí)現(xiàn)過程如下：

輸入：訓(xùn)練實(shí)例的特征向量及類別標(biāo)號，其中N為特征維數(shù)，m為迭代次數(shù)，k為最近鄰樣本個數(shù)

輸出：對應(yīng)于特征向量各個分量的權(quán)值向量W

Relief每次隨機(jī)從訓(xùn)練樣本集中取出一個樣本Ri，然后從和 Ri同類的樣本集中找出樣本Ri的k個近鄰樣本（nearest hists），從每個Ri的不同類的樣本中找出k個近鄰樣本（nearest misses），然后更新每個特征的權(quán)值。以上過程重復(fù)m次求出各個特征與類的相關(guān)性權(quán)值W后，將其排序，相關(guān)性大于某個門限值的特征就構(gòu)成最后的特征子集，這樣就消除了無效特征。

4 SVM RFE算法及改進(jìn)

RFE是由Guyon等[8]提出的在一定的特征排列標(biāo)準(zhǔn)下逐個排除特征以獲得最優(yōu)特征子集的方法，SVM RFE則是RFE在SVM中的特征排列標(biāo)準(zhǔn)的推廣。該方法是在一定的特征排列標(biāo)準(zhǔn)下逐個排除次優(yōu)特征以獲得最優(yōu)特征子集的方法。SVM RFE算法是根據(jù)SVM在訓(xùn)練時(shí)生成的權(quán)向量W來構(gòu)造排序系數(shù)，在運(yùn)行之初假定整個基因集合就是所需要的優(yōu)化特征集，而后在算法的每一步運(yùn)行中迭代去掉一個排序系數(shù)最小的特征屬性，最終得到所有特征屬性的遞減順序的排序。其排序準(zhǔn)則分?jǐn)?shù)為：

算法具體過程如下：

初始化：當(dāng)前特征子集指標(biāo)s=[1 ，2，…，k] ，特征排序指標(biāo)r=[]。

特征排序過程：

循環(huán)迭代以下過程直到s=[]

獲取當(dāng)前訓(xùn)練樣本：X0=X(:，s)

訓(xùn)練分類器：α=SVM-train( ) X，y

計(jì)算排序標(biāo)準(zhǔn)：ci=||wi||2

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

更新排序特征指標(biāo)：r=[s (f)，r]

消去最小得分特征屬性：

輸出：排序系數(shù)r

由于SVM RFE特征排列方法屬于貪婪搜索法，在特征空間很大的情況下，計(jì)算復(fù)雜度很大。為了克服這種情況，本文對其做了改進(jìn)，方法如下：

（1）令D為SVM的訓(xùn)練集，計(jì)算其訓(xùn)練所得特征的權(quán)系數(shù)向量W，則排序準(zhǔn)則分?jǐn)?shù)為ci。

（2）由于得出的排序準(zhǔn)則分?jǐn)?shù)最小值很多是相近的，于是可以相近一組最小排序系數(shù)一起消去。具體做法是把得到的排序準(zhǔn)則分?jǐn)?shù)ci做降序排列得到，設(shè)定一個較小的常數(shù)ε，將中排列最后一個排序系數(shù)分別與前k-n個做一階差分得到Δci*，若Δci*＜ε，則前k-n個作為一組消去。

由以上得到的排序表定義若干個嵌套的特征子集F1?F2?…?Fn后，輸入SVM訓(xùn)練以預(yù)測正確率大小評估這些子集的優(yōu)劣，從而獲得最優(yōu)的特征子集。在選擇最佳特征子集的過程中，采用訓(xùn)練集留一交叉檢驗(yàn)錯誤識別率和獨(dú)立測試集錯誤識別率[9]兩個指標(biāo)來綜合判定最佳的特征子集。在SVM-RFE確定特征排序表過程和訓(xùn)練集留一交叉檢驗(yàn)過程中，采用固定的參數(shù)組，在獨(dú)立測試集識別過程中使用網(wǎng)格尋參（grid search）的方法[10]來進(jìn)行參數(shù)尋優(yōu)。通過以上方法選出最優(yōu)特征子集輸入SVM分類器進(jìn)行分類識別。

5 實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)采用UMIST人臉庫作為實(shí)驗(yàn)數(shù)據(jù)，該人臉庫共有20個人，每人19～42幅圖片，隨機(jī)取每個人6幅作為訓(xùn)練集，另外13幅作為測試集。分別進(jìn)行了3組實(shí)驗(yàn)：

（1）對人臉圖像做DWT-DCT提取特征后，選取不同尺度的DCT系數(shù)后，再由ReliefF做特征初選，然后輸入SVM分類器進(jìn)行識別，結(jié)果如表1。

（2）對人臉圖像做DWT-DCT提取特征后，選取不同尺度的DCT系數(shù)后，再由SVM RFE特征選擇，然后輸入SVM分類器進(jìn)行識別，結(jié)果如表2。

（3）將實(shí)驗(yàn)（1）得到初選后的特征用SVM RFE進(jìn)行特征選擇，對選擇的最優(yōu)特征子集輸入SVM進(jìn)行分類識別，結(jié)果如表3。

表1 ReliefF人臉識別性能

表2 SVM RFE人臉識別性能

表3 ReliefF+SVM RFE人臉識別性能

以上每個數(shù)據(jù)取30次實(shí)驗(yàn)的平均值。由表1和表2知，選取的DCT系數(shù)的不同識別率也不同，但并不是選取的特征越多識別率就越高，過多的無用特征反而會干擾識別。實(shí)驗(yàn)結(jié)果可以看出在DCT選取400左右能有最佳的識別效果。說明采用DCT作為特征提取的方法不僅能夠保存人臉識別的主要信息，還能很大程度地降維以減少進(jìn)一步特征優(yōu)選的時(shí)間。表2是未經(jīng)初選的特征直接用SVM RFE進(jìn)行特征子集的選擇，其識別效果不是很理想，在特征數(shù)為選取的特征數(shù)為152時(shí)，最高識別率也只是93.67%。由表3結(jié)果看出，在識別率方面，由于使用ReliefF算法消除了類間特征的不相關(guān)性，再通過SVM RFE去除冗余特征，識別率明顯提高，在選取特征數(shù)為52的情況下就達(dá)到最佳識別率98.84%；特征選擇時(shí)間方面，雖然在SVM RFE特征選擇前使用了ReliefF特征初選，表面上增加了算法的復(fù)雜度，但由于ReliefF算法不依賴后續(xù)學(xué)習(xí)算法，在特征空間很大的情況下能很快地起到降維作用，選取合適的子空間為SVM RFE作進(jìn)一步優(yōu)選。此外，本文通過對SVM RFE算法的改進(jìn)，一次性消去多個特征，大大降低了特征選擇的時(shí)間，實(shí)驗(yàn)結(jié)果來看，在達(dá)到最佳識別率98.84%時(shí)的識別時(shí)間僅為0.037 s。

6 結(jié)束語

本文將ReliefF-SVM RFE組合式特征選擇的方法應(yīng)用于人臉識別領(lǐng)域，并通過對SVM RFE的改進(jìn)，很好地解決了該方法使用的瓶頸問題，即特征選擇因算法復(fù)雜度高實(shí)時(shí)性差的問題。實(shí)驗(yàn)結(jié)果顯示，該方法取得了很好的效果。如何尋找更好的特征選擇算法，提高算法的效率，在較少的時(shí)間里選出最優(yōu)的特征組合，進(jìn)一步提高識別率，是今后研究工作的重點(diǎn)。

[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]李偉紅，龔衛(wèi)國，陳偉民，等.基于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

針對人臉識別中因特征個數(shù)較多對識別的實(shí)時(shí)性和準(zhǔn)確性影響較大的問題，提出了ReliefF-SVM RFE組合式特征選擇的人臉識別方法。利用離散余弦變換提取特征和ReliefF對人臉圖像特征集做特征初選，降低特征維數(shù)空間，再用改進(jìn)的SVM RFE（Support Vector Machine Recursive Feature Elimination）選擇最優(yōu)特征，解決了利用SVM RFE特征選擇時(shí)因特征數(shù)多而算法需多次訓(xùn)練耗時(shí)長的問題。對訓(xùn)練得到的特征排序表采用交叉留一驗(yàn)證方法選取最優(yōu)子集，再由SVM分類識別。在UMIST人臉庫上實(shí)驗(yàn)證明，可以在特征數(shù)為52時(shí)，達(dá)到98.84%的識別率，識別時(shí)間僅需0.037 s。

人臉識別；支持向量機(jī)回歸特征消除（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—），女，博士，教授，研究領(lǐng)域?yàn)樾畔⑻幚?、模式識別；張少明（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