基于Adaboost和CART結合的優化分類算法

丁 雍，李小霞

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

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

本算法是基于以上兩種算法的改進算法，在算法的訓練過程中，用CART算法生成的二叉樹代替傳統Adaboost算法中的弱分類器，然后級聯成最終的強分類器，最后通過以實驗驗證了該算法的可靠性。實驗分別以數字圖像和人臉圖像為樣本，訓練生成分類器，再分別對若干張測試樣本分類并計算出分類誤差及誤差減小率。在目標檢測的實驗上，比較了改進算法和傳統Adaboost算法的優越性，兩種算法都能完全檢測到目標，且耗時相當。

1 Adaboost和 CART算法

1.1 Adaboost算法

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

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

圖1 Adaboost算法模型

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

1.1.1 Haar-Like特征

為了應用Adaboost算法實現對目標的檢測，VIOLA P和JONES M首次引入Haar-Like特征表示人臉目標[1]，并取得成功。實踐證明，對其他目標的表示也可以采用特定的Haar-Like特征。Haar-Like特征表示為一定大小的矩形模板，根據具體待檢測的目標形狀的不同[6]，有不同的特征模板，如圖2所示。

圖2 Haar-Like特征模板

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

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

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

1.1.2 特征生成

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

1.2 CART算法

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

圖3 CART模型

從根節點到每一個葉子節點，都對應一個規則。分類時，將待測樣本的對應特征逐一在此樹上從上到下搜索，直到葉子節點，此時，就將該樣本的屬性劃分為該葉節點所表征的類(正樣本或負樣本)。

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

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

其中，si表示 i類中正樣本的個數，s為總樣本個數。在CART算法中，因為每個節點都是二分的，即將樣本分成兩部分，所以熵的表示也就相對簡單。假設其中的正樣本出現的概率為p+，則負樣本出現的概率就是p-=1-p+，信息熵的公式表示為：

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

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

由于噪聲的存在，決策樹往往出現枝葉過于茂盛或者樹干過長的情況，在分類的過程中，這會導致對訓練數據過度擬合，使分類的錯誤率升高，反而不能對驗證數據很好地分類。所以，一棵優秀的決策樹應該包含剪枝的過程，即用驗證數據將樹的葉子或節點修剪，防止其對訓練數據的過度擬合。剪枝算法有多種，常見的有前向剪枝和后向剪枝兩種，CART算法采用的是后向剪枝算法。

2 改進算法

2.1 算法原理

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

圖4 改進算法的分類器模型

2.2 算法步驟

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

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

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

(4)For t=1，…，T

①歸一化權重：

②用CART算法構建二叉樹，作為弱分類器：

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

(b)對每一個特征 j，訓練一個小分類 hj器，小分類器與傳統的Adaboost算法中的弱分類器相同，用該小分類器對樣本分類，并計算分類錯誤率εj=Σiwi|hj(xi)-yi|。

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

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

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

③保存上面生成的3個節點的二叉樹和權值wi，作為此輪訓練得出的弱分類器Ht。

⑤最終的強分類器為：

在訓練步驟(c)中，考慮了分類錯誤率和信息熵增益兩個因素對分類的影響。算法在每一輪訓練中都選擇了對分類錯誤率最小的3個特征，然后再從其中計算信息熵增益最大的特征作為節點。這樣的選擇保證了弱分類器也能有較小的分類誤差，因此最終的強分類器也有較小的分類誤差。

3 實驗結果與分析

3.1 實驗描述

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

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

3.2 實驗結果

訓練樣本的數量越大，越能夠反映真實樣本的分布情況，在訓練的過程中，也更能提取出對分類有效的特征。實驗首先以數字圖像樣本為研究對象，以不同數量的樣本訓練分類器，然后將生成的分類器對200個測試樣本分類，得到圖5。可以明顯看出，隨著訓練樣本數量的增加，分類誤差呈現下降的趨勢，其下降的速率先快后慢，最后基本穩定在某一數值。實驗還發現，當訓練樣本數量遠遠大于測試樣本時，能夠使測試樣本的分類誤差達到最小。試驗中，在選取900個訓練樣本、100個測試樣本的條件下，能夠將100個測試樣本完全分開，分類準確率達到100%。

由以上實驗結果可知，當訓練樣本數量高于300個時，其分類誤差基本保持在某一數值。為此，實驗中將全部1 000個樣本分成500個訓練樣本和500個測試樣本(訓練樣本和測試樣本中均各含250個正樣本和負樣本)，分別用傳統的Adabost算法和改進算法生成強分類器，對測試樣本分類。圖6顯示了兩種分類器的分類誤差隨著訓練次數的變化情況。

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

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

表1統計了兩種算法對兩類樣本分類的一些參數。訓練樣本和測試樣本各占總樣本的1/2，均訓練300次。其中，誤差減小率表示改進算法的分類誤差相對于傳統Adaboost算法分類誤差的減小程度。

表1 算法誤差比較

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

將生成的分類器應用于目標檢測，能夠快速檢測出目標在圖像中的位置。由于改進算法的實現過程保留了傳統Adaboost算法中以Haar-Like模板提取特征的過程，因此兩種算法耗時相當。圖8(b)和圖8(d)分別是以上生成的數字分類器和人臉分類器對兩種目標的檢測結果。

本文以Adaboost算法和CART算法為基礎，提出了將這兩種算法相結合的改進算法，從理論上詳細闡述了算法的原理和步驟。算法的關鍵在于，在訓練樣本的每一輪訓練中尋找出對分類最有利的3個特征，形成二叉樹，用來代替傳統Adaboost算法中的弱分類器。樹的形狀是根據CART算法改進的，提高了單個弱分類器對樣本的分類能力，由于強分類器由弱分類構成，因此，強分類器的分類能力也得到提高。最后以人民幣圖像上的數字0和人臉圖像為樣本，驗證了本算法的可靠性和魯棒性。較普通的Adaboost算法而言，改進算法對數字樣本和人臉樣本的分類誤差率分別減少20%和86.5%，說明算法對樣本的分類能力有所提高。改進算法的每輪訓練都要生成有3個節點的二叉樹，其訓練過程將更加耗時，約等于普通算法的3倍。可以說，改進算法是以更長的訓練耗時換取更高的分類精確度。由于改進算法在特征提取過程中保持了傳統Adaboost算法的步驟，因此兩種算法在目標檢測的應用中耗時是相當的。

[1]毛國君.數據挖掘的概念、系統結構和方法[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.