周 鋼 郭福亮

(海軍工程大學 湖北 武漢 430033)

0 引 言

集成學習是使用投票(或權重)的方法集成多個基分類器預測值的學習算法，是機器學習的重要研究方向[1-2]。典型的集成學習方法包括袋裝(Bagging)、梯度提升(AdaBoost)和隨機森林等[3-5]，并在時間序列預測、協(xié)同過濾推薦、信用欺詐甄別等領域發(fā)揮重要作用[6-8]。

研究表明，基分類器的多樣性(diversity)是決定集成學習預測精度和泛化能力的重要因素[9]。集成系統(tǒng)的泛化性能與margin分布相關，在訓練樣例集上減少margin能夠改善集成學習的泛化誤差邊界[10]，在基分類器精度相同且確定時，集成學習的基分類器的最小margin最大化同集成學習多樣性的最大化是一致的[11]。

因此，本文以Bagging集成學習方法優(yōu)化為研究背景，將margin作為集成學習多樣性度量方法，并以此改進Bagging中基分類器的放回抽樣過程。通過動態(tài)調整基分類器權重，實現(xiàn)對錯分數據樣本集的margin值(訓練數據集的最小margin數據集)的最大化，從而提升集成學習多樣性，提高集成學習的泛化精度。

1 基于margin的集成學習多樣性度量

從集成學習的泛化誤差入手，研究集成學習泛化誤差的偏差-方差分解和誤差-分歧分解，探討集成學習多樣性對泛化誤差的影響，進而研究margin最大化與集成學習多樣性之間的相關性，構建了集成學習多樣性的margin度量方法。

1.1 集成學習多樣性

文獻[12]分別從不同角度提出了集成泛化誤差的偏差-方差分解方法。假設有多個基分類器Hi，集成學習在樣本x0上的損失函數(平方誤差)的期望為：

E(x0)=E(f(x0)-H(x0))2=E(g(x0)-H(x0))2+s2=

E(EH(x0)-g(x0))2+E(EH(x0)-H(x0))2+

Var(H(x0))+(1-1/n)Cov(hi(x0))+s2

(1)

式中:Bias2為集成平方偏差，表征各個體分類器預測均值與實際值的偏離情況；Var為集成平方差，表征各個體分類器預測均值與實際值的偏離情況；Cov為個體分類器相關性，表征各個體分類器間的相關程度，當Cov=0時，認為個體分類器相互獨立。

偏差-方差分解方法能夠解釋通過降低相關度(Cov值)來降低泛化誤差E(x0)，但是忽視了降低Cov將會增大Var和Bias的值，同時也缺乏對AdaBoost集成方法在梯度提升過程中泛化精度持續(xù)提升的有效解釋[13]。

文獻[14]則從誤差-分歧分解角度針對多樣性在集成學習泛化誤差中的作用進行探討，假設樣本x的分布概率為p(x)，那么集成的泛化誤差：

(2)

引入EH(x)為加權集成分類器，可取權重為均值，則有：

Err(h(x))-Amb(h(x))

(3)

式中:Err為分類器Hi的誤差加權均值；Amb為分類器Hi的加權分歧值，表征基分類器Hi對于樣本x上的分類不一致性。在基分類器誤差確定基礎上，基分類器Hi的多樣性越大，那么集成泛化誤差E就越小。但是由于Amb值需要在集成學習模型構建后才能估計多樣性，且該推理過程只適用于回歸模型，在實際應用中意義不大，只能用于評價表明多樣性對集成泛化誤差的影響作用。

從偏差-方差分解和誤差-分歧分解兩個角度均可以發(fā)現(xiàn)基分類器多樣性對集成學習的預測精度和泛化能力發(fā)揮的重要積極作用，但對AdaBoost集成算法在訓練誤差為0時仍能通過梯度優(yōu)化分類器提升集成學習泛化精度的問題缺乏科學解釋[15]。

1.2 集成學習多樣性分析與度量

Margin理論可以有效解釋Boosting算法，并發(fā)展了支持向量機(SVM)理論，在集成學習的多樣性分析和度量中也有較好的可解釋性[16]。

對于集成學習中的Hi(i∈1,2,…,N)分類器，假設對于樣本x，正確分類到y(tǒng)中分類器個數為vy，分類到其他類別的分類器個數為vc，那么margin定義為[17]：

(4)

也可以表示為：

(5)

對于二分類問題，margin可以簡化為：

(6)

式(6)表示能夠正確分類基分類器Hi個數與不能正確分類Hi的數量差。

對于數據集D上的最小化margin定義為：

(7)

假設基分類器Hi的正確率為P(P>0.5)，當基分類器誤差率大于0.5時，會導致集成誤差過大，則基分類器選擇過差，因此一般設定正確率P>0.5，那么有：

2P-1

(8)

(9)

由于最小值必然小于均值，因此有：

(10)

min(margin(D))≤2P-1

(11)

平均值為：

(12)

研究常用的六類多樣性度量方法包括：雙次失敗度量，不協(xié)調度量，KW差異，Kappa度量，GD度量和diff度量[18]。可以發(fā)現(xiàn):

(13)

式中:f(P)為P的負相關函數；vn是不能被正確分類的數據樣本量，與集成邊界相關；vni為第i個基學習器的分錯數據樣本數。當各基分類器的分類正確率P一定時，vn=N(1-P)，α和β為正值常量參數。綜合常見的六類多樣性度量方法，當mean(margin(D))取最大值時，P越大，vn越小，由于vn是2次方函數，div(D)越大，即在假定分類或預測準確率P一定的情況下，平均margin越大，即所有分類器都具有相同正確分類樣本數時，多樣性越強。

實際上，當平均margin過小時，由于和精度P的直接對應關系，會降低集成學習的預測精度；當平均margin過大時，各基分類器的分類正確的數據樣本越多，導致各基分類器更多選取和關注正確分類樣本，而對于不能正確分類的缺乏分類，使得各分類器趨同化，降低多樣性。文獻[19]也驗證了樣本數據平均間隔過大會導致多樣性變小，平均間隔過小會導致準確度變小，都會影響集成學習的精度和泛化能力。

由于測試集的mean(margin(D))≥min(margin(D))，因此有：

(14)

式(14)表明：提高min(margin(D))值，則div(D)的下限值提高，進而提升集成學習基分類器之間的多樣性。關注提高min(margin(D))值，關注各基分類器難以正確分類的樣本數據，更加便于實際操作。所以，最大化最小margin值能夠提升集成學習多樣性下限并具可行性。

由于mean(margin(D))是整個訓練數據樣本Dn中margin的平均值，假設min(margin(D))對應的樣本量為m，對應數據為Dm，則有：

(15)

如果對應的min(margin(D))的數據樣本m過小，單純提高min(margin(D))對mean(margin(D))影響不大，因此在最大化min(margin(D))時，還應當考慮其對應的樣本量m。如果m值過小，關注min(margin(D))的最大化問題，則會被樣本數據中的噪聲數據干擾。因此，在選取最小margin的數據樣本量時應設置總訓練數據集數目的比例，一般可以按照裁剪決策樹的2%～5%比例設置。

2 方法設計

Bagging算法是通過有放回的隨機樣本抽樣按照同質機器學習算法構建基學習器，按照組合策略形成集成學習模型，一般按照平均權重進行組合集成。Bagging集成算法采用同質基分類器和平均權重組合策略，由于基分類器使用敏感的機器學習算法，訓練樣本的微小改變會導致基分類器的差異性，因此，Bagging算法的精度和泛化能力主要來源于抽樣隨機性產生的樣本之間差異性[20]。

2.1 基于margin的集成學習方法

由于Bagging算法的基分類器集成抽樣的隨機性難以保證各基分類器之間存在足夠的多樣性，近年來，國內外學者開展了基于margin優(yōu)化基分類器的抽樣算法以提升集成學習的精度和泛化能力的相關研究。文獻[21]研究了8種不同抽樣方法的Bagging算法在UCI上18個公開數據集的表現(xiàn)，發(fā)現(xiàn)Bagging算法中不同的樣本選擇策略會導致集成學習精度出現(xiàn)55.42%～81.86%的分布，并發(fā)現(xiàn)利用平均margin作為多樣性度量標準，能達到與基于優(yōu)化的算法相當的性能并優(yōu)于另一種基于排序的算法，具有更高的執(zhí)行效率。因此平均margin方法能有效地提高初始集成系統(tǒng)的分類效率和泛化性能。文獻[22]研究了多種基于margin的抽樣方法來構建多樣化基分類器，發(fā)現(xiàn)以優(yōu)化平均margin為排序準則的Mean D-M優(yōu)化方法在訓練數據集上能夠取得最優(yōu)分類性能的基分類器子集，而優(yōu)化與margin相關的分類損失學習基分類器的權值，并以權值由大到小的順序對基分類器排序Margin-P優(yōu)化方法在測試數據集上能夠取得最優(yōu)分類性能的基分類器子集。文獻[23]按照Boosting抽樣方法提升各基分類器精度同時提升錯分樣本權重，從而有效提高集成精度。

2.2 最大化最小margin的抽樣方法

從近年來基于margin的抽樣方法提升基分類器多樣性的相關研究來看，改進Bagging算法各基分類器的抽樣方法，關注錯分樣本，可增強各基分類器的多樣性，從而提升集成學習精度和泛化能力。本文主要從樣本數據的margin分布的角度來研究樣本抽樣方法，通過調整最小margin的樣本權重來最大化最小margin提升各基分類器的多樣性，從而提高集成學習的精度和泛化能力。

通過最大化最小margin的抽樣方法實現(xiàn)集成學習，基本思想是：對于集成學習中的有限個基分類器對訓練數據樣本進行分類，計算各數據樣本的margin，通過調整基分類器的權重，實現(xiàn)最小margin的樣本數據的margin值最大化，即最小margin值大于0且接近于預期最佳margin均值(大于0的最小值)，從而提高基分類器的多樣性，提升集成學習的精度和泛化能力。為避免優(yōu)化方法關注異常數據導致異常點分類正確決策樹權重過高導致集成學習精度顯著降低，應當設置最小margin值的樣本數據量閾值。

算法的具體步驟為：

(1) 構建基分類器：對訓練數據按照有放回抽樣的方法構建N個基分類器BC1,BC2，…，BCN，基分類器一般采用不穩(wěn)定分類算法(如C4.5決策樹)，根據文獻[24]的研究，分類器個數N一般取10或11。

(2) 樣本分類編碼：對所有訓練樣本構建N位分類編碼，按照第i個基分類器對該條訓練樣本數據正確分類或錯誤分類三種分類結果，定義該條樣本數據分類編碼的第i位分別為+1、-1，從而完成了訓練數據集的分類編碼。

(3) 計算margin值：對于訓練數據集的各樣本數據N位分類編碼，計算各位之和即為該數據樣本的margin值，并按照從小到大的順序進行排序，去除其中樣本量低于5%的數據，剩余的訓練數據定義為Dt={D1,D2,…，Dm}，其中Di為第i個獨立的分類訓練數據集，Di數據集的數據量為di，且di大于總訓練數據量的5%。

(4) 設置動態(tài)權值：對N個基分類器設置權值向量W={w1,w2,…,wN}，默認均為1，其中wi≥0，通過調整W實現(xiàn)兩個目標：

① 假設第j個訓練數據集Dj(數據量為n)的margin值最小，且Dj的分類編碼為Cj,那么通過調整W實現(xiàn)：

(16)

且f1(W)接近1。

② 在W·Cj=1前提下，對于W解空間，Dt={D1,D2,…，Dm}，求訓練數據集margin均值的最小值即為W的最優(yōu)解，即最合適的各基分類器權值向量。

f2(W)=W·(CT·Dt)

(17)

那么最優(yōu)W解為minf(W)且minf(W)>0。

在滿足目標1的條件下，對于訓練數據集，數據樣本分類編碼相同的為同一類，當基分類器數量小于數據集Dj的數據類數，W存在通解W*。

為簡化計算過程，快速求解W權重向量值，默認設置W={1}，即各基分類器權值相同，找出基分類器對Dj正確分類的基分類器組，其數量假設為m,權值向量為Wc，其余向量保持為1不變，為了提高min(margin)，達到該類數據能夠正確分類即可，將f2(W)設置為略大于0的值。

因此W的求解退化為：

ΣWc+(n-m)×1≥0

(18)

本文認為，對min(margin)的數據集Dj能夠正確分類的基分類器貢獻相同，可認為權值相同，因此Wc為同值w的m維向量，方程進一步簡化為：

w×m+(n-m)×1≥0

(19)

假設式(19)取等式，那么w=(n-m)/m，由于Dj為錯分樣本數據集中的min(margin)的數據集，因此m<0.5×n，所以w>1，提升了能夠對錯分數據集進行正確分類的基分類器權重。

同時，為了確保與原有W={1}的效果對照，確保W的各權重和為n，WT=W-Wc部分的權重值應由1調整為w′=(n-m×w)/(n-m)。

對于目標2，由于W的權重調整，f2(W)會發(fā)生變化。

f2(W)=W·(CT·Dt)=(Wc+WT)·(CT·Dt)

(20)

由于Wc權限調整較大，當Wc過大時候，可能會導致f2(W)發(fā)生較大變化(變大或變小)，同時泛化精度存在下降風險。因此，結合f2(W)優(yōu)化目標，可以設置優(yōu)化權限最大值為x(如x=2.0)，從而避免泛化精度下降。

(5) 集成基分類器：根據步驟(4)計算得到的各基分類器的最優(yōu)權值向量W，按照加權求和的方法對N個基分類器的分類結果進行集成。

從定性角度分析，根據margin相關研究，通過最大化最小margin可以提高分類器多樣性。對于Bagging集成算法，最小margin對應樣本本質上是容易錯分的數據，多個基分類器對該最小margin樣本數據進行分類，包含正確分類和錯誤分類。通過調整權值，本質是增加能夠對易錯分樣本進行正確分類的分類器權值。易錯分樣本是多個分類器對訓練數據集進行分類的邊緣點，在集成分類器過程中，更加關注能夠正確分類邊緣點(易錯分樣本)的基分類器，提高該類基分類器權重，從整體集成學習分類器的角度看待整個訓練數據集時，提高了易錯分樣本的權值。易錯分樣本代表了最小margin值，因此，調整基分類器權值本質就是優(yōu)化抽樣方法，更加關注易錯分樣本，做到最大化最小margin值。

考慮到算法執(zhí)行效率和系統(tǒng)整體性能，本文選擇調整基分類器的權重，而不直接調整數據樣本權重。

從算法執(zhí)行效率看，如果直接增加最小margin值的樣本權重，由于Bagging集成算法的各基分類器一般采用不穩(wěn)定分類算法，會使基分類器結構和分類精度發(fā)生較大變化，從而導致原有margin值發(fā)生變化，出現(xiàn)新的邊緣點或易錯分樣本。或者類似AdaBoost算法，根據新的分類器結果多次調整最小margin權重，形成序列化分類精度梯度遞升，進而導致集成方法時間復雜度倍數增加。

從系統(tǒng)整體性能看，如果僅僅考慮margin均值，存在兩個問題，一是對于目標優(yōu)化函數f(W)=W·(CT·Dt)，令f(W)=1,存在多個解難以得到最優(yōu)權值向量；二是根據1.2節(jié)分析以margin均值為最優(yōu)目標，而不考慮最小margin的最大化，會導致各分類器趨近，多樣性必然降低，泛化能力減弱。

因此，本文采用的最大化最小margin方法，關注易錯分樣本，提高易錯分樣本正確分類的分類器權值，同時控制所有訓練數據集的margin均值，限定權重提升上限從而降低泛化精度風險。

3 數據實驗分析

測試平臺使用i7的2.4 GHz處理器微機作為測試平臺，利用Python 3.6的sklearn模塊實現(xiàn)相關集成學習模型構建。

3.1 不同訓練數據集占比下的集成學習算法對比

Iris是鳶尾花卉數據集，數據樣本150個，4個屬性包括花萼長度、花萼寬度、花瓣長度和花瓣寬度，1個目標屬性為鳶尾花卉的種類，分為3類，是UCI典型機器學習中分類數據集。本實驗研究在訓練數據集占比分別為30%～70%時，對比普通Bagging集成學習方法和基于最大化最小margin的優(yōu)化Bagging集成學習方法在整個Iris數據集上的預測分類精度。由于訓練數據集抽樣的隨機性，泛化精度會存在一定波動。實驗結果如表1和圖1所示。

表1 普通Bagging和優(yōu)化算法的測試精度對比

續(xù)表1

圖1 普通Bagging和優(yōu)化算法的泛化精度對比圖

可以看出：(1) 在不同的訓練數據集占比條件下優(yōu)化后的Bagging算法比普通Bagging算法在測試數據集上泛化學習精度提高4.72%，優(yōu)化方法具有更好的泛化能力和更高的預測精度。(2) 訓練數據集占比增加時，優(yōu)化算法測試精度提高較快，普通算法精度變化不大，在訓練數據集占比為70%時，優(yōu)化算法分類預測效果最好。結合自助有放回抽樣方法，多次抽樣后63.2%的數據構建訓練數據集[25]，因此，訓練數據集占比設置為60%～70%對于優(yōu)化算法最為合理。

分析可知：在不同訓練數據集占比中，優(yōu)化方法泛化精度均高于普通方法，且在訓練數據集占比為60%～70%時精度最高。

3.2 不同數據集上的集成學習算法對比

選用UCI典型的分類數據集，研究本文的優(yōu)化改進算法與梯度提升樹(Gradient Boosting Decision Tree,GBDT)、AdaBoost、隨機森林三種集成學習方法在測試精度和執(zhí)行效率上的差異。不同數據集上的規(guī)模對比如表2所示。

表2 不同數據集上的規(guī)模對比

根據3.1節(jié)分析結果，本文優(yōu)化方法選用70%的訓練數據集，在相同硬件實驗環(huán)境下，其他集成學習方法實現(xiàn)均采用Python 3.5環(huán)境下的scikit-learn模塊的默認參數。實驗結果如圖2和表3所示。

圖2 不同數據集上的算法測試精度對比

表3 不同數據集上的算法測試精度對比

對于執(zhí)行效率，以Iris數據集對比實驗為例，AdaBoost、Bagging、隨機森林和優(yōu)化方法的執(zhí)行時間分別為0.408、0.028、0.117、0.052 s。由于優(yōu)化方法是基于最大化最小margin的集成學習方法，基礎算法使用的是并行化Bagging集成學習方法，因此，執(zhí)行效率必然優(yōu)于AdaBoost的迭代串行方法和隨機森林的并串行混合方法，與基礎Bagging方法執(zhí)行時間相當。

對于泛化精度，即在全數據集上的分類準確度，對比四種集成學習方法，可以發(fā)現(xiàn)：(1) 在5個不同類型數據集上，優(yōu)化方法的測試精度高于AdaBoost方法和普通Bagging方法，僅次于隨機森林集成學習方法。(2) 對于Iris和Heart兩類典型的數據樣本有限、分類數較少、屬性數適中的分類數據集，本文優(yōu)化方法具有最好的測試精度。(3) 對于Arrhythmia的高維稀疏數據集，本文優(yōu)化方法預測精度較差。(4) 對于Glass分類數較多的數據集，由于權重調整中同一分類的數據集樣本量偏少，優(yōu)化效率難以保證高于普通Bagging方法，導致預測精度差。

據上分析可發(fā)現(xiàn)：本文集成學習優(yōu)化方法的執(zhí)行效率優(yōu)于隨機森林等集成學習方法，不同數據集上的平均泛化精度較高，僅次于隨機森林方法，更適用于數據樣本有限、分類數較少、屬性數適中的數據集，在高維稀疏和分類數多的數據集的測試精度較差。

4 結 語

從集成學習的偏差-方差分解和誤差-分歧分解兩個方面可以發(fā)現(xiàn)基分類器多樣性是提升集成學習泛化能力和分類精度的重要因素。margin方法是一種有效的多樣性度量方法，并能有效解釋Boosting算法的泛化精度持續(xù)提升問題，因此，對數據樣本通過最大化最小margin的方法可以提升集成學習多樣性。對于Bagging方法，以數據樣本最大化最小margin為目標，更多關注最小margin的數據樣本，即易錯分數據樣本集。通過優(yōu)化抽樣方法來實現(xiàn)多樣性，為能夠正確分類易錯數據樣本的基分類器賦予更高權重，從而實現(xiàn)在集成學習抽樣中該類數據樣本的margin值更大。因此，將最大化最小margin問題簡化為基分類器權重調整問題，通過科學合理設置基分類器權重向量實現(xiàn)Bagging集成學習多樣性，從而提升集成學習泛化能力和分類精度。

通過數據實驗，發(fā)現(xiàn)本文優(yōu)化方法執(zhí)行效率優(yōu)于隨機森林等集成學習方法，隨著訓練數據占比泛化精度持續(xù)提升，在70%訓練數據占比條件下泛化精度優(yōu)于普通Bagging和AdaBoost方法，僅次于隨機森林方法。本文優(yōu)化方法對于數據樣本有限、分類數較少、屬性數適中的數據集泛化精度較好，而在高維稀疏和分類數多的數據集的泛化精度較差。