AdaBoost算法分析及簡單應(yīng)用

1、動於林令孑科祙大凈guilin university of electronic technology機器學(xué)習(xí)課程結(jié)課論文學(xué)號、專業(yè)：姓名： yan氺氺論文題0 : adaboost算法分析及簡舉應(yīng)用指導(dǎo)教師：楊氺*所屬學(xué)院： 電子工程與自動化學(xué)院成績評定教師簽名桂林電子科技大學(xué)研究生院年 月 日adaboost算法分析及簡單應(yīng)用yan*（桂林電子科技大學(xué)電子工程與自動化學(xué)院廣西桂林541004）摘要：本文主要闡述了在數(shù)據(jù)挖掘領(lǐng)域屮十個主要的分類算法之一一一adaboost的來源、發(fā)展，以及開 發(fā)應(yīng)用，然后介紹丫在該算法的訓(xùn)練過程中一個簡單的應(yīng)用，最后對該算法進行丫簡單評價。關(guān)鍵詞:adabo

2、ost算法；發(fā)展背貴；訓(xùn)練過程；性能改進；分類算法analysis of the algorithm and its simple applicationyanschool of electronic engineering and automation of guilin university of electronic technology, guilin 541004, chinaabstract: this paper mainly describes one of the ten main classification algorithm in dateaminingadaboost

3、. firstly, it introduces the origin，development and application，thenintroduces the main training process of the algorithm，simple application and finally discusses the algorithm simply.keywords: adaboost algorithm; development background; training process; performance improvement; classification algo

4、rithm1引言在 1990 年，schapire 提出了 boosting 算法，次年 freund 改進 boosting 算法，這兩種算法存在共同的實踐上的缺陷，那就是都要求事先知道弱學(xué)習(xí)算法 學(xué)習(xí)正確率的下限。1995年，freund和schapire共同改進了 boosting算法， 提出了 adaboost （ adaptive boosting）算法，該算法效率和 freund 于 1991 年 提出的boosting算法幾乎相同，但不需要任何關(guān)于弱學(xué)習(xí)器的先驗知識，因而 更容易應(yīng)用到實際問題當(dāng)中。adaboost即adaptive boosting,它通過自is應(yīng)學(xué)習(xí)算法來降低

5、誤差率，多 次迭代后達(dá)到預(yù)期的效果。在另一方面，它并不需要知道樣本空間的精確分布， 每個樣品經(jīng)過弱學(xué)習(xí)調(diào)節(jié)后，通過權(quán)重的高低更新空間分布。該算法可以很容易 地應(yīng)用到實際問題，因此，己成為最流行的boosting算法。在機器學(xué)習(xí)的算法中，adaboost算法是一種比較重要且通用的用于特征分類 的算法，在圖像檢索和人臉表情識別等問題中都有普遍應(yīng)用。從現(xiàn)狀看，人們對 adaboost算法的研究及應(yīng)用主要集中用于分類問題上，另外在某些冋歸問題上 也有所涉及，比如兩類問題、多類單標(biāo)簽問題、多類多標(biāo)簽問題和回歸問題。該 學(xué)習(xí)算法可以提高其他算法的性能，其思想來自于1984年valiant提出的 pac （

6、probably approximately correct）（可能近似正確）學(xué)習(xí)模型，在這個pac 模型中，提出了兩個概念-弱學(xué)習(xí)算法和強學(xué)習(xí)算法。其概念是:如果一個學(xué)習(xí)算 法通過學(xué)4一組樣本，識別率很高，則稱其為強學(xué)習(xí)算法;如果識別正確率只冇 50%左右，僅略高于隨機猜測，則稱其為弱學(xué)習(xí)算法。強分類器是指一種算法通 過一些訓(xùn)練集的學(xué)習(xí)，來達(dá)到所需的正確識別率。如果一個學(xué)習(xí)算法的識別率僅 好于隨機的猜測，則稱其為弱分類器。通常，針對一個具體的識別問題，我們很 難找到一個理想的強分類器，但是弱分類器一般都會有很多，基于這種現(xiàn)象， adaboost算法被提出，它指出：通過一定的算法可以將一組弱分

7、類器提升為一 個強分類器。adaboost在機器學(xué)習(xí)領(lǐng)域中十分重要，它是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確 度的方法。也就是說，adaboost算法為其他算法提供了一種框架結(jié)構(gòu)，而其他 算法只在其中作為子分類器，因此adaboost算法可以運用在許多方面的實踐上。 如今通過adaboost算法，我們實現(xiàn)了手寫體字符識別，運用到了許多輸入設(shè)備 上，如流行的觸屏手機上的手寫輸入、筆記本電腦的手寫輸入、掃描儀掃面文字 轉(zhuǎn)化為電子文檔。我們實現(xiàn)了閣像識別，如人臉識別、google上的閣片檢索功 能（很方便地找到我想要的清晰度更高的圖片）。我們實現(xiàn)了語音識別，現(xiàn)在的 win7上都有了一個語音識別的功能，我們能

8、夠讓計算機知道我們說了什么話， 并通過機器自動學(xué)習(xí)提高語咅識別的精度，聲音輸入和聲控很可能在未來普及。 當(dāng)然adaboost算法還能做文本分類和醫(yī)療診斷等等。2算法描述adaboost的是一種迭代算法，其主要思想是針對相同的訓(xùn)練集用不同的分類 器（弱分類器）去學(xué)習(xí)，然后把這些弱分類器結(jié)合起來，以形成更強的最終分類 器（強分類器）。算法本身是通過改變數(shù)據(jù)分布，根據(jù)每個訓(xùn)練的樣本的分類是 否正確，以及整體分類的精度來確定每個樣本的權(quán)重來實現(xiàn)的。每次都是將樣本 加權(quán)后得到一組新的數(shù)據(jù)并將其分給下一層的分類器進行訓(xùn)練，直至達(dá)到一定的 正確率，然后將這些分類器融合在一起形成一個最終分類器，作為一個最后的

9、決 定分類。八daboost算法的基本步驟是：首先，給出一個弱學(xué)算法和訓(xùn)練集（xi, y1）,(x2, y2), (xm, ym),其中，xmex, x代表分類問題或類域?qū)嵗臻g，ymey = + 1, - 1。初始化時，adaboost算法將訓(xùn)練集指定分配1/m，即每 個訓(xùn)練樣木的權(quán)重都是1/m。然后，用弱學(xué)習(xí)算法進行t次迭代，每次迭代都根 據(jù)訓(xùn)練結(jié)果來更新訓(xùn)練集的分布情況，并為訓(xùn)練失敗的訓(xùn)練實例給予更人的權(quán) 重，這樣的訓(xùn)練實例將在下一次迭代得到更多的關(guān)注。這樣經(jīng)t次循環(huán)后將會得 到t個弱分類器，最終按更新的權(quán)重疊加到一起得到強分類器，這個最終的強分 類器是這些弱分類器的加權(quán)平均。雖然單個弱

10、學(xué)習(xí)器的準(zhǔn)確率不高，但采用 adaboost算法后，將會使得結(jié)果更為準(zhǔn)確。adaboost算法與boosting算法不同， 它不需要預(yù)先知道弱分類器分錯的概率，并ii最后它是通過所冇弱分類器的分類 精度來得到這個強分類器的分類精度，這樣可以提高分類能力。簡單地說，adaboost算法的訓(xùn)練是通過調(diào)整每個樣品相應(yīng)的權(quán)重來實現(xiàn)的。 首先,將各樣品的權(quán)重比設(shè)成一樣，其中m是一個弱學(xué)習(xí)的樣本分布的訓(xùn)練次數(shù)。 對于錯誤分類的樣木，增加相應(yīng)的權(quán)重，而對于正確分類的樣木，降低其權(quán)重， 這樣錯的樣本就受到重視以便下次“對癥下藥”。在新的樣本分布中，又一次進 行弱學(xué)習(xí)算法地訓(xùn)練。這樣經(jīng)t周期的循環(huán)得到t個弱分類

11、器，再把這些弱分類 器加權(quán)起來，最終得到一個合適的的強分類器。下面我們舉一個簡單的例子來看看adaboost的實現(xiàn)過程：+ + 一 + + 圖中，“+”和分別表示兩種類別，在這個過程中，我們使用水平或者 垂直的直線作為分類器，來進行分類。-+-+c , * "亀丨 一+ 一根據(jù)分類的正確率，得到一個新的樣本分布d2, 個子分類器hl。其中劃圈的樣木表示被分錯的。在右邊的圖中，比較大的“ + ”表示對該樣本做 了加權(quán)o算法最開始給了一個均勻分布d。所以hl里的每個點的值是0. 1。當(dāng)劃分后,有三個點劃分錯了，根據(jù)算法誤差表達(dá)式得到誤差為分錯了 的三個點的值之和，所以u=(0. 1+0.

12、 1+0. 1)=0.3,而al根據(jù)表達(dá)式可以算出來為證然后就棚算法把分錯的點權(quán)值變大。如此 迭代，最終完成adaboost算法。+ 一+ +根據(jù)分類的正確率，得到一個新的樣本分布d3, 個子分類器h2。+h °<s)一得到一個子分類器h3 整合所有子分類器：+ +此例的閾值是1,即加權(quán)平均后對于藍(lán)色中大于1的區(qū)域就劃分為藍(lán)色種類, 其他部分為紅色種類。因此，從綜合的效果來看，即使是一個簡單的分類器組合, 也可以得到較好的分類結(jié)果。3本文的方法adaboost算法的完整步驟如下：given: (./.i. "1)(/," !/m) where .r, e a

13、'，/f e v = 1. +1initialize £)i(/) = jin.for t = train weak learner using distribution l)(. get weak hypothesis : ar > l +1 with erroru = pr:認(rèn)ma) / 隊 choose(yt = update:af e if h) = yizt eqfif/if(x,) / yi(i) exp(a)ztwhere zt is a normalization factor (chosen so that will be a distribution

14、).output the final hypothesis:h（r） = sign.如今，adaboost算法有了很大的發(fā)展，并且還出現(xiàn)了許多其他boost算法， 比如gentleboost和logitboost算法等。從上圖中我們可以看到adaboost算法 的一個詳細(xì)過程。adaboost是一種較有特點的算法，現(xiàn)總結(jié)如下：1）每次迭代改變的是樣本的分布，而不是重復(fù)采樣。2）樣本分布的改變?nèi)Q于樣本是否被正確分類?？偸欠诸愓_的樣本權(quán)值低，而分類錯誤的樣本權(quán)值高。3）最終的結(jié)果是弱分類器的加權(quán)組合。權(quán)值表示該弱分類器的性能。下面我們看看adaboost是如何進行訓(xùn)練的：訓(xùn)練過程:義初始化訓(xùn)練

15、樣本y,權(quán)重召(/) /=!,.,7v(1)若ih負(fù)樣本數(shù)閂一致，則卜+(2)蕎正負(fù)樣木數(shù)ii分別為2v+，;v_，2112jv止桿本2(/ = 則負(fù)樣本=b. for in = 1,. a/(1) 訓(xùn)練弱分類器(.v) = z(2,t>nt) g l,+l(2) 估u弱分類器/,(x)的分類錯誤率q如：=去乞孔仏(.'、-)，| 注： 0-5 /=1b. for m=l.m(續(xù)前)1 c估汁弱分類器x,(x)的權(quán)重q =log(4基于弱分類器a,(x)調(diào)整各樣本權(quán)重，并歸一化 調(diào)整：(0=(0-expc«, -= p巧若凡(w、e"l歸一化：k/k /二1，

16、tvh;=ic強分類器7/(x) = sgii4實驗(1)實驗程序這是川java語言在eclipse環(huán)境巾寫的一個小程序。下面的代碼:adaboost類的代碼：public class adaboost int matrix = new int8 8;/矩陣，行代表基分類器，列代表測試點point point;baseclassifiers be;vector<integer> h = new vector<integer>();vector<double> a = new vector<double>();/預(yù)測點的labelpublic in

17、t judge(point p) double result = 0.0; for (int i = 0; i < h.size(); i+) double temp = a.get(i) * bch.get(i).classify(p); result += temp;return result > 0 ? 1 : -1;/這個函數(shù)在對象生成后就應(yīng)該被調(diào)用，但是參數(shù)由用戶輸入，所以沒有 把它放到生成函數(shù)中public void adaboost (int t) double delt) /傳過來t=10， delt=0.01;int len = this. point. leng

18、th; /長度為8，即len=8 double d = new double len;/ 每個點的權(quán)重/初始時每個點權(quán)重應(yīng)滿足勻&布for (int i = 0; i < len; i+) di = 1.0 / len;for (int t = 1; t < t; t+) double error = choosehypothese(d); if (math.abs(error - 0.5) < delt) break;double at = 0.5 * math.log(l - error) / error); a.add(at);double z = 2 * ma

19、th.sqrt(error * (1 - error); for (int i = 0; i < len; i+) di = di * math.exp(-1 * at * pointi.label* matrixh.get(h.size() - 1)i) / z;decimalformat df = new decimalformat("0.00"); for (integer i : h) system.out.print(i +system.out.println(); for (double d : a) string s = df.format(d);sys

20、tem.out.print(s +/選擇最小錯誤的分類器，返回錯誤值public double choosehypothese(double d) int min = integer,max_value; double error = 1.1; for (int i = 0; i < be.length; i+) double temp = 0.0;for (int j = 0; j < point.length; j+) if (bci.classify(pointj) != pointj.label) temp += dj;if (temp < error) error

21、= temp; min = i;h.add(min); return error;public adaboost(point point, baseclassifiers be) this.point = point; this.be = be;/計算矩陣，行代表基分類器，列代表測試點，值為1則表示分類器對 測試點分類為1，-1類似for (int i = 0; i < be.length; i+) / 遍歷分類器for (int j = 0; j < point.length; +)/ 遍歷測試點matrixij = bci.classify(pointj); baseclass

22、ifiers 類的代碼：public class baseclassifiers char type;/笑型，x代表x=coordinate，y代表y=coordinateint coordinate;public baseclassifiers(char type,int coordinate)! this.type=type; this.coordinate=coordinate;/在分類器右方或者上方返回1，否則返回-1public int classify(point p) double x=p.x; double y=p.y; if(this.type:'x1)if(x-th

23、is.coordinate>=0) return 1;elsereturn -1;elseif(y-this.coordinate>=0) return 1;elsereturn -1; point類的代碼：public class point double x; double y;int label;/標(biāo)簽0或 1public point(double xdouble y,int value) this .x=x; this.y=y; this.label=value;public string tostring() return x+" "+y+"

24、 "+label;主程序adaboosttest代碼： public class adaboosttest testpublic void test() point point = new point8;point0=new point(0.5, 0.5-1)；point1=new pointcl.s 0.5)-1);point2=new point(4.5j 0.s,1);point3=new point(0.5j 1.5,1);point4=new pointq.s, 2.5,-1)；point5=new point(2.5 0.5,1);point6=new point(4.5

25、, 3.5,1);point7=new point(2.5j 5.51)；/ 弱分類器為x=l,x=2,x=3,x=4,y=l,y=2,y=3,y=4baseclassifiers be = new baseclassifiers8;bc0 = new bcl = new be2 = new be3 = new bc4 = new be5 = new bc6 = new be7 = newx、1); x、2); x., 3);x、4);y、1); y', 2);y、3); y., 4);baseclassifiers(baseclassifiers(baseclassifiers(ba

26、seclassifiers(baseclassifiers(baseclassifiers(baseclassifiers(baseclassifiers(adaboost add = new adaboost(point, be); ada.adaboost(10, 0.01);(2)實驗結(jié)果6160.670.390.2812 1 0.970.900.4412 6(3)結(jié)果分析從上面結(jié)果可知，在x軸等于1，y軸從2到6再至1的過程，其下面對應(yīng) 的錯誤率一直減小，直至在可接受的范圍內(nèi)為止，這樣就正確的將輸入的數(shù)據(jù)分 類。5討論與結(jié)束語對于adaboost的討論，目前比較

27、熱門的就是人臉識別了。尤其是當(dāng)今互聯(lián) 網(wǎng)、電子設(shè)備的大量普及，我們可以從網(wǎng)絡(luò)中大量的圖片或錄像中識別出有人臉 的圖像，精度高的話可以篩選出某個人的頭像；不管是照相機還是手機上的照相 機也會擁有人臉識別，提高照相的效果。像這樣的應(yīng)用還冇很多很多，當(dāng)然，追 求質(zhì)量和速度的互聯(lián)網(wǎng)時代，adaboost的改進是一門熱門的課題。adaboost分類算法具有非常高的精度，我們可以采用多種方法構(gòu)建子分類器，然后用adaboost這種桐架進行綜合分類（即人家所說的三個臭皮匠賽過一 個諸葛亮）。另外，adaboost易于執(zhí)行，系統(tǒng)檢測運行的速度很高，但是adaboost 算法本身由于耍進行多次訓(xùn)練，當(dāng)次數(shù)t過大

28、時就比較耗時，因此使整個系統(tǒng)的 訓(xùn)練時間加長。也正是由于adaboost算法訓(xùn)練時間過長，從而大大地降低了該 算法的應(yīng)用范圍。再者，adaboost算法框架是建立在弱分類器的選擇上，如果 弱分類器選擇不恰當(dāng)，也會給此次執(zhí)行效果大打折扣，過度依賴弱分類器也是其 一個缺點。當(dāng)然，容易受到噪聲干擾也是大部分算法的不足之處。所以，在用 adaboost進行分析時，需要考應(yīng)到這幾點。參考文獻:|1左登宇.基于adaboost兌法檢測研允u1200937-452 柴梅平，朱明.基于彩色分割的人臉檢測算法的研究閉，計算機測量與控制，2006,14(1):1113.3 violap.rapidobjectdetectionusingaboostedcascadeofsim-plefeaturj.prcieeeconfernceoncomputervisio nandpaternrecogition，2001.511 一 518.4j freundy.boostingaweakleamingalgorithmbymajor-ityljj.inforrnationandcomputati