Algoritmus dynamické transformace časové osy

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. prosince 2014; kontroly vyžadují 11 úprav .

Algoritmus pro dynamickou transformaci časové škály ( DTW-algorithm , z anglického dynamic time warping ) je algoritmus , který umožňuje najít optimální shodu mezi časovými sekvencemi. Poprvé použito v rozpoznávání řeči , kde se používá k určení, jak dva řečové signály reprezentují stejnou původní mluvenou frázi. Následně byly nalezeny aplikace v dalších oblastech [1] .

Časová řada je široce používaný datový typ[ objasnit ] vyskytující se prakticky v jakékoli vědecké oblasti a porovnávání dvou sekvencí je standardním úkolem. Pro výpočet odchylky stačí jednoduché měření vzdálenosti mezi složkami dvou posloupností (euklidovská vzdálenost). Často však dvě sekvence mají přibližně stejné obecné tvary, ale tyto tvary nejsou zarovnány na ose x. Abychom určili podobnost mezi takovými sekvencemi, musíme „pokřivit“ časovou osu jedné (nebo obou) sekvence tak, aby dosáhnout lepšího zarovnání. [2]

Algoritmus

Měření vzdálenosti mezi dvěma časovými řadami je nezbytné pro určení jejich podobnosti a klasifikace. Takovým efektivním měřením je euklidovská metrika . Pro dvě časové sekvence je to jednoduše součet čtverců vzdáleností od každého n-tého bodu jedné sekvence k n-tému bodu druhé. Použití euklidovské vzdálenosti má však značnou nevýhodu: pokud jsou dvě časové řady stejné, ale jedna z nich je mírně posunuta v čase (podél časové osy), pak euklidovská metrika může uvažovat, že se řady od sebe liší. . Algoritmus DTW byl zaveden s cílem překonat tento nedostatek a poskytnout vizuální měření vzdálenosti mezi řadami, aniž by se věnovala pozornost jak globálním, tak lokálním posunům na časové škále . [3]

Klasický algoritmus

Uvažujme dvě časové řady – délky a délky [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)

První fáze algoritmu je následující. Sestrojíme matici řádu ( matici vzdálenosti ), ve které je prvkem vzdálenost mezi dvěma body a . Obvykle se používá euklidovská vzdálenost: , nebo . Každý prvek matice odpovídá zarovnání mezi body a . $d$ $n\krát m$ $d_{i\;j}$ $d(q_{i},c_{j})$ $q_{i}$ ${\displaystyle 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}$ ${\displaystyle c_{j))$

Ve druhé fázi vytvoříme transformační (deformační) matici , jejíž každý prvek se vypočítá na základě následujícího vztahu: $D$

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

Po vyplnění transformační matice přejdeme k poslednímu kroku, kterým je sestavení nějaké optimální transformační cesty (deformace) a vzdálenosti DTW ( path cost ).
Transformační cesta je sada sousedních prvků matice, která mapuje mezi a . Představuje cestu, která minimalizuje celkovou vzdálenost mezi a . Prvek cesty je definován jako . Takto: $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,

kde je délka cesty. $K$

Transformační cesta musí splňovat následující omezující podmínky:

Okrajové podmínky : začátek cesty , její konec - . Toto omezení zajišťuje, že transformační cesta obsahuje všechny body obou časových řad. $w_{1}=(1,1)$ $w_{K}=(n,m)$
Spojitost (podmínka délky kroku): libovolné dva sousední prvky cesty , a , splňují následující nerovnosti: , . Toto omezení zajišťuje, že se transformační cesta pohybuje vždy o jeden krok. To znamená, že oba indexy a mohou se zvýšit pouze o 1 v každém kroku cesty. $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$
Monotónnost : libovolné dva sousední prvky cesty , a , splňují následující nerovnosti: , . Toto omezení zajišťuje, že se cesta transformace nevrátí do bodu, kterým prošla. To znamená, že oba indexy a buď zůstávají stejné, nebo rostou (ale nikdy neklesají). $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$

Přestože existuje velké množství transformačních cest, které splňují všechny výše uvedené podmínky, nás zajímá pouze cesta, která minimalizuje vzdálenost DTW ( path cost ).

Vzdálenost DTW ( náklady na cestu ) mezi dvěma sekvencemi se vypočítá na základě optimální transformační cesty pomocí vzorce:

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

$K$ ve jmenovateli se používá k zohlednění skutečnosti, že transformační cesty mohou mít různé délky.

Prostorová a časová složitost algoritmu je kvadratická, protože algoritmus DTW musí zkoumat každou buňku transformační matice. $O(nm)$

Nevýhody algoritmu

Přestože byl algoritmus úspěšně použit v mnoha oblastech, může přinést nesprávné výsledky. Algoritmus se může pokusit vysvětlit volatilitu os pomocí transformace osy . To může vést k zarovnání, ve kterém je jeden bod v první sekvenci mapován na velkou podmnožinu bodů ve druhé sekvenci. $y$ $X$

Dalším problémem je, že algoritmus nemusí najít zřejmé zarovnání dvou řad kvůli skutečnosti, že singulární bod (vrchol, prohlubeň, plošina, inflexní bod ) jedné řady je umístěn mírně nad nebo pod odpovídajícím singulárním bodem druhé řady. [5] .

Odrůdy algoritmu DTW

Různá vylepšení algoritmu DTW mají urychlit jeho výpočty a také lépe řídit možné cesty transformačních cest.

Obecná (globální) omezení

Jednou z běžných variant algoritmu DTW je kladení obecných (globálních) omezujících podmínek na přípustné deformační dráhy [6] . Nechť je podmnožina , která definuje oblast globálního omezení. Nyní je cesta transformace cesta obsažená v souboru . Optimální transformační cesta je cesta, která patří a minimalizuje náklady na cestu mezi všemi transformačními cestami z . $R\subseteq [1:n]\times [1:m]$ $R$ $R$ $R$

Rychlý DTW algoritmus

Tento algoritmus má lineární prostorovou a časovou složitost . Rychlý DTW algoritmus používá vrstvený přístup se třemi klíčovými operacemi [7] :

Zmenšit v detailu - zmenšíme velikost časové řady zprůměrováním sousedních dvojic bodů. Výsledná časová řada je řada, která má o polovinu méně bodů než původní. Tuto operaci provádíme několikrát, abychom získali mnoho různých rozlišení časových řad.
Plánování - cestu transformace vezmeme při nízkém detailu a určíme, kterými buňkami bude cesta transformace procházet při dalším detailu (řádově vyšším než předchozím). Vzhledem k tomu, že rozlišení je dvojnásobné, jeden bod patřící do transformační cesty při nízkém rozlišení bude odpovídat alespoň čtyřem bodům při vyšším rozlišení. Tato plánovaná cesta je pak použita jako heuristika během zpracování k nalezení cesty s vysokým rozlišením.
Zpracování je hledání optimální deformační dráhy v okolí plánované dráhy.

Sparse DTW algoritmus

Hlavní myšlenkou této metody je dynamicky využívat přítomnost podobnosti a/nebo srovnání dat pro dvě časové sekvence. Tento algoritmus má tři specifické výhody [8] :

Transformační matice je reprezentována pomocí řídkých matic , což vede ke snížení průměrné prostorové složitosti ve srovnání s jinými metodami.
Řídký DTW algoritmus vždy vytváří optimální transformační cestu.
Protože algoritmus vytváří optimální zarovnání, lze jej snadno použít v kombinaci s jinými metodami.

Aplikace

Poznámky

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Nový přístup k urychlení dynamického zakřivení času Archivováno 13. října 2019 na Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, sekce 1 Archivováno 30. července 2016 na Wayback Machine
↑ Stan Salvador a Philip Chan Fast DTW: K přesné dynamické deformaci času v lineárním čase a prostoru Archivováno 31. října 2014 na Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, sekce 2 Archivováno 30. července 2016 na Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, sekce 1, strana 2 Archivováno 2016-07-30 . (Angličtina)
↑ DTW Algorithm Review. Sekce 3.3 Archivováno 17. prosince 2014 na Wayback Machine
↑ Stan Salvador a Philip ChanFast DTW: K přesné dynamické deformaci času v lineárním čase a prostoru Archivováno 31. října 2014 na Wayback Machine
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Nový přístup ke zrychlení, Oddíl 1.1 Archivováno 13. října 2019 na Wayback Machine