機器學習_學習筆記系列(40)：自適應增強決策樹分類(Adaptive Boosted Decision Tree Classifier)
前四篇我們介紹了兩種使用Decision Tree作為Base Leaner並結合Parallel Ensemble Learning的機器學習演算法，一個為Random Forest，另一個為Extra Tree，我們可以看到這兩個演算法，他們訓練模型的方式，都是現把資料產生成T組，然後以Decision Tree演算法，訓練出個T個模型後，再將它們結合成一格Strong Leaner。
而今天我們就要來介紹運用Adaptive Boosted結合Decision Tree的演算法，AdaBoost Decision Tree (ABDT)。
AdaBoost Decision Tree
其實對於AdaBoost Decision Tree在解決分類上的問題，其實和AdaBoost演算法本身非常的像。所以在這裡我們先回顧一下AdaBoost。
首先我們設有一組資料其中輸入資料為x，輸出資料為y，然後我們的輸入資料總共有N筆，每筆資料總共有M個特徵，而在這裡我們會引入一個權重D，而這裡的D所代表的就是每筆資料的重要性，所以D總共有N個數值。
接下來我們會把我們的輸入資料x、輸出資料y={1,-1}，和權重D，一起帶入訊出一個Base Learner。而其最佳化方程式為
其中這裡的h就是我們想要求的base learner方程式。而我們看到與一般訓練分類器的不同之處就是，前面乘上了一個權重D。接下來求出h後，我們就會計算此方程式的錯誤率：
然後再根據這個錯誤率計算Base Learner加權數α：
最後我們就用α更新我們的權重D：
而這裡我們可以看到一件有趣的事，那就是如果今天資料分類正確，y乘上h就會是+1的，所以說更新後的權重D會變小，反之分類錯誤y乘上h就會是-1，所以更新後的權重D會變大。也就是說分類錯誤的資料會再下一回被Highlight起來。
接下來我們一樣以更新後的加權數D，連同x和y一起帶入來訓練新的分類器，接著我們再用相同的步驟，計算錯誤率、算出α，再更新D，以此類推。而在這邊要注意的就是，當我們算出來的加權數α，如果超過0.5的話，那就表示我們分類器的錯誤率超過一半以上，所以我們的迴圈會在這裡停止。
所以最後經過T次迴圈後，我們總共會得到T組分類器，然後我們最後再用以下方程式
將所有model結合起來，得到我們最終的分類器。
而對於AdaBoost和AdaBoost Decision Tree的唯一差別就是，我們把D、x、y拿去訓練的時候，前者是以Decision Stump，後者是以Decision Tree。
AdaBoost Decision Tree Classifier
在這裡我們來看一下ADBT在解決平面二元分類的應用。
從這張圖我們可以看到，在執行演算法的時候，我們會發現如果上一次那個區域分類錯誤，下一個迴圈的時候，ABDT會想辦法把分類錯誤的地方修正，但是我們也能看到修正的同時，又會忽略到原本已經分類好的區域。而總體ABDT的效能如下：
我們可以看最後整體在訓練和測試集的表現ABDT都比Decision Tree來得好，這也是達到我們Ensemble Learning的目標。
Python Sample Code:
Github:
Reference:
[1] Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1), 119–139.
