Random Forest與Bagging的區(qū)別在于：Bagging每次生成決策樹的時候從全部的屬性Attributes里面選擇，而Random Forest是隨機從全部Attributes的集合里面生成一個大小固定的子集，相對而言需要的計算量更小一些。
Boosting是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確度的方法。它的思想起源于 Valiant提出的 PAC ( Probably Approxi mately Correct)學(xué)習(xí)模型。Valiant和 Kearns提出了弱學(xué)習(xí)和強學(xué)習(xí)的概念 ,識別錯誤率小于1/2,也即準(zhǔn)確率僅比隨機猜測略高的學(xué)習(xí)算法稱為弱學(xué)習(xí)算法;識別準(zhǔn)確率很高并能在多項式時間內(nèi)完成的學(xué)習(xí)算法稱為強學(xué)習(xí)算法。同時 ,Valiant和 Kearns首次提出了 PAC學(xué)習(xí)模型中弱學(xué)習(xí)算法和強學(xué)習(xí)算法的等價性問題,即任意給定僅比隨機猜測略好的弱學(xué)習(xí)算法 ,是否可以將其提升為強學(xué)習(xí)算法 ? 如果二者等價 ,那么只需找到一個比隨機猜測略好的弱學(xué)習(xí)算法就可以將其提升為強學(xué)習(xí)算法 ,而不必尋找很難獲得的強學(xué)習(xí)算法。
Adaboost算法
由于Boosting算法在解決實際問題時有一個重大的缺陷,即他們都要求事先知道弱分類算法分類正確率的下限,這在實際問題中很難做到。后來 Freund 和 Schapire提出了 AdaBoost 算法,該算法的效率與 Freund 方法的效率幾乎一樣,卻可以非常容易地應(yīng)用到實際問題中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整個訓(xùn)練集上維護一個分布權(quán)值向量 D( x) t ,用賦予權(quán)重的訓(xùn)練集通過弱分類算法產(chǎn)生分類假設(shè) Ht ( x) ,即基分類器,然后計算他的錯誤率,用得到的錯誤率去更新分布權(quán)值向量 D( x) t ,對錯誤分類的樣本分配更大的權(quán)值,正確分類的樣本賦予更小的權(quán)值。每次更新后用相同的弱分類算法產(chǎn)生新的分類假設(shè),這些分類假設(shè)的序列構(gòu)成多分類器。對這些多分類器用加權(quán)的方法進行聯(lián)合,最后得到?jīng)Q策結(jié)果。這種方法不要求產(chǎn)生的單個分類器有高的識別率,即不要求尋找識別率很高的基分類算法,只要產(chǎn)生的基分類器的識別率大于 015 ,就可作為該多分類器序列中的一員。
尋找多個識別率不是很高的弱分類算法比尋找一個識別率很高的強分類算法要容易得多,AdaBoost 算法的任務(wù)就是完成將容易找到的識別率不高的弱分類算法提升為識別率很高的強分類算法,這也是 AdaBoost 算法的核心指導(dǎo)思想所在,如果算法完成了這個任務(wù),那么在分類時,只要找到一個比隨機猜測略好的弱分類算法,就可以將其提升為強分類算法,而不必直接去找通常情況下很難獲得的強分類算法。通過產(chǎn)生多分類器最后聯(lián)合的方法提升弱分類算法,讓他變?yōu)閺姷姆诸愃惴?也就是給定一個弱的學(xué)習(xí)算法和訓(xùn)練集,在訓(xùn)練集的不同子集上,多次調(diào)用弱學(xué)習(xí)算法,最終按加權(quán)方式聯(lián)合多次弱學(xué)習(xí)算法的預(yù)測結(jié)果得到最終學(xué)習(xí)結(jié)果。包含以下2 點:
AdaBoost 通過對樣本集的操作來訓(xùn)練產(chǎn)生不同的分類器,他是通過更新分布權(quán)值向量來改變樣本權(quán)重的,也就是提高分錯樣本的權(quán)重,重點對分錯樣本進行訓(xùn)練。
(1) 沒有先驗知識的情況下,初始的分布應(yīng)為等概分布,也就是訓(xùn)練集如果有 n個樣本,每個樣本的分布概率為1/ n。(2) 每次循環(huán)后提高錯誤樣本的分布概率,分錯的樣本在訓(xùn)練集中所占權(quán)重增大,使得下一次循環(huán)的基分類器能夠集中力量對這些錯誤樣本進行判斷。
最后的強分類器是通過多個基分類器聯(lián)合得到的,因此在最后聯(lián)合時各個基分類器所起的作用對聯(lián)合結(jié)果有很大的影響,因為不同基分類器的識別率不同,他的作用就應(yīng)該不同,這里通過權(quán)值體現(xiàn)他的作用,因此識別率越高的基分類器權(quán)重越高,識別率越低的基分類器權(quán)重越低。權(quán)值計算如下:基分類器的錯誤率:e = ∑( ht ( x i) ≠yi) Di (1)基分類器的權(quán)重:W t = F( e) ,由基分類器的錯誤率計算他的權(quán)重。2.3 算法流程及偽碼描述算法流程描述算法流程可用結(jié)構(gòu)圖 1 描述,如圖 1 所示 AdaBoost重復(fù)調(diào)用弱學(xué)習(xí)算法(多輪調(diào)用產(chǎn)生多個分類器) ,首輪調(diào)用弱學(xué)習(xí)算法時,按均勻分布從樣本集中選取子集作為該次訓(xùn)練集,以后每輪對前一輪訓(xùn)練失敗的樣本,賦予較大的分布權(quán)值( Di 為第i 輪各個樣本在樣本集中參與訓(xùn)練的概率) ,使其在這一輪訓(xùn)練出現(xiàn)的概率增加,即在后面的訓(xùn)練學(xué)習(xí)中集中對比較難訓(xùn)練的樣本進行學(xué)習(xí),從而得到 T個弱的基分類器, h1 , h2 , …, ht ,其中 ht 有相應(yīng)的權(quán)值 w t ,并且其權(quán)值大小根據(jù)該分類器的效果而定。最后的分類器由生成的多個分類器加權(quán)聯(lián)合產(chǎn)生。
