基于CEA+Boruta模式的特征選擇算法

朱顥東，常志芳

(鄭州輕工業(yè)大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，鄭州 450000)

隨著大數(shù)據(jù)時(shí)代的到來和存儲(chǔ)技術(shù)的快速發(fā)展，使得各個(gè)領(lǐng)域產(chǎn)生和收集數(shù)據(jù)變得越來越容易，但所獲數(shù)據(jù)中充斥的噪聲和冗余也日益增加[1].特征選擇也稱屬性選擇，即從原始特征中選擇出最有效特征來降低數(shù)據(jù)集的維度的過程[2].由于特征選擇具有良好的去除噪聲和冗余能力，是數(shù)據(jù)預(yù)處理的關(guān)鍵步驟，所以成為機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)問題[3].一個(gè)好的特征選擇算法不僅能顯著降低特征維數(shù)，而且能提高計(jì)算效率和預(yù)測(cè)性能[4].李楊等[5]曾提出一種基于改進(jìn)mRMR和支持向量機(jī)的特征選擇方法，他通過引入特征相關(guān)冗余權(quán)重因子改進(jìn)mRMR能有效細(xì)化對(duì)特征相關(guān)性和冗余性的平衡和度量，大幅度降低原始樣本集的維數(shù).王波等[6]針對(duì)小樣本數(shù)據(jù)特征選擇問題提出了一種MIFS-Boruta算法.李占山等[7]借鑒極端提升算法，通過改進(jìn)的序列浮動(dòng)前向搜索策略搜索特征子集，以此獲得最優(yōu)特征集.陳磊等[8]結(jié)合二分法與BP神經(jīng)網(wǎng)絡(luò)對(duì)牛乳體細(xì)胞進(jìn)行識(shí)別提高了計(jì)數(shù)識(shí)別率.孫桂煌[9]在機(jī)器學(xué)習(xí)算法下結(jié)合模糊度特征提取和三維空間重組方法對(duì)細(xì)節(jié)特征進(jìn)行識(shí)別，改善了人體動(dòng)作信息檢測(cè)和辨別能力.還有許多學(xué)者在特征選擇方向上研究出適用不同情境下的特征選擇算法.

特征選擇算法通常分為過濾式(filter)、封裝式(wrapper)、嵌入式(embedded)三大類[10].過濾式是通過評(píng)價(jià)每個(gè)特征與文本的相關(guān)性和發(fā)散性程度，設(shè)定合適的閾值篩選出最相關(guān)的特征集.它不需要借助機(jī)器學(xué)習(xí)算法即可快速排除一部分非重要噪聲特征，縮小優(yōu)化了特征子集搜索范圍，但難以發(fā)現(xiàn)特征間潛在相關(guān)性，不能選擇出一個(gè)較優(yōu)且規(guī)模較小的特征子集[11].典型的過濾式有方差選擇法、相關(guān)系數(shù)法、卡方檢驗(yàn)、信息增益和互信息法.封裝式是利用特定模型的學(xué)習(xí)結(jié)果作為衡量特征間重要程度的標(biāo)準(zhǔn)，如遺傳算法，遞歸特征消除法(recursive feature elimination,RFE)、Boruta法.該類方法考慮到了特征間的相互作用，所選的優(yōu)化特征子集規(guī)模相對(duì)較小，但計(jì)算效率遠(yuǎn)遠(yuǎn)不如過濾式方法.由于封裝式特征選擇方法搜索空間大，通常需要學(xué)習(xí)算法的介入，時(shí)間復(fù)雜度較高導(dǎo)致計(jì)算量太大[12]，泛化能力也比較差.嵌入式是用機(jī)器學(xué)習(xí)中模型適應(yīng)和訓(xùn)練特征全集，以最優(yōu)的目標(biāo)函數(shù)判斷特征的去留.在sklearn中，使用Select From Model函數(shù)將各個(gè)特征的權(quán)值系數(shù)計(jì)算出來，根據(jù)系數(shù)從大到小選擇特征.最常用的是使用GBDT、L1正則化和L2正則化來選擇特征.不少學(xué)者基于這三類方式在不同領(lǐng)域中加以融合和改進(jìn)，并通過機(jī)器學(xué)習(xí)算法驗(yàn)證數(shù)據(jù)集的分類準(zhǔn)確率[13].陶勇森[14]融合信息增益與和聲搜索算法對(duì)語(yǔ)音數(shù)據(jù)集進(jìn)行特征選擇提高了語(yǔ)音情感分類效率.許行等[15]在過濾階段定義了基于互信息的特征分組標(biāo)準(zhǔn)有效去除不相關(guān)和冗余特征，結(jié)合Boruta算法為解決小樣本問題提供了一種有效的方法，但是該算法不能自動(dòng)確定合理的候選特征子集.周傳華等[16]基于filter和wrapper模式提出了FSIGR算法，為數(shù)據(jù)降維問題奠定了理論基礎(chǔ)，但是較少的考慮特征之間的相關(guān)性.

本文將基于封裝式的Boruta算法，提出一種新的兩階段特征選擇算法.在第一階段，使用CEA過濾選擇方法找到候選特征集；在第二階段采用改進(jìn)的Boruta算法從候選特征集中篩選出最優(yōu)特征集合，解決傳統(tǒng)算法時(shí)間復(fù)雜度較高，較少考慮特征之間相關(guān)性等問題，該算法在python中有相應(yīng)的模塊用于特征顯著性的挑選，可以在代碼中直接調(diào)用，十分方便.

1 預(yù)備知識(shí)

1.1 Boruta特征選擇算法

Boruta算法是特征選擇方法中一種利用隨機(jī)森林作為分類器的封裝式算法,主要通過平均減少精度值來篩選出與因變量具有相關(guān)性的特征集合，boruta_py是sklearn中的擴(kuò)展包，在python中易于實(shí)現(xiàn).對(duì)于特征變量較多甚至超過樣本數(shù)目的數(shù)據(jù)集，使用傳統(tǒng)回歸等方式會(huì)導(dǎo)致過擬合問題，因此，本文借鑒Boruta算法思想提出一種新的特征選擇方法.傳統(tǒng)的Boruta算法思想如下[17].

第1步：創(chuàng)建陰影特征，對(duì)每個(gè)真實(shí)變量R，隨機(jī)打亂后排列，將所有變量的副本構(gòu)建成隨機(jī)組合的陰影特征矩陣S，拼接到真實(shí)特征后面，構(gòu)成新的特征矩陣N=[R,S].

第2步：用新的特征矩陣N作為輸入，在監(jiān)督模式下，隨機(jī)森林作為分類器訓(xùn)練一個(gè)擴(kuò)展數(shù)據(jù)集，取陰影特征重要性的最大值smax，真實(shí)特征中重要性大于smax的，記錄一次命中，并采用平均減少精度以評(píng)估的每個(gè)特征的重要性，越高則意味著對(duì)預(yù)測(cè)結(jié)果的貢獻(xiàn)越大[18].

第3步：在每次迭代中，它檢查一個(gè)真實(shí)特征是否比最好的陰影特征具有更高的重要性(即該特征是否比最大的陰影特征得分更高)并且不斷刪除它視為非常不重要的特征，重復(fù)該過程[19].

第4步：直到遍歷過的所有特征得到“拒絕”或者“接受”的分配結(jié)果，或者達(dá)到先前設(shè)置的隨機(jī)森林運(yùn)行的迭代次數(shù)時(shí)，算法停止.

1.2 綜合評(píng)估算法(comprehensive evaluation algorithm,CEA)

第1步：計(jì)算數(shù)據(jù)集中每個(gè)特征的信息增益比值GR，當(dāng)GR等于0，認(rèn)為該特征與類別不相關(guān)，并從數(shù)據(jù)集中剔除.

第2步：從分類能力和信息相關(guān)性兩方面通過計(jì)算數(shù)據(jù)集中每個(gè)特征的平均準(zhǔn)確率降低值(MDA)和信息增益比值(GR),來對(duì)每個(gè)特征進(jìn)行重要性度量.

2 CEA+Boruta算法

2.1 CEA+Boruta算法思想及設(shè)計(jì)

CEA+Boruta特征選擇主要分為兩個(gè)階段：過濾階段和封裝階段.在過濾階段使用綜合評(píng)估CEA算法，在封裝階段使用Boruta算法.

首先采用CEA算法計(jì)算出相應(yīng)的平均準(zhǔn)確率降低值和信息增益率值，通過標(biāo)準(zhǔn)化處理得到每個(gè)特征的綜合評(píng)估值，以此對(duì)原始特征進(jìn)行過濾和綜合性評(píng)估，從不同的維度增強(qiáng)對(duì)特征的度量，刪除無關(guān)特征，降低特征空間維度，提高了算法的運(yùn)行效率，選出了最優(yōu)的候選特征集.其次，采用改進(jìn)的Boruta算法，根據(jù)先前設(shè)定好的迭代次數(shù)，通過控制陰影特征樣本的比例并只對(duì)部分樣本打亂后隨機(jī)排列，以此來降低樣本的復(fù)雜度，進(jìn)而利用訓(xùn)練的隨機(jī)森林分類器對(duì)每個(gè)特征的重要性(置換單個(gè)變量，認(rèn)為導(dǎo)致隨機(jī)森林的準(zhǔn)確性下降幅度較大的變量對(duì)于數(shù)據(jù)分類更為重要)進(jìn)行打分，計(jì)算出候選特征子集中每個(gè)特征的重要性從而去除不重要的特征，篩選出所有與因變量具有相關(guān)性的最優(yōu)特征集合，解決了只用傳統(tǒng)Boruta算法計(jì)算時(shí)間長(zhǎng)，復(fù)雜度較高的問題.

2.2 CEA+Boruta算法

輸入：數(shù)據(jù)集D，特征集合F={fi|i=1,2，…，v}

輸出：最優(yōu)特征子集S.

第1步：在數(shù)據(jù)集D上計(jì)算特征fi的綜合評(píng)估值ci，對(duì)特征進(jìn)行降序排序，刪除無關(guān)特征，剩余作為候選特征的特征集Scan.

第2步：從數(shù)據(jù)集D中取出特征集Scan對(duì)應(yīng)的數(shù)據(jù)作為新的數(shù)據(jù)集Dnew；假設(shè)數(shù)據(jù)集Dnew為m行n列，即有m組樣本，n個(gè)特征，其中m>1，n>1，將數(shù)據(jù)集Dnew復(fù)制得到復(fù)制特征樣本Dcopy.

第3步：將復(fù)制特征樣本Dcopy按照比例p(0≤p≤1)提取出(m*p)*n組樣本，進(jìn)行隨機(jī)行變換后放回得到陰影特征樣本Ds.

第4步：將原始樣本Dnew與陰影特征樣本Ds合并，得到一個(gè)m行2n列的擴(kuò)展特征樣本集E，采用評(píng)判特征重要性措施(平均減少精度)——即Z值，用來評(píng)估每個(gè)特征的重要性.在E上運(yùn)行隨機(jī)森林分類器并不斷收集計(jì)算的Z值，Z值越高則意味著該特征對(duì)于預(yù)測(cè)結(jié)果貢獻(xiàn)越大.

第5步：找出陰影特征中得分最大Z值.在每次迭代中，檢查一個(gè)真實(shí)特征的Z值，將特征得分高于最大陰影特征得分的真實(shí)特征視為“重要”，將特征得分顯著小于最大陰影特征得分的真實(shí)特征視為“不重要”，并不斷從特征集合中永久刪除不重要的特征.

第6步：重復(fù)上述步驟，算法達(dá)到規(guī)定的迭代次數(shù)k時(shí)停止.

第7步：返回最優(yōu)特征子集S.

2.3 CEA+Boruta算法時(shí)間復(fù)雜度分析

本文算法的時(shí)間開銷主要體現(xiàn)在CEA和Boruta兩個(gè)階段.

假設(shè)訓(xùn)練數(shù)據(jù)集的特征維數(shù)是m,訓(xùn)練樣本個(gè)數(shù)為n,在CEA階段，快速排序的平均時(shí)間復(fù)雜度為O(m(log(m))),隨機(jī)森林(random forest,RF)學(xué)習(xí)算法中基分類器的個(gè)數(shù)為k,則RF算法時(shí)間復(fù)雜度近似為O(kmn(log(n))2),所以CEA算法的最大漸進(jìn)時(shí)間復(fù)雜度為O(3m+kmn(log(n))2).在Boruta階段，傳統(tǒng)的Boruta算法樣本復(fù)雜度為是O(n!)m，而在改進(jìn)的Boruta算法中，只有(n*p)*m維的數(shù)據(jù)對(duì)每一列進(jìn)行了隨機(jī)行變換，所以該樣本集的時(shí)間復(fù)雜度為O(((n*p)!)m)，本算法中p的取值為0.5，兩個(gè)時(shí)間復(fù)雜度通過取對(duì)數(shù)比較可知改進(jìn)的Boruta算法明顯降低了時(shí)間復(fù)雜度.因此CEA+Boruta算法的最大時(shí)間復(fù)雜度表示為：

O(m(log(m)))+O(3m+kmn(log(n))2)+O(((n*p)!)m)=O(m*((log(m))+kn(log(n))2+3)+((n*p)!)m).

可以看出，在過濾階段本文算法時(shí)間復(fù)雜度與特征維數(shù)的平方成正比，這個(gè)過程較快的處理了樣本數(shù)據(jù)中冗余的特征，對(duì)高維數(shù)據(jù)具有較好的擴(kuò)展性，為封裝階段降低了時(shí)間開銷，提高了隨機(jī)森林分類器處理重要特征屬性的效率和泛化能力.

3 試驗(yàn)及結(jié)果分析

3.1 試驗(yàn)數(shù)據(jù)集

本文試驗(yàn)中，采用的計(jì)算機(jī)配置為雙核，內(nèi)存16 G，處理器為i7-5820K,選擇了3個(gè)來自UCI機(jī)器學(xué)習(xí)庫(kù)公開數(shù)據(jù)集進(jìn)行測(cè)試(如表1所示)，使用python3.7在Jupyter Notebook應(yīng)用程序上實(shí)現(xiàn)算法，分析了本文CEA+Boruta算法相比于Boruta算法和FSIGR算法的優(yōu)點(diǎn)和不足.

表1 試驗(yàn)數(shù)據(jù)集Tab.1 Experimental data set

3.2 評(píng)價(jià)方法和標(biāo)準(zhǔn)

為驗(yàn)證各個(gè)算法在隨機(jī)森林分類器上的效果，實(shí)驗(yàn)采用十折交叉驗(yàn)證求取運(yùn)行效果，以減小誤差，每個(gè)數(shù)據(jù)集隨機(jī)分為10個(gè)子集，取其中一個(gè)作為測(cè)試集，連續(xù)運(yùn)行10次，最后取10次試驗(yàn)結(jié)果的平均值作為運(yùn)行1次所得到的取值[20]，改進(jìn)的Boruta算法階段取p值取0.5.

本試驗(yàn)使用的評(píng)價(jià)標(biāo)準(zhǔn)如下：

1) 所選擇的特征維數(shù)；

2) 各個(gè)數(shù)據(jù)集在不同特征選擇算法運(yùn)行的時(shí)間和平均分類錯(cuò)誤率；

3) 各個(gè)數(shù)據(jù)集在不同特征選擇算法中的精確率P、召回率R與綜合評(píng)估值F.其計(jì)算公式分別為：

其中NTP表示正確分類為正例的數(shù)量，NFP表示被錯(cuò)誤分類為正例的數(shù)量，NTN表示正確分類為反例的數(shù)量，NFN表示被錯(cuò)誤分類為反例的數(shù)量.

3.3 試驗(yàn)結(jié)果對(duì)比與分析

針對(duì)3個(gè)數(shù)據(jù)集，本文通過CEA+Boruta、FSIGR和Boruta 3個(gè)模型分別對(duì)數(shù)據(jù)集進(jìn)行了驗(yàn)證，選取的平均特征維數(shù)結(jié)果如表2所示.

表2 三種方法選取特征維數(shù)Tab.2 The feature dimension selected by the three methods

為了驗(yàn)證CEA+Boruta算法的有效性，分別獨(dú)立使用FSIGR算法和傳統(tǒng)的Boruta算法進(jìn)行對(duì)比，從表2可以看出，CEA+Boruta算法同F(xiàn)SIGR算法和Boruta算法相比，3個(gè)數(shù)據(jù)集上均表明CEA+Boruta算法所選出特征子集的數(shù)目要少于FSIGR算法和Boruta算法所選的數(shù)目.以特征數(shù)目較多的數(shù)據(jù)集Biodeg(特征數(shù)目為41)為例，CEA+Boruta算法選出特征數(shù)目的平均值為22.0，而FSIGR算法和Boruta算法選出特征數(shù)目的平均值分別為28.5和32.3.可以得出，CEA+Boruta算法相比FSIGR算法和Boruta算法，選出特征子集的數(shù)目最少，有效降低了特征維數(shù).

傳統(tǒng)的特征選擇算法通常將特征重要性排序作為結(jié)果比較，這樣耗時(shí)且選擇的特征集意義不大，因此本文采取如下方式對(duì)幾種算法進(jìn)行了對(duì)比，通過CEA+Boruta算法與傳統(tǒng)的Boruta算法和FSIGR算法建立模型，在不同的數(shù)據(jù)集上觀察選擇出同樣維數(shù)的特征所需運(yùn)行的時(shí)間、平均分類錯(cuò)誤率，如表3所示.

表3 三種方法在不同數(shù)據(jù)集上運(yùn)行結(jié)果Tab.3 The results of the three methods running on different data sets

從表3可以看出，CEA+Boruta算法和FSIGR算法相比傳統(tǒng)的Boruta算法的運(yùn)行時(shí)間和平均分類錯(cuò)誤率明顯減小.對(duì)于特征數(shù)目相對(duì)較少的CreditCard和Churn數(shù)據(jù)集來說，CEA+Boruta和FSIGR算法在平均分類錯(cuò)誤率差別不大，但是CEA+Boruta算法明顯比FSIGR算法運(yùn)行時(shí)間短，可以看出本文提出的算法在特征選擇應(yīng)用上明顯縮短了運(yùn)行時(shí)間.而對(duì)于特征數(shù)目為41的Biodeg數(shù)據(jù)集，可以看出CEA+Boruta算法在各個(gè)方面明顯優(yōu)于其他兩種，這說明本文提出的算法降低了計(jì)算時(shí)間開銷，提高了分類準(zhǔn)確率.

圖1～圖3統(tǒng)計(jì)了不同數(shù)據(jù)集中3種算法在平均召回率、平均精確率和平均F值評(píng)價(jià)指標(biāo)方面的結(jié)果.通過對(duì)比可以發(fā)現(xiàn)，CEA+Boruta方法比其他兩種算法的平均綜合評(píng)估F值高出至少4%，分類效果明顯優(yōu)于FSIGR和Boruta方法，對(duì)于樣本最多的CreditCard數(shù)據(jù)集來說，因類別只有兩種，且特征維數(shù)不多，所以在隨機(jī)森林分類器上的平均F值達(dá)到最大.數(shù)據(jù)集Biodeg的原始特征維數(shù)是41，幾乎是數(shù)據(jù)集Churn維數(shù)的2倍，但和數(shù)據(jù)集Churn的樣本數(shù)相差不大，經(jīng)運(yùn)行后發(fā)現(xiàn)在數(shù)據(jù)集Biodeg中，3種算法的R、P和F值都比在數(shù)據(jù)集Churn上高，因此，本文算法在維數(shù)較高，類別較少的數(shù)據(jù)集上分類效果更好.

圖1 三種方法在不同數(shù)據(jù)集上平均召回率比較Fig.1 Comparison of the average recall rate of the three methods on different data sets

圖2 三種方法在不同數(shù)據(jù)集上平均精確率比較 圖3三種方法在不同數(shù)據(jù)集上平均F值比較

4 結(jié)語(yǔ)

特征選擇是預(yù)測(cè)模型中一個(gè)重要步驟，與傳統(tǒng)的特征選擇算法相比，Boruta算法不必調(diào)整太多參數(shù)，就能找到候選特征中與類別相關(guān)的所有特征，適用于變量較多的數(shù)據(jù)集，且易于操作和解釋.本文介紹了傳統(tǒng)的Boruta和CEA算法，并提出了一種新的基于CEA和改進(jìn)的Boruta特征選擇兩步法.該算法通過過濾和封裝兩個(gè)階段以提高算法的性能，同時(shí)避免出現(xiàn)過擬合和時(shí)間復(fù)雜度較高等問題.3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均表明，該算法與FSIGR算法和傳統(tǒng)的Boruta算法相比能獲得較優(yōu)的特征集，而且提高運(yùn)行效率的同時(shí)取得了較高的F值.因此，本文提出的特征選擇算法相比傳統(tǒng)的Boruta算法得到了明顯的改進(jìn)，具有一定的競(jìng)爭(zhēng)優(yōu)勢(shì)，但是本實(shí)驗(yàn)中數(shù)據(jù)集涉及領(lǐng)域不夠廣泛，如何在不同領(lǐng)域驗(yàn)證Boruta算法階段最優(yōu)參數(shù)P值是下一步的研究方向.