DTW(Dynamic Time Warping)

음성 신호에 대해 공부하던 중, 발음 평가를 위해 같은 말을 했지만 길이가 다른 음성 신호 두 개를 비교해야 하는 경우가 발생했다.

유사도 측정에서 주로 사용하는 유클리드 거리, 코사인 유사도 등은 길이가 동일한 데이터에 대해서만 유사도 측정이 가능하다.(물론 패딩을 통해서 길이를 맞추는 방법도 존재한다.) 그래서 찾던 중 DTW를 발견하게 됐다.

DTW(Dynamic Time Warping)이란

길이가 서로 다른 두 데이터를 비교하고 정렬하는데 사용되는 알고리즘이다.

DTW의 주요 개념

DTW는 1:n의 관계를 허용하여 왜곡을 이용해 거리를 계산한다.

거리를 계산하며 거리가 최소가 되는 방향으로 이동하여, 누적 거리가 최소가 되는 경로를 찾는다.

DTW의 3가지 조건

1. 시작점$(0, 0)$으로 시작해서 끝점$(n, m)$으로 끝나야 하고, 두 점은 이어져야 한다.
   $n$ : $X$의 길이
   $m$ : $Y$의 길이

2. 와핑 경로는 대각 요소를 포함한 인접한 셀로 제한된다.

3. 음의 경로로 이동할 수 없다.

DTW의 동작 과정

1. 두 데이터 $X$와 $Y$가 있을 때, $X$와 $Y$의 길이를 통해 거리 행렬을 만든다.

2. 거리 행렬의 $(i, j)$번째 셀은 $X_i, \ Y_j$ 간의 유클리드 거리를 의미한다.

3. 거리 행렬을 기반으로 누적 거리 행렬을 만든다. 행렬의 각 셀에는 두 데이터의 해당 인덱스까지의 누적 비용이 저장된다. 이 때 누적 비용을 계산하는 수식이다.

3. 누적 비용 행렬을 기반으로 $(0, 0)$에서 $(n, m)$으로 가는 최단 경로를 찾는다.

4. 최단 경로가 두 데이터 간의 최적 정렬을 나타내며, 유사도를 나타낸다.