Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31106
Comparison of Different k-NN Models for Speed Prediction in an Urban Traffic Network

Authors: Seyoung Kim, Jeongmin Kim, Kwang Ryel Ryu


A database that records average traffic speeds measured at five-minute intervals for all the links in the traffic network of a metropolitan city. While learning from this data the models that can predict future traffic speed would be beneficial for the applications such as the car navigation system, building predictive models for every link becomes a nontrivial job if the number of links in a given network is huge. An advantage of adopting k-nearest neighbor (k-NN) as predictive models is that it does not require any explicit model building. Instead, k-NN takes a long time to make a prediction because it needs to search for the k-nearest neighbors in the database at prediction time. In this paper, we investigate how much we can speed up k-NN in making traffic speed predictions by reducing the amount of data to be searched for without a significant sacrifice of prediction accuracy. The rationale behind this is that we had a better look at only the recent data because the traffic patterns not only repeat daily or weekly but also change over time. In our experiments, we build several different k-NN models employing different sets of features which are the current and past traffic speeds of the target link and the neighbor links in its up/down-stream. The performances of these models are compared by measuring the average prediction accuracy and the average time taken to make a prediction using various amounts of data.

Keywords: Machine Learning, Big Data, k-NN, traffic speed prediction

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 746


[1] X. Zhang and J. A. Rice, “Short-Term Travel Time Prediction Using A time-Varying Coefficient Linear Model,” Transp. Res. C, vol. 11, no. 3, pp. 187-210, 2003.
[2] L. Vanajakshi and L. R. Rilett, “A comparison of the performance of artificial neural networks and support vector machines for the prediction of traffic speed,” in Intelligent Vehicles Symposium, 2004 IEEE, 2004, pp. 194-199.
[3] M. A. Rasyidi, J. Kim, and K. R. Ryu, “Short-term Prediction of Vehicle Speed on Main City Roads using the k-Nearest Neighbor Algorithm,” J. Intell. Inf. Syst., vol. 20, no. 1, pp. 121-131, 2014.
[4] M. A. Rasyidi, and K. R. Ryu, “Short-Term Speed Prediction on Urban Highways by Ensemble Learning with Feature Subset Selection,” Database Systems for Advanced Applications, Springer Berlin Heidelberg, 2014, pp. 46-60.
[5] H. Sun, H. X. Liu, H. Xiao, and B. Ran, “Short Term Traffic Forecasting Using the Local Linear Regression Model,” UC Irvine Cent. Traffic Simul. Stud., 2002
[6] S. J. Russell, and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd ed, Pearson Education, 2010.
[7] R. Kohavi, and G. H. John, “Wrappers for feature subset selection,” Artificial intelligence, vol. 97, no. 1, 1997, pp. 273-324.
[8] G. H. John, R. Kohavi, and K. Pfleger, “Irrelevant features and the subset selection problem,” Machine Learning: Proceedings of the Eleventh International Conference, 1994, pp. 121-129.
[9] M. A. Hall, Correlation-based Feature Selection for Machine Learning, Doctoral dissertation, The University of Waikato, 1999.
[10] M. A. Rasyidi, and K. R. Ryu, “Comparison of Traffic Speed and Travel Time Predictions on Urban Traffic Network,” Computer Systems and Applications (AICCSA), 2014 IEEE/ACS 11th International conference on. IEEE, 2014, pp. 373-380.