DTW(Dynamic time wrapping) - 동적시간와핑

이번 포스팅에서는 DTW(Dynamic time wrapping)인 동적 시간 접합에 대해 알아보도록 하겠습니다. Warping이라는 사전적 뜻에서도 알 수 있듯이 DTW는 속도나 길이에 따라 움직임이 다른 두개의 시계열 데이터가 주어졌을 때, 그 둘의 유사도를 알아낼때 사용되는 방법중 하나라고 생각하면 될것 같습니다.

 

일반적으로 두 시계열 데이터의 유사도를 구할때 사용하는 척도인 euclidean distance를 사용하게되면 같은 timeline 선상에 위치한 데이터를 기반으로 계산하게되는데, 이렇게 되면 데이터의 신호의 떨림이나 움직임이 심해지게되면 유사성을 찾기 힘드며, 무엇보다 길이가 다른 시계열은 유사도를 측정할 수 없다는 단점이 존재합니다. 비록 euclidean distance를 통해 시계열의 길이를 자르거나 늘려서 두 시계열간의 유사도를 구할수는 있지만 이점 역시 한계점이 존재합니다.

이러한 문제를 해결하기위해 동일한 시간선상의 데이터 이외에 주변 시점의 데이터를 활용하여 비교한뒤 더 비슷한 요소와 매칭하자 라는 아이디어로 부터 출발한 DTW를 사용하여 두 개의 시계열 간의 유사도를 측정 할 수 있습니다. 즉 DTW는 속도나 길이가 다른 두 시계열의 유사도를 측정하는 알고리즘이라고 할 수 있습니다. 예를들어 두명의 사람이 있다고 가정한 뒤, 두 사람의 걸음걸이에 대해 유사도를 측정할때 사용 할 수 있습니다. 이를 파이썬 코드로 구현하면 아래와 같습니다.

import numpy as np

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

dummy1 = [1, 2, 3, 3, 4]
dummy2 = [1, 2, 2, 3, 3, 4, 4, 5, 5, 5]

dtw(dummy1, dummy2, window = 3)
>>> array([[ 0., inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
     	  [inf,  0.,  1.,  2.,  4.,  6.,  9., inf, inf, inf, inf],
          [inf,  1.,  0.,  0.,  1.,  2.,  4.,  6., inf, inf, inf],
          [inf,  3.,  1.,  1.,  0.,  0.,  1.,  2.,  4., inf, inf],
          [inf,  5.,  2.,  2.,  0.,  0.,  1.,  2.,  4.,  6., inf],
          [inf,  8.,  4.,  4.,  1.,  1.,  0.,  0.,  1.,  2.,  3.]])

또한 fastdtw 패키지를 통해 DTW를 사용할 수 있습니다. fastdtw의 경우 pypi를 따르고 있기때문에 pip을 통해 쉽게 설치가 가능합니다.

! pip install fastdtw

fastdtw

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean

dummy1 = np.array([1, 2, 3, 3, 7])
dummy2 = np.array([1, 2, 2, 2, 2, 2, 2, 4])

distance, path = fastdtw(dummy1, dummy2, dist=euclidean)

print(distance)
print(path)

>>> 5.0
>>> [(0, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 7), (3, 7), (4, 7)]