adaboost算法原理

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

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

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

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

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

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

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

8、為兩類，一類是“1”，一類是“-1”，根據(jù)數(shù)據(jù)的特點(diǎn)發(fā)現(xiàn)：“0 1 2”這3個(gè)數(shù)據(jù)對(duì)應(yīng)的類是“1”，“3 4 5”這3個(gè)數(shù)據(jù)對(duì)應(yīng)的類是“-1”，“6 7 8”這3個(gè)數(shù)據(jù)對(duì)應(yīng)的類是“1”，9是比較孤獨(dú)的，對(duì)應(yīng)類“-1”。拋開孤獨(dú)的9不講，“0 1 2”、“3 4 5”、“6 7 8”這是3類不同的數(shù)據(jù)，分別對(duì)應(yīng)的類是1、-1、1，直觀上推測(cè)可知，可以找到對(duì)應(yīng)的數(shù)據(jù)分界點(diǎn)，比如2.5、5.5、8.5 將那幾類數(shù)據(jù)分成兩類。當(dāng)然，這只是主觀臆測(cè)，下面實(shí)際計(jì)算下這個(gè)過程。13Adaboost對(duì)于m=1，在權(quán)值分布為D1（10個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)的權(quán)值皆初始化為0.1）的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：閾值v取2

9、.5時(shí)誤差率為0.3（x 2.5時(shí)取-1，則6 7 8分錯(cuò)，誤差率為0.3），閾值v取5.5時(shí)誤差率最低為0.4（x 5.5時(shí)取-1，則3 4 5 6 7 8皆分錯(cuò)，誤差率0.6大于0.5，不可取。故令x 5.5時(shí)取1，x 5.5時(shí)取-1，則0 1 2 9分錯(cuò)，誤差率為0.4），閾值v取8.5時(shí)誤差率為0.3（x 8.5時(shí)取-1，則3 4 5分錯(cuò)，誤差率為0.3）。所以無論閾值v取2.5，還是8.5，總得分錯(cuò)3個(gè)樣本，故可任取其中任意一個(gè)如2.5，弄成第一個(gè)基本分類器為：從而得到G1(x)在訓(xùn)練數(shù)據(jù)集上的誤差率（被G1(x)誤分類樣本“6 7 8”的權(quán)值之和）e1=P(G1(xi)yi) =

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

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

12、.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：閾值v取2.5時(shí)誤差率為0.1666*3（x 2.5時(shí)取-1，則6 7 8分錯(cuò)，誤差率為0.1666*3），閾值v取5.5時(shí)誤差率最低為0.0715*4（x 5.5時(shí)取1，x 5.5時(shí)取-1，則0 1 2 9分錯(cuò)，誤差率為0.0715*3 + 0.0715），閾值v取8.5時(shí)誤差率為0.0715*3（x 8.5時(shí)取-1，則3 4 5分錯(cuò)，誤差率為0.0715*3）。所以，閾值v取8.5時(shí)誤差率最低，故第二個(gè)基本分類器為：面對(duì)的還是下述樣本：很明

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

14、，得到的第二個(gè)基本分類器sign(f2(x)在訓(xùn)練數(shù)據(jù)集上有3個(gè)誤分類點(diǎn)（即3 4 5）。17Adaboost迭代過程3對(duì)于m=3，在權(quán)值分布為D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：閾值v取2.5時(shí)誤差率為0.1060*3（x 2.5時(shí)取-1，則6 7 8分錯(cuò)，誤差率為0.1060*3），閾值v取5.5時(shí)誤差率最低為0.0455*4（x 5.5時(shí)取1，x 5.5時(shí)取-1，則0 1 2 9分錯(cuò)，誤差率為0.0455*3 + 0.0715

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