[6기 강남 송태현] DTW(Dynamic time warping) 알고리즘

안녕하세요 엘리트회원 6기 23-2 송태현 입니다.

 

이번시간에는 제가 예전에 창의과제에서 진행했던 핵심 알고리즘인 DTW알고리즘에 대해서 알아보겠습니다.

 

1. DTW알고리즘은 시간순서상에 여러개의 연속적인 데이터를 각각 비교하여 그 두 종료의 데이터가 얼마나 유사한가를 판별해 내는 알고리즘 입니다.

 

2. 다음과 같은 판별로 두개의 그래프가 얼마나 비슷한 그래프인가를 볼 수 있습니다.

 

 

T그래프와 C그래프는 같은 시간축선상에 이산데이터 입니다.

그 이산데이터들을 선으로 연결한것이 그래프인데

위와 같은 그래프에 데이터

T(2, 5, 2, 5, 3), C(0, 3, 6, 0, 6, 1)에 값을 서로 비교를 합니다.

 

3. 두 그래프를 비교하는 것은 다음과 같습니다.

 

유클리드 거리공식을 통해 2차원배열에 채우게 되고,

 

위에 첫번째 그림은 warping path를 결정하는 값을 뽑는거고,

두번째 그림은 위 테이블에 D 유클리드 공식에 따라 D의 최소값을 결정하게 됩니다.

 

최종적으로 D(i, j)값인 9가 이 그래프에 유사도가 되겠습니다.

0에 가까울수록 그래프는 유사하다고 판별 할 수 가 있고,

0이면 같은 그래프입니다.

 

4. 기존에 음성데이터의 비교나 또는 어떤 모션 비교에 이 알고리즘을 많이 사용하여 비교하게 됩니다.

이 알고리즘에 가장 큰 특징은 다른 유사도 패턴 알고리즘보다 구현하기 쉽다는 장점이 있어서 패턴 알고리즘을 공부해보고 싶은 분들은 이 알고리즘을 처음으로 공부해보는것도 좋을거 같습니다.

 

5. 제가 이 알고리즘을 구현한 코드는 다음과 같습니다.

다음과 같이 자바로 구현하였습니다.

 

public int DTWDistance(int s[], int t[]) // DTW Distancce
{
  int i, j, cost = 0;

  for (i = 1; i <= n; i++)
   // some value set = MAX int
   dtw[0][i] = 3000;

  for (i = 1; i <= m; i++)
   dtw[i][0] = 3000;

  dtw[0][0] = 0;
  // 1 to n
  for (i = 1; i <= n; i++) {
   for (j = 1; j <= m; j++) {
    cost = d(s[i], t[j]); // Uclid distance proc
    dtw[i][j] = cost + Math.min(dtw[i - 1][j], Math.min(dtw[i][j - 1], dtw[i - 1][j - 1]));
   }
  }
  return dtw[n][m]; // DTW value return
 }

어떤 2차원 배열에 값 n, m배열을 생성하여 그 곳을 DTW 알고리즘을 적용하여 리턴된 값이 그래프의 유사도가 되겠습니다.

 

감사합니다.