DTW 기본 설명 및 실습코드

DTW(Dynamic Time Warping)은 동적 시간 워핑이라고 불린다.

두개의 시계열 데이터가 서로 얼마나 유사한지 비교할 때 사용한다.

 

DTW를 사용하는 이유?

- 두개의 시계열 데이터 길이가 달라도 유사도 비교 가능

- 비슷한 패턴이지만 시간차가 있는 경우(shift 발생) 유사도 비교 가능

 

 

 

 

 

DTW 계산방법 이론

공식으로 보는 방법도 있는데 예시를 들어서 계산하는게 더 이해가 잘 된다.

이론적인 설명 이후에 예시를 들어서 직접 계산해보도록 하자.

 

시계열 데이터 2개가 있다.

두 시계열의 길이 n, m은 길이가 같을 수도 있고 다를 수도 있다.

 

이 두개의 시계열을 나열하여 n x m 행렬을 만든다.

유클리드거리를 이용하여 최적의 와핑 경로를 탐색한다.

와핑경로는 두개의 시계열 데이터 P와 Q 사이의 맵핑을 나타내는 와핑 거리의 집합이며, 연속적이여야한다.

 

• boundary conditions : 와핑집합의 첫번째와 마지막은 이어져야한다.
• continuity : 와핑경로는 대각 요소를 포함한 인접한 셀로 제한된다.
• monotonicity : 와핑경로는 음의 방향으로 이동하지 않는다.

이 세가지 조건을 만족하는 셀들 중 와핑거리합이 최소가 되는 경로를 찾으면 된다.

와핑거리의 합은 와핑경로비용 이라고 부르기도 한다.

와핑경로는 위와 같은 공식으로 찾으면 되는데 미지수들로 이루어져 있어 보기 힘들다면 실제 계산으로 쉽게 이해할 수 있다.

 

DTW 계산방법 실습코드

DTW를 사용할 수 있는 패키지는 dtaidistance와 dtw-python 이 있다.

내가 dtw-python 계산식을 못찾아서 적용을 못해봤다.

같은 데이터이지만 distance 값이 다르게 나와서 내가 계산식을 이해한 dtaidistance 패키지를 사용했다.

 

# 패키지 설치
# pip install dtaidistance

import numpy as np
import pandas as pd
from dtaidistance import dtw

 

데이터 만들기

실습에 사용할 데이터가 있다면 불러오기를 해도 되고, 없다면 간단하게 리스트로 만들어도 된다.

a = [1, 2, 5, 7, 4, 3, 6, 8, 2, 1]
b = [3, 6, 1, 2, 8, 9, 3, 4, 3, 2, 1, 2]
c = [2, 5, 7, 4, 3, 6, 8, 2, 1, 1]

a가 빨간선, b가 노란선, c가 보라색 선이다.

a와 b는 길이가 다르고

a와 c는 패턴을 비슷하지만 시간차가 있다.

 

행렬만들기

먼저 a, b에 대한 행렬을 만들어 준다.

 

계산식 = (a1 - b1)의 제곱 + min(인접셀 3개)

 

> (1, 1) 자리 계산

(1, 1) 자리에는 첫번째 요소들의 차의 제곱값을 적어준다.

(a의 첫번째 요소인 1 - b의 첫번째 요소인 3)의 제곱 = 4

 

> 행, 열 첫번째 줄

(1, 2) 부터는 이전 셀 + 두번째요소들의 차 로 계산해서 넣어주면 된다.

(1, 2)

=(1, 1)의 값 4 + (a의 두번째 요소 2 - b의 첫번째 요소 3)의 제곱

= 4 + 1

= 5

 

(1, 3)

= (1, 2) 의 값 5 + (a의 세번째 요소 5 - b의 첫번째 요소 3)의 제곱

= 5 + 4

= 9

 

이런식으로 한줄씩 채워가면 되고, 세로줄의 경우도 마찬가지로 계산해주면 된다.

(2, 1)

= (1, 1) 의 값 4 + (a의 첫번재 요소 1 - b의 두번째 요소 6)의 제곱

= 4 + 25

= 29

 

 

 

 

 

 

 

> 행, 열 두번째줄 이상

(2, 2)부터는 인접한 셀 값들 중 가장 작은 값을 사용한다.

(2, 2)를 감싸고 있는 인접한 셀은 (1, 1)=4, (1, 2)=5, (2, 1)=29이다.

 

(2, 2)

= (a의 두번째 요소 2 - b의 두번째 요소 6)의 제곱 + 인접셀 중 가장 작은 값

= 16 + 4

= 20

 

(2, 3)

= (a의 세번째 요소 5 - b의 두번재 요소 6)의 제곱 + 인접셀 중 가장 작은 값 5

= 1 + 5

= 6

 

 

 

최적의 와핑 경로 찾기

최적의 와핑경로는 마지막 셀에서 작은 숫자로 역추적 하는 방법을 사용한다.

 

최종 와핑 경로 비용 DTW

와핑경로비용은 마지막 값에 루트를 씌운 값이다.

DTW

= sqrt(28)

= 5.29...

 

from dtaidistance import dtw

a = [1, 2, 5, 7, 4, 3, 6, 8, 2, 1]
b = [3, 6, 1, 2, 8, 9, 3, 4, 3, 2, 1, 2]

distance = dtw.distance(a, b)
print(distance)

>> 5.291502622129181

동일하게 5.29가 나오는 것을 확인할 수 있다.

distance 값이 작을수록 기준이 되는 a값과 유사도가 높다고 분석한다.

 

from dtaidistance import dtw_visualisation as dtwvis

dtwvis.plot_warping(a, b, path = dtw.warping_path(a, b))

 

 

 

a와 c를 DTW를 구해보자

 

a와 c의 경우 시간차이만 있을 뿐 패턴은 비슷하게 진행된다.

이를 유클리드 거리로 측정할 경우 시간차이가 있기 때문에 그리 유사하다고 나오지는 않는데

DTW의 경우에는 이 시간인덱스를 감안해서 계산하기 때문에 distance가 1이 나왔다.

 

from dtaidistance import dtw

a = [1, 2, 5, 7, 4, 3, 6, 8, 2, 1]
c = [2, 5, 7, 4, 3, 6, 8, 2, 1, 1]

distance = dtw.distance(a, c)
print(distance)

>> 1.0

 

from dtaidistance import dtw_visualisation as dtwvis

dtwvis.plot_warping(a, b, path = dtw.warping_path(a, b))

DTW 분류

실제 데이터를 가지고 분석을 해본 결과다

출처 kubwa_ian

위 표와 같이 DTW 거리에 따른 분류 및 차이를 확인할 수 있다.

 

 

참고

https://syj9700.tistory.com/58