시공간 자기 상관 데이터 분석으로 도착시간 예측하기
9편 - AI/ML을 활용한 시공간 자기 상관 데이터 분석
TMAP 내비게이션 서비스는 사용자가 목적지에 도착하게 될 예상 시간을 다양한 경로와 함께 제공하고 있습니다. 가장 빠른 경로 찾기와 더불어 정확한 도착 예상 시간의 제공은 내비게이션 서비스의 기본이자 제일 중요한 덕목이죠.
그렇지만 사용자가 지나가게 될 도로의 미래 시점 교통 상황을 예상하고, 이를 반영하여 도착 시간을 계산하는 일은 상당히 어려운 일입니다(그런데 말입니다. 그 어려운 일을 TMAP이 해 냅니다). 이미 90점이 넘는 도착 예상 시간 정확도를 가진 대한민국 1등 TMAP 내비게이션이지만, 안주하지 않고 보다 정확한 도착 시간 정보를 위해 노력하는 Map컨텐츠팀의 스토리를 말씀드려볼까 합니다.
목적지 예상 도착 시간 계산
목적지까지의 예상 도착 시간을 계산하기 위해서는 먼저 출발지부터 목적지까지 지나게 될 도로 링크들을 사용자의 경로 탐색 조건에 맞게 선택해야 합니다. 그 후 사용자가 각 도로 링크에 도달하는 예상 시간 기준, 해당 도로 링크들의 미래 시점 평균 속도와 도로 링크의 길이를 곱하여 주행에 소요되는 시간을 계산할 수 있습니다 (s = vt, 참 쉽죠?).
TMAP은 전국의 도로 링크 정보를 가지고 있고, 각 도로 링크의 길이는 (도로 자체가 변하지 않는다면, 그리고 변해도 TMAP은 금방 압니다) 변하지 않는 값이기 때문에, 예상 도착 시간 계산에서 가장 중요한 정보는 미래 시점 각 도로 링크들의 예상 평균 속도일 것입니다. 현재 TMAP은 이 예상 속도의 정확한 계산을 위해 셀 수 없이 쌓인 방대한 과거 데이터와 Daily Authorized User 1등 내비게이션에 걸맞은 소중한 사용자 여러분들의 실시간 속도 정보를 바탕으로 AI/ML 기법을 포함한 다양한 방법론을 활용하고 있습니다. (그렇습니다. 저희는 90점에 만족하지 않습니다. 100점이 목표니까요!)
시공간 데이터의 특수성
시공간적 자기 상관(spatio-temporal autocorrelation)
시공간적 자기 상관은 '시공간적으로 위치가 가까운 관측치들이 서로 유사한 값을 가지고 있다'는 것을 의미하며, 그런 의미에서 도로 링크의 속도는 시공간적 자기 상관의 특성을 가진 데이터입니다. 구체적으로 도로 링크 속도의 시공간 자기 상관이라 함은 t시점의 r도로 링크의 속도 v를 예측할 때 r도로 링크 자신의 시간적 이웃 값(temporal lagged values, 과거 시점 a도로 링크의 속도)과 r도로 링크 주변의 공간적 이웃 값(spatial lagged values, 현재 및 과거 시점 r 도로 링크와 연결된 이웃 도로 링크들의 속도)들 간에 강한 상관관계가 존재하는 것을 의미합니다.
간단한 예를 들어 볼게요. 그림 1.처럼 매우 단순한 도로 네트워크를 가정해 보겠습니다. 도로의 진행 방향은 그림의 화살표 방향과 같으며, 표시된 도로 이외의 도로는 없다고 가정하겠습니다. r4 도로 링크의 t시점 속도는 r4 도로 링크의 t-1 시점 속도와 강한 상관관계가 있을 것입니다(그림의 빨간색 점선 화살표). 직전 시간에 막히던 도로는 지금 시간에도 막힐 것이며, 정체가 풀린다 하더라도 서서히 속도가 변화될 것입니다. 이것이 시간적 자기 상관입니다.
또한 r4 도로 링크의 t시점 속도는 연결된 도로인 r2 도로 링크 및 r3 도로 링크의 t시점(그림의 파란색 점선 화살표) 또는 그 이전 시점의 속도(그림의 초록색 점선 화살표)와 큰 관련이 있을 것입니다. r2 도로 및 r3 도로에서 교통량이 늘어나 속도가 줄게 되면 r4 도로로 진입하는 차량이 늘어나서 마찬가지로 속도가 줄어들 것이기 때문이죠. 이것이 공간적 자기 상관입니다. 꼬리에 꼬리를 무는 정체는 연결된 다른 도로로 전이될 수 있기 때문이죠. 물론 반대로 r4의 속도가 r2, r3로 영향을 끼칠 수도 있습니다.
그림 1. 단순 도로 네트워크 예시시공간 자기 상관이 강하게 존재하는 데이터의 분석은 반드시 이러한 데이터의 특성을 고려하여야 합니다. 이를 간과할 경우 분석의 결과는 그 신뢰성을 담보할 수 없는 경우가 많습니다. 이것은 회귀분석에서 가장 중요하고 영향력이 큰 변수를 빼고 결과를 도출한 것과 마찬가지며, 이때 추정된 회귀 계수는 신뢰성이 매우 낮아 바른 분석 결과라 보기 어렵습니다.
이에 따라 시간적 자기 상관과 공간적 자기 상관은 각각의 분야에서 많은 방법론들을 탄생시켰습니다. 시간 데이터를 다루는 시계열 분석 영역에서 Autoregression (AR), Moving Average (MA), Autoregressive Moving Average (ARMA), Autoregressive Integrated Moving Average (ARIMA) 등의 시간적 자기 상관(그림 2-a)을 고려하는 방법론들이, 공간 데이터를 다루는 공간 분석 영역에서 Simultaneous Autoregressive (SAR), Eigenvector Spatial Filtering (ESF) 등의 공간적 자기 상관(그림 2-b)을 고려하는 방법론들이 개발되고 검증을 거쳐 각각의 자기 상관이 존재하는 데이터의 분석에 활용되고 있습니다.
그림 2-(a) 시간적 자기 상관 데이터 예시1949년~1960년 월별 미국 항공기 승객 수 데이터, 계절에 따른 변화가 심하지만, 강한 시간적 자기 상관이 존재 (출처)
그림 2-(b) 공간적 자기 상관 데이터 예시미국 카운티별 35세 이상 성인의 심장병 사망 비율 (2017~2019), 중남부 지역 (오클라호마, 앨라배마, 루이지애나, 미주리, 오클라호마 등)에 비율이 높은 카운티가 몰려 있는 등 가까운 이웃의 값이 비슷한 강한 공간적 자기 상관이 존재 (출처)
Graph Neural Network (GNN)
시간과 공간의 자기 상관이 함께 존재하는 TMAP의 도로 링크 속도 데이터의 경우 기존에 개발된 방법론들을 적용하여 분석하기 어렵습니다. 그리고 서로 다른 기저의 두 자기 상관을 동시에 처리할 수 있는 전통적인 통계적 방법은 없습니다. 그래서 저희는 인공지능과 기계 학습의 힘을 빌려 이 문제를 해결해왔고, 더욱더 다듬어 나가고 있습니다.
그래프는 도로 네트워크를 표현할 수 있는 가장 좋은 방법 중에 하나입니다. 절대적인 도로 링크의 위치보다는 다른 도로 링크와의 연결에 관한 정보가 중요하고, 복잡한 도로 네트워크를 단순화 한 표현이 가능하기 때문입니다. 또한 다양한 GNN 방법론들을 이용하여 시공간 자기 상관을 고려한 분석이 가능합니다.
예를 들어 convolution in temporal dimension을 통해 시간적 자기 상관을, graph convolution in spatial dimension을 활용하여 공간적 자기 상관을 고려할 수 있습니다. 여기에 attention mechanism 혹은 phased LSTM 등을 활용하여 도로 링크의 시간적, 공간적 차원에서의 차별적인 정보 전달 또한 구현 가능합니다. 즉, 보다 가까운 도로 링크의 가중치를 크게 준다든가, 멀리 떨어진 시간이지만 관계가 높을 것으로 예상되는 시점(e.g., 이전 주 같은 요일)의 가중치를 크게 주는 것이지요.
그림 3그림 3. GNN을 이용한 시공간 자기 상관 분석 모식도, 같은 시점의 그래프 구조를 통해 공간적 자기 상관을, 연속된 시점의 도로 링크 값에서 시간적 자기 상관을 고려할 수 있음 (출처)
사용자가 지나게 될 도로 링크의 미래 시점 예상 속도 값을 종속 변수로 상정하고, 해당 도로 링크의 과거와 현재 속도 값, 이웃 도로들의 과거와 현재 속도 값들, 그리고 속도에 영향을 줄 것으로 판단되는 TMAP의 각종 데이터들을 독립 변수로 정한 후 다양한 GNN 방법론들을 활용 중에 있습니다. 현재는 실시간 교통 정보 수집에 어려움을 겪고 있는 GPS 음영 지역(e.g., 터널) 및 단순한 도로 네트워크(i.e., 진출입이 적은 고속도로) 들을 대상으로 GNN의 초기 모델을 세우고 검증하는 단계입니다만, 하루빨리 더 정확한 모델을 만들어 언제 어디서나 누구보다 정확한 당신의 목적지 예상 도착 시간 안내를 위해 매일매일 최선을 다하는 TMAP이 되겠습니다. 감사합니다.
