AdaBoost 是一種更高級(jí)的「森林」類型的決策樹，和隨機(jī)森林比起來，它有以下三個(gè)特點(diǎn)
- AdaBoost 的每棵樹都只有一個(gè)根節(jié)點(diǎn)和兩個(gè)葉子節(jié)點(diǎn)，實(shí)際上叫樹樁（stump）可能會(huì)更合適
- AdaBoost 的每個(gè)樹樁的權(quán)重是不同的，而隨機(jī)森林中的每棵樹的權(quán)重是相同的
- 前一個(gè)樹樁的錯(cuò)誤數(shù)據(jù)會(huì)影響后一個(gè)樹樁的生成，意味著后面的樹樁是前面樹樁的補(bǔ)足。這種思想也被稱為 Boost，除 AdaBoost 外，GBDT 和 XGBoost 也是這樣的思想（很明顯它們中都有 Boost）。
AdaBoost 的生成步驟
假設(shè)我們有以下訓(xùn)練數(shù)據(jù)，我們想通過「胸口疼痛」、「血管堵塞」和「體重」這三個(gè)特征來訓(xùn)練一個(gè)心臟病預(yù)測(cè)模型：
| 胸口疼痛 | 血管堵塞 | 體重 | 患心臟病 |
|---|---|---|---|
| Yes | Yes | 205 | Yes |
| No | Yes | 180 | Yes |
| Yes | No | 210 | Yes |
| Yes | Yes | 167 | Yes |
| No | Yes | 156 | No |
| No | Yes | 125 | No |
| Yes | No | 168 | No |
| Yes | Yes | 172 | No |
首先，我們需要為每個(gè)樣本附上一個(gè)相同的權(quán)重，因?yàn)橹挥?8 條數(shù)據(jù)，所以每個(gè)樣本的權(quán)重均為 1/8，如下
| 胸口疼痛 | 血管堵塞 | 體重 | 患心臟病 | 樣本權(quán)重 |
|---|---|---|---|---|
| Yes | Yes | 205 | Yes | 1/8 |
| No | Yes | 180 | Yes | 1/8 |
| Yes | No | 210 | Yes | 1/8 |
| Yes | Yes | 167 | Yes | 1/8 |
| No | Yes | 156 | No | 1/8 |
| No | Yes | 125 | No | 1/8 |
| Yes | No | 168 | No | 1/8 |
| Yes | Yes | 172 | No | 1/8 |
接下來，我們利用基尼不純度在這 3 個(gè)特征中找一個(gè)最合適的作為樹根，經(jīng)過計(jì)算，當(dāng)「體重 >176」 時(shí)，基尼不純度最小，則第一個(gè)樹樁的節(jié)點(diǎn)為「體重 >176」，如下圖所示：
產(chǎn)生出一個(gè)樹樁后，我們把該樹樁判斷錯(cuò)誤的樣本拿出來，將它們的權(quán)重相加，便得出該樹樁的總誤差，上述樹樁只有一個(gè)錯(cuò)誤樣本：
| 胸口疼痛 | 血管堵塞 | 體重 | 患心臟病 | 樣本權(quán)重 |
|---|---|---|---|---|
| Yes | Yes | 167 | Yes | 1/8 |
則該樹樁的總誤差（Total Error）即這條錯(cuò)誤樣本的權(quán)重——0.125。通過總誤差，我們便可以計(jì)算出該樹樁的 Weight：
該公式的曲線如下圖所示，可以看到，誤差的取值范圍在 0 到 1 之間，隨著誤差越大，樹樁的 Weight 越小，上例中，我們的誤差為 0.125，所對(duì)應(yīng)的 Weight 為 0.973，也就是圖中藍(lán)色點(diǎn)所處的位置：
一棵樹樁產(chǎn)生出來后，接著就要產(chǎn)生第二棵，前面說了，后一棵樹的生成依賴于前一棵樹的誤差，具體的，我們會(huì)根據(jù)這個(gè)誤差來調(diào)整每個(gè)樣本的權(quán)重，這樣，后面的樹就可以根據(jù)樣本的新權(quán)重來訓(xùn)練了，更進(jìn)一步，前一棵樹中錯(cuò)誤的樣本，我們希望在下一棵樹的訓(xùn)練中，提高這些樣本的權(quán)重，同時(shí)降低正確樣本的權(quán)重，這樣下一棵樹便會(huì)更傾向于把這類樣本處理好，起到了對(duì)前面樹的補(bǔ)足作用。
整體誤差和樹的 Weight 成負(fù)相關(guān)關(guān)系，Weight 越高代表置信度越高，這時(shí)錯(cuò)誤的樣本相對(duì)于 Weight 低的樹來說，樣本權(quán)重要調(diào)的更高，而正確的樣本的權(quán)重要調(diào)的更低，錯(cuò)誤樣本權(quán)重和正確樣本權(quán)重的調(diào)整分別如下面左圖和右圖所示：
對(duì)于本例來說，第一個(gè)樹樁的 Weight 為 0.973，則錯(cuò)誤樣本的權(quán)重根據(jù)左圖公式，將調(diào)整為 ，同理，正確樣本的權(quán)重根據(jù)右圖公式，將調(diào)整為
，歸一化后，最終所有樣本的權(quán)重調(diào)整如下：
| 序號(hào) | 舊樣本權(quán)重 | 新樣本權(quán)重 | 歸一化后 |
|---|---|---|---|
| 1 | 1/8 | 0.05 | 0.07 |
| 2 | 1/8 | 0.05 | 0.07 |
| 3 | 1/8 | 0.05 | 0.07 |
| 4 | 1/8 | 0.33 | 0.49 |
| 5 | 1/8 | 0.05 | 0.07 |
| 6 | 1/8 | 0.05 | 0.07 |
| 7 | 1/8 | 0.05 | 0.07 |
| 8 | 1/8 | 0.05 | 0.07 |
接下來，我們需要根據(jù)新的特征權(quán)重來訓(xùn)練樹樁，其中的一種辦法是根據(jù)權(quán)重來抽樣，即在每抽一條數(shù)據(jù)之前，產(chǎn)生一個(gè) 0-1 的隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)來決定抽哪條數(shù)據(jù)。以上面的數(shù)據(jù)舉例，當(dāng)隨機(jī)數(shù)落在 [0, 0.07) 范圍內(nèi)時(shí)，則抽出第 1 條樣本，落在 [0.07, 0.14) 范圍內(nèi)時(shí)，則抽出第 2 條樣本，以此類推。
抽樣完成后，我們重新對(duì)這些樣本賦予等值的權(quán)重，如下：
| 胸口疼痛 | 血管堵塞 | 體重 | 患心臟病 | 樣本權(quán)重 |
|---|---|---|---|---|
| No | Yes | 156 | No | 1/8 |
| Yes | Yes | 167 | Yes | 1/8 |
| No | Yes | 125 | No | 1/8 |
| Yes | Yes | 167 | Yes | 1/8 |
| Yes | Yes | 167 | Yes | 1/8 |
| Yes | Yes | 172 | No | 1/8 |
| Yes | Yes | 205 | Yes | 1/8 |
| Yes | Yes | 167 | Yes | 1/8 |
可見第 4 條樣本被重復(fù)抽出來了多次（它的樣本權(quán)重最高），使用這批數(shù)據(jù)訓(xùn)練后，新的樹樁會(huì)更傾向于把這條樣本分類正確，因?yàn)樵谟?xùn)練時(shí)，重復(fù)的樣本會(huì)受到更大的懲罰。
接下來的步驟和最開始的一樣，重復(fù)上面的過程就可以了。
AdaBoost 的預(yù)測(cè)
在構(gòu)建完 AdaBoost 后，我們?cè)撊绾巫鲱A(yù)測(cè)呢？預(yù)測(cè)過程和隨機(jī)森林類似，都是用每棵樹的結(jié)果來投票，差別在于這里采用的是加權(quán)投票。例如我們有條數(shù)據(jù)，每棵樹對(duì)該數(shù)據(jù)的預(yù)測(cè)結(jié)果如下：
| 樹序號(hào) | 樹 Weight | 預(yù)測(cè)結(jié)果 |
|---|---|---|
| 1 | 0.97 | 1 |
| 2 | 0.34 | 0 |
| ... | ... | ... |
| 100 | 0.46 | 1 |
聚合后，把相同預(yù)測(cè)結(jié)果的 Weight 相加，如下
| 預(yù)測(cè)結(jié)果 | 樹 Weight 之和 |
|---|---|
| 1 | 43.7 |
| 0 | 20.1 |
取 Weight 較大者，所以該條數(shù)據(jù)的預(yù)測(cè)結(jié)果為 1.
總結(jié)
本文我們一起學(xué)習(xí)了 AdaBoost 的構(gòu)建過程，AdaBoost 和隨機(jī)森林比起來，有 3 個(gè)特點(diǎn)：
- 每棵樹只有一個(gè)根節(jié)點(diǎn)和兩個(gè)葉子節(jié)點(diǎn)
- 后一棵樹由前一棵樹的誤差決定
- 每棵樹都有不同的權(quán)重，預(yù)測(cè)時(shí)會(huì)根據(jù)權(quán)重來聚合預(yù)測(cè)結(jié)果
參考：AdaBoost, Clearly Explained
相關(guān)文章：
