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

李斌　王凱　徐英杰

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

關鍵詞關鍵詞：AdaBoost算法；決策樹；車輛檢測

DOIDOI：10.11907/rjdk.162868

中圖分類號：TP319

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

0引言

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

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

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

1基本原理

1.1AdaBoost算法

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

1.2決策樹

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

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

2AdaBoostDT算法

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

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

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

2.2改進的分類器級聯架構

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

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

第t級的再判決函數為：

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

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

第t級的再判決為：

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

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

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

3實驗

3.1實驗平臺

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

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

3.2測試數據

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

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

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

3.3測試圖像庫實驗

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

3.4測試視頻庫實驗

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

圖3為圖像庫的實驗結果示例。

3.5實驗結果分析

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

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

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

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

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

4結語

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

參考文獻參考文獻：

[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.

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