本文不定期更新。原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處，謝謝。

Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。Adaboost算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個(gè)樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次得到的分類器最后融合起來，作為最后的決策分類器。

算法概述

1、先通過對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器；
2、將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)的訓(xùn)練樣本，通過對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器；
3、將1和2都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)的訓(xùn)練樣本，通過對(duì)這個(gè)樣本的學(xué)習(xí)得到第三個(gè)弱分類器
4、最終經(jīng)過提升的強(qiáng)分類器。即某個(gè)數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。

與boosting算法比較

1. 使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上； 　　
2. 將弱分類器聯(lián)合起來，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。 ?

與Boosting算法不同的是，AdaBoost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。

算法步驟

1. 給定訓(xùn)練樣本集S，其中X和Y分別對(duì)應(yīng)于正例樣本和負(fù)例樣本；T為訓(xùn)練的最大循環(huán)次數(shù)；
2. 初始化樣本權(quán)重為1/n ，即為訓(xùn)練樣本的初始概率分布； 　　
3. 第一次迭代：(1)訓(xùn)練樣本的概率分布相當(dāng)，訓(xùn)練弱分類器;(2)計(jì)算弱分類器的錯(cuò)誤率;(3)選取合適閾值，使得誤差最小；(4)更新樣本權(quán)重； 　　
經(jīng)T次循環(huán)后，得到T個(gè)弱分類器，按更新的權(quán)重疊加，最終得到的強(qiáng)分類器。?

具體步驟如下：

一.樣本
Given: m examples (x1, y1), …, (xm, ym)
? ? ?where xi?X, yi?Y={-1, +1}
? ? ?xi表示X中第i個(gè)元素，
? ? ?yi表示與xi對(duì)應(yīng)元素的屬性值，+1表示xi屬于某個(gè)分類，
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-1表示xi不屬于某個(gè)分類
二.初始化訓(xùn)練樣本xi的權(quán)重D(i) :i=1,……，m;
? ? (1).若正負(fù)樣本數(shù)目一致，D1(i) = 1/m
? ? (2).若正負(fù)樣本數(shù)目m+, m-則正樣本D1(i) = 1/m+，
負(fù)樣本D1(i) = 1/m-

實(shí)例詳解

圖中“+”和“-”表示兩種類別。我們用水平或者垂直的直線作為分類器進(jìn)行分類。

算法開始前默認(rèn)均勻分布D，共10個(gè)樣本，故每個(gè)樣本權(quán)值為0.1.

第一次分類：

第一次劃分有3個(gè)點(diǎn)劃分錯(cuò)誤，根據(jù)誤差表達(dá)式

?計(jì)算可得e1=（0.1+0.1+0.1）/1.0=0.3

分類器權(quán)重：

然后根據(jù)算法把錯(cuò)分點(diǎn)的權(quán)值變大。對(duì)于正確分類的7個(gè)點(diǎn)，權(quán)值不變，仍為0.1,對(duì)于錯(cuò)分的3個(gè)點(diǎn)，權(quán)值為：

D1=D0*(1-e1)/e1=0.1*(1-0.3)/0.3=0.2333

第二次分類：

如圖所示，有3個(gè)"-"分類錯(cuò)誤。上輪分類后權(quán)值之和為：0.1*7+0.2333*3=1.3990

分類誤差：e2=0.1*3/1.3990=0.2144

分類器權(quán)重a2=0.6493

錯(cuò)分的3個(gè)點(diǎn)權(quán)值為：D2=0.1*（1-0.2144）/0.2144=0.3664

第三次分類：

同上步驟可求得：e3=0.1365 ；a3=0.9223；D3=0.6326

最終的強(qiáng)分類器即為三個(gè)弱分類器的疊加，如下圖所示：

每個(gè)區(qū)域是屬于哪個(gè)屬性，由這個(gè)區(qū)域所在分類器的權(quán)值綜合決定。比如左下角的區(qū)域，屬于藍(lán)色分類區(qū)的權(quán)重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區(qū)域的權(quán)重為h3 中的0.92；屬于淡紅色分類區(qū)的權(quán)重小于屬于藍(lán)色分類區(qū)的權(quán)值，因此左下角屬于藍(lán)色分類區(qū)。因此可以得到整合的結(jié)果如上圖所示，從結(jié)果圖中看，即使是簡(jiǎn)單的分類器，組合起來也能獲得很好的分類效果。

分類器權(quán)值調(diào)整的原因

由公式可以看到，權(quán)值是關(guān)于誤差的表達(dá)式。每次迭代都會(huì)提高錯(cuò)分點(diǎn)的權(quán)值，當(dāng)下一次分類器再次錯(cuò)分這些點(diǎn)之后，會(huì)提高整體的錯(cuò)誤率，這樣就導(dǎo)致分類器權(quán)值變小，進(jìn)而導(dǎo)致這個(gè)分類器在最終的混合分類器中的權(quán)值變小，也就是說，Adaboost算法讓正確率高的分類器占整體的權(quán)值更高，讓正確率低的分類器權(quán)值更低，從而提高最終分類器的正確率。

算法優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

1)Adaboost是一種有很高精度的分類器
2)可以使用各種方法構(gòu)建子分類器,Adaboost算法提供的是框架
3)當(dāng)使用簡(jiǎn)單分類器時(shí)，計(jì)算出的結(jié)果是可以理解的。而且弱分類器構(gòu)造極其簡(jiǎn)單
4)簡(jiǎn)單，不用做特征篩選
5)不用擔(dān)心overfitting(過度擬合)

缺點(diǎn)

1)容易受到噪聲干擾，這也是大部分算法的缺點(diǎn)

2)訓(xùn)練時(shí)間過長(zhǎng)

3)執(zhí)行效果依賴于弱分類器的選擇

SQL實(shí)現(xiàn)

?

#開始迭代 while(@i<=3) do set @evalue=0,@temp=0;set @flag1=0,@flag2=0,@flag3=0,@flag4=0;set @las=concat('d',@i-1);set @cur=concat('d',@i);set @a=concat('select hx,hy into @hx,@hy from hea where id = ',@i); prepare stmt1 from @a;execute stmt1;set @aa=concat('update adaset set ',@cur,' = ',@las); prepare stmt111 from @aa;execute stmt111; #1.分類器為垂直x軸直線if (@hy=0) then #處理分類1set @b=concat('select count(class) into @l_1 from adaset where class="1" and x < ',@hx);prepare stmt2 from @b;execute stmt2;set @c=concat('select count(class) into @l_2 from adaset where class="-1" and x < ',@hx);prepare stmt3 from @c;execute stmt3;if(@l_1=0 and @l_2!=0) thenset @clas=concat('update hea set l=-1 where id = ',@i);prepare stmt28 from @clas;execute stmt28;end if;if(@l_1!=0 and @l_2 =0) thenset @clas=concat('update hea set l=1 where id = ',@i);prepare stmt29 from @clas;execute stmt29;end if;set @weight=concat('d',@i-1);if (@l_1 !=0 and @l_2 !=0 and @l_1>@l_2) then #@l_2是錯(cuò)分點(diǎn)set @d=concat('select sum(',@weight,') into @temp from adaset where class="-1" and x < ',@hx);prepare stmt4 from @d;execute stmt4;set @evalue=@evalue+@temp;set @flag1=1;set @clas=concat('update hea set l=1 where id = ',@i);prepare stmt20 from @clas;execute stmt20;end if;if (@l_1 !=0 and @l_2 !=0 and @l_1<@l_2) then #@l_1是錯(cuò)分點(diǎn)set @d=concat('select sum(',@weight,') into @temp from adaset where class="1" and x < ',@hx);prepare stmt5 from @d;execute stmt5;set @evalue=@evalue+@temp;set @flag2=1;set @clas=concat('update hea set l=-1 where id = ',@i);prepare stmt21 from @clas;execute stmt21;end if; #總權(quán)值&誤差set @h=concat('select sum(',@weight,') into @temp from adaset');prepare stmt10 from @h;execute stmt10;set @evalue = round(@evalue/@temp,4);set @avalue = round((0.5*ln((1-@evalue)/@evalue)),4);set @eee=round((1-@evalue)/@evalue,4); #更新誤差e&假設(shè)權(quán)重aset @j=concat('update hea set e = ',@evalue,' ,a = ',@avalue,' where id = ',@i);prepare stmt11 from @j;execute stmt11; #更新錯(cuò)分樣本的權(quán)重if (@hy=0) thenif (@flag1=1) thenset @k=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class="-1" and x < ',@hx);prepare stmt12 from @k;execute stmt12;end if;if (@flag2=1) thenset @m=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class="1" and x < ',@hx);prepare stmt13 from @m;execute stmt13;end if;if (@flag3=1) thenset @n=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class="-1" and x > ',@hx);prepare stmt14 from @n;execute stmt14;end if;if (@flag4=1) thenset @o=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class="1" and x > ',@hx);prepare stmt15 from @o;execute stmt15;end if;end if; set @i=@i+1; end while;

以上是博主最近用SQL實(shí)現(xiàn)的Adaboost算法的部分代碼。數(shù)據(jù)庫(kù)表以后整理一下再貼。Ubuntu不穩(wěn)定啊，死機(jī)兩次了。。編輯的博客都沒了。。累覺不愛。。

?

個(gè)人疑問

上文中的缺點(diǎn)提到，Adaboost算法的效果依賴于弱分類器的選擇，那么面對(duì)巨大的待分類數(shù)據(jù)時(shí)，如何選擇弱分類呢？有沒有什么原則。博主依舊在探索中，找到答案的話會(huì)在這里更新。

推薦資料：由Adaboost算法創(chuàng)始人Freund和Schapire寫的關(guān)于Adaboost算法的文檔，我已經(jīng)上傳。

?

原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處，謝謝。

原文鏈接:http://blog.csdn.net/iemyxie/article/details/40423907

轉(zhuǎn)載于:https://www.cnblogs.com/realkate1/p/5153400.html

總結(jié)

以上是生活随笔為你收集整理的Adaboost 2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。