access icon free Short-term traffic forecasting using self-adjusting k-nearest neighbours

Short-term traffic forecasting is becoming more important in intelligent transportation systems. The k-nearest neighbour (kNN) method is widely used for short-term traffic forecasting. However, the self-adjustment of kNN parameters has been a problem due to dynamic traffic characteristics. This study proposes a fully automatic dynamic procedure kNN (DP-kNN) that makes the kNN parameters self-adjustable and robust without predefined models or training for the parameters. A real-world dataset with more than one year traffic records is used to conduct experiments. The results show that the DP-kNN can perform better than the manually adjusted kNN and other benchmarking methods in terms of accuracy on average. This study also discusses the difference between holiday and workday traffic prediction as well as the usage of neighbour distance measurement.

Inspec keywords: intelligent transportation systems; road traffic; learning (artificial intelligence)

Other keywords: intelligent transportation systems; short-term traffic forecasting; road traffic; DP-kNN; dynamic procedure kNN; self-adjusting k-nearest neighbours

Subjects: Traffic engineering computing; Knowledge engineering techniques

References

    1. 1)
      • 13. Vlahogianni, E.I., Karlaftis, M.G., Golias, J.C.: ‘Short-term traffic forecasting: where we are and where we're going’, Transp. Res. C, Emerg. Technol., 2014, 43, (1), pp. 319.
    2. 2)
      • 52. Kehagias, D., Salamanis, A., Tzovaras, D.: ‘Speed pattern recognition technique for short-term traffic forecasting based on traffic dynamics’, IET Intell. Transp. Syst., 2015, 9, (6), pp. 646653.
    3. 3)
      • 4. Guo, J., Huang, W., Williams, B.M.: ‘Real time traffic flow outlier detection using short-term traffic conditional variance prediction’, Transp. Res. C, Emerg. Technol., 2015, 50, pp. 160172.
    4. 4)
      • 22. Byon, Y.-J., Liang, S.: ‘Real-time transportation mode detection using smartphones and artificial neural networks: performance comparisons between smartphones and conventional global positioning system sensors’, J. Intell. Transp. Syst., 2014, 18, (3), pp. 264272.
    5. 5)
      • 50. Smith, B.L., Oswald, R.K.: ‘Meeting real–time traffic flow forecasting requirements with imprecise computations’, Comput.-Aided Civ. Infrastruct. Eng., 2003, 18, (3), p. 5.
    6. 6)
      • 43. Sun, B., Cheng, W., Goswami, P., et al: ‘Flow-aware WPT k-nearest neighbours regression for short-term traffic prediction’. Proc. IEEE Symp. on Computers and Communication (ISCC), Heraklion, Greece, July 2017, pp. 4853.
    7. 7)
      • 29. Bajwa, S., Chung, E., Kuwahara, M.: ‘Performance evaluation of an adaptive travel time prediction model’. Proc. IEEE Intelligent Transportation Systems, Vienna, Austria, September 2005, pp. 10001005.
    8. 8)
      • 10. Bhatia, N., Ashev, V.: ‘Survey of nearest neighbor techniques’, Int. J. Comput. Sci. Inf. Sec., 2010, 8, (2), pp. 302305.
    9. 9)
      • 42. Everitt, B.: ‘Euclidean distance’, in Everitt, B. S., Skrondal, A. (Eds.): ‘The cambridge dictionary of statistics’ (Cambridge University Press, Cambridge, 2002), p. 134.
    10. 10)
      • 24. Zheng, W.Z., Lee, D.H., Shi, Q.X.: ‘Short-term freeway traffic flow prediction: Bayesian combined neural network approach’, J. Transp. Eng., 2006, 132, (2), pp. 114121.
    11. 11)
      • 7. Davis, G.A., Nihan, N.L.: ‘Nonparametric regression and short-term freeway traffic forecasting’, J. Transp. Eng., 1991, 117, (2), pp. 178188.
    12. 12)
      • 40. Chang, H., Lee, Y., Yoon, B., et al: ‘Dynamic near-term traffic flow prediction: system-oriented approach based on past experiences’, IET Intell. Transp. Syst., 2012, 6, (3), pp. 292305.
    13. 13)
      • 53. Garcia, V., Debreuve, E., Barlaud, M.: ‘Fast k nearest neighbor search using GPU’. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition Workshops CVPRW, Anchorage, AK, June 2008, pp. 16.
    14. 14)
      • 49. Filzmoser, P., Garrett, R.G., Reimann, C.: ‘Multivariate outlier detection in exploration geochemistry’, Comput. Geosci., 2005, 31, (5), pp. 579587.
    15. 15)
      • 41. Kim, T., Kim, H., Lovell, D.J.: ‘Traffic flow forecasting: overcoming memoryless property in nearest neighbor non-parametric regression’. 8th IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), Vienna, Austria, September 2005, pp. 965969.
    16. 16)
      • 3. Clark, S.: ‘Traffic prediction using multivariate nonparametric regression’, J. Transp. Eng., 2003, 129, (2), pp. 161168.
    17. 17)
      • 23. Vlahogianni, E.I., Karlaftis, M.G., Golias, J.C.: ‘Optimized and meta-optimized neural networks for short-term traffic flow prediction: a genetic approach’, Transp. Res. C, Emerg. Technol., 2005, 13, (3), pp. 211234.
    18. 18)
      • 45. Qi, Y., Smith, B.L.: ‘Identifying nearest neighbors in a large-scale incident data archive’, Transp. Res. Rec., 2004, 1879, (1), pp. 8998.
    19. 19)
      • 8. Castro-Neto, M., Han, L.D., Jeong, Y., et al: ‘Toward training-Free automatic detection of freeway incidents simple algorithm with one parameter’, Transp. Res. Rec., 2012, 2278, (1), pp. 4249.
    20. 20)
      • 56. Sun, B., Ma, L., Cheng, W., et al: ‘An improved k-nearest neighbours method for traffic time series imputation’. Chinese Automation Congress (CAC), Jinan, China, October 2017.
    21. 21)
      • 11. Sun, B., Cheng, W., Goswami, P., et al: ‘An overview of parameter and data strategies for k-nearest neighbours based short-term traffic prediction’. Int. Conf. on Intelligent Traffic and Transportation (ICITT), Zurich, Switzerland, September 2017.
    22. 22)
      • 28. Ohba, Y., Ueno, H., Kuwahara, M.: ‘Travel time calculation method for expressway using toll collection system data’. Proc. IEEE/IEEJ/JSAI Int. Conf. on Intelligent Transportation Systems, Tokyo, Japan, 1999, pp. 471475.
    23. 23)
      • 54. Nvidia: ‘CUDA programming guide 8.0’ (Nvidia Ltd, 2016).
    24. 24)
      • 21. Boto-Giralda, D., Diaz-Pernas, F.J., Gonzalez-Ortega, D., et al: ‘Wavelet-based denoising for traffic volume time series forecasting with self-organizing neural networks’, Comput.-Aided Civ. Infrastruct. Eng., 2010, 25, (7), pp. 530545.
    25. 25)
      • 39. Packard, N.H., Crutchfield, J.P., Farmer, J.D., et al: ‘Geometry from a time series’, Phys. Rev. Lett., 1980, 45, (9), pp. 712716.
    26. 26)
      • 38. Takens, F.: ‘Detecting strange attractors in turbulence’. ‘Dynamical Systems and Turbulence: Proc. of a Symposium Held at the University of Warwick’Warwick, 1981, pp. 366381.
    27. 27)
      • 31. Ling, P., Gao, D., Zhou, X., et al: ‘Improve the diagnosis of atrial hypertrophy with the local discriminative support vector machine’, Bio-Med. Mater. Eng., 2015, 26, pp. 18131820.
    28. 28)
      • 14. Hyndman, R.J., Athanasopoulos, G.: ‘Seasonal ARIMA models’, in Hyndman, R. J. (Ed): ‘Forecasting: principles and practice’ (oTexts, 2015).
    29. 29)
      • 6. Oh, S., Byon, Y.-J., Jang, K., et al: ‘Short-term travel-time prediction on highway: a review of the data-driven approach’, Transp. Rev., 2015, 35, (1), pp. 432.
    30. 30)
      • 35. Singh, H., Desai, A., Pudi, V.: ‘PAGER: parameter less, accurate, generic, efficient kNN-based regression’. inBringas, P.G., Hameurlain, A., Quirchmayr, G., et al (Eds): ‘Database and expert systems applications, Pt 2’ (Springer-Verlag, Berlin, 2010), pp. 168176.
    31. 31)
      • 48. De Maesschalck, R., Jouan-Rimbaud, D., Massart, D.L.: ‘The mahalanobis distance’, Chemometr. Intell. Lab. Syst., 2000, 50, (1), pp. 118.
    32. 32)
      • 1. An, S., Zhang, T., Zhang, X., et al: ‘Unrecorded accidents detection on highways based on temporal data mining’, Math. Probl. Eng., 2014, 852, (495), pp. 17.
    33. 33)
      • 51. Sun, B., Cheng, W., Bai, G., et al: ‘Correcting and complementing freeway traffic accident data using mahalanobis distance based outlier detection’, Teh. Vjesn., 2017, 24, (5), pp. 111.
    34. 34)
      • 27. Kohn, R., Smith, M., Chan, D.: ‘Nonparametric regression using linear combinations of basis functions’, Stat. Comput., 2001, 11, (4), pp. 313322.
    35. 35)
      • 37. Dubey, H., Pudi, V.: ‘CLUEKR: CLUstering based efficient kNN regression’. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, Gold Coast, Australia, April 2013, pp. 450458.
    36. 36)
      • 44. Innamaa, S.: ‘Self-adapting traffic flow status forecasts using clustering’, IET Intell. Transp. Syst., 2009, 3, (1), pp. 6776.
    37. 37)
      • 33. Zhang, X., Song, Q.: ‘Predicting the number of nearest neighbors for the k-NN classification algorithm’, Intell. Data Anal., 2014, 18, (3), pp. 449464.
    38. 38)
      • 16. Yoon, B., Chang, H.: ‘Potentialities of data-driven nonparametric regression in urban signalized traffic flow forecasting’, J. Transp. Eng., 2014, 4, (14), p. 27.
    39. 39)
      • 36. Oh, S., Byon, Y.J., Yeo, H.: ‘Improvement of search strategy with K-nearest neighbors approach for traffic state prediction’, IEEE Trans. Intell. Transp., 2016, 17, (4), pp. 11461156.
    40. 40)
      • 17. Markovic, H., Basic, B.D., Gold, H., et al: ‘GPS Data-based non-parametric regression for predicting travel times in urban traffic networks’, PROMET Traffic Transp., 2010, 22, (1), pp. 113.
    41. 41)
      • 2. Zou, Y., Shi, G., Shi, H., et al: ‘Traffic incident classification at intersections based on image sequences by HMM/SVM classifiers’, Multimedia Tools Appl., 2011, 52, (1), pp. 133145.
    42. 42)
      • 26. Wu, S., Yang, Z., Zhu, X., et al: ‘Improved k-NN for short-term traffic forecasting using temporal and spatial information’, J. Transp. Eng., 2014, 14, (7), p. 26.
    43. 43)
      • 18. Hong, H., Huang, W., Xing, X., et al: ‘Hybrid multi-metric K-nearest neighbor regression for traffic flow prediction’. 18th IEEE Int. Conf. on Intelligent Transportation Systems, Gran Canaria Canary Islands, Spain, September 2015, pp. 22622267.
    44. 44)
      • 20. Dell'Acqua, P., Bellotti, F., Berta, R., et al: ‘Time-aware multivariate nearest neighbor regression methods for traffic flow prediction’, IEEE Trans. Intell. Transp., 2015, 16, (6), pp. 33933402.
    45. 45)
      • 30. Ruiz Aguilar, J.J., Turias, I.J., Moscoso Lopez, J.A., et al: ‘Forecasting of short-term flow freight congestion: a study case of algeciras Bay port (Spain)’, Dyna, 2016, 83, (195), pp. 163172.
    46. 46)
      • 34. Hong, H., Zhou, X., Huang, W., et al: ‘Learning common metrics for homogenous tasks in traffic flow prediction’. 14th IEEE Int. Conf. on Machine Learning and Applications (ICMLA), Miami, FL, December 2015, pp. 10071012.
    47. 47)
      • 25. Moghaddam, S.S., Hellinga, B.: ‘Real-time prediction of arterial roadway travel times using data collected by bluetooth detectors’, Transp. Res. Rec., 2014, 2442, pp. 117128.
    48. 48)
      • 12. Lin, L., Wang, Q., Sadek, A.W.: ‘Short-term forecasting of traffic volume – evaluating models based on multiple data sets and data diagnosis measures’, Transp. Res. Rec., 2013, 23, (92), pp. 4047.
    49. 49)
      • 47. Laurikkala, J., Juhola, M., Kentala, E., et al: ‘Informal identification of outliers in medical data’. Fifth Int. Workshop on Intelligent Data Analysis in Medicine and Pharmacology, Berlin, Germany, May 2000, pp. 2024.
    50. 50)
      • 5. Roess, R.P., Prassas, E.S., McShane, W.R.: ‘Traffic engineering’ (Prentice Hall, Upper Saddle River, NJ, 2010, 4 edn.).
    51. 51)
      • 55. Smith, B.L., Demetsky, M.J.: ‘Traffic flow forecasting: comparison of modeling approaches’, J. Transp. Eng., 1997, 123, (4), pp. 261266.
    52. 52)
      • 9. Bernas, M., Placzek, B., Porwik, P., et al: ‘Segmentation of vehicle detector data for improved k-nearest neighbours-based traffic flow prediction’, IET Intell. Transp. Syst., 2015, 9, (3), pp. 264274.
    53. 53)
      • 19. Zheng, Z., Su, D.: ‘Short-term traffic volume forecasting: a k-nearest neighbor approach enhanced by constrained linearly sewing principle component algorithm’, Transp. Res. C, Emerg. Technol., 2014, 43, pp. 143157.
    54. 54)
      • 32. He, Z., Lee, B.S., Snapp, R.: ‘Self-tuning cost modeling of user-defined functions in an object-relational DBMS’, ACM Trans. Database Syst., 2005, 30, (3), pp. 812853.
    55. 55)
      • 15. Hyndman, R.J., Khandakar, Y.: ‘Automatic time series forecasting: the forecast package for R’, J. Stat. Softw., 2008, 27, (3), pp. 122.
    56. 56)
      • 46. Maurer, C.R., Qi, R.S., Raghavan, V.: ‘A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions’, IEEE Trans. Pattern Anal. Mach. Intell., 2003, 25, (2), pp. 265270.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2016.0263
Loading

Related content

content/journals/10.1049/iet-its.2016.0263
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading