一種新的選擇集成算法

王道慶，孫浩軍

（汕頭大學工學院計算機系，廣東 汕頭 515063）

0 引 言

集成學習（ensemble learning）通過訓練數據集來訓練若干個有差異的個體學習器（base learning machine），并使用某種規則將這些個體學習器的學習結果進行整合.相對于單個學習器，集成學習在多數情況下可以顯著提升學習系統的泛化性能.因此，人們在很多實際應用領域直接或間接地使用了集成學習算法.

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

1 選擇集成方法

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

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

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

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

總結各類選擇集成方法的特點，本文在排序法的基礎上采取“貪心策略”設計了一種快速剪枝選擇集成算法（Fast Pruning Selective Ensemble，FPSE）.

2 FPSE算法

2.1 算法思路

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

在大多數的算法中，為了選擇出最理想的分類器子集，會在訓練數據集中單獨分出一小部分數據集，可以用分類器在此數據集上的分類結果來評價其準確性，也可以根據各分類器的分類結果來計算分類器差異度，或者使用其他的評估指標計算依據.這種單獨拿出部分訓練數據的做法究竟是否會導致過擬合尚存在爭議，但有一點可以肯定，因為用于訓練的數據量減少，必然會影響基分類器的訓練效果.

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

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

因為采取排序策略，所以算法的主要優勢是快速簡單，除此之外，分類器泛化性能和分類器間差異度的計算方法則是另一個優勢.一般比較常用的做法是：首先從全體數據集中劃分出一個驗證集Mval，用于計算各基分類器Ci的準確性R：

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

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

泛化性能的計算使用預測準確率就可以近似代替，但個體分類器間差異度的計算方式目前有很多選擇.已經有很多個體學習器間的差異性（多樣性）度量方法，如KW方差[7]，K度量[8]，難度度量θ[9]，廣義多樣性GD[10]，PCDM度量[11]，熵度量E[12]等.本文算法選用改進的熵度量E[13]作為評估分類器間差異程度的指標.

文獻[13]提出的這種熵度量，沒有使用對數函數，更易處理且能快速運算.這種度量方式的主要思想是利用多個分類器的分類結果的熵值來表征分類器間的差異程度.計算公式為：

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

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

圖1顯示了兩種熵值與a的關系，其中橫坐標代表a值，縱坐標代表熵值.這兩種度量在計算效果上基本相當，但顯然運算速度上Ent要更快速.

圖1 兩種熵度量與分類正確占比a的關系

2.2 FPSE算法

上節說明了算法的一些關鍵問題，并闡述了算法設計的思路.下面是FPSE算法的完整表述.

算法描述：

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

輸出：對每個新樣例點x，集成系統的預測結果為

過程：

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

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

3.end for；

4.計算每個分類器在包外樣本上的準確率Acchi；

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

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

7.while Numbers＞k2*Num；

8.計算當前分類器群差異度Enow；

9.計算去除第i個分類器后，分類器群體差異度Enext；

10.if Enext－Enow＞ΔE；

11.delete mifrom S；

12.i＋＋；

13.已經刪除該基分類器，返回7；

14.無法繼續刪除過程或刪除數量達到閾值，停止；

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

3 實驗結果與分析

3.1 實驗設置

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

實驗中，將數據全集隨機分開，80%用作訓練集，20%用作測試集.對每個數據集重復此過程50次.

使用分類結果的正確率作為評價指標，計算公式如下：

其中，N為樣例數量（分類器預測的次數）；Ci在分類器預測正確時為1，錯誤時為0.本式代表分類器預測結果的總命中數占預測次數的比例.

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

3.2 實驗結果與分析

實驗結果見表2.在正確率指標值后方加入誤差波動范圍值供參考，該數值取的是50次實驗結果的標準差.

表1 數據集基本信息表

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

圖2和圖3描述了DT-Tree、SVM、AdaBoost、Bagging、FPSE-u和FPSE等6個算法分別在12個數據集上的分類準確率.

圖2 算法在數據集上的正確率直方圖part1

圖3 算法在數據集上的正確率直方圖part2

因為統一選用決策樹作為基分類器，使得AdaBoost算法、Bagging算法和本文的FPSE算法的對比更客觀.就正確率而言（見表2），有以下幾點值得關注：

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

（2）FPSE算法除了在pima-indians-diabetes、transfusion、habermans-survival三個數據集上表現略遜于Bagging算法，在其他的9個數據集上正確率都優于Bagging算法.在全部12個數據集上，FPSE算法與AdaBoost算法相比，正確率具有明顯優勢；

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

（4）在 ecoli、glass、zoo、ionosphere、contraceptive-method-choice 數據集上，本文FPSE算法比SVM算法的正確率表現得更優秀；

（5）參考誤差范圍值，FPSE算法的正確率變化也較為穩定.

4 總結

本文主要提出了一種新的選擇性集成學習算法.其主要的優勢是能夠較為顯著地提升一個學習系統的泛化能力，在部分數據集上的表現大致與Bagging算法和AdaBoost算法相當甚至略優于它們.本文工作的一個特色在于，提出了一種計算分類器的預測準確性和群體差異性的方法，且無需單獨設置部分數據集.使用此方法確實可以進一步提升集成系統的預測性能.

后續還可以繼續展開的工作有：選取更多的數據集來驗證FPSE算法的效能，并在實際應用領域使用FPSE算法來解決分類問題；對FPSE算法中個體分類器評估的做法進行概括與改進，并嵌入其他的一些選擇集成算法，驗證此做法是否具有普適性.