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

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

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

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

4、新訓(xùn)練數(shù)據(jù)集中數(shù)據(jù)的權(quán)值的分布，放大被錯誤分類數(shù)據(jù)的權(quán)值，減小正確分類數(shù)據(jù)的權(quán)值 當(dāng)某一輪迭代完后組成的強(qiáng)分類器使得分類誤差率很低的時候就可以得到最終的強(qiáng)分類器。給定一個二類分類的訓(xùn)練數(shù)據(jù)集。假設(shè)弱分類器由xv產(chǎn)生。其閥值使得該分類器在訓(xùn)練數(shù)據(jù)集上分類誤差率最低，使用Adaboost學(xué)習(xí)一個強(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)練集來訓(xùn)練不同的弱分類規(guī)則為了找到弱分類規(guī)則，我們應(yīng)用基礎(chǔ)學(xué)習(xí)算法（決策樹樁）。每次應(yīng)用基礎(chǔ)學(xué)習(xí)算法都會生成一個新的弱分類規(guī)則。這是一個迭代過程。多次迭代后，提升算法結(jié)合這些弱分類規(guī)則形成一個強(qiáng)大的分類預(yù)測規(guī)則。如何調(diào)整訓(xùn)練集，使得再訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行Step 1:算法對每個訓(xùn)練元組賦予相等的權(quán)重Step 2: 使用基礎(chǔ)學(xué)習(xí)算法來預(yù)測分類，對這一次的基礎(chǔ)學(xué)習(xí)算法中預(yù)測錯誤的訓(xùn)練元組提高權(quán)重，并將它們應(yīng)用于下一輪基礎(chǔ)學(xué)習(xí)算

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