短时交通流预测的改进<i>K</i>近邻算法

谢海红; 戴许昊; 齐远

短时交通流预测的改进K近邻算法

谢海红^{1, 2,},
戴许昊¹,
齐远³

1.
北京交通大学城市交通复杂系统理论与技术教育部重点实验室, 北京 100044
2.
北京城市交通协同创新中心, 北京 100044
3.
湖南省交通规划勘察设计院, 湖南长沙 410008

基金项目:

国家973计划项目 2012CB725403

详细信息

作者简介:
谢海红(1963-), 女, 山东烟台人, 北京交通大学副教授, 从事城市交通规划与管理研究

中图分类号: U491.112
计量
- 文章访问数: 625
- HTML全文浏览量: 52
- PDF下载量: 865
- 被引次数: 0
出版历程
- 收稿日期: 2014-01-13
- 刊出日期: 2014-06-25

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

摘要

摘要: 分析了原有的短时交通流预测的K近邻算法, 用模式距离搜索方法代替原有的欧氏距离搜索方法, 引入多元统计回归模型, 建立了一种改进的短时交通流预测的K近邻算法, 并以北京市某路段进行实例验证。试验结果表明: 当K取23时, 利用改进的K近邻算法, 预测结果的均方误差、平均相对误差、平均绝对误差分别为31.43%、4.17%、0.27%;利用原有的K近邻算法, 预测结果的均方误差、平均相对误差、平均绝对误差分别为33.33%、4.40%、0.28%;利用历史平均模型, 预测结果的均方误差、平均相对误差、平均绝对误差分别为46.20%、11.40%、0.48%。可见, 改进的K近邻算法的预测精度明显高于其他2种方法, 在提高搜索效率的同时准确地刻画了交通流的真实情况。
- 交通规划 /
- 短时交通流预测 /
- K近邻算法 /
- 模式距离 /
- 多元统计回归
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

HTML全文

图 1 算法流程

Figure 1. Algorithm flow

下载: 全尺寸图片幻灯片

图 2 多元统计回归算法流程

Figure 2. Flow of multiple statistical regression algorithm

下载: 全尺寸图片幻灯片

图 3 实测现场

Figure 3. Measurement field

下载: 全尺寸图片幻灯片

图 4 交通量

Figure 4. Traffic volumes

下载: 全尺寸图片幻灯片

图 5 ξ与K关系

Figure 5. Relationship between ξ and K

下载: 全尺寸图片幻灯片

图 6 T_m曲线

Figure 6. T_m curve

下载: 全尺寸图片幻灯片

图 7 欧氏距离搜索结果

Figure 7. Search result by using Euclidean distance

下载: 全尺寸图片幻灯片

图 8 模式距离搜索结果

Figure 8. Search result by using pattern distance

下载: 全尺寸图片幻灯片

图 9 均方误差

Figure 9. Errors of mean square

下载: 全尺寸图片幻灯片

图 10 平均绝对误差

Figure 10. Mean absolute errors

下载: 全尺寸图片幻灯片

图 11 平均相对误差

Figure 11. Average relative errors

下载: 全尺寸图片幻灯片

表 1 欧氏距离与模式距离搜索结果

Table 1. Search results with Euclidean distance and pattern distance

下载: 导出CSV

表 2 因子排序结果

Table 2. Factor order result

下载: 导出CSV

参考文献(22)

[1]	贺国光, 李宇, 马寿峰. 基于数学模型的短时交通流预测方法探讨[J]. 系统工程理论与实践, 2000, 20 (12): 51-56. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200012007.htm 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]	董春娇, 邵春福, 熊志华, 等. 基于Elman神经网络的道路网短时交通流预测方法[J]. 交通运输系统工程与信息, 2010, 10 (1): 145-151. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201001022.htm 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]	魏文, 余立建, 龚炯. 基于混沌理论和PSO神经网络的短时交通流预测[J]. 物流工程与管理, 2010, 32 (2): 75-77. https://www.cnki.com.cn/Article/CJFDTOTAL-SPCY201002031.htm 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]	承向军, 刘军, 马敏书. 基于分形理论的短时交通流预测算法[J]. 交通运输系统工程与信息, 2010, 10 (4): 106-110. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201004017.htm 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]	樊娜, 赵祥模, 戴明, 等. 短时交通流预测模型[J]. 交通运输工程学报, 2012, 12 (4): 114-119. http://transport.chd.edu.cn/article/id/201204015 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]	林德花, 袁振洲. 基于IOWA算子的短时交通流预测方法研究[J]. 科学技术与工程, 2013, 13 (25): 7596-7600. https://www.cnki.com.cn/Article/CJFDTOTAL-KXJS201325063.htm 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]	宫晓燕, 汤淑明. 基于非参数回归的短时交通流预测与事件检测综合算法[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. https://www.cnki.com.cn/Article/CJFDTOTAL-TJDZ200611014.htm 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]	于滨, 邬珊华, 王明华, 等. K近邻短时交通流预测模型[J]. 交通运输工程学报, 2012, 12 (2): 105-111. http://transport.chd.edu.cn/article/id/201202015 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]	屈莉, 兰时勇, 张建伟. 基于浮动车数据非参数回归短时交通速度预测[J]. 计算机工程与设计, 2013, 34 (9): 3298-3332. https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ201309059.htm 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]	李振龙, 张利国, 钱海峰. 基于非参数回归的短时交通流预测研究综述[J]. 交通运输工程与信息学报, 2008, 6 (4): 34-39. https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC200804009.htm 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]	王达, 荣冈. 时间序列的模式距离[J]. 浙江大学学报: 工学版, 2004, 38 (7): 795-798. https://www.cnki.com.cn/Article/CJFDTOTAL-ZDZC200407001.htm 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]	吴耿锋, 周佩玲, 储阅春, 等. 基于相空间重构的预测方法及其在天气预报中的应用[J]. 自然杂志, 1999, 21 (2): 107-110. https://www.cnki.com.cn/Article/CJFDTOTAL-ZRZZ199902011.htm 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]	朱莉, 吴建华, 胡广书. 基于Cao算法的心率变异信号分析[J]. 航天医学与医学工程, 2009, 22 (2): 132-134. https://www.cnki.com.cn/Article/CJFDTOTAL-HYXB200902013.htm 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]	陈德望, 高海军, 陈龙, 等. 城市高速道路微波检测器RTMS的检测精度分析[J]. 公路交通科技, 2002, 19 (5): 122-124. https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK200205034.htm 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