DOI: 10.11817/j.issn.1672-7207.2017.06.036

城市快速路交通事件自动检测算法

邴其春^{1, 2}，龚勃文^{1, 3}，林赐云^{1, 3}，杨兆升^{1, 3}

(1. 吉林大学 交通学院，吉林 长春，130022；

2. 青岛理工大学 汽车与交通学院，山东 青岛，266520；

3. 吉林大学 汽车仿真与控制国家重点实验室，吉林 长春，130022)

摘要：为了进一步提高城市快速路交通事件检测的精度，在分析交通事件上、下游交通流参数变化规律的基础上，构建包含12个变量的交通事件检测初始变量集，并采用随机森林方法对初始变量集的关键变量进行筛选，进而构建基于粒子群优化的组合核函数相关向量机模型。最后，利用上海市南北高架快速路的感应线圈实测参数进行实验验证和对比分析。研究结果表明：关键变量筛选可以有效提高交通事件检测的精度，组合核函数相关向量机模型也明显优于单一核函数相关向量机模型和支持向量机模型。

关键词：交通事件自动检测；随机森林；相关向量机模型；组合核函数

中图分类号：U491             文献标志码：A         文章编号：1672-7207(2017)06-1682-06

Traffic incident automatic detection algorithm for urban expressway

BING Qichun^{1, 2}, GONG Bowen^{1, 3}, LIN Ciyun^{1, 3}, YANG Zhaosheng^{1, 3}

(1. School of Transportation, Jilin University, Changchun 130022, China;

2. School of Automobile and Transportation, Qingdao Technology University, Qingdao 266520, China;

3. State Key Laboratory of Automobile Simulation and Control, Jilin University, Changchun 130022, China)

Abstract: In order to improve the accuracy of traffic incident detection for urban expressway, through analyzing the change rules of traffic flow parameters, the initial variables set of traffic incident detection which contains 12 variables was built, and the random forest method was used to select the key variables. Then combined kernel function, relevance vector machine model was constructed based on particle swarm optimization. Finally, validation and comparative analysis were carried out using inductive loop parameters measured from the north-south viaduct in Shanghai. The results show that the key variable selection can effectively improve the accuracy of traffic incident detection. The detection performance of combined kernel function RVM model is also better than that of the single kernel function RVM model and SVM model.

Key words: automatic incident detection; random forest; relevance vector machine model; combined kernel function

城市快速路是城市路网的重要组成部分，承载着城市中大部分出行交通，快速路的畅通程度直接影响着城市路网的总体运行效率。然而，交通事件常常导致快速路发生大范围交通拥堵，严重影响着快速路的交通运行效率。据统计，在发达国家的快速路交通拥堵中，由交通事件引起的超过70%，在我国上海，因交通事件引起的交通拥堵也占快速路总拥堵的50%~75%^[1]，因此，研究准确、及时的交通事件自动检测(automatic incident detection，AID)算法对于保证快速路运行效率、提高道路安全水平具有重要意义。迄今为止，已有许多有效的模型与方法应用于交通事件自动检测的研究。早期开发的交通事件检测算法主要有加利福尼亚算法^[2]、标准偏差算法^[3]、基于突变理论的McMaster算法^[4]、低通滤波算法^[5]等。随着对交通流特性的深入研究以及人工智能新技术的发展，越来越多的交通事件自动检测模型相继被提出，如神经网络模型^[6-7]、支持向量机模型^[8-9]、贝叶斯方法^[10]、小波理论^[11]以及模糊逻辑方法^[12]等，并取得了一定的应用效果。然而，现有的研究主要集中于模型方法的整合优化，忽视了对交通事件检测输入变量的有效筛选；同时，神经网络、支持向量机等人工智能算法普遍存在计算复杂、泛化能力不强、容易出现过拟合等问题，严重影响模型的推广应用。为此，本文作者以交通流基本参数及其多角度组合的方式，构建较全面的交通事件检测初始变量集，并采用随机森林的变量重要性度量筛选出对交通事件更为敏感的关键变量，进而构建基于粒子群优化的组合核函数相关向量机模型，并以快速路实测数据对变量筛选及模型的有效性进行评价分析。

1  初始变量集构建

事件发生时段交通流参数的显著变化是设计交通事件自动检测算法的基本依据。当路段发生交通事件时，交通事件发生位置上游检测器采集的流量和速度急剧下降，占有率急剧上升；下游检测器采集的流量下降，速度上升，占有率下降^[13]。通过大量分析线圈检测器检测结果发现，不仅流量、速度、占有率这3个基本交通参数在交通事件发生时段会有明显变化，不同交通参数之间的组合以及上、下游检测器交通参数的组合对交通事件的发生也表现出很强的敏感性。因此，本文以交通流基本参数及其多角度组合的方式，构建较全面的交通事件检测初始变量集。初始变量集分为3部分：第1部分为检测器获取的基本交通参数；第2部分为同一检测器交通参数的组合；第3部分为相邻上、下游检测器交通参数的组合。表1所示为交通事件检测初始变量集。

交通参数的预测值采用移动平均模型获得，用相邻前n个时刻的数据预测第n+1个时刻的交通参数，本文中n取4。

表1  交通事件检测初始变量集

Table 1  Initial variables set of traffic incident detection

2  基于随机森林的变量筛选

交通事件检测初始变量集中有12个初始变量，较全面地涵盖了交通事件特性信息。但从实际应用的角度看，变量的个数过多，不仅会导致交通流信息冗余，而且极大地增加了模型的复杂性，因此，有必要对初始变量进行有效筛选，从初始变量集中选择对交通事件更敏感的关键变量，在保证交通事件检测效果的前提下降低模型的复杂度。随机森林(random forest, RF)模型是由BREIMAN提出的一种集成学习方法^[14]，能够有效处理高维数据，其变量重要性度量被广泛应用于特征选择^[15]。本文采用随机森林算法的变量重要性度量对交通事件检测初始变量集进行筛选，其基本思想是：依次对袋外数据中的每个变量添加随机噪声干扰，通过计算所有CART树上袋外数据分类正确率的平均降低值来决定该变量的重要性。具体流程如下。

Step 1：生成随机森林。

1) 在原始训练样本集L中应用Bootstrap抽样技术随机抽出L_b个样本，并由此构建1棵CART树h_i，未被选中的L-L_b个样本构成对应的袋外数据。

2) 在CART树的每个节点处抽取所有p个变量中的m_try个变量(m_try≤p)，计算每个变量蕴含的信息量，在m_try个变量中选择1个分类能力最佳的变量进行节点分裂。

3) 每棵树都自然生长，不进行剪枝处理。

4) 重复上述步骤m次，生成含有N棵CART树的随机森林f={h₁，h₂，…，h_m}。

Step 2：对于随机森林中的每棵CART树h_i(i=1，2，…，m)，使用相应的袋外数据进行分类，统计分类正确率R_i。

Step 3：对于任一变量x_j(j=1，2，…，p)，分别对袋外数据中x_j加入随机噪声干扰，变换后的袋外数据记为。利用每棵CART树h_i对进行分类，并计算分类正确率。

Step 4：计算每个变量袋外数据加入随机干扰后分类正确率的平均降低值作为该变量的重要度。变量x_j重要度I_V的计算式为

            (1)

若某个变量加入随机噪声后，袋外数据的分类准确率显著降低，则说明这个变量对分类结果影响较大，其重要度也就越高。

3  组合核函数相关向量机构建

相关向量机(relevance vector machine，RVM)模型是由TIPPING^[16]提出的一种稀疏贝叶斯概率模型，已成为近年来统计学习领域的重要研究热点之一。该算法起源于支持向量机(support vector machine，SVM)模型，与SVM具有相同的决策形式，同时拥有SVM所不具备的优点，例如RVM具有优于SVM的稀疏性；RVM只需设置核参数，对核函数的选择突破了Mercer条件限制；RVM在权值上引进了超参数，从而大大降低了计算的复杂度等。本文针对相关向量机模型的核函数选择问题，将具有不同特点的核函数结合起来，构建一种组合核函数相关向量机(combined kernel function relevance vector machine，CKF-RVM)模型。

3.1  组合核函数构造

传统的相关向量机模型大多采用单一核函数完成特征空间的映射过程，虽然在许多实际应用中取得了较好效果，但当样本数据特征中含有异构信息、样本规模较大或样本数据在高维空间中分布不平坦时^[17]，采用单一核函数映射方式对所有样本数据进行处理具有较大的局限性。因此，本文综合高斯核函数和多项式核函数各自的优势，构造新的组合核函数，使相关向量机模型不仅具有高斯核函数的局部学习能力，并且具有多项式核函数较强的泛化能力。构造的组合核函数形式为

 (2)

式中：λ为权重系数，0≤λ≤1；σ为高斯核函数的核宽度；d为多项式核函数的阶数。

当λ趋近于0时，组合核函数近似多项式核函数，虽然对离测试点较远处的样本数据具有较强的拟合能力，但对测试点附近的数据拟合效果不佳；当λ趋近于1时，组合核函数接近于高斯核函数，对测试点附近的小范围数据产生影响，但对全局的泛化能力较弱。由于不同的核函数各有特点，若核函数中的权重系数选择不合适，则组合核函数的拟合能力可能会低于单一核函数的拟合能力。因此，合适的权重系数对于组合核函数的性能至关重要。

3.2  基于粒子群算法的参数优化

本文所构造的组合核函数共有λ，σ和d 3个待优化参数，目前较常用的参数优化方法主要有交叉验证法、网格搜索法、遗传算法等，但这些方法往往计算量较大、耗时过长。粒子群(particle swarm optimization，PSO)算法是一种高效的全局优化方法，已被广泛应用于参数的优化设置。为此，本文采用粒子群优化算法获取组合核函数的最优参数，从而构建组合核函数相关向量机模型。

粒子群优化(particle swarm optimization，PSO)算法是由KENNEDY等^[18]提出来的一种进化计算技术，源于对鸟群捕食行为的研究。设在D维搜索空间中，存在M个粒子构成的粒子群体，PSO优化算法采用速度-位置搜索模型，第i个粒子的空间位置x_i=(x_i1，x_i2，…，x_iD)(其中，i=1，2，…，M)表示解空间的一个可行解，将其代入优化目标函数计算相应的适应度函数值来衡量x_i的优劣。第i个粒子的速度v_i=(v_i1，v_i2，…，v_iD)决定粒子在搜索空间单位迭代次数时的位移。粒子通过动态跟踪个体最佳位置P_i=(p_i1，p_i2，…，p_iD)和全局最佳位置P_g=(p_g1，p_g2，…，p_gD)来更新自身的速度和位置，更新公式如下：

   (3)

              (4)

式中：ω为惯性权重系数；r₁和r₂为2个在[0，1]之间变化的随机数；c₁和c₂为加速因子。

基于粒子群算法进行参数优化的具体步骤如下。

1) 初始化粒子群优化算法的参数，包括种群规模、粒子维数、迭代次数、加速因子、惯性权重系数等。

2) 采用5折交叉验证的交通事件平均检测率作为适应度函数值，并将其与自身的历史最佳位置适应度进行比较，若当前位置的适应度高于历史适应度，则将当前位置取代个体历史最佳位置。

3) 判断粒子群的全局最佳位置。将各个粒子的个体最佳位置适应度与群体的全局最佳位置适应度相比较，若高于群体的全局适应度，则将其位置取代全局最佳位置。

4) 判断终止条件。若不满足终止条件，则按式(3)和式(4)更新粒子的速度和位置，否则，输出得到的最优解。

4  实例分析

4.1  数据来源

本文选取上海市南北高架快速路上延东立交至共和立交长约10 km路段作为研究对象。该路段包括24个主线检测截面和30个匝道检测截面，共布设88个主线线圈检测器和60个匝道线圈检测器，主线检测器的平均间距约为500 m。数据采集时间分别为2008-09-01，2008-09-08，2008-09-15，2008-09-22和2008-09-29这连续5个星期一，线圈检测器可获取流量、速度和占有率3个基本交通流参数，数据采样间隔为5 min。通过分析交通流参数的变化趋势，人工筛选出107个主线交通事件，其中东侧主线62个，西侧主线45个。将交通事件数据按照东侧主线、西侧主线和整个路段进行分类，并与相应的正常状态数据构成3个样本数据集，每个数据集中的2/3作为训练样本，剩余部分作为测试样本。

4.2  变量筛选

采用随机森林算法对初始变量的重要性进行度量，进而筛选出对交通事件更为敏感的关键变量。其中，m_try取Breiman建议的特征变量个数的平方根，设置为3；随机森林中CART数的数量设置为1 000。利用Matlab7.0编程实现随机森林的变量重要度计算，将12个初始变量归一化处理后输入到随机森林程序中。图1所示为各个初始变量的重要度(其中，变量序号见图1)。

为了体现关键变量筛选的作用，应选择尽量少的变量个数，但又要保证交通事件检测的正确率。通过比较分析，最终选择重要度最高的4个变量作为关键变量。由图1可见：重要度最高的4个变量分别为同一检测器占有率与速度的比值、相邻上、下游检测器在同一时刻采集的占有率比值、同一检测器占有率与流量的比值、相邻上下游检测器在同一时刻采集的速度比值。

图1  变量重要度

Fig. 1  Importance of variable

4.3  参数优化

采用粒子群优化算法获得组合核函数的最优参数，其中，粒子群优化算法的具体参数设置如下：粒子个数为20，粒子维数为3，加速因子c₁=c₂=2，惯性权重系数从0.9随迭代次数线性减小至0.4，最大迭代次数为100，采用5折交叉验证的交通事件平均检测率作为适应度函数值。以东侧主线的样本数据集为例进行参数优化，图2所示为PSO寻优的适用度曲线。

图2  PSO寻优适应度曲线

Fig. 2  Fitness curves of PSO optimization

由图2可见：东侧主线样本数据集的组合核函数最优参数分别为λ=0.53，σ=0.25，d=3。

4.4  实验结果分析

4.4.1  评价指标

常用的AID算法评价指标主要有检测率R_D、误警率R_FA和平均检测时间D_MTT，但由于本文的交通事件数据库中无法获取交通事件的确切发生时间，因此，只能采用检测率和误警率这2个指标进行评价。

检测率R_D是指在特定的时间段内，由AID算法检测出的交通事件的数量N_D占实际发生交通事件数量N_A的百分比，即R_D=(N_D/N_A)×100%。误报率R_FA是指在特定时间段内，由AID算法检出的虚假交通事件的数量N_F占所有决策次数N_R的百分比，即R_FA=(N_F/N_R)×100%。

4.4.2  变量筛选有效性分析

为了验证基于随机森林的变量筛选对于提高交通事件检测效果的有效性，分别将初始变量和经过筛选的关键变量作为模型输入变量，利用东侧主线样本数据集构建的相关向量机模型和支持向量机模型进行实验验证，核函数均采用高斯核函数。表2所示为变量筛选有效性分析结果。

表2  变量筛选有效性分析结果

Table 2  Efficiency analysis results of variable selection

由表2可知：2种不同形式的输入变量均获得了较好的检测效果，以关键变量作为模型输入的交通事件检测效果更优。由此可见：深入分析交通事件对交通流参数的影响，多角度设计初始变量，能够获得较好的交通事件检测效果。同时，对初始变量进行有效筛选，既能减少冗余信息，又能有效提高交通事件检测的精度。

4.4.3  模型有效性分析

为了进一步验证组合核函数相关向量机模型在交通事件检测上的优越性，分别选取高斯核函数相关向量机(Gaussian kernel function relevance vector machine，GKF-RVM)模型、多项式核函数相关向量机(polynomial kernel function relevance vector machine，PKF-RVM)模型以及经典的高斯核函数支持向量机(Gaussian kernel function support vector machine，GKF-SVM)模型作为对比方法进行对比分析，模型输入变量均为筛选后的关键变量。为确保实验的充分性与全面性，分别对3个样本数据集进行实验与对比分析。表3所示为不同方法对3个数据集的参数取值，表4所示为不同方法的实验结果。

由表4可知：不同核函数RVM模型的检测效果均优于SVM模型的检测效果，说明RVM模型具有较强的分类能力，能够有效地进行交通事件检测。从3种不同核函数RVM模型的检测效果看，本文构建的CKF-RVM模型的检测效果明显优于GKF-RVM模型和PKF-RVM模型的检测效果，说明组合核函数能够兼顾不同核函数的优势，具有比单一核函数更强的交通事件检测性能。从不同样本数据集的检测效果看，东侧主线的事件检测效果最好，这是因为东侧主线的交通事件大多导致交通流参数波动较大，且持续时间较长；西侧主线的事件检测效果最差，这是由于西侧主线的交通事件大多对交通流影响较小，交通流参数波动不明显。综合结果表明：本文所构建的CKF-RVM模型取得了较好的检测效果，明显优于对比算法。

表3  不同方法的参数取值

Table 3  Parameters selection for different methods

表4  不同方法的交通事件检测效果对比

Table 4  Comparison of traffic incident detection results for different methods

5  结论

1) 在综合分析交通事件对交通流参数影响的基础上，构建交通事件检测初始变量集，并采用随机森林方法筛选出对交通事件敏感性较强的关键变量。

2) 构建组合核函数相关向量机模型，并利用粒子群优化算法获得最优参数。

3) 利用上海市南北高架快速路实测数据对算法的有效性进行了实验验证和对比分析。然而，本文在变量筛选过程中关键变量的个数需要依靠人工经验确定，定量确定标准有待进一步研究。

参考文献：

[1] 姬杨蓓蓓, 张小宁, 孙立军. 基于贝叶斯决策树的交通事件持续时间预测[J]. 同济大学学报(自然科学版), 2008, 36(3): 319-324.

JI Yangbeibei, ZHANG Xiaoning, SUN Lijun. Incident duration prediction grounded on Bayesian decision method based tree algorithm[J]. Journal of Tongji University(Natural Science), 2008, 36(3): 319-324.

[2] PAYNE H J, HELFENBEIN E D, KNOBEL H C. Development and testing of incident detection algorithms[R]. Washington D C, USA: Federal Highway Administration, 1976: 1-20.

[3] DUDEK C L, MESSER C J, NUCKLES N B. Incident detection on urban freeways[C]//Transportation Research Board. Washington D C: Transportation Research Board, 1974: 12-24.

[4] PERSAUD B N, HALL F L. Catastrophe theory and patterns in 30-second freeway traffic data-implication for incident detection[J]. Transportation Research Part A, 1990, 23(2): 103-113.

[5] STEPHANEDES Y J, CHASSIAKOS A P. Application of filtering techniques for incident detection[J]. Journal of Transportation Engineering, 1993, 119(1): 13-26.

[6] 姜桂艳, 温惠敏, 杨兆升. 高速公路交通事件自动检测系统与算法设计[J]. 交通运输工程学报, 2001, 1(1): 77-81.

JIANG Guiyan, WEN Huimin, YANG Zhaosheng. Design of freeway automatic incident detection system and algorithm[J]. Journal of Traffic and Transportation Engineering, 2001, 1(1): 77-81.

[7] SRINIV D, SHARMA V, TOH K A. Reduced multivariate polynomial-based neural network for automated traffic incident detection[J]. Neural Networks, 2008, 21(2/3): 484-492.

[8] 王武功, 马荣国. 交通事件检测的加权支持向量机算法[J]. 长安大学学报(自然科学版), 2013, 33(6): 84-87.

WANG Wugong, MA Rongguo. Weighed support vector machine for traffic incident detection[J]. Journal of Changan University (Natural Science Edition), 2013, 33(6): 84-87.

[9] 陈维荣, 关佩, 邹月娴. 基于SVM的交通事件检测技术[J]. 西南交通大学学报, 2011, 46(1): 63-67.

CHEN Weirong, GUAN Pei, ZOU Yuexian. Automatic incident detection technology based on SVM[J]. Journal of Southwest Jiaotong University, 2011, 46(1): 63-67.

[10] 张轮, 杨文臣, 刘拓. 基于朴素贝叶斯分类的高速公路交通事件检测[J]. 同济大学学报(自然科学版), 2014, 42(4): 558-563.

ZHANG Lun, YANG Wenchen, LIU Tuo. A naive Bayesian classifier-based algorithm for freeway traffic incident detection[J]. Journal of Tongji University (Natural Science), 2014, 42(4): 558-563.

[11] 尹春娥, 陈宽民, 万继志. 基于小波方程的高速公路交通事故自动检测方法[J]. 中国公路学报, 2014, 27(12): 106-112.

YIN Chune, CHEN Kuanmin, WAN Jizhi. Automatic detection method for expressway traffic accident based on wavelet equation[J]. China Journal of Highway and Transport, 2014, 27(12): 106-112.

[12] ROSSI R, GASTALDI M, GECCHELE G. Fuzzy logic-based incident detection system using loop detectors data[J]. Transportation Research Procedia, 2015(10): 266-175.

[13] 蔡志理. 高速公路交通事件检测及交通疏导技术研究[D]. 长春: 吉林大学交通学院, 2007: 51-52.

CAI Zhili. Study on traffic incident detection and traffic evanesce technologies for freeway[D]. Changchun: Jilin University, College of Transportation, 2007: 51-52.

[14] BREIMAN L. Random forest[J]. Machine Learning, 2011, 45(1): 5-32.

[15] GENUER R, POGGI J M, TULEAU-MALOT C. Variable selection using random forests[J]. Pattern Recognition Letters, 2015, 31(14): 2225-2236.

[16] TIPPING M E. Sparse Bayesian learning and the relevance vector machine[J]. Journal of Machine Learning Research, 2001, 1(3): 211-244.

[17] 瞿娜娜. 基于组合核函数支持向量机研究及应用[D]. 广州: 华南理工大学经济与贸易学院, 2011: 23-24.

QU Nana. Research and application of support vector machine based on mixed-kernel function[D]. Guangzhou: South China University of Technology. School of Economic and Commerce, 2011: 23-24.

[18] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Network. Piscataway, NJ: IEEE Service Center, 1995: 1942-1948.

(编辑  陈灿华)

收稿日期：2016-07-24；修回日期：2016-09-24

基金项目(Foundation item)：“十二五”国家科技支撑计划项目(2014BAG03B03)；国家自然科学基金青年基金资助项目(51308248，51408257)(Project (2014BAG03B03) supported by the National Science and Technology Pillar Program During the 12th “Five-year”; Projects(51308248, 51408257) supported by the National Natural Science Youth Foundation of China)

通信作者：龚勃文，博士，讲师，从事智能交通关键理论与技术研究；E-mail：gongbowen@ jlu.edu.cn