adaboost算法原理

1、AdaboostAdaboost 算法的原理與推導2目錄目錄123Adaboost算法基礎Adaboost算法原理Adaboost算法示例Adaboost31 Adaboost算法基礎Adaboost 分類是數據挖掘的一種非常重要的方法。分類的概念是在已有數據的基礎上學會一個分類函數或構造出一個分類模型（即：分類器(Classifier)）。該函數或模型能夠把數據庫中的數據紀錄映射到給定類別中的某一個，從而可以應用于數據預測。總之，分類器是數據挖掘中對樣本進行分類的方法的統(tǒng)稱，包含決策樹、邏輯回歸、樸素貝葉斯、神經網絡等算法。1.1 分類器41 Adaboost算法基礎Adaboost 1.2

2、 強分類器、弱分類器 分類器的強弱是其分類能力的一種描述。能夠迅速正確的識別的過程就是強分類器，而易錯的則是弱分類器(基本分類器)。強分類器可以由多個弱分類器組成。51 Adaboost算法基礎Adaboost 1.3 分類器訓練基本分類器1G1(X)弱分類器nGn(x)弱分類器i+1Gi+1(x)弱本分類器iGi(x)弱分類器2G2(X).權重a1權重an權重ai+1權重ai權重a2樣本1樣本2樣本i樣本i+1樣本n.強分類器f(x)=Gi(x)*ai分類器訓練過程62 Adaboost算法原理Adaboost AdaBoost，是英文Adaptive Boosting（自適應增強）的縮寫，

3、由Yoav Freund和Robert Schapire在1995年提出。它的自適應在于：前一個基本分類器分錯的樣本會得到加強，加權后的全體樣本再次被用來訓練下一個基本分類器。針對同一個訓練集訓練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構成一個更強的最終分類器(強分類器)，同時，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率或達到預先指定的最大迭代次數。2.1 Adaboost是什么7Adaboost步驟1、初始化訓練數據的權值分布。如果有N個樣本，則每一個訓練樣本最開始時都被賦予相同的權重：1/N。2、訓練弱分類器。具體訓練過程中，如果某個樣本點已經被準確地分

4、類，那么在構造下一個訓練集中，它的權重就被降低；相反，如果某個樣本點沒有被準確地分類，那么它的權重就得到提高。然后，權重更新過的樣本集被用于訓練下一個分類器，整個訓練過程如此迭代地進行下去。3、將各個訓練得到的弱分類器組合成強分類器。各個弱分類器的訓練過程結束后，加大分類誤差率小的弱分類器的權重，使其在最終的分類函數中起著較大的決定作用，而降低分類誤差率大的弱分類器的權重，使其在最終的分類函數中起著較小的決定作用。換言之，誤差率低的弱分類器在最終分類器中占的權重較大，否則較小。8 給定一個訓練數據集T=(x1,y1), (x2,y2)(xN,yN)，其中實例 ，而實例空間 ，yi屬于標記集合-

5、1,+1，Adaboost的目的就是從訓練數據中學習一系列弱分類器或基本分類器，然后將這些弱分類器組合成一個強分類器。2 Adaboost的原理Adaboost2.2 Adaboost算法流程9Adaboost步驟1初始化訓練數據的權值分布。每一個訓練樣本最開始時都被賦予相同的權重：1/N。10c. 計算Gm(x)的系數，am表示Gm(x)在最終分類器中的重要程度（目的：得到基本分類器在最終分類器中所占的權重）： （這里的log表示ln， 的推導式在統(tǒng)計學習方法第八章）由上述式子可知，em = 0，且am隨著em的減小而增大，意味著分類誤差率越小的基本分類器在最終分類器中的作用越大Adaboo

6、st步驟2進行多輪迭代，用m = 1,2, ., M表示迭代的第多少輪a. 使用具有權值分布Dm的訓練數據集學習，得到基本分類器：由上述式子可知，Gm(x)在訓練數據集上的誤差率em就是被Gm(x)誤分類樣本的權值之和。b. 計算Gm(x)在訓練數據集上的分類誤差率 （這里相當于概率論里面的數學期望：E=Xi*Pi）由上述式子可知，Gm(x)在訓練數據集上的誤差率em就是被Gm(x)誤分類樣本的權值之和。d. 更新訓練數據集的權值分布（目的：得到樣本的新的權值分布），用于下一輪迭代使得被基本分類器Gm(x)誤分類樣本的權值增大，而被正確分類樣本的權值減小。就這樣，通過這樣的方式，AdaBoos

7、t方法能“聚焦于”那些較難分的樣本上。其中，Zm是規(guī)范化因子規(guī)范化因子，使得Dm+1成為一個概率分布： Zm的推導過程在統(tǒng)計學習方法第六章：最大熵模型11Adaboost步驟3 組合各個弱分類器：從而得到最終分類器，如下：123 Adaboost算法示例Adaboost初步分析下面，給定下列訓練樣本，請用AdaBoost算法學習一個強分類器。求解過程：初始化訓練數據的權值分布，令每個權值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ., 10，然后分別對于m = 1,2,3, .等值進行迭代。拿到這10個數據的訓練樣本后，根據 X 和 Y 的對應關系，要把這10個數據分

8、為兩類，一類是“1”，一類是“-1”，根據數據的特點發(fā)現：“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 將那幾類數據分成兩類。當然，這只是主觀臆測，下面實際計算下這個過程。13Adaboost對于m=1，在權值分布為D1（10個數據，每個數據的權值皆初始化為0.1）的訓練數據上，經過計算可得：閾值v取2

9、.5時誤差率為0.3（x 2.5時取-1，則6 7 8分錯，誤差率為0.3），閾值v取5.5時誤差率最低為0.4（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，則3 4 5分錯，誤差率為0.3）。所以無論閾值v取2.5，還是8.5，總得分錯3個樣本，故可任取其中任意一個如2.5，弄成第一個基本分類器為：從而得到G1(x)在訓練數據集上的誤差率（被G1(x)誤分類樣本“6 7 8”的權值之和）e1=P(G1(xi)yi) =

10、3*0.1 = 0.3。然后根據誤差率e1計算G1的系數：這個a1代表G1(x)在最終的分類函數中所占的權重，為0.4236。迭代過程114Adaboost迭代過程1接著更新訓練數據的權值分布，用于下一輪迭代：值得一提的是，由權值更新的公式可知，每個樣本的新權值是變大還是變小，取決于它是被分錯還是被分正確。即如果某個樣本被分錯了，則yi * Gm(xi)為負，負負等正，結果使得整個式子變大（樣本權值變大），否則變小。第一輪迭代后，最后得到各個數據新的權值分布D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666,

11、 0.1666, 0.0715)。由此可以看出，因為樣本中是數據“6 7 8”被G1(x)分錯了，所以它們的權值由之前的0.1增大到0.1666，反之，其它數據皆被分正確，所以它們的權值皆由之前的0.1減小到0.0715。分類函數f1(x)= a1*G1(x) = 0.4236G1(x)。此時，得到的第一個基本分類器sign(f1(x)在訓練數據集上有3個誤分類點（即6 7 8）。從上述第一輪的整個迭代過程可以看出：被誤分類樣本的權值之和影響誤差率，誤差率影響基本分類器在最終分類器中所占的權重。15Adaboost迭代過程2對于m=2，在權值分布為D2 = (0.0715, 0.0715, 0

12、.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，則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，則3 4 5分錯，誤差率為0.0715*3）。所以，閾值v取8.5時誤差率最低，故第二個基本分類器為：面對的還是下述樣本：很明

13、顯，G2(x)把樣本“3 4 5”分錯了，根據D2可知它們的權值為0.0715, 0.0715, 0.0715，所以G2(x)在訓練數據集上的誤差率e2=P(G2(xi)yi) = 0.0715 * 3 = 0.2143。16Adaboost迭代過程2計算G2的系數：更新訓練數據的權值分布：D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分錯的樣本“3 4 5”的權值變大，其它被分對的樣本的權值變小。 f2(x)=0.4236G1(x) + 0.6496G2(x)此時

14、，得到的第二個基本分類器sign(f2(x)在訓練數據集上有3個誤分類點（即3 4 5）。17Adaboost迭代過程3對于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，則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

15、），閾值v取8.5時誤差率為0.1667*3（x 8.5時取-1，則3 4 5分錯，誤差率為0.1667*3）。所以閾值v取5.5時誤差率最低，故第三個基本分類器為（下圖畫反了，待后續(xù)修正）： 依然還是原樣本：此時，被誤分類的樣本是：0 1 2 9，這4個樣本所對應的權值皆為0.0455，所以G3(x)在訓練數據集上的誤差率e3 = P(G3(xi)yi) = 0.0455*4 = 0.1820。5.5, 15.5, 1xG3xx）（18Adaboost迭代過程3計算G3的系數：更新訓練數據的權值分布：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”的權值變大，其它被分對的樣本的權值變小。f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)此時，得到的第三個