改進的最大相關最小冗余特征選擇方法研究

姚明海，王 娜，齊 妙，李 妍

YAO Minghai1，2,WANG Na3,QI Miao2,LI Yan4

1.渤海大學 信息科學與技術學院，遼寧 錦州 121013

2.東北師范大學 計算機科學與信息技術學院，長春 130117

3.錦州師范高等專科學校 計算機系，遼寧 錦州 121013

4.大連市婦女創就業指導服務中心，遼寧 大連 116001

1.College of Information Science and Technology,Bohai University,Jinzhou,Liaoning 121013,China

2.School of Computer Science and Information Technology,Northeast Normal University,Changchun 130117,China

3.Department of Computer,Jinzhou Teachers Training College,Jinzhou,Liaoning 121013,China

4.Dalian Women and Employment Guidance Service Center,Dalian,Liaoning 116001,China

1 引言

隨著科學技術的飛速發展，描述事物的數據維數越來越龐大，這些龐大的數據必然會引起維數災難（Curse of dimensionality）[1]。特征選擇是處理高維數據，實現數據降維的有效方法，從原始特征集合中提取特征子集，去掉冗余信息和干擾信息，實現特征維數的最優縮減，從而提高了后續算法的預測準確率和計算性能[2-3]。近些年，特征選擇方法在模式識別[4-5]、生物信息學[6]、醫學數據處理[7]等多個領域受到廣泛的關注。特征選擇不改變特征的原始表達，僅從特征集中篩選最能代表觀測數據特點的最優特征子集，因此能很好地保持原始特征的含義，更利于人們的理解和判斷。

特征評價和特征搜索策略是構成特征選擇方法的兩個重要因素。特征評價是判斷所選特征優劣的標準，特征搜索策略是生成特征子集的主要手段。特征選擇方法按特征子集的評價機制和搜索策略主要分為過濾式和封裝式兩大類。過濾式方法通過數據的內在屬性評價特征的優劣，獨立于后續的學習算法，是一種計算效率較高的方法。具有代表性的方法有T檢驗（T-test）[8]、Fisher score[9]、信息增益（Information Gain，InforGain）[10]等。但是，過濾式特征選擇方法往往忽略了關于相關性的分析。封裝式方法是依賴于機器學習算法的特征選擇方法，通過分類算法的分類性能評價特征子集的優劣。與過濾式方法相比封裝式方法計算的精度會好一些，但算法效率較低?？紤]到特征之間的相關性和冗余性，人們提出了基于空間搜索的最大相關最小冗余（Minimal Redundancy Maximal Relevance，MRMR）算法[11]。MRMR算法使用互信息衡量特征的相關性與冗余度，并使用信息差和信息熵兩個代價函數來尋找特征子集。但是，MRMR算法存在冗余度和相關性評價方法單一，不能根據用戶需求設置特征維度等問題。曹靜在文獻[12]中提出了針對特征相關性和冗余性加權融合的方法，但對于特征選擇的評價方法仍然沒有改進。因此本文針對MRMR算法中的特征冗余度與相關性計算方法提出了改進方案。在冗余度計算過程中提出了一種新的簡單快速的計算方法；在計算特征相關性過程中引入多種經典過濾式特征選擇方法對特征重要性進行計算。

2 MRMR算法

最大相關最小冗余算法是最為典型的基于空間搜索的過濾式方法。最大相關就是指特征與類別相關度大，即特征能最大程度反映樣本類別信息；最小冗余指特征間相關度小即冗余度小。MRMR方法使用互信息度量特征的相關性與冗余度，使用信息差和信息熵構建特征子集的搜索策略。

MRMR算法中最大相關和最小冗余定義分別如公式（1）和公式（2）所示：

其中，F為特征集合，c為樣本類別，I(fr，c)表示特征fr與類別c之間的互信息，I(fr，fo)表示特征 fr與特征fo之間的互信息。

給定兩個隨機變量x和 y，設它們的概率密度分別為 p(x)，p(y)和 p(x，y)，則它們之間的互信息定義如公式（3）所示：

MRMR算法利用公式（4）作為評價函數指導特征子集的選擇。

3 MMRMR算法

3.1 算法流程

MRMR算法從空間搜索角度考慮了特征與類別間的相關性和特征冗余度，在性能上普遍優于基于排序的特征選擇方法，但其還存在一定的不足。首先，MRMR方法僅使用互信息來度量特征間的相關性，這就降低了該方法的適用范圍。眾所周知，評價特征重要程度的指標有很多，如基尼系數、Fisher得分、信息增益等等。所以，本文在評價特征重要性時提出了使用多種評價指標對特征重要性進行評價的方法，針對不同的數據選用不同的評價指標，使算法更具有魯棒性，適用范圍更廣。同時在冗余度評價上，設計了簡單直觀的冗余度評價函數。MRMR方法以實現特征的最大相關最小冗余為前提，這就意味著無法避免某些情況下選出的特征維數過低。針對MRMR方法的以上問題，本文提出了MMRMR方法，該算法能夠具有更廣泛的適用性和更高的預測準確性。算法流程如圖1所示。

圖1 MMRMR算法流程圖

3.2 冗余度評價函數

針對數字圖像提出一個新的冗余度評價函數。其核心思想是：對于兩個特征，如果其特征值越相近，則這兩個特征越相對冗余。針對數字圖像數據，如果圖像兩個不同位置的像素值所構成的兩組向量值域越相近，就說明這兩個位置越相對冗余。再進一步考慮到數字圖像往往存在噪聲、模糊等降質情況的存在。這里根據高斯分布 3σ法則（有68.3%的取值存在于 (μ-σ，μ+σ]區間），利用特征的均值和方差來重建值域，克服噪聲等降質情況的影響。數學描述如公式（5）所示：

其中，V是一個256維的向量，且V∈{0，1}。

對于特征 f，設其均值為 fˉ，方差為 fv，則V(max(0，fˉ-fv)，min(255，fˉ+fv))=1 ，即256 維V僅在[max(0，fˉ-fσ)，min(255，fˉ+fσ)]值域范圍內為 1，其余為0。該方法即能準確計算不同特征間的冗余性，又能避免噪聲的影響。

3.3 相關性評價函數

對于特征重要性的判斷有許多經典算法，并且這些算法被廣泛地應用到了各個領域。但是目前還沒有給出某種方法更適用于哪種數據的推薦。因此，為了更充分地挖掘數據本質，擴大方法的使用范圍，本文采用多種評價指標計算特征的重要性。

本文將要進行對比的評價函數分別是：基于T檢驗（T-test）的評價方法[8]、基于 χ2算法（Chi2 algorithm，ChiSquare）的特征選擇方法[13]、基于Relief算法的特征得分方法[14]、Fisher得分方法[9]、基于信息增益（Information Gain，InforGain）的方法[10]、基于基尼系數（Gini index，Gini）的方法[15]和 Kruskal-Wallis方法[16]。其中，T-test是利用t分布理論來比較兩個特征的差異是否顯著的統計方法；ChiSquare算法利用χ2統計來計算特征與類標簽的相關性，實現特征重要性打分；Relief算法通過計算類內和類間樣本距離來對特征打分；Fisher得分方法是尋找一組具有最好判別能力的特征子集的有監督方法；InforGain通過計算使用特征前后信息熵的改變來進行特征打分；Gini得分是一種基于統計測量和不純分割的方法，Gini系數值越小說明這個特征越好；Kruskal-Wallis得分通過計算不同特征的分布是否存在差異進行特征打分。鑒于每種方法都有著自身的特點，因此本文在特征相關性評價上，針對不同數據集采用了不同的評價方法。

3.4 評價函數

MMRMR算法的目標是在所有特征中選出k個具有最大權重且冗余度最小的特征組合。評價函數定義如公式（6）所示：

4 實驗結果與分析

使用五個經典的用于生物認證的數據庫來驗證MMRMR算法的有效性。在實驗中，對于相關性評價采用了七種不同的特征權重計算方法，產生了七種不同的MMRMR方法，表1中列出了由此產生的七種方法。為了說明方法的有效性，本文提出的MMRMR方法同這七種經典的過濾式方法以及原始的MRMR方法在特征選擇維度最高不超過200維的前提下進行對比實驗。眾所周知，每種特征選擇方法采用的評價標準都不盡相同，所以針對不同的數據類型一些特征選擇方法會有著其獨特的優勢。因此，本文在MMRMR框架下特征權重計算方法的選擇上，參考了經典方法在不同數據庫的識別效果，針對每一個數據庫選擇識別率相對較高的評價函數作為MMRMR框架下的特征權重計算方法。

表1 MMRMR框架生成的各種方法

為了體現特征選擇的作用，本文選用基于歐氏距離的K-nn分類器進行預測判斷。本文將以預測準確率（Predictive Accuracy，PR）作為評估標準，其定義如公式（7）所示：

其中，Num表示測試樣本總數，RP表示被正確判斷的樣本數量。為了使實驗結果符合統計規律，在實驗過程中進行10次隨機采樣，將每類樣本的一半作為訓練樣本，剩余樣本作為測試樣本，隨機采樣次數滿足99%的數據均參與過訓練和測試，計算獲得的平均PR作為最終結果。

4.1 在FERET數據庫上的實驗結果

FERET數據庫[17]包含1428個用戶（60%男性，40%女性）的14051張多姿態人臉灰度圖像。從數據庫中隨機選出72（人）×6（張）圖像作為實驗數據，并將圖像大小調整為32×32。圖2列出了部分實驗用圖像。

圖2 FERET數據庫中部分人臉圖像

由表2可以看出，原始的Fisher得分方法和Relief方法在該數據庫上識別率相對較高，因此本文采用了Fisher得分方法和Relief方法作為MRMR框架下的特征權重計算方法。MMRMR（F）在維數僅為200維的前提下就具有最高的準確率78.06%，其次MMRMR（R）也具有較高的預測準確率。

表2 FERET數據庫上各種方法的平均預測準確率

為了對實驗結果有更直觀的認識，將MMRMR框架下的Fisher和Relief方法與傳統Fisher和Relief方法的預測準確率隨維度變化的情況在圖3中顯示出來。由圖3中可以看出本文提出的MMRMR（F）方法在維數僅為140維時，其準確率就明顯超過其他方法，接近采用全體特征的預測準確率。這也充分說明了該算法能夠在充分去掉冗余信息的同時具有更高的預測準確率。MMRMR（R）結果次之，但是在較低維度時，它的準確率上升最快，如果再配合更精細的分類器模型，它會具有在較低運算復雜度的情況下就能產生較高的識別率的特性。

圖3 部分方法的結果對比圖

4.2 在ORL人臉數據庫上的實驗結果

ORL人臉數據庫[18]包含400張圖片（40（人）×10（張）），包括了面部表情和姿態的輕微變化。將數據庫中圖像大小調整為44×36，圖4列出了該數據庫的部分人臉圖像。

圖4 ORL數據庫中部分人臉圖像

由表3可以看出，基于InforGain、ChiSquare和Fisher為評價方法的MMRMR（I）、MMRMR（Chi）和MMRMR（F）在維數為200、180和200時就具有較高的預測準確率，幾乎都高于傳統的InforGain、ChiSquare和Fisher方法。并且，MMRMR（I）的預測準確率已經超過了90%。在該數據庫上獲得最高預測準確率的方法與FERET數據庫上具有最高準確率的方法不同，這也說明不同的特征選擇方法適用范圍各不相同。

表3 ORL數據庫上各種方法的平均預測準確率

圖5 部分方法的結果對比圖

圖6 部分方法的特征選擇結果（200維）對比圖

圖5中顯示了本文方法與傳統方法的預測準確率隨選擇特征維度變化的情況。由圖中可以看出本文提出的MMRMR（I）方法明顯優于其他方法，在160維時就接近90%。所有方法的準確率都沒有在較低維的時候超過使用全體特征的準確率。原因在于：（1）本文將特征選擇的維度上限設為200維，如果將上限進一步升高，選出更多的特征就可以進一步升高準確率；（2）在經過調整大小的預處理后，冗余信息被減少；（3）數據庫過于簡單，未能充分體現特征選擇的優勢。

圖6給出了部分方法在200維時的特征選擇對比結果圖。由圖6中可以看出，原始的特征選擇方法除了T-test方法，其他方法基本上都認為識別的重要特征是頭發，這明顯與常識不服。本文方法選出的特征更多集中在面部區域，更能代表圖像的特征，并且和實際情況相吻合。

4.3 在CMU PIE人臉數據庫上的實驗結果

CMU PIE數據庫[19]包含了68個人的41368張不同姿態、光照和表情的人臉圖片。實驗中對每一個人選取同一姿態、同一表情和不同光照的21張圖像，并在實驗前根據眼睛位置將裁剪出的臉部區域調整大小為32×32的大小，部分圖像如圖7所示。

圖7 CMU PIE數據庫中部分人臉圖片

由表4可以看出，由于該數據庫的原因，所有方法的預測準確率都很高，甚至達到100%。但本文方法的預測準確率仍然高于原始方法，并且展現了在低維數時就具有較高識別率的特性，同時，多個方法都能在低維度時達到100%的準確率。對于傳統MRMR算法和文獻[12]中的方法在多個數據庫上的實驗結果都不是很理想，這也表明這兩種方法的特征評價標準不適用于生物特征數據庫。

表4 PIE數據庫上各種方法的平均預測準確率

由圖8中可以看出，雖然這幾種方法最后都能達到100%的準確率，但是本文提出的幾種方法在20維時就具有較高的準確率，在40維的時候就接近了100%。

圖8 部分方法的結果對比圖

圖9給出了這幾種方法在60維時的特征選擇結果。雖然在準確率上這幾種方法都很接近，但是從選擇的圖像區域可以發現本文提出的幾種方法更優秀。其他方法僅選出了輪廓和少量的眼睛，而本文方法選出了五官區域的重要特征。

圖9 部分方法的特征選擇結果（60維）對比圖

4.4 在擴展的YaleB人臉數據庫上的實驗結果

擴展的YaleB數據庫[20]包含38個人，每個人大約64張圖片，包括了面部表情和光照條件的變化。圖片在使用前調整為32×32像素的大小。圖10中顯示了擴展的YaleB數據庫中的部分圖片。

圖10 擴展的YaleB數據庫中部分人臉圖片

表5列出了不同方法的預測準確率，可以看到本文提出的MMRMR（Chi）方法在維數僅為80維的時候就具有最高的預測準確率。

表5 擴展的YaleB數據庫上各種方法的平均預測準確率

圖11是識別率較高的四種方法的預測準確率隨維度變化曲線圖，如圖所示，本文提出的MMRMR（Chi）方法隨著維度的增大準確率迅速達到最大值。其他幾種方法在60維后預測準確率基本無法進一步提高。

圖11 部分方法的結果對比圖

在圖11中看出其他方法在200維時達到的預測準確率本文的方法在80維時就已經達到。在80維之后，隨著維數的增加預測準確率有了明顯下降，這說明在80維時選出的特征組合最好，當維數進一步增加就無法避免選出了冗余特征，造成準確率的降低。雖然隨著后續特征的增加，準確率有了一定的回升，但是冗余特征的存在使得準確率無法回到最優時候的高度。部分方法的特征選擇結果對比圖如圖12所示。

圖12 部分方法的特征選擇結果對比圖

4.5 在CASIA（1.0）虹膜數據庫上的實驗結果

中國科學院自動化研究所的CASIA虹膜圖像數據庫[21]包括756張來自108只不同眼睛的圖片，每只眼睛有7幅灰度圖像，圖13顯示了CASIA數據庫中部分虹膜圖像。本文采用文獻[22]中的方法對虹膜進行預處理。

圖13 CASIA數據庫中部分虹膜圖片

表6的結果指出，無論是哪種特征選擇方法在200維的情況下都沒有超過不進行特征選擇的準確率。造成這一情況的原因主要是因為在實驗之前進行了一系列的預處理操作。這些操作已經將原始圖像中大量的冗余信息和噪聲去除。即使這樣本文提出的MMRMR（I）方法仍然高于原有方法。

表6 CASIA數據庫上各種方法取得的最高平均預測準確率

圖14是ChiSquare、Relief、InforGain、Fisher和MMRMR（I）幾種方法準確率隨維度變化的曲線圖。從圖中可以看出 MMRMR（I）方法的預測準確率在所有維度下都優于其他方法。

圖14 部分方法的結果對比圖

5 結論

雖然MRMR方法的理念非常先進，但在實際應用中卻有很多明顯的不足，因此本文在現有特征選擇方法的基礎上，針對MRMR方法進行了改進，提出了MMRMR算法，避免了傳統MRMR算法僅使用互信息判斷特征的相關性和冗余度的問題，另外還解決了傳統算法中不能根據用戶需求設置特征選擇數量的問題。通過在多個數據庫上實驗，驗證了算法的有效性。同時，本文的方法可以適用于不同的數據庫，能夠根據不同數據庫的特點具體問題具體分析。本文采用經典的過濾式特征選擇方法進行權重計算，在后續研究中會針對具體問題選擇特定的重要性評價算法和冗余度計算方法或提出新的算法來提高預測的精準度。

[1]Jain A K，Duin R P W，Mao J.Statistical pattern recognition：a review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（1）：4-37.

[2]Blum A，Langley P.Selection of relevant features and examples in machine learning[J].Artif Intell，1997，97：245-271.

[3]Dash M，Liu H.Feature selection for classifications[J].Intelligent Data Analysis：An Inter J，1997，1：131-156.

[4]Saeys Y，Inza I，Larra?aga P.A review of feature selection techniques in bioinformatics[J].Bioinformatics，2007，23（19）：2507-2517.

[5]Zhang D，Chen S，Zhou Z H.Constraint score：a new filter method for feature selection with pairwise constraints[J].Pattern Recognition，2008，41（5）：1440-1451.

[6]Naikal N，Yang A Y，Sastry S S.Informative feature selection for object recognition via sparse PCA[C]//2011 IEEE International Conference on Computer Vision（ICCV），2011：818-825.

[7]Zhang N，Ruan S，Lebonvallet S，et al.Kernel feature selection to fuse multi-spectral MRI images for brain tumor segmentation[J].Computer Vision and Image Understanding，2011，115（2）：256-269.

[8]Press W H，Teukolsky S A，Vetterling W T，et al.Numerical recipes in C：the art of scientific computing[M].2nd ed.New York：Cambridge University Press，1992.

[9]Bishop C M.Neural networks for pattern recognition[M].Oxford：Oxford University Press，1995.

[10]Cover T M，ThomasJ A.Elementsofinformation theory[M].[S.l.]：Wiley，1991.

[11]Peng H，Long F，Ding C.Feature selection based on mutual information：criteria of max-dependency，max-relevance，and min-redundancy[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（8）：1226-1238.

[12]曹靜.基于最大相關最小冗余的特征選擇算法研究[D].秦皇島：燕山大學，2010.

[13]Liu H，Setiono R.Chi2：feature selection and discretization of numeric attributes[C]//Proc 7th Int Conf Tools with Artif Intell，1995：388-391.

[14]Kira K，Rendell L A.A practical approach to feature selection[C]//Proc 9th Int Workshop on Machine Learning，1992.

[15]Breiman L，Friedman J，Olshen R，et al.Classification and regression trees[M].Montery，CA：Wadsworth Int Group，1984.

[16]Wei L J.Asymptotic conservativeness and efficiency of kruskal-wallis test for k dependent samples[J].Journal of the American Statistical Association，1981，76（376）：1006-1009.

[17]Phillips P J.The FERET evaluation methodology for face recognition algorithms[J].IEEE Trans on PAMI，2000，22（10）：1090-1104.

[18]Samaria F S，Harter A C.Parameterisation of a stochastic model for human face identification[C]//Proceedings of the Second IEEE Workshop on Applications of Computer Vision，1994：138-142.

[19]Sim T，Baker S，Bsat M.The CMU pose，illumination，and expression database[J].IEEE Trans on PAMI，2003，25：1615-1618.

[20]Lee K C，Ho J，Kriegman D J.Acquiring linear subspaces for face recognition under variable lighting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（5）：684-698.

[21]CASIA-IrisV1[EB/OL].[2013-09-28].http：//www.cbsr.ia.ac.cn/IrisDatabase.htm.

[22]Qi M，Lu Y，Li J，et al.User-specific iris authentication based on feature selection[C]//2008 International Conference on Computer Science and Software Engineering，2008：1040-1043.