Dynamic Time Warping(동적 시간 접합)

DTW는 두 개의 시간적 순서가 있는 벡터 간에 유사도를 평가하는 방법이다. 이 말을 쉽게 얘기하자면 우리는 예측값에 대해 정확히 알면 좋긴하나 현실적으로 제한적일 때 경향성이라도 비슷하게 잘 맞추는 알고리즘이 무엇인가 평가하고자 한다. 하지만  성능평가 지표로 사용하는 RMSE, MAE 등의 경우 예측값에 지현 현상이 일어 났을 때 단순히 예측값과 해당 시점의 관측값 간의 차이만을 평가하므로 적합한 평가지표가 아닐 수 있다. 이러한 경우 유사도 개념을 활용하게 되는데 유사도는 거리의 반대의 개념이라고 생각하면 좀 더 이해하기 쉽다.

 

그렇다면 DTW는 어떠한 알고리즘으로 구성 되어 있을까?

1. 두 개의 시계열 간의 거리를 모두 구하는 과정

2. 가장 가까운 거리를 구하기 위해 이를 누적합 하는 과정

3. 가장 가까운 거리간에 매칭하는 과정

 

이렇게 3가지로 구성이 된다.

 

예를 들어보자. 

 

시계열 예측값이 다음과 같이 존재한다고 하자.

 

x=c(1, 1, 2, 3, 3, 2)

y=c(1, 2, 3, 3, 2, 1)

 

이제 각각의 거리의 절대값에 대한 행렬을 구해보자 

 

       1  1  2  3  3  2

1     0  0  1  2  2  1

2     1  1  0  1  1  0

3     2  2  1  0  0  1

3     2  2  1  0  0  1

2     1  1  0  1  1  0

1     0  0  1  2  2  1

 

위와 같이 두개의 시계열 간의 거리의 절대값을 구하였다면 누적합을 구해보자.

주대각성분(현재 0, 1, 1 , 0 ,1 ,1 에 해당하는 (m, m)행렬의 대각선 성분)을 기준으로 i>j이면 행으로 누적합을 j>i이면 열로 누적합을 진행한다.

 

       1  1  2  3  3  2

1     0  0  1  3  5  6

2     1  1 0   1  2  2

3     3  3  1  0  0  1

3     5  5  2  0  0  1

2     6  6  2  1  1  0

1     6  6  3  3  3  1

 

아래는 R에 존재하는 DTW이다. 

#====library(dtw)====#
x=c(1,1,2,3,3,2)
y=c(1,2,3,3,2,1)
mydtw = dtw(y,x, keep.internals=T)
mydtw$costMatrix

 

맨 마지막 m,m 성분을 DTW값이라 한다. 

 

이렇게 구한 값을 이제 m,m부터 인접한 가장 작은 값과 매칭하자. 

 

그러면 매칭이 되는 값들을 이어 시각화 하면 다음과 같은 그림이 나타난다.

 

이는 DTW 상으로 가장 가까운 거리를 의미한다.

이를 기반으로 성능을 평가한다면 패턴 인식에 대한 성능평가지표로 RMSE나 MAE보다 좀 더 우수한 성능 평가 지표로 사용 될 수 있다 생각 된다.

 

참고 : http://hamait.tistory.com/862 

파이썬 코딩으로 말하는 데이터 분석 - 10. DTW (Dynamic time wrapping)