本文不定期更新。原創文章,轉載請附上連結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 xiX, yiY={-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 @[email protected][email protected];
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 @[email protected][email protected];
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(([email protected])/@evalue)),4);
set @eee=round(([email protected])/@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 @[email protected]+1;
end while;
以上是部落客最近用SQL實作的Adaboost算法的部分代碼。資料庫表以後整理一下再貼。Ubuntu不穩定啊,當機兩次了。。編輯的部落格都沒了。。累覺不愛。。
個人疑問
上文中的缺點提到,Adaboost算法的效果依賴于弱分類器的選擇,那麼面對巨大的待分類資料時,如何選擇弱分類呢?有沒有什麼原則。部落客依舊在探索中,找到答案的話會在這裡更新。
推薦資料:由Adaboost算法創始人Freund和Schapire寫的關于Adaboost算法的文檔,我已經上傳。
原創文章,轉載請原創文章,轉載請附上連結http://blog.csdn.net/iemyxie/article/details/40423907 謝謝