|Table of Contents|

Improved K-nearest neighbor algorithm for short-term traffic flow forecasting(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2014年03期
Page:
87-94
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Improved K-nearest neighbor algorithm for short-term traffic flow forecasting
Author(s):
XIE Hai-hong1; 2;  DAI Xu-hao1;  QI Yuan3
1. MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China; 2. Center of Cooperative Innovation for Beijing Metropolitan Transportation, Beijing 100044, China; 3. Hunan Provincial Communications Planning, Survey and Design Institute, Changsha 410008, Hunan, China
Keywords:
traffic planning;  short-term traffic flow forecasting;  K-nearest neighbor algorithm;  pattern distance;  multiple statistical regression
PACS:
U491.112
DOI:
-
Abstract:
The original K-nearest neighbor algorithm for short-term traffic flow forecasting was analyzed. Pattern distance search method was used to replace the original Euclidean distance search method, the multiple statistics regression model was introduced, an improved K-nearest neighbor algorithm for short-term traffic flow forecasting was put forward, and an example verification was carried out by using the traffic flow data from a certain section in Beijing. Test result indicates when K is 23, the error of mean square, mean absolute error and average relative error of forecasting results are 31.43%, 4.17% and 0.27% respectively by using the improved K-nearest neighbor algorithm. By using the original K-nearest neighbor algorithm, the error of mean square, mean absolute error and average relative error of forecasting results are 33.33%, 4.40% and 0.28% respectively. By using the historical average model, the error of mean square, mean absolute error and average relative error of forecasting results are 46.20%, 11.40% and 0.48% respectively. The forecasting accuracy of the improvedK-nearest neighbor algorithm is obviously higher than the other two algorithms. The improved K-nearest neighbor algorithm not only increases searching efficiency, but also accurately reflects the real situation of traffic flow. 2 tabs, 11 figs, 22 refs.

References:

[1] 贺国光,李 宇,马寿峰.基于数学模型的短时交通流预测方法探讨[J].系统工程理论与实践,2000,20(12):51-56.HE Guo-guang, LI Yu, MA Shou-feng. Discussion on short-term traffic flow forecasting methods based on mathematical models[J]. Systems Engineering—Theory and Practice, 2000, 20(12): 51-56.(in Chinese)
[2] SMITH B L, DEMETSKY M J. Traffic flow forecasting: comparison of modeling approaches[J]. Journal of Transportation Engineering, 1997, 123(4): 261-266.
[3] KREER J B. A comparison of predictor algorithms for computerized control[J].Traffic Engineering, 1975, 45(4): 51-56.
[4] WILLIAMS B M, HOEL L A. Modeling and forecasting vehicular traffic flow as a seasonal ARIMA process: theoretical basis and empirical results[J]. Journal of Transportation Engineering, 2003, 129(6): 664-672.
[5] OKUTANI I, STEPHANEDES Y J. Dynamic prediction of traffic volume through Kalman filtering theory[J]. Transportation Research Part B: Methodological, 1984, 18(1): 1-11.
[6] SIMON D, SIMON D L. Kalman filtering with inequality constraints for turbofan engine health estimation[J]. Control Theory and Applications, 2006, 153(3): 371-378.
[7] 董春娇,邵春福,熊志华,等.基于Elman神经网络的道路网短时交通流预测方法[J].交通运输系统工程与信息,2010,10(1):145-151.DONG Chun-jiao, SHAO Chun-fu, XIONG Zhi-hua, et al. Short-term traffic flow forecasting of road network based on Elman neural net work[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(1): 145-151.(in Chinese)
[8] 魏 文,余立建,龚 炯.基于混沌理论和PSO神经网络的短时交通流预测[J].物流工程与管理,2010,32(2):75-77.WEI Wen, YU Li-jian, GONG Jiong. Short-time traffic flow prediction based on chaos and particle swarm optimized neural network[J]. Logistics Engineering and Management, 2010, 32(2): 75-77.(in Chinese)
[9] 承向军,刘 军,马敏书.基于分形理论的短时交通流预测算法[J].交通运输系统工程与信息,2010,10(4):106-110.CHENG Xiang-jun, LIU Jun, MA Min-shu. Algorithm of short-term traffic flow forecasting using fractal theory[J]. Journal of Transportation System Engineering and Information Technology, 2010, 10(4): 106-110.(in Chinese)
[10] 樊 娜,赵祥模,戴 明,等.短时交通流预测模型[J].交通运输工程学报,2012,12(4):114-119.FAN Na, ZHAO Xiang-mo, DAI Ming, et al. Short-term traffic flow prediction model[J]. Journal of Traffic and Transportation Engineering, 2012, 12(4): 114-119.(in Chinese)
[11] 林德花,袁振洲.基于IOWA算子的短时交通流预测方法研究[J].科学技术与工程,2013,13(25):7596-7600.LIN De-hua, YUAN Zhen-zhou. Research on short-term traffic flow forecasting method based on IOWA operator[J]. Science Technology and Engineering, 2013, 13(25):7596-7600.(in Chinese)
[12] ISHAK S, ALECSANDRU C. Optimizing traffic prediction performance of neural networks under various topological input and traffic condition setting[J]. Journal of Transportation Engineering, 2004, 130(7): 452-465.
[13] SMITH B L, WILLIAMS B M R, OSWALD K. Comparison of parametric and nonparametric models for traffic flow forecasting[J]. Transportation Research Part C: Emerging Technologies, 2002, 10(4): 303-321.
[14] 宫晓燕,汤淑明.基于非参数回归的短时交通流预测与事件检测综合算法[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.(in Chinese)
[15] 周小鹏,冯 奇,孙立军.基于最近邻法的短时交通流预测[J].同济大学学报:自然科学版,2006,34(10):1494-1498.ZHOU Xiao-peng, FENG Qi, SUN Li-jun. Short-term traffic flow forecasting based on nearest neighbor algorithm[J]. Journal of Tongji University: Natural Science, 2006, 34(10): 1494-1498.(in Chinese)
[16] 于 滨,邬珊华,王明华,等.K近邻短时交通流预测模型[J].交通运输工程学报,2012,12(2):105-111.YU Bin, WU Shan-hua, WANG Ming-hua, et al. K-nearest neighbor model of short-term traffic flow forecast[J]. Journal of Traffic and Transportation Engineering, 2012, 12(2): 105-111.(in Chinese)
[17] 屈 莉,兰时勇,张建伟.基于浮动车数据非参数回归短时交通速度预测[J].计算机工程与设计,2013,34(9):3298-3332.QU Li, LAN Shi-yong, ZHANG Jian-wei. Short-term traffic forecasting based on nonparametric regression and floating car data[J]. Computer Engineering and Design, 2013, 34(9): 3298-3332.(in Chinese)
[18] 李振龙,张利国,钱海峰.基于非参数回归的短时交通流预测研究综述[J].交通运输工程与信息学报,2008,6(4):34-39.LI Zhen-long, ZHANG Li-guo, QIAN Hai-feng. Review of the short-term traffic flow forecasting based on the non-parametric regression[J]. Journal of Transportation Engineering and Information, 2008, 6(4): 34-39.(in Chinese)
[19] 王 达,荣 冈.时间序列的模式距离[J].浙江大学学报:工学版,2004,38(7):795-798.WANG Da, RONG Gang. Pattern distance of time series[J]. Journal of Zhejiang University: Engineering Science, 2004, 38(7): 795-798.(in Chinese)
[20] 吴耿锋,周佩玲,储阅春,等.基于相空间重构的预测方法及其在天气预报中的应用[J].自然杂志,1999,21(2):107-110.WU Geng-feng, ZHOU Pei-ling, CHU Yue-chun, et al. Prediction based on phrase construction and its application in weather forecast[J]. Nature Magazine, 1999, 21(2): 107-110.(in Chinese)
[21] 朱 莉,吴建华,胡广书.基于Cao算法的心率变异信号分析[J].航天医学与医学工程,2009,22(2):132-134.ZHU Li, WU Jian-hua, HU Guang-shu. Analysis of heart rate variability signal based on Cao algorithm[J]. Space Medicine and Medical Engineering, 2009, 22(2): 132-134.(in Chinese)
[22] 陈德望,高海军,陈 龙,等.城市高速道路微波检测器RTMS的检测精度分析[J].公路交通科技,2002,19(5):122-124.CHEN De-wang, GAO Hai-jun, CHEN Long, et al. Accuracy analysis of RTMS on urban freeway[J]. Journal of Highway and Transportation Research and Development, 2002, 19(5): 122-124.(in Chinese)

Memo

Memo:
-
Last Update: 2014-06-30