基于变量分析和粒子群优化加权随机森林的交通事件检测方法

罗预欣，张 兵，薛运强

(华东交通大学交通运输与物流学院，南昌 330013)

高速公路是城市间的主要通道，其特点是流量大，速度快，在高速公路上发生交通事件会带来严重的人员伤亡和降低道路通行效率，若不及时处理对后续的车辆还是乘车人员都有发生二次安全事故的可能性。据统计，美国快速路总拥堵事件中的55%～75%拥堵事件是由交通事件的发生引起的[1]，在中国上海，1/3的交通拥堵是由交通事件、车辆故障等交通事件造成[2]。因此，为了保障道路通行效率，道路安全水平，研究出准确及时的AID算法具有重要意义。近几十年，越来越多的交通自动检测(AID)算法被相继研究出。早期开发的AID算法主要有加利福尼亚算法[3]、基于突变理论的McMaster算法[4]等。随着对交通事故影响下事发路段交通特性变化分析[5]和机器学习、大数据的发展，越来越多的算法模型被相继提出，如神经网络模型[6]、支持向量机(SVM)模型[7]，随机森林(RF)模型[8]等。然而，在以往的交通事件自动检测算法中大多数的输入特征变量只是简单的流量、速度、占有率，并没有对交通事件初始变量进行全面的分析，导致检测效果并不理想。为此，从变量分析的角度构建全面的初始变量并进行筛选，在算法层面，将根据随机森林算法分类的缺点，提出对决策树进行权重赋值并利用粒子群(PSO)算法进行优化。提出基于变量分析和粒子群优化加权随机森林交通事件检测算法，实现快速有效地检测交通事件，提高AID系统的检测性能，确保高速公路交通事件发生时能及时有效地处理。

1 交通事件初始特征变量分析

高速公路交通流参数主要包括流量、速度、占有率、车头时距、车头间距。但对于交通事件检测算法来说常用的三种参数为流量、速度、占有率。其中流量指在某一截面或某一地点单位时间内通过的车辆数；速度指车辆在单位时间内行驶的距离；占有率也分为时间和空间上的占有率，由于空间占有率难以获取，一般来说在交通事件检测中，占有率通常指的是时间占有率，其含义指的是在某一时间内，车辆占用检测器时间与检测时间的比值。在高速公路上目前车辆检测器是常见的采集设备，它能采集交通流各参数，可运用这些参数进行AID算法的研究。

1.1 交通流基本参数分析

在发生交通异常状态时，交通流各参数数据将会发生显著的波动，与之相反，对于交通状态处于正常情况下的交通流各参数数据波动是在一定范围内的，当高速公路发生交通事件时，往往属于偶发性交通事件，如车辆追尾，货物散落等将造成这一路段在一定时间和范围内的交通拥堵导致道路的通行能力下降，车辆的行驶速度降低，道路占有率增加，如图1所示。其初始特征变量：检测器所采集的流量、速度、占有率。

图1 事件发生前后基本参数的变化Fig.1 Changes in basic parameters before and after the event

1.2 交通流参数组合分析

在发生交通事件时候，交通流参数将会发生一定的变化，对于单一的参数不能将这种变化放大，将考虑同一检测器参数的不同的组合，例如不同参数之间的差值、乘积、比值，以同一检测器交通实测量和交通预测量差值为例，如图2所示，图2中椭圆区域代表事件的发生。其中，本文交通流参数的预测值将采用移动平均法算出。其初始特征变量：同一检测器所采集的实测流量与预测流量的差值，同一检测器所采集的实测速度与预测速度的差值，同一检测器所采集的实测占有率与预测占有率的差值，同一检测器所采集的占有率与速度的比值，同一检测器所采集的流量与速度的比值，同一检测器所采集的占有率与流量的比值。

图2 事件发生时交通实测量与预测量之差Fig.2 The difference between the measured and predicted traffic at the time of the incident

1.3 不同区间交通流参数分析

当交通事件发生时，在事件发生路段的上下游是处于一个相反的交通状态，上游拥堵，则下游畅通。从数据层面上，其相邻的两个检测器采集到的交通流参数车辆速度、流量、占有率等数据将有明显的不同的变化，上游车辆速度降低，流量增加，占有率增加；下游则相反。其上下游检测器交通参数的组合对交通事件的发生也有很强的敏感性。其初始特征变量：上下游检测器流量的比值，上下游检测器占有率的比值，上下游检测器速度的比值。

综上所述，设计15个特征变量，构成交通事件检测的初始变量见表1。

2 基于树模型的变量选择

树模型一般不仅可以用来作为分类和回归，还可以对特征变量进行选择和重要度排序，比如决策树是一种基本的分类和回归的方法，但它也可以对特征变量进行选择，选出对训练集有较好分类能力的特征，一般采用的准则是基尼系数、信息增益或者信息增益比来进行特征选择。通过树模型：AdaBoost[9]、决策树的提升方法梯度提升树(GBDT)[10]，还有决策树的集合随机森林(RF)作为树模型对初始变量集进行特征变量筛选和排序，然后再将各特征变量在不同树模型中的重要度排序，最终得到所有变量的重要度排序对应不同变量个数的分类正确率。其流程如图3所示。

表1 初始特征变量Table 1 Initial characteristic variables

图3 变量选择流程Fig.3 Variable selection process

3 加权随机森林

3.1 随机森林理论

随机森林(RF)[11-14]是一种集成学习的组合分类器，利用Bootstrap重采样方法从原始数据中有放回的抽样，然后对抽取的样本进行决策树建模，将多颗决策树组合在一起，通过投票得出最终分类和预测的结果。随机森林算法在生成过程中实质上是采用Bagging采样技术对决策树进行集成，其目的是防止产生局部最优解。随机森林算法的随机性主要体现在两点，第一是训练集的随机抽取，第二是特征变量的随机选择。其算法流程如下：

(1)确定训练集X、随机变量m、树的规模T。

(2)通过Bagging采样技术从训练集中采取样本。

(3)在随机变量m中，随机的抽取n个变量(n≤m)与采取的样本构建决策树。

(4)通过以上的不断重复，形成多棵决策树，生成随机森林。并通过每棵决策树的投票确定最终的分类结果。

其最终的分类结果，可以表达为

(1)

式(1)中：H(X)为分类结果；ht(X)=y表示第t棵决策树得出的结果；I(·)表示括号中的个数；y=1,2,…，c表示类别数；t=1,2,…，T为决策树的数量。

3.2 加权随机森林算法

对于传统的随机森林，在进行最后投票分类的时候，每棵决策树的投票权重都是相同的，看似这种投票方式公平，但在随机森林中每棵决策树的分类精度都不一样，有些分类效果可能较好，有些则相对较差，再加上交通事件数据样本是一个不平衡数据样本，将导致随机森林的分类能力将趋向于大样本数据下决策树的分类结果。因此，提出加权随机森林模型[15-16]。其主要思路是在给每棵决策树设置一个权重，在进行投票时，每棵决策树都要乘以这个权重值。其中将训练样中的一部分样本用来对传统随机森林中的决策树进行训练，在训练完成后，用另一部分训练样本作为测试样本，对决策树进行测试其分类能力。

(2)

(3)

4 粒子群优化加权随机森林模型

对于加权随机森林算法，其中决策树数量T、测试样本X、随机变量m、剪枝阈值ε等参数在实际编程时都是通过经验来选取，若取值不当将对模型的输出有很大的影响，所以这些参数要进行优化。现在常用的参数优化方法有网格子搜索法、遗传算法相对于粒子群算法在优化上的性能较差。为此，采用粒子群算法[17]对加权随机森林的参数进行优化，获取最优的参数。

基于粒子群算法对加权随机森林参数优化的步骤如下：

(1)最开始对决策树数量T、测试样本X、随机变量m、剪枝阈值ε进行一个随机的设定。

(2)对用于分类的数据集进行Bootstrap采样，随机生成T个训练数据集，并在每个训练数据集中选出X个测试样本。

(3)将每个训练数据集中的另一部分数据样本对决策树进行构建，共T棵，在对决策树进行构建时，变量的选择均从全部的变量中选出m个特征变量作为该决策树结点的决策变量。

(4)当结点内包含的样本数少于阈值ε时，将该结点作为叶结点，并返回其目标属性的众数作为该决策树的分类结果。

(5)在生成完T棵决策树后，对每棵树进行测试，并计算其权重。

(6)通过式(3)计算出分类结果。

(7)将分类结果作为准确率，采用粒子群算法对(1)中提到的参数进行迭代优化，确定最终模型的参数。

其本文算法流程图如图4所示。

图4 本文算法流程图Fig.4 Flow chart of the proposed algorithm

5 实例验证

5.1 数据来源

数据来源于某市高速公路环形线圈检测器采集的交通事件数据，选取该高速公路长约为10 km的路段作为研究对象，该路段单向2车道，单车道宽3.5 m，大约平均500 m设置一个检测截面。检测器所采集的交通数据为流量、速度、占有率(时间占有率)，采集时间间隔为1 min，共计发生5 760个样本数据，部分样本数据见表2。

表2 部分样本数据Table 2 Partial sample data

5.2 特征变量选择

采用基于树模型的各种算法对交通事件的特征变量进行筛选，利用Python3.7编程实现这三种基于树模型的算法对初始变量进行排序，图5～图7分别是各算法初始变量重要度排序，最终通过各算法得出的变量重要度[18]进行综合得分排序，选择出对于交通事件发生更为敏感的关键变量，如图8所示。当进行初始变量筛选时，在寻找关键变量的同时也要保证分类正确率，经过三种算法比较分析，选取5个重要度相对较高的关键变量，分别为：同一检测器所采集的实测速度与预测速度的差值；同一检测器所采集的实测占有率与预测占有率差值。

图5 基于Adaboost算法变量筛选Fig.5 Variable selection based on Adaboost algorithm

图6 基于GBDT算法变量筛选Fig.6 Variable selection based on GBDT algorithm

图7 基于RF变量筛选Fig.7 Screening based on random forest variables

图8 最终变量重要度排序Fig.8 Ranking of importance of final variables

同一检测器实际占有率与预测占有率比值；上下游检测器速度的比值；上下游检测器占有率的比值。

5.3 参数优化

在设定决策树棵数T和剪枝阈值ε时，对决策树的数量在100～1 000取值；对剪枝阈值在10～100取值，分别判断其取值对建立加权随机森林模型分类正确率的影响。

从图9和图10可以看出剪枝阈值和决策树数量对加权随机森林模型的分类准确率有一定的影响，其中当剪枝阈值达到50时，准确率达到最优值，其后准确率逐渐降低并在此左右波动；准确率与决策树的数量的曲线为缓慢上升的趋势，决策树到500时准确率达到最高，之后缓慢降低；由此可见，加权随机森林的参数对模型的分类效果有一定的影响，所有将采用粒子群算法对模型参数进行优化以取得最优值。其中，粒子群优化算法的参数设置如下：学习因子c1=2，c2=2，惯性权重w=0.8，粒子个数为20，粒子维数为4，迭代次数为100。

5.4 实验结果分析

5.4.1 评价指标

交通事件自动检测算法(AID)评价指标采用以下指标：检测率(detection rate,DR)、误报率(false alarm rate,FAR)、平均检测时间(mean time to detection,MTTD)。

图9 剪枝阈值对加权随机森林分类性能的影响Fig.9 The influence of pruning threshold on the classification performance of weighted random forest

图10 决策树数量对加权随机森林分类性能的影响Fig.10 The influence of the number of decision trees on the classification performance of weighted random forest

(1)检测率(DR)：是指在同一时间段内AID算法检测到的事件数与实际发生的事件总数的百分比。

(4)

式(4)中：DM为检测到的事件数；AM为实际发生的事件数。

(2)误报率(FAR):表示在一定时间段内，误报事件数与所有决策次数之比。

(5)

式(5)中：FN为误报事件数；NR为所有决策次数。

(3)平均检测时间(MTTD)：指求实际发生时间和AID算法检测出事件的时间相差的算术平均值。

(6)

式(6)中：T(i)为被检测到的第i个事件发生的时间；A(i)为第i个事件实际发生的时间。

5.4.2 性能分析

为了验证对初始变量筛选后对事件检测的有效影响和本文模型(PSO优化的加权随机森林)在交通事件自动检测上综合性能的评价，将引入支持向量机(SVM)、随机森林(RF)算法进行检测效果整体分析。通过构建初始变量训练集，重要变量训练集，并带入这三种算法中测试其性能，结果见表3。

由表3可知，从变量角度看出，在进行过变量筛选后，利用重要变量进行检测，性能比利用初始变量检测有所改善，其中构建的三种算法检测率提高，误报率降低；从算法模型的角度可以看出，本文构建的PSO优化加权随机森林模型对初始变量和重要变量的检测性能都要比SVM、RF算法的检测效果要更优，在检测率和误报率上都有更优的效果，但在检测时间上还有进一步提高。综合实验结果分析：本文中对特征变量进行筛选并构建PSO优化的加权随机森林模型与SVM、RF算法相比，在检测性能上更优。

表3 不同算法检测效果对比Table 3 Comparison of detection effects of different algorithms

6 结论

以往传统的交通事件检测算法，其输入的特征变量是简单的交通流参数。通过对事件发生前后基本交通流参数的分析，不同交通流参数组合分析，不同区间交通流参数的组合，构建了较为完整的初始变量，通过几种不同基于树模型的算法综合分析得出重要变量。并运用PSO算法对加权随机森林优化，构建交通事件检测的模型，通过与SVM、RF的比较，本文算法在性能上更优。