맨위로가기

동적 시간 워핑

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 동적 계획법 - 배낭 문제
    배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다.
  • 동적 계획법 - 차원의 저주
    차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다.
  • 기계 학습 알고리즘 - 강화 학습
    강화 학습은 에이전트가 환경과의 상호작용을 통해 누적 보상을 최대화하는 최적의 정책을 학습하는 기계 학습 분야이며, 몬테카를로 방법, 시간차 학습, Q-러닝 등의 핵심 알고리즘과 탐험과 활용의 균형, 정책 경사법 등의 다양한 연구 주제를 포함한다.
  • 기계 학습 알고리즘 - 기댓값 최대화 알고리즘
동적 시간 워핑
개요
명칭동적 시간 워핑
영어 명칭Dynamic Time Warping (DTW)
분야시계열 분석
데이터 마이닝
목적두 시계열 간의 유사성 측정
상세 설명
정의길이가 다른 시계열 간의 최적 정렬을 찾는 알고리즘
핵심 아이디어시간 축을 늘이거나 줄여서 두 시계열의 형태를 최대한 일치시킴
활용음성 인식
필기 인식
생체 인식
의료 데이터 분석
주가 예측
동작 원리
거리 측정두 시계열의 각 점 사이의 거리를 계산 (예: 유클리드 거리)
워핑 경로두 시계열을 정렬하는 최적의 경로 탐색
누적 거리가 최소가 되는 경로를 선택
제약 조건단조성: 워핑 경로는 시간 순서를 유지
연속성: 워핑 경로는 점프 없이 연속적으로 진행
경계 조건: 워핑 경로는 시작점과 끝점을 반드시 포함
알고리즘 종류전역 제약 DTW
로컬 제약 DTW
변형 및 발전
가중치 DTW특정 구간에 가중치를 부여하여 중요도를 조절
다변량 DTW여러 변수를 동시에 고려하여 유사성 측정
유연한 DTW다양한 제약 조건을 적용하여 정확도 향상
FastDTW계산 속도 향상을 위한 근사 알고리즘
장점 및 단점
장점시계열의 길이와 속도 변화에 강건함
다양한 분야에 적용 가능
단점계산 복잡도가 높음 (시간 소요)
이상치에 민감함
최적의 워핑 경로를 찾기 위한 추가적인 연구 필요
구현
프로그래밍 언어파이썬
R
MATLAB
관련 라이브러리dtw-python
dtw
mlpy
참고 문헌

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 | \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 | \le w가 되도록 조정해야 한다.

4. 개선된 알고리즘

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

4. 1. FastDTW

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

4. 2. PrunedDTW

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

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

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

4. 3. LB_Keogh 및 기타 하한

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

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

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

5. 평균 시퀀스

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

5. 1. DBA (DTW Barycenter Averaging)

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

6. 응용 분야

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

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

6. 1. 음성 인식

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

6. 2. 필기 인식

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

7. 기타 접근 방식

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

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

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

7. 1. 함수형 데이터 분석

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

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

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

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

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

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

8. 소프트웨어

참조

[1] 논문 Simultaneous inference for misaligned multivariate functional data
[2] 간행물 Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier 2018
[3] 서적 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
[4] 서적 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
[5] 문서 Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation http://sites.labic.i[...] 2015
[6] 문서 SparseDTW: A Novel Approach to Speed up Dynamic Time Warping https://arxiv.org/ab[...] 2012
[7] 문서 FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space KDD Workshop on Mining Temporal and Sequential Data 2004
[8] 문서 An Efficient Multiscale Approach to Audio Synchronization https://www.audiolab[...] Proceedings of the International Conference on Music Information Retrieval (ISMIR) 2006
[9] 문서 Memory-Restricted Multiscale Dynamic Time Warping Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2016
[10] 간행물 Exact indexing of dynamic time warping
[11] 간행물 Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound
[12] 간행물 Tight lower bounds for Dynamic Time Warping 2021
[13] 간행물 Experimental comparison of representation methods and distance measures for time series data
[14] 서적 Proceedings of the 2019 SIAM International Conference on Data Mining 2019
[15] 간행물 Nonlinear alignment and averaging for estimating the evoked potential
[16] 간행물 A global averaging method for dynamic time warping, with applications to clustering
[17] 간행물 Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment
[18] 간행물 Querying and mining of time series data: experimental comparison of representations and distance measures
[19] 간행물 Amercing: An intuitive and effective constraint for dynamic time warping
[20] 간행물 On the Registration of Time and the Patterning of Speech Movements
[21] 간행물 Toward a Comprehensive Framework for the Spatiotemporal Statistical Analysis of Longitudinal Shape Data https://hal.inria.fr[...] 2013
[22] 서적 Speech Motor Control: New Developments in Basic and Applied Research Oxford University Press
[23] 간행물 Speech production variability in fricatives of children and adults: Results of functional data analysis 2008
[24] 간행물 Speaker-Independent English Consonant and Japanese Word Recognition by a Stochastic Dynamic Time Warping Method 1988-01-01
[25] 웹사이트 From Dynamic Time Warping (DTW) to Hidden Markov Model (HMM) http://eecs.ceas.uc.[...]
[26] 간행물 On the hidden Markov model and dynamic time warping for speech recognition #x2014; A unified view 1984-09
[27] 간행물 A nonlinear mixed-effects model for simultaneous smoothing and registration of functional data
[28] 간행물 Separating timing, movement conditions and individual differences in the analysis of human movement
[29] 서적 2021 IEEE International Conference on Data Mining (ICDM) 2021
[30] 간행물 dtwParallel: A Python package to efficiently compute dynamic time warping between time series https://www.scienced[...] 2024-12-06
[31] 간행물 Dynamic programming algorithm optimization for spoken word recognition
[32] 간행물 Financial markets' deterministic aspects modeled by a low-dimensional equation 2022-02-01
[33] 간행물 Decoupling and recoupling in the crude oil price benchmarks: An investigation of similarity patterns https://www.scienced[...] 2021-02-01
[34] 간행물 Modelling bursts and chaos regularization in credit risk with a deterministic nonlinear model https://www.scienced[...] 2021-12-10


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com