Dynamic Time Wrapping(DTW)란 ?
: 속도 또는 길이에 따라 움직임이 다른 두 시계열간의 유사성(거리)를 측정하는 알고리즘
모든 변화와 속도를 무시하여 두 개 이상의 시계열을 비교하는 매우 강력한 기술이다.
- 모든 시계열 형태의 sequence 데이터에 활용할 수 있음
- 유사도를 바탕으로 두 시계열 데이터 간 시간 정렬 가능
- 음성 인식이나 자연어 처리에 자주 활용됨
- 비교 데이터 포인트 사이의 시간 지표가 완벽하게 동기화되지 않을 때 사용되는 기술
다이브 프로젝트에서 우리가 계속 고민해오던 문제점 중 1개가 우리가 만든 데이터셋이 웹캠으로 실시간 인식하는 손 동작이 모두 다른 사람이 동작하는 것이기때문에 두 데이터의 속도차이가 나는 것이었음. DTW가 시간 지표가 완벽하게 동기화되지 않을때 사용되는 기술이기때문에 공부를 해봐야겠다고 생각함
두 댄서가 서로 다른 스타일과 상관없이 조화를 이루는 것처럼 보이게 할 수 있는 천재 안무가와 같다.
실제로 2개의 서로 다른 목소리가 동일인의 것인지 확인하고자할때 Dynamic time wrapping을 사용한다. 같은 사람이 말하더라도 속도가 다를 수 있기 때문에 통상적인 방법으로는 비교하기 어려울 수 있음. 이때 구글에서는 DTW를 사용했었음.
적용 기술
- 금융시장 : 완벽하게 일치하지 않더라도 유사한 기간 동안 주식 거래 데이터를 비교할 수 있음
- 웨어러블 피트니스 트래커 : 보행 속도가 시간에 따라 변하더라도 보행 속도와 걸음 숫자를 정확하게 계산함
- 루트 계산 : 좌회전 시 직진 차로보다 운행할 때보다 느리게 주행하는 것과 같은 사용자의 운전 습관을 알고있다면 예상 도착 시간을 보다 정확하게 계산할 수 있음
Dynamic time warping의 기본 원리
시계열이란 ? 시간 순서대로 색인된 일련의 데이터 포인트
본질적으로 DTW는 시계열 분석 도구이다.
DTW는 1대다의 관계 비교를 허용하여 그것들 사이의 왜곡을 이용해 거리를 계산한다. 계산을 하며 거리가 최소화되는 방향으로 매칭시켜서 누적 거리가 최소가 되는 warping 경로를 찾는.
최적(워핑)경로를 사용하여 크기를 일치시키도록 규칙에 따라 f(x)와 매핑할 수 있는 두 시계열은 유사한 것으로 간주한다.
A = [1,3,4,9,8,2,1,5,7,3]
B = [1,6,2,3,0,9,4,3,6,3]
먼저, 이 시계열을 나열하여 length(A),length(B)를 만든다.
행렬의 (i,j) 번째 요소는 두 점 간의 유클리드 거리 를 의미하며 이를 이용하여 최적의 와핑 경로를 찾는다.
이때 와핑 경로 W는 Q와 C사이의 mapping을 나타내는 와핑 거리의 집합이며 연속적이어야 한다.
여기에서 와핑거리는 W의 k번째 요소로 Wk= (i,j)k로 정의되며 3가지 조건을 만족해야한다.
- Boundary condition : 시작점은 (1,1) 끝점은 (m,n)이어야함
- continuity : 와핑 경로는 대각 요소를 포함한 인접한 셀로 제한
- monotonicity :와핑 경로는 음의 방향으로 이동하지않음
와핑경로가 최소가 되는 것이 목표임
DTW 거리가 0 이라는 것은 시계열이 매우 유사하다는 것을 의미한다.