[ML] DTW (Dynamic Time Warping)

 

• 속도가 다를 수 있는 두 개의 시간 sequence의 유사도를 측정하는 알고리즘

 

적용분야

• 소리패턴 감지
  • 사람들은 같은 단어를 속도나 악센트가 다르게 발음하기 때문에 사운드 트랙을 일치시키고 식별할수 있는 알고리즘이 필요

• 주식시장

• 비디오

• 그래픽 데이터

 

정의 및 아이디어

• 파란색 패턴이 빨간색 패턴보다 더 긺. 그러므로 euclidean matchng 을 이용하여 매핑이 완벽하게 동기화 되지 않음. 하지만 DTW는 동일한 패턴의 최저점과 최고점이 완벽하게 일치하고 두 곡선 모두에 대해 누락이 없도록 일대다 일치를 개발하여 문제를 극복

 

DTW 방법

💡

DTW는 특정 제한 사항과 규칙(wiki에서 제공)을 사용하여 주어진 두 시퀀스(예: 시계열) 간의 최적 일치를 계산하는 방법

1. 첫 번째 시퀀스의 모든 인덱스는 다른 시퀀스의 하나 이상의 인덱스와 일치해야 하며 그 반대의 경우도 마찬가지입니다.

2. 첫 번째 시퀀스의 첫 번째 인덱스는 다른 시퀀스의 첫 번째 인덱스와 일치해야 합니다(단, 유일한 일치일 필요는 없음).

3. 첫 번째 시퀀스의 마지막 인덱스는 다른 시퀀스의 마지막 인덱스와 일치해야 합니다(단, 유일한 일치일 필요는 없음).

4. 첫 번째 시퀀스의 인덱스를 다른 시퀀스의 인덱스로 매핑하는 것은 단조 증가해야 하며 그 반대의 경우도 마찬가지입니다. 즉, 첫 번째 시퀀스의 인덱스인 경우 인덱스가 일치하도록 다른 시퀀스에 j > il > kiljk두 개의 인덱스가 있어서는 안 됩니다. with index 및 index 는 index 와 일치하며 그 반대도 마찬가지 입니다.

 

• 최적의 일치는 모든 제한 사항과 규칙을 충족하고 최소 비용을 갖는 일치로 표시. 여기서 비용은 일치하는 각 인덱스 쌍에 대해 해당 값 사이의 절대 차이의 합으로 계산

⇒ 머리와 꼬리는 위치적으로 일치해야 하며 교차 일치나 누락이 있어서는 안 됨

 

구현

 

DTW[i, j] := 비용 + 최소값(DTW[i-1, j ], 
                            DTW[i , j-1], 
                            DTW[i-1, j-1])

 

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean

x = np.array([1, 2, 3, 3, 7])
y = np.array([1, 2, 2, 2, 2, 2, 2, 4])

distance, path = fastdtw(x, y, dist=euclidean)

print(distance)
print(path)

 

• window 제약 추가
  • 배열의 한 요소가 다른 배열의 요소 수에 제한없이 일치하도록 하기 때문에 매핑이 매~우 구부짐
  ⇒ 그러므로 window 제약을 추가하여 일치할 수 있는 요소수를 제한
•