資料探勘入門筆記——AdaBoost（一脈相承）
寫在前面：健忘星人自學筆記，僅供參考。
另外感謝大神，終於讓我看懂了公式推導，感激涕零~~
AdaBoost 演算法原理及推導
正文：
在上一篇 《隨機森林》的介紹中，我們順帶介紹了整合學習，再次祭出下面這張圖。
而整合學習又和決策樹頗有淵源，
1）Bagging + 決策樹 = 隨機森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
今天我們主要學習的內容，就是“AdaBoost“
1、AdaBoost 與 Boosting
在整合學習的介紹中，我們說過，Boosting 系列演算法是一族可將“弱”學習器
提升
為“強”學習器的演算法。
Boosting 系列演算法中，各個學習器之間是串連的關係
，每一輪的訓練集不變，基於上一輪的學習誤差更新各個訓練樣本的權重。
誤差率高的訓練樣本賦予更高的權重
，這樣誤差率高的點在後面的弱學習器中就會得到更多的重視；然後基於調整後的樣本分佈來訓練下一個基學習器，一直反覆進行，直到達到指定值。
AdaBoost 演算法，是Boosting（提升）演算法中最具代表性的。
下圖是 AdaBoost 演算法的流程示意。
我們注意到 AdaBoost 特殊的兩點：
（1） AdaBoost 不進行取樣，
每一輪訓練都投入全部訓練樣本
（2） AdaBoost 每一輪生成的弱學習器最終
透過“加權表決”的方式融合
除此之外，
（3）AdaBoost
一般採用單層決策樹作為弱學習器。
單層決策樹是一種最簡單的決策樹，僅基於單個特徵來做決策。
理論上任何學習器都可以用於Adaboost。但一般來說，使用最廣泛的Adaboost弱學習器是決策樹和神經網路。對於決策樹，Adaboost分類用了CART分類樹，而Adaboost迴歸用了CART迴歸樹。
在此之上，我們需要理解 AdaBoost 演算法中兩個重要的權重：
2、AdaBoost 的兩個重要權重
2.1 樣本的權重
首先思考，為什麼需要更新樣本權重？
AdaBoost 採用單層決策樹，每一輪訓練又是全部樣本。單層決策樹的原理是在所有決策點中選擇一個最好的，如果樣本權重保持不變，那麼每次找到的最好的點當然都是同一個點了，並達不到“提升“的目的。
接下來思考，如何更新樣本的權重？
假設我們有2個不同的樣本，權重分別為 ［
，
］ ，樣本點的權重沒有區別。哪個樣本判斷錯誤，都扣掉同樣的分數，分類器在訓練時自然也是對這2個樣本也是一視同仁。
經過幾輪訓練，樣本權重更新為 ［
，
］。第一樣本，即使判斷錯誤，也只扣掉0。1分；但是第二個樣本判斷錯誤，就要一下扣掉0。9分（肉疼）。我們自然不希望第二個樣本出現誤判，會給予第二個樣本更多的關注，分類器也是如此。
在 AdaBoost 演算法中，每訓練完一個弱分類器都就會調整權重，
上一輪訓練中被誤分類的點的權重會增加。
在本輪訓練中，由於權重影響，本輪的弱分類器將更有可能把上一輪的誤分類點分對，如果還是沒有分對，那麼分錯的點的權重將繼續增加，下一個弱分類器將更加關注這個點，儘量將其分對。
權重增加的具體公式，我們留後再說。
2.2 分類器權重
AdaBoost 演算法串連起來的各個分類器的關係是，
第N個分類器更關注第N-1個分類器（前一個）誤分的資料
，受權重影響，對這部分誤分資料更有可能分對，而不能保證之前分對的資料也能同時分對。所以在 Adaboost 演算法中，每個弱分類器都有各自最關注的點，每個弱分類器都只關注整個資料集的中一部分資料，所以它們必然是共同組合在一起才能發揮出作用。
由於 AdaBoost 演算法採用的是弱分類器“加權表決”的融合方式 ，給哪個分類器投票權多，哪個分類器投票權少，這個權重大小是根據弱分類器的分類錯誤率計算得出的。
總的規律就是弱分類器錯誤率越低，其權重就越高。
這個很容易理解。
3、計算推導
上面介紹了基本原理，下面我們來看具體計算過程。
3.1 迭代過程
（1） 初始化樣本權重
= 1 / 樣本總數；
（2） 使用具有權重
的樣本集來訓練資料，得到弱學習器
；
（3） 計算弱分類器的分類效果——
錯誤率/誤分率 #FormatImgID_11# ；
注意： 錯誤率計算的是
誤分樣本的權值之和，
不是簡單的誤分樣本個數。；
（4） 根據錯誤率，計算要給
該弱分類器的權重係數
公式，
（5） 更新下一輪訓練器的樣本權重，誤分樣本給予更高的權值，按照公式：
對上述公式進行歸一化處理，
，得到百分比
…………
重複上述過程，直到所有點都被正確劃分，或者迭代達到指定的次數。
3.2 融合過程
經過上面的步驟，我們得到了若干個分類器 {
}
以及各個分類器的權重 {
}
最終得到強分類器：
3.3 公式推導
在上面的迭代步驟中，我們直接給出了分類器權值計算的公式
，刻意忽略了公式的推導和計算過程，下面我們簡單解釋一下。
從模型融合倒著往前看，
模型最終想要實現的，是損失函式的最小化。
損失函式（loss function）是機器學習裡面一個重要概念，用來估量你模型的預測值 f（x） 與真實值Y的不一致程度，它是一個非負實值函式，通常使用
L(Y, f(x))
來表示，損失函式越小，模型的魯棒性就越好。
損失函式有很多種，常見的包括：
0-1損失函式（0-1 loss function）
也就是說，當預測錯誤時，損失函式為1，當預測正確時，損失函式值為0。該損失函式不考慮預測值和真實值的誤差程度。只要錯誤，就是1。
平方損失函式
預測值與實際值差的平方。
而 AdaBoost 演算法的損失函式的形式是
指數損失函式
指數損失函式是分類任務原本0-1損失函式的一致性替代函式。由於這個替代函式是單調連續可微函式，因此用它代替0-1損失函式作為最佳化目標。
而我們得到的最終分類器
代入
，求解出令
最小的
即可。
但這是個複雜的全域性最佳化問題，通常我們使用其簡化版：
假設在第m次迭代中，前m-1次的係數α和基學習器G（x）都是固定的，則
代入
，對
求偏導，即可得到之前看到的公式。
求解的過程省略，請參考以下文章，講解的非常詳細。看懂公式推導需要細心和耐心，同學們不要放棄~~
AdaBoost 演算法原理及推導
補充資料：
AdaBoost原理詳解 - ScorpioLu - 部落格園
4、優缺點
Adaboost 演算法 的主要優點有：
（1）泛化錯誤率低，精度高
（2）基本無引數調整
Adaboost的主要缺點有：
對異常樣本敏感，異常樣本在迭代中可能會獲得較高的權重，影響最終的強學習器的預測準確性
今天的內容就到這裡，
AdaBoost 演算法主要的難點在於理解迭代步驟，以及公式推導~~
下一節預計繼續學習決策樹和他的小夥伴，感謝觀看
