基于mBagging的隨機森林*

鄭金萍，劉趙發(fā)，胡珍珍，李澤南，黎 姿，劉漢明，汪廷華，胡聲洲

(贛南師范大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，江西 贛州 341000)

1 引言

集成學(xué)習(xí)(Ensemble Learning)克服了單個模型或者某一組參數(shù)的模型分類效果不夠理想的不足，通過訓(xùn)練多個基學(xué)習(xí)器并對結(jié)果加以集成，達(dá)到了提高模型的穩(wěn)健性和分類精度的效果[1].隨機森林(Random Forest, RF)[2]便是典型的集成案例，利用Bagging[3]的組合方法，將多棵決策樹組合成森林，隨機森林具有訓(xùn)練模型泛化能力強、對部分特征缺失的容忍度高、訓(xùn)練高度并行化而適用于大數(shù)據(jù)集等特點,使其得到了迅速的發(fā)展，應(yīng)用領(lǐng)域包括醫(yī)學(xué)、管理學(xué)、經(jīng)濟學(xué)等.在經(jīng)濟管理方面最突出的是對客戶流失的預(yù)測[4]，而醫(yī)學(xué)更多的是對疾病的風(fēng)險的預(yù)測以及病患者的易感性[5].利用Bagging對決策樹的集成，隨機森林提高了決策樹分類器的分類精度與穩(wěn)健性[2]，但Bagging在面對大數(shù)據(jù)挖掘時存在算法時間較長等不足[6-7].

Liu等基于Bagging 算法原有的良好性能提出一種改進(jìn)的Bagging 組合方法mBagging( modified Bagging)[6-7]，并通過以最大信息系數(shù)(Maximal Information Coefficeint, MIC)[8]作為基學(xué)習(xí)器進(jìn)行組合，應(yīng)用于全基因組關(guān)聯(lián)研究(Genome-wide Association Study, GWAS)進(jìn)行了仿真實驗，結(jié)果表明mBagging 的算法時間僅為Bagging的 20%、統(tǒng)計功效提高了15% ，同時假陽率也降為Bagging的69%[6-7]明顯優(yōu)于作為對比算法的PLINK[9]、BEAM[10]和BoNB[11].本文采用全基因組SNP仿真數(shù)據(jù)集的實驗表明，與傳統(tǒng)隨機森林相比，改進(jìn)的隨機森林在GWAS中獲得了更低的OOB (out-of-bag)袋外錯誤率和更快的運算速度.

2 mBagging 原理

在預(yù)測能力方面，組合分類器普遍優(yōu)于單個分類器，在神經(jīng)網(wǎng)絡(luò)集成[12]、隨機森林[2]和選擇性集成[13]等方法中已經(jīng)得到驗證.mBagging與Bagging的不同主要體現(xiàn)在對原訓(xùn)練集的重抽樣過程，mBagging抽樣設(shè)置袋內(nèi)數(shù)據(jù)集(訓(xùn)練集)遠(yuǎn)小于袋外數(shù)據(jù)集(測試集)個數(shù)，沒有采用傳統(tǒng)Bagging的袋內(nèi)數(shù)據(jù)集與袋外數(shù)據(jù)集一一對應(yīng)的做法.研究表明Bagging的計算復(fù)雜度僅與數(shù)據(jù)集個數(shù)有關(guān)[7].mBagging的思想可以用下式表示[6-7]：

(1)

3 數(shù)據(jù)與方法

3.1 數(shù)據(jù)

參考已有工作[6,14]的GWAS研究中復(fù)雜疾病風(fēng)險SNP(Single Nucleotide Polymorphism)的挖掘，利用PLINK工具集生成了實驗仿真數(shù)據(jù)集.數(shù)據(jù)集中對照與病例樣本各1 000個，并設(shè)置了1 980個疾病無關(guān)SNP和20個疾病風(fēng)險SNP.

3.2 決策樹

決策樹[15]是一種有代表性的機器學(xué)習(xí)分類算法，它通過訓(xùn)練好的決策樹模型中的樹形結(jié)構(gòu)節(jié)點與待分類的輸入數(shù)據(jù)作匹配分析(以進(jìn)行類別預(yù)測).它主要應(yīng)用于離散型數(shù)據(jù)挖掘，能夠在沒有先驗知識的情況下提取數(shù)據(jù)中蘊含的規(guī)則， 比神經(jīng)網(wǎng)絡(luò)等方法更具解釋性，是一種非線性模型卻具有簡單、高效的優(yōu)良性能[15].但決策樹存在易過擬合等缺點[15]，通過Bagging組合決策樹的隨機森林，改善了這一問題，進(jìn)而提高了其分類性能.

3.3 袋外數(shù)據(jù)分類錯誤率與特征變量重要性評估

隨機森林可以在內(nèi)部進(jìn)行評估[2]，誤差的無偏估計只需要基于一個獨立的測試集，這是它優(yōu)于決策樹的一大特點. 一般來說，隨機森林度量特征重要性分為利用基尼指數(shù)計算節(jié)點不純度減少和OOB袋外錯誤率表示的平均準(zhǔn)確率減少的兩種方法[2].基尼指數(shù)計算節(jié)點不純度減少具有更高的穩(wěn)定性[16]，但對具有高基數(shù)的數(shù)字特征和分類特征有傾向性，并且對于具有相關(guān)的特征，只會選擇其中之一而忽略其它(可能得到有偏差的結(jié)論)[17].OOB袋外錯誤率表示的平均準(zhǔn)確率減少應(yīng)用范圍更加廣泛，能夠衡量變量單獨分類能力以及變量間相互作用分類能力[18]，但當(dāng)分類數(shù)據(jù)不平衡時，會嚴(yán)重低估相關(guān)預(yù)測變量的重要性[19].

4 實驗結(jié)果

根據(jù)Liu等采用的比例Bt/Bv≈1/20，仿真實驗中對mBagging的Bt和Bv分別取值為20和400，同時設(shè)置兩組Bagging抽樣Bt=Bv=400、Bt=Bv=20作為對照組，用于對比實驗[14].

實驗利用MATLAB實現(xiàn)Bagging、mBagging組合決策樹的隨機森林算法.

4.1 OBB袋外錯誤率

分別對經(jīng)典的隨機森林設(shè)置Bt=Bv=400、Bt=Bv=20兩種重抽樣數(shù)，與基于mBagging的隨機森林進(jìn)行對比實驗，采用OOB袋外錯誤率作為重要性度量.3種方法的平均OOB袋外錯誤率如圖1所示.結(jié)果顯示基于mBagging的隨機森林的平均OOB袋外錯誤率是兩種經(jīng)典的隨機森林的平均.

圖1 基于Bagging與mBaggging的隨機森林平均OOB袋外錯誤率

4.2 算法運行時間

實驗硬件平臺是Intel Core i3-4170 CPU(3.70 GHz) 、4 GB內(nèi)存、集成顯卡，軟件平臺Windows 7 x86(單線程).實驗得到3種隨機森林方法的算法運行時間見表1.

表1 算法時間(a)(ms/數(shù)據(jù)集)

4.3 特征變量重要性排列

除OOB袋外錯誤率外，我們還采用基尼指數(shù)計算節(jié)點不純度減少得到各個特征變量的重要性(即SNP與疾病的相關(guān)性).表2顯示了Bt=Bv=20和Bt=Bv=400的兩種經(jīng)典隨機森林與基于mBagging的隨機森林對風(fēng)險SNP正確識別個數(shù)，同時可得到對風(fēng)險SNP判斷準(zhǔn)確率分別是80%、95%以及90%.

表2 前20個疾病風(fēng)險SNP判斷正確數(shù)

5 討論

圖1顯示，抽樣次數(shù)為20的經(jīng)典隨機森林平均OOB袋外錯誤率遠(yuǎn)大于抽樣次數(shù)為400的經(jīng)典隨機森林(0.43 vs. 0.30，平均0.37)，基于mBagging的隨機森林則處于它們之間(0.36，相當(dāng)于前兩者的平均)；從表1容易得到，基于mBagging的隨機森林的算法時間是兩種經(jīng)典隨機森林均值的53.09%.另外，由表2得到的風(fēng)險SNP準(zhǔn)確率可知，基于mBagging的隨機森林比兩種經(jīng)典隨機森林的均值提高了3%.這些實驗結(jié)果表明，與經(jīng)典隨機森林相比，基于mBagging隨機森林的平均OOB袋外錯誤率相當(dāng)，但算法時間可以得到明顯的減少，算法準(zhǔn)確率也有提高，總體優(yōu)于經(jīng)典隨機森林.

基于mBagging的隨機森林通過調(diào)整自舉抽樣過程中訓(xùn)練集與測試集的個數(shù)，在保證算法錯誤率與準(zhǔn)確率不劣于經(jīng)典隨機森林的前提下，大大縮短了算法時間，為組合方法應(yīng)用于大數(shù)據(jù)挖掘提供了新的借鑒.