동적 시간 뒤틀림

모션 캡쳐 시스템을 사용하여 기록된 걷기 시퀀스의 두 번 반복. 반복마다 걷는 속도에 차이가 있지만 팔다리의 공간적 경로는 매우 유사하다.^[1]

시계열 분석에서 동적 시간 뒤틀림(DTW)은 속도가 다를 수 있는 두 시간적 시퀀스 사이의 유사성을 측정하기 위한 알고리즘이다. 예를 들어, 한 사람이 다른 사람보다 더 빨리 걷는다거나 관찰 과정에서 가속과 감속이 있는 경우에도 DTW를 사용하여 걷는 유사성이 감지될 수 있다. DTW는 비디오, 오디오, 그래픽 데이터의 임시 시퀀스에 적용되었다. 실제로, 선형 시퀀스로 변환될 수 있는 데이터는 DTW로 분석할 수 있다. 잘 알려진 응용 프로그램은 다양한 말하기 속도에 대처하기 위해 자동 음성 인식이었다. 다른 애플리케이션에는 스피커 인식과 온라인 서명 인식이 포함된다. 부분모양 매칭 어플리케이션에도 사용할 수 있다.

일반적으로 DTW는 일정한 제한과 규칙을 가지고 주어진 두 시퀀스(예: 시계열) 사이의 최적 일치를 계산하는 방법이다.

첫 번째 시퀀스의 모든 인덱스는 다른 시퀀스의 하나 이상의 인덱스와 일치해야 하며, 그 반대의 경우도 마찬가지 입니다.
첫 번째 시퀀스의 첫 번째 인덱스는 다른 시퀀스의 첫 번째 인덱스와 일치해야 하지만 유일한 인덱스가 될 필요는 없다.
첫 번째 시퀀스의 마지막 인덱스는 다른 시퀀스의 마지막 인덱스와 일치해야 한다(단, 유일한 일치일 필요는 없음).
즉 만약 j입니다. 지수의 첫번째 시퀀스에서 지수의 다른 시퀀스의 매핑 monotonically 수도 있고 반대로, 나는 첫번째 시퀀스에서 있지수{\displaystyle j>, 나는}, 다른 시퀀스고 지수 나는{\displ 다음 없어야 한다 두 지수 나는>k{\displaystyle l>, k}, 증가하고 있어야 한다.aystyle 나는} 인덱스 $l$ $l$ 과 $l$ (와) 일치하고 인덱스 $j$ $j$ 과 $j$ (와) $인덱스$ k $k$ 과 $k$ 와) 일치하며 그 반대의 경우도 마찬가지 입니다.

최적 일치는 모든 제한사항과 규칙을 만족하는 일치로 표시되며, 최소 비용(각 일치된 지수 쌍에 대해 절대 차이의 합으로 계산되는 비용)이 값 사이에 표시된다.

시간 차원의 특정 비선형 변동에 독립적인 유사성의 측정치를 결정하기 위해 시간 차원의 "비선형"으로 시퀀스를 "왜곡"한다. 이 시퀀스 정렬 방법은 시계열 분류에 자주 사용된다. DTW는 주어진 두 시퀀스 사이의 거리 같은 양을 측정하지만, 삼각형 불평등이 유지되도록 보장하지는 않는다.

두 시퀀스 사이의 유사성 측정에 더하여 이 경로에 따라 뒤틀림으로써 이른바 "뒤틀림 경로"가 생성될 수 있다. 원래 점 X(원본), Y(원본)의 세트가 있는 신호는 X(원본), Y(원본)로 변환된다. 이것은 유전적 순서와 오디오 동기화에서 응용 프로그램을 찾아낸다. 관련 기법에서 이 기법을 사용하여 다양한 속도의 시퀀스를 평균화할 수 있다. 평균 시퀀스 섹션을 참조하십시오.

이것은 개념적으로 니들맨과 매우 유사하다.운슈 알고리즘.

실행

이 예는 두 시퀀스 중 동적 시간 뒤틀림 알고리즘의 구현을 예시한다. s 그리고 t 별개의 기호의 끈이다. 두 기호용 x 그리고 y, d(x, y) 기호 사이의 거리(예: d(x, y) = $|x-y|$ - $|x-y|$ $displaystyle 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  ],    // insertion                                         DTW[i , j-1], // 삭제 DTW[i-1, j-1]) // 반환 DTW[n, m] }과(와) 일치

어디에 DTW[i, j] 사이의 거리 s[1:i] 그리고 t[1:j] 가장 잘 정렬하여

우리는 때때로 지역성의 제약을 추가하고 싶다. 즉, 다음과 같은 경우 s[i] 와 일치하다 t[j], 그러면 $|i-j|$ - $|i-j|$ $displaystyle i-j }$ 은 $| i - j |$ (는) 다음보다 크지 않음 w, 창 매개 변수.

위 알고리즘을 쉽게 수정하여 위치 제약(표시된 차이)을 추가할 수 있다. $|n-m|$ $|n-m|$ 의 지정된 수정은 n $|n-m|$ - m $displaystyle n-m }$ 이 $| n - m |$ (가) 다음보다 크지 않은 경우에만 작동한다. w즉, 끝점은 대각선으로부터 창 길이 내에 있다. 알고리즘을 작동시키기 위해 윈도우 파라미터 w $|n-m|\leq w$ - $|n-m|\leq w$ $|n-m|\leq w$ $|n-m|\leq w$ $n-m \leq w$ 이( $|n-m|\leq 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)) // adapt window size (*)      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  ],    // insertion                                         DTW[i  , j-1],    // deletion                                         DTW[i-1, j-1])    // match      return DTW[n, m] }

뒤틀림 특성

DTW 알고리즘은 한 영상 시리즈의 기존 요소와 다른 영상 시리즈 사이의 이산 매칭을 생성한다. 즉, 시퀀스 내의 세그먼트에 대한 시간 척도를 허용하지 않는다. 다른 방법들은 계속해서 뒤틀리는 것을 허용한다. 예를 들어 COW(Correlation Optimized Warping)는 선형 보간법을 사용하여 시간에 따라 크기가 조정되는 균일한 세그먼트로 시퀀스를 분할하여 가장 잘 일치하는 워핑을 생성한다. 세그먼트 스케일링은 DTW의 원시 요소 이산 매칭보다 더 민감한 뒤틀림을 생성하며, 하향 또는 상향 조정 세그먼트에 의해 새로운 요소의 잠재적 생성을 유발한다.

복잡성

DTW 알고리즘의 시간 복잡성은 $O(NM)$ M $O(NM)$ ) $O(NM)$ 이며 $O(NM)$ 여기서 $N$ $N$ 과 $N$ M $M$ 은 두 입력 시퀀스의 길이입니다 $M$ . .[2]이 알고리즘 또한 다른 l.의 시퀀스에 적응할 수 있는 50살 2차 시간에 묶여 최근에, 금·Sharir로 인한 알고리즘 컴퓨팅 DTW O에서(N2/로그 ⁡ 로그 ⁡(N) 할 수 있게 하는)length N{N\displaystyle}의 2개 입력 시퀀스에{\displaystyle O({N^{2}}/\log \log(N))}시간과 공간을 깨트렸다engths. 이러한 개선에도 불구하고, $\epsilon >0$ $\epsilon >0$ > 0 $\epsilon >0$ ${\$ $displaystyle$ $O$ $epsilon }}})$ 에 $O(N^{2-\epsilon })$ 대한 $O(N^{2-\epsilon })$ 한 2분법 실행 시간은 강 지수 시간 가설이 실패하지 않는 한 존재할 수 없다는 $\epsilon >0$ 것을 보여주었다.^[3]^[4]

DTW의 동적 프로그래밍 알고리즘은 순진한 구현에서 $O(NM)$ ( $O(NM)$ M $){\displaystyle$ O $(NM)}$ 공간을 $O(NM)$ 필요로 하는 반면, 공간 소비량은 허쉬버그의 알고리즘을 이용하여 $O(min(N,M))$ $O(min(N,M))$ $O(min(N,M))$ $O(min(N,M))$ $){\displaystyle O(N,M)}$ 로 줄일 수 있다.

빠른 연산

Pruned를 포함한 DTW 컴퓨팅을 위한 빠른 기술DTW,^[5] 스파스DTW,^[6] FastDTW ^[7]및 멀티스케일DTW.^[8]^[9] 유사한 시계열의 검색인 공통 작업은 LB_Keogh^[10] 또는 LB_Improveed와 같은 하한을 사용하여 가속할 수 있다.^[11] 한 조사에서 왕 외 연구진은 LB_Keogh 바운드보다 LB_Envanced lower bound로 약간 더 나은 결과를 보고했고, 다른 기법이 비효율적이라는 것을 발견했다.^[12]

평균순서

동적 시간 뒤틀림 평균은 일련의 시퀀스에 대한 평균 시퀀스를 찾는 문제다. NLAF는^[13] DTW를 사용하여 두 시퀀스를 평균화하는 정확한 방법이다. 세 개 이상의 시퀀스에 대해 문제는 다중 정렬 중 하나와 관련되며 휴리스틱스가 필요하다. DBA는^[14] 현재 DTW와 일관되게 일련의 시퀀스를 평균화하는 참조 방법이며, COMASA는^[15] DBA를 로컬 최적화 프로세스로 사용하여 평균 시퀀스에 대한 검색을 효율적으로 랜덤화한다.

감독 학습

가장 가까운 분류기는 동적 시간 뒤틀림을 거리 측정으로 사용할 때 최첨단 성능을 얻을 수 있다.^[16]

대체 접근 방식

기능 데이터 분석에서 시계열은 시간의 매끄러운 (차별 가능한) 함수의 분실로 간주된다. 관찰된 표본을 매끄러운 함수로 보면 연속수학을 활용해 데이터를 분석할 수 있다.^[17] 예를 들어 시간 워프 함수의 매끄럽고 단조로운 점은 시간 분산 방사상 기준 함수를 통합하여 1차원 차이점형 함수를 얻을 수 있다.^[18] 최적의 비선형 시간 뒤틀림 함수는 함수 집합의 거리 측정과 뒤틀림 평균을 최소화하여 계산한다. 휘는 함수에 대한 거칠기 페널티 항은 곡률 크기를 제한하여 추가할 수 있다. 결과적으로 뒤틀림 기능이 원활해 추가 처리가 용이하다. 이 접근방식은 언어 움직임의 패턴과 변동성을 분석하는 데 성공적으로 적용되었다.^[19]^[20]

또 다른 관련 접근방식은 숨겨진 마르코프 모델(HM)이며, HM을 통해 가장 가능성이 높은 경로를 검색하는 데 사용되는 비테르비 알고리즘은 확률론 DTW와 동등하다는 것이 밝혀졌다.^[21]^[22]^[23]

DTW 및 관련 뒤틀림 방법은 일반적으로 데이터 분석에서 사전 또는 사후 처리 단계로 사용된다. 관측된 시퀀스가 값, 관측된 시퀀스의 형태 및 랜덤 시간 정렬의 두 가지 변동을 모두 포함하는 경우, 뒤틀림이 노이즈에 오버핏되어 편향된 결과를 초래할 수 있다. 두 값(수직)과 시간 매개변수(수평)의 랜덤 변동을 갖는 동시 모형 제형은 비선형 혼합 효과 모델의 예다.^[24] 인간 이동 분석에서 동시 비선형 혼합 효과 모델링은 DTW에 비해 우수한 결과를 생성하는 것으로 나타났다.^[25]

오픈소스 소프트웨어

lb향상된 C++ 라이브러리는 GNU General Public License(GPL)에 따라 Fast Near-Neighbor Research 알고리즘을 구현한다. 또한 다양한 하한뿐만 아니라 동적 시간 뒤틀림의 C++ 구현도 제공한다.
FastDTW 라이브러리는 표준 DTW 알고리즘에 대한 O(N²) 요구사항과 대조적으로 O(N) 시간 및 메모리 복잡성에 대한 최적 또는 거의 최적 맞춤을 제공하는 DTW와 FastDTW 구현의 자바 구현이다. FastDTW는 다단계 접근방식을 사용하여 코어저 해상도에서 솔루션을 재귀적으로 투영하고 투영된 솔루션을 재조정한다.
FastDTW 포크(Java)가 메이븐 센트럴에 발행되었다.
Weka에서 DTW를 사용한 시계열 분류용 패키지(Java).
DTW 제품군은 Python(dtw-python)과 R 패키지(dtw)에 다양한 재귀 규칙(단계 패턴이라고도 함), 제약 조건 및 하위 문자열 일치를 포함하여 DTW 알고리즘 패밀리 멤버에 대한 포괄적인 커버리지를 제공한다.
mlpy Python 라이브러리는 DTW를 구현한다.
Pydtw Python 라이브러리는 LB_Keogh 하한을 포함한 맨해튼 및 유클리드 향의 DTW 조치를 구현한다.
C++/CUDA 라이브러리는 CUDA 지원 가속기에서 인기 있는 UCR-Suite와 유사한 유클리드-향료 DTW 및 z-정규화된 유클리드 거리를 다시 정렬하는 기능을 구현한다.
JavaML 머신러닝 라이브러리는 DTW를 구현한다.
ndtw C# 라이브러리는 다양한 옵션으로 DTW를 구현한다.
Sketch-a-Char는 LaTeX 기호 분류 프로그램의 일부로 Twich DTW(JavaScript에서 구현됨)를 사용한다.
MatchBox는 오디오 신호의 멜-주파수 cepsstral 계수를 일치시키기 위해 DTW를 구현한다.
시퀀스 평균화: DBA의 GPL Java 구현.^[14]
제스처 인식 툴킷 GRT C+++ 실시간 제스처 인식 툴킷은 DTW를 구현한다.
PyHubs 소프트웨어 패키지는 DTW와 가장 가까운 이웃의 분류자 및 확장자(허브스 인식 분류자)를 구현한다.
단순화된 Two Python 라이브러리는 고전적인 O(NM) 동적 프로그래밍 알고리즘을 구현하고 Numpy를 기반으로 한다. 거리에 대한 사용자 정의 표준 함수를 사용할 뿐만 아니라 모든 차원의 값을 지원한다. 그것은 MIT 면허에 따라 면허가 있다.
Tslearn Python 라이브러리는 시계열 컨텍스트에서 DTW를 구현한다.
TWED CUDA Python 라이브러리는 경이적인 속도의 선형 메모리만을 사용하여 개선된 시간 워프 편집 거리 기술을 구현한다.
DynamicAxisWarping.jl은 Julia의 DTW 구현 및 FastDTW, SoftDTW, GeneralDTW 및 DTW 바이리센서와 같은 관련 알고리즘이다.

적용들

구어 인식

말하기 비율이 다르기 때문에 음성 패턴 대 시간 축에 비선형 변동이 발생하는데, 이를 제거해야 한다.^[26] DP 매칭은 시간 정규화 효과를 이용한 동적 프로그래밍(DP) 기반의 패턴 매칭 알고리즘으로, 시간 축의 변동은 비선형 시간 워핑 함수를 사용하여 모델링한다. 어떤 두 가지 언어 패턴을 고려했을 때, 우리는 다른 언어와 최대의 우연이 이루어지도록 한 언어의 시간 축을 뒤틀어서 그들의 시간 차이를 없앨 수 있다. 게다가, 만약 뒤틀림 기능이 가능한 어떤 값을 취하도록 허용된다면, 다른 범주에 속하는 단어들 간에 매우 적은^[clarify] 구별이 이루어질 수 있다. 그래서, 다른 범주에 속하는 단어의 구별을 강화하기 위해, 뒤틀림 함수 경사면에 제한을 두었다.

상관 전력 분석

불안정한 시계는 순진한 전력 분석을 물리치기 위해 사용된다. 이 방어에 대항하기 위해 몇 가지 기술이 사용되는데, 그 중 하나는 동적 시간 뒤틀림이다.

참고 항목

참조

^ Olsen, NL; Markussen, B; Raket, LL (2018), "Simultaneous inference for misaligned multivariate functional data", Journal of the Royal Statistical Society, Series C, 67 (5): 1147–76, arXiv:1606.03295, doi:10.1111/rssc.12276, S2CID 88515233
^ Gold, Omer; Sharir, Micha (2018). "Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier". Association for Computing Machinery. 14 (4). doi:10.1145/3230734. S2CID 52070903.
^ Bringmann, Karl; Künnemann, Marvin (2015). "Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 79–97. arXiv:1502.01063. doi:10.1109/FOCS.2015.15. ISBN 978-1-4673-8191-8. S2CID 1308171.
^ Abboud, Amir; Backurs, Arturs; Williams, Virginia Vassilevska (2015). "Tight Hardness Results for LCS and Other Sequence Similarity Measures". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 59–78. doi:10.1109/FOCS.2015.14. ISBN 978-1-4673-8191-8. S2CID 16094517.
^ 실바, D. F., 바티스타, G. E. A. A. A. (2015) All-Pairwise Dynamic Time Warping Matrix 계산 속도 향상.
^ 알 나이야트, G, 차울라, S, 타헤리, J. (2012) 스파스DTW: 동적 시간 워핑 속도를 높이기 위한 새로운 접근법
^ Stan Salvador, Philip Chan, FastDTW: To Strong Dynamic Time Warping in Linear Time and Space. KDD 시간 및 순차 데이터 마이닝 워크숍, 페이지 70–80, 2004.
^ 메이나드 뮐러, 헤닝 마테스, 프랭크 커스(2006) 등이 대표적이다. 효율적인 멀티스케일 방식의 오디오 동기화. 국제 음악 정보 검색 회의(ISMIR), 페이지 192-197.
^ 토마스 프래즐리히, 조나단 드라이거, 메이너드 뮐러(2016년). 메모리 제한 멀티스케일 동적 시간 워핑. 음향, 음성 및 신호 처리에 관한 IEEE 국제 회의(ICASSP), 페이지 569-573의 진행.
^ Keogh, E.; Ratanamahatana, C. A. (2005). "Exact indexing of dynamic time warping". Knowledge and Information Systems. 7 (3): 358–386. doi:10.1007/s10115-004-0154-9. S2CID 207056701.
^ Lemire, D. (2009). "Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound". Pattern Recognition. 42 (9): 2169–2180. arXiv:0811.3301. doi:10.1016/j.patcog.2008.11.030. S2CID 8658213.
^ Wang, Xiaoyue; et al. (2010). "Experimental comparison of representation methods and distance measures for time series data". Data Mining and Knowledge Discovery. 2010: 1–35. arXiv:1012.2789.
^ Gupta, L.; Molfese, D. L.; Tammana, R.; Simos, P. G. (1996). "Nonlinear alignment and averaging for estimating the evoked potential". IEEE Transactions on Biomedical Engineering. 43 (4): 348–356. doi:10.1109/10.486255. PMID 8626184. S2CID 28688330.
^ ^a ^b Petitjean, F. O.; Ketterlin, A.; Gançarski, P. (2011). "A global averaging method for dynamic time warping, with applications to clustering". Pattern Recognition. 44 (3): 678. doi:10.1016/j.patcog.2010.09.013.
^ Petitjean, F. O.; Gançarski, P. (2012). "Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment". Theoretical Computer Science. 414: 76–91. doi:10.1016/j.tcs.2011.09.029.
^ Ding, Hui; Trajcevski, Goce; Scheuermann, Peter; Wang, Xiaoyue; Keogh, Eamonn (2008). "Querying and mining of time series data: experimental comparison of representations and distance measures". Proc. VLDB Endow. 1 (2): 1542–1552. doi:10.14778/1454159.1454226.
^ Lucero, J. C.; Munhall, K. G.; Gracco, V. G.; Ramsay, J. O. (1997). "On the Registration of Time and the Patterning of Speech Movements". Journal of Speech, Language, and Hearing Research. 40 (5): 1111–1117. doi:10.1044/jslhr.4005.1111. PMID 9328881.
^ Durrleman, S; Pennec, X.; Trouvé, A.; Braga, J.; Gerig, G. & Ayache, N. (2013). "Toward a Comprehensive Framework for the Spatiotemporal Statistical Analysis of Longitudinal Shape Data". International Journal of Computer Vision. 103 (1): 22–59. doi:10.1007/s11263-012-0592-x. PMC 3744347. PMID 23956495.
^ Howell, P.; Anderson, A.; Lucero, J. C. (2010). "Speech motor timing and fluency". In Maassen, B.; van Lieshout, P. (eds.). Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. pp. 215–225. ISBN 978-0199235797.
^ Koenig, Laura L.; Lucero, Jorge C.; Perlman, Elizabeth (2008). "Speech production variability in fricatives of children and adults: Results of functional data analysis". The Journal of the Acoustical Society of America. 124 (5): 3158–3170. Bibcode:2008ASAJ..124.3158K. doi:10.1121/1.2981639. ISSN 0001-4966. PMC 2677351. PMID 19045800.
^ Nakagawa, Seiichi; Nakanishi, Hirobumi (1988-01-01). "Speaker-Independent English Consonant and Japanese Word Recognition by a Stochastic Dynamic Time Warping Method". IETE Journal of Research. 34 (1): 87–95. doi:10.1080/03772063.1988.11436710. ISSN 0377-2063.
^ Fang, Chunsheng. "From Dynamic Time Warping (DTW) to Hidden Markov Model (HMM)" (PDF).
^ Juang, B. H. (September 1984). "On the hidden Markov model and dynamic time warping for speech recognition #x2014; A unified view". AT&T Bell Laboratories Technical Journal. 63 (7): 1213–1243. doi:10.1002/j.1538-7305.1984.tb00034.x. ISSN 0748-612X. S2CID 8461145.
^ Raket LL, Sommer S, Markussen B (2014). "A nonlinear mixed-effects model for simultaneous smoothing and registration of functional data". Pattern Recognition Letters. 38: 1–7. doi:10.1016/j.patrec.2013.10.018.
^ Raket LL, Grimme B, Schöner G, Igel C, Markussen B (2016). "Separating timing, movement conditions and individual differences in the analysis of human movement". PLOS Computational Biology. 12 (9): e1005092. Bibcode:2016PLSCB..12E5092R. doi:10.1371/journal.pcbi.1005092. PMC 5033575. PMID 27657545.
^ Sakoe, Hiroaki; Chiba, Seibi (1978). "Dynamic programming algorithm optimization for spoken word recognition". IEEE Transactions on Acoustics, Speech, and Signal Processing. 26 (1): 43–49. doi:10.1109/tassp.1978.1163055.

추가 읽기

Vintsyuk, T. K. (1968). "Speech discrimination by dynamic programming". Kibernetika. 4: 81–88.
Sakoe, H.; Chiba (1978). "Dynamic programming algorithm optimization for spoken word recognition". IEEE Transactions on Acoustics, Speech, and Signal Processing. 26 (1): 43–49. doi:10.1109/tassp.1978.1163055.
Myers, C. S.; Rabiner, L. R. (1981). "A Comparative Study of Several Dynamic Time-Warping Algorithms for Connected-Word Recognition". Bell System Technical Journal. 60 (7): 1389–1409. doi:10.1002/j.1538-7305.1981.tb00272.x. ISSN 0005-8580. S2CID 12857347.
Rabiner, Lawrence; Juang, Biing-Hwang (1993). "Chapter 4: Pattern-Comparison Techniques". Fundamentals of speech recognition. Englewood Cliffs, N.J.: PTR Prentice Hall. ISBN 978-0-13-015157-5.
Müller, Meinard (2007). Dynamic Time Warping. In Information Retrieval for Music and Motion, chapter 4, pages 69-84 (PDF). Springer. doi:10.1007/978-3-540-74048-3. ISBN 978-3-540-74047-6.
Rakthanmanon, Thanawin (September 2013). "Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping". ACM Transactions on Knowledge Discovery from Data. 7 (3): 10:1–10:31. doi:10.1145/2513092.2500489. PMC 6790126. PMID 31607834.

[olsen_et_al_2018-1] Olsen, NL; Markussen, B; Raket, LL (2018), "Simultaneous inference for misaligned multivariate functional data", Journal of the Royal Statistical Society, Series C, 67 (5): 1147–76, arXiv:1606.03295, doi:10.1111/rssc.12276, S2CID 88515233

[2] Gold, Omer; Sharir, Micha (2018). "Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier". Association for Computing Machinery. 14 (4). doi:10.1145/3230734. S2CID 52070903.

[3] Bringmann, Karl; Künnemann, Marvin (2015). "Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 79–97. arXiv:1502.01063. doi:10.1109/FOCS.2015.15. ISBN 978-1-4673-8191-8. S2CID 1308171.

[4] Abboud, Amir; Backurs, Arturs; Williams, Virginia Vassilevska (2015). "Tight Hardness Results for LCS and Other Sequence Similarity Measures". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 59–78. doi:10.1109/FOCS.2015.14. ISBN 978-1-4673-8191-8. S2CID 16094517.

[5] 실바, D. F., 바티스타, G. E. A. A. A. (2015) All-Pairwise Dynamic Time Warping Matrix 계산 속도 향상.

[6] 알 나이야트, G, 차울라, S, 타헤리, J. (2012) 스파스DTW: 동적 시간 워핑 속도를 높이기 위한 새로운 접근법

[7] Stan Salvador, Philip Chan, FastDTW: To Strong Dynamic Time Warping in Linear Time and Space. KDD 시간 및 순차 데이터 마이닝 워크숍, 페이지 70–80, 2004.

[8] 메이나드 뮐러, 헤닝 마테스, 프랭크 커스(2006) 등이 대표적이다. 효율적인 멀티스케일 방식의 오디오 동기화. 국제 음악 정보 검색 회의(ISMIR), 페이지 192-197.

[9] 토마스 프래즐리히, 조나단 드라이거, 메이너드 뮐러(2016년). 메모리 제한 멀티스케일 동적 시간 워핑. 음향, 음성 및 신호 처리에 관한 IEEE 국제 회의(ICASSP), 페이지 569-573의 진행.

[10] Keogh, E.; Ratanamahatana, C. A. (2005). "Exact indexing of dynamic time warping". Knowledge and Information Systems. 7 (3): 358–386. doi:10.1007/s10115-004-0154-9. S2CID 207056701.

[11] Lemire, D. (2009). "Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound". Pattern Recognition. 42 (9): 2169–2180. arXiv:0811.3301. doi:10.1016/j.patcog.2008.11.030. S2CID 8658213.

[12] Wang, Xiaoyue; et al. (2010). "Experimental comparison of representation methods and distance measures for time series data". Data Mining and Knowledge Discovery. 2010: 1–35. arXiv:1012.2789.

[13] Gupta, L.; Molfese, D. L.; Tammana, R.; Simos, P. G. (1996). "Nonlinear alignment and averaging for estimating the evoked potential". IEEE Transactions on Biomedical Engineering. 43 (4): 348–356. doi:10.1109/10.486255. PMID 8626184. S2CID 28688330.

[DBA-14] Petitjean, F. O.; Ketterlin, A.; Gançarski, P. (2011). "A global averaging method for dynamic time warping, with applications to clustering". Pattern Recognition. 44 (3): 678. doi:10.1016/j.patcog.2010.09.013.

[15] Petitjean, F. O.; Gançarski, P. (2012). "Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment". Theoretical Computer Science. 414: 76–91. doi:10.1016/j.tcs.2011.09.029.

[16] Ding, Hui; Trajcevski, Goce; Scheuermann, Peter; Wang, Xiaoyue; Keogh, Eamonn (2008). "Querying and mining of time series data: experimental comparison of representations and distance measures". Proc. VLDB Endow. 1 (2): 1542–1552. doi:10.14778/1454159.1454226.

[17] Lucero, J. C.; Munhall, K. G.; Gracco, V. G.; Ramsay, J. O. (1997). "On the Registration of Time and the Patterning of Speech Movements". Journal of Speech, Language, and Hearing Research. 40 (5): 1111–1117. doi:10.1044/jslhr.4005.1111. PMID 9328881.

[18] Durrleman, S; Pennec, X.; Trouvé, A.; Braga, J.; Gerig, G. & Ayache, N. (2013). "Toward a Comprehensive Framework for the Spatiotemporal Statistical Analysis of Longitudinal Shape Data". International Journal of Computer Vision. 103 (1): 22–59. doi:10.1007/s11263-012-0592-x. PMC 3744347. PMID 23956495.

[19] Howell, P.; Anderson, A.; Lucero, J. C. (2010). "Speech motor timing and fluency". In Maassen, B.; van Lieshout, P. (eds.). Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. pp. 215–225. ISBN 978-0199235797.

[20] Koenig, Laura L.; Lucero, Jorge C.; Perlman, Elizabeth (2008). "Speech production variability in fricatives of children and adults: Results of functional data analysis". The Journal of the Acoustical Society of America. 124 (5): 3158–3170. Bibcode:2008ASAJ..124.3158K. doi:10.1121/1.2981639. ISSN 0001-4966. PMC 2677351. PMID 19045800.

[21] Nakagawa, Seiichi; Nakanishi, Hirobumi (1988-01-01). "Speaker-Independent English Consonant and Japanese Word Recognition by a Stochastic Dynamic Time Warping Method". IETE Journal of Research. 34 (1): 87–95. doi:10.1080/03772063.1988.11436710. ISSN 0377-2063.

[22] Fang, Chunsheng. "From Dynamic Time Warping (DTW) to Hidden Markov Model (HMM)" (PDF).

[23] Juang, B. H. (September 1984). "On the hidden Markov model and dynamic time warping for speech recognition #x2014; A unified view". AT&T Bell Laboratories Technical Journal. 63 (7): 1213–1243. doi:10.1002/j.1538-7305.1984.tb00034.x. ISSN 0748-612X. S2CID 8461145.

[Raket_et_al_2014-24] Raket LL, Sommer S, Markussen B (2014). "A nonlinear mixed-effects model for simultaneous smoothing and registration of functional data". Pattern Recognition Letters. 38: 1–7. doi:10.1016/j.patrec.2013.10.018.

[Raket_et_al_2016-25] Raket LL, Grimme B, Schöner G, Igel C, Markussen B (2016). "Separating timing, movement conditions and individual differences in the analysis of human movement". PLOS Computational Biology. 12 (9): e1005092. Bibcode:2016PLSCB..12E5092R. doi:10.1371/journal.pcbi.1005092. PMC 5033575. PMID 27657545.

[26] Sakoe, Hiroaki; Chiba, Seibi (1978). "Dynamic programming algorithm optimization for spoken word recognition". IEEE Transactions on Acoustics, Speech, and Signal Processing. 26 (1): 43–49. doi:10.1109/tassp.1978.1163055.

[1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

Search