低關(guān)聯(lián)度的Boosting類集成算法研究

關(guān) 超，高敬陽，尚 穎

（北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院計算機(jī)系，北京100029）

0 引 言

Boosting類算法和Bagging類算法是目前神經(jīng)網(wǎng)絡(luò)集成研究中個體網(wǎng)絡(luò)生成方法最為流行的。其中Adaboost及其改進(jìn)算法［1－4］的提出解決了Boosting類算法雖然能提高網(wǎng)絡(luò)的泛化能力但穩(wěn)定性差且很難運用于實際的問題，使得Boosting類算法在很多領(lǐng)域得到應(yīng)用和改進(jìn)［5－8］。

但Adaboost存在過分調(diào)整權(quán)值的問題，學(xué)者Chun－Xia Zhang提出的Local Boost方法采用局部誤差計算方法，調(diào)整權(quán)值時更容易有區(qū)分的修改權(quán)值，能避免噪聲數(shù)據(jù)權(quán)值的累積，因此在有噪聲訓(xùn)練的情況下表現(xiàn)良好，甚至優(yōu)于Bagging方法。但有學(xué)者研究發(fā)現(xiàn)，Local Boost這類動態(tài)調(diào)整權(quán)值的方法在采用不穩(wěn)定的訓(xùn)練方法時有可能會陷入某局部最優(yōu)解［9］。且由于采用了鄰居算法，在一定程度上Local Boost的方法會使個體網(wǎng)絡(luò)之間的差異度變小，網(wǎng)絡(luò)之間的相關(guān)程度較高，學(xué)者通過引入Q－statistics統(tǒng)計方法來計算個體網(wǎng)絡(luò)之間的相關(guān)度，相關(guān)度較高的集成在某些領(lǐng)域并不適用，其泛化能力較低［10］。

我們在實驗過程中發(fā)現(xiàn)，Local Boost方法具有使局部表現(xiàn)較差的樣本在迭代過程中顯現(xiàn)出來的特性，容易將出現(xiàn)這類情況的網(wǎng)絡(luò)丟棄，在迭代次數(shù)有限時易導(dǎo)致訓(xùn)練失敗。Lazy Bagging方法采用鄰居方法圍繞測試樣本生成訓(xùn)練樣本集［11］，使網(wǎng)絡(luò)對測試樣本訓(xùn)練更有針對性，能很好地用于特定樣本的識別，能生成足夠的個體網(wǎng)絡(luò)用于集成。

基于上述考慮，本文將Lazy Bagging選取訓(xùn)練樣本的方法融入Local Boost算法，提出了Boosting類新算法BSE（boosting seeded ensemble）。BSE算法和Local Boost算法一樣能使 “較難”樣本通過計算鄰居誤差顯現(xiàn)出來，引入Lazy Bagging選取訓(xùn)練樣本的方法，采用 “較難”樣本作為種子樣本生成個體網(wǎng)絡(luò)訓(xùn)練集。把生成的樣本集針對“較難”種子樣本做 “平滑”處理，即當(dāng) “較難”樣本是噪聲樣本時，則該樣本生成的訓(xùn)練樣本集將弱化噪聲對網(wǎng)絡(luò)的影響，使整體網(wǎng)絡(luò)的穩(wěn)定性得到提高，并且使得并行訓(xùn)練成為可能，從而通過種子樣所生成的訓(xùn)練樣本集并非完全通過權(quán)值選取，隨機(jī)性較高避免了Local Boost方法生成的個體網(wǎng)絡(luò)之間高關(guān)聯(lián)度的問題，且節(jié)省了訓(xùn)練時間開銷。模型及相關(guān)度計算見第1章，利用Matlab及UCI數(shù)據(jù)集［12－14］驗證新算法對比Local Boost方法在采用不穩(wěn)定訓(xùn)練方法時迭代過程對樣本過于敏感，易陷入局部最優(yōu)解的實驗及其分析見第2章。

1 模型及相關(guān)度計算

BSE方法繼承了Local Boost能在迭代過程中通過局部誤差計算方法找出那些 “較難”樣本的特性，并將這些“較難”樣本作為Lazy Bagging方法的測試樣本，生成與其相關(guān)的訓(xùn)練樣本集。

為了度量個體網(wǎng)絡(luò)之間的相關(guān)度，我們引入了Q－statistics統(tǒng)計量，計算如下：設(shè)樣本 （xl，yl）∈樣本集Y，樣本個數(shù)為N，分類器Ci與Ck之間的相關(guān)度統(tǒng)計量矩陣關(guān)系如表1所示。

表1 Q統(tǒng)計量個體網(wǎng)絡(luò)相關(guān)

N＝A＋B＋C＋D，相關(guān)度Q統(tǒng)計量

針對M個個體網(wǎng)絡(luò)的集成，相關(guān)度度量值定義為

BSE算法將權(quán)值高的樣本作為種子樣本，從訓(xùn)練集中選擇K個鄰居形成鄰居子樣本集，再由原始樣本集中隨機(jī)選取N－K個樣本形成隨機(jī)子樣本集，兩個子集構(gòu)成了訓(xùn)練個體網(wǎng)絡(luò)的樣本集，具體如下：

設(shè)初始訓(xùn)練樣本集L共包含 N個樣本 ｛x1，x2...xN｝，每個樣本x1的權(quán)值D （i）為1/N，樣本輸出為 ｛y1，y2...yN｝，其中yi＝ ｛－1，＋1｝，目標(biāo)迭代次數(shù)為T，Ct為第t個網(wǎng)絡(luò)，初始時t＝1。

迭代步驟：

（1）在L中挑選權(quán)值最大的M個種子樣本 ｛S1，S2...SN｝。當(dāng)t＝1（初始訓(xùn)練時）或上一輪訓(xùn)練失敗時，在L中Lt＝L隨機(jī)選取M個種子樣本。

（2）針對種子樣本Si挑選K個鄰近樣本組成子集subL1，選取方法如下：

定義1 迭代過程中較難識別樣本的權(quán)值會增大，挑選時更容易被選到，樣本xi與其鄰居樣本xj的加權(quán)距離

dis’（xi，xj）從鄰居 Nei（xi）中選取 K個加權(quán)距離dis’（xi，xj）值最大的樣本構(gòu)成子集subL1。距離越近權(quán)值越大的樣本越容易被選中。

再由L中隨機(jī)挑選N－K個樣本組成子集subL2，則針對種子樣本Si的訓(xùn)練樣本集L＝subL1∪subL2，i＝1，2…M，如此組成第t輪的訓(xùn)練樣本集 ｛L1，L2...LN｝。

（3）將 ｛L1，L2...LN｝應(yīng)用于訓(xùn)練子分類器，i＝1，2…M，將得到的M個子分類器集成

由于測試種子樣本各不相同，所生成的測試樣本集之間互相獨立，因此在第一次結(jié)果集成時得到的個體網(wǎng)絡(luò)之間相關(guān)度較低。

（4）計算個體網(wǎng)絡(luò)誤差

式中：yj——樣本輸出，Ct（xj）——由輸入樣本xj得到的輸出，I為判斷Ct（xj）與yj是否相等的函數(shù)，如果相等則I＝0，否則I＝1。如果εt（xi）＞0.5則放棄網(wǎng)絡(luò)Ct，將所有樣本的權(quán)值置為1/N，返回第 （1）步。否則保存?zhèn)€體網(wǎng)絡(luò)Ct到個體網(wǎng)絡(luò)集CS，CS＝ ｛C1，C2...CR｝，R≦T繼續(xù)執(zhí)行第 （5）步。

（5）根據(jù)誤差更新樣本權(quán)值

（6）如果未達(dá)到迭代次數(shù)，返回第 （1）步，否則輸出結(jié)果，并集成。

結(jié)果集成

其算法流程如圖1所示。

2 實驗及分析

2.1 算法性能分析

數(shù)據(jù)分析實驗采用UCI數(shù)據(jù)集，并采用BP網(wǎng)絡(luò)訓(xùn)練分類器，計算4種集成方法的訓(xùn)練誤差和泛化誤差，結(jié)果見表2。

圖1 算法訓(xùn)練流程

由表2可以看出，多次試驗的結(jié)果統(tǒng)計顯示對分類數(shù)較少的Ionosphere和Iris樣本集，Boosting類算法訓(xùn)練誤差、泛化誤差都明顯優(yōu)于Bagging算法，而BSE的泛化誤差波動幅度明顯較小，且泛化誤差較低。

采用噪聲比例為10%的Ionosphere樣本，設(shè)置迭代次數(shù)為20，得到訓(xùn)練次數(shù)與泛化誤差的關(guān)系 （見圖2）。

圖2 訓(xùn)練次數(shù)與泛化誤差的關(guān)系

表2 4種集成方法的訓(xùn)練誤差/%和泛化誤差/%

由于Boosting類算法對某些積累的噪聲樣本過分匹配，造成整體網(wǎng)絡(luò)傾向于某一投票 （權(quán)值）較多的結(jié)果，迭代使個體網(wǎng)絡(luò)只對特定的 “較難”樣本適應(yīng)，陷入某一局部最優(yōu)解。從圖1可以看出，隨著訓(xùn)練次數(shù)增加，Boosting類算法泛化誤差明顯增加，BSE方法的泛化誤差增加較少。因為BSE算法采取了Bagging生成個體網(wǎng)絡(luò)，由于Bagging集成的分類器初始權(quán)值不同，即使某一分類器陷入局部最優(yōu)解，只要其它分類器不會陷入同一局部最優(yōu)解，整體網(wǎng)絡(luò)陷入某一局部最優(yōu)解的概率大大降低，得到的結(jié)果保證了差異度，從而提高了網(wǎng)絡(luò)的泛化能力。

從表3可以看出，樣本Ionosphere的Q統(tǒng)計量，BSE方法的相關(guān)度均值總是低于Local方法，而Local方法的相關(guān)度波動幅度最小，特別當(dāng)個體網(wǎng)絡(luò)學(xué)習(xí)強(qiáng)度增加時，Local方法由于生成的個體網(wǎng)絡(luò)相關(guān)度較高，那些過分匹配的噪聲樣本較低相關(guān)度的集成方法更容易積累，雖然整體抗噪性能提高，但容易受到個體網(wǎng)絡(luò)學(xué)習(xí)算法的影響，當(dāng)個體網(wǎng)絡(luò)出現(xiàn)過分匹配時其泛化誤差的增長較為迅速 （見圖2），因此，個體網(wǎng)絡(luò)之間的相關(guān)度較低的BSE算法在這一問題上表現(xiàn)較為突出。

表3 噪聲比例為10%情況下4種方法的相關(guān)度

2.2 算法穩(wěn)定性分析

選取Ionosphere的訓(xùn)練集和測試集，設(shè)置目標(biāo)迭代次數(shù)20，LB個體網(wǎng)絡(luò)數(shù)為10，得到不同噪聲水平時的泛化誤差 （%），見表4。

從表4可以看出，當(dāng)樣本噪聲增加后，BSE算法的泛化誤差增加幅度較Local Boost和AdaBoost算法小，比Bagging方法更為穩(wěn)定，且波動幅度小。Bagging方法不會造成噪聲積累 （見圖2），其集成結(jié)果趨于穩(wěn)定，而Ada－Boost和Local Boost則由于訓(xùn)練步長的增加，對積累的噪聲樣本過分匹配，導(dǎo)致泛化誤差增加。BSE算法中的個體網(wǎng)絡(luò)是一種Bagging集成，個體網(wǎng)絡(luò)之間互不相關(guān)，且在重取訓(xùn)練樣本集時將噪聲樣本 “平滑”處理 （如果某一噪聲樣本被分配以較高權(quán)值，在重取訓(xùn)練樣本時還能從該噪聲樣本鄰居中挑選類似樣本），比隨機(jī)處理更有效。

表4 噪聲對4種集成方法的影響

AdaBoost的誤差是全局誤差，只要整體樣本誤差不超過50%，個體網(wǎng)絡(luò)就可以被接受。Local Boost算法對某些“較難”樣本過分匹配時，計算的局部誤差很容易超過50%，而拋棄該個體網(wǎng)絡(luò)，從而使Local Boost相對Ada－Boost而言對樣本更敏感，生成的個體網(wǎng)絡(luò)數(shù)也更少，其分類器對初始時的權(quán)值敏感度更高。BSE算法由于引入了二次集成，個體網(wǎng)絡(luò)本身是一次Bagging集成，在挑選子樣本集時對 “較難”樣本做了平滑處理，減弱了在迭代過程中對某些樣本的過分匹配，保證了生成的個體網(wǎng)絡(luò)數(shù)。

個體網(wǎng)絡(luò)數(shù)多不表示其精度高，只是在相同條件下，BSE算法更為穩(wěn)定，對分類器的初始時的權(quán)值依賴性更少。從圖3可以看出，隨著種子個數(shù)的增加，整體網(wǎng)絡(luò)集成的泛化誤差降低，但對于Iris樣本當(dāng)種子個數(shù)大到一定程度后整體網(wǎng)絡(luò)的泛化誤差趨于穩(wěn)定。這說明當(dāng)個體網(wǎng)絡(luò)集成的分類器個數(shù)增多后，整體網(wǎng)絡(luò)對單個分類器初始權(quán)值的依賴性降低，集成結(jié)果更為穩(wěn)定。

為了比較各集成算法的時間消耗，我們比較了幾組訓(xùn)練樣本的訓(xùn)練時間，在串行處理的情況下得到的統(tǒng)計數(shù)據(jù)如表5所示。

表5 串行訓(xùn)練時間/s

圖3 種子個數(shù)的選取對集成結(jié)果的影響

從表5可以看出，新模型的時間消耗是很大的，這一點繼承了Lazy Bagging模型和Local Boosting模型的特點，Local Boosting模型在訓(xùn)練前均需要對訓(xùn)練樣本進(jìn)行預(yù)處理，計算其鄰居，這一點新模型中也需要，而新模型中的個體網(wǎng)絡(luò)由另外一次集成得到，挑選新樣本訓(xùn)練集只能通過所得到權(quán)值最高的幾個樣本確定，這是一個非常耗時的過程，由上表可以看出，BSLB算法的個體網(wǎng)絡(luò)數(shù)僅為10，在Ionosphere問題中，所耗時間是Bagging的近6倍，而樣本數(shù)較多的Letter問題中，BSLB耗費的時間是Bagging的近12倍。

采用Matlab2009a并行計算的時間消耗，為了比較各集成算法的時間消耗，比較了幾組訓(xùn)練樣本的訓(xùn)練時間，在并行處理的情況下得到的統(tǒng)計數(shù)據(jù)如表6所示。

表6 并行訓(xùn)練時間/s

從表6可以看出，雖然新模型的時間消耗很大，但由于采用了Bagging方法來生成個體網(wǎng)絡(luò)，而Bagging方法各個體網(wǎng)絡(luò)的生成互相獨立，可以采用并行計算的方法來訓(xùn)練、生成，所有其時耗可以降低到與Local Boosting方法相近，但由于采用了計算鄰居誤差的方法，這樣的計算時耗不能避免，即使采用了并行方法，時耗還是很高，而采用了并行計算的Bagging方法則不同，在實驗機(jī)器上其時耗降低到原有時耗的近1/2。

新算法采用了Local Boosting來計算鄰居及其局部誤差，這樣的計算較為耗時，而二次集成中個體網(wǎng)絡(luò)的生成采用了Bagging方法，使得并行處理成為可能，這樣的處理節(jié)省了訓(xùn)練時耗。

3 結(jié)束語

BSE算法通過Local Boost方法計算權(quán)值，采用加權(quán)距離來選取Lazy Bagging的種子樣本集，減弱了分類器對初始權(quán)值的依賴性。實驗結(jié)果顯示，訓(xùn)練得到的網(wǎng)絡(luò)更為穩(wěn)定，集成結(jié)果的誤差波動幅度較小，生成的個體網(wǎng)絡(luò)之間的相關(guān)度較低；另外BSE算法吸收了Bagging類算法 “平滑處理”“較難”訓(xùn)練樣本的優(yōu)點，即使是不穩(wěn)定的訓(xùn)練方法 （BP）也依然能給出較為穩(wěn)定的輸出結(jié)果，且在過度訓(xùn)練的情況下不會對特殊 “較難”樣本過分匹配，各個體網(wǎng)絡(luò)之間的相關(guān)度更低，減弱了個體網(wǎng)絡(luò)學(xué)習(xí)算法對集成泛化能力的影響，因此泛化能力不會因為Boosting類集成算法在不穩(wěn)定訓(xùn)練情況下受到影響，且采用了Bagging集成生成個體網(wǎng)絡(luò)使得并行處理成為可能，從而節(jié)省了時間開銷。

［1］Mohammad Assaad.Romuald bone a new boosting algorithm for improved time－series forecasting with recurrent neural networks ［J］.Information Fusion，2008，9 （1）：41－55.

［2］ZHANGChun－xia，ZHANG Jiang－she，ZHANG Gai－ying.Using boosting to prune double－bagging ensembles ［J］.Computational Statistics and Data Analysis，2009，53 （4）：1218－1231.

［3］ZHANG Huaxiang，LU Jing.Creating ensembles of classifiers via fuzzy clustering and deflection ［J］.Fuzzy Sets and Systems，2010，161 （13）：1790－1802.

［4］ZHANG Chun－xia，ZHANG Jiang－she，ZHANG Gai－ying.An efficient modified boosting method for solving classification problems［J］.Journal of Computational and Applied Mathematics，2008，214 （2）：381－392.

［5］QIAN Bo，LI Yan－ping，TANG Zhen－min，et al.Speaker recognition algorithm based on neural network ensemble and its simulation study ［J］.Journal of System Simulation，2008，20（5）：1285－1288 （in Chinese）.［錢博，李燕萍，唐振民，等.基于神經(jīng)網(wǎng)絡(luò)集成的說話人識別算法仿真研究 ［J］.系統(tǒng)仿真學(xué)報，2008，20 （5）：1285－1288.］

［6］BU Zhi－qiong，ZOU Wei－qiang，ZHOU Yun－xiang.License plate recognition based on ensemble neural networks ［J］.Computer Engineering and Design，2007，28 （19）：4741－4742（in Chinese）.［卜質(zhì)瓊，鄒衛(wèi)強(qiáng)，周運祥.基于神經(jīng)網(wǎng)絡(luò)集成的汽車牌照識別 ［J］.計算機(jī)工程與設(shè)計，2007，28（19）：4741－4742.］

［7］ZHANG Chun－xia，ZHANG Jiang－she.RotBoost：A technique for combining rotation forest and AdaBoost［J］.Pattern Recognition Letters，2008，29 （10）：1524－1536.

［8］Gonzalo Martlnez－Munoz，Alberto Suarez.Using boosting to prune bagging ensembles ［J］.Pattern Recognition Letters，2007，28 （1）：156－165.

［9］YANG Xinzhu，YUAN Bo，LIU Wenhuang.An empirical study of the convergence of RegionBoost ［G］.LNAI 5755：Proceedings of the 5th International Conference on Emerging Intelligent Computing Technology and Applications，2009：527－535.

［10］Mohammad Assaad.Romuald bone a new boosting algorithm for improved time－series forecasting with recurrent neural networks ［J］.Information Fusion，2008，9 （1）：41－55.

［11］ZHU Xingquan，YANG Ying.A lazy bagging approach to classification ［J］.Pattern Recognition，2008，41 （10）：2980－2992.

［12］ZHANG Defeng.The application of Matlab neural network design ［M］.Beijing：Machinery Industry Press，2009 （in Chinese）.［張德豐.Matlab神經(jīng)網(wǎng)絡(luò)應(yīng)用設(shè)計 ［M］.北京：機(jī)械工業(yè)出版社，2009.］

［13］MA Li.MATLAB language tutorial［M］.Beijing：Tsinghua University Press，2010 （in Chinese）. ［馬莉編.MATLAB語言實用教程 ［M］.北京：清華大學(xué)出版社，2010.］

［14］UCI repository of machine learning data bases［EB/OL］.http：//www.ies.uei.Edu/－mlearn/MLRepository.htm，1998.