[机器学习] Boosting算法1 --- AdaBoost
?
[機器學習] Boosting算法1 --- AdaBoost
[機器學習] Boosting算法2 --- GBDT
[機器學習] Boosting算法3 --- XGBoost
[機器學習] Boosting算法4 --- LightGBM
目錄
一、提升算法概論
二、AdaBoost算法
弱分類器（單層決策樹）
關于Adaboost的兩種權重
Adaboost數據權重與弱分類器
Adaboost分類器的權重
Adaboost實例解析<1>
圖示說明adaboost的實現過程<2>
一、提升算法概論
Boosting(提升)是一族可將弱學習器提升為強學習器的算法。提升算法基于這樣一種思想：對于一個復雜的任務，將多個專家的判斷總和得出的結果要比任何一個專家單獨的判斷好。這族算法的工作機制類似：先從初始訓練集訓練出一個基學習器，再根據基學習器表現對訓練樣本分布進行調整，是的先前基學習器做錯的樣本在后續收到更多關注（賦予做錯的樣本更大的權值），然后基于調整后的樣本分布來訓練下一個基學習器，一直反復進行，直到達到指定值。boosting方法通過分步迭代（stage-wise）的方式來構建模型，在迭代的每一步構建的弱學習器都是為了彌補已有模型的不足。（個體學習器之間存在強依賴關系。）
對樣本加權的過程如下：
上圖中被放大的點是被加權的樣本，樣本加權后，在下一次的學習中就會收到更多的關注。
也就是說提升算法對分類錯誤的樣本更為關注，通過改變錯誤樣本所占的權值來改變分類邊界，從而一步步提升算法的準確度。
?
二、AdaBoost算法
AdaBoost算法是提升算法中最具代表性的。其中AdaBoost是Adaptive Boosting的縮寫， 正如上面所說的，在AdaBoost算法中會提高前一輪分類器分類錯誤的樣本的權值，而降低那些被分類正確樣本的權值。對于弱分類器的組合，AdaBoost算法采取加權多數表決的方法。具體的說就是加大分類誤差率小的弱分類器的權值，使其在表決中起到較大的作用；減小分類誤差率大的弱分類器的權值，使其在表決中起較小的作用。
主要解決的問題：目前對AdaBoost算法的研究以及應用大多集中于分類問題，同時近年也出現了一些在回歸問題上的應用。就其應用adaBoost系列主要解決了: 兩類問題、多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。
?
1.????為數據集里的每個樣本賦予相同的權重（一般情況），然后開始依據一定的分類標準來對該數據集分類，從而得到第一個Classifier[1]（弱分類器）。同時由此可得此次分類中被分錯的樣本，提高他們的權重，用于下一個Classifier[2]的訓練。
2.????依據上一次Classifier訓練更新樣本權重后的樣本集，來訓練此次Classifier[2]。其中可以依據樣本權重來影響此次訓練的錯誤率來使此次Classifier[2]足夠重視之前錯分的樣本。這樣我們可以得到對于上次分錯的樣本有較好分類能力的Classifier[2]，然后提高本次分類中被分錯的樣本的權重。重復此過程，得到若干的弱分類器Classifier[i]。
3.????為1、2步中得到的Classifier[i]確定在最終的強分類器中的權重（此權重的確定也可以在1、2步中確定）。Strong_Classifier =?∑（?weight[i] *Classifier[i]）（弱分類器的線性組合），計算Strong_Classifier的錯誤率，然后綜合考慮程序迭代次數來判斷是否繼續重復1-3步迭代訓練。
?
對于這個算法需要介紹的是：?
1. 算法開始前，需要將每個樣本的權重初始化為1/m,這樣一開始每個樣本都是等概率的分布，每個分類器都會公正對待。?
2. 開始迭代后，需要計算每個弱分類器的分類錯誤的誤差，誤差等于各個分錯樣本的權重和，這里就體現了樣本權重的作用。如果一個分類器正確分類了一個權重大的樣本，那么這個分類器的誤差就會小，否則就會大。這樣就對分類錯誤的樣本更大的關注。?
3. 獲取最優分類器后，需要計算這個分類器的權重，然后再更新各個樣本的權重，然后再歸一化。?
4. 算法迭代的次數一般不超過弱分類器的個數，如果弱分類器的個數非常之多，那么可以權衡自己性價比來折中選擇。?
5. 迭代完成后，最后的分類器是由迭代過程中選擇的弱分類器線性加權得到的。
弱分類器（單層決策樹）
Adaboost一般使用單層決策樹作為其弱分類器。單層決策樹是決策樹的最簡化版本，只有一個決策點，也就是說，如果訓練數據有多維特征，單層決策樹也只能選擇其中一維特征來做決策，并且還有一個關鍵點，決策的閾值也需要考慮。
關于單層決策樹的決策點，來看幾個例子。比如特征只有一個維度時，可以以小于7的分為一類，標記為+1，大于（等于）7的分為另一類，標記為-1。當然也可以以13作為決策點，決策方向是大于13的分為+1類，小于（等于）13的分為-1類。在單層決策樹中，一共只有一個決策點，所以下圖的兩個決策點不能同時選取。
同樣的道理，當特征有兩個維度時，可以以縱坐標7作為決策點，決策方向是小于7分為+1類，大于（等于）7分類-1類。當然還可以以橫坐標13作為決策點，決策方向是大于13的分為+1類，小于13的分為-1類。在單層決策樹中，一共只有一個決策點，所以下圖的兩個決策點不能同時選取。
擴展到三維、四維、N維都是一樣，在單層決策樹中，一共只有一個決策點，所以只能在其中一個維度中選擇一個合適的決策閾值作為決策點。
關于Adaboost的兩種權重
Adaboost算法中有兩種權重，一種是數據的權重，另一種是弱分類器的權重。其中，數據的權重主要用于弱分類器尋找其分類誤差最小的決策點，找到之后用這個最小誤差計算出該弱分類器的權重（發言權），分類器權重越大說明該弱分類器在最終決策時擁有更大的發言權。
Adaboost數據權重與弱分類器
剛剛已經介紹了單層決策樹的原理，這里有一個問題，如果訓練數據保持不變，那么單層決策樹找到的最佳決策點每一次必然都是一樣的，為什么呢？因為單層決策樹是把所有可能的決策點都找了一遍然后選擇了最好的，如果訓練數據不變，那么每次找到的最好的點當然都是同一個點了。
所以，這里Adaboost數據權重就派上用場了，所謂“數據的權重主要用于弱分類器尋找其分類誤差最小的點”，其實，在單層決策樹計算誤差時，Adaboost要求其乘上權重，即計算帶權重的誤差。
舉個例子，在以前沒有權重時（其實是平局權重時），一共10個點時，對應每個點的權重都是0.1，分錯1個，錯誤率就加0.1；分錯3個，錯誤率就是0.3。現在，每個點的權重不一樣了，還是10個點，權重依次是[0.01,0.01,0.01,0.01,0.01,0.01, 0.01,0.01,0.01,0.91]，如果分錯了第1一個點，那么錯誤率是0.01，如果分錯了第3個點，那么錯誤率是0.01，要是分錯了最后一個點，那么錯誤率就是0.91。這樣，在選擇決策點的時候自然是要盡量把權重大的點（本例中是最后一個點）分對才能降低誤差率。由此可見，權重分布影響著單層決策樹決策點的選擇，權重大的點得到更多的關注，權重小的點得到更少的關注。
在Adaboost算法中，每訓練完一個弱分類器都就會調整權重，上一輪訓練中被誤分類的點的權重會增加，在本輪訓練中，由于權重影響，本輪的弱分類器將更有可能把上一輪的誤分類點分對，如果還是沒有分對，那么分錯的點的權重將繼續增加，下一個弱分類器將更加關注這個點，盡量將其分對。
這樣，達到“你分不對的我來分”，下一個分類器主要關注上一個分類器沒分對的點，每個分類器都各有側重。
Adaboost分類器的權重
由于Adaboost中若干個分類器的關系是第N個分類器更可能分對第N-1個分類器沒分對的數據，而不能保證以前分對的數據也能同時分對。所以在Adaboost中，每個弱分類器都有各自最關注的點，每個弱分類器都只關注整個數據集的中一部分數據，所以它們必然是共同組合在一起才能發揮出作用。所以最終投票表決時，需要根據弱分類器的權重來進行加權投票，權重大小是根據弱分類器的分類錯誤率計算得出的，總的規律就是弱分類器錯誤率越低，其權重就越高。
?
如圖所示為Adaboost分類器的整體結構。從右到左，可見最終的求和與符號函數，再看到左邊求和之前，圖中的虛線表示不同輪次的迭代效果，第1次迭代時，只有第1行的結構，第2次迭代時，包括第1行與第2行的結構，每次迭代增加一行結構，圖下方的“云”表示不斷迭代結構的省略。
第i輪迭代要做這么幾件事：?
1. 新增弱分類器WeakClassifier(i)與弱分類器權重alpha(i)?
2. 通過數據集data與數據權重W(i)訓練弱分類器WeakClassifier(i)，并得出其分類錯誤率，以此計算出其弱分類器權重alpha(i)?
3. 通過加權投票表決的方法，讓所有弱分類器進行加權投票表決的方法得到最終預測輸出，計算最終分類錯誤率，如果最終錯誤率低于設定閾值（比如5%），那么迭代結束；如果最終錯誤率高于設定閾值，那么更新數據權重得到W(i+1)
?
對于boosting算法，存在兩個問題： ?
1. 如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行； ?
2. 如何將訓練得到的各個弱分類器聯合起來形成強分類器。?
針對以上兩個問題，AdaBoost算法進行了調整： ?
1. 使用加權后選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上； ?
2. 將弱分類器聯合起來，使用加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。
?
Adaboost實例解析<1>
例１. Adaboost的一個例子?
下面，給定下列訓練樣本，請用AdaBoost算法學習一個強分類器。?
?
求解過程：?
初始化訓練數據的權值分布，令每個權值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, …, 10，然后分別對于m = 1,2,3, …等值進行迭代。?
拿到這10個數據的訓練樣本后，根據 X 和 Y 的對應關系，要把這10個數據分為兩類，一類是“1”，一類是“-1”，根據數據的特點發現：“0 1 2”這3個數據對應的類是“1”，“3 4 5”這3個數據對應的類是“-1”，“6 7 8”這3個數據對應的類是“1”，9是比較孤獨的，對應類“-1”。拋開孤獨的9不講，“0 1 2”、“3 4 5”、“6 7 8”這是3類不同的數據，分別對應的類是1、-1、1，直觀上推測可知，可以找到對應的數據分界點，比如2.5、5.5、8.5 將那幾類數據分成兩類。當然，這只是主觀臆測，下面實際計算下這個過程。?
迭代過程1?
(1)?對于m=1，在權值分布為D1（10個數據，每個數據的權值皆初始化為0.1）的訓練數據上，經過計算可得：
- 閾值v取2.5時誤差率為0.3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.3），
- 閾值v取5.5時誤差率最低為0.4（x < 5.5時取1，x > 5.5時取-1，則3 4 5 6 7 8皆分錯，誤差率0.6大于0.5，不可取。故令x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.4），
- 閾值v取8.5時誤差率為0.3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.3）。
所以無論閾值v取2.5，還是8.5，總得分錯3個樣本，故可任取其中任意一個如2.5，夠成第一個基本分類器為：?
- 上面說閾值v取2.5時則6 7 8分錯，所以誤差率為0.3，更加詳細的解釋是：因為樣本集中0 1 2對應的類（Y）是1，因它們本身都小于2.5，所以被G1(x)分在了相應的類“1”中，分對了。
- 3 4 5本身對應的類（Y）是-1，因它們本身都大于2.5，所以被G1(x)分在了相應的類“-1”中，分對了。
- 但6 7 8本身對應類（Y）是1，卻因它們本身大于2.5而被G1(x)分在了類”-1”中，所以這3個樣本被分錯了。
- 9本身對應的類（Y）是-1，因它本身大于2.5，所以被G1(x)分在了相應的類“-1”中，分對了。
(2)?從而得到G1(x)在訓練數據集上的誤差率（被G1(x)誤分類樣本“6 7 8”的權值之和）e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。然后根據誤差率e1計算G1的系數：?
這個a1代表G1(x)在最終的分類函數中所占的權重為0.4236。?
(3)?接著更新訓練數據的權值分布，用于下一輪迭代。?
?
值得一提的是，由權值更新的公式可知，每個樣本的新權值是變大還是變小，取決于它是被分錯還是被分正確。即如果某個樣本被分錯了，則yi * Gm(xi)為負，負負等正，結果使得整個式子變大（樣本權值變大），否則變小。?
(４)?第一輪迭代后，最后得到各個數據新的權值分布：?
? ? ? ?D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。?
? ? ? 由此可以看出，因為樣本中是數據“6 7 8”被G1(x)分錯了，所以它們的權值由之前的0.1增大到0.1666，反之，其它數據皆被分正確，所以它們的權值皆由之前的0.1減小到0.0715。?
(5)?分類函數：f1(x)= a1*G1(x) = 0.4236G1(x)。
此時，得到的第一個基本分類器sign(f1(x))在訓練數據集上有3個誤分類點（即6 7 8）。從上述第一輪的整個迭代過程可以看出：被誤分類樣本的權值之和影響誤差率，誤差率影響基本分類器在最終分類器中所占的權重。
?
迭代過程2?
(1)?對于m=2，在權值分布為D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的訓練數據上，經過計算可得：
- 閾值v取2.5時誤差率為0.1666*3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1666*3），
- 閾值v取5.5時誤差率最低為0.0715*4（x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0715*3 + 0.0715），
- 閾值v取8.5時誤差率為0.0715*3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.0715*3）。
所以，閾值v取8.5時誤差率最低，故第二個基本分類器為：?
(2)?面對的還是下述樣本：?
?
很明顯，G2(x)把樣本“3 4 5”分錯了，根據D2可知它們的權值為0.0715, 0.0715, 0.0715，所以G2(x)在訓練數據集上的誤差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。?
計算G2的系數：?
(3)?更新訓練數據的權值分布：?
D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。?
被分錯的樣本“3 4 5”的權值變大，其它被分對的樣本的權值變小。?
(4)?f2(x)=0.4236G1(x) + 0.6496G2(x)?
此時，得到的第二個基本分類器sign(f2(x))在訓練數據集上有3個誤分類點（即3 4 5）
迭代過程3?
(1)?對于m=3，在權值分布為D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的訓練數據上，經過計算可得：
- 閾值v取2.5時誤差率為0.1060*3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1060*3），
- 閾值v取5.5時誤差率最低為0.0455*4（x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0455*3 + 0.0715），
- 閾值v取8.5時誤差率為0.1667*3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.1667*3）。
所以閾值v取5.5時誤差率最低，故第三個基本分類器為：?
(2)?依然還是原樣本：?
?
此時，被誤分類的樣本是：0 1 2 9，這4個樣本所對應的權值皆為0.0455， 所以G3(x)在訓練數據集上的誤差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。?
計算G3的系數：?
(3)?更新訓練數據的權值分布：?
D4 = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)。?
被分錯的樣本“0 1 2 9”的權值變大，其它被分對的樣本的權值變小。?
(4)?f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)?
此時，得到的第三個基本分類器sign(f3(x))在訓練數據集上有0個誤分類點。至此，整個訓練過程結束。?
?
訓練結束?
G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]，?
將上面計算得到的a1、a2、a3各值代入G(x)中，得到最終的分類器為：?
G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]
?
? ? ? ? 毫無疑問這個模型的最大的一個優點是可以自動的組合弱分類器，這在實際應用中的便利之處十分明顯。算法本身簡單，高效，易于編寫而且訓練過程是沒有參數需要調節的。?但是adaboost也是有缺點的，并不是所有問題都能搞定，從wiki上介紹的來看，adaboost對于噪音數據和異常數據是十分敏感的。
?
圖示說明adaboost的實現過程<2>
圖中，“+”和“-”分別表示兩種類別，在這個過程中，我們使用水平或者垂直的直線作為分類器，來進行分類。?
第一步：?
根據分類的正確率，得到一個新的樣本分布D2-，一個子分類器h1。
其中劃圈的樣本表示被分錯的。在右邊的途中，比較大的“+”表示對該樣本做了加權。?
也許你對上面的?1，ɑ1怎么算的也不是很理解。下面我們算一下，算法最開始給了一個均勻分布 D 。所以h1 里的每個點的值是0.1。ok，當劃分后，有三個點劃分錯了，根據算法誤差表達式ε1=Pri～Dt[ht(xi)≠yi]ε1=Pri～Dt[ht(xi)≠yi]，得到誤差為分錯了的三個點的值之和，所以?1=(0.1+0.1+0.1)=0.3，而ɑ1 根據表達式的可以算出來為0.42. 然后就根據算法把分錯的點權值變大。如此迭代，最終完成Adaboost算法。?
第二步：?
根據分類的正確率，得到一個新的樣本分布D3，一個子分類器h2。?
第三步：?
得到一個子分類器h3
整合所有子分類器：
因此可以得到整合的結果，從結果中看，及時簡單的分類器，組合起來也能獲得很好的分類效果，在例子中所有的。
? ? ? ?而a是關于誤差的表達式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯誤點的權值，當下一次分類器再次分錯了這些點之后，會提高整體的錯誤率，這樣就導致 a 變的很小，最終導致這個分類器在整個混合分類器的權值變低。也就是說，這個算法讓優秀的分類器占整體的權值更高，而挫的分類器權值更低。這個就很符合常理了。
?
?
?
參考：
總結
以上是生活随笔為你收集整理的[机器学习] Boosting算法1 --- AdaBoost的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网友用 7 斤铜柱为 i9 被动散热，跑
- 下一篇： Win10自带虚拟机Hpyer-V怎么用