基于支持向量机的城市道路交通状态模式识别研究

于 荣,王国祥,郑继媛,王海燕

(1.南京财经大学管理科学与工程学院,南京210046;2.江苏省质量安全工程研究院,南京210046; 3.东南大学交通学院,南京210002)

基于支持向量机的城市道路交通状态模式识别研究

于 荣1,王国祥1,郑继媛2,3,王海燕*2

(1.南京财经大学管理科学与工程学院,南京210046;2.江苏省质量安全工程研究院,南京210046; 3.东南大学交通学院,南京210002)

城市道路交通状态识别是现代智能交通系统的重要组成部分,是交通智能控制、诱导和协同系统的基础.基于支持向量机建立车流量、平均速度和占有率的三维反映空间,以堵塞流、拥挤流、平稳流和顺畅流为标签对道路交通状态进行分类;并在MATLAB平台下利用LiBSVM工具包进行实验分析,对SVM各种核函数的分类效果进行比较研究,实现了支持向量机技术的交通状态模式识别.结果表明:选择的指标能很好地反映交通状态的特征,SVM核函数可以以较高的分类精度区分开交通流的状态识别,数据的归一化对分类的结果具有重要的影响.

城市道路交通;交通状态;模式识别;支持向量机;LiBSVM

1 引 言

城市道路交通状态识别是现代智能交通系统(Intelligent Transportation System,ITS)的重要组成部分,通常是在道路交通数据实时采集的基础上,通过各种判别算法实现对各类交通数据的分析,与先验的交通状态标准进行比较,得到目前交通系统处于何种运行状态,并依据这个判别结果实现交通系统的智能控制、管理和诱导[1].实现快速有效的交通状态识别,是实现城市交通实时智能、有效控制的重要保证.现阶段对城市道路交通状态分类识别的研究主要集中在两个方面:一是道路交通状态的分类研究,侧重于面向交通实时数据的分类分析;二是基于先验分类的交通状态识别的研究,侧重在对交通状态识别方法的研究.

Adel W.Sadek[2]等学者将不同类型的交通网络状态定义为25个不同的案例,亦即25种模式. Francesco Palmieri[3]等学者针对交通网络状态,提出了一种非线性、基于循环的交通分类方法,这种非线性的方法不容易受到动态的交通端口变化的影响,具有较好的稳定性.Angélica Lozano[4]等基于K-means聚类分析算法,面向交通流实时数据分析,提出了一种在道路交通问题研究中的拥挤水平的识别算法.M.Montazeri-Gh[5]等面向驾驶环境状态识别问题,基于K-means聚类分析提出了一种交通状态识别的数学方法.Mohamed Abdel-Aty[6]等分析实时交通流参数和交通事故的相关关系,为识别事故车速和非事故车速,设计了一种基于神经网络的BAYES分类器.Andrzej Ruta[7]等针对实时交通信号识别问题,通过录像分析图像特定识别指标的方法对交通状态进行识别和分析.美国道路通行能力手册[8]中采用道路交通服务水平来描述车辆之间的运行条件及其驾驶员和乘客主观感觉,分为A～F级,前三级交通一般认为处于顺畅的运行状态,E、F级处于拥挤状态.

同济大学交通工程系ITS研究中心基于聚类分析方法对交通检测器所采集的道路上的交通流基础数据进行分析,选择的分类特征量为车流量、平均速度和占有率,将道路状态分为四个类别:堵塞流、拥挤流、稳定流、顺畅流.并给出了具体的流量—密度关系曲线.李清泉等[9]运用模糊支持向量机的方法对城市交通状态进行了分类.主要对交通流状态进行分类,但其仅仅以道路交通车辆运行速度为特征参数,将交通状态划分为畅通、基本畅通、拥挤、拥堵、堵塞五个层级.多数学者[10,11]在研究交通状态分类识别过程中对交通流的分类研究取得了较为成熟的成果,通过案例推理、聚类分析等分析手段,将交通状态分为不同等级进行研究,为本文提供了良好的研究基础和理论支撑.然而,在交通状态的识别和模拟仿真方面,虽然有各种算法在交通领域应用,但多数指标体系选择较为单一,在某种程度上并不能反映道路交通状态的实际情况,为本文的进一步研究提供了广泛的空间.

在现代智能交通管理系统中,各种判别算法经常被用来进行交通状态实时判断.现有的检测分类算法主要有四类,包括直接比较算法、时空预测算法、模式识别算法、人工智能算法等.本文将在前人状态分类的基础上,考虑交通多维特征进行交通状态定义和反映,基于模式识别算法中的支持向量机(Support Vector Machine,SVM)方法,实现对城市道路交通状态的识别,并在MATALB下进行数据实验分析.

2 基于支持向量机的城市道路交通状态分类理论与方法

2.1 道路交通状态特征参数的提取

在交通工程学的研究中,平均行驶速度、路段占有率、平均流量是反映交通流特征的重要参数,城市路段、路口及路网等不同区域内,特定时段交通流在这些参数方面表现出不同的特性[12].综合国内外研究成果,本文选取道路交通参数中的车流量、平均速度和占有率3个特征参数[13],对相应计算公式进行适当修订,以符合仿真系统参数设置,据此构建三维样本空间,相关指标定义如下:

(1)车流量:单车道2 min内为各车型的车辆数目乘上相应的车型比重后之和.计算公式为

式中 ni为t时段内通过的第i类车的车辆数;ωi为该类车辆折算系数;本文定义t为2 min.为实现进一步分析,并与既往研究成果相对应,将单位转换为pcu/h.

(2)平均速度:单车道2 min内所有机动车的平均速度,单位为mile/h.计算公式为

式中 v1——表示第1分钟内的平均速度;

v2——表示第2分钟内的平均速度;

f1——第1分钟内的流量;

f2——第2分钟内的流量.

(3)占有率:单车道2 min内车辆在某点检测器上的时间比例,单位为百分率.计算公式为

式中 ft——t时间段内的流量;

lt——t时间段内所有机动车量的车身长度;

vt——表示t时间段内的平均速度;

t——时间间隔,此处为2 min.

2.2 城市道路交通状态的定义

根据上述指标,结合现有理论研究成果,对城市道路交通状态进行聚类分析,相关聚类中心矩阵为

该矩阵第1行代表流量,单位为pcu/h,第2行代表速度,单位为mile/h,第3行代表占有率,单位百分率.

v1,v2,v3,v4分别代表堵塞流、拥挤流、平稳流和畅通流聚类中心.

3 SVM多类分类模型的构建

支持向量机(support vector machine)是Vapnik等人根据统计学理论提出的一种新的通用学习方法,它是建立在统计学理论的VC维理论和结构风险最小原理的基础上的,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以期获得最好的推广能力,能够较好地解决小样本、非线性、高维数和局部极小点等实际问题[14].近年来SVM在理论研究和算法实现方面都取得了突破性进展,并成功地应用于分类、函数逼近和时间序列预测等方面[15].

在城市交通状态识别中,结合交通的实际情况,定义观测矩阵x=[流量,速度,占有率],选取适当的核函数,并将观测矩阵x带入SVM判别函数,实现状态分类.

SVM方法是从线性可分情况下的最优分类面提出的,它的求解分类器为

其中的 ai,i=1,2,…,n,是下列二次优化问题的解

其中的b可通过使如下方程成立的样本(即支持向量)求得:

对于线性不可分情况,SVM通过满足Mercer条件的核函数代替原模式空间的向量数积运算以实现非线性变换,而不是显式地使用非线性变换的具体形式,其实质是将原模式空间变换为一个高维甚至无限维的Hilbert空间[16,17].如果对x进行非线性变换,记新特征为z=φ(x),可以证明,无论变换的具体形式如何,变换对支持向量机的影响是把两个在元特征空间中的内积(xi·xj)变成了在新空间中的内积(φ(xi)·φ(xj))[18].

记K(xi,xj)=(φ(xi)·φ(xj)),称之为核函数,则变换空间里的支持向量机可以写成:

其中的系数α是下列优化问题的解:

系数b通过使如下方程成立的样本(即支持向量)求得:

目前常用的核函数有3类,分别是:

(1)多项式核函数.

(2)径向基(RBF)核函数.

(3)sigmoid核函数.

本文构建的道路交通状态识别体系是一个多类分类问题,由于传统的支持向量机方法只考虑了二值分类的问题,所以需要对SVM模型进行扩展,建立多个支持向量机分类器.目前,构造SVM多类分类器主要有两类方法:一是直接法,直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该最优化问题一次性实现多类分类.这种方法计算复杂度比较高,实现起来比较困难,只适合用于小型问题中;另一类是间接法,主要是通过组合多个二分类器来实现多类分类器的构造,本文利用LIBSVM工具箱,采用一对一方法进行多类分类器的构建.

4 MATLAB下的实验分析

本文设定交通流的堵塞流、拥挤流、平稳流和顺畅流,通过模拟的方法生成有关流量、平均速度和占有率数据.每一种交通状态生成50个样本,共200组观测数据.并取每种状态40个样本作为训练数据,10个数据作为检测数据.利用MATLAB的LIBSVM 工 具 箱[14,19],利 用 matlab 自 带 的MAPMINMAX函数数据进行预处理,将数据归一化到[0,1]区间内,选取不同的核函数进行训练和分类,具体结果如下:

图1给出了样本在各维度的分布情况,由box图可见,数据中无异常点.

图2给出了样本在特征空间的分布情况,可见,在特征空间内,样本分布呈现较好的聚类效果,说明该特征空间对样本类别具有较好的区分效果.

图1 样本数据的可视化box图Fig.1 Visualization box diagram of sample data

图2 样本在特征空间的分布情况Fig.2 Sample distribution in the feature space

图3为利用多项式核函数,采用归一化的分类结果.由图可见,测试集分类效果不甚理想.40个测试样本中有12个被错分,正确率为70%.

图3 多项式核函数下归一化数据分类结果Fig.3 Normalized data classification results under polynomial kernel function

图4为利用多项式核函数,不采用归一化的分类结果,由图可见,测试集分类效果很好.所有样本均能正确分类,正确率为100%.

图4 多项式核函数下未经归一化数据分类结果Fig.4 Unnormalized data classification results under polynomial kernel function

比较多项式核函数在归一化和未归一化的处理结果可见,数据归一化对提高多项式核函数的分类效果无益,相比之下未归一化的数据分类效果更为理想.

图5为利用RBF核函数,采用归一化的分类结果,c=2,g=1,由图可见,测试集分类效果很好.所有样本均能正确分类,正确率为100%.

图5 RBF核函数下归一化数据分类结果Fig.5 Normalized data classification results under RBF kernel function

图6为利用RBF核函数,不采用归一化的分类结果,其中c=2,g=1,由图可见,测试集分类效果很不好.只有10个样本被正确分类,分类正确率25%.

图7为利用Sigmoid核函数,采用归一化的分类结果,由图可见,测试集分类效果很好.所有样本均能正确分类,正确率为100%.

图6 RBF核函数下未经归一化数据分类结果Fig.6 Unnormalized data classification results under RBF kernel function

图7 Sigmoid核函数下归一化数据分类结果Fig.7 Normalized data classification results undersigmoid kernel function

图8 Sigmoid核函数下未经归一化数据分类结果Fig.8 Unnormalized data classification results undersigmoid kernel function

图8为利用Sigmoid核函数,不采用归一化的分类结果,由图可见,测试集分类效果很不好.只有10个样本被正确分类,分类正确率25%.

比较上述结果,可见,RBF和函数和Sigmoid核函数对归一化之后的数据具有良好的分类效果,而对未进行归一化的数据分类效果不理想.从以上结果我们可以看出不同SVM核函数的参数设置及分类结果的不同,具体的比较如表1所示.

表1 不同SVM核函数参数设置及分类结果的比较Table1 Parameters setting and classification results comparison among different SVM kernel functions

5 研究结论

本文通过文献研究和仿真实际,构建了城市道路交通单车道流量、平均速度、占有率的三维参数体系,并根据该指标将道路交通划分为堵塞流、拥挤流、平稳流和顺畅流,在MATLAB平台下进行SVM算法实验分析,完成交通状态分类识别,得到的主要结论如下:

(1)选取城市道路交通单车道流量、平均速度、占有率来反映交通运行状态,并根据该指标将道路交通划分为堵塞流、拥挤流、平稳流和顺畅流,不仅反映了交通流中的重要参数,同时可以作为交通状态有效识别的特征参数.

(2)通过比较各种类型的SVM核函数,发现在利用单车道流量、平均速度、占有率三个指标及堵塞流、拥挤流、平稳流和顺畅流四类分类标签下,是否进行数据与处理及使用SVM各种核函数的分类结果可见,使用各种核函数均可以具有较高的分类精度,说明利用该分类标签及指标进行分类具有很好的应用效果.

(3)数据的归一化对SVM分类具有重要影响.通过比较归一化数据与未经归一化数据在不同核函数下的分类结果可见,相同参数设置条件下, RBF核函数和Sigmoid核函数对归一化数据具有良好的分类效果,而多项式核函数则对未经归一化数据分类效果明显.

[1]皮晓亮,杨晓光,孙亚.基于环形线圈检测器采集信息的交通状态分类方法应用研究[J].华东公路, 2006(1):33-38.[PI X L,YANG X G,SUN Y. Application research oftraffic state classification method based on collected Information from loop detector[J].East China Highway,2006(1):33-38.]

[2]Adel W Sadek,Michael J Demetsky,Brain L Smith. Case-based reasoning for real time traffic flow management[J]. Computer-Aided Civil and Infrastructure Engineering,1999,14:347-356.

[3]Francesco Palmieri,Ugo Fiore.A nonlinear recurrencebased approach to traffic classification[J].Computer Networks,2009,53(6):761-773.

[4]Angélica Lozano,Giuseppe Manfredi,Luciano Nieddu. An algorithm for the recognition of levels of congestion in road traffic problems[J].Matherematics and computers in simulation,2009,76(6):1926-1934.

[5]M.Montazeri-Gh,A Fotouhi. Trafficcondition recognition using the k-means clustering method[J]. Transportation Research B:Mechanical Engineering, 2011,18(4):930-937.

[6]Mohamed Abdel-Aty,Anurag Pande.Identifying crash propensity using specific traffic speed conditions[J]. Journal of Safety Research,2005,36(1):91-108.

[7]Andrzej Ruta,Yongmin Li,Xiaohui Liu.Real-time traffic sign recognition from video by class-specific discriminative features[J]. Pattern Recognition, 2010,43(1):416-430.

[8]美国交通研究委员会.道路通行能力手册[M].人民交通出版社,2007.[U S Transportation Research Board.Highway capacity manual[M].China Communications Press,2007.]

[9]李清泉,高德荃,杨必胜.基于模糊支持向量机的城市道路交通状态分类[J].吉林大学学报(工学版), 2009,39:131-134.[LI Q Q,GAO D Q,YANG B S. Urban road traffic status classification based on fuzzy support vector machines[J].Journal of Jilin University (Engineering and Technology Edition),2009,39:131-134.]

[10]李志恒,孙东,靳雪翔,等.基于模式的城市交通状态分类与性质研究[J].交通运输系统工程与信息, 2008,8(5):83-87.[LI Z H,SUN D,JIN X X et,al. Pattern-Based study on urban transportation system states and properties with fuzzy reasoning methods[J]. Journal of Transportation Systems Engineering and Information Technology,2008,8(5):83-87.]

[11]任江涛,欧晓凌,张毅,等.交通状态模式识别研究[J].公路交通科技,2003,20(2):63-67.[REN J T, OU X L,ZHANG Y,et al.Pattern recognition of traffic states[J].Journal of Highway and Transportation Research and Development,2003,20(2):63-67.]

[12]Kannal L.Patterns in pattern recognition:1968-1974 [J].IEEE Trans.on Information Theory,1974,20 (6).

[13]李作敏.交通工程学[M].人民交通出版社,2000. [LI Z M. Traffic engineering[M]. China Communications Press,2000.]

[14]杨淑莹.模式识别与智能计算——MATLAB技术实现[M].电子工业出版社,2011.[YANG S Y.Pattern recognition and intelligentcomputing——MATLAB technologyrealization[M].Publishing House of Electronics Industry,2011.]

[15]JP Marques de Sá著,吴逸飞译.模式识别——原理方法及应用[M].清华大学出版社,2002.[JP Marques de Sá,WU Y F.Pattern recognition——Principle,method and application[M].Tsinghua University Press,2002.]

[16]孙即祥.现代模式识别[M].高等教育出版社, 2008.[SUN J X.Modern pattern recognition[M]. Higher Education Press,2008.]

[17]Richard O Duda,Peter E Hart,David G Stork著,李宏东等译.模式分类[M].电子工业出版社,2010. [Richard O Duda,Peter E Hart,David G Stork,LI H D.Pattern classification[M].Publishing House of Electronics Industry,China CITIC Press,2010.]

[18]张学工.模式识别(第三版)[M].清华大学出版社, 2010.[ZHANG X G.Pattern recognition(Third edition)[M].Tsinghua University Press,2010.]

[19]Chih-Wei Hsu,Chih-Chung Chang,Chih-Jen Lin.A practical guide to support vector classification[EB/ OL].http://www.csie.ntu.edu.tw/～cjlin.

Urban Road Traffic Condition Pattern Recognition Based on Support Vector Machine

YU Rong1,WANG Guo-xiang1,ZHENG Ji-yuan2,3,WANG Hai-yan2
(1.School of Management Science and Engineering,Nanjing University of Finance and Economics,Nanjing 210046,China; 2.Jiangsu Province Institute of Quality and Safety Engineering,Nanjing 210046,China; 3.School of Transportation,Southeast University,Nanjing 210002,China)

As an important part of the modern intelligent transportation system,urban transport condition recognition is the base of intelligent control,guidance and synergy system.This paper establishes a threedimensional space with traffic volume,average speed and occupation ratio.It then classifies transportation condition patterns in terms of blocking flow,crowded flow,steady flow and unhindered flow based on wide literature review.Furthermore,this paper presents the algorithm with the MATALB LiBSVM toolbox.To process the data,this paper compares the classification result of different SVM kernel functions and thus realizes the transport condition pattern recognition via the support vector machine(SVM).The results reveal that the selected indexes effectively reflect the characteristics of the traffic conditions.The SVM kernelfunction can separate different patterns from traffic flows with high classification accuracy,and the data normalization has a significant influence on the result of classification.

urban road traffic; traffic state; pattern recognition; supportvectormachine (SVM);LiBSVM

U491

A

U491

A

1009-6744(2013)01-0130-07

2012-09-25

2012-11-09录用日期:2012-11-30

美国能源基金会资助项目(G-1208-16658).

于荣(1985-),女,江苏东海人,讲师,博士.

*通讯作者:njue2010@163.com