改進Boruta算法在特征選擇中的應用

陳逸杰 唐加山

摘 要：特征選擇在機器學習中運用廣泛，Boruta算法是一種常見的特征選擇方法，算法思想簡單、易于操作，但樣本復雜度較高。針對該問題提出改進Boruta算法，在原算法陰影特征樣本建造中只對部分樣本打亂重排序，降低了陰影特征樣本的復雜度。實驗結果表明，改進的Boruta算法在混合比例約為0.4～0.6時相比原算法，提取出的特征擬合模型預測性能略有提高。使用平均減少不純度（mean decrease impurity）和隨機Lasso這兩種傳統方法選擇同樣數量的特征建立模型進行預測，發現改進的Boruta算法預測性能比上述兩種方法更優，改進的Boruta算法在降低樣本復雜度的同時提高了預測性能。

關鍵詞：特征選擇;Boruta;機器學習;陰影特征;混合比例

DOI：10. 11907/rjdk. 182315

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）004-0069-05

0 引言

特征選擇是機器學習方法應用的重要步驟，現代數據集通常用實際模型構建的變量來描述，而大多數變量與分類無關，這導致兩個問題：①處理大型數據集會降低算法速度，占用太多資源;②當變量數量明顯高于最優值時，許多機器學習算法的準確度會降低[1-2]。因此，進行特征選擇就變得非常必要。特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數的過程[3-4]，是模式識別的關鍵步驟。一個好的訓練樣本對于分類器而言至關重要，將直接影響模型預測的準確度[5-6]，因此高效的特征選擇算法是本文研究的重點。

特征選擇算法根據所采用的特征評價策略分為過濾和包裝兩大類。過濾方法獨立于后續采取的機器學習算法，可較快排除一部分非關鍵性噪聲特征，縮小優化特征子集搜索范圍，但它并不能保證選擇出一個規模較小的優化特征子集。包裝方法在篩選特征過程中直接用所選特征子集訓練分類器，根據分類器在測試集的性能表現評價該特征子集優劣。該方法在計算效率上不如過濾方法，但其所選的優化特征子集規模相對較小[7-8]。

特征選擇算法很多，最常用的是隨機森林重要性排序，其它比如mRMR 算法[9，10]采用最大相關最小冗余準則進行特征子集排序，使用包裝方法進行特征子集選擇，其問題是特征子集計算時間長，不能有效刪除冗余特征。Shao等[11]提出了一種混合優化的特征選擇算法（hybrid optimization based multi-label feature selection，HOML）。該算法綜合了模擬退火算法和遺傳算法以及貪婪算法尋找最優特征子集。這兩種方法直接使用分類器評價特征與標簽集合之間的關系，算法計算較復雜，在實際中難以應用。

本文討論機器學習中常用的Boruta算法[9]。該算法在R及python軟件中皆有現成的包，可在軟件中直接調用。Boruta算法是一種圍繞隨機森林[10-12]分類器構建的包裝器方法，是Stoppiglia、Dreyfus、Dubois和Oussar（2003）思想的擴展。通過比較真實特征與陰影特征之間的相關性確定變量相關性，在股票收益率研究[13]、地理統計研究[14]中皆有應用。

Boruta算法和mRMR算法及HOML算法存在類似問題，即計算時間長、復雜度較高，影響了運行效率。具體體現在創建陰影特征的樣本這一步驟中。因此，本文增加一個參數用于控制陰影特征的比例，不僅可降低樣本復雜度，還可提高預測性能。

1 Boruta算法

1.1 Boruta算法原理

Boruta算法是圍繞R包randomForest中實現的隨機森林分類算法構建的包裝器。隨機森林分類算法通常可在不調整參數的情況下運行，并給出特征重要性的數值估計。隨機森林是一種集成方法，通過對多個無偏的弱分類器投票比如決策樹來執行分類。這些樹是在訓練集的不同裝袋樣本上獨立構建的。將對象之間的屬性值隨機排列引起的分類準確性的損失作為屬性的重要性度量。Boruta算法考慮了森林中樹木的平均準確度損失的波動，使用平均下降精度用于度量重要性。

Boruta算法使用隨機設計的屬性擴展了變量特征。對每個特征創建一個相應的“陰影”特征，其值是通過重新排列原始特征的值獲得的。然后，使用此擴展變量的所有特征執行分類，并計算所有特征的重要性。由于存在隨機波動，陰影特征的重要性可能非零。因此，由陰影特征的重要性決定哪些特征真正重要。重要性度量本身隨隨機森林分類器的隨機性而變化，對陰影特征很敏感，需要重復洗牌程序以獲得有效結果。

簡而言之，Boruta算法和隨機森林分類器基于相同的思想，即通過向系統添加隨機性并從隨機樣本集合中收集結果，以減少隨機波動和相關性產生的誤差。這種額外的隨機性令使用者更清楚地了解特征的重要程度。

1.2 Boruta算法流程

算法流程如圖1所示。

①將[m]行[n]列的原始樣本進行復制得到混合樣本;②將混合樣本中的每一列都獨立進行隨機行變換，得到[m]行[n]列的陰影特征樣本;③將原始樣本與陰影特征樣本合并得到[m]行[2n]列混合樣本;④在新的混合樣本上運行隨機森林分類器并收集計算每個變量不在模型中的下降精度，計算出平均減少精度MeanImp;⑤將重要性低于MeanImp的特征標記為“不重要”，并將其從變量中永久刪除;⑥在陰影特征中找到最好的陰影特征MaxImp;⑦將重要性高于MaxImp的特征標記為“重要”，其它特征標記為“暫定”;⑧刪除所有陰影特征;⑨重復此過程，直到所有特征指定重要性，即沒有“暫定”特征。

2 改進Boruta算法

2.1 改進算法原理及流程

在創建陰影特征樣本時，對每列的全部樣本都進行隨機重排導致復雜度較高。為提高運行效率，針對樣本比例進行改進，改進算法獲得陰影特征樣本流程如圖2所示。

2.3 數據模擬

本改進算法主要體現在擴展數據的陰影特征方面。原算法通過重新排列原始特征值獲得陰影特征矩陣，本文通過一組數據模擬展示改進算法與原算法中陰影特征的具體創建過程。

假設有一個5行3列數據，其中[X1]、[X2]、[X3]為原始特征，假設建造陰影特征為[X1]、[X2]、[X3]。將[X1]中的樣本隨機重新排列后放入[X1]中，同理可得到[X2]和[X3]的樣本，與原始特征合并得到5行6列的擴展數據集，如表1所示。

此時混合樣本的復雜度為[（5！）3]，即混合樣本中最多有1 728 000種組合，本文提出的改進在于改變建造陰影特征時原始特征值重新排列的比例。

為保證比例選取的隨機性，首先將陰影特征打亂，以[X1]、[X2]、[X3]每一行的數據作為一個整體進行行變換，如表2所示。

在5行3列的混合樣本中，假設以原算法相同的方法只隨機打亂前3行變量得到新的混合樣本，與原始樣本合并，如表3所示。

3 數值實例

3.1 數據集說明

本文使用的數據集ForestType、Dermatology、Ionosphere、biodeg均來自UCI 數據集（網址為 http：//archive.ics.uci.edu/ml/），每個數據集均隨機提取70%～80%之間的數據作為訓練集，剩下的數據作為測試集，數據集具體說明見表4。

3.2 Boruta算法改進結果

為檢驗改進Boruta算法的降維效果，分別對四組數據進行運行實驗，首先計算出不使用特征選擇算法，以及p值分別從0以0.1為間隔取到1（取1時即為原算法）的改進算法得到的特征數，并使用隨機森林作為分類器建立模型，在測試集上檢驗模型得到預測性能。為避免隨機誤差的影響，特征數及后續預測皆為計算10次取得的均值，其中，圓圈代表特征數，三角形代表預測性能，見圖3-圖6。

可以看出，幾組數據集在使用改進Boruta算法進行特征選擇的情況下，得到的模型預測性能在幾種方法中均較高，比使用原始Boruta算法（[p=1]）以及不使用特征選擇算法時的模型預測性能更好。在ForestTpye數據集中發現，[p]從0.3～0.4之后特征選擇值出現變化，對應預測性能得到提高，特征數為20;而在Dermatology數據集中，改進算法對該數據的特征選擇結果與原算法完全相同，特征數為33;在Ionosphere數據集中從0.6～0.7變化時，特征選擇結果出現變化，預測性能隨之降低，性能最優時特征數為33;在biodeg數據集中，改進算法對該數據的特征選擇結果也同樣與原算法相同，特征數為31。對4個數據集結果進行分析比較發現，在0.4～0.6區間上，預測性能均達到各自的最高值。歸納發現，不同樣本數不同特征數的數據集，代表混合比例的[p]值在區間[0.4，0.6]中取值時，預測性能可達最優。究其原因，隨著p值從0.1開始增加，陰影特征樣本可提供更多信息，然而隨著p值的進一步增大，特別當p值接近于1時，數據冗余反而會降低預測性能。為方便改進算法的使用，不失一般性，取[p]值為區間中值，即0.5。因此得出結論，改進Boruta算法在降低樣本復雜度的情況下修正了特征選擇結果，使模型得到了更高的預測性能。

3.3 與傳統特征選擇算法對比

為進一步檢驗改進的Boruta算法預測性能，選取兩種傳統特征選擇方法與改進Boruta算法進行比較，分別是平均減少不純度和隨機LASSO（改進算法的特征數由[p]=0.5時計算得到）。

（1）計算平均減少不純度。當訓練決策樹時，可計算每個特征減少了多少樹的不純度。當訓練決策樹森林時，則可計算出每個特征平均減少了多少不純度，并把平均減少的不純度作為特征選擇的值[12-15] 。

（2）隨機LASSO[16-18]。該方法使用正則化方法把額外的約束或懲罰項加到已有模型（損失函數）上，以防止過擬合并提高泛化能力。損失函數由原來的[E（X，Y）]變為[E（X，Y）+alpha*||w||]。[w]是模型系數組成的向量，[||.||]一般是[L1]或[L2]范數，[alpha]是一個可調的參數，控制著正則化強度。[L1]正則化時即為Lasso。Lasso能夠對變量進行篩選并降低模型的復雜度。這里的變量篩選指不把所有的變量都放入模型中進行擬合，而是有選擇地把變量放入模型，從而得到更好的性能參數[19-20]。

由于傳統特征選擇算法得到的結果為特征重要性排序，因此本文采取如下方式對幾種方法進行對比：觀察改進Boruta算法選擇的[n]個特征，及兩種傳統算法特征重要性順序得出的前[n]個特征，記改進Boruta算法和傳統算法得到的相同特征占比為特征相符度。以這三組特征分別建立模型得到模型預測性能，如表5所示。

從表5可以發現，在ForestType、Dermatology和biodeg數據集上驗證的結果均為改進Boruta算法的結果最優，而Ionosphere數據集的實驗結果則與3種方法得出的特征完全相同，得到的模型預測性能也相同。因此，可得出結論：傳統算法與改進Boruta算法篩選出相同特征數情況下，改進的Boruta算法效果最佳。

4 結語

數據集存在過多的無用變量影響后續模型，因此特征選擇必不可少。本文在研究Boruta算法時發現了陰影特征樣本復雜度較高問題，在陰影特征樣本構建時選擇比例0.4-0.6進行改進，不僅降低了樣本復雜度，還修正了特征選擇結果，從而得到比原Boruta算法更優的預測性能，在與兩種傳統的特征選擇算法相比較時具有更優的預測結果，因此改進的Boruta算法在成功降低樣本復雜度的同時提高了預測性能。至于混合比例為何在0.4～0.6之間會取得較好效果是一個值得進一步研究的問題。

參考文獻：

[1] KOHAVI R， JOHN G H.Wrappers for feature subset selection[J]. Artificial Intelligence，1997（3）：273-324.

[2] 周志華. 機器學習[M]. 北京：清華大學出版社，2016.

[3] 李航. 統計學習方法[M]. 北京：清華大學出版社，2012.

[4] 邊肇祺，張學工. 模式識別[M]. 第2版. 北京：清華大學出版社，2000.

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

[6] YAO H，LIU C，ZHANG P，et al. A feature selection method based on synonym merging in text classification system[J]. Eurasip Journal on Wireless Communications & Networking，2017（1）：166-167.

[7] INZA I，LARRA？AGA P，BLANCO R，et al. Filter versus wrapper gene selection approaches in DNA microarray domains[J]. Artificial Intelligence in Medicine，2004， 31（2）：91-103.

[8] 姚登舉，楊靜，詹曉娟. 基于隨機森林的特征選擇算法[J]. 吉林大學學報，2014，44（1）：137-141.

[9] PENG H，LONG F，DING C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. IEEE Transactions pattern analysis and machine intelligence，2005，27（8）：1226-1238.

[10] ZHOU P，HU X，LI P，et al. Online feature selection for high-dimensional class-imbalanced data[J]. Knowledge-Based Systems，2017（136）： 187-199.

[11] SHAO H， LI G，LIU G， et al. Symptom selection for multi-label data of inquiry diagnosis in traditional Chinese medicine[J]. Science China Information Sciences， 2012， 54（1）： 1-13

[12] KURSA MB，RUDNICKI W R. Feature selection with the Boruta package[J].? Journal of Statistical Software，2010，36（11）：1-13.

[13] 郭海山，高波涌，陸慧娟. 基于Boruta-PSO-SVM的股票收益率研究[J]. 傳感器與微系統，2018（3）：194-197.

[14] SHAHEEN A，IQBAL J. Spatial distribution and mobility assessment of carcinogenic heavy metals in soil profiles using geostatistics and random forest， Boruta algorithm[J]. Sustainability， 2018， 10（3）：799-780.

[15] BREIMAN L. Random forests， machine learning 45[J]. Journal of Clinical Microbiology， 2001（2）：199-228.

[16] OUSSAR Y. Ranking a random feature for variable and feature selection[J]. Journal of Machine Learning Research，2003（3）：1399-1414.

[17] 師彥文， 王宏杰.? 基于新型不純度度量的代價敏感隨機森林分類器[J].? 計算機科學，2017， 44（b11）：98-101.

[18] DAMBROSIO A， TUTORE V A. Conditional classification trees by weighting the Gini impurity measure[M].? New Perspectives in Statistical Modeling and Data Analysis， Springer Berlin Heidelberg， 2011：273-280.

[19] KHAN A，BAIG A R. Multi-objective feature subset selection using non-dominated sorting genetic algorithm[J].? Journal of Applied Research & Technology， 2015， 13（1）：145-159.

[20] 李洪成，許金煒，李艦.? 機器學習與 R 語言[M]. 北京： 機械工業出版社，2015： 65-67.

[21] 王小寧，劉擷芯，黃俊文.? R 語言實戰[M]. 北京： 人民郵電出版社，2016： 363-367.

[22] 劉睿智，杜溦. 基于LASSO變量選擇方法的投資組合及實證分析[J].? 經濟問題， 2012（9）：103-107.

[23] 張秀秀，王慧，田雙雙，等. 高維數據回歸分析中基于LASSO的自變量選擇[J]. 中國衛生統計， 2013， 30（6）：922-926.

[24] 胡敏杰，林耀進，王晨曦，等. 基于拉普拉斯評分的多標記特征選擇算法[EB/OL]. [2018-08-21]. http：//kns.cnki.net/kcms/detail/51.1307.TP.20180719.1010.014.html

[25] ALHAMZAWI R，HTM A. The Bayesian adaptive Lasso regression[M].? Mathematical Biosciences， 2018.

（責任編輯：杜能鋼）