孫 勤，蔣艷凰，胡 維，張 毅，高 峰

1.國防科學技術(shù)大學 高性能計算國家重點實驗室，長沙 410073

2.國防科學技術(shù)大學 計算機學院，長沙 410073

3.中國人民解放軍 91550部隊

1 引言

特征選擇是數(shù)據(jù)挖掘中特征降維的重要方式之一[1]，通過特征選擇能適當去除無關(guān)和冗余特征，降低系統(tǒng)的存儲負擔和不必要的模型訓練開銷，同時能提高學習算法的性能。與特征提取相比，特征選擇是從原始特征集中選出一組最能替代原始特征的子集達到降維的目的，它不改變原始集合的物理特性，能在降維的同時真正降低系統(tǒng)的存儲負擔和時間開銷。

根據(jù)特征選擇是否與后續(xù)學習算法相關(guān)，可將其分為兩類：過濾式（Filter）[2]和封裝式（Wrapper）[3]特征選擇算法。過濾式特征選擇獨立于學習過程，它直接利用原始數(shù)據(jù)集的統(tǒng)計特性進行評估從而選出合適的子集，其效率高，但評估準確度低；使用過濾式方法力求某種評價準則最優(yōu)[4]，而對于不同的特征集，很難確定最適合的評價準則。目前已有的基于過濾式算法的評價標準有信息度量[5-6]、距離度量[6-8]、一致度度量等[8-9]。不同評價方法的復雜度和分類精度各不相同，不同的準則著重于不同的層面反應特征的優(yōu)劣，單一的準則往往無法全面評估特征集的好壞[10]。封裝式算法直接利用學習算法的準確率評價特征子集的好壞，其評估準確率高但是運行速度慢，特征越多，運行速度越慢。

針對兩類特征選擇算法各自存在的優(yōu)缺點，本文提出一種過濾式和封裝式相組合的特征選擇方法mCRC（Feature Selection Algorithm Based on multi-Criterion-Ranking and C-SVM），使用兩種準則同時對特征評估賦權(quán)，剔除完全冗余和不相關(guān)特征，得到重要程度權(quán)重降序排列的特征子集，再通過C-SVM分類器[11]采用順序前向浮動搜索算法（Sequential Forward Floating Selection，SFFS）[12]搜索分類精度高的特征，得到最佳特征子集，從而補充特征選擇兩大類算法存在的不足。

2 相關(guān)定義

2.1 互信息

互信息[5-6]是用來度量兩個變量的統(tǒng)計相關(guān)性的重要方法，也是目前特征選擇中普遍運用的評價準則。互信息的計算公式為：

其中，H(X)和H(Y )為X和Y的信息熵，H(X ,Y)為兩者的聯(lián)合熵。設p(x ,y)為(X ,Y )的聯(lián)合概率，則：

類別與各特征之間的互信息為：

特征兩兩之間的互信息為：

通過公式（2）可以計算特征與類別之間的關(guān)聯(lián)程度，I值越大，特征與類別標簽的相關(guān)性程度越高；I=0時特征與類別不相關(guān)，可以剔除。

通過公式（3）可以計算特征兩兩之間的相關(guān)性，I值越大，說明特征之間的冗余度越高；當fi和fj完全冗余時，則二者保留其一即可。

2.2 距離度量

距離度量也可以稱作類別可分性度量[7-8]。對于有監(jiān)督分類，不同類別間距越大類別的相似程度越低，可區(qū)分的概率越大，相同類別之間距離越小相似性越大，可區(qū)分性越小，分類準確率越高?；诰嚯x度量的特征子集評價能有效提高小樣本與線性不可分數(shù)據(jù)集上特征選擇的能力。特征選擇應該選擇類間間距大且類內(nèi)間距小的特征。

設第j維特征fj包含N個樣本，這N個樣本的平均值為avg(j)，則：

其中xt()j為第t個樣本的第j維特征。

設第c'類樣本個數(shù)為M，則第c'類樣本的第j維特征的特征均值為avgc'()j，則

第j維特征的類間距離為：

則第j維特征fj的類別可分性度量可表示為：

可用W(fj)來衡量特征的分類能力。W(fj)越大，特征的分類準確率越高。

2.3 C-支持向量機

在機器學習中，C-支持向量機（C-SVM）[11]是一種用于分類的監(jiān)督式學習算法，其基本思想是樣本點在線性不可分的情況下，引入松弛變量ξ和從輸入空間Rn到Hilbert空間Hil的變換：

映射為：

這樣便得到原始問題：

其中δ為懲罰參數(shù)，δ越大表示對錯誤分類的懲罰越大且δ＞0。

對于多分類問題，C-SVM通常轉(zhuǎn)化為多個兩類問題解決。C-SVM作為迄今為止最小錯分率和最大泛化能力的分類器，應用于特征選擇能用來分辨出分類正確率高的特征。因此，本文采用C-SVM作為分類器對特征集分類，篩選出分類精確度高的特征，從而得到最佳特征子集。

3 mCRC特征選擇算法

過濾式特征選擇中的互信息和距離兩種度量方法各有優(yōu)缺點，若將兩種評價準則結(jié)合起來共同對特征進行評價能夠綜合各方法的優(yōu)勢，能獲得比單個評價準則更高的精度?；谝陨详U述，本文提出了多準則賦權(quán)排序的過濾式算法和C-SVM互補的特征選擇算法mCRC。

3.1 特征排序與篩選

通過互信息和距離兩種度量準則同時計算原始特征集S中各特征與類別C的相關(guān)性，求得各特征的均值權(quán)重，在此過程可刪除互信息為零，即與類別不相關(guān)的特征，得到去掉不相關(guān)特征且含均值權(quán)重的特征子集U；對于集合U，本文設定一個初始空集Q，從U每次選擇一個特征放入Q中。在第一步，使得

gj∈Q，對于U中未被選中的特征，取任意gj若H(fi)=H(gj)=H(fi,gj)，則 fi與 gj完全冗余，從U 中刪除 fi，否則，對于fi取互信息最大值Imax(fi,gj)表示其與子集Q的冗余度，通過最大相關(guān)最小冗余標準來評估特征的重要性，并選擇當前重要程度最高的特征放入集合Q中，評價公式為：

其中Q的第l（l為Q的大?。﹤€特征被選依據(jù)為：

3.2 C-SVM封裝及最佳特征子集的確定

在過濾排序階段，mCRC算法刪除了不相關(guān)的和完全冗余的特征，并將特征進行重要性降序排序，使得在封裝階段可以直接利用C-SVM對過濾階段的排序結(jié)果采用SFFS策略選擇最佳特征子集，在搜索之前設定閾值λ（λ＞0，且λ=1時退化為順序前向搜索），當搜索到某個特征時子集分類精度上升，則將該特征加入最佳子集中，若搜索到某個特征之后的連續(xù)λ個特征都使得子集的分類精度均不大于這個特征的精度，則停止搜索。這種方式能夠較快地確定特征選擇的結(jié)果。相比傳統(tǒng)的Wrapper算法利用分類器對整個原始特征集進行評估再做特征選擇，mCRC算法節(jié)省了特征選擇所需的時間。另過濾器排序部分多準則同時評估與單準則評估相比大大提高了權(quán)重的可靠性。

3.3 mCRC算法描述

根據(jù)以上描述，給出多準則賦權(quán)排序與C-SVM相結(jié)合的特征選擇算法（mCRC）的偽代碼描述：

4 實驗設置與分析

本文采用UCI[13]機器學習知識庫中的數(shù)據(jù)集進行測試，表1給出了實驗所用數(shù)據(jù)集的基本信息。實驗環(huán)境為：Intel Core i5-6400 2.70 GHz CPU，8 GB內(nèi)存，Win10 64位操作系統(tǒng)，Matlab R2010a。

為了使實驗結(jié)果更具統(tǒng)計意義，采用5次交叉驗證[14]實驗，同時實驗采用LibSVM工具箱[15]，C-SVM的核函數(shù)采用徑向核函數(shù)RBF，并采用網(wǎng)格搜索來選取最優(yōu)懲罰因子δ和核函數(shù)參數(shù)g。

表1 實驗數(shù)據(jù)集基本情況表

圖1 mCRC、mRMR、CSB在各數(shù)據(jù)集上排序性能比較圖

實驗分為兩部分，第一部分，分別對mCRC算法、基于互信息排序的mRMR算法[5]及基于類別可分性排序的CSB算法[7]的排序部分進行性能比較，用三種算法將特征進行排序后再用C-SVM對去除了完全冗余和完全不相關(guān)并按重要性降序排好的所有特征逐一進行子集分類精度測試，檢驗各算法能否識別重要特征。圖1給出了三種算法的排序階段在各數(shù)據(jù)集上的實驗結(jié)果。

由圖1可知，對于表1中的8個數(shù)據(jù)集，三種算法都表現(xiàn)出隨著特征數(shù)目的增多，分類精度先不斷上升，隨后保持相對穩(wěn)定或下降狀態(tài)，表明通過mCRC、mRMR、CSB三種算法各自的過濾排序部分對特征進行重要性排序之后可以通過少量特征就達到與全集相同甚至高于全集的分類率，說明三種特征選擇算法的過濾排序部分都基本能夠識別重要特征。同時幾乎在所有數(shù)據(jù)集上mCRC都可以在比其余兩種算法少的特征數(shù)目下達到甚至高于初始數(shù)據(jù)集的分類準確率。但是，從圖1中也可以看出，三種算法并不是隨特征數(shù)據(jù)一直遞增到某個精度后再穩(wěn)定或下降，在精度上升過程中個別特征的加入會使得算法的性能突然下降再上升，說明排序過程存在某些誤差，因此，本文不用順序前向搜索算法來獲取最佳特征子集，而是通過采用設置一個λ值的順序前向浮動搜索的方法來得到最佳特征子集，從而避免采用順序前向搜索時精度在上升過程中因個別特征的加入降低特征集的分類性能而停止搜索達不到最佳性能的情況。λ值不宜設的過大，過大的λ值相當于在整個特征集上進行順序浮動前向搜索而失去的特征排序的意義。

實驗第二部分采用mCRC、mRMR、CSB三種特征選擇算法的排序部分分別對特征排序后再通過C-SVM和設閾值λ的SFFS進行性能比較。λ取2和3進行兩次實驗，實驗結(jié)果如表2、表3所示。

表2中λ等于2時的SFFS結(jié)果顯示：mCRC在6個特征集上有規(guī)模最小的最佳屬性子集，在7個數(shù)據(jù)集上的最佳屬性子集的分類性能高于其余兩種算法；mRMR在2個數(shù)據(jù)集上有最小約減的最佳特征子集，但相比其余兩種算法，mRMR在所有數(shù)據(jù)集上的最佳特征子集的分類性能最低；CSB在3個數(shù)據(jù)集上有最小約減的最佳屬性子集，相比其余二者，CSB在1個數(shù)據(jù)集上最佳屬性子集的分類精度最高。從效率來看，mCRC在4個數(shù)據(jù)集上有最高效率，而mRMR只有一個，CSB只有兩個。

表3取λ等于3時的SFFS結(jié)果與表2相比精度總體稍有變化，在多個數(shù)據(jù)集上mCRC的精度仍然最高，說明λ變化，mCRC的分類性能仍然最優(yōu)；相比表2，表3中λ取3使得各算法在個別數(shù)據(jù)集上對低精度的特征個數(shù)容忍度稍微增大，但在所有數(shù)據(jù)集上運行時間都有所增長，由此得出對于效率要求高的學習算法，λ的取值應盡量小?？傮w來看，在表3中，mCRC無論在從最佳子集規(guī)模、分類精度還是運行時間來看，mCRC算法都占優(yōu)勢。

表2、表3表明無論在效率、最佳特征子集大小還是分類精度上，mCRC的性能都優(yōu)于mRMR和CSB，說明基于多準則賦權(quán)排序選擇的最佳特征子集不僅規(guī)模小，泛化能力好，而且運行效率高。對于時間性要求很高的學習算法，數(shù)據(jù)處理的速度稍有提高都能大大提高學習算法的性能。而對于所有學習算法，數(shù)據(jù)集的分類精度越高越好。本文提出的mCRC算法能兼顧快速識別重要特征、得出小規(guī)模的最佳特征子集的同時減輕計算機的存儲負擔。

表2 λ取2時mCRC、mRMR、CSB的性能比較

表3 λ取3時mCRC、mRMR、CSB的性能比較

5 結(jié)論

本文提出了一種基于兩種準則賦權(quán)排序的過濾式和C-SVM混合的特征選擇方法，該方法使用兩種準則同時評估特征與類別的相關(guān)度及特征間的冗余度來對特征進行賦權(quán)排序，并使用C-SVM對按重要性降序排列的特征子集通過設容忍度閾值λ的順序前向浮動搜索策略（SFFS）搜索最優(yōu)特征子集。實驗結(jié)果表明，mCRC能夠識別重要特征，相較于單準則賦權(quán)排序，mCRC能在相對較短的時間內(nèi)得到分類精度更高的特征子集，并較大力度地降低了數(shù)據(jù)集的特征數(shù)，為快速并高效地對海量及高維數(shù)據(jù)進行挖掘提供了有力保障。

本文中兩種準則對特征進行賦權(quán)后采用平均值得到特征的最終權(quán)重，這樣面臨某個準則對某一特征集的評估很好，而另一準則對此特征集的評估效果很差，取平均權(quán)重會使得效果較差的準則拉低效果較好的準則的評估性能，如表2中的數(shù)據(jù)集segment。下一步，計劃采取某種方式對兩種準則進行加權(quán)，使得對某個數(shù)據(jù)集評估效果較好的準則占較重權(quán)重，評估效果較差的準則占較小權(quán)重，從而使得本文提出的mCRC特征選擇算法更具適應性。

[1]Kantardzic M，坎塔爾季奇，王曉海，等.數(shù)據(jù)挖掘：概念，模型，方法和算法[M].北京：清華大學出版社，2013.

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

[3]John G H，Kohavi R，Pfleger K.Irrelevant features and the subset selection problem[C]//11th International Conference on Machine Learning，1994：121-129.

[4]Li Y，Lu B L.Feature selection based on loss-margin of nearest neighbor classification[J].Pattern Recognition，2009，42（9）：1914-1921.

[5]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.

[6]姚旭，王曉丹，張玉璽，等.特征選擇方法綜述[J].控制與決策，2012，27（2）：161-166.

[7]張岐龍，單甘霖，段修生，等.基于特征空間中類別可分性判據(jù)的特征選擇[J].火力與指揮控制，2010，35（6）：118-120.

[8]任雙橋，傅耀文，黎湘，等.基于分類間隔的特征選擇算法[J].軟件學報，2008，19（4）：842-850.

[9]Dash M，Liu H.Consistency-based search in feature selection[J].Artificial Intelligence，2003，151（1/2）：155-176.

[10]李勇明，張素娟，曾孝平，等.輪詢式多準則特征選擇算法的研究[J].系統(tǒng)仿真學報，2009，21（7）：2010-2013.

[11]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法：支持向量機[M].北京：科學出版社，2004.

[12]Pudil P，Novovi?ová J，Kittler J.Floating search methods in feature selection[J].Pattern Recognition Letters，1994，15（11）：1119-1125.

[13]Blake C.UCI repository of machine learning databases[C]//Neural Information Processing Systems，1998.

[14]Bengio Y，Grandvalet Y.No unbiased estimator of the variance of k-fold cross-validation[J].Journal of Machine Learning Research，2004，5（3）：1089-1105.

[15]Chang C C，Lin C J.LIBSVM：A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology（TIST），2011，2（3）：389-396.