基于子類問題分類能力度量的特征選擇方法

劉 磊，鄭陶然，趙晨飛，劉 林，王淑琴，何茂偉

(1.天津師范大學(xué) 計算機與信息工程學(xué)院，天津300387；2.天津工業(yè)大學(xué) 計算機科學(xué)與軟件學(xué)院，天津 300387)

特征選擇與特征抽取是維數(shù)約簡中2個主要的方法[1]，是構(gòu)造分類器中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟，其結(jié)果直接影響分類器的準(zhǔn)確率.在當(dāng)今大數(shù)據(jù)時代，數(shù)據(jù)呈數(shù)量巨大且紛繁復(fù)雜的特點，使得特征選擇方法的研究尤為重要[2].特征選擇是指根據(jù)一些評價標(biāo)準(zhǔn)在原有的特征集合上選擇對分類有意義的特征子集，而去除無關(guān)或冗余特征，從而將原空間的維數(shù)降至遠(yuǎn)小于原維數(shù)的m維.特征選擇方法分為Wrapper、Filter和Embedded 3類[3-4].Wrapper和Embedded方法通常用分類器的準(zhǔn)確率來評價選擇的特征子集[5-7]，而Filter方法不依賴于分類器，只考慮特征的分類能力.Filter方法運算速度快，適用于大數(shù)據(jù).Filter方法可以分為對各個特征單獨評價和對特征子集評價2類[8]，前者可以獲得所有特征的得分排序，而后者根據(jù)某種搜索策略獲得特征子集，本文方法屬于前者.

近年來，國內(nèi)外學(xué)者對特征選擇方法做了大量的研究.大多特征選擇方法有一個共同之處，即各種分類能力度量方法都是針對一個特征或特征子集給出描述該特征或特征子集的分類能力大小的一個分值，如卡方檢驗、信息增益、互信息、增益比、Relief、相關(guān)性、Fisher評分等指標(biāo)[9-13].這些方法通常認(rèn)為分值大的特征比分值小的特征的分類能力強，因而分值大的特征也就會被優(yōu)先選擇.然而，一些研究已經(jīng)表明一些分值小的特征也應(yīng)該被選擇，而且一些有較高分類能力值的特征組合也不總是能得到好的分類結(jié)果[8，14-15].以單一值表示特征分類能力大小僅僅是對這個特征分類能力的綜合評價，而忽略了特征對于不同類別的分類能力評價.

針對上述問題，本文既考慮各個特征對不同子類問題的分類能力，又考慮各特征總的分類能力，進而提出了一個新的特征分類能力排序方法.該方法既能確?？偡诸惸芰姷奶卣鞅贿x擇，也能確保對子類問題分類能力強但總分類能力不強的特征被選擇，從而獲得特征分類能力更合理的排序，以提高分類準(zhǔn)確率.

1 基于子類問題分類能力度量的特征選擇方法

本文提出的基于子類問題分類能力度量的特征選擇方法，簡記為RRSPFS(Round-Robin and subproblem based feature selection).首先計算所有特征對各子類問題的分類能力，并按分類能力降序排列所有特征；然后采用Round-Robin[16]方法計算各子類問題中特征的并集.

1.1 相關(guān)定義

2個特征X和Y的信息增益IG(X，Y)為

2個特征X和Y的信息增益比GR(X，Y)為

給定具有m個特征k類n個樣本的分類問題D=(F，C)，F(xiàn)={f1，f2，…，fm}為特征集合，C={c1，c2，…，cn}為類別特征，ci∈{1，2，…，k}.采用 1-vs-1 形式將其轉(zhuǎn)化為由任意兩類組成的s個二分類子問題，s=k(k-1)/2，其中每個二分類子問題稱為子類問題或子問題.

本文采用特征對類別特征的信息增益比作為特征的分類能力值，特征fi對第j個子問題的分類區(qū)分能力 fca(i，j)為

其中：Nj為第j個子問題中所含樣本的個數(shù).特征fi的總分類能力R(f)i是它對各個子問題的分類能力的加權(quán)平均.

1.2 RRSPFS特征選擇方法

對于分類問題D=(F，C)，計算每個特征fi對第j個子問題的分類區(qū)分能力fca(i，j)，獲得各個特征對各個子問題的分類能力矩陣(fac(i，j))m×s，將每個子問題中的所有特征按照其分類能力進行降序排列，即可得到各子問題中分類能力由高到低的特征的排列.

采用Round-Robin方法計算各子問題中特征的并集，即首先依次選擇各子問題中排在第一且未被選擇的特征，再選擇排在第二且未被選擇的特征，依此類推，直到所有子問題中特征都被選擇.其中對于屬于各子問題同一等級的特征的選擇次序，按照其總分類能力降序進行.

按照上述方法就得到了各特征的分類能力的降序序列.具體算法流程如下.

算法：特征選擇方法RRSPFS.

輸入：具有n個樣本、m個特征、k類的訓(xùn)練集D=({fi1，…，fim，c)i}ni=1，F(xiàn)={f1，…，fm}，ci∈{1，2，…，k}.

輸出：按分類能力降序排列的特征集合Fm.

令s=k(k-1)/2，F(xiàn)m= ，T= ；對F中的每一個特征 fi和每個子問題 j，計算 fca(i，j)；對每個子問題j，按分類能力 fac(i，j)降序排列所有特征.

對集合T中的特征按照R(f)i降序排列；

2 結(jié)果與分析

2.1 數(shù)據(jù)集

為了驗證RRSPFS算法的正確性和有效性，在4個數(shù)據(jù)集 Breast、Cancers、GCM 和 Leukemia3 上進行了實驗，它們均下載自http：//www.ccbm.jhu.edu/[17].表1給出了這些數(shù)據(jù)集中含有的類別數(shù)(numberofclassifications)k、特征數(shù)(number of features)m 及樣本數(shù)(number of samples)n.采用傳統(tǒng)的客觀評價指標(biāo)，即分類預(yù)測準(zhǔn)確率測試算法的性能.分類預(yù)測準(zhǔn)確率是將選擇的特征子集作為分類器的輸入獲得的準(zhǔn)確率.將本方法與現(xiàn)有的特征分類能力排序算法InfoGain、GainRation、ReliefF進行比較，并使用樸素貝葉斯(NB)、支持向量機(SVM)、K近鄰(KNN)、決策樹(C4.5)、隨機森林(RandomForest)、簡單邏輯回歸(Simple Logistic)和簡單分類與回歸樹(SimpleCart)等 7種分類器進行分類預(yù)測.

表1 多類基因表達數(shù)據(jù)集Tab.1 Multiclass gene expression datasets

2.2 實驗結(jié)果及分析

為合理比較這些方法的實驗結(jié)果，選擇每種方法獲得的特征排序結(jié)果中相同個數(shù)的特征，分別使用上述7種分類器在4個數(shù)據(jù)集上進行分類預(yù)測，相應(yīng)實驗結(jié)果見圖1～圖4，橫坐標(biāo)為排在前面的特征的個數(shù)(m)，縱坐標(biāo)為選擇特征后使用上述7種分類器進行分類預(yù)測獲得的準(zhǔn)確率的平均值(average of accuracies，AACC).

圖1 Breast數(shù)據(jù)集上的準(zhǔn)確率比較Fig.1 Accuracy comparison on Breast dataset

圖2 Cancers數(shù)據(jù)集上的準(zhǔn)確率比較Fig.2 Accuracy comparison on Cancers dataset

圖3 GCM數(shù)據(jù)集上的準(zhǔn)確率比較Fig.3 Accuracy comparison on GCM dataset

圖4 Leukemia3數(shù)據(jù)集上的準(zhǔn)確率比較Fig.4 Accuracy comparison on Leukemia3 dataset

由圖1～圖4可以看出，RRSPFS與其他3種算法相比，不僅在多數(shù)情況下獲得的分類預(yù)測準(zhǔn)確率更高，而且也能最快獲得最高的準(zhǔn)確率.4種算法獲得最高準(zhǔn)確率(the highest accuracy，HACC)及其選擇的特征數(shù)比較見表2.這些結(jié)果表明RRSPFS優(yōu)于另外3種，能獲得更準(zhǔn)確的特征分類能力的排序，并提高了分類器的預(yù)測準(zhǔn)確率.

表2 最高準(zhǔn)確率(HACC)及其選擇的特征數(shù)(m)比較Tab.2 Comparison of highest accuracy(HACC)and number of features(m)selected with highest accuracy

記錄了RRSPFS在Breast數(shù)據(jù)集上獲得的前21個特征的編號，以及這些特征在另3種算法中的相應(yīng)排位，表3給出了這21個特征中在另3種算法排名靠后的部分特征.由表3可以看出，有些特征在另3種算法中排序在1000位以后，但它們對子問題的分類能力很強，因此被RRSPFS排在了前面，如特征44、17、115、632、124 等.由圖 1 可以看出，排序在前 21的特征的準(zhǔn)確率都高于其他算法，這說明了總分類能力不強但子問題分類能力強的特征應(yīng)該被排在前面.

表3 Breast數(shù)據(jù)集中部分特征在各個方法中的排名比較Tab.3 Comparison of ranking of features selected by each method on Breast dataset

表4給出了Leukemia3數(shù)據(jù)集上RRSPFS排名前58但在其他算法中排名靠后的部分特征，可以看到特征 3 035、4 007、11 005、6 796、5 009、2 444、2 701 在其他3種算法中排名比較靠后，有的甚至在9 000位之后，而圖4顯示RRSPFS的特征排序得到了更好的準(zhǔn)確率，這也表明RRSPFS獲得的特征排名更合理.

表4 Leukemia3數(shù)據(jù)集中部分特征在各個方法中的排名比較Tab.4 Comparison of ranking of features selected by each method on Leukemia3 dataset

參考文獻：

[1]JAIN A K，DUIN R P W，MAO J C.Statistical pattern recognition：A review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(1)：4-37.

[2]BOLóN-CANEDO V，SáNCHEZ-MARON~O N，ALONSO-BETANZOS A.Recent advances and emerging challenges of feature selection in the contextofbigdata[J].Knowledge-BasedSystems，2015，86(C)：33-45.

[3]GUYON I，GUNN S，NIKRAVESH M，et al.Feature Extraction：Foundations and Applications(Studies in Fuzziness and Soft Computing)[M].New York：Springer，2006.

[4]SAEYS Y，INZA I，LARRAN~AGA P.A review of feature selection techniques in bioinformatics[J].Bioinformatics，2007，23(19)：2507-2523.

[5]CHEN G，CHEN J.A novel wrapper method for feature selection and its applications[J].Neurocomputing，2015，159(C)：219-226.

[6]RODRIGUES D，PEREIRA L A M，NAKAMURA R Y M，et al.A wrapper approach for feature selection based on Bat Algorithm and Optimum-Path Forest[J].Expert Systems with Applications，2014，41(5)：2250-2258.

[7]WANG A G，AN N，CHEN G L，et al.Accelerating wrapper-based feature selection with K-nearest-neighbor[J].Knowledge-Based Systems，2015，83(C)：81-91.

[8]YU L，LIU H.Efficient feature selection via analysis of relevance and redundancy[J].Journal of Machine Learning Research，2004，5(12)：1205-1224.

[9]PENG H C，LONG F H，DING C.Feature selection based on mutual information：Criteria of max-dependency，max-relevance，and minredundancy[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(8)：1226-1238.

[10]KONONENKO I.Analysis and extension of Relief[C]//Proceedings of theEuropeanConferenceonMachineLearning，Berlin：Springer，1994：171-182.

[11]FENG J，JIAO L C，LIU F，et al.Unsupervised feature selection based on maximum information and minimum redundancy for hyperspectral images[J].Pattern Recognition，2016，51(C)：295-309.

[12]KOPRINSKA I，RANA M，AGELIDIS V G.Correlation and instance based feature selection for electricity load forecasting[J].Knowledge-Based Systems，2015，82：29-40.

[13]WANG J，WEI J M，YANG Z，et al.Feature selection by maximizing independent classification information[J].IEEE Transactions on Knowledge and Data Engineering，2017，29(4)：828-841.

[14]WANG J Z，WU L S，KONG J，et al.Maximum weight and minimum redundancy：A novel framework for feature subset selection[J].Pattern Recognition，2013，46(6)：1616-1627.

[15]WANG S Q，WEI J M.Feature selection based on measurement of ability to classify subproblems[J].Neurocomputing，2017，224(C)：155-165.

[16]FORMAN G.A pitfall and solution in multi-class feature selection for text classification[C]//Proceedings of the 21st International Conference on Machine Learning，New York：ACM，2004：38-46.

[17]TAN A C，NAIMAN D Q，XU L，et al.Simple decision rules for classifying human cancers from gene expression profiles[J].Bioinformatics，2005，21(20)：3896-3904.