Brain's Pick
[TGNet] 1.택시 수요 예측 모델 연구 동향을 소개합니다
2018/12/06 by 이수경 이도엽

택시 수요 모델을 만든 이유

우버(Uber), 디디(Didi), 리프트(Lyft), 카카오택시와 같은 라이드 헤일링 서비스(ride hailing service)[1]가 도시인의 라이프스타일에서 필수적인 요소로 자리매김하고 있습니다. 길 위에서 기다리는 대신 모바일 앱을 켜서 출발지와 도착지를 입력하기만 하면 택시를 호출하거나 카풀 서비스를 이용할 수 있습니다. 요금은 앱에 미리 등록한 카드로 간편하게 결제할 수 있습니다. 나를 태우고 갈 차량이 어디쯤 왔는지 그 위치도 실시간으로 확인할 수도 있죠. 이런 편의성 덕분에 라이드 헤일링 서비스가 뜨게 된 것으로 분석됩니다.

[ 그림 1 ] 라이드 헤일링 서비스를 이용하면 자신이 원하는 시간, 원하는 장소에서 이동 수단을 호출할 수 있다. ©카카오브레인 김강희

이처럼 도시인들이 일상에서 라이드 헤일링 서비스를 이용하게 됨에 따라 하루에도 수십만 건의 사용자 이용 데이터가 축적되고 있습니다. 이 데이터는 (출발시간, 출발지) - (도착시간, 도착지)와 같은 시공간 정보(spatiotemporal information)를 담고 있습니다. 이 정보를 통해 우리는 [표 1]에서처럼 이동 정보에 관한 3가지 특징을 알 수 있습니다.

[ 표 1 ] 시공간 데이터에서 알 수 있는 3가지 특징

카카오브레인과 카카오모빌리티는 이런 시공간 정보를 활용해 공급자(택시 기사)와 수요자(택시 승객)를 모두 만족할 방법을 고민해보기로 했습니다. 공동 연구팀은 택시 공급과 수요의 균형을 맞추는 것이야말로 고객이 원하는 핵심적인 가치라고 판단했습니다. 승차 수요가 발생할 것으로 예상되는 장소와 시간에 택시를 적절하게 배치한다면 기사는 더 많은 승객을 태울 수 있게 되리라 생각했습니다. 아울러 승차 수요가 과잉되는 시간과 장소에 택시를 충분히 공급한다면 승객에게는 이동에 있어서 편리성을 줄 수 있겠다 싶었습니다.

그렇다면 수요-공급 간 불균형 문제는 어떻게 해결할 수 있을까요? 여기에는 2가지 방법이 있습니다.

① 수요가 없는 지역에서 활동하는 택시를 수요가 많거나 많을 것으로 예상되는 지역에 택시를 재배치(redistribution)합니다.

② 택시 수요는 많으나 공급이 적은 지역에서는 택시 요금을 올리는 가변 가격제(dynamic pricing)를 적용합니다.

이 2가지 방법을 적용하기 위해서는 우선 어느 시간대에, 어느 지역에 수요가 발생할지 미리 알아야 합니다. 카카오브레인(이도엽, 정수헌, 천영재)과 카카오모빌리티(김동일, 유승일)가 택시 수요를 예측하는 모델을 만들기로 한 배경입니다. 공동 연구팀이 고안한 택시 수요 모델인 TGNet은 신경정보처리시스템학회(NeurlPS)[2] 워크숍 주제 중 하나인 ‘시공간 영역에서의 모델링과 의사결정(Modeling and decision-making in the spatiotemporal domain)’에 승인됐습니다(accepted). TGNet 아키텍처 및 성능에 관한 부분은 2편에서 자세히 소개해 드리겠습니다.


주요 선행 연구를 소개합니다

공동 연구팀은 선행 연구를 살펴봤습니다. 최근 전미인공지능학회(AAAI)[3]나 KDD[4]를 중심으로 도시의 택시나 교통량을 예측하는 연구가 활발하게 이뤄지고 있으며, 우버와 디디와 같은 거대 모바일 플랫폼 기업에서도 관련 연구를 활발하게 진행하고 있음을 확인할 수 있었습니다. 또한, 딥러닝을 이용한 모델이 기존 통계 모델보다 더 나은 성능을 보임을 알 수 있었습니다. 이번 글에서는 연구팀이 분석한 최신 논문 중 연구 방향성을 설정하는 데 큰 영향을 미친 AAAI 3편의 연구를 소개하고자 합니다.


(1) DeepST: DNN-based prediction model for spatio-temporal data

DeepST는 마이크로소프트(Microsoft)에서 제안한 모델로, 아키텍처([그림 2])는 정말 간단합니다. 이미지 형식으로 전처리(pre-processing)된 데이터를 컨볼루션 층(convolution layer)[5]에 입력해 시공간적 특징을 추출하고 선형 회귀(linear regression)[6]로 구성된 출력층(output layer)에서 다음 시간대에서의 택시 수요를 예측합니다. 마이크로소프트 연구팀은 이후 컨볼루션 층을 res block[7]으로 대체해 그 성능을 한 단계 더 발전시킨 모델을 선보였습니다.

[ 그림 2 ] DeepST 아키텍처

DeepST의 특징은 다음과 같습니다. 첫 번째, 시공간적으로 유의미한 상관관계를 추론했습니다. 이를 위해 DeepST는 로그(log)[8] 형태의 택시 수요 데이터를 그리드(grid)[9] 배열의 이미지 형식으로 전처리했습니다. 그 결과, [그림 3]처럼 특정 시간대에 특정 지역(그리드 셀)에서 발생하는 택시 수요를 보다 직관적으로 알 수 있습니다. 컨볼루션 네트워크는 이 이미지에서 특정 시간, 특정 지역의 택시 수요는 주변 지역에서 발생하는 수요와 연관됨을 학습합니다.

[ 그림 3 ] DeepST에서는 이미지 형태로 전처리된 데이터를 학습한다

두 번째, DeepST는 특정 시간대마다 반복되는 패턴을 고려했습니다. 가장 기본적인 시계열 모델에서는 인접 시간대(4시간) 데이터를 수요 예측에 활용합니다. 예를 들어, 현재 시각(오후 8시)을 기준으로 30분 후의 수요를 알고자 한다면 오후 7시 30분, 오후 7시, … , 오후 3시 30분, 오후 4시의 수요 패턴을 활용하는 거죠. 물론 인접 시간을 보는 것만으로는 특정 기간마다(periodicity), 주기마다(seasonality) 반복되는 유사 패턴까지는 파악하기가 어렵습니다. 이에 DeepST는 인접 시간, 하루 단위・주 단위 과거 데이터별로 얻은 특징 맵(feature map)[10]을 합칩니다(fusion).

세 번째, ‘날씨’라는 외부 정보를 활용해 예측력을 높였습니다. 비나 눈이 내리는 기상 변화에는 특이 수요가 발생한다는 점을 고려했다고 볼 수 있습니다. 다시 정리하자면, DeepST는 컨볼루션 층에서 추출된 과거 수요 패턴의 최종 특징 맵에 날씨 정보를 더해 미래 수요를 예측했습니다.


(2) DMVST-Net: Deep multi-view spatial-temporal network for taxi demand prediction

DMVST-Net은 펜실베니아 주립 대학교(Pennsylvania State University)의 화시우 야오(Huaxiu Yao)가 제안한 모델로, 디디가 보유한 중국 광저우시 택시 수요 데이터를 활용했습니다. 글의 서두에서 밝힌 3가지 특징(공간적, 시간적, 의미론적 맥락)을 추출하는 데 각기 다른 모델을 이용했습니다. 인접 지역 사이의 공간 맥락의 특징을 추출하는 데는 local CNN(a), 시간 맥락 특징 추출에는 LSTM[11](b), 의미론적 맥락에서 특징을 추출하는 데는 그래프 임베딩(graph embedding)[12](c)이 활용됐습니다([그림 3]).

[ 그림 4 ] DMVST-Net 아키텍처

DMVST-Net의 local CNN은 전체 이미지가 아닌 작은 이미지를 활용합니다. 좀 더 자세히 설명하면 다음과 같습니다. 학습에 이용되는 이미지의 그리드 배열은 20행×20열입니다. Local CNN에서는 [그림 5]처럼 각각의 그리드 셀을 중심으로 7행×7열의 작은 이미지를 만드는 전처리 작업을 진행합니다. 특정 그리드와 멀리 떨어진 그리드는 수요 예측 면에서 연관 관계가 거의 없다고 판단해 그리드를 중심부로 놓고 가까운 주변 지역만을 살펴본 거죠. local CNN은 이렇게 전처리된 400장의 작은 이미지를 입력받아 특징 맵을 출력합니다. 기존 CNN[13]과 비교하면 계산적인 기법이 다르지는 않습니다. 다만 입력되는 이미지가 각 그리드를 중심으로 작게 자른 이미지를 활용한다는 점에서 네트워크에 ‘local’이라는 이름이 붙었습니다.

[ 그림 5 ] DMVST-Net의 local CNN에서 그리드를 중심으로 크로핑하는 과정

LSTM에서는 시간 맥락을 파악합니다. 30분 간격으로 추출된 local CNN 특징 맵과 날씨 데이터, 이벤트 데이터 등을 LSTM에 입력합니다. 이로써 Local CNN과 LSTM를 이용해 각각 지역적, 시간적 맥락 특징을 추출했습니다.

이제 의미론적 맥락을 파악하는 일이 남았죠. 주거 지역 또는 상업 지역에 따라 달라지는 특성을 파악하는 일은 그리드 셀 사이 수요 패턴의 유사도를 알면 해결할 수 있습니다. 우선 그리드 셀별 주간 평균 수요 패턴을 계산한 뒤, 그리드 셀의 유사도를 0과 1 사이 실수값으로 표현합니다. 그리고 대표적인 그래프 임베딩 방법인 LINE을 통해 특징 벡터(feature vector)[14]를 얻습니다. 이 특징 벡터와 LSTM의 결과를 FC(fully connected layer)에 함께 입력하면 다음 30분 후의 택시 수요를 예측할 수 있습니다.

그 결과, DMVST-Net은 기존 통계 모델과 딥러닝 모델, ST-ResNet(DeepST의 발전 모델)보다 더 좋은 성능을 내는 것으로 나타났습니다. 시공간・의미론적 맥락이 택시 수요 예측에 중요하다는 통찰력을 줬다는 점에서 의의가 있는 연구라고 할 수 있겠습니다.


(3) STDN: Modeling spatial-temporal dynamics for traffic prediction

DMVST-Net의 후속 연구인 STDN은 뉴욕시 택시 데이터를 활용한 모델입니다. STDN의 local CNN은 DMVST-Net과 동일합니다만, 다른 게 하나 있습니다. 바로 입력 데이터의 범위입니다. DMVST-Net에서는 택시 수요를 알고 싶은 시점에서의 과거 4시간의 데이터만 예측에 활용했습니다. 반면, STDN은 전날, 전전날, 1주일 전과 2주일 전과 과거 같은 다른 날짜의 같은 시간대의 데이터도 활용합니다.

입력 데이터가 넓어짐에 따라 STDN에서의 학습은 더 어려워졌습니다. 입력되는 데이터의 시간 범위가 넓어짐에 따라 LSTM의 길이가 늘어나면서 미분값 소멸(gradient vanishing)[15]이 심화됐기 때문입니다. 주기성이 발생하는 시간대가 옮겨지는 현상(temporal shifting of periodicity)[16]도 학습의 복잡도를 높이는 데 영향을 줍니다. 이에 연구진은 시간 주의(temporal attention) 방식인 PSAM(periodically shifted attention mechanism)으로 집중해야 할 시간대를 학습시킴으로써 문제를 해결했습니다.

[ 그림 6 ] STDN 아키텍처

한편, 이 모델은 여러 개의 태스크(task)를 동시에 학습해 예측모델의 성능을 높이는 방법인 다중작업 학습(multi-task learning)을 활용했습니다. 어떤 지역에서 발생하는 택시 수요량이 어떤 지역으로 이동하는 택시 수와 서로 연관이 있다고 봤을 때 두 태스크에서 공통적으로 중요한 변수를 선택해 모델을 구축할 수 있다면 예측 성능이 높아지리라고 판단한 것으로 보입니다. 이에 연구진은 과거 데이터로부터 택시 수요를 예측하는 것뿐만 아니라 지역별로 얼마나 많은 택시가 도착하는지도 함께 예측했죠. 차량 흐름(traffic flow)[17] 데이터도 학습에 활용됐습니다. 그 결과, 뉴욕시 택시 데이터를 기준으로 했을 때 STDNDMVST-Net보다 SOTA(state-of-the-art, 현재 최고 수준의) 성능을 냈습니다.

카카오브레인과 카카오모빌리티가 제안한 택시 수요 예측 모델인 TGNet에 대한 자세한 이야기는 2편에서 이어서 하겠습니다.


참고
[1] 특정 지역으로 이동하고 싶은 사람과 이동 서비스를 제공하고 싶은 사람을 연결해주는 플랫폼
[2] Neural Information Processing Systems의 약자. 기계학습 국제컨퍼런스(International Conference on Machine Learning, ICML)과 더불어 AI 연구 결과가 발표되는 대표적인 학회로 꼽힌다.
[3] Association for the Advancement of Artificial Intelligence의 약자.
[4] Knowledge Discovery and Data Mining의 약자. ACM 주최로 열리는 학회로, 데이터마이닝 및 인공지능 분야 관련 연구를 다룬다.
[5] 이미지에서 숨은 특징을 추출하는 층
[6] 종속 변수 y와 한 개 이상의 독립 변수 x와의 선형 상관 관계를 모델링하는 회귀분석 기법
[7] ResNet(Deep residual networks)에서 제안된 블록. CNN 아키텍처에서는 층이 깊어질수록 역전파 시 기울기가 소실되는 문제가 발생한다. 이에 지름길(shortcut, skip connection) 구조를 활용해 기울기가 잘 전달될 수 있도록 했다.
[8] 시간에 따라 기록되는 사용자의 행위나 이벤트 정보
[9] 일정한 간격으로 가로세로를 나눈 것
[10] 컨볼루션 연산으로 얻는 결과
[11] long short term memory의 약자. RNN의 셀(cell)을 세 가지 게이트로 구성된 메모리 블록(memory block)으로 대체한 구조를 가리킨다. 이전 상태에서 넘어온 새로운 정보를 얼마나 반영할지(output gate), 어떤 정보를 얼마나 입력할지(input gate), 어떤 정보를 얼마나 출력할지(forget gate)를 가중치를 통해 결정한다. 이는 가장 기본적인 구조이며, 모델마다 그 구조가 조금씩 다르다.
[12] 그래프의 노드와 연결 사이의 관계를 고려해 노드를 연속된 벡터 공간의 점으로 변환하는 기법
[13] 이미지의 공간 정보를 유지하면서 특징을 효과적으로 인식하고 강조하는 딥러닝 모델. 특징을 추출하는 영역은 컨볼루션 층은 풀링 층로 구성된다. 컨볼루션 층은 필터(filter)를 사용해 공유 파라미터 수를 최소화하면서 이미지의 특징을 찾는다. 풀링 층은 특징을 강화하고 모은다.
[14] 차원을 가진 벡터로 특징을 표현하는 것
[15] 역전파 알고리즘에서는 낮은 층으로 갈수록 전파되는 오류(error)의 양이 적어진다. 이로 인해 미분값의 변화가 거의 없어져 학습이 제대로 일어나지 않는다. LSTM에서는 체인의 길이가 길어서 앞쪽 정보가 제대로 학습이 이뤄지지 않는다.
[16] 예를 들어, 한 주를 기준으로 했을 때 오전 시간 수요 피크는 매일 다른 시간대(7시부터 9시)에 발생한다.
[17] 일정 시간 특정 지역에서 차량이 몇 대나 들어왔고 나갔는지와 같은 차량의 흐름을 보여준다.
이 글을 쓴 사람들
samantha.lee
이수경 | samantha.lee@kakaobrain.com
2016년 3월 알파고와 이세돌 9단이 펼치는 세기의 대결을 두 눈으로 목도한 이후 인공지능을 제대로 공부해봐야겠다고 결심했습니다. 인공지능 본진이자 연구소인 카카오브레인으로 걸어들어온 이유죠. 인공지능 기술과 이로 인해 바뀔 미래 사회를 다루는 글을 통해 사람들과 소통하고자 합니다.
damien.lee
이도엽 | damien.lee@kakaobrain.com
인공지능 기술이 세상을 밝고 행복하게 만들어주길 기대하며 매일 조금씩 성장해나가고 있습니다. 카카오브레인에서 시계열 데이터와 이상 탐지를 연구하고 있습니다. 사람이 해결하지 못한 문제를 푸는 인공지능을 통해 더욱 윤택하고 안전한 인간 세상을 만드는 데 일조하고자 합니다.