본문 바로가기
Language

DTW (Dynamic time warping)

by hyez 2021. 5. 30.

DTW (Dynamic time warping) 란?

 시계열 분석에서 Dynamic time warping(DTW)은 속도에서 달라질 수 있는 두 시간적 시퀀스 사이의 유사성을 측정하기 위한 알고리즘 중 하나이다. 예를들어, 한 사람이 다른 사람보다 더 빨리 걷거나 관찰 과정에서 가속과 감속이 있더라도  DTW를 사용하여 보행의 유사성을 감지할 수 있었다. 실제로, 선형 시퀀스로 변환될 수 있는 모든 데이터는 DTW로 분석할 수 있다.

 

 잘 알려진 응용 프로그램은 다양한 말하기 속도에 대처하기 위한 자동 음성 인식(automatic speech recognition)이다. 다른 응용 프로그램에는 스피커 인식(speaker recognition)과 온라인 서명 인식(signature recognition)이 있다.

 

(왼) Dynamic time warping / (오) Two repetitions of a walking sequence recorded using a motion-capture system. While there are differences in walking speed between repetitions, the spatial paths of limbs remain highly similar.

 

 일반적으로 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()

 

 

Reference

댓글