Algoritmul de transformare dinamică a cronologiei

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 decembrie 2014; verificările necesită 11 modificări .

Algoritmul pentru transformarea dinamică a scării de timp ( DTW-algorithm , din engleza dynamic time warping ) este un algoritm care vă permite să găsiți potrivirea optimă între secvențele de timp. Aplicat mai întâi în recunoașterea vorbirii , unde este folosit pentru a determina modul în care două semnale vocale reprezintă aceeași frază vorbită originală. Ulterior s-au găsit aplicații în alte domenii [1] .

Seria temporală este un tip de date utilizat pe scară largă[ clarifica ] care apare în aproape orice domeniu științific, iar compararea a două secvențe este o sarcină standard. Pentru a calcula abaterea, este suficientă o simplă măsurare a distanței dintre componentele a două secvențe (distanța euclidiană). Cu toate acestea, adesea două secvențe au aproximativ aceleași forme generale, dar aceste forme nu sunt aliniate pe axa X. Pentru a determina asemănarea dintre astfel de secvențe, trebuie să „deformam” axa temporală a uneia (sau a ambelor) secvențe pentru a obține o aliniere mai bună. [2]

Algoritm

Măsurarea distanței dintre două serii de timp este necesară pentru a determina asemănarea și clasificarea acestora. O astfel de măsurare eficientă este metrica euclidiană . Pentru două secvențe de timp, aceasta este pur și simplu suma distanțelor pătrate de la fiecare punct al n-lea al unei secvențe la al n-lea punct al celuilalt. Cu toate acestea, utilizarea distanței euclidiene are un dezavantaj semnificativ: dacă două serii temporale sunt aceleași, dar una dintre ele este ușor deplasată în timp (de-a lungul axei timpului), atunci metrica euclidiană poate considera că seria diferă una de cealaltă. . Algoritmul DTW a fost introdus pentru a depăși acest neajuns și pentru a oferi o măsurare vizuală a distanței dintre rânduri, fără a acorda atenție schimbărilor globale și locale pe scara de timp . [3]

Algoritm clasic

Luați în considerare două serii temporale - lungimi și lungimi [4] : $Q$ $n$ $C$ $m$

Q=q_{1},q_{2},\ldots,q_{i},\ldots,q_{n};\qquad \qquad (1)

C=c_{1},c_{2},\ldots,c_{j},\ldots,c_{m}.\qquad \qquad (2)

Prima etapă a algoritmului este următoarea. Construim o matrice de ordine ( matrice de distanta ) in care elementul este distanta dintre doua puncte si . De obicei se folosește distanța euclidiană: , sau . Fiecare element al matricei corespunde alinierii dintre punctele și . $d$ $de n\ ori m$ $d_{i\;j}$ $d(q_{i},c_{j})$ $q_{i}$ $c_{j)$ $d(q_{i},c_{j})=(q_{i}-c_{j})^{2}\quad$ $d(q_{i},c_{j})=|q_{i}-c_{j}|$ $(i, j)$ $q_{i}$ $c_{j)$

În a doua etapă, construim o matrice de transformare (deformare) , fiecare element fiind calculat pe baza următoarei relații: $D$

D_{i\;j}=d_{i\;j}+min({D_{i-1\;j},D_{i-1\;j-1},D_{i\;j -1}}).\qquad(3)

După completarea matricei de transformare, trecem la pasul final, care este construirea unei căi de transformare optime (deformare) și a distanței DTW ( costul căii ).
O cale de transformare este un set de elemente matrice adiacente care se mapează între și . Reprezintă calea care minimizează distanța totală dintre și . Al-lea element al căii este definit ca . În acest fel: $W$ $Q$ $C$ $Q$ $C$ $k$ $W$ $w_{k}=(i,j)_{k},\quad d(w_{k})=d(q_{i},c_{j})=(q_{i}-c_{j })^{2}$

W=w_{1},w_{2},\ldots,w_{k},\ldots,w_{K};\qquad max(m,n)\leqslant K<m+n,

unde este lungimea drumului. $K$

Calea de transformare trebuie să îndeplinească următoarele condiții de constrângere:

Condiții de limită : începutul căii , sfârșitul acesteia - . Această constrângere asigură că calea de transformare conține toate punctele ambelor serii de timp. $w_{1}=(1,1)$ $w_{K}=(n,m)$
Continuitate (condiție privind lungimea pasului): oricare două elemente adiacente ale căii , și , satisfac următoarele inegalități: , . Această constrângere asigură că calea de transformare se deplasează cu un pas la un moment dat. Adică, ambii indici și pot crește doar cu 1 la fiecare pas al căii. $W$ $w_{k}=(w_{i},w_{j})$ $w_{k+1}=(w_{i+1},w_{j+1})$ $w_{i}-w_{i+1}\leqslant 1$ $w_{j}-w_{j+1}\leqslant 1$ $i$ $j$
Monotonicitate : oricare două elemente adiacente ale căii , și , satisfac următoarele inegalități: , . Această constrângere asigură că calea de transformare nu se întoarce la punctul în care a trecut. Adică ambii indici și fie rămân la fel, fie cresc (dar nu scad niciodată). $W$ $w_{k}=(w_{i},w_{j})$ $w_{k-1}=(w_{i-1},w_{j-1})$ $w_{i}-w_{i-1}\geqslant 0$ $w_{j}-w_{j-1}\geqslant 0$ $i$ $j$

Deși există un număr mare de căi de transformare care satisfac toate condițiile de mai sus, totuși, ne interesează doar calea care minimizează distanța DTW ( costul căii ).

Distanța DTW ( costul drumului ) dintre două secvențe este calculată pe baza traseului optim de transformare folosind formula:

DTW(Q,C)=min\left\{{\frac {\sum \limits _{k=1}^{K}{d(w_{k)))}} {K}}\dreapta \ }.\qquad(4)

$K$ în numitor este folosit pentru a explica faptul că traseele de transformare pot fi de lungimi diferite.

Complexitatea spațială și temporală a algoritmului este pătratică, deoarece algoritmul DTW trebuie să examineze fiecare celulă a matricei de transformare. $O(nm)$

Dezavantajele algoritmului

Deși algoritmul a fost utilizat cu succes în multe domenii, poate produce rezultate incorecte. Algoritmul poate încerca să explice volatilitatea axei printr-o transformare a axei . Acest lucru poate duce la o aliniere în care un punct din prima secvență este mapat la un subset mare de puncte din a doua secvență. $y$ $X$

O altă problemă este că algoritmul poate să nu găsească o aliniere evidentă a două serii din cauza faptului că punctul singular (vârf, jgheab, platou, punct de inflexiune ) al unei serii este situat puțin deasupra sau sub punctul singular corespunzător al celeilalte serii. [5] .

Varietăți ale algoritmului DTW

Diverse perfecționări ale algoritmului DTW sunt menite să accelereze calculele acestuia, precum și să controleze mai bine rutele posibile ale căilor de transformare.

Restricții generale (globale)

Una dintre variantele comune ale algoritmului DTW este impunerea unor condiții limitative generale (globale) pe căile de deformare admisibile [6] . Fie o submulțime care definește aria constrângerii globale. Acum calea de transformare este calea conținută în . Calea optimă de transformare este calea care aparține și minimizează costul căii dintre toate căile de transformare de la . $R\subseteq [1:n]\times [1:m]$ $R$ $R$ $R$

Algoritm DTW rapid

Acest algoritm are complexitate liniară în spațiu și timp . Algoritmul rapid DTW utilizează o abordare stratificată cu trei operații cheie [7] :

Scăderea în detaliu - reducem dimensiunea seriei de timp făcând media perechilor de puncte adiacente. Seria temporală rezultată este o serie care are jumătate din mai multe puncte decât cea originală. Efectuăm această operațiune de mai multe ori pentru a obține mai multe rezoluții diferite în serie de timp.
Planificare - luăm calea de transformare la detalii reduse și determinăm prin ce celule va trece calea de transformare la următorul detaliu (un ordin de mărime mai mare decât cel precedent). Deoarece rezoluția este dublată, un punct aparținând căii de transformare la rezoluție scăzută va corespunde cu cel puțin patru puncte la rezoluție mai mare. Această cale planificată este apoi utilizată ca euristică în timpul procesării pentru a găsi calea de înaltă rezoluție.
Prelucrarea este căutarea traseului optim de deformare în vecinătatea traseului planificat.

Algoritm DTW rar

Ideea principală a acestei metode este utilizarea dinamică a prezenței similarității și/sau a comparării datelor pentru două secvențe de timp. Acest algoritm are trei avantaje specifice [8] :

Matricea de transformare este reprezentată folosind matrici rare , rezultând o reducere a complexității medii a spațiului în comparație cu alte metode.
Algoritmul DTW rar produce întotdeauna calea optimă de transformare.
Deoarece algoritmul produce o aliniere optimă, poate fi utilizat cu ușurință în combinație cu alte metode.

Aplicații

recunoaștere a vorbirii
extragerea datelor
recunoașterea gesturilor
robotică
medicamentul
bioinformatica
verificarea semnăturii

Note

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: O abordare inedită pentru a accelera Dynamic Time Warping Arhivat 13 octombrie 2019 la Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Secțiunea 1 Arhivată la 30 iulie 2016 la Wayback Machine
↑ Stan Salvador și Philip Chan Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Arhivat la 31 octombrie 2014 la Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Secțiunea 2 Arhivată la 30 iulie 2016 la Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Secțiunea 1, pagina 2 Arhivat 30.07.2016 . (Engleză)
↑ DTW Algorithm Review. Secțiunea 3.3 Arhivată la 17 decembrie 2014 la Wayback Machine
↑ Stan Salvador și Philip ChanFast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Arhivat la 31 octombrie 2014 la Wayback Machine
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up, Secțiunea 1.1 Arhivat la 13 octombrie 2019 la Wayback Machine