數(shù)據(jù)挖掘Adaboost

1、Adaboost算法周明，熊毅Catalog1234IntroductionAdaboostHow Boosting Algorithms works?ThanksIntroductionPART.1分類器、弱分類器和強(qiáng)分類器提升（boosting）方法過度擬合（overfitting）決策樹樁Concept比如：銀行貸款員需要分析貸款申請(qǐng)者們的各項(xiàng)數(shù)據(jù)，建立分類模型以便搞清楚哪些貸款申請(qǐng)者是“安全的”；銷售經(jīng)理需要分析客戶和產(chǎn)品的數(shù)據(jù)，以便幫助他預(yù)測(cè)如何定向?qū)哂胁煌卣鞯目蛻敉斗裴槍?duì)性的產(chǎn)品廣告；醫(yī)學(xué)研究人員需要分析癌癥數(shù)據(jù)，以便預(yù)測(cè)病人應(yīng)該接受三種具體治療方案中的哪一種。數(shù)據(jù)挖掘中分類的

2、算法有很多，比如KNN算法（王飛，吳小萌），C4.5算法（汪意，楊小濤），樸素貝葉斯算法（何鵬）等，分類是一種重要的數(shù)據(jù)分析形式，它提取出能刻畫數(shù)據(jù)類型的模型，也就是我們常說的分類器。弱分類器：在二分情況下弱分類器的錯(cuò)誤率會(huì)低于50%。其實(shí)任意的分類器都可以做為弱分類器，比如KNN、決策樹、Nave Bayes、logiostic回歸和SVM都可以。這里我們采用的弱分類器是單層決策樹，它是一個(gè)單節(jié)點(diǎn)的決策樹。它是adaboost中最流行的弱分類器，當(dāng)然并非唯一可用的弱分類器。強(qiáng)分類器：識(shí)別準(zhǔn)確率很高并能在多項(xiàng)式時(shí)間內(nèi)完成的學(xué)習(xí)算法提升方法是一種常用的統(tǒng)計(jì)學(xué)習(xí)方法，應(yīng)用廣泛且有效，在分類問題上，

3、它通過改變訓(xùn)練樣本的權(quán)重，學(xué)習(xí)多個(gè)分類器，并將這些分類器進(jìn)行線性組合，提高分類性能。一個(gè)分類器在訓(xùn)練數(shù)據(jù)上能夠獲得比其他分類器更好的擬合，但是在訓(xùn)練數(shù)據(jù)外的數(shù)據(jù)集上卻不能很好的擬合數(shù)據(jù)，這時(shí)就稱為該分類器出現(xiàn)了過擬合（overfitting）。提升算法能夠有效地防止過擬合現(xiàn)象的發(fā)生。Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。AdaboostPART.2 初始化訓(xùn)練數(shù)據(jù)集的權(quán)值分布 迭代： a、選取弱分類器 b、計(jì)算弱分類器的分類誤差率，使得這個(gè)值盡量小 c、計(jì)算分類器的權(quán)重 d、更

4、新訓(xùn)練數(shù)據(jù)集中數(shù)據(jù)的權(quán)值的分布，放大被錯(cuò)誤分類數(shù)據(jù)的權(quán)值，減小正確分類數(shù)據(jù)的權(quán)值 當(dāng)某一輪迭代完后組成的強(qiáng)分類器使得分類誤差率很低的時(shí)候就可以得到最終的強(qiáng)分類器。給定一個(gè)二類分類的訓(xùn)練數(shù)據(jù)集。假設(shè)弱分類器由xv產(chǎn)生。其閥值使得該分類器在訓(xùn)練數(shù)據(jù)集上分類誤差率最低，使用Adaboost學(xué)習(xí)一個(gè)強(qiáng)分類器x0123456789y111-1-1-1111-1x0123456789111-1-1-1-1-1-1-10.10.10.10.10.10.10.10.10.10.1x0123456789111-1-1-1-1-1-1-10.07140.07140.07140.07140.07140.07140.

5、16670.16670.16670.0714x0123456789111-1-1-1-1-1-1-10.42360.42360.4236111-1-1-1-1-1-1-1x0123456789111111111-10.07140.07140.07140.07140.07140.07140.16670.16670.16670.0714x0123456789111-1-1-1-1-1-1-10.04550.04550.04550.16670.16670.16670.10600.10600.10600.0455x0123456789111-1-1-1-1-1-1-1111111111-11.0732

6、1.07321.07320.2260.2260.2260.2260.2260.226111111111-1x0123456789-1-1-1-1-1-111110.04550.04550.04550.16670.16670.16670.10600.10600.10600.0455x0123456789-1-1-1-1-1-111110.1250.1250.1250.1020.1020.1020.0650.0650.0650.125x0123456789111-1-1-1-1-1-1-1111111111-1-1-1-1-1-1-111110.32180.32180.3219-0.5245-0.

7、5245-0.52450.97740.2260.226111-1-1-1111-1How Boosting Algorithms works?PART.3如何通過訓(xùn)練集來(lái)訓(xùn)練不同的弱分類規(guī)則為了找到弱分類規(guī)則，我們應(yīng)用基礎(chǔ)學(xué)習(xí)算法（決策樹樁）。每次應(yīng)用基礎(chǔ)學(xué)習(xí)算法都會(huì)生成一個(gè)新的弱分類規(guī)則。這是一個(gè)迭代過程。多次迭代后，提升算法結(jié)合這些弱分類規(guī)則形成一個(gè)強(qiáng)大的分類預(yù)測(cè)規(guī)則。如何調(diào)整訓(xùn)練集，使得再訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行Step 1:算法對(duì)每個(gè)訓(xùn)練元組賦予相等的權(quán)重Step 2: 使用基礎(chǔ)學(xué)習(xí)算法來(lái)預(yù)測(cè)分類，對(duì)這一次的基礎(chǔ)學(xué)習(xí)算法中預(yù)測(cè)錯(cuò)誤的訓(xùn)練元組提高權(quán)重，并將它們應(yīng)用于下一輪基礎(chǔ)學(xué)習(xí)算

8、法；記錄下本次產(chǎn)生的弱分類規(guī)則。Step 3: 迭代Step 2，結(jié)合所產(chǎn)生的這些弱分類規(guī)則形成一個(gè)強(qiáng)大的分類預(yù)測(cè)規(guī)則如何將訓(xùn)練得到的各個(gè)弱分類器聯(lián)合起來(lái)形成強(qiáng)分類器對(duì)于訓(xùn)練得到的各個(gè)弱分類器計(jì)算它的分類錯(cuò)誤率，錯(cuò)誤率越低，它的預(yù)測(cè)準(zhǔn)確性就越高，因此它的表決權(quán)重就越高。算法輸入l一個(gè)復(fù)合模型。（一個(gè)強(qiáng)分類器）算法輸出AdaBoost-box12022-2-18你可以看到，我們給每個(gè)數(shù)據(jù)點(diǎn)賦予相等的權(quán)重（大小一樣），并應(yīng)用決定樹樁將其歸類為+（加）或 - （減號(hào)）。該決策樹樁算法（D1）在左側(cè)畫一條垂直線將空間分成兩份，從而將數(shù)據(jù)點(diǎn)分成兩類。我們看到，該垂直線已不正確地預(yù)測(cè)的三個(gè)+（加）為- （負(fù)）。在這種情況下，我們會(huì)將這三個(gè)+（加）賦予較高的權(quán)重，并應(yīng)用到下一個(gè)決定樹樁。AdaBoost-box22022-2-18在這里，你可以看到，相對(duì)于數(shù)據(jù)點(diǎn)，三個(gè)被錯(cuò)誤地預(yù)測(cè)+（加）的size變大了。在這種情況下，第二次使用決策樹樁（D2）將嘗試正確預(yù)測(cè)它們?，F(xiàn)在，在該圖右側(cè)的垂直線將3個(gè)誤分類的+（加）分類正確。但同樣，這也造成誤分類誤差。此時(shí)有三個(gè)- （負(fù)）被錯(cuò)誤分類。同樣，我們將指派較高的權(quán)重給三個(gè)- （減號(hào)）并應(yīng)用下一次決定樹樁。AdaBoost-box32022-2-18在這里，三個(gè)- （減）被給予更高的權(quán)重。第三次決定