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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

迭代步驟：

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

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

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

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

再由L中隨機(jī)挑選N－K個(gè)樣本組成子集subL2，則針對(duì)種子樣本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個(gè)子分類器集成

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

（4）計(jì)算個(gè)體網(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到個(gè)體網(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 實(shí)驗(yàn)及分析

2.1 算法性能分析

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

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

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

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

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

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

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

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

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

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

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

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

表4 噪聲對(duì)4種集成方法的影響

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

［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ò)集成的說(shuō)話人識(shí)別算法仿真研究 ［J］.系統(tǒng)仿真學(xué)報(bào)，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)，周運(yùn)祥.基于神經(jīng)網(wǎng)絡(luò)集成的汽車牌照識(shí)別 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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è)計(jì) ［M］.北京：機(jī)械工業(yè)出版社，2009.］

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

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