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

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

1 引言

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

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

2 mBagging 原理

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

(1)

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

3.1 數(shù)據(jù)

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

3.2 決策樹

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

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

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

4 實驗結果

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

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

4.1 OBB袋外錯誤率

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

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

4.2 算法運行時間

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

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

4.3 特征變量重要性排列

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

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

5 討論

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

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