Dynamic Time Warping (DTW) with trajectory data 시계열 분석

source: https://rtavenar.github.io/blog/dtw.html

DTW

개요

- 두 개의 입력 시계열 간의 거리 메트릭을 생성한다.

- 데이터를 벡터로 변환하고 벡터 공간에서 해당 지점 간의 유클리드 거리를 계산하여 계산하여 두 시계열의 유사성 계산한다.

- 첫 번째와 마지막 포인트를 포함한 모든 포인트가 각각 연결되어야 한다.

 

계산 방법

1. DTW 그리드를 만든다.
2. 각 그리드 내부에 두 시계열의 거리 측정값(e.g. absolute differences)이 들어간다.
3. total distance를 최소화하는 그리드를 통과하는 경로를 찾는다.

(source: Yuan, Y., & Raubal, M. (2012))

 

수식

$P=\{p_1, p_2, ..., p_m\}$, $Q=\{q_1, q_2, ..., q_m\}$ 이라는 두 시계열 데이터가 있을 때, $P$와 $Q$ 사이의 DTW 거리는 다음과 같다.

$$D(P,Q)=dist(p_1,q_1)+min\left\{\begin{array}{rl}& D(Re(P),Re(Q))\\ & D(Re(P),Q)\\ & D(P,Re(Q))\end{array}\right\}$$

이때, $D$는 $P$와 $Q$ 사이의 거리, $dist(p_1, q_1)$는 두 점 사이의 유사도, $Re(P)$와 $Re(Q)$는 각각 첫 번째 point를 제거한 후의 시퀀스를 나타낸다. 각 point끼리 DTW 합이 작을수록 유사도가 높아진다.