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

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

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

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

針對(duì)上述問(wèn)題，本文既考慮各個(gè)特征對(duì)不同子類(lèi)問(wèn)題的分類(lèi)能力，又考慮各特征總的分類(lèi)能力，進(jìn)而提出了一個(gè)新的特征分類(lèi)能力排序方法.該方法既能確?？偡诸?lèi)能力強(qiáng)的特征被選擇，也能確保對(duì)子類(lèi)問(wèn)題分類(lèi)能力強(qiáng)但總分類(lèi)能力不強(qiáng)的特征被選擇，從而獲得特征分類(lèi)能力更合理的排序，以提高分類(lèi)準(zhǔn)確率.

1 基于子類(lèi)問(wèn)題分類(lèi)能力度量的特征選擇方法

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

1.1 相關(guān)定義

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

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

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

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

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

1.2 RRSPFS特征選擇方法

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

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

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

算法：特征選擇方法RRSPFS.

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

輸出：按分類(lèi)能力降序排列的特征集合Fm.

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

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

2 結(jié)果與分析

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

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

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

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

為合理比較這些方法的實(shí)驗(yàn)結(jié)果，選擇每種方法獲得的特征排序結(jié)果中相同個(gè)數(shù)的特征，分別使用上述7種分類(lèi)器在4個(gè)數(shù)據(jù)集上進(jìn)行分類(lèi)預(yù)測(cè)，相應(yīng)實(shí)驗(yàn)結(jié)果見(jiàn)圖1～圖4，橫坐標(biāo)為排在前面的特征的個(gè)數(shù)(m)，縱坐標(biāo)為選擇特征后使用上述7種分類(lèi)器進(jìn)行分類(lèi)預(yù)測(cè)獲得的準(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ù)情況下獲得的分類(lèi)預(yù)測(cè)準(zhǔn)確率更高，而且也能最快獲得最高的準(zhǔn)確率.4種算法獲得最高準(zhǔn)確率(the highest accuracy，HACC)及其選擇的特征數(shù)比較見(jiàn)表2.這些結(jié)果表明RRSPFS優(yōu)于另外3種，能獲得更準(zhǔn)確的特征分類(lèi)能力的排序，并提高了分類(lèi)器的預(yù)測(cè)準(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個(gè)特征的編號(hào)，以及這些特征在另3種算法中的相應(yīng)排位，表3給出了這21個(gè)特征中在另3種算法排名靠后的部分特征.由表3可以看出，有些特征在另3種算法中排序在1000位以后，但它們對(duì)子問(wèn)題的分類(lèi)能力很強(qiáng)，因此被RRSPFS排在了前面，如特征44、17、115、632、124 等.由圖 1 可以看出，排序在前 21的特征的準(zhǔn)確率都高于其他算法，這說(shuō)明了總分類(lèi)能力不強(qiáng)但子問(wèn)題分類(lèi)能力強(qiáng)的特征應(yīng)該被排在前面.

表3 Breast數(shù)據(jù)集中部分特征在各個(gè)方法中的排名比較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ù)集中部分特征在各個(gè)方法中的排名比較Tab.4 Comparison of ranking of features selected by each method on Leukemia3 dataset

參考文獻(xiàn)：

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