Short-term Traffic States Prediction Using k-Nearest Neighbor Algorithm: Focused on Urban Expressway in Seoul

Hyungjoo Kim; Shin Hyoung Park; Kitae Jang

doi:10.7470/jkst.2016.34.2.158

All Issue

2016 Vol.34, Issue 2 Preview Page Next Page

Short-term Traffic States Prediction Using k-Nearest Neighbor Algorithm: Focused on Urban Expressway in Seoul k-NN 알고리즘을 활용한 단기 교통상황 예측: 서울시 도시고속도로 사례

April 2016. pp. 158-167

PDF XML

Abstract

This study evaluates potential sources of errors in k-NN(k-nearest neighbor) algorithm such as procedures, variables, and input data. Previous research has been thoroughly reviewed for understanding fundamentals of k-NN algorithm that has been widely used for short-term traffic states prediction. The framework of this algorithm commonly includes historical data smoothing, pattern database, similarity measure, k-value, and prediction horizon. The outcomes of this study suggests that: i) historical data smoothing is recommended to reduce random noise of measured traffic data; ii) the historical database should contain traffic state information on both normal and event conditions; and iii) trial and error method can improve the prediction accuracy by better searching for the optimum input time series and k-value. The study results also demonstrates that predicted error increases with the duration of prediction horizon and rapidly changing traffic states.

Keywords

event condition

historical data

k-nearest neighbor

short-term prediction

real-time data

본 연구는 실시간 자료를 기반으로 k-NN을 활용한 단기 교통상황 예측 시 각 단계별 세부절차 및 변수결정, 입력자료 구축 등의 각 단계별 잠재적 예측오차에 대한 원인분석 및 시사점 도출을 목적으로 한다. 다양한 단기 예측모형에 대한 선행연구 검토를 통하여 k-NN 모형의 유용성을 검토하였고 이에 대한 적용가능성을 분석하였다. 본 연구의 k-NN 모형은 이력자료 평활화 및 패턴DB 구축의 입력자료 부분, 실시간 자료와 과거 이력자료와의 유사성 측정 및 k 근접이웃 결정 등의 k-NN 알고리즘 부분, 그리고 예측 시간간격에 따른 출력결과 부분 등으로 구성되며 올림픽대로 김포방향 한강대교 남단~여의상류IC 구간을 대상으로 분석을 실시하였다. 교통자료의 불규칙 잡음으로 인하여 정확한 패턴매칭을 위해서 이력자료의 평활화를 실시하였으며, 이력자료 패턴 DB는 일반 및 이벤트 상황으로 구분하여 활용하였다. 최적의 시계열 자료 및 k 근접이웃 결정을 위해서 시행착오 방법을 적용하였으며, 단기 교통상황 예측 시 예측 시간간격이 증가할수록 예측오차가 증가하는 패턴, 그리고 교통상태가 급변하는 시점에서도 예측오차가증가함을 알 수 있었다. 본 연구의 k-NN 모형에 대한 각 단계별 예측오차에 대한 원인을 분석하여 개선방향을 제시함으로써 향후 신뢰성 있는 단기 교통상황예측 정보제공 및 시스템에 활용이 가능할 것으로 판단된다.

키워드

이벤트 상황

이력자료

k-최대근접이웃

단기예측

실시간자료

References

Altman N. S. (1992), An Introduction to Kernel and Nearest-Neighbor Nonparametric Regression, American Stat., 46(3), 175-185.

Chen M., Chien S. I. J. (2001), Dynamic Freeway Travel-time Prediction With Probe Vehicle Data: Link Based Versus Path Based, Transp. Res. Rec., 1768(1), 157-161.

Chien S., Ding Y., Wei C. (2002), Dynamic Bus Arrival Time Prediction With Artificial Neural Network, J. Transp. Eng., 128(5), 429-438.

Clark S. (2003), Traffic Predicting Using Multivariate Nonparametric Regression, J. Transp. Eng., 129(2), 161-168.

Guin A., Laval J., Chilukuri B. R. (2013), Freeway Travel-time Estimation and Forecasting, School of Civil and Environmental Engineering Georgia Institute of Technology, GDOT Research Project 10-01; TO 02-60.

Innamaa S. (2005), Short-term Prediction of Travel Time Using Neural Networks on an Interurban Highway, Transp., 32(6), 649-669.

Kwon J., Coifman B., Bickel P. (2000), Day-to-day Travel-time Trends and Travel-time Prediction From Loop-detector Data, Transp. Res. Rec., 1717(1), 120-129.

Lam W. H. K., Tang Y. F., Chan K. S., Tam M. L. (2006), Short-term Hourly Traffic Forecasts Using Hong Kong Annual Traffic Census, Transp., 33(3), 291-310.

Lam W. H. K., Tang Y. F., Tam M. L. (2006), Comparison of Two Non-parametric Models for Daily Traffic Forecasting in Hong Kong, J. Forecasting, 25(3), 173-192.

Lim S., Lee C. (2011), Data Fusion Algorithm Improves Travel Time Predictions, IET Intell. Transp. Syst., 5(4), 302-309.

Rice J., van Zwet E. (2004), A Simple and Effective Method for Predicting Travel-times on Freeways, IEEE Intell. Transp. Syst., 5(3), 200-207.

Shalaby A., Farhan A. (2004), Prediction Model of Bus Arrival and Departure Times Using AVL and APC data, J. Public Transp., 7(1), 41-61.

Smith B., Williams B., Oswald K. (2002), Comparison of Parametric and Non Parametric Models for Traffic Flow Forecasting, Transp. Res. C, 10(4), 303-321.

van Lint J. W. C. (2006), Reliable real-time framework for short-term freeway travel-time prediction, J. Transp. Eng., 132(12), 921-932.

van Lint J. W. C., Hoogendoorn S. P., van Zuylen H. J. (2005), Accurate Freeway Travel-time Prediction With State-space Neural Networks Under Missing Data, Transp. Res. C, 13(5), 347-369.

Zhang X., Rice J. A. (2003), Short-term Travel-time Prediction, Transp. Res. C, 11(3), 187-210.

Information

Publisher :Korean Society of Transportation
Publisher(Ko) :대한교통학회
Journal Title :Journal of Korean Society of Transportation
Journal Title(Ko) :대한교통학회지
Volume : 34
No :2
Pages :158-167
Received Date : 2015-10-07
Revised Date : 2015-11-27
Accepted Date : 2016-03-18
DOI :https://doi.org/10.7470/jkst.2016.34.2.158

Journal of Korean Society of Transportation ISSN:1229-1366(Print) 2234-4217(Online) 대한교통학회지

All Issue