Improved <i>K</i>-nearest neighbor algorithm for short-term traffic flow forecasting

XIE Hai-hong; DAI Xu-hao; QI Yuan

Volume 14 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2014 > 14(3): 87-94

Next Previous

XIE Hai-hong, DAI Xu-hao, QI Yuan. Improved K-nearest neighbor algorithm for short-term traffic flow forecasting[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 87-94.

Citation:

XIE Hai-hong, DAI Xu-hao, QI Yuan. Improved K-nearest neighbor algorithm for short-term traffic flow forecasting[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 87-94.

XIE Hai-hong, DAI Xu-hao, QI Yuan. Improved K-nearest neighbor algorithm for short-term traffic flow forecasting[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 87-94.

Citation:

XIE Hai-hong, DAI Xu-hao, QI Yuan. Improved K-nearest neighbor algorithm for short-term traffic flow forecasting[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 87-94.

PDF( 569 KB)

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

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

More Information

Author Bio:
XIE Hai-hong (1963-), female, associate professor, +86-10-51687138, xiehaihong16@163.com
Received Date: 2014-01-13
Publish Date: 2014-06-25

Abstract

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 Kis 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 improved K-nearest neighbor algorithm is obviously higher than the other two algorithms.The improved K-nearest neighbor algorithm notonly increases searching efficiency, but also accurately reflects the real situation of traffic flow.
- traffic planning,
- short-term traffic flow forecasting,
- K-nearest neighbor algorithm,
- pattern distance,
- multiple statistical regression

FullText(HTML)

References(22)

References

[1]	HE Guo-guang, LI Yu, MA Shou-feng. Discussion on shortterm traffic flow forecasting methods based on mathematical models[J]. Systems Engineering—Theory and Practice, 2000, 20 (12): 51-56. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200012007.htm
[2]	SMITH B L, DEMETSKY M J. Traffic flow forecasting: comparison of modeling approaches[J]. Journal of Transportation Engineering, 1997, 123 (4): 261-266. doi: 10.1061/(ASCE)0733-947X(1997)123:4(261)
[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. doi: 10.1061/(ASCE)0733-947X(2003)129:6(664)
[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. doi: 10.1016/0191-2615(84)90002-X
[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. doi: 10.1049/ip-cta:20050074
[7]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201001022.htm
[8]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-SPCY201002031.htm
[9]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201004017.htm
[10]	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). http://transport.chd.edu.cn/article/id/201204015
[11]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-KXJS201325063.htm
[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]	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]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-TJDZ200611014.htm
[16]	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). http://transport.chd.edu.cn/article/id/201202015
[17]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ201309059.htm
[18]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC200804009.htm
[19]	WANG Da, RONG Gang. Pattern distance of time series[J]. Journal of Zhejiang University: Engineering Science, 2004, 38 (7): 795-798. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZDZC200407001.htm
[20]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-ZRZZ199902011.htm
[21]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-HYXB200902013.htm
[22]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK200205034.htm