Learn R | AdaBoost of Data Mining（一）

01-23

前言

之前在學習隨機森林（Random Forest）的時候提到，隨機森林屬於集成學習的一大分支，該演算法通過生成一棵棵不相關的決策樹將多棵樹（分類器/模型）集成為森林，每一棵樹都各自獨立地學習和作出預測。這些預測匯總得到最後的預測結果，並且所得到的結果優於任何一個單分類器（詳見Learn R | Random Forest of Data Mining（上））。

今天所要學習的是集成學習中的另一大分支——Boosting以及最具代表性的AdaBoost演算法，不過在具體的演算法學習之前，我們有必要對集成學習有著一個基本的了解。

一、集成學習

所謂集成學習（ensemble learning），是指通過構建多個弱學習器，然後結合為一個強學習器來完成分類任務，並相比較於弱學習器而言，進一步提升結果的準確率。嚴格說來，集成學習並不算是一種分類器，而是一種學習器結合的方法。

一個簡單的集成學習示意圖（圖片來源：Ensemble learning（集成學習） - GJS Blog）：

從上圖中我們可以看到集成學習的整個流程：首先先產生一組個體學習器，這些個體學習器可以是「同質」的（例如全部是決策樹），這一類學習器被稱為基學習器（Base learner）；集成中也可以包含不同類型的個體學習器（例如同時包含決策樹與神經網路），這一類學習器則被稱為組件學習器（Component learner）。

接下來，集成學習的作用就是將這多個學習器進行結合，從而獲得比單一學習器更為顯著優越的泛化性能，直觀一點理解，就是我們平時所說的「三個臭皮匠，頂個諸葛亮」。

當然，這種通過集成學習來提高學習器（這裡特指分類器）的整體泛化能力也是有條件的：

分類器之間應該具有差異性。這個很好理解，如果使用的是同一個分類器，那麼集成起來的分類結果是不會有變化的。
每個個體分類器的分類精度必須大於0.5，如果 $p<0.5$ ，那麼隨著集成規模的增加，分類精度會下降；但是如果大於0.5的話，那麼最終分類精度是可以趨於1的。

因此，集成學習的關鍵就在於：如何構建出具有差異性的分類器，並將這些分類器的預測結果進行整合。

當前，我們可以立足於對數據集的處理，即在原有數據集上採用抽樣技術獲得多個訓練數據集來生成多個差異性分類器。這一方法可大致分為以下兩大類：

bagging：通過對原數據集進行有放回的抽取，構建出多個樣本數據集，然後用這些新的數據集訓練多個分類器。因為是有放回的採用，所以一些樣本可能會出現多次，而其他樣本會被忽略。該方法通過降低基分類器方差來改善泛化能力，因此bagging的性能依賴於基分類器的穩定性，如果基分類器是不穩定的，bagging有助於減低訓練數據的隨機擾動導致的誤差，但是如果基分類器是穩定的，即對數據變化不敏感，那麼bagging方法就得不到性能的提升，甚至會減低。該方法的典型代表為隨機森林演算法。
Boosting：提升方法是一個迭代的過程，通過改變樣本分布，使得分類器聚集在那些很難分的樣本上，對那些容易錯分的數據加強學習，增加錯分數據的權重，這樣錯分的數據再下一輪的迭代就有更大的作用（對錯分數據進行懲罰）。該方法的典型代表就是我們接下來要學習到的AdaBoost演算法。

這樣，我們對集成學習有了一個基本的了解和把握，接下來我們將依次學習Adaboost演算法的基本內容及演算法的R實現。

二、AdaBoost演算法初探

前面提到，Boosting一族是將弱學習器提升為強學習器的演算法，而其中最具代表性的就是AdaBoost演算法，該演算法框架如下圖所示（圖片來源：Pattern Recognition and Machine Learning）

具體說來，整個AdaBoost演算法包括以下3個步驟：

初始化訓練樣本的權值分布。如果有 $N$ 個樣本，則每一個訓練樣本最開始時都被賦予相同的權值： $1/N$
訓練弱分類器。具體訓練過程中，如果某個樣本點已經被準確地分類，那麼在構造下一個訓練集中，它的權值就被降低；相反，如果某個樣本點沒有被準確地分類，那麼它的權值就得到提高。然後，權值更新過的樣本集被用於訓練下一個分類器，整個訓練過程如此迭代地進行下去，使得分類器在迭代過程中逐步改進。
將各個訓練得到的弱分類器組合成強分類器。各個弱分類器的訓練過程結束後，加大分類誤差率小的弱分類器的權重，使其在最終的分類函數中起著較大的決定作用；降低分類誤差率大的弱分類器的權重，使其在最終的分類函數中起著較小的決定作用，最後將所有分類器進行加權結合，得到最終分類器。

三、AdaBoost的演算法流程

假設給定一個二分類的訓練數據集為 $T=left{ left( x_{1},y_{1} ight) ,left( x_{2},y_{2} ight) ,...,left( x_{n},y_{n} ight) ight}$ ，其中 $y_{i}$ 屬於二分類的標記組合，即 $y_{i}in left{ +1,-1 ight}$ ，整個演算法流程如下：

步驟一：初始化每個訓練樣例的權值，假設共有 $n$ 個訓練樣例，每一個訓練樣本最開始時都被賦予相同的權值 $1/n$

數學化的語言表示為： $D_{1}=left( w_{11},w_{12},...w_{1n} ight) ,w_{1i}=1/n,i=1,2,...,n$

步驟二：進行多輪迭代，第 $m$ 輪的學習過程如下：

使用權值分布為 $D_{m}$ 的訓練樣例學習得到基分類器 $G_{m}$ （當然，每一輪都是選取讓誤差率最低的閾值來設計基本分類器）
計算上一步得到的基分類器的誤差率 $e_{m}$ ，具體誤差率公式及推導過程如下所示： $e_{m}=P(G_{m}(x_{i}) e y_{i})=frac{sum_{i=1}^{n}{w_{mi}I(G_{m}(x_{i}) e y_{i})} }{sum_{i=1}^{n}{w_{mi}} } =sum_{i=1}^{n}{w_{mi}I(G_{m}(x_{i}) e y_{i})}$ （已知 $sum_{i=1}^{n}{w_{mi}} =1$ ）
計算 $G_m$ 前面的權重係數 $alpha _m$ ，該係數表示 $G_m$ 在最終分類器中的重要程度，目的在於使我們得到基本分類器在最終分類器中所佔的權重，係數計算公式如下： $alpha _m=frac{1}{2}logfrac{1-e_m}{e_m}$ 。由該式可知，當 $e_mleq frac{1}{2}$ 時， $alpha_m geq 0$ ，且 $alpha _m$ 隨著 $e_m$ 的減小而增大，意味著分類誤差率越小的基本分類器在最終分類器中的作用越大，而 $e_mgeq frac{1}{2}$ 則正好相反，這正好驗證了我們前面在集成學習里提到的每個個體分類器的分類精度必須大於0.5的前提條件。
更新訓練樣例的權重係數，用於下一輪迭代：