基于Adaboost和CART結(jié)合的優(yōu)化分類算法

丁 雍，李小霞

(西南科技大學(xué) 信息工程學(xué)院 模式識(shí)別與圖像處理實(shí)驗(yàn)室，四川 綿陽 621010)

數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中提取出隱含有用信息的過程[1]。分類是數(shù)據(jù)挖掘的一種重要形式，在分類算法中，Adaboost算法和 CART(Classification and Regression Tree)算法在對(duì)數(shù)據(jù)的分類中都有著重要的作用。Adaboost算法是一種迭代算法，其核心思想是針對(duì)同一個(gè)分類集訓(xùn)練不同的弱分類器，然后把這些弱分類器結(jié)合起來形成一個(gè)強(qiáng)分類器進(jìn)而實(shí)現(xiàn)對(duì)數(shù)據(jù)分類，其分類速度快、精度高。2001年，由VIOLA P和JONES M將該算法應(yīng)用于人臉定位[2]，算法開始得到快速的發(fā)展。此后，LIENHART R和MAYDT J又用此算法成功實(shí)現(xiàn)了對(duì)不同方位人臉的檢測(cè)[3]。決策樹算法最早是由HUNT等人于1966年提出的CLS(Concept Learning System)。當(dāng)前，最有影響的決策樹算法是QUINLAN于1986年提出的ID3和1993年提出的C4.5。CART算法是基于以上兩種方法的改進(jìn)算法，它采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個(gè)子樣本集，使得生成的決策樹的每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)分支。因此，CART算法生成的決策樹是結(jié)構(gòu)簡(jiǎn)潔的二叉樹[4]，比ID3和C4.5算法具有更好的抗噪聲性能。

本算法是基于以上兩種算法的改進(jìn)算法，在算法的訓(xùn)練過程中，用CART算法生成的二叉樹代替?zhèn)鹘y(tǒng)Adaboost算法中的弱分類器，然后級(jí)聯(lián)成最終的強(qiáng)分類器，最后通過以實(shí)驗(yàn)驗(yàn)證了該算法的可靠性。實(shí)驗(yàn)分別以數(shù)字圖像和人臉圖像為樣本，訓(xùn)練生成分類器，再分別對(duì)若干張測(cè)試樣本分類并計(jì)算出分類誤差及誤差減小率。在目標(biāo)檢測(cè)的實(shí)驗(yàn)上，比較了改進(jìn)算法和傳統(tǒng)Adaboost算法的優(yōu)越性，兩種算法都能完全檢測(cè)到目標(biāo)，且耗時(shí)相當(dāng)。

1 Adaboost和 CART算法

1.1 Adaboost算法

Adaboost算法的訓(xùn)練過程就是找出若干個(gè)弱分類器[5]。設(shè) n個(gè)弱分類器(h1，h2，…，hn)是由相同的學(xué)習(xí)算法形成的，每個(gè)弱分類器能單獨(dú)對(duì)未知樣本分類成正樣本或負(fù)樣本(二分類情況)，通過加權(quán)統(tǒng)計(jì)弱分類器的分類結(jié)果得出最終的分類結(jié)果。選擇弱分類器的過程中，只要求分類器對(duì)樣本的分類能力大于自然選擇就可以了，即分類錯(cuò)誤率小于0.5。凡是分類錯(cuò)誤率低于0.5的分類器都可以作為弱分類器，但在實(shí)際的訓(xùn)練過程中，還是選擇錯(cuò)誤率最低的分類器作為該輪選擇的弱分類器，表示如下：

其中，p=±1，用于改變不等式的方向，θj代表某個(gè)特征j的閾值。Adaboost算法模型如圖1所示。

圖1 Adaboost算法模型

圖1中，權(quán)重代表弱分類器對(duì)樣本分類的貢獻(xiàn)大小，其值越大，表明特征對(duì)樣本的分類能力越好。分類結(jié)果是由n個(gè)弱分類器加權(quán)“投票”的結(jié)果，投票結(jié)果與某一閾值比較，得出最終對(duì)樣本的分類。強(qiáng)分類器F表示為：

1.1.1 Haar-Like特征

為了應(yīng)用Adaboost算法實(shí)現(xiàn)對(duì)目標(biāo)的檢測(cè)，VIOLA P和JONES M首次引入Haar-Like特征表示人臉目標(biāo)[1]，并取得成功。實(shí)踐證明，對(duì)其他目標(biāo)的表示也可以采用特定的Haar-Like特征。Haar-Like特征表示為一定大小的矩形模板，根據(jù)具體待檢測(cè)的目標(biāo)形狀的不同[6]，有不同的特征模板，如圖2所示。

圖2 Haar-Like特征模板

特征為矩形圖像中白色區(qū)域內(nèi)的像素總和減去黑色區(qū)域的像素總和，它反映了白色區(qū)域到黑色區(qū)域的梯度變化情況。

試驗(yàn)中對(duì)特征的提取一般都是基于特征圖的，特征圖可以使計(jì)算量大大減少。積分圖就是對(duì)要處理的圖像二次積分，表示如下：

其中，f(x，y)表示積分圖，g(i，j)表示原圖像。 對(duì)數(shù)字圖像而言，點(diǎn)(x，y)處的積分圖為該像素左上所有像素的和。

1.1.2 特征生成

特征生成即是將樣本圖像表示成矢量的形式。以24×24樣本圖為例，生成積分圖之后，選擇有效的Haar-Like特征模板，在積分圖中移動(dòng)，并保存特征值。當(dāng)一次移動(dòng)完之后，改變模板大小繼續(xù)移動(dòng)取特征值，然后將所有特征按先后順序排列成一維向量成為代表樣本的特征向量。由于模板是在積分圖上移動(dòng)的，因此，每次只需要知道模板的4個(gè)頂點(diǎn)坐標(biāo)就可以通過加減法輕松計(jì)算出特征值。生成的特征數(shù)量相對(duì)較多，參考文獻(xiàn)[3]具體分析了每個(gè)模板對(duì)應(yīng)的特征的個(gè)數(shù)及其計(jì)算公式，統(tǒng)計(jì)了所有模板在24×24圖像上移動(dòng)生成的特征總數(shù)為117 941個(gè)，即以117 941維的矢量表示一個(gè)樣本圖。

1.2 CART算法

CART算法是決策樹的一種，所不同的是，它的分支始終是二分的。用變量y表示分類結(jié)果，用X表示p維特征，該算法首先找出p維特征中對(duì)分類有效的某個(gè)特征x，將樣本分成兩個(gè)本集子樣，以樹的左右枝表示，并將此特征作為根節(jié)點(diǎn)。接下來判斷左右子樣本集是否只包含純樣本(全部正樣本或全部負(fù)樣本)，如果是，則將此樣本集定義為葉子；否則，再次在此子樣本集中找出有效特征，繼續(xù)將子樣本集空間劃分成左右枝，直到被劃分的子樣本集中只包含純樣本為止。在同一等級(jí)的節(jié)點(diǎn)中，可以選取相同屬性的特征作為節(jié)點(diǎn)，這個(gè)劃分是以遞歸方式實(shí)現(xiàn)的，最終形成一棵二叉樹，形狀如圖3所示。

圖3 CART模型

從根節(jié)點(diǎn)到每一個(gè)葉子節(jié)點(diǎn)，都對(duì)應(yīng)一個(gè)規(guī)則。分類時(shí)，將待測(cè)樣本的對(duì)應(yīng)特征逐一在此樹上從上到下搜索，直到葉子節(jié)點(diǎn)，此時(shí)，就將該樣本的屬性劃分為該葉節(jié)點(diǎn)所表征的類(正樣本或負(fù)樣本)。

在決策樹的分支中，常用的分支準(zhǔn)則為信息熵法和信息增益法。其中，信息熵是ID3算法中常用的分支方法，而信息增益法主要是C4.5和CART中常用的分支方法。

信息熵本為通信電路攜帶信息量的大小，在這里反映的是某一個(gè)特征閾值對(duì)樣本的劃分準(zhǔn)確率。對(duì)于訓(xùn)練例集U，假設(shè)有m個(gè)類別，全局信息熵表示為：

其中，si表示 i類中正樣本的個(gè)數(shù)，s為總樣本個(gè)數(shù)。在CART算法中，因?yàn)槊總€(gè)節(jié)點(diǎn)都是二分的，即將樣本分成兩部分，所以熵的表示也就相對(duì)簡(jiǎn)單。假設(shè)其中的正樣本出現(xiàn)的概率為p+，則負(fù)樣本出現(xiàn)的概率就是p-=1-p+，信息熵的公式表示為：

如某一特征閾值將正負(fù)樣本完全分開，此時(shí)被分開的每個(gè)子集的信息熵就達(dá)到最小。設(shè)訓(xùn)練樣本空間為U，以某一特征A將樣本空間劃分為U1和U2兩個(gè)子集，在子空間，如果包含20個(gè)樣本，10個(gè)正樣本和10個(gè)負(fù)樣本，則正樣本的概率等于負(fù)樣本的概率，即p+=p-=0.5，帶入式(5)可計(jì)算得到此空間的信息熵達(dá)到最大值1。與此類似，如果樣本空間U1為同一樣本，則計(jì)算得到熵的最小值0。如果用屬性A將訓(xùn)練集劃分為兩個(gè)子集S1和 S2，每個(gè)子集中的信息熵又按照式(5)計(jì)算，分別用Es1和Es2表示，此時(shí)的正負(fù)樣本概率都以該子集中的樣本為依據(jù)統(tǒng)計(jì)。然后得出信息期望熵：

CART算法對(duì)節(jié)點(diǎn)的分支依賴于信息熵增益，即選取信息增益熵最大的特征作為一個(gè)節(jié)點(diǎn)。信息熵增益反映了全局信息熵降低的程度，信息熵增益越大，表明特征對(duì)樣本分類越有利，信息熵增益表示如下：

由于噪聲的存在，決策樹往往出現(xiàn)枝葉過于茂盛或者樹干過長(zhǎng)的情況，在分類的過程中，這會(huì)導(dǎo)致對(duì)訓(xùn)練數(shù)據(jù)過度擬合，使分類的錯(cuò)誤率升高，反而不能對(duì)驗(yàn)證數(shù)據(jù)很好地分類。所以，一棵優(yōu)秀的決策樹應(yīng)該包含剪枝的過程，即用驗(yàn)證數(shù)據(jù)將樹的葉子或節(jié)點(diǎn)修剪，防止其對(duì)訓(xùn)練數(shù)據(jù)的過度擬合。剪枝算法有多種，常見的有前向剪枝和后向剪枝兩種，CART算法采用的是后向剪枝算法。

2 改進(jìn)算法

2.1 算法原理

Adaboost算法在每一輪的訓(xùn)練過程中都會(huì)判斷某一單獨(dú)特征對(duì)訓(xùn)練樣本的分類能力，然后加大被錯(cuò)誤分類樣本的權(quán)重，減少被正確分類樣本的權(quán)重。由于權(quán)重在每一輪訓(xùn)練完成之后都在改變，因此，每次選擇的特征并不一定是最好特征，只是在當(dāng)前權(quán)值條件下分類最好的特征。為了改善弱分類器對(duì)樣本的分類能力，選擇一棵具有3個(gè)節(jié)點(diǎn)的二叉樹代替原來的弱分類器，即每輪訓(xùn)練都找出3個(gè)對(duì)分類最優(yōu)的特征，構(gòu)成一棵樹。弱分類器的分類結(jié)果由這3個(gè)特征共同決定，比起只用單獨(dú)特征分類的弱分類器而言，它對(duì)樣本的分類能力更高。由于每個(gè)弱分類器對(duì)樣本的分類能力提高了，因此，最終的強(qiáng)分類器的分類能力也將提高。為了與Adaboost算法中的弱分類器h區(qū)別，改進(jìn)算法中的弱分類器用H表示。圖4描述了本算法形成的分類器模型。

圖4 改進(jìn)算法的分類器模型

2.2 算法步驟

根據(jù)圖4的分類器模型，算法步驟如下：

(1)給定訓(xùn)練集圖像 I1，I2，…，In，規(guī)范化到相同尺寸，計(jì)算積分圖，利用Haar-like矩陣生成特征。

(2)給 定 訓(xùn) 練 集 (x1，y1)，(x2，y2)， … ，(xn，yn)， 其 中 ，x1，x2，…，xn代表圖像的特征；yi=0，1，分別代表負(fù)樣本圖像和正樣本圖像。

(4)For t=1，…，T

①歸一化權(quán)重：

②用CART算法構(gòu)建二叉樹，作為弱分類器：

(a)計(jì)算全局信息熵E。

(b)對(duì)每一個(gè)特征 j，訓(xùn)練一個(gè)小分類 hj器，小分類器與傳統(tǒng)的Adaboost算法中的弱分類器相同，用該小分類器對(duì)樣本分類，并計(jì)算分類錯(cuò)誤率εj=Σiwi|hj(xi)-yi|。

(c)找出錯(cuò)誤率最小的 3 個(gè)小分類器 h1、h2、h3，計(jì)算由它們劃分的兩個(gè)子樣本集的信息熵，計(jì)算信息期望熵E(U，A)，并計(jì)算信息增益 G=E-E(U，A)。

(d)選擇信息熵增益最大的特征作為根節(jié)點(diǎn)，將該節(jié)點(diǎn)分支，分成兩個(gè)子集。

(e)在兩個(gè)子集中分別按照步驟(b)~(d)再次找到兩分支節(jié)點(diǎn)，生成有3個(gè)節(jié)點(diǎn)的二叉樹。

③保存上面生成的3個(gè)節(jié)點(diǎn)的二叉樹和權(quán)值wi，作為此輪訓(xùn)練得出的弱分類器Ht。

⑤最終的強(qiáng)分類器為：

在訓(xùn)練步驟(c)中，考慮了分類錯(cuò)誤率和信息熵增益兩個(gè)因素對(duì)分類的影響。算法在每一輪訓(xùn)練中都選擇了對(duì)分類錯(cuò)誤率最小的3個(gè)特征，然后再?gòu)钠渲杏?jì)算信息熵增益最大的特征作為節(jié)點(diǎn)。這樣的選擇保證了弱分類器也能有較小的分類誤差，因此最終的強(qiáng)分類器也有較小的分類誤差。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)描述

為了說明改進(jìn)算法的效果，在相同條件下得出了兩種算法的實(shí)驗(yàn)結(jié)果并進(jìn)行了比較。實(shí)驗(yàn)一以人民幣圖像中的數(shù)字0作為樣本，樣本圖像均由人工采集，在不同面額的人民幣圖像上采集得到正樣本圖像和負(fù)樣本圖像各500張。實(shí)驗(yàn)二以人臉圖像作為樣本，樣本來源于AR (AR Face Database.http：//cobweb.ecn.purdue.edu/~aleix/aleix_face_DB.html)人臉數(shù)據(jù)庫，正負(fù)樣本各1 000張。

實(shí)驗(yàn)均選擇以圖2(a)和圖2(b)的 Haar-Like模板生成特征。實(shí)驗(yàn)過程采用交叉驗(yàn)證的方式完成，所有實(shí)驗(yàn)均在同一條件下進(jìn)行。實(shí)驗(yàn)條件：PC機(jī)采用AMD AthlonTMII x2220 2.81GHz處理器和2GB內(nèi)存；代碼執(zhí)行平臺(tái)為MATLAB7.0。

3.2 實(shí)驗(yàn)結(jié)果

訓(xùn)練樣本的數(shù)量越大，越能夠反映真實(shí)樣本的分布情況，在訓(xùn)練的過程中，也更能提取出對(duì)分類有效的特征。實(shí)驗(yàn)首先以數(shù)字圖像樣本為研究對(duì)象，以不同數(shù)量的樣本訓(xùn)練分類器，然后將生成的分類器對(duì)200個(gè)測(cè)試樣本分類，得到圖5?？梢悦黠@看出，隨著訓(xùn)練樣本數(shù)量的增加，分類誤差呈現(xiàn)下降的趨勢(shì)，其下降的速率先快后慢，最后基本穩(wěn)定在某一數(shù)值。實(shí)驗(yàn)還發(fā)現(xiàn)，當(dāng)訓(xùn)練樣本數(shù)量遠(yuǎn)遠(yuǎn)大于測(cè)試樣本時(shí)，能夠使測(cè)試樣本的分類誤差達(dá)到最小。試驗(yàn)中，在選取900個(gè)訓(xùn)練樣本、100個(gè)測(cè)試樣本的條件下，能夠?qū)?00個(gè)測(cè)試樣本完全分開，分類準(zhǔn)確率達(dá)到100%。

由以上實(shí)驗(yàn)結(jié)果可知，當(dāng)訓(xùn)練樣本數(shù)量高于300個(gè)時(shí)，其分類誤差基本保持在某一數(shù)值。為此，實(shí)驗(yàn)中將全部1 000個(gè)樣本分成500個(gè)訓(xùn)練樣本和500個(gè)測(cè)試樣本(訓(xùn)練樣本和測(cè)試樣本中均各含250個(gè)正樣本和負(fù)樣本)，分別用傳統(tǒng)的Adabost算法和改進(jìn)算法生成強(qiáng)分類器，對(duì)測(cè)試樣本分類。圖6顯示了兩種分類器的分類誤差隨著訓(xùn)練次數(shù)的變化情況。

由圖6可以看出，隨著訓(xùn)練次數(shù)的增加，兩種分類器對(duì)測(cè)試樣本的分類誤差逐漸減小。在訓(xùn)練次數(shù)高于某個(gè)數(shù)值之后，改進(jìn)算法的錯(cuò)誤率明顯低于普通的Adaboost算法，說明改進(jìn)算法的分類能力較強(qiáng)。由于實(shí)驗(yàn)中所選樣本的可分性較強(qiáng)，因此，無論是傳統(tǒng)的Adaboost算法還是改進(jìn)算法，其分類誤差都比較低(小于1%)。

為了驗(yàn)證算法魯棒性，實(shí)驗(yàn)從AR人臉庫中得到正負(fù)人臉樣本各1 000張，再次比較兩種算法的分類情況，如圖7所示。從圖中可以看出，改進(jìn)算法對(duì)特征不明顯的人臉圖像分類照樣能達(dá)到較高的分類精度(99.3%)，高于普通的Adaboost算法(94.8%)，這說明本算法的魯棒性較強(qiáng)。

表1統(tǒng)計(jì)了兩種算法對(duì)兩類樣本分類的一些參數(shù)。訓(xùn)練樣本和測(cè)試樣本各占總樣本的1/2，均訓(xùn)練300次。其中，誤差減小率表示改進(jìn)算法的分類誤差相對(duì)于傳統(tǒng)Adaboost算法分類誤差的減小程度。

表1 算法誤差比較

從表1可以看出，改進(jìn)算法對(duì)不同的目標(biāo)樣本分類能力均有所提高，并且提高的程度有所不同。數(shù)字樣本的Harr-like特征較明顯，所以，無論是改進(jìn)算法還是普通的Adaboost算法，分類誤差都較小，而且誤差減小率也相對(duì)較小。而從兩種算法對(duì)人臉樣本的分類可以看出，改進(jìn)算法能明顯減小分類誤差，提高分類器的分類能力。

將生成的分類器應(yīng)用于目標(biāo)檢測(cè)，能夠快速檢測(cè)出目標(biāo)在圖像中的位置。由于改進(jìn)算法的實(shí)現(xiàn)過程保留了傳統(tǒng)Adaboost算法中以Haar-Like模板提取特征的過程，因此兩種算法耗時(shí)相當(dāng)。圖8(b)和圖8(d)分別是以上生成的數(shù)字分類器和人臉分類器對(duì)兩種目標(biāo)的檢測(cè)結(jié)果。

本文以Adaboost算法和CART算法為基礎(chǔ)，提出了將這兩種算法相結(jié)合的改進(jìn)算法，從理論上詳細(xì)闡述了算法的原理和步驟。算法的關(guān)鍵在于，在訓(xùn)練樣本的每一輪訓(xùn)練中尋找出對(duì)分類最有利的3個(gè)特征，形成二叉樹，用來代替?zhèn)鹘y(tǒng)Adaboost算法中的弱分類器。樹的形狀是根據(jù)CART算法改進(jìn)的，提高了單個(gè)弱分類器對(duì)樣本的分類能力，由于強(qiáng)分類器由弱分類構(gòu)成，因此，強(qiáng)分類器的分類能力也得到提高。最后以人民幣圖像上的數(shù)字0和人臉圖像為樣本，驗(yàn)證了本算法的可靠性和魯棒性。較普通的Adaboost算法而言，改進(jìn)算法對(duì)數(shù)字樣本和人臉樣本的分類誤差率分別減少20%和86.5%，說明算法對(duì)樣本的分類能力有所提高。改進(jìn)算法的每輪訓(xùn)練都要生成有3個(gè)節(jié)點(diǎn)的二叉樹，其訓(xùn)練過程將更加耗時(shí)，約等于普通算法的3倍?？梢哉f，改進(jìn)算法是以更長(zhǎng)的訓(xùn)練耗時(shí)換取更高的分類精確度。由于改進(jìn)算法在特征提取過程中保持了傳統(tǒng)Adaboost算法的步驟，因此兩種算法在目標(biāo)檢測(cè)的應(yīng)用中耗時(shí)是相當(dāng)?shù)摹?/p>

[1]毛國(guó)君.數(shù)據(jù)挖掘的概念、系統(tǒng)結(jié)構(gòu)和方法[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2002，23(8)：13-17.

[2]VIOLA P， JONES M.Rapid objectdetection using a boosted cascade of simple features[C].Accepted Conference on Computer Vision and Pattern Recognition， 2001(5)：511-518.

[3]LIENHART R，MAYDT J.An extended set of Haar-like features for rapid object detection[C].IEEE ICIP 2002， 2002，1：900-903.

[4]YOHANNES Y， HODDINOTT J. Classification and regression trees：an introduction[C]. International Food Policy Research Institute 2033 K Street， N.W.Washington， D.C.20006 U.S.A， 1999.

[5]HORE U W.Comparative implementation of colour analysis based methods for face detection algorithm [C].Emerging Trends in Engineering and Technology (ICETET)， 2010(3)：176-179.

[6]LISU L.Research on facedetection classifierusingan improved adaboost algorithm[C].International Symposium on Computer Science， 2009(2)：199-204.

[7]FREUND Y，SCHAPIRE R E.Experiments with a new boosting algorithm[C].Machine Learning：Proceedings of the Thirteenth International Conference， San Francisco， 1996(5)：148-156.