# 數據挖掘算法學習（八）Adaboost算法
> 來源：http://blog.csdn.net/iemyxie/article/details/40423907
Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。Adaboost算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最后將每次得到的分類器最后融合起來，作為最后的決策分類器。
**算法概述**
1、先通過對N個訓練樣本的學習得到第一個弱分類器；
2、將分錯的樣本和其他的新數據一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器；
3、將1和2都分錯了的樣本加上其他的新樣本構成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器
4、最終經過提升的強分類器。即某個數據被分為哪一類要由各分類器權值決定。
**與boosting算法比較**
1\. 使用加權后選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上；
2\. 將弱分類器聯合起來，使用加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。 ?
與Boosting算法不同的是，AdaBoost算法不需要預先知道弱學習算法學習正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。
**算法步驟**
1\. 給定訓練樣本集S，其中X和Y分別對應于正例樣本和負例樣本；T為訓練的最大循環次數；
2\. 初始化樣本權重為1/n ，即為訓練樣本的初始概率分布；
3\. 第一次迭代：(1)訓練樣本的概率分布相當，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取合適閾值，使得誤差最小；(4)更新樣本權重；
經T次循環后，得到T個弱分類器，按更新的權重疊加，最終得到的強分類器。?
具體步驟如下：
一.樣本
```
Given: m examples (x1, y1), …, (xm, ym)
where xi?X, yi?Y={-1, +1}
xi表示X中第i個元素，
yi表示與xi對應元素的屬性值，+1表示xi屬于某個分類，
-1表示xi不屬于某個分類
```
二.初始化訓練樣本
```
xi的權重D(i) :i=1,……，m;
(1).若正負樣本數目一致，D1(i) = 1/m
(2).若正負樣本數目m+, m-則正樣本D1(i) = 1/m+，
負樣本D1(i) = 1/m-
```
**實例詳解**
圖中“+”和“-”表示兩種類別。我們用水平或者垂直的直線作為分類器進行分類。
算法開始前默認均勻分布D，共10個樣本，故每個樣本權值為0.1.
第一次分類：
第一次劃分有3個點劃分錯誤，根據誤差表達式
?計算可得`e1=（0.1+0.1+0.1）/1.0=0.3`
分類器權重：
然后根據算法把錯分點的權值變大。對于正確分類的7個點，權值不變，仍為0.1,對于錯分的3個點，權值為：
```
D1=D0*(1-e1)/e1=0.1*(1-0.3)/0.3=0.2333
```
第二次分類：
如圖所示，有3個"-"分類錯誤。上輪分類后權值之和為：0.1*7+0.2333*3=1.3990
分類誤差：`e2=0.1*3/1.3990=0.2144`
分類器權重`a2=0.6493`
錯分的3個點權值為：`D2=0.1*（1-0.2144）/0.2144=0.3664`
第三次分類：
同上步驟可求得：`e3=0.1365` ；`a3=0.9223`；`D3=0.6326`
最終的強分類器即為三個弱分類器的疊加，如下圖所示：
每個區域是屬于哪個屬性，由這個區域所在分類器的權值綜合決定。比如左下角的區域，屬于藍色分類區的權重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區域的權重為h3 中的0.92；屬于淡紅色分類區的權重小于屬于藍色分類區的權值，因此左下角屬于藍色分類區。因此可以得到整合的結果如上圖所示，從結果圖中看，即使是簡單的分類器，組合起來也能獲得很好的分類效果。
**分類器權值調整的原因**
由公式可以看到，權值是關于誤差的表達式。每次迭代都會提高錯分點的權值，當下一次分類器再次錯分這些點之后，會提高整體的錯誤率，這樣就導致分類器權值變小，進而導致這個分類器在最終的混合分類器中的權值變小，也就是說，Adaboost算法讓正確率高的分類器占整體的權值更高，讓正確率低的分類器權值更低，從而提高最終分類器的正確率。
**算法優缺點**
優點
1)Adaboost是一種有很高精度的分類器
2)可以使用各種方法構建子分類器,Adaboost算法提供的是框架
3)當使用簡單分類器時，計算出的結果是可以理解的。而且弱分類器構造極其簡單
4)簡單，不用做特征篩選
5)不用擔心overfitting(過度擬合)
缺點
1)容易受到噪聲干擾，這也是大部分算法的缺點
2)訓練時間過長
3)執行效果依賴于弱分類器的選擇
**SQL實現**
```
#開始迭代
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
#處理分類1
set @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) then
set @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) then
set @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是錯分點
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是錯分點
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;
#總權值&誤差
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&假設權重a
set @j=concat('update hea set e = ',@evalue,' ,a = ',@avalue,' where id = ',@i);
prepare stmt11 from @j;
execute stmt11;
#更新錯分樣本的權重
if (@hy=0) then
if (@flag1=1) then
set @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) then
set @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) then
set @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) then
set @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實現的Adaboost算法的部分代碼。數據庫表以后整理一下再貼。Ubuntu不穩定啊，死機兩次了。。編輯的博客都沒了。。累覺不愛。。
**個人疑問**
上文中的缺點提到，Adaboost算法的效果依賴于弱分類器的選擇，那么面對巨大的待分類數據時，如何選擇弱分類呢？有沒有什么原則。博主依舊在探索中，找到答案的話會在這里更新。
推薦資料：由Adaboost算法創始人Freund和Schapire寫的關于Adaboost算法的文檔，我已經上傳。
