基于自适应时序剖分与KNN的短时交通流量预测

doi:10.12082/dqxxkx.2022.210392

地球信息科学学报 ›› 2022, Vol. 24 ›› Issue (2): 339-351.doi: 10.12082/dqxxkx.2022.210392

• 地球信息科学理论与方法 • 上一篇下一篇

基于自适应时序剖分与KNN的短时交通流量预测

祁朵¹(), 毛政元¹^,²^,^*()

1.福州大学数字中国研究院（福建）,福州 350108
2.福州大学空间数据挖掘与信息共享教育部重点实验室,福州 350108

收稿日期:2021-07-14 修回日期:2021-07-30 出版日期:2022-02-25 发布日期:2022-04-25
通讯作者: *毛政元（1964— ）,男,湖南武冈人,教授,博士生导师,主要从事城市变化检测、时空数据分析等研究。 E-mail: zymao@fzu.edu.cn
作者简介:祁朵（1995— ）,男,安徽阜阳人,硕士生,主要从事智能算法、交通流预测等研究。 E-mail: qiduo1996@163.com
基金资助:
国家自然科学基金项目(41471333);福建省自然科学基金面上项目(2018J01619)

Short-term Traffic Flow Prediction based on Adaptive Time Slice and KNN

QI Duo¹(), MAO Zhengyuan¹^,²^,^*()

1. Academy of Digital China, Fuzhou University, Fuzhou 350108, China
2. Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350108, China

Received:2021-07-14 Revised:2021-07-30 Online:2022-02-25 Published:2022-04-25
Contact: MAO Zhengyuan
Supported by:
National Natural Science Foundation of China(41471333);Project of Science and Technology of Fujian Province(2018J01619)

摘要/Abstract

摘要：

在智能交通系统中,准确和高效的短时交通流量预测是交通诱导、管理和控制的前提。由于交通流量动态变化中表现出的时变性和非平稳性特征,其预测难度较大,是交通领域中亟待解决的难题。为提高短时交通流量的预测精度,本文设计与实现了基于自适应时序剖分与KNN（A-TS-KNN）的短时交通流量预测算法。① 基于动态时间规整（Dynamic Time Warping,DTW）动态剖分单日时序为不同的交通模式;② 在不同交通模式,采用互信息法求解每个预测时刻时间延迟的最大阈值,构造不同时间延迟的状态向量,生成交通流量历史数据库;③ 采用十次十折交叉验证的方法求解每个时刻不同时间延迟与不同K值的正交误差结果分布,提取误差最小的正交结果,得到自适应时间延迟与K值的参数组合;④ 采用K个最相似的近邻的距离倒数加权值作为预测结果。对比K近邻（K-nearest neighbors, KNN）、支持向量回归（Support vector regression,SVR）、长短期记忆神经网络（Long-short term memory neural network,LSTM）以及门控递归单元神经网络（Gate recurrent unit neural network,GRU）共4种主流预测模型,A-TS-KNN算法预测精度显著提升;将A-TS-KNN算法用于福州市城市路网中其他交叉路口的短时交通流量预测,结果表现出良好的泛化能力。

关键词: 短时交通流量预测, DTW, KNN, 自适应时序剖分, 互信息法, 交叉验证, 自适应时间延迟与K值

Abstract:

Short-term traffic flow prediction with high accuracy and efficiency plays an important role in Intelligent Transportation Systems, which is a prerequisite for traffic guidance, management, and control. Due to the time-varying and non-stationary characteristics of the dynamic change of traffic flow, it is difficult to predict traffic flow with high accuracy, which needs to be resolved urgently in the transportation field. In order to improve the accuracy and efficiency of short-term traffic flow prediction, the paper develops a short-term traffic flow predicting algorithm based on adaptive time slice and the improved KNN model (A-TS-KNN), which is then implemented successfully in short-term traffic flow predicting experiments. In the first, the Dynamic Time Warping (DTW) algorithm is used to dynamically slice the daytime sequence of traffic flow into different traffic patterns. Secondly, the mutual information method is used to solve the maximum threshold of the time delays of traffic flow at each time in different traffic patterns. Then the traffic flow state vectors of different time delays is constructed, which generates a history database of traffic flow. Thirdly, the method of ten times ten-fold cross-validation is used to solve the orthogonal error distribution of different time delays and K values of traffic flow at each time. The orthogonal result with the smallest error is selected, and the parameters combination of adaptive time delay and K value are obtained. In the end, the weighted value of the reciprocal Euclidean distance of the K most similar neighbors is used for predicting traffic flow of next time. The forecasting accuracies of the improved A-TS-KNN and other four models including K-Nearest Neighbors (KNN) model, Support Vector Regression (SVR) model, Long-Short Term Memory (LSTM) neural networks, and Gate Recurrent Unit (GRU) neural networks are compared. The experimental results indicate that the improved A-TS-KNN model is more appropriate for short-term traffic flow forecasting than the other models. In addition, the A-TS-KNN algorithm is used for short-term traffic flow predicting at other four different intersections in the urban road network of Fuzhou, which has been shown good generalization ability.

Key words: short-term traffic flow prediction, DTW, KNN, adaptive time slice, mutual information method, cross validation, adaptive time delay and K value

祁朵, 毛政元. 基于自适应时序剖分与KNN的短时交通流量预测[J]. 地球信息科学学报, 2022, 24(2): 339-351.DOI:10.12082/dqxxkx.2022.210392

QI Duo, MAO Zhengyuan. Short-term Traffic Flow Prediction based on Adaptive Time Slice and KNN[J]. Journal of Geo-information Science, 2022, 24(2): 339-351.DOI:10.12082/dqxxkx.2022.210392

图/表 17

图1

算法1 基于DTW的单日交通模式动态剖分算法
输入：日交通流量序列 $F ← f i n$ ,模板交通流量序列 $D ← d n$ ,时间延迟参数 $M ← r, l$
输出：日交通流量模式区间分隔点 $P ← p n - 1$ $FunctionSEG_TRAFFIC_MODEL (F, D, M)$
Step 1 $for d n inD :$
Step 2 $for f i n inF :$
$forrinM :$
$forlinM :$
Step 2.1 //计算测试序列与模板序列间DTW
$cal culateDTW (F i n, d n)$
Step 2.2 //获取DTW相似度最小值对应时间序列
$get ind ex_of_Min (f i n)$
Step 2.3 //获取该序列交通模式起始和结束时刻
$get p i, p i + 1$

图2

图3

表1

图4

图5

图6

图7

图8

图9

表2

图10

图11

图12

图13

图14

参考文献 19

[1]	Li W, Wang J X, Fan R, et al. Short-term traffic state prediction from latent structures: Accuracy vs. efficiency[J]. Transportation Research Part C: Emerging Technologies, 2020, 111:72-90. DOI: 10.1016/j.trc.2019.12.007 doi: 10.1016/j.trc.2019.12.007
[2]	Coogan S, Flores C, Varaiya P. Traffic predictive control from low-rank structure[J]. Transportation Research Part B: Methodological, 2017, 97:1-22. DOI: 10.1016/j.trb.2016.11.013 doi: 10.1016/j.trb.2016.11.013
[3]	Wu S S, Wang Z Y, Du Z H, et al. Geographically and temporally neural network weighted regression for modeling spatiotemporal non-stationary relationships[J]. International Journal of Geographical Information Science, 2021, 35(3):582-608. DOI: 10.1080/13658816.2020.1775836 doi: 10.1080/13658816.2020.1775836
[4]	Cai P L, Wang Y P, Lu G Q, et al. A spatiotemporal correlative k-nearest neighbor model for short-term traffic multistep forecasting[J]. Transportation Research Part C: Emerging Technologies, 2016, 62:21-34. DOI: 10.1016/j.trc.2015.11.002 doi: 10.1016/j.trc.2015.11.002
[5]	Toshniwal D, Chaturvedi N, Parida M, et al. Application of clustering algorithms for spatio-temporal analysis of urban traffic data[J]. Transportation Research Procedia, 2020, 48:1046-1059. DOI: 10.1016/j.trpro.2020.08.132 doi: 10.1016/j.trpro.2020.08.132
[6]	Deng M, Yang W T, Liu Q L, et al. Heterogeneous space-time artificial neural networks for space-time series prediction[J]. Transactions in GIS, 2018, 22(1):183-201. DOI: 10.1111/tgis.12302 doi: 10.1111/tgis.12302
[7]	梁艳平, 毛政元, 邹为彬, 等. 基于相似数据聚合与变K值KNN的短时交通流量预测[J]. 地球信息科学学报, 2018, 20(10):1403-1411. doi: 10.12082/dqxxkx.2018.180281
	[ Liang Y P, Mao Z Y, Zou W B, et al. Short-term traffic flow prediction based on similar data aggregation and KNN with varying K-value[J]. Journal of Geo-Information Science, 2018, 20(10):1403-1411. ] DOI: 10.12082/dqxxkx.2018.180281 doi: 10.12082/dqxxkx.2018.180281
[8]	姚卫红, 方仁孝, 张旭东. 基于混合人工鱼群优化SVR的交通流量预测[J]. 大连理工大学学报, 2015, 55(6):632-637.
	[ Yao W H, Fang R X, Zhang X D. Traffic flow forecasting based on optimized SVR with hybrid artificial fish swarm algorithm[J]. Journal of Dalian University of Technology, 2015, 55(6):632-637. ] DOI: 10.7511/dllgxb201506011 doi: 10.7511/dllgxb201506011
[9]	Yu H Y, Wu Z H, Wang S Q, et al. Spatiotemporal recurrent convolutional networks for traffic prediction in transportation networks[J]. Sensors (Basel, Switzerland), 2017, 17(7):1501. DOI: 10.3390/s17071501 doi: 10.3390/s17071501
[10]	李明晓, 张恒才, 仇培元, 等. 一种基于模糊长短期神经网络的移动对象轨迹预测算法[J]. 测绘学报, 2018, 47(12):1660-1669.
	[ Li M X, Zhang H C, Qiu P Y, et al. Predicting future locations with deep fuzzy-LSTM network[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(12):1660-1669. ] DOI: CNKI:SUN:CHXB.0.2018-12-012 doi: CNKI:SUN:CHXB.0.2018-12-012
[11]	Davis G A, Nihan N L. Nonparametric regression and short-term freeway traffic forecasting[J]. Journal of Transportation Engineering, 1991, 117(2):178-188. DOI: 10.1061/(ASCE)0733-947X(1991)117:2(178) doi: 10.1061/(ASCE)0733-947X(1991)117:2(178
[12]	Yu B, Song X L, Guan F, et al. K-nearest neighbor model for multiple-time-step prediction of short-term traffic condition[J]. Journal of Transportation Engineering, 2016, 142(6):04016018. DOI: 10.1061/(ASCE)TE.1943-5436.0000816 doi: 10.1061/(ASCE)TE.1943-5436.0000816
[13]	Ryu U, Wang J A, Kim T, et al. Construction of traffic state vector using mutual information for short-term traffic flow prediction[J]. Transportation Research Part C: Emerging Technologies, 2018, 96:55-71. DOI: 10.1016/j.trc.2018.09.015 doi: 10.1016/j.trc.2018.09.015
[14]	Cheng S F, Lu F, Peng P. Short-term traffic forecasting by mining the non-stationarity of spatiotemporal patterns[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 99:1-19. DOI: 10.1109/tits.2020.2991781 doi: 10.1109/tits.2020.2991781
[15]	Cheng S F, Lu F, Peng P, et al. A spatiotemporal multi-view-based learning method for short-term traffic forecasting[J]. ISPRS International Journal of Geo-information, 2018, 7(6):218. DOI: 10.3390/ijgi7060218 doi: 10.3390/ijgi7060218
[16]	Stathopoulos A, Karlaftis M G. A multivariate state space approach for urban traffic flow modeling and prediction[J]. Transportation Research Part C, 2003, 11(2):121-135. DOI: 10.1016/S0968-090X(03)00004-4 doi: 10.1016/S0968-090X(03)00004-4
[17]	Rakthanmanon T, Campana B, Mueen A, et al. Searching and mining trillions of time series subsequences under dynamic time warping[J]. KDD: Proceedings International Conference on Knowledge Discovery & Data Mining, 2012, 2012:262-270. DOI: 10.1145/2339530.2339576 doi: 10.1145/2339530.2339576
[18]	Chalapathy R, Chawla S. Deep learning for anomaly detection: A Survey[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019.
[19]	Cheng S F, Lu F, Peng P, et al. Short-term traffic forecasting: An adaptive ST-KNN model that considers spatial heterogeneity[J]. Computers, Environment and Urban Systems, 2018, 71:186-198. DOI: 10.1016/j.compenvurbsys.2018.05.009 doi: 10.1016/j.compenvurbsys.2018.05.009

模式名称	模式类型	模式时间区间
a	缓慢下降模式	[00:00, 03:00)
b	畅通平稳模式	[03:00, 06:00)
c	迅速增长模式	[06:00, 07:30)
d	早高峰模式	[07:30, 11:00)
e	次高峰模式	[11:00, 13:00)
f	平稳下降模式	[13:00, 14:00)
g	平稳增长模式	[14:00, 17:00)
h	晚高峰模式	[17:00, 19:20)
i	畅通平稳模式	[19:20, 21:40)
j	畅通稳降模式	[21:40, 23:59)

算法	MAE	RMSE	MAPE/%	EC
KNN	24.70	33.75	10.97	0.88
AK-KNN	19.88	29.63	8.88	0.89
AD-KNN	18.10	26.31	8.00	0.91
TS-KNN	13.12	20.62	5.85	0.93
A-TS-KNN	12.69	20.21	5.52	0.94

基于自适应时序剖分与KNN的短时交通流量预测

Short-term Traffic Flow Prediction based on Adaptive Time Slice and KNN

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 19

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	李雨欣, 王瑛, 马庆媛, 刘天雪, 司丽丽, 俞海洋. 基于DTW与K-means算法的河北场雨及雨型分区特征研究[J]. 地球信息科学学报, 2021, 23(5): 860-868.
[2]	梁艳平, 毛政元, 邹为彬, 许锐. 基于相似数据聚合与变K值KNN的短时交通流量预测[J]. 地球信息科学学报, 2018, 20(10): 1403-1411.
[3]	王景云, 杨军, 杨俊兴, 雷梅, 万小铭, 周小勇, 陈同斌, 张红日, 赵相伟. 基于空间自相关和概率论的土壤重金属异常值的识别方法[J]. 地球信息科学学报, 2017, 19(5): 605-612.
[4]	苏巧梅, 赵尚民, 郭建立. 霍西煤矿区地表滑坡灾害敏感性数值建模与等级划分[J]. 地球信息科学学报, 2017, 19(12): 1613-1622.
[5]	仇培元, 张恒才, 陆锋. 互联网文本蕴含道路交通信息抽取的模式匹配方法[J]. 地球信息科学学报, 2015, 17(4): 416-422.
[6]	宋敦江, 岳天祥, 龚云, 杜正平. 散乱数据插值的HASM方法[J]. 地球信息科学学报, 2007, 9(3): 45-51.
[7]	徐新良, 曹明奎. 森林生物量遥感估算与应用分析[J]. 地球信息科学学报, 2006, 8(4): 122-128.