基于決策樹的改進AdaBoost算法在車輛檢測中的應用

李斌　王凱　徐英杰

摘要摘要：為滿足車輛檢測實時性和準確性需求，將基于C4.5的決策樹算法作為AdaBoost算法的弱分類器，產(chǎn)生一種速度快、識別率高的強分類器，稱之為AdaBoostDT算法。算法訓練多個決策樹并將之作為弱分類器，之后通過改進級聯(lián)架構(gòu)的AdaBoost算法將若干弱分類器組合成一個強分類器。該算法特點在于：相對于廣泛使用的以SVM作為弱分類器的算法，其以決策樹作為分類器，速度提高了29%；通過在AdaBoost算法進行強分類器的形成階段加入再判決函數(shù)，準確率提高了14.1%。

關(guān)鍵詞關(guān)鍵詞：AdaBoost算法；決策樹；車輛檢測

DOIDOI：10.11907/rjdk.162868

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：16727800（2017）005012903

0引言

隨著我國城鎮(zhèn)化建設的飛快發(fā)展及汽車保有量的增加，土地資源越發(fā)緊張，停車難的問題越發(fā)嚴重，由此產(chǎn)生的交通擁堵事故層出不窮。停車引導自動化成為一項重要技術(shù)，其解決的主要問題是車輛識別的速度和準確率。目前存在的識別方案主要有以下幾種：紅外感應、無線傳感器、圖像識別。在這些方案中，第一種還需要解決信號干擾、信號復用等問題，第二種方法不僅建設的成本高，而且還需要解決信道可靠傳輸?shù)膯栴}，結(jié)構(gòu)比較復雜。由此，基于圖像識別的車輛檢測與停車位識別技術(shù)受到人們的廣泛關(guān)注[1]，這其中最受關(guān)注的當屬分類器技術(shù)。

分類器技術(shù)不僅能夠用于目標檢測領(lǐng)域，在其它很多領(lǐng)域也發(fā)揮了重要作用，例如在語音信號處理、數(shù)據(jù)挖掘、信號聚類、圖像檢索等。目前存在很多能實現(xiàn)分類功能的算法，其中應用比較廣泛的為AdaBoost算法[2]，該算法先對車輛進行特征提取，在此基礎上采用支持向量機（Support Vector Machhine，SVM）[3]的方法進行車輛識別，取得了一定效果。基于SVM的檢測方法雖然具有很強的分類能力，但是選取特征的過程復雜，且易陷入局部極小。此外，基于SVM的檢測方法一般都需要比較大的計算量進行特征提取，這在一定程度上影響了算法的性能，很多情況下不能滿足車輛識別的效率要求。

本文提出的AdaBoostDT算法通過采用決策樹[45]作為AdaBoost的弱分類器，提高了車輛識別速度，并通過改進AdaBoost算法的級聯(lián)架構(gòu)，彌補決策樹作為分類器所導致的準確率下降，從而使集成后的強分類器與基于SVM的分類器相比，在準確度略微下降的情況下，速度能有很大程度的提升，更好地滿足車輛檢測系統(tǒng)對于實時性的要求。

1基本原理

1.1AdaBoost算法

AdaBoost算法是一種機器學習算法，它能將弱分類器提升為強分類器，其中分類器的強弱是指識別率高低。算法是通過調(diào)整訓練集上樣本的權(quán)重來實現(xiàn)其功能。開始時每個樣本的權(quán)重相等且總和為1，隨后AdaBoost算法對訓練集進行訓練，產(chǎn)生第一個弱分類器，并計算錯誤率。根據(jù)錯誤率調(diào)整權(quán)重，提升錯判樣本的權(quán)重，降低辨別正確的樣本的權(quán)重，這樣在之后的訓練中就會更多地考慮這些被錯判的樣本。在調(diào)整后的樣本權(quán)重基礎上，再進行訓練產(chǎn)生新的分類器，次迭代后就產(chǎn)生了N個檢測能力一般的弱分類器。AdaBoost再將這些弱分類器按照一定的權(quán)重進行一系列的組合，產(chǎn)生強分類器。理論證明，弱分類器的數(shù)量越多，各個弱分類器之間的差異越大，強分類器的效果越好。

1.2決策樹

決策樹算法是一種由J Ross Quinlan等提出的逼近離散函數(shù)值的算法，于20世紀60年代出現(xiàn)。該算法最初的用處是在已知各種情形出現(xiàn)概率的情況下，通過決策分支來獲取期望值及其對應的概率，評價項目風險，判斷可行性。由于形狀像一顆擁有很多分枝的樹，所以稱為決策樹。

決策樹算法是典型的分類算法，該算法先處理數(shù)據(jù)，產(chǎn)生一定的規(guī)則和決策樹，然后再運用決策分支對數(shù)據(jù)進行分析，本質(zhì)是按照一定的規(guī)則對數(shù)據(jù)進行分類。典型的決策樹算法有ID3[6]、C4.5[7]、CART等。本文提出的AdaBoostDT算法采用基于C4.5算法的決策樹作為弱分類器。C4.5算法作為ID3算法的改進算法，彌補了ID3算法的兩個不足之處[8]：一是ID3算法采用信息熵作為選擇樣本屬性的標準，很多時候，通過該標準選擇的屬性并不具有代表性，C4.5算法采用信息增益率作為樣本屬性的選擇標準，彌補了這個缺點；二是ID3算法只對屬性離散的數(shù)據(jù)集有處理能力，而不能處理屬性連續(xù)的數(shù)據(jù)集，而C4.5算法則對屬性離散和屬性連續(xù)的數(shù)據(jù)集都有較好的處理能力。

2AdaBoostDT算法

2.1弱分類器最佳分割闕值方法改進

C4.5算法作為ID3算法的改進算法，彌補了ID3算法的兩個缺點，但仍存在一些不足：C4.5算法要隨機地在屬性的不同取值中插入一些點，計算這些點的信息增益率，選擇值最大的屬性作為最佳分裂屬性。當遇到?jīng)Q策樹節(jié)點數(shù)量較多的情況時，將影響到?jīng)Q策樹的效率。提高決策樹識別速度的關(guān)鍵之處在于快速地找到最佳分割闕值。

根據(jù)邊界點原理[9]：連續(xù)數(shù)據(jù)集的最佳分割點總在邊界點處。本文按照遞減的順序?qū)⑦B續(xù)型屬性排列，再從相鄰的兩個邊界點附近選擇4個屬性作為測試屬性，按遞減的順序依次為：a1、a2、a3、a4。其中a1為類1中屬性的最大值，a2為類1中屬性的最小值，a3為類2中屬性的最大值，a4為類2中屬性的最小值。計算每個點的信息增益率，選擇最大的值作為最佳分割闕值，這樣只需計算4個屬性值，相對于傳統(tǒng)需遍歷所有屬性，計算相應的值，能極大提升決策樹的效率。當屬性只有兩個類別時，本文算法效率最高；每個屬性都只有一個類別時，本文提出的改進算法與傳統(tǒng)算法效率相同，效率最低。

2.2改進的分類器級聯(lián)架構(gòu)

傳統(tǒng)的AdaBoost級聯(lián)架構(gòu)就是一定數(shù)量的弱分類器簡單串聯(lián)[10]。由于每一級的弱分類器都有一定的誤判概率，使得整個分類器的識別率較低。例如，6個正確率為90%的分類器采用傳統(tǒng)方式級聯(lián)之后準確率為53.1%，6個正確率為96%的分類器采用傳統(tǒng)的級聯(lián)方式之后準確率也僅為78.3%，這顯然不能滿足車輛識別的實際需要。對此，本文通過增加再判決函數(shù)改進了AdaBoost算法的級聯(lián)架構(gòu)以滿足算法準確率的需求，改進算法的結(jié)構(gòu)如圖1所示。

在傳統(tǒng)的級聯(lián)判決中，每個分類器只考慮當前級別分類器對樣本的判決結(jié)果，而沒有考慮到前面分類器的判決結(jié)果，實際情況是分類器可以將前面分類器的結(jié)果作為參照用來修正當前的分類器，使準確率得到提高。本文對AdaBoost算法的每一級分類器后面增加一個再判決函數(shù)來提高準確率，再判決函數(shù)對被當前分類器判決為假的樣本進行再判決。如果再判決函數(shù)判決結(jié)果為假，那么認為樣本不是車輛，否則將樣本送到后一級分類器中。

第t級的再判決函數(shù)為：

Ht（xi）=γht（xi）+（1-γ）·（1/2）m

其中，γ代表當前分類器的權(quán)重系數(shù)，0<γ<1，ht（xi）=∑Dti=1f，表示第i級分類器判決對樣本xi判決的隸屬度；Dt為第t級中分類器數(shù)量；f表示在第t級分類器中用第i個弱分類器對樣本xi進行判決得到的結(jié)果；m為樣本Xi被前面t-1級分類器判斷為假的次數(shù)。

第t級的再判決為：

Tt（xi）=1，（xt）>bound0，other

其中，bound是第t級再判決器的閾值，大于該值認為是真，小于該值則認為是假。

再判決函數(shù)考慮了前面分類器的判決結(jié)果，它的作用相當于給后面的分類器設置了一個闕值，該闕值可根據(jù)前面各級分類器對樣本的判斷結(jié)果而作相應調(diào)整：當樣本被前面多個分類器錯判時，闕值變大，反之變小。這樣，對于正樣本而言，前期被拒絕次數(shù)少，闕值變小，在后面能盡早地通過判決。對于負樣本，前期被拒絕次數(shù)多，闕值很快就會變得很大，會盡早地被淘汰。

3實驗

3.1實驗平臺

實驗平臺包括硬件配置和軟件環(huán)境兩部分，硬件配置為配置intel Corei7-3612，16GB內(nèi)存的PC機，軟件環(huán)境采用了基于Win 10操作系統(tǒng)的VisualStudio2013搭載OpenCV2.4.8視覺庫。

下文將對OpenCV進行簡單介紹，OpenCV是由Intel公司于1999年開發(fā)的一個開源計算機視覺庫，全稱為Open Sorece Computer Vision Library。OpenCV集成了部分C++類和函數(shù)，為使用者提供了與圖像處理相關(guān)的許多通用算法。

3.2測試數(shù)據(jù)

本文創(chuàng)建了用于車輛識別的圖像庫和視頻庫，以全面檢驗決策樹分類器的性能。

本文建立了針對車輛前后俯視角度的圖像庫，該圖像庫大多數(shù)樣本為從網(wǎng)上搜集來的照片，從中挑選了100幅各種背景和各種光線強度下的圖片，通過剪輯使照片的尺寸都在720×480，每幅圖片都包含1～5輛車，總共含有368輛車，圖2為圖像庫的幾個示例。

為了測試算法的實時性，還建立了用于測試的視頻庫，視頻庫的視頻是在幾個不同的停車場進行錄制，再通過后期整理得到，共有6段時間長短不同的視頻，視頻分辨率為720×480，幀數(shù)為25fps。

3.3測試圖像庫實驗

依次用基于決策樹的AdaBoost算法、基于SVM的AdaBoost算法和本文提出的改進的基于決策樹的AdaBoostDT算法對圖像庫進行識別測試。3種算法正確識別車輛數(shù)目、車輛檢測率、誤檢車輛數(shù)目、誤檢率及對300張照片進行檢測花費的總時間如表1所示。

3.4測試視頻庫實驗

為了檢驗分類器是否滿足系統(tǒng)對實時性的要求，運用視頻庫對上述3種算法進行實驗，實驗時，每隔50ms從視頻中取一幀圖像。3種算法對每一段視頻中車輛的正確識別率、誤檢率和每一幀圖像的平均處理時間如表2所示。

圖3為圖像庫的實驗結(jié)果示例。

3.5實驗結(jié)果分析

通過運用圖像庫和視頻庫進行實驗，可以看出：

（1）普通的基于決策樹的識別算法，在車輛的正確識別率和誤檢率兩個方面與其它兩種算法相差很多，其不到80%的正確識別率明顯不能滿足對車輛識別準確性的要求。

（2）基于SVM的分類器算法，在檢測所花的時間上遠遠超過另外兩種算法，可以用在靜態(tài)的車輛檢測方向，但是對于停車場這種對實時性要求較高的系統(tǒng)不太適合。

（3）本文提出的AdaBoostDT算法雖然在車輛的正確識別率上比基于SVM的算法低3個百分點，但是其高于91%的識別率也足以滿足車輛檢測的需要。此外，本文提出的算法在辨別速度上比基于SVM的算法提高了30%，更能滿足及時性的要求。

（4）用于測試的照片包括各種光線條件下的、各種背景的照片，另外照片上的車輛也是各種各樣，有普通轎車、SUV甚至卡車。本文算法在復雜的情況下依然能保持較高的檢測率，說明本文算法的適用范圍很廣。

4結(jié)語

本文提出的AdaBoostDT算法，與傳統(tǒng)的基于SVM的AdaBoost算法不同，采用基于C4.5的決策樹算法作為弱分類器，顯著提高了AdaBoost算法的效率，得到結(jié)果的速度更快；再通過對AdaBoost算法級聯(lián)架構(gòu)進行改良，彌補決策樹算法相較于SVM算法作為弱分類器導致的準確率下降問題。實驗證明，本文提出的AdaBoostDT算法具有快速的識別速度和較高的準確率，更能滿足車輛識別系統(tǒng)實時識別的需要。

參考文獻參考文獻：

[1]ZHANG J P，WANG F Y，WANG K，et al.Datadriven intelligent transportation systems：asurver[J].IEEE Trans IntellTransp Syst，2011，12（4）：16241639.

[2]FREUND Y，SCHAPIRE R.Adecisiontheoretic generalization of online learning and an application to boosting[J].Journal of Computer and System Sciences，1997，55（1）：119139.

[3]ANOSPIDE J，SALGADOL.Regiondependent vehicle classification using PCA features[C].IEEE International Conference on Image Processing.Washiington DC：IEEE Computer Society，2012：453456.

[4]LI FACHAO，LI PING，JIN CHENXIA.Summary of decision tree algorithm and its application in attribute reduction[R].Shijiazhuang：Hebei Univ.of Seism and Technology，2009：313317.

[5]謝金梅，王艷妮.決策樹算法綜述[J].軟件導刊，2008，7（11）：8385.

[6]CHEN JIN，LUO DELIN，MU FENXIANG.An improved ID3 decision tree algorithm[C].Chengdu：4th International Conference on IEEE Computer Science and Education，2009：127130.

[7]QUINLAN J R.C4.5：programs for machine learning[M].San Mateo：morgan Kaufmann Publishbers Inc，1993：1742.

[8]YANG XUEBING，ZHANGJUN.Decision tree algorithm and its key techniques[J].Computer Technology and Developmeng，2007，17（1）：4446.

[9]FAYYAD U M，INANIK B.On the handing of continuesvalue attributers in decision tree generation[J].Machine Learning，1992，8（1）：87102.

[10]VDLA P，JONESM.Robust realtiem object detection[C].Second Internationl Workshop on Statistical and Computationsl Theories of Vision：Modeling，Learning，Computing and Sampling，2007.

責任編輯（責任編輯：孫娟）