| 标题 | 基于决策树的改进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. 责任编辑（责任编辑：孙娟） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。