融合分類信息的隨機(jī)森林特征選擇算法及應(yīng)用

武煒杰，張景祥

江南大學(xué) 理學(xué)院，江蘇 無(wú)錫214122

從海量特征中科學(xué)提取關(guān)鍵特征，達(dá)到降維、提升模型性能的效果是機(jī)器學(xué)習(xí)與模式識(shí)別的關(guān)鍵問(wèn)題[1]。特征選擇是從原始特征集中選出若干具有代表性的特征子集，且在該特征子集上所構(gòu)建的分類或回歸模型達(dá)到與特征選擇前近似甚至更好的預(yù)測(cè)精度。特征選擇不僅可以提高應(yīng)用算法的空間和時(shí)間效率，避免“維數(shù)災(zāi)難”[2]，還可以在一定程度上避免算法的過(guò)擬合問(wèn)題。

根據(jù)特征評(píng)價(jià)策略，特征選擇方法大致分為兩種：過(guò)濾式（Filter）和封裝式（Wrapper）[3-4]。過(guò)濾式方法在數(shù)據(jù)預(yù)處理步驟中對(duì)特征排序，設(shè)定閾值選擇最優(yōu)特征子集，這種方法獨(dú)立于后續(xù)采取的機(jī)器學(xué)習(xí)算法。過(guò)濾式方法中經(jīng)典的排序準(zhǔn)則有Pearson相關(guān)系數(shù)[5]、互信息[6]、Laplacian得分[7]等。Kira等[8]提出的Relief算法依據(jù)特征權(quán)重對(duì)特征排序，但算法只針對(duì)于二分類問(wèn)題的特征選擇。Kononenko[9]在Relief算法的基礎(chǔ)上進(jìn)一步提出了Relief-F算法，可以進(jìn)行多分類問(wèn)題的特征選擇。Peng等[10]提出mRMR（max-Relevance and Min-Redundancy）算法，保留與分類信息具有強(qiáng)相關(guān)性的特征，又在一定程度上去除冗余特征。

封裝式方法通過(guò)與后續(xù)的學(xué)習(xí)算法結(jié)合，根據(jù)分類器的準(zhǔn)確率分別評(píng)價(jià)每個(gè)特征子集，從而選擇最優(yōu)特征子集。Breiman[11]提出通過(guò)隨機(jī)森林置換特征計(jì)算其重要性得分，進(jìn)行特征選擇是典型的封裝式方法。但當(dāng)特征規(guī)模較大，不可能對(duì)每個(gè)特征子集進(jìn)行評(píng)價(jià)，所以通常向前或向后算法來(lái)引入或消除特征。如Gregorutti等[12]通過(guò)研究隨機(jī)森林模型內(nèi)決策樹(shù)之間相關(guān)性對(duì)特征置換的影響，基于隨機(jī)森林特征置換計(jì)算其重要性得分同時(shí)，提出了一種遞歸特征消除算法；姚登舉等[13]提出了一種基于隨機(jī)森林模型的封裝式特征選擇算法，采用序列后向選擇和廣義序列后向選擇方法選擇特征。

隨機(jī)森林算法通過(guò)特征隨機(jī)置換前后誤差分析，計(jì)算每個(gè)特征重要性得分，分值越高，特征越重要，進(jìn)一步可以確定特征排序，與過(guò)濾式特征選擇方法相比，隨機(jī)森林模型不僅能體現(xiàn)特征間相互作用，還對(duì)噪聲數(shù)據(jù)和存在缺失值的數(shù)據(jù)具有較好的魯棒性，目前在醫(yī)學(xué)[14-15]、信息學(xué)[16]等方面廣泛應(yīng)用。但隨著數(shù)據(jù)特征增加，傳統(tǒng)的隨機(jī)森林算法計(jì)算效率大幅降低。

針對(duì)這個(gè)問(wèn)題，本文基于特征聚類與特征和分類信息的相關(guān)度策略，提出一種隨機(jī)森林多特征置換（Multi-Feature Permutation by Random Forests，MFPRF）算法。首先，算法對(duì)數(shù)據(jù)特征進(jìn)行聚類，保持其他特征簇內(nèi)的特征不變，逐一對(duì)同特征簇內(nèi)的特征同時(shí)隨機(jī)置換，通過(guò)置換前后預(yù)測(cè)誤差大小衡量特征簇的重要程度，得到簇間排序。計(jì)算簇內(nèi)特征與分類信息的相關(guān)性進(jìn)一步得到簇內(nèi)排序。算法結(jié)合過(guò)濾式方法，設(shè)定相關(guān)性閾值在排序后的特征簇內(nèi)依次選出重要特征，剩余特征則按照先簇間后簇內(nèi)的規(guī)則排序，得到全部特征排序，由分類器在不同特征子集上的分類精度，確定最優(yōu)特征子集達(dá)到降維效果。與文獻(xiàn)[11]相比，MFPRF算法優(yōu)點(diǎn)在于：（1）MFPRF算法將相似特征聚為一類，對(duì)若干個(gè)相似特征同時(shí)隨機(jī)置換，可避免當(dāng)特征規(guī)模過(guò)大時(shí)，逐一計(jì)算特征重要性得分，算法運(yùn)行時(shí)間更短。（2）MFPRF算法結(jié)合過(guò)濾式方法引入相關(guān)性閾值，在排序后的特征簇內(nèi)依次選出重要特征，體現(xiàn)出特征的相互作用的同時(shí)便于對(duì)數(shù)據(jù)的理解，增強(qiáng)最后分類模型的可解釋性。（3）MFPRF算法基于隨機(jī)森林模型，選擇的數(shù)據(jù)與特征均具有隨機(jī)性，對(duì)噪聲數(shù)據(jù)與缺失數(shù)據(jù)具有較強(qiáng)的魯棒性，算法性能穩(wěn)定。

1 隨機(jī)森林

隨機(jī)森林是通過(guò)組合（Ensemble）或又稱分類器組合（Classifier Combination）的方法，聚集多個(gè)模型提高預(yù)測(cè)精度的經(jīng)典代表算法之一。RF是裝袋算法（Bootstrap aggregating，Bagging）的一個(gè)擴(kuò)展體[17]，生成決策樹(shù)的過(guò)程中引入隨機(jī)特征選擇策略，最終根據(jù)投票原則確定最終結(jié)果。隨機(jī)森林生成過(guò)程如圖1所示。

圖1 隨機(jī)森林算法框架Fig.1 Framework of random forests algorithm

本文介紹的RF以構(gòu)建在Bagging基礎(chǔ)上的C4.5決策樹(shù)[18]為基分類器，在構(gòu)建過(guò)程中基于信息增益率引入隨機(jī)特征選擇。

1.1 傳統(tǒng)隨機(jī)森林特征重要性度量方法

傳統(tǒng)隨機(jī)森林特征重要性度量方法，是對(duì)每一個(gè)特征隨機(jī)置換。經(jīng)由隨機(jī)森林對(duì)特征置換后生成新的袋外數(shù)據(jù)進(jìn)行測(cè)試，隨機(jī)森林預(yù)測(cè)誤差率相比原來(lái)特征置換前會(huì)增大。當(dāng)特征重要程度越高，隨機(jī)森林模型預(yù)測(cè)誤差率的變化值會(huì)越大。這樣通過(guò)特征置換前后的袋外數(shù)據(jù)誤差率的變化值對(duì)每一個(gè)特征進(jìn)行打分，從而得到特征的重要性得分。

定義1（第i棵決策樹(shù)的袋外數(shù)據(jù)（Out-Of-Bag，OOB））假設(shè)訓(xùn)練集D，通過(guò)Bootstrap方法生成數(shù)據(jù)集Di構(gòu)建第i棵決策樹(shù)。其中未參與第i棵決策樹(shù)構(gòu)建的數(shù)據(jù)D-Di稱為第i棵決策樹(shù)的袋外數(shù)據(jù)OOBi。

定義2（基于OOB誤差分析的特征Xj重要性度量）基于OOB誤差分析的特征Xj重要性度量為對(duì)所有決策樹(shù)的OOB的特征Xj隨機(jī)置換前與置換后的OOB分類誤差率的平均變化量。

假設(shè)隨機(jī)森林中決策樹(shù)數(shù)目為Ntree，原始數(shù)據(jù)集有d個(gè)特征，單特征Xj(j=1,2,…,d)的基于OOB誤差分析的特征重要性度量按照下述步驟計(jì)算：

（1）計(jì)算第i棵決策樹(shù)相應(yīng)的袋外數(shù)據(jù)OOBi的袋外錯(cuò)誤樣本數(shù)ErrOOBi。

（2）在保持其他特征不變的同時(shí)，對(duì)OOBi中的特征Xj進(jìn)行隨機(jī)的序列改變得到，重新計(jì)算袋外數(shù)據(jù)的袋外錯(cuò)誤樣本數(shù)

（4）計(jì)算所有決策樹(shù)特征Xj置換前后OOB分類誤差率的平均變化量：

其中，VI(Xj)作為特征Xj的重要性得分。

1.2 隨機(jī)森林多特征重要性度量方法

由于傳統(tǒng)的隨機(jī)森林特征重要性度量方法是對(duì)單個(gè)特征進(jìn)行隨機(jī)置換，通過(guò)置換前后的袋外數(shù)據(jù)誤差分析對(duì)該特征的重要程度打分。相較于中、高維數(shù)據(jù)集，傳統(tǒng)方法對(duì)低維數(shù)據(jù)集優(yōu)勢(shì)較為明顯。由于中、高維數(shù)據(jù)集的特征數(shù)目增大，采用單個(gè)特征重要性度量的方式會(huì)導(dǎo)致算法運(yùn)行占據(jù)空間大，時(shí)間長(zhǎng)，效率低。本文在傳統(tǒng)方法上進(jìn)行改進(jìn)，引入隨機(jī)森林多特征重要性度量方法。在使用隨機(jī)森林度量特征重要性前，首先對(duì)原始特征進(jìn)行聚類，將相似性較高的特征聚成一類。對(duì)多個(gè)相似性較高的特征組成的特征簇采用多特征同時(shí)隨機(jī)置換的方式，度量特征簇的重要性得分。

定義3（基于OOB誤差分析的特征簇XJ重要性度量）基于OOB誤差分析的特征簇XJ={Xj|j∈J}重要性度量為對(duì)所有決策樹(shù)的OOB的特征簇XJ內(nèi)所有特征{Xj|j∈J}同時(shí)隨機(jī)置換前后OOB的分類誤差率的平均變化量。

假設(shè)隨機(jī)森林中決策樹(shù)數(shù)目為Ntree，原始數(shù)據(jù)集有d個(gè)特征，對(duì)原始特征集進(jìn)行聚類，聚成l類后得到特征簇集合{XJk|k=1,2,…,l}。第k個(gè)特征簇XJk基于OOB誤差分析的特征簇重要性度量按照下述步驟計(jì)算：

（1）計(jì)算第i棵決策樹(shù)相應(yīng)的袋外數(shù)據(jù)OOBi的袋外錯(cuò)誤樣本數(shù)ErrOOBi。

（2）在保持其他特征簇內(nèi)的特征不變的同時(shí)，對(duì)OOBi中的特征簇XJk內(nèi)所有特征{Xj|j∈J}同時(shí)進(jìn)行隨機(jī)的序列改變，重新計(jì)算袋外數(shù)據(jù)的袋外錯(cuò)誤樣本數(shù)

（4）計(jì)算所有決策樹(shù)特征簇置換前后OOB分類誤差率的平均變化量：

其中，||Jk為第k個(gè)特征簇內(nèi)含有特征的個(gè)數(shù)，VI(XJk)作為特征XJk的重要性得分。

由于特征簇內(nèi)的特征越多，該特征簇的重要性得分越高。為防止出現(xiàn)特征簇內(nèi)實(shí)際每個(gè)特征重要性得分低，但由于該特征簇內(nèi)的特征較多，導(dǎo)致得到虛高的特征簇重要性得分，所以得出的特征簇的重要性得分取該特征簇內(nèi)特征個(gè)數(shù)的平均值。

2 隨機(jī)森林多特征置換算法

本文根據(jù)引入的隨機(jī)森林多特征度量方法，提出隨機(jī)森林多特征置換算法。MFPRF算法對(duì)特征進(jìn)行聚類，由隨機(jī)森林多特征度量方法確定特征簇間排序，簇內(nèi)特征按與分類信息的相關(guān)性確定簇內(nèi)排序。MFPRF算法流程圖如圖2所示。

圖2 MFPRF算法框架圖Fig.2 Framework of MFPRF algorithm

2.1 特征聚類及有效性的衡量

聚類根據(jù)相似性原則將數(shù)據(jù)進(jìn)行劃分，相似性較高的數(shù)據(jù)劃為一簇，相似性較低的數(shù)據(jù)劃為不同簇。為了將相似性較高的特征聚為一簇，本文采用三種經(jīng)典聚類算法K均值（K-means，KM）聚類、層次聚類（Hierarchical Clustering，HC）和模糊C均值（FuzzyC-means，F(xiàn)CM）聚類算法對(duì)特征進(jìn)行聚類，得到MFPRF-KM（MFPRF based onK-means）、MFPRF-HC（MFPRF based on HC）和MFPRF-FM（MFPRF based on FCM）三種基于隨機(jī)森林多特征置換的特征選擇算法。引入與類間距離和類內(nèi)離散度相關(guān)的DBI（Davies-Bouldin-Index）指標(biāo)[19-21]來(lái)衡量特征聚類的有效性，其中DBI指標(biāo)內(nèi)容如下：

（1）類內(nèi)平均離散度：

其中，Zi是Ci類的類中心，||Ci表示Ci類樣本數(shù)。

（2）用兩個(gè)類中心的距離表示類間距離：

（3）DBI計(jì)算：

在DBI指標(biāo)中，DBk的值越小，聚類的效果越好，由此可以確定對(duì)特征聚類的最佳類數(shù)。

2.2 特征排序機(jī)制與重要特征的選擇

通過(guò)隨機(jī)森林得到特征簇間排序，再按簇內(nèi)特征與分類信息之間的相關(guān)性大小進(jìn)一步得到簇內(nèi)排序。簇內(nèi)特征與分類信息為兩個(gè)非退化的隨機(jī)變量，其相關(guān)性使用皮爾遜相關(guān)性系數(shù)ρxy衡量（見(jiàn)式（6）），相關(guān)系數(shù)ρxy的絕對(duì)值大小表示特征x、y相關(guān)程度的高低，ρxy絕對(duì)值越大，表示相關(guān)程度越高。

逐一計(jì)算全部特征與分類信息的相關(guān)性，設(shè)定相關(guān)性閾值δ作為標(biāo)準(zhǔn)選擇重要特征。本文參考文獻(xiàn)[22]，選取δ=EX+C×std(X)，其中EX與std(X)分別為數(shù)據(jù)集所有特征與分類信息相關(guān)性的均值與標(biāo)準(zhǔn)差。通過(guò)相關(guān)性閾值δ，依次從排序后的特征簇內(nèi)選取與分類信息相關(guān)性大于δ的特征作為重要特征。剩余特征按照先簇間、后簇內(nèi)順序依次排列在重要特征之后，得到最終的特征序列。

2.3 MFPRF算法

算法1MFPRF算法

輸入：訓(xùn)練集D∈Rn×d，隨機(jī)森林RForest。

輸出：重要特征數(shù)目s(s≤d)；特征序列{S}。

步驟1取特征集F←D，對(duì)特征集F聚類并計(jì)算其DBI指標(biāo)，取最優(yōu)聚類數(shù)生成的特征簇集合得到

步驟2通過(guò)隨機(jī)森林RForest對(duì)特征簇排序，即{Lk'}←RForest({Lk})，其中k'為k的置換。

步驟3取分類信息ClassInform←D，計(jì)算簇內(nèi)特征與分類信息的相關(guān)性CorrD，確定其相關(guān)性閾值δ=mean(CorrD)+C×std(CorrD)，重復(fù)下述步驟：

（1）依據(jù)簇內(nèi)特征與分類信息的相關(guān)性對(duì)簇內(nèi)特征排序得到L'k'←corr(Lk',ClassInform)。

（2）挑選重要特征fk←select({L'k'},δ)。

步驟4(s,U)←Number{fk|k=1,2,…,g}，U為重要特征序列；{S}←{U}+rank(F-{U})。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)在8個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行，其中兩個(gè)數(shù)據(jù)集結(jié)腸癌數(shù)據(jù)集Colon[23]與白血病數(shù)據(jù)集Leukemia[24]為生物數(shù)據(jù)集，其余數(shù)據(jù)集均為UCI數(shù)據(jù)集[25]。為了方便本文實(shí)驗(yàn)中描述數(shù)據(jù)集特征數(shù)目的大小，本文根據(jù)不同數(shù)據(jù)集特征數(shù)目所在范圍將數(shù)據(jù)集劃分為低維、中維或高維數(shù)據(jù)集。數(shù)據(jù)集詳細(xì)描述可見(jiàn)表1，其中d為特征數(shù)目。

3.1 實(shí)驗(yàn)設(shè)計(jì)

根據(jù)傳統(tǒng)隨機(jī)森林特征重要性度量方法得到最終特征排序的算法記為FSRF（Feature Selection by Random Forests）算法。MFPRF算法是在傳統(tǒng)隨機(jī)森林特征重要性度量方法上提出的。本文驗(yàn)證了FSRF算法的有效性，通過(guò)與FSRF、mRMR與Laplacian三種算法對(duì)比驗(yàn)證提出的基于隨機(jī)森林多特征置換的特征選擇算法MFPRF-KM、MFPRF-HC和MFPRF-FM的性能。實(shí)驗(yàn)方式如下：

（1）在低、中維數(shù)據(jù)集上通過(guò)將FSRF算法與ReliefF、MI兩種特征選擇方法在SVM分類器實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證基于傳統(tǒng)隨機(jī)森林特征重要性度量方法的FSRF算法的有效性。

（2）在低、中維數(shù)據(jù)集上通過(guò)將MFPRF算法與FSRF、mRMR與Laplacian三種算法在SVM分類器上實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證MFPRF算法的有效性與優(yōu)越性。

（3）在低、中維數(shù)據(jù)集上通過(guò)將MFPRF算法與FSRF算法的運(yùn)行時(shí)間對(duì)比，驗(yàn)證MFPRF算法更具有高效性。

MFPRF算法中的隨機(jī)森林決策樹(shù)數(shù)目Ntree=200，生成每棵決策樹(shù)的樣本數(shù)ψ=0.63×N（其中N為訓(xùn)練數(shù)據(jù)集的樣本數(shù)）。為了得到較為穩(wěn)定的結(jié)果，F(xiàn)SRF算法運(yùn)行20次，取20次均值為特征的重要性得分。MFPRFKM算法采用歐式距離度量特征相似性，MFPRF-HC算法采用余弦相似性度量特征相似性。對(duì)比算法ReliefF參數(shù)選取抽樣次數(shù)m=80,k=8。

實(shí)驗(yàn)對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理：刪除數(shù)據(jù)集內(nèi)缺失數(shù)據(jù)；為避免特征之間不同量綱對(duì)實(shí)驗(yàn)結(jié)果的影響，采用最大最小化方法標(biāo)準(zhǔn)化數(shù)據(jù)。采用SVM和KNN（K=1）兩種分類器檢驗(yàn)選取的重要特征集效果，并在排序后的特征序列中選取最優(yōu)特征子集。SVM分類器使用林智仁等開(kāi)發(fā)的SVM工具箱Libsvm，其中，核函數(shù)采用線性核函數(shù)，參數(shù)取值詳見(jiàn)表1。以10次5折交叉驗(yàn)證實(shí)驗(yàn)結(jié)果的平均值比較各算法的性能，評(píng)價(jià)準(zhǔn)則采用分類準(zhǔn)確率ACC、AUC（或MAUC）與F-measure，其中MAUC是AUC對(duì)多類問(wèn)題的推廣。實(shí)驗(yàn)代碼使用MATLAB 2014a實(shí)現(xiàn)；實(shí)驗(yàn)環(huán)境為Win7 64 bit操作系統(tǒng)，4 GB內(nèi)存，Intel?Core?i7-3520M CPU@2.90 GHz。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述及在SVM分類器參數(shù)Table 1 Descriptions of datasets used in experiments and parameters in SVM

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 FSRF算法實(shí)驗(yàn)結(jié)果對(duì)比

圖3為FSRF算法與ReliefF算法、MI算法在低、中維數(shù)據(jù)集上選擇不同特征子集基于SVM分類器的平均ACC指標(biāo)值。從圖3實(shí)驗(yàn)結(jié)果可以得到如下結(jié)論：

（1）在6個(gè)數(shù)據(jù)集上，F(xiàn)SRF算法與ReliefF算法、MI算法相比，在選擇較少特征時(shí)，就能取得最高（圖3（a）、（b）、（c）、（e））或較高的分類準(zhǔn)確率（圖3（d）、（f））。這說(shuō)明相較于ReliefF算法與MI算法，F(xiàn)SRF算法在較少特征時(shí)就可以選擇到對(duì)分類模型最重要的特征。

（2）在6個(gè)數(shù)據(jù)集上FSRF算法在取到部分特征時(shí)可以達(dá)到峰值（如圖3（a）、（b）、（c））或局部峰值（圖3（d）、（e）、（f））。這說(shuō)明FSRF算法在這6個(gè)數(shù)據(jù)集上特征選擇是有效的，可以在較少特征上取得近似或更好的結(jié)果。

圖3 FSRF與對(duì)比算法在數(shù)據(jù)集上的ACC指標(biāo)值Fig.3 ACC of FSRF and its contrast algorithms on datasets

3.2.2 MFPRF算法實(shí)驗(yàn)結(jié)果對(duì)比

將隨機(jī)森林多特征置換的特征選擇算法MFPRF算法與FSRF、MI、Laplacian三種算法基于SVM分類器的實(shí)驗(yàn)結(jié)果對(duì)比，分別在低、中維共6個(gè)數(shù)據(jù)集上測(cè)試。

圖4為MFPRF算法與對(duì)比算法在低維數(shù)據(jù)集上選擇不同特征子集基于SVM分類器實(shí)驗(yàn)結(jié)果的平均指標(biāo)值。由于低維數(shù)據(jù)集的特征數(shù)目較少，從優(yōu)化特征序列考慮對(duì)分類效果的影響，圖4所示實(shí)驗(yàn)結(jié)果顯示，圖4（a）中MFPRF-FM算法選擇的特征序列在分類中取到最高分類準(zhǔn)確率，其分類性能略優(yōu)于其他算法，MFPRF-HC算法在選擇較少特征時(shí)，可達(dá)到較高的分類準(zhǔn)確率，并且其AUC指標(biāo)明顯優(yōu)于其他算法；圖4（b）中，基于MFPRF的三種算法在首特征上的分類性能優(yōu)于其他算法，其中MFPRF-FM、MFPRF-KM算法優(yōu)化后的特征序列分類平均準(zhǔn)確率與F-measure指標(biāo)優(yōu)于其他算法；圖4（c）基于MFPRF的三種算法的分類性能優(yōu)于Laplacian算法，其中MFPRF-KM算法選擇的特征序列AUC指標(biāo)明顯高于其他算法。

圖4 MFPRF與對(duì)比算法在低維數(shù)據(jù)集上的指標(biāo)值Fig.4 Index of MFPRF and its contrast algorithms on low dimensional datasets

圖5為MFPRF算法與對(duì)比算法在中維數(shù)據(jù)集上選擇不同特征子集基于SVM分類器實(shí)驗(yàn)結(jié)果的平均指標(biāo)值。圖5所示實(shí)驗(yàn)結(jié)果顯示，圖5（a）中，基于MFPRF的三種算法在首特征上均達(dá)到較高的分類準(zhǔn)確率，在選擇最優(yōu)特征子集上，MFPRF-FM算法分類性能略優(yōu)與其他算法；圖5（b）中基于MFPRF的三種算法在分類準(zhǔn)確率與F-measure指標(biāo)上與mRMR算法相當(dāng)，明顯優(yōu)于FSRF與Laplacian算法，在AUC指標(biāo)上優(yōu)于其他對(duì)比算法；圖5（c）中基于MFPRF的三種算法的分類性能略優(yōu)于FSRF算法或與其相當(dāng)，明顯優(yōu)于Laplacian算法。

圖5 MFPRF與對(duì)比算法在中維數(shù)據(jù)集上的指標(biāo)值Fig.5 Index of MFPRF and its contrast algorithms on medium dimensional datasets

由圖6結(jié)果所示，在6個(gè)數(shù)據(jù)集上，F(xiàn)SRF算法所用時(shí)間明顯多于MFPRF算法，并且隨著數(shù)據(jù)集特征數(shù)的增加，F(xiàn)SRF算法與MFPRF算法所用時(shí)間差值呈上升趨勢(shì)。從圖6得到數(shù)據(jù)集特征數(shù)目越多，MFPRF算法比FSRF算法更高效。

圖6 FSRF與MFPRF算法在低、中維數(shù)據(jù)集的時(shí)間差值Fig.6 Difference of time of FSRF and MFPRF algorithms on low or medium dimensional datasets

3.3 MFPRF算法重要特征與最優(yōu)特征子集選擇結(jié)果

為了進(jìn)一步驗(yàn)證MFPRF算法的性能，表2、3分別給出了三種MFPRF算法在低、中維數(shù)據(jù)集上F/B/I（全部特征/最優(yōu)特征子集/重要特征集）基于SVM與KNN不同分類器的分類準(zhǔn)確率平均指標(biāo)值F_ACC/B_ACC/I_ACC，ACC表示無(wú)特征排序時(shí)的分類準(zhǔn)確率。MFPRF算法參數(shù)C的取值與每個(gè)數(shù)據(jù)集的特征與分類信息之間的相關(guān)系數(shù)有關(guān)，C的大小可以控制MFPRF算法選擇重要特征的數(shù)目，其具體取值時(shí)可以根據(jù)平均分類準(zhǔn)確率與需要特征數(shù)目來(lái)進(jìn)行調(diào)整，本文選取的參數(shù)C在表2、3中列出。

從表2數(shù)據(jù)看出：MFPRF算法在6個(gè)數(shù)據(jù)集上的重要特征分類準(zhǔn)確率與無(wú)特征排序時(shí)相比，在Breastcancer數(shù)據(jù)集上最高高出1.95%，在Ecoli數(shù)據(jù)集上下降最多，但選取的重要特征數(shù)目為2，約占全部特征的29%，大大減少了選擇特征的數(shù)目，并且分類準(zhǔn)確率均在85%以上；MFPRF算法在6個(gè)數(shù)據(jù)集上的最優(yōu)特征子集分類精度與無(wú)特征排序時(shí)相比，在Heart數(shù)據(jù)集上最高高出2.38%，在Ionosphere數(shù)據(jù)集上下降了0.29%，但選取的最優(yōu)特征子集數(shù)目?jī)H約為全部特征數(shù)目的15%，有效實(shí)現(xiàn)降維的目的。

表2 MFPRF算法在數(shù)據(jù)集上F/B/I的SVM分類器ACC指標(biāo)值Table 2 ACC of SVM classifier of MFPRF algorithms for F/B/I on datasets

從表3數(shù)據(jù)得出：MFPRF算法在6個(gè)數(shù)據(jù)集上的重要特征分類精度與無(wú)特征排序時(shí)相比，在Breastcancer數(shù)據(jù)集上最高高出4.36%，在Ecoli數(shù)據(jù)集上下降最多，但選取的重要特征數(shù)目約占全部特征的29%，且分類準(zhǔn)確率均在80%；MFPRF算法在6個(gè)數(shù)據(jù)集上的最優(yōu)特征子集分類準(zhǔn)確率與無(wú)特征排序時(shí)相比，在Breastcancer數(shù)據(jù)集上最高高出8.26%，在Sonar數(shù)據(jù)集上下降了0.77%，但選取的重要特征數(shù)約為全部特征的78%，減少了選擇特征的數(shù)目。

表3 MFPRF算法在數(shù)據(jù)集上F/B/I的KNN分類器ACC指標(biāo)值Table 3 ACC of KNN classifier of MFPRF algorithms for F/B/I on datasets

MFPRF算法的最優(yōu)特征子集的分類準(zhǔn)確率略優(yōu)于重要特征，但其所含特征數(shù)目明顯多于重要特征數(shù)。在6個(gè)數(shù)據(jù)集上選擇重要特征子集就可以達(dá)到較好的結(jié)果，若要分類結(jié)果達(dá)到最好，可以選擇最優(yōu)特征子集。

3.4 MFPRF算法應(yīng)用在高維生物數(shù)據(jù)集

上述實(shí)驗(yàn)驗(yàn)證了MFPRF算法的有效性與優(yōu)越性，相較于傳統(tǒng)的FSRF算法更具有高效性，在運(yùn)行時(shí)間少于FSRF算法的情況下，選擇的重要特征數(shù)目遠(yuǎn)遠(yuǎn)少于全部特征數(shù)目，并可達(dá)到較高的分類準(zhǔn)確率。將MFPRF應(yīng)用在Colon與Leukemia兩個(gè)高維的生物數(shù)據(jù)集上。圖7為三種MFPRF算法分別在Colon數(shù)據(jù)集與Leukemia數(shù)據(jù)集上選取的重要特征子集在SVM分類器與KNN分類器上的平均分類準(zhǔn)確率。MFPRF算法在Colon數(shù)據(jù)集上，所取參數(shù)C=2.2，在2 000個(gè)特征中選取了62個(gè)特征；在Leukemia數(shù)據(jù)集上，所取參數(shù)C=2.9，在7 070個(gè)特征中選取了84個(gè)特征。

從圖7的實(shí)驗(yàn)結(jié)果可以得到如下結(jié)論：

圖7 MFPRF算法在數(shù)據(jù)集上重要特征的ACC指標(biāo)值Fig.7 ACC of MFPRF algorithms for important feature subset on datasets

（1）在Colon數(shù)據(jù)集上，三種MFPRF算法中MFPRF-FM算法結(jié)果最好，選取重要特征中前20特征子集在SVM分類器與KNN分類器上均可以達(dá)到很好的分類效果。MFPRF-FM與MFPRF-HC算法結(jié)果略次于MFPRFFM算法，在SVM分類器上的結(jié)果略好于KNN分類器，并且分類精度基本在80%以上。

（2）在Leukemia數(shù)據(jù)集上，三種MFPRF算法在SVM分類器上選擇前70左右的重要特征后分類精度達(dá)到最高并趨于穩(wěn)定。在KNN分類器上，三種MFPRF算法在選取的重要特征子集上一直取得較高的分類精度，結(jié)果較為穩(wěn)定。

4 結(jié)論與展望

針對(duì)高維特征計(jì)算消耗巨大問(wèn)題，本文基于隨機(jī)森林提出多特征置換的選擇算法，包括MFPRF-KM、MFPRF-HC和MFPRF-FCM。實(shí)驗(yàn)結(jié)果證明了FSRF算法與MFPRF算法在低、中維數(shù)據(jù)集上的有效性；MFPRF算法在低、中維數(shù)據(jù)集上取得的重要特征集與最優(yōu)特征子集的特征數(shù)目遠(yuǎn)遠(yuǎn)小于總特征數(shù)目，且在重要特征集上得到較好的分類效果，MFPRF算法計(jì)算效率明顯高于FSRF；MFPRF算法在高維生物數(shù)據(jù)集上，其選取的重要特征在兩個(gè)分類器上均能達(dá)到較好的分類結(jié)果。

MFPRF算法屬于過(guò)濾式方法，比較依賴設(shè)定閾值，最優(yōu)特征子集與分類器檢驗(yàn)相互獨(dú)立。MFPRF算法雖然簡(jiǎn)單高效，但不利于后續(xù)特征優(yōu)化，影響分類模型的泛化性能。今后的工作重點(diǎn)設(shè)計(jì)出基于隨機(jī)森林的多特征封裝式算法，進(jìn)一步提高分類器性能。