AdaBoost 是一種更進階的「森林」類型的決策樹，和随機森林比起來，它有以下三個特點
- AdaBoost 的每棵樹都隻有一個根節點和兩個葉子節點，實際上叫樹樁（stump）可能會更合适
- AdaBoost 的每個樹樁的權重是不同的，而随機森林中的每棵樹的權重是相同的
- 前一個樹樁的錯誤資料會影響後一個樹樁的生成，意味着後面的樹樁是前面樹樁的補足。這種思想也被稱為 Boosting，除 AdaBoost 外，GBDT 和 XGBoost 也是這樣的思想（很明顯它們中都有 Boost）。
AdaBoost 的生成步驟
假設我們有以下訓練資料，我們想通過「胸口疼痛」、「血管堵塞」和「體重」這三個特征來訓練一個心髒病預測模型：
| 胸口疼痛 | 血管堵塞 | 體重 | 患心髒病 |
|---|---|---|---|
| Yes | 205 | ||
| No | 180 | ||
| 210 | |||
| 167 | |||
| 156 | |||
| 125 | |||
| 168 | |||
| 172 |
首先，我們需要為每個樣本附上一個相同的權重，因為隻有 8 條資料，是以每個樣本的權重均為 1/8，如下
| 樣本權重 | ||||
|---|---|---|---|---|
| 1/8 | ||||
接下來，我們利用基尼不純度在這 3 個特征中找一個最合适的作為樹根，經過計算，當「體重 >176」 時，基尼不純度最小，則第一個樹樁的節點為「體重 >176」，如下圖所示：
産生出一個樹樁後，我們把該樹樁判斷錯誤的樣本拿出來，将它們的權重相加，便得出該樹樁的總誤差，上述樹樁隻有一個錯誤樣本：
則該樹樁的總誤差（Total Error）即這條錯誤樣本的權重——0.125。通過總誤差，我們便可以計算出該樹樁的 Weight：
$$
Weight_{stump} = \frac{1}{2}\log(\frac{1-TotalError}{TotalError})
該公式的曲線如下圖所示，可以看到，誤差的取值範圍在 0 到 1 之間，随着誤差越大，樹樁的 Weight 越小，上例中，我們的誤差為 0.125，所對應的 Weight 為 0.973，也就是圖中藍色點所處的位置：
一棵樹樁産生出來後，接着就要産生第二棵，前面說了，後一棵樹的生成依賴于前一棵樹的誤差，具體的，我們會根據這個誤差來調整每個樣本的權重，這樣，後面的樹就可以根據樣本的新權重來訓練了，更進一步，前一棵樹中錯誤的樣本，我們希望在下一棵樹的訓練中，提高這些樣本的權重，同時降低正确樣本的權重，這樣下一棵樹便會更傾向于把錯誤樣本處理好，起到了對前面樹的補足作用。
整體誤差和樹的 Weight 成負相關關系，Weight 越高代表置信度越高，這時錯誤的樣本相對于 Weight 低的樹來說，樣本權重要調的更高，而正确的樣本的權重要調的更低，錯誤樣本權重和正确樣本權重的調整分别如下面左圖和右圖所示：
對于本例來說，第一個樹樁的 Weight 為 0.973，則錯誤樣本的權重根據左圖公式，将調整為 $0.125 \times 2.646 = 0.33$，同理，正确樣本的權重根據右圖公式，将調整為 $0.125 \times 0.378=0.05$，歸一化後，最終所有樣本的權重調整如下：
| 序号 | 舊樣本權重 | 新樣本權重 | 歸一化後 |
|---|---|---|---|
| 1 | 0.05 | 0.07 | |
| 2 | |||
| 3 | |||
| 4 | 0.33 | 0.49 | |
| 5 | |||
| 6 | |||
| 7 | |||
| 8 |
接下來，我們需要根據新的特征權重來訓練樹樁，其中的一種辦法是根據權重來抽樣，即在每抽一條資料之前，産生一個 0-1 的随機數，根據随機數來決定抽哪條資料。以上面的資料舉例，當随機數落在 [0, 0.07) 範圍内時，則抽出第 1 條樣本，落在 [0.07, 0.14) 範圍内時，則抽出第 2 條樣本，以此類推。
抽樣完成後，我們重新對這些樣本賦予等值的權重，如下：
因為在選樣本時，第 4 條樣本的權重最高，它被抽到的機率就最大，從上表也可以看出，第 4 條樣本重複了 4 次，這樣做的好處是，使用這批資料訓練後，新的樹樁會更傾向于把第 4 條樣本分類正确。推而廣之，在 AdaBoost 中，後面的樹樁會更擅長于處理前面樹樁的錯誤情況。
接下來的步驟和最開始的一樣，重複上面的過程就可以了。
AdaBoost 的預測
在建構完 AdaBoost 後，我們該如何做預測呢？預測過程和随機森林類似，都是用每棵樹的結果來投票，差别在于這裡采用的是權重投票。例如我們有條資料，每棵樹對該資料的預測結果如下：
| 樹序号 | 樹 Weight | 預測結果 |
|---|---|---|
| 0.97 | ||
| 0.34 | ||
| ... | ||
| 100 | 0.46 |
聚合後，把相同預測結果的 Weight 相加，如下
| 樹 Weight 之和 | |
|---|---|
| 43.7 | |
| 20.1 |
取 Weight 較大者，是以該條資料的預測結果為 1.
總結
本文我們一起學習了 AdaBoost 的建構過程，AdaBoost 和随機森林比起來，有 3 個特點：
- 每棵樹隻有一個根節點和兩個葉子節點
- 後一棵樹由前一棵樹的誤差決定
- 每棵樹都有不同的權重，預測時會根據權重來聚合預測結果
此外，文中對樣本權重的手段很有借鑒意義，我們可以把這種方法運用到預測 CTR 等模型的場景中。
參考：
AdaBoost, Clearly Explained