一種新的選擇集成算法

王道慶，孫浩軍

（汕頭大學(xué)工學(xué)院計(jì)算機(jī)系，廣東 汕頭 515063）

0 引 言

集成學(xué)習(xí)（ensemble learning）通過訓(xùn)練數(shù)據(jù)集來訓(xùn)練若干個(gè)有差異的個(gè)體學(xué)習(xí)器（base learning machine），并使用某種規(guī)則將這些個(gè)體學(xué)習(xí)器的學(xué)習(xí)結(jié)果進(jìn)行整合.相對(duì)于單個(gè)學(xué)習(xí)器，集成學(xué)習(xí)在多數(shù)情況下可以顯著提升學(xué)習(xí)系統(tǒng)的泛化性能.因此，人們?cè)诤芏鄬?shí)際應(yīng)用領(lǐng)域直接或間接地使用了集成學(xué)習(xí)算法.

集成學(xué)習(xí)可以利用多個(gè)學(xué)習(xí)器來獲得比單一學(xué)習(xí)器更好的效果（泛化性能），因此一種較為直觀的思路是通過大量的基學(xué)習(xí)器來獲得更好的集成效果.目前，多數(shù)的集成學(xué)習(xí)算法是采取這種思路，其中最有代表性的是Boosting和Bagging算法.隨著參與集成的學(xué)習(xí)器數(shù)量增多，集成學(xué)習(xí)的過程中不可避免地存在以下問題：集成的速度因?yàn)榇罅康幕鶎W(xué)習(xí)器產(chǎn)生和集合過程變得緩慢；集成的規(guī)模過大會(huì)占用較大的存儲(chǔ)空間并耗費(fèi)預(yù)測過程的時(shí)間.因此，人們開始考慮：使用較少量的基學(xué)習(xí)器是否可以達(dá)到更好的性能？2002年，周志華等[1]人提出了“選擇性集成”的概念，對(duì)上述問題得出肯定的結(jié)論.相關(guān)的理論分析和實(shí)驗(yàn)研究表明，從已有的基學(xué)習(xí)器中將作用不大和性能不好的個(gè)體刪除，只選出部分個(gè)體學(xué)習(xí)器用于構(gòu)建集成確實(shí)可以得到更好的預(yù)測效果.

1 選擇集成方法

選擇集成算法的思想大體上都是在個(gè)體學(xué)習(xí)器生成和學(xué)習(xí)器集合這兩個(gè)階段之外再增加一個(gè)選擇學(xué)習(xí)器或者剔除學(xué)習(xí)器的階段.根據(jù)算法所采用的選擇策略的不同，選擇集成方法主要有以下幾類：迭代優(yōu)化法，聚類分簇法，排序法，其他類型.

迭代優(yōu)化法中，周志華等[1]提出了基于實(shí)值編碼遺傳算法的選擇性集成學(xué)習(xí)算法GASEN（Genetic Algorithm based Selective ENsemble），主要思想是用遺傳算法來優(yōu)化每個(gè)基分類器被賦予的權(quán)重，最終權(quán)重低于一定閾值的基學(xué)習(xí)器被剔除.受限于迭代優(yōu)化方法的特性，GASEN等基于遺傳算法的選擇集成的收斂速度均較慢.爬山法應(yīng)用于選擇性集成的策略可以看做一個(gè)逐步求優(yōu)的搜索過程，每次的搜索都建立在上一步的基礎(chǔ)上，這種貪心策略可以使搜索空間較快地減小，速度得到提高.爬山法根據(jù)搜索的方向可以分為前向選擇（Forward Selection）和后向消除（Backward Elimination）兩種[2].爬山法的思想簡單，但隨著問題規(guī)模的擴(kuò)大，在算法運(yùn)行的初期的搜索空間仍較大，計(jì)算耗費(fèi)仍不能控制在理想的范圍內(nèi).

聚類分簇法一般首先采用某種聚類算法將相似的基分類器分在不同的簇，然后再在每個(gè)簇中選擇一定數(shù)量的基分類器，最后進(jìn)行集成.此類方法的思路是利用聚類操作來保證基分類器的多樣性，輔以簇內(nèi)選擇操作來去除“無益”分類器.文獻(xiàn)[3]從驗(yàn)證集分類結(jié)果構(gòu)造的矩陣中得到不同基分類器間的歐氏距離，應(yīng)用K-means聚類算法將基分類器進(jìn)行分組，并根據(jù)基分類器子集的準(zhǔn)確性和多樣性進(jìn)行選擇.文獻(xiàn)[4]定義了新的基分類器間的距離，然后采用層次凝聚的聚類算法來尋找相似預(yù)測結(jié)果的分類器簇，在算法的每一步后選擇每個(gè)簇中到其他簇的平均距離最大的基分類器，采用簡單投票法進(jìn)行集成.再在形成的各種分類器子集中選取對(duì)驗(yàn)證集預(yù)測效果最佳的子集.此類方法根據(jù)選用的聚類策略的不同，計(jì)算時(shí)間耗費(fèi)也不同，但總體上看也不是一種簡單快速的方法.

排序法是采用某種特定的評(píng)估函數(shù)對(duì)所有基分類器進(jìn)行排序，然后按照次序選擇一定比例的基分類器.排序法最大優(yōu)勢(shì)在于選擇速度快.目前排序法已經(jīng)有很多算法取得不錯(cuò)的效果，其中方向排序[5]和邊界距離最小化[6]這兩種算法是比較有代表性且性能較好的.排序法的關(guān)鍵在于排序標(biāo)準(zhǔn)的確立.早期的算法大多依據(jù)預(yù)測性能等進(jìn)行排序，但實(shí)驗(yàn)結(jié)果表明：個(gè)體基分類器預(yù)測性能好并不能保證集成分類器也有好的性能，所以還需結(jié)合分析分類器之間的相關(guān)性，使得分類器間具有互補(bǔ)性.排序法的另一個(gè)關(guān)鍵在于確立怎樣的保留比例.一種是根據(jù)實(shí)驗(yàn)統(tǒng)計(jì)直接確定一個(gè)保留比例，一種是設(shè)定基于精度等度量的閾值，達(dá)到閾值的被保留.

總結(jié)各類選擇集成方法的特點(diǎn)，本文在排序法的基礎(chǔ)上采取“貪心策略”設(shè)計(jì)了一種快速剪枝選擇集成算法（Fast Pruning Selective Ensemble，F(xiàn)PSE）.

2 FPSE算法

2.1 算法思路

由上節(jié)介紹可知，基于排序法的選擇集成算法計(jì)算速度快，策略簡單，但尋求一個(gè)合適的排序準(zhǔn)則是關(guān)鍵.本文將提出的FPSE就是屬于此類算法，但在排序策略上進(jìn)行了一定的改進(jìn)以求達(dá)到更好的效果.

在大多數(shù)的算法中，為了選擇出最理想的分類器子集，會(huì)在訓(xùn)練數(shù)據(jù)集中單獨(dú)分出一小部分?jǐn)?shù)據(jù)集，可以用分類器在此數(shù)據(jù)集上的分類結(jié)果來評(píng)價(jià)其準(zhǔn)確性，也可以根據(jù)各分類器的分類結(jié)果來計(jì)算分類器差異度，或者使用其他的評(píng)估指標(biāo)計(jì)算依據(jù).這種單獨(dú)拿出部分訓(xùn)練數(shù)據(jù)的做法究竟是否會(huì)導(dǎo)致過擬合尚存在爭議，但有一點(diǎn)可以肯定，因?yàn)橛糜谟?xùn)練的數(shù)據(jù)量減少，必然會(huì)影響基分類器的訓(xùn)練效果.

可以考慮設(shè)計(jì)一種無需損失訓(xùn)練數(shù)據(jù)集的方法來對(duì)基分類器進(jìn)行評(píng)估，這樣做可以使訓(xùn)練數(shù)據(jù)更完整，基分類器預(yù)測精度在總體上得到提升，從而達(dá)到提升集成系統(tǒng)效果的目的.在FPSE算法中設(shè)計(jì)了一種策略，即使用“包外樣例”和全體訓(xùn)練數(shù)據(jù)分別評(píng)估“準(zhǔn)確性”和“差異度”的辦法來取代單獨(dú)設(shè)置數(shù)據(jù)集進(jìn)行基分類器評(píng)估，并把這種策略與一般評(píng)估策略進(jìn)行性能對(duì)比.

算法的主要流程概括為：（1）首先根據(jù)泛化性能對(duì)全體分類器進(jìn)行排序；（2）直接刪除少量的較差個(gè)體分類器；（3）根據(jù)（1）、（2）步的結(jié)果，逐次選擇泛化性能最差的個(gè)體分類器，若將其刪除可以使剩余分類器差異度提高，則刪除，否則保留，這一步的目的是保留下來的分類器有較大的差異度.

因?yàn)椴扇∨判虿呗?，所以算法的主要?yōu)勢(shì)是快速簡單，除此之外，分類器泛化性能和分類器間差異度的計(jì)算方法則是另一個(gè)優(yōu)勢(shì).一般比較常用的做法是：首先從全體數(shù)據(jù)集中劃分出一個(gè)驗(yàn)證集Mval，用于計(jì)算各基分類器Ci的準(zhǔn)確性R：

各基分類器間差異性指標(biāo)也一般使用驗(yàn)證集Mval來計(jì)算.但是這樣的做法可能存在兩方面缺陷：一是導(dǎo)致部分訓(xùn)練數(shù)據(jù)的損失，尤其在訓(xùn)練數(shù)據(jù)不夠多的情況下，容易導(dǎo)致訓(xùn)練的模型欠擬合；二是將優(yōu)化目標(biāo)設(shè)定為一部分?jǐn)?shù)據(jù)集（即Mval），在部分算法中可能會(huì)導(dǎo)致生成模型的偏移，不能接近最佳模型.

新算法不再單獨(dú)設(shè)立驗(yàn)證集Mval從而避免上面提出的缺陷.FPSE算法的分類器生成階段是采用Bagging算法的Bootstrap思路，在每個(gè)個(gè)體分類器生成的時(shí)候只使用了約63.2%的數(shù)據(jù)樣例，剩下的約36.8%的樣例則用來計(jì)算該分類器的泛化能力.分類器的差異度則評(píng)估每個(gè)分類器對(duì)整個(gè)訓(xùn)練集的判別結(jié)果的差異.

泛化性能的計(jì)算使用預(yù)測準(zhǔn)確率就可以近似代替，但個(gè)體分類器間差異度的計(jì)算方式目前有很多選擇.已經(jīng)有很多個(gè)體學(xué)習(xí)器間的差異性（多樣性）度量方法，如KW方差[7]，K度量[8]，難度度量θ[9]，廣義多樣性GD[10]，PCDM度量[11]，熵度量E[12]等.本文算法選用改進(jìn)的熵度量E[13]作為評(píng)估分類器間差異程度的指標(biāo).

文獻(xiàn)[13]提出的這種熵度量，沒有使用對(duì)數(shù)函數(shù)，更易處理且能快速運(yùn)算.這種度量方式的主要思想是利用多個(gè)分類器的分類結(jié)果的熵值來表征分類器間的差異程度.計(jì)算公式為：

其中，N代表樣例數(shù)，L代表基分類器數(shù)目，zj表示第j個(gè)樣例，l（zj）表示對(duì)樣例分類正確的分類器的數(shù)量.對(duì)于樣例zj，如果所有的基分類器輸出結(jié)果一致，即沒有差異性，則此時(shí)熵度量值為0；如果一半（即個(gè)）的分類器分類正確，另一半錯(cuò)誤，則熵度量值為1，此時(shí)集成系統(tǒng)的差異性最大.

不妨記上述熵度量為Ent，記經(jīng)典熵度量[12]為Ecc，假設(shè)在分類器數(shù)量無窮多情況下，a為正確分類數(shù)量占比，兩種度量方式結(jié)果為：

圖1顯示了兩種熵值與a的關(guān)系，其中橫坐標(biāo)代表a值，縱坐標(biāo)代表熵值.這兩種度量在計(jì)算效果上基本相當(dāng)，但顯然運(yùn)算速度上Ent要更快速.

圖1 兩種熵度量與分類正確占比a的關(guān)系

2.2 FPSE算法

上節(jié)說明了算法的一些關(guān)鍵問題，并闡述了算法設(shè)計(jì)的思路.下面是FPSE算法的完整表述.

算法描述：

輸入：數(shù)據(jù)集D＝（{x1，y1），（x2，y2），…，（xm，ym）}；基學(xué)習(xí)算法L；初始基分類器數(shù)量T；初步刪除比例k1，最終保留比例k2，差異度最小提升量ΔE；

輸出：對(duì)每個(gè)新樣例點(diǎn)x，集成系統(tǒng)的預(yù)測結(jié)果為

過程：

1.for t＝1，2，…，T do；

2.ht＝L（tD，Dbootstra）p；

3.end for；

4.計(jì)算每個(gè)分類器在包外樣本上的準(zhǔn)確率Acchi；

5.根據(jù)準(zhǔn)確率排序分類器得集合{h1，h2，…，hT（}Acchi＜Acchi＋1）；

6.根據(jù)初步刪除比例k1刪除掉分類器集合前部分的分類器，剩余集合S{m1，m2，…，mi，…（}Accmi＜Accmi＋1），剩余數(shù)量Num；

7.while Numbers＞k2*Num；

8.計(jì)算當(dāng)前分類器群差異度Enow；

9.計(jì)算去除第i個(gè)分類器后，分類器群體差異度Enext；

10.if Enext－Enow＞ΔE；

11.delete mifrom S；

12.i＋＋；

13.已經(jīng)刪除該基分類器，返回7；

14.無法繼續(xù)刪除過程或刪除數(shù)量達(dá)到閾值，停止；

15.簡單投票法集成剩余分類器.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

本文根據(jù)算法的類型、樣本適應(yīng)等因素，選取了UCI數(shù)據(jù)庫中的12個(gè)數(shù)據(jù)集來測試FPSE算法的性能.為進(jìn)行對(duì)比實(shí)驗(yàn)，使用開源算法包sklearn上提供的幾個(gè)分類學(xué)習(xí)算法作為對(duì)照組，它們分別是：Cart決策樹、支持向量機(jī)、AdaBoost算法、Bagging算法.其中AdaBoost算法、Bagging算法以及本文FPSE算法都將使用Cart決策樹生成基分類器.為驗(yàn)證本文算法對(duì)差異度和泛化性能評(píng)價(jià)所做改進(jìn)的有效性，在訓(xùn)練集中設(shè)置驗(yàn)證集作為優(yōu)化目標(biāo)并嵌入進(jìn)本文算法中，不妨稱之為FPSE-useVal.并加入對(duì)照組.

實(shí)驗(yàn)中，將數(shù)據(jù)全集隨機(jī)分開，80%用作訓(xùn)練集，20%用作測試集.對(duì)每個(gè)數(shù)據(jù)集重復(fù)此過程50次.

使用分類結(jié)果的正確率作為評(píng)價(jià)指標(biāo)，計(jì)算公式如下：

其中，N為樣例數(shù)量（分類器預(yù)測的次數(shù)）；Ci在分類器預(yù)測正確時(shí)為1，錯(cuò)誤時(shí)為0.本式代表分類器預(yù)測結(jié)果的總命中數(shù)占預(yù)測次數(shù)的比例.

本文使用了12個(gè)數(shù)據(jù)集作為算法的測試，數(shù)據(jù)集都來源于UCI.這12個(gè)數(shù)據(jù)集分別是：iris，wine，banlance-scale，ecoli，glass，breast-cancer-wisconsin，zoo，pima-indiansdiabetes，transfusion，contraceptive-method-choice，habermans-survival，ionosphere.數(shù)據(jù)集基本信息見表1.

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)結(jié)果見表2.在正確率指標(biāo)值后方加入誤差波動(dòng)范圍值供參考，該數(shù)值取的是50次實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差.

表1 數(shù)據(jù)集基本信息表

表2 各算法在數(shù)據(jù)集上的正確率表（決策樹作為基分類器）

圖2和圖3描述了DT-Tree、SVM、AdaBoost、Bagging、FPSE-u和FPSE等6個(gè)算法分別在12個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率.

圖2 算法在數(shù)據(jù)集上的正確率直方圖part1

圖3 算法在數(shù)據(jù)集上的正確率直方圖part2

因?yàn)榻y(tǒng)一選用決策樹作為基分類器，使得AdaBoost算法、Bagging算法和本文的FPSE算法的對(duì)比更客觀.就正確率而言（見表2），有以下幾點(diǎn)值得關(guān)注：

（1）FPSE算法明顯比基分類算法（Cart決策樹）的平均正確率高（最少1個(gè)百分點(diǎn)，最多8個(gè)百分點(diǎn)）；

（2）FPSE算法除了在pima-indians-diabetes、transfusion、habermans-survival三個(gè)數(shù)據(jù)集上表現(xiàn)略遜于Bagging算法，在其他的9個(gè)數(shù)據(jù)集上正確率都優(yōu)于Bagging算法.在全部12個(gè)數(shù)據(jù)集上，F(xiàn)PSE算法與AdaBoost算法相比，正確率具有明顯優(yōu)勢(shì)；

（3）可以看到，單獨(dú)設(shè)置驗(yàn)證集的本文算法的變型FPSE-useVal算法的正確率表現(xiàn)在全體12個(gè)數(shù)據(jù)上都遜于本文FPSE算法.這也就是說明FPSE算法使用的分類器評(píng)估策略是有效的，比單獨(dú)設(shè)置數(shù)據(jù)集來評(píng)估分類器性能的做法更能提升集成泛化性能；

（4）在 ecoli、glass、zoo、ionosphere、contraceptive-method-choice 數(shù)據(jù)集上，本文FPSE算法比SVM算法的正確率表現(xiàn)得更優(yōu)秀；

（5）參考誤差范圍值，F(xiàn)PSE算法的正確率變化也較為穩(wěn)定.

4 總結(jié)

本文主要提出了一種新的選擇性集成學(xué)習(xí)算法.其主要的優(yōu)勢(shì)是能夠較為顯著地提升一個(gè)學(xué)習(xí)系統(tǒng)的泛化能力，在部分?jǐn)?shù)據(jù)集上的表現(xiàn)大致與Bagging算法和AdaBoost算法相當(dāng)甚至略優(yōu)于它們.本文工作的一個(gè)特色在于，提出了一種計(jì)算分類器的預(yù)測準(zhǔn)確性和群體差異性的方法，且無需單獨(dú)設(shè)置部分?jǐn)?shù)據(jù)集.使用此方法確實(shí)可以進(jìn)一步提升集成系統(tǒng)的預(yù)測性能.

后續(xù)還可以繼續(xù)展開的工作有：選取更多的數(shù)據(jù)集來驗(yàn)證FPSE算法的效能，并在實(shí)際應(yīng)用領(lǐng)域使用FPSE算法來解決分類問題；對(duì)FPSE算法中個(gè)體分類器評(píng)估的做法進(jìn)行概括與改進(jìn)，并嵌入其他的一些選擇集成算法，驗(yàn)證此做法是否具有普適性.