DTW(Dynamic Time Warping)

안녕하세요!

이번 시간에는 DTW에 대해 포스팅 했습니다.

아마 시계열 데이터를 전처리하다보면 한번쯤 들어봤을만한 알고리즘입니다.

제가 참고한 사이트는 다음과 같습니다.

 

https://towardsdatascience.com/dynamic-time-warping-3933f25fcdd

Dynamic Time Warping

https://en.wikipedia.org/wiki/Dynamic_time_warping

Dynamic time warping - Wikipedia

(논문)

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.465.4905&rep=rep1&type=pdf

 

DTW란 두 개의 시간 sequence의 유사도를 측정하는 알고리즘을 말합니다! wiki를 보면 주로 음성인식에서 많이 활용되었다고 하는데요. 무엇보다 이 알고리즘의 큰 장점은 두 개의 sequence 길이가 달라도 유사도를 측정할 수 있다는 점입니다. 예를 들면 [1,4,2,5,2], [1,3,2,1]이라는 2개의 sequence가 있을 때 기존 방법인 euclidean distance, Pearson 상관계수 수는 길이가 달라 아무래도 쓰기가 어려운 점이 있습니다. 이럴 때 이 알고리즘을 쓰면 유용할 수 있습니다.

 

DTW는 크게 2단계로 구성됩니다. 첫 번째로는 DTW가 유사도를 측정하기 위한 matrix를 만들어야 합니다. Base 알고리즘을 보면 다음과 같습니다.

 

그림 1. DTW의 유사도 측정을 위한 matrix를 만드는 과정

그림 1을 보면 int, for 등등 익숙치 않은(?) 단어들이 좀 나옵니다. 하나씩 글로 쓰지 않고 이렇게 컴퓨터 코딩에 쓰이는 언어로 쓰게 되면 알고리즘을 설명할 때 훨씬 간결하기 때문에 이런 설명의 형식으로 wiki에 나온 것을 볼 수 있습니다. 하나씩 살펴보면 다음과 같습니다.

 

① int DTWDistance(s: array [1..n], t: array [1..m])

  ● 함수 이름과 매개변수를 정의하는 부분.

  ● s라는 array는 총 n개 원소, t라는 array는 총 m개의 원소를 가짐

      (s, t는 sequence 객체로 위에서 [1,4,2,5,2], [1,3,2,1]와 같은 존재라고 생각하시면 됩니다.)

② DTW := array [0..n, 0..m] 

  ● n x m 형태의 matrix로 output 값입니다.

③ for i := 0 to n ......

  ● DTW matrix를 초기화 하는 단계입니다. DTW[0,0]만 0을 넣고 나머지 DTW의 모든 원소 값에 '∞'(이하 inf라고 명명) 값을 넣습니다. 

④ for i := 1 to n ......

  ● DTW 값을 다시 채우는 과정입니다. 인덱스는 0이 아닌 1부터 채웁니다.

  ● cost := d(s[i], t[j])에서 d 부분은 s[i]와 t[j] 간의 거리 함수입니다. 여기서는 d(x,y) = |x-y|를 의미합니다. 즉 s라는 array의 i번째 원소와 t라는 array의 j번째 원소 값 간 차이의 절대값입니다.

  ● minimum : 괄호 안에 있는 값 중 최솟값을 추출합니다. 예를 들어 minimum(3,1,5)라면 최솟값인 1이 출력됩니다.

⑤ return DTW[n,m] 

  ● 최종적으로 만들어진 DTW에서 두 sequence의 거리값인 DTW[n,m]를 반환합니다.

 

이렇게 단계가 구성되어 있습니다. 글로 보면 설명이 어렵기 때문에 그림과 함께 보도록 하겠습니다.

s = [1,4,2,6,5,3], t = [2,6,3,1]라고 한다면 ③의 DTW 결과값은 다음과 같습니다.

		1	4	2	6	5	3
	0	inf	inf	inf	inf	inf	inf
2	inf	inf	inf	inf	inf	inf	inf
6	inf	inf	inf	inf	inf	inf	inf
3	inf	inf	inf	inf	inf	inf	inf
1	inf	inf	inf	inf	inf	inf	inf

 

④는 두 번으로 나누어 보도록 하겠습니다. 첫 번째로 DTW[1,1]은 1과 2의 cost, minimum 값으로 구성됩니다.

cost = d(1,2) = |1-2| = 1

minimum을 더한 값은 다음과 같습니다

-> minimum(0, inf, inf, inf) = 0

따라서 DTW[1,1]은 1+0 = 1이 됩니다. 여기서 key point는 자기를 기준으로 한칸 위, 왼쪽, 대각선 방향의 값을 기준으로 minimum 값을 구하는 점입니다.

		1	4	2	6	5	3
	0	inf	inf	inf	inf	inf	inf
2	inf	1	inf	inf	inf	inf	inf
6	inf	inf	inf	inf	inf	inf	inf
3	inf	inf	inf	inf	inf	inf	inf
1	inf	inf	inf	inf	inf	inf	inf

 

이렇게 1개씩 구하면 다음과 같은 형태로 완성됩니다.

		1	4	2	6	5	3
	0	inf	inf	inf	inf	inf	inf
2	inf	1	3	3	7	10	11
6	inf	6	3	7	3	4	7
3	inf	8	4	4	6	5	4
1	inf	8	7	5	9	9	6

⑤의 값인 두 sequence 간의 유사도인 최종 거리값은 6이 됩니다. 이 값은 거리값이기 때문에 작을수록 유사도가 높다고 판단할 수 있습니다.(단, 단위가 통일되어 있어야 다른 결과와 비교 가능)

 

이와 동시에 warping path라는 sequence가 나오는데 이는 두 sequence의 sync를 맞춘 평균 결과값이라 보시면 됩니다. 두 sequence를 합성한 것과 조금 비슷하다고 생각할 수도 있습니다. 이 값을 구하기 위해서는 다음과 같은 3가지가 전제되어야 합니다.

 

1. 위의 표를 만들 때 첫 번째 값, 마지막 값을 서로 매칭시켜 만들어야 한다. : 아까 sequence의 첫 번째 값은 각각 1과 2였는데 표에서 이를 각각 첫번째 값으로 놓아야 한다는 의미입니다. 마지막 값도 마찬가지 입니다.

2. index 값은 단조적으로 커진다. : DTW를 만들 때 두 sequence의 index 값을 섞지 말고 1,2,3,4,5,6 같이 순차적으로 나열해야 한다는 의미입니다.

3. (prototype의 경우) 위의 최종 표에서 warping path를 만들 때 DTW[n,m]인 6에서 부터 거꾸로 올라가면서 path를 만들 때 최솟값으로 이동하는데 이동할 수 있는 경우의 수는 minimum을 구할 때랑 같다. : 이는 DTW[n,m]에서 이동 가능한 경우는 위, 왼쪽, 대각선 왼쪽 위 방향만 가능하다는 것을 의미합니다.

 

이를 기준으로 Warp path를 구하면 [(1, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (4, 6)]의 path를 만들게 됩니다. 즉, [1,3,3,3,4,4,6]의 Warp path가 만들어지게 됩니다.

 

하지만 이렇게 sequence 간의 모든 값을 고려하게 되면 시간 상으로 엄청 멀리 떨어진 경우까지도 고려하게 되어 현실적으로 맞지 않을 수 있습니다. 우리가 현재 비가 올지 안올지 예측할 때 12시간 전에 비가 온 것보다는 1시간 전에 비가 왔을 때의 정보가 더 유용할테니까요. 그래서 이를 제약하는 모델도 있는데 이는 위의 첫번째 링크인 'towardsdatascience.com'를 참조하시면 될 것 같습니다.

그 외에도 이렇게 구하는 과정의 계산량, 정확도 등의 효율성을 높이기 위해 minimum값을 구할 때 다른 방식으로 구하든지 등의 다른 알고리즘 방법이 있습니다.

 

글이 좀 길었는데 크게 정리하면 다음과 같습니다.

○ DTW는 두 sequence 간의 유사도 측정 및 sync를 맞춘 sequence를 생성하는 모델이다.

○ optimization의 최적화, 정확도 향상 등을 위한 방법으로 변형된 모델들이 있다.

○ 장점

  ● 두 sequence의 길이가 달라도 유사도를 구할 수 있다.

  ● 과거의 값을 고려하여 만들 수 있다.

○ 단점

  ● 모든 시간대를 비교하기 때문에 관계없는 시간대까지 알고리즘 결과에 반영될 수 있다.

 

여기까지가 DTW에 대한 설명이었습니다. 궁금하신 사항이나 잘못된 점 있으면 바로 말씀해주세요!

읽어주셔서 감사합니다!