陳逸杰 唐加山

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

關(guān)鍵詞：特征選擇;Boruta;機(jī)器學(xué)習(xí);陰影特征;混合比例

DOI：10. 11907/rjdk. 182315

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0069-05

0 引言

特征選擇是機(jī)器學(xué)習(xí)方法應(yīng)用的重要步驟，現(xiàn)代數(shù)據(jù)集通常用實(shí)際模型構(gòu)建的變量來(lái)描述，而大多數(shù)變量與分類無(wú)關(guān)，這導(dǎo)致兩個(gè)問(wèn)題：①處理大型數(shù)據(jù)集會(huì)降低算法速度，占用太多資源;②當(dāng)變量數(shù)量明顯高于最優(yōu)值時(shí)，許多機(jī)器學(xué)習(xí)算法的準(zhǔn)確度會(huì)降低[1-2]。因此，進(jìn)行特征選擇就變得非常必要。特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數(shù)的過(guò)程[3-4]，是模式識(shí)別的關(guān)鍵步驟。一個(gè)好的訓(xùn)練樣本對(duì)于分類器而言至關(guān)重要，將直接影響模型預(yù)測(cè)的準(zhǔn)確度[5-6]，因此高效的特征選擇算法是本文研究的重點(diǎn)。

特征選擇算法根據(jù)所采用的特征評(píng)價(jià)策略分為過(guò)濾和包裝兩大類。過(guò)濾方法獨(dú)立于后續(xù)采取的機(jī)器學(xué)習(xí)算法，可較快排除一部分非關(guān)鍵性噪聲特征，縮小優(yōu)化特征子集搜索范圍，但它并不能保證選擇出一個(gè)規(guī)模較小的優(yōu)化特征子集。包裝方法在篩選特征過(guò)程中直接用所選特征子集訓(xùn)練分類器，根據(jù)分類器在測(cè)試集的性能表現(xiàn)評(píng)價(jià)該特征子集優(yōu)劣。該方法在計(jì)算效率上不如過(guò)濾方法，但其所選的優(yōu)化特征子集規(guī)模相對(duì)較小[7-8]。

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

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

Boruta算法和mRMR算法及HOML算法存在類似問(wèn)題，即計(jì)算時(shí)間長(zhǎng)、復(fù)雜度較高，影響了運(yùn)行效率。具體體現(xiàn)在創(chuàng)建陰影特征的樣本這一步驟中。因此，本文增加一個(gè)參數(shù)用于控制陰影特征的比例，不僅可降低樣本復(fù)雜度，還可提高預(yù)測(cè)性能。

1 Boruta算法

1.1 Boruta算法原理

Boruta算法是圍繞R包randomForest中實(shí)現(xiàn)的隨機(jī)森林分類算法構(gòu)建的包裝器。隨機(jī)森林分類算法通?？稍诓徽{(diào)整參數(shù)的情況下運(yùn)行，并給出特征重要性的數(shù)值估計(jì)。隨機(jī)森林是一種集成方法，通過(guò)對(duì)多個(gè)無(wú)偏的弱分類器投票比如決策樹(shù)來(lái)執(zhí)行分類。這些樹(shù)是在訓(xùn)練集的不同裝袋樣本上獨(dú)立構(gòu)建的。將對(duì)象之間的屬性值隨機(jī)排列引起的分類準(zhǔn)確性的損失作為屬性的重要性度量。Boruta算法考慮了森林中樹(shù)木的平均準(zhǔn)確度損失的波動(dòng)，使用平均下降精度用于度量重要性。

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

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

1.2 Boruta算法流程

算法流程如圖1所示。

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

2 改進(jìn)Boruta算法

2.1 改進(jìn)算法原理及流程

在創(chuàng)建陰影特征樣本時(shí)，對(duì)每列的全部樣本都進(jìn)行隨機(jī)重排導(dǎo)致復(fù)雜度較高。為提高運(yùn)行效率，針對(duì)樣本比例進(jìn)行改進(jìn)，改進(jìn)算法獲得陰影特征樣本流程如圖2所示。

2.3 數(shù)據(jù)模擬

本改進(jìn)算法主要體現(xiàn)在擴(kuò)展數(shù)據(jù)的陰影特征方面。原算法通過(guò)重新排列原始特征值獲得陰影特征矩陣，本文通過(guò)一組數(shù)據(jù)模擬展示改進(jìn)算法與原算法中陰影特征的具體創(chuàng)建過(guò)程。

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

此時(shí)混合樣本的復(fù)雜度為[（5?。?]，即混合樣本中最多有1 728 000種組合，本文提出的改進(jìn)在于改變建造陰影特征時(shí)原始特征值重新排列的比例。

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

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

3 數(shù)值實(shí)例

3.1 數(shù)據(jù)集說(shuō)明

本文使用的數(shù)據(jù)集ForestType、Dermatology、Ionosphere、biodeg均來(lái)自UCI 數(shù)據(jù)集（網(wǎng)址為 http：//archive.ics.uci.edu/ml/），每個(gè)數(shù)據(jù)集均隨機(jī)提取70%～80%之間的數(shù)據(jù)作為訓(xùn)練集，剩下的數(shù)據(jù)作為測(cè)試集，數(shù)據(jù)集具體說(shuō)明見(jiàn)表4。

3.2 Boruta算法改進(jìn)結(jié)果

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

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

3.3 與傳統(tǒng)特征選擇算法對(duì)比

為進(jìn)一步檢驗(yàn)改進(jìn)的Boruta算法預(yù)測(cè)性能，選取兩種傳統(tǒng)特征選擇方法與改進(jìn)Boruta算法進(jìn)行比較，分別是平均減少不純度和隨機(jī)LASSO（改進(jìn)算法的特征數(shù)由[p]=0.5時(shí)計(jì)算得到）。

（1）計(jì)算平均減少不純度。當(dāng)訓(xùn)練決策樹(shù)時(shí)，可計(jì)算每個(gè)特征減少了多少樹(shù)的不純度。當(dāng)訓(xùn)練決策樹(shù)森林時(shí)，則可計(jì)算出每個(gè)特征平均減少了多少不純度，并把平均減少的不純度作為特征選擇的值[12-15] 。

（2）隨機(jī)LASSO[16-18]。該方法使用正則化方法把額外的約束或懲罰項(xiàng)加到已有模型（損失函數(shù)）上，以防止過(guò)擬合并提高泛化能力。損失函數(shù)由原來(lái)的[E（X，Y）]變?yōu)閇E（X，Y）+alpha*||w||]。[w]是模型系數(shù)組成的向量，[||.||]一般是[L1]或[L2]范數(shù)，[alpha]是一個(gè)可調(diào)的參數(shù)，控制著正則化強(qiáng)度。[L1]正則化時(shí)即為L(zhǎng)asso。Lasso能夠?qū)ψ兞窟M(jìn)行篩選并降低模型的復(fù)雜度。這里的變量篩選指不把所有的變量都放入模型中進(jìn)行擬合，而是有選擇地把變量放入模型，從而得到更好的性能參數(shù)[19-20]。

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

從表5可以發(fā)現(xiàn)，在ForestType、Dermatology和biodeg數(shù)據(jù)集上驗(yàn)證的結(jié)果均為改進(jìn)Boruta算法的結(jié)果最優(yōu)，而Ionosphere數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果則與3種方法得出的特征完全相同，得到的模型預(yù)測(cè)性能也相同。因此，可得出結(jié)論：傳統(tǒng)算法與改進(jìn)Boruta算法篩選出相同特征數(shù)情況下，改進(jìn)的Boruta算法效果最佳。

4 結(jié)語(yǔ)

數(shù)據(jù)集存在過(guò)多的無(wú)用變量影響后續(xù)模型，因此特征選擇必不可少。本文在研究Boruta算法時(shí)發(fā)現(xiàn)了陰影特征樣本復(fù)雜度較高問(wèn)題，在陰影特征樣本構(gòu)建時(shí)選擇比例0.4-0.6進(jìn)行改進(jìn)，不僅降低了樣本復(fù)雜度，還修正了特征選擇結(jié)果，從而得到比原Boruta算法更優(yōu)的預(yù)測(cè)性能，在與兩種傳統(tǒng)的特征選擇算法相比較時(shí)具有更優(yōu)的預(yù)測(cè)結(jié)果，因此改進(jìn)的Boruta算法在成功降低樣本復(fù)雜度的同時(shí)提高了預(yù)測(cè)性能。至于混合比例為何在0.4～0.6之間會(huì)取得較好效果是一個(gè)值得進(jìn)一步研究的問(wèn)題。

參考文獻(xiàn)：

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

[2] 周志華. 機(jī)器學(xué)習(xí)[M]. 北京：清華大學(xué)出版社，2016.

[3] 李航. 統(tǒng)計(jì)學(xué)習(xí)方法[M]. 北京：清華大學(xué)出版社，2012.

[4] 邊肇祺，張學(xué)工. 模式識(shí)別[M]. 第2版. 北京：清華大學(xué)出版社，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ī)森林的特征選擇算法[J]. 吉林大學(xué)學(xué)報(bào)，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]. 傳感器與微系統(tǒng)，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] 師彥文， 王宏杰.? 基于新型不純度度量的代價(jià)敏感隨機(jī)森林分類器[J].? 計(jì)算機(jī)科學(xué)，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] 李洪成，許金煒，李艦.? 機(jī)器學(xué)習(xí)與 R 語(yǔ)言[M]. 北京： 機(jī)械工業(yè)出版社，2015： 65-67.

[21] 王小寧，劉擷芯，黃俊文.? R 語(yǔ)言實(shí)戰(zhàn)[M]. 北京： 人民郵電出版社，2016： 363-367.

[22] 劉睿智，杜溦. 基于LASSO變量選擇方法的投資組合及實(shí)證分析[J].? 經(jīng)濟(jì)問(wèn)題， 2012（9）：103-107.

[23] 張秀秀，王慧，田雙雙，等. 高維數(shù)據(jù)回歸分析中基于LASSO的自變量選擇[J]. 中國(guó)衛(wèi)生統(tǒng)計(jì)， 2013， 30（6）：922-926.

[24] 胡敏杰，林耀進(jìn)，王晨曦，等. 基于拉普拉斯評(píng)分的多標(biāo)記特征選擇算法[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.

（責(zé)任編輯：杜能鋼）