동적 시간 워핑

1. 개요

동적 시간 워핑(DTW)은 시계열 간의 유사성을 측정하는 알고리즘으로, 시간 축의 비선형적인 변동을 허용하여 패턴 매칭을 수행한다. DTW는 두 시퀀스 간의 이산적인 매칭을 생성하며, 세그먼트의 시간 스케일링을 허용하지 않는다. 알고리즘은 두 시퀀스 간의 거리 계산, 최적 경로 탐색을 통해 구현되며, 지역성 제약 조건을 추가하여 성능을 개선할 수 있다. DTW는 음성 인식, 필기 인식, 이상 탐지 등 다양한 분야에 응용되며, FastDTW, PrunedDTW, LB_Keogh 등 개선된 알고리즘과 소프트웨어 라이브러리가 존재한다.

2. 기본 원리

(빈 내용)

3. 구현

두 시퀀스 s와 t가 이산 기호 문자열일 때 동적 시간 워핑 알고리즘의 구현 예시는 다음과 같다. 아래 코드는 지역성 제약 조건이 추가된 버전이다.

```
int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
DTW := array [0..n, 0..m]

w := max(w, abs(n-m)) // 윈도우 크기 조정

for i := 0 to n
for j:= 0 to m
DTW[i, j] := infinity
DTW[0, 0] := 0
for i := 1 to n
for j := max(1, i-w) to min(m, i+w)
DTW[i, j] := 0

for i := 1 to n
for j := max(1, i-w) to min(m, i+w)
cost := d(s[i], t[j])
DTW[i, j] := cost + minimum(DTW[i-1, j ], // 삽입
DTW[i , j-1], // 삭제
DTW[i-1, j-1]) // 일치
return DTW[n, m]
}

3.1. 기본 알고리즘

두 시퀀스 s와 t가 이산 기호 문자열일 때 동적 시간 워핑 알고리즘의 구현은 다음과 같다. 두 기호 x와 y에 대해 `d(x, y)`는 기호 간의 거리이며, 예를 들어 `d(x, y)` = $|\; x\; -\; y\; |$이다.

```
int DTWDistance(s: array [1..n], t: array [1..m]) {
DTW := array [0..n, 0..m]

for i := 0 to n
for j := 0 to m
DTW[i, j] := infinity
DTW[0, 0] := 0

for i := 1 to n
for j := 1 to m
cost := d(s[i], t[j])
DTW[i, j] := cost + minimum(DTW[i-1, j ], // 삽입
DTW[i , j-1], // 삭제
DTW[i-1, j-1]) // 일치

return DTW[n, m]
}
```

여기서 `DTW[i, j]`는 최상의 정렬을 가진 `s[1:i]`와 `t[1:j]` 간의 거리이다.

경우에 따라 지역성 제약 조건을 추가할 수 있다. 즉, `s[i]`가 `t[j]`와 일치하는 경우 $|\; i\; -\; j\; |$가 윈도우 매개변수인 w보다 크지 않도록 요구한다.

위에 주어진 알고리즘을 수정하여 지역성 제약 조건을 쉽게 추가할 수 있다. 그러나 위에서 제공된 수정은 $|\; n\; -\; m\; |$이 w보다 작을 때만 작동한다. 즉, 끝점이 대각선에서 윈도우 길이 내에 있다. 알고리즘이 작동하도록 하려면 윈도우 매개변수 w를 $|\; n\; -\; m\; |\; \backslash le\; w$가 되도록 조정해야 한다.

```
int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
DTW := array [0..n, 0..m]

w := max(w, abs(n-m)) // 윈도우 크기 조정

for i := 0 to n
for j:= 0 to m
DTW[i, j] := infinity
DTW[0, 0] := 0
for i := 1 to n
for j := max(1, i-w) to min(m, i+w)
DTW[i, j] := 0

for i := 1 to n
for j := max(1, i-w) to min(m, i+w)
cost := d(s[i], t[j])
DTW[i, j] := cost + minimum(DTW[i-1, j ], // 삽입
DTW[i , j-1], // 삭제
DTW[i-1, j-1]) // 일치
return DTW[n, m]
}

3.2. 지역성 제약 조건

경우에 따라 지역성 제약 조건을 추가할 수 있다. 즉, `s[i]`가 `t[j]`와 일치하는 경우 $|\; i\; -\; j\; |$가 윈도우 매개변수인 w보다 크지 않도록 요구할 수 있다.

위에 주어진 알고리즘을 수정하여 지역성 제약 조건을 쉽게 추가할 수 있다. 그러나 이 수정은 $|\; n\; -\; m\; |$이 w보다 작을 때만 작동한다. 다시 말해, 끝점이 대각선에서 윈도우 길이 내에 있어야 한다. 알고리즘이 작동하도록 하려면 윈도우 매개변수 w를 $|\; n\; -\; m\; |\; \backslash le\; w$가 되도록 조정해야 한다.

4. 개선된 알고리즘

동적 시간 워핑(DTW) 알고리즘을 개선하기 위해 PrunedDTW, SparseDTW, FastDTW, MultiscaleDTW 등의 방법이 개발되었다. 이러한 기술들은 DTW의 계산 속도를 향상시키는 것을 목표로 한다.

4.1. FastDTW

동적 시간 워핑(DTW)을 빠르게 계산하는 기술로는 PrunedDTW, SparseDTW, FastDTW, 및 MultiscaleDTW가 있다.

4.2. PrunedDTW

PrunedDTW는 동적 시간 워핑(DTW)을 빠르게 계산하는 기술 중 하나이다.

유사 시계열 검색과 같은 작업은 LB_Keogh, LB_Improved, 또는 LB_Petitjean과 같은 하한을 사용하여 가속화할 수 있다. 그러나 Early Abandon 및 Pruned DTW 알고리즘은 하한이 제공하는 가속 정도를 줄여 때로는 효과가 없게 만든다.

Wang 등의 조사에서는 LB_Improved 하한이 LB_Keogh 하한보다 약간 더 나은 결과를 보였고, 다른 기술은 비효율적이라고 보고했다. 이후 LB_Keogh보다 항상 더 좁으면서도 계산 효율성이 높은 LB_Enhanced 하한이 개발되었다. LB_Petitjean은 선형 시간 내에 계산할 수 있는 가장 좁은 하한으로 알려져 있다.

4.3. LB_Keogh 및 기타 하한

동적 시간 워핑(DTW)을 빠르게 계산하는 기술에는 PrunedDTW, SparseDTW, FastDTW, 및 MultiscaleDTW가 있다.

유사 시계열 검색과 같은 일반적인 작업은 LB_Keogh, LB_Improved, 또는 LB_Petitjean과 같은 하한을 사용하여 가속화할 수 있다. 그러나 Early Abandon 및 Pruned DTW 알고리즘은 하한이 제공하는 가속 정도를 줄여 때로는 효과가 없게 만든다.

Wang 등은 조사에서 LB_Improved 하한이 LB_Keogh 하한보다 약간 더 나은 결과를 보고했으며 다른 기술은 비효율적임을 발견했다. 이 조사 이후 LB_Keogh보다 항상 더 좁으면서도 계산 효율성이 높은 LB_Enhanced 하한이 개발되었다. LB_Petitjean은 선형 시간 내에 계산할 수 있는 가장 좁은 알려진 하한이다.

5. 평균 시퀀스

동적 시간 워핑(DTW)의 평균화는 일련의 시퀀스 집합에 대한 평균 시퀀스를 찾는 문제이다. NLAAF는 DTW를 사용하여 두 시퀀스를 평균화하는 정확한 방법이다. 두 개 이상의 시퀀스의 경우에는 다중 정렬 문제와 관련이 있으며 휴리스틱이 필요하다. DBA, COMASA와 같은 방법들이 사용된다.

5.1. DBA (DTW Barycenter Averaging)

동적 시간 워핑(DTW)의 평균화는 일련의 시퀀스 집합에 대한 평균 시퀀스를 찾는 문제이다. NLAAF는 DTW를 사용하여 두 시퀀스를 평균화하는 정확한 방법이다. 두 개 이상의 시퀀스의 경우, 이 문제는 다중 정렬 문제와 관련이 있으며 휴리스틱이 필요하다. DBA는 현재 DTW와 일관되게 일련의 시퀀스를 평균화하는 데 사용되는 기준 방법이다. COMASA는 DBA를 로컬 최적화 프로세스로 사용하여 평균 시퀀스 검색을 효율적으로 무작위화한다.

6. 응용 분야

동적 시간 워핑(DTW)은 여러 분야에서 활용된다.

음성 인식에서 발화 속도 차이로 생기는 음성 패턴의 시간 축 상 비선형적 변동은 제거해야 할 대상이다. 동적 프로그래밍(DP) 기반 패턴 매칭 알고리즘인 DP 매칭이 이 문제를 해결한다. DP 매칭은 비선형 시간 워핑 함수로 시간 축 변동을 모델링하고, 시간 정규화 효과를 낸다. 서로 다른 두 음성 패턴에서 한 패턴의 시간 축을 워핑해 다른 패턴과 최대한 일치시켜 시간 차이를 없앤다. 워핑 함수가 모든 값을 가지면 서로 다른 범주의 단어를 구분하기 어려우므로, 기울기에 제한을 두어 구별력을 높인다.

6.1. 음성 인식

발화 속도의 차이로 인해 음성 패턴 대 시간 축에서 비선형적인 변동이 발생하며, 이를 제거해야 한다. DP 매칭은 동적 프로그래밍(DP)을 기반으로 하는 패턴 매칭 알고리즘으로, 시간 축의 변동을 비선형 시간 워핑 함수를 사용하여 모델링하는 시간 정규화 효과를 사용한다. 임의의 두 음성 패턴을 고려할 때, 하나의 시간 축을 워핑하여 다른 패턴과 최대 일치를 이루도록 함으로써 시간 차이를 제거할 수 있다. 또한 워핑 함수가 가능한 모든 값을 가질 수 있다면, 서로 다른 범주에 속하는 단어들 사이에서 구별이 매우 적게 이루어질 수 있다. 따라서, 서로 다른 범주에 속하는 단어들 사이의 구별을 향상시키기 위해, 워핑 함수 기울기에 제한을 두었다.

6.2. 필기 인식

(원본 소스에 해당 섹션 관련 내용이 없으므로 작성할 수 없습니다.)

7. 기타 접근 방식

함수적 데이터 분석에서 시계열은 시간의 매끄러운(미분 가능한) 함수의 이산화로 간주된다. 관측된 샘플을 매끄러운 함수로 봄으로써 데이터를 분석하기 위해 연속 수학을 활용할 수 있다. 시간 와핑 함수의 매끄러움과 단조성은 시간 변화 방사 기저 함수를 적분하여 얻을 수 있으며, 이는 1차원 미분 동형 사상이다. 최적의 비선형 시간 와핑 함수는 함수 집합과 왜곡된 평균 간의 거리 척도를 최소화하여 계산된다. 와핑 함수의 거칠기 페널티 항은 곡률 크기를 제한하는 방식으로 추가할 수 있다. 이 접근 방식은 음성 움직임의 패턴과 변동성을 분석하는 데 성공적으로 적용되었다.

은닉 마르코프 모델(HMM)과 관련된 접근 방식이 있으며, HMM을 통해 가장 가능성이 높은 경로를 검색하는 데 사용되는 비터비 알고리즘이 확률적 DTW와 동일하다는 것이 입증되었다.

DTW 및 관련 와핑 방법은 일반적으로 데이터 분석의 전처리 또는 후처리 단계로 사용된다. 관측된 시퀀스에 값, 관측된 시퀀스 모양 및 임의의 시간적 정렬 불일치 모두에 임의의 변동이 포함된 경우 와핑은 노이즈에 과적합되어 편향된 결과를 초래할 수 있다. 값(세로)과 시간 매개변수화(가로) 모두에 임의의 변동이 있는 동시 모델 공식은 비선형 혼합 효과 모델의 예이다. 인간 운동 분석에서 동시 비선형 혼합 효과 모델링이 DTW보다 우수한 결과를 생성하는 것으로 나타났다.

7.1. 함수형 데이터 분석

함수적 데이터 분석에서 시계열은 시간의 매끄러운(미분 가능한) 함수의 이산화로 간주된다. 관측된 샘플을 매끄러운 함수로 봄으로써 데이터를 분석하기 위해 연속 수학을 활용할 수 있다. 시간 와핑 함수의 매끄러움과 단조성은 시간 변화 방사 기저 함수를 적분하여 얻을 수 있으며, 이는 1차원 미분 동형 사상이다. 최적의 비선형 시간 와핑 함수는 함수 집합과 왜곡된 평균 간의 거리 척도를 최소화하여 계산된다. 와핑 함수의 거칠기 페널티 항은 곡률 크기를 제한하는 방식으로 추가할 수 있다. 결과 와핑 함수는 매끄러워 추가 처리를 용이하게 한다. 이 접근 방식은 음성 움직임의 패턴과 변동성을 분석하는 데 성공적으로 적용되었다.

또 다른 관련 접근 방식은 은닉 마르코프 모델(HMM)이며 HMM을 통해 가장 가능성이 높은 경로를 검색하는 데 사용되는 비터비 알고리즘이 확률적 DTW와 동일하다는 것이 입증되었다.

DTW 및 관련 와핑 방법은 일반적으로 데이터 분석의 전처리 또는 후처리 단계로 사용된다. 관측된 시퀀스에 값, 관측된 시퀀스 모양 및 임의의 시간적 정렬 불일치 모두에 임의의 변동이 포함된 경우 와핑은 노이즈에 과적합되어 편향된 결과를 초래할 수 있다. 값(세로)과 시간 매개변수화(가로) 모두에 임의의 변동이 있는 동시 모델 공식은 비선형 혼합 효과 모델의 예이다. 인간 운동 분석에서 동시 비선형 혼합 효과 모델링이 DTW보다 우수한 결과를 생성하는 것으로 나타났다.

7.2. 은닉 마르코프 모델 (HMM)

은닉 마르코프 모델(HMM)과 관련된 접근 방식이 있으며, HMM을 통해 가장 가능성이 높은 경로를 검색하는 데 사용되는 비터비 알고리즘이 확률적 DTW와 동일하다는 것이 입증되었다.

DTW 및 관련 워핑 방법은 일반적으로 데이터 분석의 전처리 또는 후처리 단계로 사용된다. 관측된 시퀀스에 값, 관측된 시퀀스 모양 및 임의의 시간적 정렬 불일치 모두에 임의의 변동이 포함된 경우, 워핑은 노이즈에 과적합되어 편향된 결과를 초래할 수 있다. 값(세로)과 시간 매개변수화(가로) 모두에 임의의 변동이 있는 동시 모델 공식은 비선형 혼합 효과 모델의 한 예이다. 인간 운동 분석에서 동시 비선형 혼합 효과 모델링이 DTW보다 우수한 결과를 생성하는 것으로 나타났다.

8. 소프트웨어

* https://github.com/MonashTS/tempo tempo C++ 라이브러리는 Python 바인딩을 통해 Early Abandoned 및 Pruned DTW와 Early Abandoned 및 Pruned ADTW 및 DTW 하한 LB_Keogh, LB_Enhanced 및 LB_Webb를 구현한다.
* https://github.com/ChangWeiTan/UltraFastWWS UltraFastMPSearch Java 라이브러리는 빠른 워핑 윈도우 조정을 위한 UltraFastWWSearch 알고리즘을 구현한다.
* https://github.com/lemire/lbimproved lbimproved C++ 라이브러리는 GNU General Public License(GPL)에 따라 가장 가까운 이웃 검색 알고리즘을 구현한다. 또한 동적 시간 워핑 및 다양한 하한에 대한 C++ 구현을 제공한다.
* https://github.com/rmaestre/FastDTW FastDTW 라이브러리는 DTW와 FastDTW를 Java로 구현한 것으로, 표준 DTW 알고리즘의 O(N²) 요구 사항과 달리 최적 또는 거의 최적의 정렬을 O(N) 시간 및 메모리 복잡성으로 제공한다. FastDTW는 더 조잡한 해상도에서 솔루션을 재귀적으로 투영하고 투영된 솔루션을 개선하는 다단계 접근 방식을 사용한다.
* https://mvnrepository.com/artifact/com.github.davidmoten/fastdtw FastDTW fork (Java)는 Maven Central에 게시되었다.
* https://github.com/cesarsotovalero/time-series-classification time-series-classification (Java)는 Weka에서 DTW를 사용하여 시계열 분류를 위한 패키지이다.
* https://dynamictimewarping.github.io/ DTW suite는 다양한 재귀 규칙(단계 패턴이라고도 함), 제약 조건 및 부분 문자열 일치를 포함하여 DTW 알고리즘 패밀리 구성원에 대한 포괄적인 범위를 갖춘 Python([https://pypi.org/project/dtw-python/ dtw-python]) 및 R 패키지([https://cran.r-project.org/package=dtw dtw])를 제공한다.
* mlpy Python 라이브러리는 DTW를 구현한다.
* https://pypi.python.org/pypi/pydtw pydtw Python 라이브러리는 LB_Keogh 하한을 포함한 Manhattan 및 Euclidean 방식의 DTW 척도를 구현한다.
* https://gravitino.github.io/cudadtw/ cudadtw C++/CUDA 라이브러리는 CUDA 지원 가속기에서 널리 사용되는 UCR-Suite와 유사하게 유클리드 방식의 DTW 및 z-정규화된 유클리드 거리의 하위 시퀀스 정렬을 구현한다.
* http://java-ml.sourceforge.net/ JavaML 기계 학습 라이브러리는 [https://sourceforge.net/p/java-ml/java-ml-code/ci/9f6726deab4e55b7617478bc51e29c20308bffb9/tree/net/sf/javaml/distance/dtw/FastDTW.java DTW]를 구현한다.
* https://github.com/doblak/ndtw ndtw C# 라이브러리는 다양한 옵션으로 DTW를 구현한다.
* https://github.com/kirel/sketch-a-char Sketch-a-Char는 LaTeX 기호 분류기 프로그램의 일부로 Greedy DTW(JavaScript로 구현)를 사용한다.
* https://github.com/hfink/matchbox MatchBox는 오디오 신호의 멜-주파수 켑스트럼 계수를 일치시키기 위해 DTW를 구현한다.
* https://github.com/fpetitjean/DBA Sequence averaging: DBA의 GPL Java 구현.
* GRT C++ 실시간 제스처 인식 툴킷은 DTW를 구현한다.
* http://biointelligence.hu/pyhubs/ PyHubs 소프트웨어 패키지는 DTW 및 가장 가까운 이웃 분류기를 구현하며, 확장 기능(허브 인식 분류기)도 구현한다.
* https://github.com/talcs/simpledtw simpledtw Python 라이브러리는 고전적인 O(NM) 동적 프로그래밍 알고리즘을 구현하고 Numpy를 기반으로 한다. 모든 차원의 값과 거리에 대한 사용자 지정 노름 함수를 지원한다. MIT 라이선스에 따라 사용이 허가된다.
* https://tslearn.readthedocs.io/en/latest/# tslearn Python 라이브러리는 시계열 컨텍스트에서 DTW를 구현한다.
* https://github.com/garrettwrong/cuTWED cuTWED CUDA Python 라이브러리는 놀라운 속도 향상으로 선형 메모리만 사용하여 최첨단 시간 워프 편집 거리를 구현한다.
* https://github.com/baggepinnen/DynamicAxisWarping.jl DynamicAxisWarping.jl은 FastDTW, SoftDTW, GeneralDTW 및 DTW 중점과 같은 DTW 및 관련 알고리즘의 Julia 구현이다.
* https://github.com/kaen2891/Multi_DTW/ Multi_DTW는 두 개의 1차원 배열 또는 2차원 음성 파일(2차원 배열)을 일치시키기 위해 DTW를 구현한다.
* https://pypi.org/project/dtwParallel/ dtwParallel (Python) 패키지는 현재 DTW 라이브러리에서 사용할 수 있는 주요 기능과 병렬화, 유사성(커널 기반) 값 계산 및 다른 유형의 기능(범주형, 실수 값 등)이 있는 데이터 고려와 같은 새로운 기능을 통합한다.