高 林， 刘 英， 盛子豪

(青岛科技大学 自动化与电子工程学院， 山东 青岛 266042)

随机森林算法在交通状态判别中的应用

高 林， 刘 英， 盛子豪

(青岛科技大学 自动化与电子工程学院， 山东 青岛 266042)

随机森林算法随机选择多个决策树构成森林，算法分类结果由这些决策树投票得到，在运算量没有显著增加的前提下提高了预测精度，是一种目前比较流行的组合分类器算法。随机森林算法不仅可以用来做分类，也可用来做回归预测，是机器学习、计算机视觉等领域内应用极为广泛的一个算法。该文将随机森林分类算法用于交通状态判别，利用实测数据进行模型训练和验证，并用袋外数据计算判别正确率，实验结果表明该方法具有可行性，为交通状态判别提供了一种新思路。

随机森林算法； 交通状态判别； 袋外数据

随机森林(random forest,RF)算法是Leo Breiman提出的一种利用多个树学习器进行分类预测和回归预测的组合算法[1]。该算法具有广泛的应用,在生物信息学、生态学、医学、遗传学、遥感地理学、经济学等领域都有学者做了相关研究[2]。张华伟等[3]将随机森林模型应用于文本分类,实验表明分类性能胜于C4.5,与KNN、SMO和SVM效果相当。林成德等[4]将随机森林算法用于企业信用评估指标体系的确定,该方法确定的指标体系更有效地体现企业的信用状况。周博翔等[5]将改进的随机森林算法应用于基于加速度传感器的人体姿态识别,具有较高的分类预测正确率和行为识别率。

但随机森林算法在交通领域的应用较少。刘擎超等[6]提出了基于随机森林算法的交通事件检测模型,进一步提高了决策树模型的交通事件检测性能,且避免了噪声和过拟合现象,提高了检测率，减少了检测时间，提高了分类正确率。传统的交通状态判别算法多基于聚类算法、神经网络和支持向量机[7-9]。黄衍等[10]选取了20个UCI数据集,从泛化能力、噪声鲁棒性和不平衡分类主要方面进行分析,发现在多分类问题上,随机森林算法的泛化能力显著优于支持向量机,二者对数据类别噪声的鲁棒性无显著差异,在不平衡分类问题上,随机森林算法显著逊色于支持向量机。本文用随机森林算法进行交通状态判别,为交通状态的识别开辟了一种新途径。

1 随机森林算法简介

1.1 随机森林算法

随机森林算法基于决策树[11],决策树是数据挖掘与机器学习领域中一种非常重要的分类器,该算法通过训练数据来构建一棵用于分类的树,从而对未知数据进行高效分类。

构建决策树是个递归过程,理想情况下所有的记录都能被精确分类,但现实条件往往很难满足,使得决策树在构建时可能很难停止。即使构建完成,最终节点数往往过多,导致过度拟合现象。因此在实际应用中需要设定停止条件,当达到停止条件时,直接停止决策树的构建,但这不能完全解决过度拟合问题。实际中常常需要对构建好的决策树进行剪枝,但它不能解决根本问题。随机森林算法的出现能够较好地处理决策树的过拟合问题。

随机森林算法是一种有监督的集成学习算法,其基本思想是首先将大量的分类回归树(classification and regression tree,CART)通过特定规则组合成一片森林,然后对测试样本进行投票表决,最终分类结果由森林中的所有决策树根据多数占优的原则投票得出。

给定两个随机向量X、Y和由一系列分类器{h(x,θ1),h(x,θ2),…,h(x,θk),k=1,2,3,…}(其中参数集{θk}是独立同分布的随机向量,x是输入向量)构成的森林。边缘函数(margin function)的定义如下：

mg(X,Y)=aνkI(hk(x)=y)

-maxj≠yaνkI(hk(x)=j)

(1)

其中I(·)是示性函数,y为正确的分类向量,j为不正确的分类向量,aνk(·)表示取平均。实际上,边缘函数表示的是在正确分类Y之下X的得票数超过其他分类的最大得票数的程度,边缘函数的值与分类器置信度呈正相关。

在随机森林算法中,hk(x)=h(x,θk),当树的数目很大时,它遵循大数定律。边缘函数可以表示为：

mr(X,Y)=P(hk(x)=y)

-maxj≠yP(hk(x)=j)

(2)

其中,P(hk(x)=y)为判断正确的分类的概率,maxj≠yP(hk(x)=j) 为判断错误的其他分类的概率的最大值。

泛化误差PE*由下式得到：

PE*=PX,Y(mg(X,Y)<0)

(3)

其中,下标X,Y表明了概率的定义空间。

随着分类树数目的增加,对于所有的序列θk,PE*几乎处处收敛到：

Px,y(Pθ(hk(x)=y)=y-

maxj≠yPθ(hk(x)=j)<0)

(4)

因此随机森林算法不会随着分类树的增加而产生过拟合,但是会有一个有限的泛化误差。

1.2 袋外数据(OOB)估计

用Bootstrap自助采样方法(有放回)生成随机森林训练集时,初始的数据样本有一部分是不能被抽取的,这些样本的个数是初始数据集的(1-1/N)N,其中N为初始训练集中样本的个数[12]。已经有人证明,当N足够大时,(1-1/N)N会收敛于1/e≈0.368,即有将近37%的数据样本不会被抽取,这些不能从初始数据集中被抽取出来的样本组成的集合称为袋外数据(outofbag,OOB)。使用OOB数据估计随机森林算法的性能,称为OOB估计。

在随机森林生成的过程中,每一棵决策树生成过程中都会产生OOB数据,因此对于每棵决策树都会得到一个OOB估计。将森林中所有决策树的OOB误差估计取平均,即可得到随机森林算法的泛化误差估计。因为OOB数据是在随机森林算法生成过程中产生的,所以在随机森林算法中不需要再进行交叉验证或者单独地测试集来获取测试集误差的无偏估计,因此只用很少的资源就可以评估算法的泛化误差。

本文结合交通状态判别的实际需求,根据交通流特性[13],利用随机森林算法进行交通状态判别,仅利用OOB数据来计算判别结果的正确率。

2 实例应用

本文所用数据取自某市智能交通系统管控平台数据库,数据库中原始数据的存储周期为1min,考虑到实际应用情况,交通状态判别所用数据周期为5min。每条数据都包含速度、流量、占有率以及交通状态,其中交通状态是通过视频判断的结果。对数据库中原始数据进行加权平均,因为时间越近对交通状态的影响越大,所以所赋权重越大。计算公式如下：

xl=0.5xl,t+0.2xl,t-1+0.15xl,t-2

+0.1xl,t-3+0.005xl,t-4,l=1,2,3

(5)

其中,t为交通状态发布时刻,xl,t～xl,t-4为交通状态发布时刻所对应的5个时刻的原始数据,x1、x2、x3分别代表速度、车流量和时间占有率在t时刻的值。加权平均后交通流数据格式见表1。

表1 交通流数据格式

其中,为记录及编程方便,用1、2、3分别代表交通的畅通、缓行、拥堵3个状态。一般而言,速度越大,占有率越小,交通状态越趋向于畅通。由于进行了加权处理,所以车流量不是整数而是会出现小数。

本文为研究选取不同时间段数据对交通状态判别准确率的影响,将交通流数据分为普通时间段数据(包含晚高峰数据)与晚高峰数据进行验证分析,原始数据以及交通状态分别见图1和图2。

图1 普通时间段交通状态分布图

图2 晚高峰交通状态分布图

图1共取306个数据,图2取145个数据。图中不同符号表示不同的交通流状态,加号代表“畅通”状态,菱形代表“缓行”状态,圆圈代表“拥堵”状态。从图中可以看出,普通时间段“畅通”状态居多,“缓行”和“拥堵”所占比例很小；而晚高峰数据3种状态的数据比例相差不大。本文将这2个数据集作为原始数据集。

随机森林算法判别交通状态流程见图3。

图3 基于随机森林算法的交通状态判别流程

(1) 原始数据集中数据个数为N,从原始数据集中随机抽取2/3的数据作为训练集,对训练集进行学习,由此可构建N×2/3棵决策树分类器模型,剩余的N×1/3未被抽中的数据形成OOB数据,作为测试集。

(2) 假设共有M个特征变量,从M个特征中随机抽取F个特征,各个内部节点均是利用这F个特征变量上最优的分裂方式来分裂,F值在随机森林模型生成过程中固定不变。本文数据共有速度、流量、占有率3个特征变量,因此M=3,F≤3。

(3) 对测试集中的每个数据,将所有决策树分类器模型的判别结果采用多数投票法进行投票,票数最多的结果作为最终交通状态判别结果。

根据随机森林算法,用Matlab进行编程实现,利用OOB数据计算交通状态判别正确率,结果如图4和图5所示。

图4 普通时间段RF算法交通状态判别正确率

图5 晚高峰RF算法交通状态判别正确率

图4所示的普通时间段的交通状态判别正确率平均值为93.16%,图5所示晚高峰时的判别正确率平均值为82.38%,说明将随机森林算法用于交通状态判别是可行的。普通时间段判别正确率明显高于晚高峰时的判别正确率,结合图1和图2的交通状态分布情况,说明对于交通状态判别来说,时间的影响不可忽略。

从图4和图5也可以看出,验证次数取100次,但是每次验证的准确度都不同,因为随机森林分类算法执行时,每次都会随机选取数据样本构成决策树,数据样本选择不同,训练学习时产生的模型不同，则学习分类效果就会有所区别。

3 结语

将随机森林算法用于交通状态判别,并且利用OOB数据计算判别正确率。Matlab验证结果显示,基于随机森林算法的交通状态判别正确率可以达到80%以上,说明该算法具有可行性。普通时间段和晚高峰数据的正确率对比说明在进行交通状态判别时,选取不同时间段的数据对判别正确率会有影响,在今后提高交通状态判别算法正确率的研究时,可以仅利用晚高峰数据,这样更具有实际意义。

致谢:本文得到了山东省自然科学基金,青岛科技大学博士启动基金以及“黄彪泰山学者团队”资助。

)

[1]BreimanL.Randomforests[J].MachineLearning, 2001,45:5-32.

[2] 方匡南,吴见彬,朱建平,等. 随机森林方法研究综述[J]. 统计与信息论坛,2011,26(3):32-38.

[3] 张华伟,王明文,甘丽新. 基于随机森林的文本分类模型研究[J]. 山东大学学报(理学版),2006,41(3):5-9.

[4] 林成德,彭国兰. 随机森林在企业信用评估指标体系确定中的应用[J].厦门大学学报(自然科学版),2007,46(2):199-203.

[5] 周博翔,李平,李莲. 改进随机森林及其在人体姿态识别中的应用[J].计算机工程与应用,2015(16):86-92.

[6] Liu Qingchao, Lu Jian, Chen Shuyuan. Design and analysis of traffic incident detection based on random forest[J]. Journal of Southeast University (English Edition), 2014(1):88-95.

[7] 姜桂艳,郭海锋,吴超腾. 基于感应线圈数据的城市道路交通状态判别方法[J]. 吉林大学学报(工学版),2008(增刊1):37-42.

[8] 巫威眺,靳文舟,林培群. 基于BP神经网络的道路交通状态判别方法研究[J]. 交通信息与安全,2011,29(4):71-74.

[9] 于荣,王国祥,郑继媛,等. 基于支持向量机的城市道路交通状态模式识别研究[J].交通运输系统工程与信息,2013,13(1):130-136.

[10] 黄衍,查伟雄. 随机森林与支持向量机分类性能比较[J]. 软件,2012,33(6):107-110.

[11] 唐华松,姚耀文. 数据挖掘中决策树算法的探讨[J]. 计算机应用研究,2001,18(8):18-19.

[12] 刘建,吴翊,谭璐. 对Bootstrap方法的自助抽样的改进[J]. 数学理论与应用,2006(1):69-72.

[13] 郑建湖,郭银岁,叶润真,等. 基于环形线圈检测器信息的交通状态模糊识别方法[J]. 昆明理工大学学报(自然科学版),2009,34(2):71-75.

《国际单位制及应用》GB 3100—93列出了国际单位制(SI)的构成体系，规定了可以与国际单位制并用的单位以及计量单位的使用规则。

本标准适用于国民经济、科学技术、文化教育等一切领域中使用计量单位的场合。

摘自《国际单位制及应用》GB3100—93

Application of random forest algorithm to traffic state identification

Gao Lin, Liu Ying, Sheng Zihao

(College of Automation and Electronic Engineering, Qingdao University of Science and Technology, Qingdao 266042, China)

The random forest algorithm selects multiple decision trees randomly to constitute a forest, and the algorithm classification results are obtained by voting of these decision trees. The prediction accuracy is improved under the premise of no significant increase in computation, and it is a popular combination classifier algorithm at present. The random forest algorithm can be used for not only classification, but also regression prediction. It is most widely used in the fields of machine learning, computer vision and so on. This paper applies the random forest algorithm to the traffic state identification, and by using the real measured data, the model training and validation are carried out. The discriminant accuracy is calculated with the data out of the bag. The experimental results show that the method is feasible and provides a new idea for traffic state identification.

random forest; traffic state identification； data out of bag

10.16791/j.cnki.sjg.2017.04.012

2016-11-03 修改日期：2016-11-19

山东省自然科学基金项目(ZR2014FL018); 青岛科技大学博士启动基金项目(010022530)

高林(1976—)，男，山东青岛，博士，副教授，从事智能交通和数据挖掘算法的研究

E-mail：gaolin0619@126.com

刘英(1992—)，女，山东潍坊，硕士研究生，研究方向为数据挖掘和算法.

U491

A

1002-4956(2017)4-0043-04