[논문 리뷰] A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip

이번에 리뷰할 논문은 디디추싱(DiDiChuXing)에서 발표한 A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip 이라는 논문입니다. 위 논문에서는 Taxi Trip의 이동 시간과 이동 거리를 동시에 예측할 수 있는 모델인 ST-NN(Spatio-Temporal Neural Network)에 대해서 소개하고 있습니다.

1. Abstract

• ST-NN은 출발지와 목적지 사이의 이동 거리를 먼저 예측한 다음, 이를 시간 정보와 결합하여 이동 시간을 예측한다.
• Feature Engineering없이 출도착지의 GPS Point와 시간 정보만을 활용하여 이동 시간과 거리를 동시에 예측 할 수 있다.
• Taxi trip의 경우 교통 이상, 차량 경유와 같은 예기치 못한 상황이 많이 발생합니다. ST-NN은 이와 같은 이상치(outlier)에 강건하다.

2. Problem Definition

2.1 문제 정의

2.1.1 예측 변수 정의

• 이동 시간(Travel time): 차량이 한 위치에서 다른 위치로 이동하는 시간
• 이동 거리(travel distance): 차량이 한 위치에서 다른 위치로 이동한 거리

2.1.2 해결 문제

• 특정 시간(t)에서 출발지(o)와 목적지(d) 사이의 이동 거리 및 이동 시간을 추정하는 것

2.1.3 데이터 정의

• Taxi trip을 5-tuple로 나타낼 수 있다: (출발지 위치, 도착지 위치, 출발 시간, 이동 거리, 이동 시간)
• 이중 출발지와 도착지의 위치 정보는 위도, 경도의 2-tuple로 나타내진다.
• 데이터셋을 구성할 때 출발 시간을 추가한 이유는 시간대에 따라 교통 상황이 다르기 때문이다.

2.2 Data Mapping

2.2.1 위치 데이터 (출도착지)

• 지리 좌표(Geo-Coordinates)는 여러가지 이유로 수집된 데이터가 정확하지 않을 수 있다. 따라서 위치 데이터의 불확실성을 처리해주기 위해 모델링에 앞서 데이터를 전처리해야 한다.
• GPS 좌표를 아래 그림과 같이 2-D의 사각셀의 왼쪽 모서리로 매핑했다.
• 한 셀의 길이는 200m이다.
  

  

2.2.2 시간 데이터(출발 시간)

• 위치 데이터와 마찬가지로 우리는 또한 하루의 시간을 1-D 시간 셀로 처리해줬다.
• 하루를 10분 단위로 나누면 총 144개의 시간 셀을 만들 수 있다.
• 아래의 EDA결과를 보면 주말과 평일의 택시의 평균 이동시간이 다른 것을 확인할 수 있다.
  

  

• 따라서 위의 144개의 시간셀을 주말과 평일을 구분하여 시간 데이터를 최종적으로 총 288개의 Time binning 데이터로 나타냈다.
  

  

3. Proposed Approach

3.1 STNN

• 아래의 그림은 STNN의 아키텍처이다. 모델은 크게 이동 거리를 예측하는 Dist DNN Module과 이동 시간을 예측하는 부분인 Time DNN Module으로 구성되어 있다.
  

  

3.1.1 Dist DNN Module

• Dist DNN Module은 GPS position binning 데이터만 입력으로 들어간다.
• 이동시간을 예측할 때는 출발시간에 따른 영향이 있을 수 있지만 이동거리는 언제 출발하든 같기 때문에 출발 시간과 같은 시간 데이터를 넣는 것은 오히려 모델 학습에 방해가 될 수 있다.
• 또한 직관적으로 생각했을 때도 Taxi Driver들은 언제든지 최단거리로 이동한다.
• Dist DNN Module의 입력 차원은 출발지와 도착지의 위도경도인 4-D이다.

3.1.2 Time Dnn Module

• Time Dnn Module의 입력은 Time binning 데이터와 Dist DNN Module의 마지막 레이어이다.

4. Experiments and results

4.1 NYC Dataset

• 173M taxi trip data
• 전체 taxi trip의 80%가 이동 시간 20분 이하, 60%가 이동 거리 2mile 이하

4.2 Evaluation Methods

• 비교한 모델은 아래와 같다.
  • Linear Regression for Time (LRT): 2-D GPS square cell + 1-D time cell & Linear Regression
  • Linear Regression for Time (LRD): 2-D GPS square cell & Linear Regression
  • TimeNN: 2-D GPS square cell + 1-D time cell & Time DNN Module
    

    

  • DistNN: 2-D GPS square cell & Distance DNN module
    

    

  • STNN: stochastic gradient descent jointly
    

    

  • BTE: 위 논문에서 비교 대상으로 삼은 다른 모델

4.3 Outliers Rejection

• Taxi trip 데이터의 특징은 몇몇 이상치(outlier)가 존재한다.
• (블로그 필자의 경험이지만) 라이드 헤일링 데이터의 특징은 드라이버가 특정 루트를 경유해서 가는 경우, 다수의 고객이 동승을 해서 중간에 몇몇 인원을 내려주는 경우와 같은 변수가 존재한다.
• 또한 예상 이동 시간과 예상 이동 거리는 날씨, 교통상황에도 많은 영향을 받는다.
• 본 논문에서는 정확한 비교 분석을 위해 이와 같은 이상치를 제거한 뒤 학습을 진행했다.

4.4 Performance evaluation

• MAE (Mean Absolute Error)
• MRE (Mean Relative Error)
• MedAE (Median Absolute Error) : 데이터 셋이 이상치를 포함하고 있어서 사용
• MedRE (Median Relative Error) : 데이터 셋이 이상치를 포함하고 있어서 사용
• R2

4.5 Results

4.5.1 이동 시간

• STNN > TimeNN > LRT 순으로 성능이 좋다.

• Actual Travel Time이 늘어날수록, 즉 장거리로 이동할 수록 MAE가 커지는 것을 확인할 수 있다.
• 짧은 운행 건에 대해서는 높은 성능을 보이지만 장거리 운행건에 대해서는 약 8~10분 정도 오차가 존재하는 것을 확인할 수 있다.

4.5.2 이동 거리

• STNN > TimeNN > LRT 순으로 성능이 좋다.
  

  

• 이동거리를 예측할 때도 거리가 택시 운행 거리가 멀어질수로 MAE가 증가하는 것을 확인할 수 있다.
  

  

4.5.3 이상치 강건함 테스트

• 이상치 포함여부에 따라서 ST-NN과 BTL을 비교한 결과 ST-NN은 이상치를 학습에 포함시켰어도 MAE기준으로 약 2초의 오차만 발생했다.
• 보통 taxi trip 데이터에서 이상치를 완벽하게 제거하는 것은 상당히 까다로운 작업인데 ST-NN은 이상치에 매우 강건한 것을 확인할 수 있다.
  

  

4.5.4 모델 성능 비교 (평일 vs 주말)

• 아래의 그래프에서 빨간색 점선 왼쪽은 평일 오른쪽은 주말의 모델 성능이다.
• 평일의 경우 Predicted Travel Time이 Actual Travel Time을 잘 따라가는 경향이 있는데, 실제 이동 시간을 성공적으로 예측하는 것을 확인할 수 있다.
• 반면, 평소와 다른 교통 패턴이 있는 늦은 시간대에는 ST-NN이 평일에 비해 시간적 패턴을 효율적으로 포착할 수 없는 것을 확인할 수 있다.
  

  

5. Summary

• ST-NN은 Taxi trip의 이동거리, 이동시간을 동시에 예측하도록 고안된 Deep Learning 모델이다.
• 출발지, 도착지, 시간 정보만을 활용하여 모델링을 할 수 있다.
• 이동거리, 이동시간을 각각 예측하는 것보다 이들을 jointly 하게 학습 및 예측하는 것이 더 좋은 성능을 보였다.
• Taxi trip의 경우 많은 이상치가 발생할 수 있는데 ST-NN은 이상치에 강건하다.
• 이동 시간을 예측할 대 평일의 경우 실제 패턴을 잘 따라가는 경향이 있다. 하지만 늦은 시간대에는 시간적 패턴을 효율적으로 포착할 수 없다.