用于交通流预测的带距离权重模式识别算法*

刘树青 徐建闽 卢凯 马莹莹

(华南理工大学 土木与交通学院, 广东 广州 510640)



用于交通流预测的带距离权重模式识别算法*

刘树青 徐建闽 卢凯 马莹莹

(华南理工大学 土木与交通学院, 广东 广州 510640)

基于带权重的模式识别算法(WPRA)的交通流短时预测根据历史交通模式所属时段特征区分不同历史状态值权重系数的大小,但权重值的主观设定降低了方法实际应用的可靠性.通过分析基于数据驱动的非参数回归交通流预测算法核心原理,针对WPRA模型权重系数的主观随机性进行预测算法改进,建立了能预测短时交通流的带距离权重的模式识别算法(DWPRA).最后,应用实际交通流数据引入均方根误差进行算法验证,验证结果显示相同近邻K值情况下,DWPRA比WPRA均方根误差降低约4.8%～7.1%,证明了算法的有效性.

模式识别;交通流短时预测;K-近邻搜索;距离权重;均方根误差

交通流具有复杂的时空特征,随着城市交通需求的急速增长,对交通流的态势分析和预测研究逐渐成为智能交通领域的热点问题.交通流状态参数(流量、速度、密度、占有率等)预测对交通控制策略的主动性研究、交通信息诱导、交通信号控制方案优化具有重要的实际应用意义.交通参数的变化具有一定的确定性和随机性.确定性是指交通流态势变化在一定时段内具有一定的波动规律,使交通状态变得可预测,例如一个路口每周工作日期间早高峰、平峰、晚高峰时段波动,每周五晚下班时段交通流量远大于平常日晚下班时段交通流量等流量的随时段规律性波动现象.随机性是指每天相同时刻的交通流量可能是不同,增加了交通状态预测的不确定性,这种随机性的影响因素有很多,可能是因为驾驶员的路径随机选择,也可能是因为交通突发事件.通过大量路网历史交通信息数据,我们可以具体分析交通流变化的确定性和随机性.因此,基于数据驱动的交通流预测,即从大量历史观测数据学习交通流变化规律,再利用这些规律预测当前时刻的未来交通状态,一直是交通流预测的重要方法.这类方法主要有支持向量机模型[1]、神经网络模型[2]、非参数回归模型[3]3种.其中,支持向量机、神经网络等需要对参数做耗时的调整,且模型可移植性差[4].相对而言,非参数回归法[3]不需要任何先验知识,是一种完全依靠数据驱动且具有良好的数据挖掘和可移植性的算法,预测精度也满足智能交通系统的要求.

Davis等[5]于1991年将非参数回归方法应用于交通流预测,后来Smith等[6]利用K-NN(K Nearest Neighbor)方法进行单点交叉口交通流短时预测.2005年,Kim等[7]提出一种基于交通流变化序列的PRA(Pattern Recognition Algorithm)非参数回归预测方法,Li等[8]根据相同变化序列的历史交通流数据所处的时段特征,对近邻历史交通状态赋予不同的权重系数,提出了一种预测精度高于K-NN方法和PRA方法的WPRA(Weighted Pattern Recognition Algorithm)非参数回归预测方法,后来又利用局部加权回归法[9]提高了算法的运算效率.但是，WPRA交通流短时预测模型并不能给出明确的权重设定方法,权重参数的主观设定使预测结果存在很大随机性.所以,文中在分析非参数回归交通流短时预测原理的基础上,提出一种基于新的DWPRA(Distance Weighted Pattern Recognition Algorithm)交通流短时预测方法,经实际交通数据验证,预测结果比WPRA模型RMSE误差降低4.8%～7.1%.

1 相关交通流预测方法分析

1.1 相关方法介绍

(1)K-NN

(1)

式中,ωi为历史状态i的权重系数,K为近邻历史交通状态数,K-NN预测模型的建立是基于以下3点:

①当前交通状态V与历史同时刻交通状态Vhi(i=1,2,…,m)具有规律性重复特征;

③近邻历史状态间的距离差异可以表达xt+1的随机性.

(2)PRA

(2)

未来t+1时刻交通状态值与当前t时刻交通状态值及(t-n,t)时段内的交通变化序列VC有关是PRA预测模型建立的核心依据.

(3)WPRA

WPRA将一天分为几个时段,对PRA方法提出的具有相同交通变化序列的历史状态按照所处时段不同赋予大小不同的权值,与当前时刻t处于相同时段的权重系数大,处于其他时段的权重系数小.WPRA模型预测算法[8]为

(3)

WPRA模型依据时段特征对权重系数ωi赋予大小不同的两种权重值的设计思想是:相同时段相同交通变化序列的历史状态对未来t+1时刻交通预测的价值更大.

1.2 方法对比分析

K-NN方法仅在同时刻历史交通数据中寻找距离最近的交通状态,PRA方法将数据寻找范围扩展为任意时段内交通变化序列相同的历史交通状态，WPRA方法为近邻历史交通状态按照时段不同赋予了不同的权重系数.以均方根误差[10]作为预测精确度评估误差,应用实际交通流检测数据和交通流仿真生成数据进行验证,PRA方法比K-NN方法精确度提高约20%[7],WPRA方法比PRA方法精度提高约20%[8].通过历史数据样本分析,研究交通流规律性重复和随机性波动对短时交通预测的影响,是所有基于数据驱动的交通流短时预测算法的建模思路.对预测t+1时刻交通状态最有价值的历史交通状态的选取标准和相关权重系数计算方法,都对预测结果精度有重要影响.

2 DWPRA交通流预测

2.1 历史数据整理

历史数据库容量越大,说明预测可参照的数据样本越多,相同预测模型下的预测结果就越精确,但庞大的历史数据量会降低计算效率.因此,在进行交通预测之前,要通过数据过滤和数据归类对历史数据库进行整理.

数据过滤是指通过阈值判断或条件规则判断[9],对由于硬件故障或噪声干扰产生的错误数据进行过滤.不同类型检测器检测的交通参数不同,但错误的交通数据一般分为两类:第一类是检测数据过大或超出合理阈值范围,例如单车道检测流量为2 500 veh/h;第二类是检测数据冲突,例如车道断面检测线圈检测交通流量为0,但平均占有率不为0.通过数据过滤可以得到正确的历史数据库,提高算法精度.

数据归类是指通过归类分析技术将历史数据归到所属的类别中,产生不同类型样本数据库.论文将历史交通数据按照日期类型和天气归为8类:首先将数据按照日期归为工作日、非工作日两类,然后按照天气不同(雨、雪、雾、其他)将每种日期类型包含的数据归为四类,历史数据最终归为8类.通过数据归类可以提高交通流预测运算效率和算法精度.

2.2 交通变化序列

以交通流量为例,假设数据检测时间间隔为5 min,交通变化序列是指相邻检测间隔时间交通流量“增加”、“不变”、“降低”变化的符号表示.记连续n+1个交通流量检测结果为(xt,xt-1,…,xt-n),t-i至t-i+1的交通流量变化序列为sgn(xt-i+1-xt-i),则连续n+1个检测时段内交通流量变化序列为VC=(sgn(xt-xt-1),sgn(xt-1-xt-2),…,sgn(xt-n+1-xt-i)),1表示流量增加,0表示流量不变,-1表示流量减少,n为交通变化序列长度.例如,长度为2的t时刻交通变化序列可能情况如图1所示.

图1 9种长度为2的t时刻交通变化序列

2.3 基于距离权重的预测算法

(4)

(5)

综上所述，路面交通检测信息按历史数据整理流程处理后存入数据库,初始化当前交通时刻为t,交通变化序列长度为n,近邻个数为K,预测t+1时刻交通流:

步骤1 计算交通变化序列Pt=(sgn(xt-xt-1),sgn(xt-1-xt-2),…,sgn(xt-n+1-xt-n));

步骤2 遍历历史数据库交通变化序列Pt,记与相同的历史交通状态个数为M,如果M

步骤4 计算t+1时刻交通状态

3 案例验证

3.1 误差说明

均方根误差RMSE是用来衡量观测值同真值之间的偏差,也称为标准误差,是观测值与真值偏差的平方和与观测次数n比值的平方根.假设真实值为(x1,x2,…,xn)、观测值(y1,y2,…,yn),则均方根误差计算公式如下:

(6)

3.2 数据说明

以广州市马场路—花城大道路口与马场路—金穗路路口之间南往北方向路段为例,数据来自路段上断面线圈检测数据,检测时间间隔5 min.根据2012年6月1日至7月30日线圈检测结果如图2所示,对2012年7月31日路段断面交通流量分别用WPRA[8]和DWPRA模型进行预测,用Matlab实现模型算法编程和数据处理,最终通过比较两种方法的RMSE说明文中算法的有效性.

图2 算例道路情况

3.3 结果分析

两种模型方法均对K取值2～20,对交通变化序列长度n取值3～5,最优预测结果的选取标准是对应RMSE最小.图3展示了不同K值情况下不同长度的交通变化序列对应的RMSE变化情况,最优的预测结果对应了一组最佳的K、n.图3所示的几组数据中最小RMSE对应K=10,n=5,图中当K=10、n=5时,没有相应的RMSE值,说明受历史数据库大小限制,长度为5拥有相同交通变化序列的历史状态个数不超过12个,无法进行满足要求的交通预测.

两种算法RMSE随K值变化的具体数据见表1.分析数据可知:两种方法RMSE随K值的变化趋势相同,当K=13时RMSE最小且DWPRA方法比WPRA方法的RMSE降低约5.75%;相同K值情况下,DWPRA方法所得RMSE值更小,RMSE减小约4.8%～7.1%.综合以上分析,当K取值范围相同时,DWPRA方法较WPRA方法预测结果更优.图4直观展示了7：00～19：00时两种算法预测结果和实际交通流量数据的对比.

图3 不同K值不同交通变化序列长度下的RMSE变化情况

表1 WPRA与SWPRA预测结果的RMSE对比

图4 交通流量预测结果

4 结语

文中通过分析基于数据驱动的非参数回归方法短时交通流预测原理,针对WPRA交通流短时预测模型权重系数的不确定性进行算法改进,建立了基于距离权重系数的DWPRA交通流短时预测模型,并通过实例数据计算证明DWPRA能得到更好的交通流短时预测结果.

虽然历史数据库数据量越大预测精度越高,但相应的DWPRA交通流短时预测速度越慢;数据检索方便、数据库容量小但数据变化特征丰富是提高预测精度和预测效率的保障;不同非参数回归交通流预测方法精度与近邻K值选取也有很大关系.因此,历史数据库存储结构优化、数据特征简化提取、快速确定最佳近邻值K,是DWPRA方法的改进研究方向.

[1] 傅贵,韩国强,逯峰,等.基于支持向量机回归的短时交通流预测模型 [J].华南理工大学学报:自然科学版,2013,41(9):71- 76. Fu Gui，Han Guo-qiang，Lu Feng，et al.Short-term traffic flow forecasting model based on support vector machine regression [J].Journal of South China University of Technology:Natural Science Edition,2013,41(9):71- 76.

[2] 李松,刘力军,翟曼.改进粒子群算法优化BP神经网络的短时交通流预测 [J].系统工程理论与实践,2012,32(9):2045- 2049. Li Song，Liu Li-jun，Zhai Man.Prediction for short-term traffic flow based on modified PSO optimized BP neural network [J].Systems Engineering —Theory & Practice,2012,32(9):2045- 2049

[3] 张涛,陈先,谢美萍,等.基于K近邻非参数回归的短时交通流预测方法 [J].系统工程理论与实践,2010,30(2):376- 384. Zhang Tao，Chen Xian，Xie Mei-ping，et al.K-NN based nonparametric regression method for short-term traffic flow forecasting [J].Systems Engineering —Theory & Practice,2010,30(2):376- 384.

[4] 张晓利,贺国光,陆化普.基于K-邻域非参数回归短时交通流预测方法 [J].系统工程学报,2009,24(2):178- 183. Zhang Xiao-li，He Guo-guang，Lu Hua-pu.Short-term traffic flow forecasting based on K-nearest neighbors non-pa-rametric regression [J].Journal of Systems Engineering,2009,24(2):178- 183.

[5] Davis Gary A，Nihan Nancy L.Nonparametric regression and short-term freeway traffic forecasting [J].Journal of Transportation Engineering,1991,117(2):178- 188.

[6] Smith B L，William B M，Oswald R K.Comparison of parametric and nonparametric models for traffic flow forecasting [J].Transportation Research Part C:Emerging Technologies,1997,123(4):261- 266.

[7] Kim T，Kim H，Lovell D J.Traffic flow forecasting:overcoming memoryless property in nearest neighbor non-parametric regression[C]∥Proceedings of 8th International IEEE Conference on Intelligent Transportation System.Vienna:IEEE,2005:965- 969

[8] Li Shuang-shuang.A weighted pattern recognition algorithm for short-term traffic flow forecasting[C]∥Proceedings of 9th International IEEE Conference on Networking，Sensing and Control.Beijing:[s.n.],2012:1- 6.

[9] 宫晓燕,汤淑明.基于非参数回归的短时交通流量预测与事件检测综合算法 [J].中国公路学报,2003,16(1):82- 86. Gong Xiao-yan，Tang Shu-ming.Integrated traffic flow forecasting and traffic incident detection algorithm based on non-parametric regression [J].China Journal of Highway and Transport,2003,16(1):82- 86.

[10] Sun S L，Yu G Q，Zhang C S.Short-term traffic flow forecasting using sampling Markov chain method with incomplete data [C]∥IEEE Intelligent Vehicles Symposium.Parma:IEEE,2004:437- 441.

A Distance-Based Weighted Pattern Recognition Algorithm for Traffic Flow Forecasting

LiuShu-qingXuJian-minLuKaiMaYing-ying

(School of Civil Engineering and Transportation,South China University of Technology,Guangzhou 510640,Guangdong,China)

In the short-term traffic flow forecasting based on the weighted traffic pattern recognition algorithm (WPRA),the weights of different historical state values are distinguished according to the time-interval characteristics of historical traffic patterns,but in practical application,the subjective setting of the weight values reduces the reliability of this method.In this paper,by analyzing the core principle of the data-driven non-parametric-regression traffic flow forecasting algorithm and by improving the forecasting algorithm aiming at the uncertainty of the time-interval-characteristic weights of WPRA,a distance-based weighted pattern recognition algorithm (DWPRA) is proposed to forecast the short-term traffic flow.Finally,the root mean square error between real traffic flows and predicted ones is introduced to verify the proposed algorithm.The results show that,at the same neighbor numberK,the root mean square error of DWPRA is 4.8%～7.1% lower than that of WPRA,which proves the effectiveness of DWPRA.

pattern recognition;short-term traffic flow forecasting;K-nearest neighbor search; distance weight;root mean square error

2014- 11- 24

国家自然科学基金资助项目(51308227,61174184);华南理工大学中央高校基本科研业务专项资金资助项目(2015ZM039);同济大学道路与交通工程教育部重点实验室开放基金资助项目(K201304) Foundation items: Supported by the National Natural Science Foundation of China(51308227,61174184)

刘树青(1987-),女,博士生,主要从事城市智能交通信息工程与控制研究.E-mail: toliusq@foxmail.com

1000- 565X(2015)12- 0114- 05

TP391

10.3969/j.issn.1000-565X.2015.12.016