一種改進的組合方法mBagging*

劉漢明，劉趙發(fā)，鄭金萍，胡聲洲

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

1 引言

有監(jiān)督的機器學習目標是利用訓練集學習一個穩(wěn)定且在各個方面表現(xiàn)都較好的分類模型，但實際情況往往不理想，大多數(shù)時候我們得到的可能是有偏模型(弱監(jiān)督模型).組合方法(Ensemble Learning，也譯為“集成學習”)就是組合多個弱監(jiān)督模型以期得到一個更好、更全面的強監(jiān)督模型.其潛在的思想是利用多個弱分類器糾正某個弱分類器得到的錯誤預測，以達到減小方差(如Bagging[1])、偏差(如ADBOOST[2])或改進預測(如Stacking[3])的目的.Bagging(Bootstrap aggregating)是Leo Breiman于1996提出的一種機器學習算法，它在改善弱分類器的穩(wěn)定性和精度上有著重要的價值.已被成功地應用于多種形式的隨機森林[4-7]、體外藥物敏感性預測[8]、生物標記選擇與分類[9]及同種型概率估計[10]等研究.Bagging能夠提高分類器的穩(wěn)定性[1]并改善其統(tǒng)計功效[11]，同時，它在含噪數(shù)據(jù)中，對模型的過擬合也不敏感[12].不過，Bagging的重抽樣技術(shù)使得它通常要消耗比較多的算法時間，在大數(shù)據(jù)挖掘中表現(xiàn)不夠理想.

Liu等在保持Bagging算法良好性能的前提下，對Bagging加以改進，提出了一種改進的Bagging組合方法mBagging(modified Bagging)[13-14]，并利用最大信息系數(shù)(Maximal Information Coefficeint, MIC)[15]作為基分類器進行組合，應用于全基因組關(guān)聯(lián)研究(Genome-wide Association Study, GWAS)，取得了較好的效果.作者的仿真實驗表明，mBagging的算法時間僅為Bagging的20%，統(tǒng)計功效提高了15%，同時假陽率也降為Bagging的69%[13-14].明顯優(yōu)于作為對比算法的PLINK[16]、BEAM[17]和BoNB[9].

2 mBagging原理

現(xiàn)有工作已經(jīng)證明，組合分類器的預測能力通常比單個分類器好得多[11].mBagging是對Bagging的一種改進，其核心思想是，在對原訓練集重抽樣時，改變Bagging方法抽樣后的訓練集與測試集個數(shù)相同的做法，讓抽樣所得的袋內(nèi)數(shù)據(jù)集(訓練集)個數(shù)遠小于袋外數(shù)據(jù)集(測試集).其算法思想可以簡單地用下式表示[13-14]：

(1)

顯然，若Bt=Bv，則式(1)表示了Bagging的算法復雜度.mBagging的改進之處就是令Bt

一般來說，組合方法通常采用“投票”法來生成x投至類j的權(quán)重Q(x,j)，并使用該權(quán)重作為重要性度量以組合分類器[4].不過，“投票”法的分類錯誤率會隨測試集個數(shù)的增加而增大[18].隨機森林則采用“百分增量”的重要性度量以克服此不足.其做法是在測試集中加入“噪聲”以測試重要性度量所表示的誤分類率的變化[4].考慮到這種加入的“噪聲”可能過強而影響算法的性能.mBagging定義了一種新的重要性度量[13-14]

(2)

其中，x、xs分別是分類器所有可能的得分和測試集屬性“替代”后的得分,x0則是“替代”前的得分.所謂“替代”就是把測試集中隨機選取的第i個屬性值用隨機選取的第j(j≠i)個屬性值替換.

3 基于皮爾遜相關(guān)系數(shù)的mBagging實驗

3.1 數(shù)據(jù)

我們以GWAS研究中SNP(Single Nucleotide Polymorphism)挖掘為例，利用PLINK工具集，采用參數(shù)OR(Odds Ratio)等于1.1～2.0(步長0.1)、MAF(Minor Allele Frequency)為 0.05～0.50(步長0.05)生成了500個獨立的仿真數(shù)據(jù)集.每個數(shù)據(jù)集包含對照與病例實例各1 000和990個疾病無關(guān)SNP及10個疾病風險SNP.

3.2 皮爾遜相關(guān)系數(shù)

皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient, PCC)[19]廣泛用于度量2個變量之間的相關(guān)程度，它由Karl Pearson從Francis Galton在19世紀80年代提出的一個相似卻又稍有不同的設想演變而來.PCC具有簡單、運算速度快的顯著優(yōu)點，但缺點也很明顯——它只用于度量變量間的線性相關(guān)程度.由于GWAS的表型與SNP之間幾乎不存在線性相關(guān)，PCC直接應用于GWAS研究中是一種弱分類器，所以，利用Bagging組合PCC是一個很好的選擇.事實上，如果Bagging組合強分類器，則其性能不僅可能無法改善，反而可能退化[1, 11-12].

4 實驗結(jié)果

4.1 統(tǒng)計功效與假陽率

使用mBagging組合PCC分類器，并采用上述參數(shù)，分析了500個仿真數(shù)據(jù)集，最后對“替代”結(jié)果作Wilcoxon檢驗得到P值，并對P值作Bonferroni校正.利用校正后的P值以0.05為閾值計算各方法的統(tǒng)計功效(Power)和假陽率(False Positive Rate, FPR).統(tǒng)計功效的計算結(jié)果如圖1所示，mBagging、Bagging(抽樣次數(shù)400)、Bagging(抽樣次數(shù)20)的中位數(shù)分別是0.90、0.70、0.10.兩種方法的FPR結(jié)果如圖2，各方法對應的FPR中位數(shù)分別是0.010、0、0.

圖1 mBagging與Baggging的統(tǒng)計功效 圖2 mBagging與Baggging的假陽率(左側(cè)是mBagging、中間和右側(cè)的是Bagging)

4.2 算法運行時間

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

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

a除數(shù)據(jù)文件讀取時間外的總時間；

b參數(shù)Bt=Bv=400的Bagging；

c參數(shù)Bt=Bv=20的Bagging.

5 討論

從圖1可以看出，mBagging方法的統(tǒng)計功效明顯優(yōu)于兩種不同抽樣數(shù)的Bagging方法，高達0.9.但圖2的FPR中位數(shù)顯示mBagging弱于Bagging，與Liu等的實驗結(jié)果不同，這是因為他們采用的是與本研究不同的基分類器，且通過實驗找到mBagging和Bagging 2種方法的最佳抽樣數(shù)后進行比較實驗.不過，雖然我們的實驗沒使用最佳抽樣數(shù)，但mBagging的FPR也僅僅0.01，說明它的優(yōu)勢還是比較明顯.另外，表1顯示mBagging方法的算法時間僅為采用參數(shù)Bt=Bv=400的Bagging的一半不到，說明Bt

Bagging算法可以通過增加抽樣數(shù)方法來提高基分類器的性能，但是，隨著訓練集的增加，過擬合的現(xiàn)象隨之加重[20]，特別是對于海量的大數(shù)據(jù)來說，這種情況更為突出[4].mBagging減少了訓練集個數(shù)，從而降低了過擬合的風險；同時，它又增加了測試集個數(shù)，為提高訓練后分類器的檢驗精度帶來了可能.

mBagging通過調(diào)整訓練集與測試集的個數(shù)平衡了統(tǒng)計功效、FPR和算法時間，取得較好的效果，為組合方法應用于大數(shù)據(jù)挖掘提供了很好的借鑒.我們通過實驗的方法驗證了mBagging的可行性，但沒有為mBagging和Bagging方法對PCC的組合尋找最佳抽樣數(shù)，這是今后需要進一步完善之處.