交 通 工 學 大 韓 土 木 學 會 論 文 集
第31卷 第1D 號·2011年 1月 pp. 43~50
결측 택시 Probe 통행속도 예측기법 개발에 관한 연구
A Study on the Development of a Technique to Predict Missing Travel Speed Collected by Taxi Probe
윤병조*
Yoon, Byoung Jo
···
Abstract
The monitoring system for link travel speed using taxi probe is one of key sub-systems of ITS. Link travel speed collected by taxi probe has been widely employed for both monitoring the traffic states of urban road network and providing real-time travel time information. When sample size of taxi probe is small and link travel time is longer than a length of time interval to collect travel speed data, and in turn the missing state is inevitable. Under this missing state, link travel speed data is real-timely not collected. This missing state changes from single to multiple time intervals. Existing single interval prediction techniques can not generate multiple future states. For this reason, it is necessary to replace multiple missing states with the estimations gen- erated by multi-interval prediction method. In this study, a multi-interval prediction method to generate the speed estimations of single and multiple future time step is introduced overcoming the shortcomings of short-term techniques. The model is devel- oped based on Non-Parametric Regression (NPR), and outperformed single-interval prediction methods in terms of prediction accuracy in spite of multi-interval prediction scheme.
Keywords : taxi probe, real-time missing travel speed, historical data, npr, travel speed estimation
···
요 지
택시 프로브(Probe)를 이용한 구간통행속도 모니터링체계는 지능형교통체계(ITS)의 핵심적인 하부시스템 중 하나이다. 택 시 프로브기법을 통해 수집되는 구간통행속도는 도시가로망의 교통상태 모니터링과 통행시간 정보제공에 널리 활용되고 있 다. 그러나 택시 Probe기법은 표본수가 적고 교통혼잡으로 인하여 구간통행시간이 자료수집 주기보다 큰 경우, 실시간으로 자료가 수집되지 않는 누락상태가 발생하게 된다. 이러한 누락상태는 단일시간대에서 다중시간대에 걸쳐 발생하게 되며, 기 존의 단일시간대 예측기법으로는 다중시간대의 상태를 예측하지 못하는 단점이 있다. 따라서 다중시간대 누락상태에서 실시 간 구간통행속도를 예측하기위한 기법이 요구된다. 본 연구에서는 기존의 단일시간대 예측기법의 한계를 극복하면서 단일 및 다중시간대 통행속도를 예측하기위한 기법을 개발하였다. 개발된 모형은 비모수회귀(NPR)을 기반으로 개발되었으며, 다중시 간대 예측에도 불구하고 기존의 단일시간대 예측기법보다 우수한 정확도를 보였다.
핵심용어 : 택시 Probe, 실시간 누락통행속도, 이력자료, 비모수회귀(NPR), 통행속도 추정
···
1. 연구의 배경 및 목적
ITS 분야에서 실시간 교통정보수집체계는 매우 주요한 역 할을 수행하고 있다. 그리고 ITS의 하위시스템인 ATIS, ATMS 등에 이용되는 실시간 속도정보는 기존의 지점검지에 서 AVI(Automatic Vehicle Identification, DSRC(Dedicated Short Range Communication) 등을 이용한 구간검지로 변 화하고 있다. 그리고 수집된 교통류 속도정보는 소통상태 모 니터링, 통행시간 정보제공 등에 활용되고 있다.
실시간 구간 속도 및 통행시간 정보는 예측기법을 활용하 여 동적으로 장래의 교통상태(통행속도 또는 통행시간)를 평 가한 후 이용된다. 동적 예측기법으로는 시간대(t)에서 시간
대(t+1)의 교통상태를 예측하는 단일시간대 예측기법(Single- interval prediction technique)을 적용하고 있다. 지점검지기 법을 통해 수집된 교통상태는 시간대(t-∞)에서 시간대(t)까지 정보가 수집됨으로 기존의 단일시간대 예측기법을 이용하여 시간대(t+1)의 장래 교통상태를 예측하기에 적합하다.
지점검지기법과 달리 구간검지기법을 통해 수집된 교통상 태는 시간대(t-∞)에서 시간대(t-m, m≥0, m=정수)까지 정보가 수집된다. 이는 차량 프로브의 샘플이 해당 시간대에 존재하 지 않거나 시간대길이(l)보다 통행시간이 길어 해당시간대의 통행시간 자료가 수집되지 않는 시간처짐(Time lag) 현상이 발생하기 때문이다. 단구간의 경우, 시간처짐은 교통혼잡 등 으로 인하여 시간대길이 동안에 해당구간의 통행을 완료하
*정회원·인천대학교 도시과학대학 도시환경공학부 조교수·공학박사 (E-mail : [email protected])
지 못 하였기 때문에 발생하게 되며, 통행시간(tt)>시간대길 이(l)인 경우이다. 따라서 m=1일 경우, 기존의 단일시간대 예측기법을 이용한 시간대(t)의 실시간 교통상태 모니터링이 가능하다. 그러나 m>1일 경우, 기존의 예측기법으로는 실시 간 교통상태를 예측할 수 없는 문제가 있다. 이는 기존의 단일시간대 예측기법의 경우 다중시간대에 걸쳐 나타나는 시 간처침 문제를 극복할 수 없기 때문이다. 이러한 다중시간대 시간처짐 문제를 극복하기 위해서는 다중시간대 예측기법이 필연적이다.
이상의 현실적인 문제점을 극복하기 위하여 본 연구에서는 택시프로브 기법을 이용하여 수집되는 도시부 구간속도자료 의 다중시간대 누락상태에서 실시간 구간통행속도를 예측하 기위한 다중시간대 예측기법을 개발하였다. 개발된 다중시간 대 예측기법은 비모수회귀(NPR, Non-Parametric Regression) 를 기반으로 개발되었으며, 이력자료와 누락자료를 포함하는 현행자료를 이용하도록 설계되었다. 개발모형은 택시 프로브 기법으로 수집된 실제 구간통행속도 자료를 이용하여 단일 시간대 예측기법으로 널리 이용되는 칼만필터링(Kalman Filtering)기법과 비교하였으며, 우수한 결과를 보였다. 개발 된 다중시간대 예측기법은 기존 단일시간대 예측기법의 한 계를 극복함으로서 보다 사전대응적인 교통정보제공 및 제 어전략에 적용이 가능할 것으로 판단된다.
2. 기존연구 고찰
본 연구에서는 택시 프로브자료의 연속된 누락상태에서 실 시간 구간통행속도를 예측하는 다중시간대 구간통행속도 예 측기법을 NPR기법을 개반으로 개발하고자 한다. 따라서 기 존연구 고찰은 단일시간대, 다중시간대 예측기법에 대하여 고찰한 후, 본 연구에서 소개되는 다중시간대 구간통행속도 예측모형의 접근법인 NPR기법에 대하여 수행하도록 한다.
단일시간대(Single interval) 예측기법은 연속된 시간대의 교통상태인 시간대(t-∞)~시간대(t)의 실시간 자료를 이용하여 시간대(t+1)의 단기적인 장래상태를 예측하기 때문에 단기예 측기법(Short-term prediction)이라고 한다. 대부분의 기존연 구는 단일시간대 예측기법으로서 회귀식(Regression, Lin과 Zeng 1999; Jeong과 Rilett 2005), 시계열모형(Time Series model, Ahmed와 Cook 1979; Smith 등 2002), 인공신경 망(Artificial Neural Network, Smith와 Demetsky 1995;
Park과 Rilett 1999; Chien 등 2002; Jeong과 Rilett 2005), 칼만필터링(Kalman Filtering, Chen과 Chien 2001; Chien 등 2002; Cathey와 Dailey 2003; Shalaby와 Farhan 2004) 등의 기법이 주로 이용되고 있다. 단일시간대 예측기법은 주 로 실시간 시계열자료를 입력상태로 이용하는 일종의 이동 평균기법이라 할 수 있다. 따라서 장래상태가 급변하는 경우 나 시계열적 변동이 클 경우 예측의 한계를 가지고 있다.
이러한 한계는 장래상태의 예측에 대한 방향성과 불확실성 (Uncertainty)에 대한 문제와 연결된다. 따라서 단일시간대 예측기법을 이용하여 다중시간대 예측문제를 해결하기에는 한계가 있다.
AVI, 프로브 차량 기법 등을 이용한 구간통행속도의 수집 은 구간통행시간 만큼의 시간처짐(m)문제가 발생한다. 구간
통행시간이 예측단위 시간대(Time Interval)의 길이보다 클 경우, 시간처짐의 문제가 발생하게 되며, 이는 시간대(t-∞)~
시간대(t-m)에서 시간대(t+1)의 장래상태를 예측하는 다중시 간대 예측문제로 귀착되다. 다중시간대 예측문제는 위에서 언급한 다중시간대 장래상태의 방향성과 불확실성을 증폭시 키게 된다. 이러한 필요성에도 불구하고 다중시간대 장래상 태 예측에 관한 연구는 거의 보고되고 있지 않다. Park과 Rilett(1999)는 인공신경망을 이용하여 다중시간대 구간통행 속도를 예측하였다. 예측오차는 시간대(t+1)에서 약 8%에서 시간대(t+5)에서 약 16%까지 증가하였으나 다중시간대 예측 임을 고려하면 우수한 결과라고 할 수 있다. Chang 등 (2010)은 NPR기법을 기반으로 출발지에서 도착지까지의 버 스 경로통행시간을 출발지 버스정류장에서 출발시각을 기준 으로 예측하는 다중시간대 경로통행시간 예측기법을 제시하 였다. 3~7까지의 변동적인 다중시간대를 예측하였으며, 예측 오차는 2.9~3.7%로 낮게 나타나 우수한 결과를 보였다.
이상의 단일 및 다중시간대 예측기법에 대한 기존연구 고 찰결과, 대부분의 연구는 단일시간대 예측기법이며 다중시간 대 예측기법은 그 필요성에도 불구하고 심도 깊은 연구가 보고되고 있지 않는 실정이다. 특히, 택시 프로브를 이용해 수집되는 구간속도의 경우 시계열자료의 변동(Variation)이 크기 때문에 장래상태에 대한 방향성과 불확실성 문제를 수 반하게 된다. 또한 택시 프로브 자료의 특성상 수집되는 구 간속도자료는 변동적인 시간처짐을 수반한다. 따라서 시간처 짐상태에서 발생하는 누락자료 상태에서 현재상태 즉 시간 대(t)의 구간속도를 예측하는 문제는 가변적인 시간처짐, 장 래상태의 방향성과 불확실성이라는 3개 문제를 해결해야 한 다. 따라서 본 연구에서는 이러한 3개 문제를 이력자료와(시 간처짐으로 발생하는 누락상태를 포함하는) 실시간자료를 이 용하고 NPR를 기반으로 현재 상태의 구간통행속도를 예측 하는 기법을 제시하고자 하며, NPR기법에 대한 특성과 기 존연구는 다음과 같다.
회귀모형은 모수와 비모수으로 구분된다. 모수회귀(Para- metric Regression)는 독립변수가 장래에도 동일하게 종속변 수에 영향을 미친다고 가정하는 반면, 비모수회귀(NPR)는 현재상태와 유사한 과거상태를 탐색하여 장래상태를 추정하 는데 용이하다(Oswald 등 2000; Smith 등 2000). NPR은 입력과 출력 상태간의 비선형적인 관계를 결정하는데 있어 파라미터의 계산없이 새로운 관측상태의 추가가 용이하다. 모 수회귀와 같이 통계적 분포(Statistical distribution)을 가정하 지 않는 장점이 있다. 반면, 변수간의 상관관계를 알 수 없 다(Oswald 등 2000). 그러나 알려지지 않은 변수(Unknown parameter)를 포함하는 확률적 상태를 고려하면 이러한 분포 에 대한 가정은 NPR기법의 강력한 기능이다.
NPR기법은 (모수)회귀와 같이 입력변수간, 입력변수와 종 속변수간의 통계적 가정이 아닌 과거의 경험을 기반으로 하 는 의사결정과정이라고 할 수 있다. 의사결정은 현재의 상태 벡터와 유사한 과거상태벡로로 구성되는 군집(Neighborhood) 에 의해서 수행되며, 군집은 과거상태인 이웃(Neighbor)로 구성된다. NPR의 군집은 현재상태와 유사한 과거상태의 개 수, 즉 군집의 개수를 정의하는 방법에 의하여 결정된다. 군 집의 개수를 정의하는 방법은 크게 최인접-k 이웃(k-nearest
neighbor)기법과 최인접 개수의 ±범위를 설정하는 Kernel 군 집기법이 있다.
NPR은 현재상태를 설명하기위한 과거의 경험 즉, 이력자 료를 기반으로 하기 때문에 방대한 양의 이용 가능한 이력 자료가 지원될 경우, 유용한 기법중 하나로서 다양한 분아에 적용되고 있다. 확률적(Stochastic) 또는 혼재된(Mixed) 상태 에서 비선형 시계열의 예측문제는 NPR를 이용하면 구조적으 로 모형화가 가능하다(Robinson, 1983; Mulhern과 Caprara, 1994). NPR은 무질서 상태에서 타 기법보다 장점을 갖는다 (Disbro와 Frame, 1989; Mulhern과 Caprara, 1994). 이러한 장점을 갖는 NPR은 Rainfall-runoff(Karlsson과 Yakawitz, 1987), Market response(Mulhern과 Caprara, 1994), Utility load(Wehenkel, 1996; Charytoniuk 등, 1998) 등 다양한 분야의 예측에 적용되었다. 교통분야에서 NPR은 주로 단일 시간대 예측(Davis와 Nihan, 1991; Smith 등, 2002; Sun 등, 2003)에 적용되었으며, Chang 등(2010)은 버스 경로통 행시간의 예측에 있어 다중시간대로 확장하였다.
3. 방법론 개발
3.1 속도상태 변화의 특성분석
예측기법의 개발에 앞서, 상태자료의 특성분석을 수행하도 록 한다. 상태자료의 특성에 따라 예측방법론에서 고려되어 할 사항과 접근법이 결정됨으로 예측하고자 하는 자료의 특 성분석은 예측기법의 개발에 있어 매우 중요하다. 그림 1은 택시 프로브의 이력 구간통행속도의 시간대에 따른 시계열 적 변동을 보여주고 있다. 속도는 매우 큰 변동을 보이고 있으며, 결정론적(deterministic) 또는 혼돈적(Chaotic)이라기 보다는 확률적(Stochastic)이다. 또한 이러한 이력자료는 다양 한 패턴과 알려지지 않은 변수(Unknown parameter)를 포함 하고 있다. 그러나 동적으로 변화하는 통행속도자료의 다양 한 패턴을 분석하고 알려지지 않은 변수를 통계적으로 분석 하는 것은 매우 어려운 과정이다. 그림 2는 통행속도자료의 시계열적 변동을 보여주고 있다. 통행속도는 시간대에 따라 급격하게 속도가 변화하는 지그제그 형태의 변동을 보이고 있다. 이러한 급격한 상태 변동을 기존의 단일시간대 예측기 법을 이용하여 예측할 경우, 예측의 밀림현상 즉, 예측값의 지그재그 현상이 발생하게 된다. 이는 장래 상태의 방향성과 불확실성이 증폭되기 때문이다.
상태가 급격하게 변화하는 경우 즉, 상태의 소음(Noise)이 큰 경우에는 장래상태의 방향성을 고려하면서 불확실성을 감 소시키는 접근법이 필요하며, 이는 확률적이고 또는 혼재된 상태의 비선형 시계열 예측문제에 귀착된다(Robinson, 1983; Mulhern과 Caprara, 1994). 이러한 상태에서 NPR모 형은 타 예측기법에 비하여 장점을 갖는다(Disbro와 Frame, 1989; Mulhern과 Caprara, 1994). 따라서 본 연구에서는 NPR을 기반으로 다중시간대 구간통행속도 예측기법을 개발 하였다.
3.2 다중시간대 구간속도 예측기법 개발 3.2.1 다중시간대 예측의 개념
택시 프로브를 이용한 구간통행속도 수집은 구간의 시종을 주행하는 시간이 요구되며, 수집된 개별 차량의 속도자료는 일정 시간간격(보통 5분)으로 집계된다. 따라서 최소한 1개 의 시간간격 단위의 시간처짐(m≥1, 정수)이 발생하게 되며, 통행시간이 증가하면 시간처짐은 증가하게 된다. 시간처짐 특성을 갖는 프로브 속도정보를 이용한 구간통행속도의 실 시간 모니터링을 위해서는 유동적인 시간처짐을 고려한 통 행속도 예측기법이 필요하며, 예측의 시간대는 단일에서 다 중시간대까지 변화한다.
시간처짐 상태에서 실시간 모니터링을 위한 본 연구의 예 측 영역(Horizon)을 시간과 상태의 개념적으로 살펴보면 그 림 3과 같다. 시간영역은 시간대(t)의 예측시간대와 시간대(t- 1)에서 (t-(2×m+n)의 현행시간대로 구성된다. 현행시간대는 m개의 시간처짐 시간대(t-1)~(t-m)과 현행 시계열 시간대 (t- (m+1)~(t-(2×m+n)로 구성된다. 여기서 n(≥2, 정수)은 장래상 태의 방향성과 유사한 과거의 상태 탐색를 위한 최소의 현 행 시계열자료의 크기이다. 시간처짐은 m≥1임으로 현행시계 열자료의 크기는 최소 3개를 확보하게되며, 이는 장래상태의 방향을 판단하게 된다. 또한 시간처짐 시간대의 크기(m)이 증가함에 따라 장래상태의 방향성과 불확실성은 증가하게 된 다. 이를 고려하기 위하여 m값의 증가에 따라 현행 시계열 시간대의 길이는 2×m에 비래하여 증가하도록 함으로써 불확 실한 장래상태의 방향성을 고려하게 된다. 그리고 속도의 상 태는 시간대(t)의 예측상태, 시간대(t-1)~(t-m)의 누락상태, 그 리고 시간대(t-(m+1)~(t-(2×m+n)의 현행상태로 구성된다. 따 라서 시간대(t)의 예측상태는 시간대(t-(m+1)~(t-(2×m+n)의 현행상태를 이용하여 예측하게 된다.
그림 1. 속도자료의 Stochastic 특성
그림 2. 속도자료의 시계열 변동
3.2.2 개발모형의 구조
NPR모형은 ① 현행, 입력 그리고 출력 상태벡터(State vector), ② 현행상태와 입력상태간의 상태간 거리(Distance metric), ③ 예측모형(Prediction model), 그리고 ④ 수행 알 고리즘으로 구성된다. 그림 4는 본 연구에서 개발한 NPR기 반 구간속도추정모형의 구조와 수행과정을 보여주고 있다.
모형의 수행과정은 현재상태와 유사한 과거상태의 군집 (Neighborhood)을 구축하는 과정과 구축된 군집을 이용하여 장래상태를 예측하는 과정으로 구성된다. 군집을 구축하는 과정은 상태간 거리를 이용하여 현행상태벡터(Current state vector)와 상태거리가 가까운 과거의 입력상태벡터(Input state vector)를 검색하는 반복적인 과정을 통하여 k개의 과 거 상태벡터와 상태간 거리로 구성되는 군집인 출력상태벡 터(Output state vector)를 구성하는 것이다. 그리고 구축된 출력상태벡터와 예측모형을 이용하여 장래상태를 예측하게 된다. 이상의 과정은 KNN(k-Nearest Neighbor) 알고리즘을 이용하여 구현된다. 따라서 개발된 모형은 ① 현행, 입력, 그 리고 출력 상태벡터, ② Distance Metric, ③ 장래상태 예측 모형, ④ KNN 알고리즘의 Pseudo-code로 설명하도록 한다.
3.2.3 상태벡터
KNN-NPR(k-Nearest Neighbor NPR)의 상태벡터(State vector)는 현행(Current), 입력(Input), 그리고 출력(Output) 상태벡터로 구성된다. 입력벡터는 설명변수 그리고 출력벡터 는 종속변수의 역할을 수행하게 된다. 현행상태벡터(sc)는
Distance metric을 이용하는 이력자료(Historical data)에서 현행상태벡터와 상태간 거리가 근접한 입력상태벡터를 탐색 하여 출력상태벡터에 추가하기위해 이용된다. 시간대(t)에서 현행상태벡터(sc)는 현행 구간속도 시계열자료(sc(i), t-(2×
m+n) ≤ i ≤ t-(m+1))를 이용하여 다음과 같이 정의한다.
(1) 군집인 출력상태벡터는 k개의 최인접 이웃(k-nearest neighbors)으로 구성되며, 각 이웃은 이력자료의 구성요소이 다. 즉, k개의 최인접 입력상태벡터는 현행상태백터와 Distance metric을 이용하는 KNN알고리즘의 이력자료 탐색 과정을 통하여 추출되어 군집에 추가/갱신된다. 방대한 양의 이력자료가 존재하기 때문에 가능한 입력상태벡터의 형태는 다양하다. Smith(2002)는 이력평균상태를 입력상태에 통합하 여 이용하였다. Chang(2010)은 예측상태의 동적상태를 고려 하기 위하여 시간처짐(Lagged)된 이력상태를 이용하였으며, 보다 동적으로 장래상태를 설명하였다. 시간대(t)에서 입력상 태벡터(sh)는 이력 Database의 구간속도 시계열자료(sh(i))를 이용하여 다음과 같이 정의하며, 현행상태벡터에 시간적으로 종속적이다.
(2) 예측모형을 이용하여 시간대(t)의 상태를 예측하기 위해서 는 군집을 구성하는 요소인 이웃들(Neighbors)이 필요하며, 이웃들은 시간대(t)의 과거 이력상태들이다. 따라서 시간대 (t)의 출력상태벡터(o(t))는 k개의 개별 출력상태벡터(ok(t), k≥1)로 구성되며, 식 (3)과 같이 정의한다. 본 연구에서 이 용된 예측모형은 상태간 거리를 장래상태의 의사결정에 이 용하게 된다. 따라서 K번째 개별 출력상태벡터(oK(t), 1≤K
≤k)는 시간대(t)에서 K번째 이웃인 shK(t)와 이때의 현행상태 와 출력상태간의 상태거리인 EKch로 구성되며, 식 (4)와 같이 정의한다.
, (3) , (4)
3.2.4 Distance Metric
현행상태벡터와 유사한 입력상태벡터를 이력자료에서 탐색 하여 출력상태벡터를 구성하기 위해서는 탐색알고리즘을 이 용하게 된다. 탐색의 과정에서 현행상태벡터와 입력상태벡터 의 유사성(Similarity), 즉 상태간 거리는 일반적으로 Lm거리 를 이용하여 산정된다. Lm거리는 m={1, 2, ..., ∞}에 따라 Manhattan, Euclidean, ..., 무한 거리로 각각 불리우며 식 (5)와 같다. 유클리디언 거리는 맨하턴 거리와 같이 상태간 거리가 같은 경우라도 상태벡터의 요소간 거리를 고려할 수 있다. 따라서 본 연구에서는 m=2인 유클리디언 거리를 이용 하도록 한다. 현행상태벡터인 식 (1)과 입력상태벡터 식 (2) 을 유클리디언 거리로 전개하면 식 (6)과 같다.
sc=sc( )i
sc(t–(m 1+ )) s, c(t–(m 2+ )) ..., , [
=
sc(t m n–( + )) ... s, , c(t 2 m–( × +n))]
sh=sh( )i
sh(t–(m 1+ )) s, h(t–(m 2+ )) ..., , [
=
sh(t m n–( + )) ... s, , h(t 2 m–( × +n))]
o t( )=[o1( ) ... ot, , K( ) ... ot, , k( )t] k 1≥ oK( )t =[shK( ) Et, chK] 1 K k≤ ≤ 그림 3. 다중시간대 예측의 개념
그림 4. 본 연구의 NPR모형 구조
, (5)
(6)
3.2.5 장래상태 예측모형
출력상태벡터가 구축되면 장래상태는 예측모형을 이용하여 평가된다. 예측모형은 장래상태에 대한 의사결정의 마지막 과정이라 할 수 있다. 예측모형은 종속변수를 산술평균하는 방법과 현행상태와 입력상태간 거리의 역수로 가중평균한 방 법으로 구분할 수 있다. 산술평균은 상태간 거리 즉, 상태간 유사성을 고려할 수 없는 단점이 있다. 상태간 거리의 역수 를 이용한 가중평균은 유사한 상태일수록 장래상태에 대한 의사결정의 권한을 고려할 수 있으며, 산술평균에 비하여 우 수한 예측결과를 보였다(Smith 등, 2002; Chang 등, 2010).
따라서 본 연구에서는 상태간 거리의 역수로 가중평균한 방 법을 이용하여 시간대(t)의 구간통행속도( )를 예측하도록 하며, 식 (7)과 같다.
(7)
3.2.6 k-Nearest Neighbor(KNN) 알고리즘
NPR의 출력상태벡터를 구성하는 방법은 최인접 k를 정하 는 KNN(k-nearest neighbor) 알고리즘과 Kernel 거리를 이 용하여 최인접 개수의 ±범위를 정의하는 Kernel 군집 알고 리즘이 주로 이용된다. 본 연구에서는 KNN알고리즘을 이용 하였다. KNN알고리즘은 이력자료의 상태벡터를 검색하여 현 행상태벡터와 상태간 거리가 가장 가까운 k개의 이웃해, 즉 출력상태벡터를 구축하는 탐색과정이다. 본 연구에서 이용한 KNN 알고리즘의 Pseudo-code는 다음과 같이, 초기화, 탐색, 갱신, 예측으로 구성된다.
주어진 시간대(t)에서 주어진 현행상태벡터(sc)와 최인접 이 웃해의 개수 k에 대하여:
I. 출력상태벡터(o(t))의 1에서 k까지 개별 출력상태(ok(t))를 초기화.
II. 모든 입력상태벡터( )에 대하여
II-1 j번째 입력벡터(shj)와 현행벡터(sc)간의 Echj을 계산 II-2 If Then
(여기서, Emax=max{ , ..., , ..., })
① Emax에 해당하는 oK(t)을 제거
② shj와 Echj을 출력벡터(o(t))에 갱신
③ 갱신된 출력벡터에서 Emax을 탐색 III. 식 (7)을 이용하여 산정
4. 개발모형의 적용 및 평가 4.1 적용연구 설계
NPR모형은 다량의 이력자료를 기반으로 장래상태를 예측 하게 된다. 따라서 본 연구에서는 강남대로 신사역사거리~논
현역사거리 구간의 개별 택시프로브 구간속도자료를 이용하 여 2009년 4월 17일~7월 16일까지의 총 91일 동안의 이력 자료를 구축하였으며, 개별 속도자료의 집계를 위한 시간대 길이는 5분으로 설정하였다. 따라서 이력자료의 배열크기는 26,208=[91(일)＊24(시간/일)＊12(시간대/시)]이다. 구축된 이 력자료 중 마지막 1일의 288시간대는 개발모형의 평가에 적 용하였다.
개발모형의 평가를 위한 평가지표는 평균절대값백분위오차 (MAPE: Mean Absolute Percentage Error, %)를 적용하였 다. 그림 1과 그림 2에서 구간통행속도는 Noise가 크게 나 타나며 주간과 야간에 5kph에서 40kph까지 크게 변화하고 있다. 이러한 경우 MAPE는 직관적이고 용이한 비교의 기준 을 제시하여 준다. 따라서 MAPE를 적정 k값의 분석과 오 차분석에 이용하도록 하며, 식 (8)과 같다.
(8) 여기서, xi: 관측값, : 예측값, n: 자료의 개수
아직까지 시간대의 개수(≥1)가 변동하면서 장래상태를 예 측하는 다중시간대 예측기법은 보고되고 있지 않고 있다. 따 라서 본 연구에서는 빠른 연산수행속도와 우수한 예측력을 보이기 때문에 널리 이용되는 단일시간대 예측기법인 칼만 필터링 기법과 단일시간대 예측력을 비교하였다. 또한 칼만 필터링의 단일시간대 예측결과와 본 연구의 다중시간대 예 측결과를 비교함으로서 다중시간대에서 예측력을 상대적으로 분석하도록 한다.
4.2 평가결과 4.2.1 적정 k값 분석
NPR의 예측력은 k개로 구성되는 개별 출력벡터의 유사성 에 의해 결정되기 때문에 적정 k값의 분석은 매우 중요하다.
그림 5는 k에 따른 다중시간대(m)별 MAPE(%)변화를 보여 주고 있다. 예측오차곡선은 약간의 시계열적 변동을 보이면 서 k가 증가함에 따라 급격히 감소한 후, 적정 k이후 다시 증가하는 오목함수(Concave) 형태를 보인다. 다중시간대별 오차곡선 또한 오목함수 형태를 보이면서 k값 6~13의 범위 에서 오차를 전역적으로 최소화되고 있으며, 오차는 0.5내에 서 약간의 변동을 보이고 있다. 평균 오차곡선은 k값 12에 Lm xi–yim
i
∑d
⎝ ⎠
⎜ ⎟
⎛ ⎞1 m/
= d i≥
Ech sc( ) si – h( )i 2
i t= –(m 1+ ) t–(2 m× +n)
∑
1 2/
=
sˆ t( )
sˆ t( )
shi( )t
i 1=
∑k ×Echi 1–
Echi 1–
i 1=
∑k
---
=
sh∈Sh
Echj <Emax
Ech1 EchK Echk
sˆ t( )
MAPE %( ) 1 n--- xi–xˆi
xi ---
i 1=
∑N
⎝ ⎠
⎜ ⎟
⎛ ⎞
×100
=
xˆi
그림 5. 적정 k값의 분석
서 예측오차 약 14.5%로 최소화되고 있다. 따라서 적정 k값 은 12로 설정하였다.
4.2.2 예측결과 분석
본 연구에서 개발된 모형은 단일시간대(m=1)의 경우 칼만 필터링 기법과의 비교를 통해 분석하였으며, 다중시간대 (m≥2)의 경우 시간처짐이 가변적인 상태에서 다중시간대 예 측기법이 보고되고 있지 않고 있기 때문에 칼만필터링의 단 일시간대 예측결과를 이용하여 상대적 비교를 수행하였다.
상대적 분석의 편의를 위해 칼만필터링 기법을 이용한 단일 시간대의 구간통행속도 결과를 살펴보면 표 1과 그림 6과 같다. 표 1에서 칼만필터링의 예측오차는 17.04%로서 본 연 구에서 제시된 다중시간대 예측기법의 오차 11.46~15.16%보 다 높게 나타났다. 이는 차이(관측값-예측값)의 평균은 -0.62 로서 본 연구의 다중시간대 예측기법보다 절대값이 크고, 차 이의 표준편차는 3.91로서 본 연구의 다중시간대 예측기법의 2.89~3.52보다 크게 나타났기 때문이다.
본 연구에서 개발된 다중시간대 예측기법의 예측오차는 단 일시간대(m=1)의 경우 11.46%로서 칼만필터링보다 약 5.5%
낮게 나타났으며, 다중시간대(m≥2)의 경우 다중시간대 예측 임에도 불구하고 예측오차는 13.33~15.16%로서 칼만필터링 의 단일시간대 예측오차보다 낮게 나타났다. 그러나 예측시간대가 증가함에 따라 장래상태에 대한 방향성과 불 확실성이 증가하기 때문에 오차는 증가하고 있지만 칼만필 터링의 오차보다 낮게 나타났다. 또한 차이의 표준편차는 단 일시간대의 경우 개발모형 2.89 칼만필터링 3.91로 나타났으 며, 다중시간대의 경우 개발모형은 3.19~3.52로서 칼만필터 링의 단일시간대보다 낮게 나타났다. 이는 개발모형이 다중 시간대 예측임에도 불구하고 장래상태의 방향성과 불확실성 을 다소 극복하였기 때문이며, 특히 상태의 변동이 심한 경 우 장점을 갖는다고 판단된다.
그림 6에서 관측과 예측 구간통행속도 시계열자료는 심한 변동을 보이고 있다. 이러한 변동상태에서 기존의 단일시간 대 예측기법은 장래상태에 대한 방향성과 불활실성을 극복 할 수 없기 때문에 예측된 장래상태는 심한 시계열적 변동 을 보이면서 실제 상태와 예측상태가 지그재그로 어긋나는 현상을 보이기 때문에 예측력이 현저히 저하된다. 따라서 예 측된 상태의 시계열적 변동은 실제 상태의 변동보다 크게 나타나고 있다. 이는 현행 시계열자료를 이용하는 대부분의 단일시간대 예측기법이 가지는 한계라 할 수 있다.
그림 7은 개발모형으로 예측된 단일시간대의 예측결과를
보여주고 있다. 개발모형의 예측치은 칼만필터링의 예측치보 다 낮은 시계열적 변동을 보이면서 실측치의 높은 변동상태 를 설명하고 있다. 다시말해 개발모형은 속도자료와 같은 변 동이 심한 상태의 예측에 있어 방향성과 평활화(Smoothing) 기능을 가진다. 이러한 기능은 심한 소음(Noise)을 보이는 방향성의 인식과 장래의 불확실성이 높은 장래상태의 예측 에 있어 불확실성을 완화시키는 역할을 수행하게 된다.
시계열의 변동이 심한 상태자료는 장래상태의 방향성에 대 한 불확실성이 증가한다. 따라서 구간통행속도와 같은 시계 열 상태의 변동이 심한 경우의 다중시간대 예측은 장래상태 의 방향성과 불확실성으로 인하여 예측오차는 증폭된다. 따 라서 다중시간대 예측모형의 성능은 방향성과 예측정확도로 설명하도록 한다. 그림 8에서 그림 10는 개발모형의 다중시
표 1. 개발모형과 칼만필터링의 적용결과
모형 예측
시간대 MAPE MD SDD MDD
개발모형
m=1 11.46 0.52 2.89 0.41
m=2 13.33 0.53 3.19 0.55
m=3 14.31 0.61 3.41 0.41
m=4 15.16 0.64 3.52 0.42
칼만필터 m=1 17.04 -0.62 3.91 -0.64
주) 차이=관측값-예측값, MD: 차이의 평균, SDD: 차이의 표준 편차, MDD: 차이의 중앙값
그림 6. 관측치와 예측치의 비교: 칼만필터링, m=1
그림 7. 관측치와 예측치의 비교: 개발모형, m=1
그림 8. 관측치와 예측치의 비교: 개발모형, m=2
간대(m≥2)의 예측결과를 시계열로 보여주고 있다. 다중시간 대 예측임에도 불구하고 개발모형의 예측치는 그림 6의 단 일시간대 예측기법인 칼만필터링의 예측치 보다 낮은 시계 열적 변동을 보이면서 높은 변동상태의 방향성을 설명하고 있다. 이는 개발모형이 속도자료와 같은 변동이 심한 상태의 다중시간대 예측에 있어 평활화 기능을 통하여 방향성에 대 한 불확실성을 감소시키기 때문이다. 따라서 예측시간대의 수가 증가함에 따라 방향성에 대한 불확실성이 증가함에도 불구하고 예측오차는 13.33에서 15.16%로 1.83% 낮게 증 가하고 있다. 칼만필터링을 이용한 단일시간대 예측오차가 17.04%인 점을 고려하면 개발모형의 다중시간대 예측력은 우수하다고 판단된다.
5. 결론 및 향후연구 5.1 결론
ITS의 정보수집체계는 기존의 지점검지체계에서 AVI, DSRC 등 요소기술을 기반으로 하는 구간정보 수집체계로 전환되고 있다. 수집된 구간정보는 정보수집의 과정에서 단 일에서 다중시간대에 걸친 시간처짐이 발생하게 된다. 따라 서 구간검지 정보가 실시간 및 장래 상태의 정보로 활용되 기 위해서는 기존의 단일시간대 예측기법에서 다중시간대 예 측기법으로의 기술적 발전이 요구된다. 이러한 현실적인 필 요성에도 불구하고 다중시간대 예측기법은 보고되고 있지 않 은 실정이다. 이는 장래상태의 방향성과 불확실성을 극복할 수 있는 유력한 대안의 부재 때문이다.
한편으로 ITS의 정보수집체계를 통해 수집되는 방대한 양
의 이력자료는 시스템의 DB에 축적된 후 사용되고 있지 않 거나 일정시간이 경과하면 삭제되고 있었다. 그러나 최근의 첨단자료관리시스템(ADMS, Advanced Data Management System)의 도입은 이력자료에 대한 활용성을 향상시켜 주고 있다. 이러한 첨단자료관리시스템의 도입은 전문가 시스템 (Expert system), 사례기반 이론(Case-based reasoning), NPR 등의 분야를 낳고 있다.
따라서 본 연구에서는 다양한 정보와 패턴 그리고 알려지 지 않은 변수(Unknown parameter)를 포함하고 있는 이력자 료와 현행자료를 활용하여 장래의 다중시간대 구간속도를 예 측하는 다중시간대 예측모형을 NPR기법을 기반으로 개발하 였다. 개발된 모형은 다중시간대 임에도 불구하고 기존의 단 일시간대 예측모형보다 우수한 예측정확도를 보였다. 이는 개발모형이 다중시간대 장래상태의 방향성과 불확실성 문제 를 이력자료에 내재된 정보를 활용하였기 때문이다. 개발된 다중시간대 예측기법은 보다 동적이고 사전대응(Proactive)적 인 교통상태 모니터링, 교통정보제공, 제어전략의 적용이 가 능할 것으로 판단된다.
5.2 향후연구
본 연구는 장래상태의 방향성과 불확실성을 현행 시계열자 료의 확장으로 접근하고 현행상태와 과거상태의 유사성을 이 용하여 장래상태를 예측하는 모형을 개발하였다. 그러나 장 래상태의 보다 정확한 상태예측을 위해서는 상태의 유사성 과 더불어 방향성을 고려하는 추가 연구가 필요하다. 그리고 개발모형은 단거리 단속류 구간에 대하여 적용하였으나, 시 간처짐이 길어지는 장거리 연속류 구간의 적용에 대한 연구 가 수행되어야 할 것이다.
감사의 글
이 논문은 인천대학교 2010년도 자체연구비 지원에 의하 여 연구되었음.
참고문헌
Ahmed, M. and Cook, A. (1979) Analysis of freeway traffic time series data by using Box-Jenkins techniques. Transportation Research Board, 722, pp. 1-9.
Cathey, F. and Dailey, D. (2003) A prescription for transit arrival/
departure prediction using AVL data. Transportation Research Part C, 11, pp. 241-264.
Chang, H., Park, D., Lee, S., Lee, H., and Baek, S. (2010) Dynamic multi-interval bus travel time prediction using bus transit data.
Transportmetrica, Vol. 6, No. 1, pp. 19-38.
Charytoniuk, W., Chen, M. S., and Olinda, P. V. (1998) Nonpara- metric regression based short-term load forecasting. IEEE Transactions on Power Systems, Vol. 13, No. 3, pp. 725-730.
Chen, M. and Chien, S. (2001) Dynamic freeway travel-time pre- diction with probe vehicle data: link based versus path based.
TRR, Vol. 1879, pp. 89-98.
Chien, S., Ding, Y., and Wei, C. (2002) Dynamic bus arrival time prediction with artificial neural network. ASCE Journal of Transportation Engineering, Vol. 128, pp. 429-438.
Davis, G. and Nihan, N. (1991) Nonparametric regression and short-term freeway traffic forecasting. Journal of Transporta- 그림 9. 관측치와 예측치의 비교: 개발모형, m=3
그림 10. 관측치와 예측치의 비교: 개발모형, m=4
tion Engineering, Vol. 117, pp. 178-188.
Disbro, J. E. and Frame, M. (1989). Traffic Flow Theory and Cha- otic Behavior. New York State Department of Transportation Report FHWA/NY/SR-98/91, New York.
Jeong, R. and Rilett, L. R. (2005) Prediction model of bus arrival time for real-time applications. Transportation Research Record, Vol. 1927, pp. 195-204.
Karlsson, M. and Yakowitz, S. (1987) Rainfall-runoff forecasting methods, old and new. Stochastic Hydrology and Hydraulics, Vol. 1, pp. 303-318.
Lin, W. H. and Zeng, J. (1999) Experimental study of real-time bus arrival time prediction with GPS data. Transportation Research Record, Vol. 1666, pp. 101-109.
Mulhern, F. J. and Caprara, R. J. (1994) A nearest neighbor model for forecasting market response. International Journal of Fore- casting, Vol. 10, pp. 191-207.
Park, D. and Rilett, L. R. (1999) Forecasting freeway link travel times with a multilayer feedforward neural network. Computer-
Aided Civil and Infrastructure Engineering, Vol. 14, pp. 357-367.
Robinson, P. (1983) Nonparametric estimators for time series. Jour- nal of Time Series Analysis, Vol. 4, pp. 185-207.
Shalaby, A. and Farhan, A. (2004) Prediction model of bus arrival and departure times using AVL and APC data. Journal of Pub- lic Transportation, Vol. 7, No. 1, pp. 41-61.
Smith, B. L. and Demetsky, M. J. (1995) Short-term flow predic- tion: Neural network approach, Transportation Research Record, Vol. 1453, pp. 98-104.
Smith, B. L., Williams, B. M., and Oswald, R. K. (2002) Compari- son of parametric and nonparametric models for traffic flow forecasting. Transportation Research Part C, Vol. 10, pp. 303- 321.
Wehenkel, L. (1996). Contingency severity assessment for voltage security using nonparametric regression techniques. IEEE Transactions on Power Systems, Vol. 11, pp. 101-111.
(접수일: 2010.11.12/심사일: 2010.11.23/심사완료일: 2010.11.23)
