DTW (Dynamic time warping) 란?
시계열 분석에서 Dynamic time warping(DTW)은 속도에서 달라질 수 있는 두 시간적 시퀀스 사이의 유사성을 측정하기 위한 알고리즘 중 하나이다. 예를들어, 한 사람이 다른 사람보다 더 빨리 걷거나 관찰 과정에서 가속과 감속이 있더라도 DTW를 사용하여 보행의 유사성을 감지할 수 있었다. 실제로, 선형 시퀀스로 변환될 수 있는 모든 데이터는 DTW로 분석할 수 있다.
잘 알려진 응용 프로그램은 다양한 말하기 속도에 대처하기 위한 자동 음성 인식(automatic speech recognition)이다. 다른 응용 프로그램에는 스피커 인식(speaker recognition)과 온라인 서명 인식(signature recognition)이 있다.
일반적으로 DTW는 특정 제한과 규칙을 사용하여 주어진 두 시퀀스(예: 시계열)간의 최적 일치를 계산하는 방법이다.
- 첫번째 시퀀스의 모든 인덱스는 다른 시퀀스의 하나 이상의 인데스와 일치해야하며 그 반대의 경우도 마찬가지이다.
- 첫번째 시퀀스의 첫번째 인덱스는 다른 시퀀스의 첫번째 인덱스와 일치해야 한다. (단, 하나만 일치할 필요는 없음)
- 첫번째 시퀀스의 마지막 인덱스는 다른 시퀀스의 마지막 인덱스와 일치해야 한다. (단, 하나만 일치할 필요는 없음)
- 첫번째 시퀀스에서 다른 시퀀스의 인덱스로의 인덱스 매핑은 단조증가해야하며 그 반대도 마찬가지이다. 즉, $j > i$가 첫 번째 시퀀스의 인덱스인 경우 다른 시퀀스에는 두 개의 인덱스 $l > k$가 없어야 한다. 즉, 인덱스 $i$는 인덱스 $l$ 과 일치하고, 인덱스 $j$는 인덱스 $k$와 일치하며, 그 반대의 경우도 마찬가지이다.
최적 일치는 모든 제한과 규칙을 만족하고 최소 비용을 갖는 일치로 나타내며, 여기서 비용은 각 일치된 인덱스 쌍에 대한 절대 차이의 합으로 계산된다.
시퀀스는 시간 차원에서 비선형적으로 "warped"되어 시간 차원의 특정 비선형 변동과 무관한 유사성 측도를 결정한다. 이 시퀀스 정렬 방법은 종종 시계열 분류에 사용된다. DTW는 주어진 두 시퀀스 사이의 거리 같은 양을 측정하지만, 삼각 부등식이 유지되는 것을 보장하지는 않는다.
두 시퀀스 사이의 유사성 측도, 이른바 "warping path(왜곡 경로)"가 이 경로에 따라 뒤틀림으로써 두 신호를 시간에 맞춰 정렬할 수 있다. 원래 점 $(X, Y)$(원본)의 집합이 있는 신호는 $(X, Y)$(warped)로 변환된다. 이는 genetic sequence와 audio synchronisation에서 응용될 수 있다. 관련 기술에서 다양한 속도의 시퀀스는 이 기법을 사용하여 평균화 할 수 있다.
Implementation
from math import *
import numpy as np
import sys
def DTW(A, B, window=sys.maxint, d=lambda x, y: abs(x - y)):
# 비용 행렬 초기화
A, B = np.array(A), np.array(B)
M, N = len(A), len(B)
cost = sys.maxint * np.ones((M, N))
# 첫번째 로우,컬럼 채우기
cost[0, 0] = d(A[0], B[0])
for i in range(1, M):
cost[i, 0] = cost[i - 1, 0] + d(A[i], B[0])
for j in range(1, N):
cost[0, j] = cost[0, j - 1] + d(A[0], B[j])
# 나머지 행렬 채우기
for i in range(1, M):
for j in range(max(1, i - window), min(N, i + window)):
choices = cost[i - 1, j - 1], cost[i, j - 1], cost[i - 1, j]
cost[i, j] = min(choices) + d(A[i], B[j])
# 최적 경로 구하기
n, m = N - 1, M - 1
path = []
while (m, n) != (0, 0):
path.append((m, n))
m, n = min((m - 1, n), (m, n - 1), (m - 1, n - 1), key=lambda x: cost[x[0], x[1]])
path.append((0, 0))
return cost[-1, -1], path
def main():
A = np.array([1,2,3,4,2,3])
B = np.array([7,8,5,9,11,9])
cost, path = DTW(A, B, window = 6)
print 'Total Distance is ', cost
import matplotlib.pyplot as plt
offset = 5
plt.xlim([-1, max(len(A), len(B)) + 1])
plt.plot(A)
plt.plot(B + offset)
for (x1, x2) in path:
plt.plot([x1, x2], [A[x1], B[x2] + offset])
plt.show()
if __name__ == '__main__':
main()
댓글