Idővonal dinamikus transzformációs algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. december 12-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

Az időskála dinamikus transzformációjának algoritmusa ( DTW-algoritm , az angol dynamic time warping szóból ) egy olyan algoritmus , amely lehetővé teszi az idősorok közötti optimális egyezés megtalálását. Először a beszédfelismerésben alkalmazták , ahol annak meghatározására szolgál, hogy két beszédjel hogyan reprezentálja ugyanazt az eredeti kimondott kifejezést. Ezt követően más területeken is találtak alkalmazásokat [1] .

Az idősorok egy széles körben használt adattípus[ tisztázni ] gyakorlatilag bármely tudományterületen előfordul, és két szekvencia összehasonlítása szokásos feladat. Az eltérés kiszámításához elegendő két sorozat összetevői közötti távolság egyszerű mérése (euklideszi távolság). Azonban gyakran két sorozatnak megközelítőleg azonos az általános alakja, de ezek az alakzatok nem illeszkednek az x tengelyhez. Az ilyen sorozatok közötti hasonlóság megállapításához a sorozat egyik (vagy mindkettő) időtengelyét "el kell vetemítenünk" jobb összhangot elérni. [2]

Algoritmus

Két idősor közötti távolság mérése szükséges ahhoz, hogy meghatározzuk hasonlóságukat és osztályozásukat. Ilyen hatékony mérés az euklideszi metrika . Két idősorozat esetén ez egyszerűen az egyik sorozat n-edik pontja és a másik n-edik pontja közötti távolság négyzetének összege. Az euklideszi távolság használatának azonban van egy jelentős hátulütője is: ha két idősor azonos, de az egyik időben kissé eltolódott (az időtengely mentén), akkor az euklideszi metrika figyelembe veheti, hogy a sorozatok különböznek egymástól. . A DTW algoritmust azért vezették be, hogy kiküszöböljék ezt a hiányosságot, és vizuálisan lemérjék a sorok közötti távolságot, figyelmen kívül hagyva az időskála globális és lokális eltolódásait . [3]

Klasszikus algoritmus

Tekintsünk két idősort – hosszúságot és hosszt [4] : $K$ $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)

Az algoritmus első szakasza a következő. Készítünk egy sorrendi mátrixot ( távolságmátrix ) , amelyben az elem a két pont közötti távolság és . Általában az euklideszi távolságot használják: , vagy . A mátrix minden eleme megfelel a pontok és a pontok közötti igazításnak . $d$ $n\szer m$ ${\displaystyle d_{i\;j))$ $d(q_{i},c_{j})$ ${\displaystyle 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)$ ${\displaystyle q_{i))$ ${\displaystyle c_{j))$

A második lépésben felállítunk egy transzformációs (deformációs) mátrixot , amelynek minden elemét a következő összefüggés alapján számítjuk ki: $D$

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

A transzformációs mátrix kitöltése után továbblépünk az utolsó lépésre, ami egy optimális transzformációs út (deformáció) és DTW távolság (útköltség) felépítése .
A transzformációs útvonal szomszédos mátrixelemek halmaza, amely és között van leképezve . Azt az utat jelöli, amely minimálisra csökkenti a és közötti teljes távolságot . Az útvonal edik eleme a következőképpen van definiálva: . Ilyen módon: $W$ $K$ $C$ $K$ $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,

hol van az út hossza. $K$

Az átalakítási útvonalnak meg kell felelnie a következő kényszerfeltételeknek:

Peremfeltételek : az út eleje , vége - . Ez a megszorítás biztosítja, hogy a transzformációs útvonal mindkét idősor összes pontját tartalmazza. $w_{1}=(1,1)$ $w_{K}=(n,m)$
Folytonosság (a lépéshossz feltétele): a , és az útvonal bármely két szomszédos eleme kielégíti a következő egyenlőtlenségeket: , . Ez a megkötés biztosítja, hogy az átalakítási útvonal lépésenként mozogjon. Vagyis mindkét index és csak 1-gyel nőhet az útvonal minden lépésében. $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$ $én$ $j$
Monotonitás : a , és a pálya bármely két szomszédos eleme kielégíti a következő egyenlőtlenségeket: , . Ez a megkötés biztosítja, hogy az átalakítási útvonal ne térjen vissza arra a pontra, amelyen áthaladt. Vagyis mindkét index vagy ugyanaz marad, vagy nő (de soha nem csökken). $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$ $én$ $j$

Bár sok olyan transzformációs útvonal létezik, amely az összes fenti feltételt kielégíti, minket azonban csak az az útvonal érdekel, amely minimalizálja a DTW távolságot (útköltség ) .

A két sorozat közötti DTW távolság (útköltség ) az optimális transzformációs út alapján kerül kiszámításra a következő képlet segítségével:

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

$K$ a nevezőben azt a tényt használják, hogy a transzformációs utak különböző hosszúságúak lehetnek.

Az algoritmus térbeli és időbeli összetettsége kvadratikus, mivel a DTW algoritmusnak a transzformációs mátrix minden celláját meg kell vizsgálnia. $O(nm)$

Az algoritmus hátrányai

Bár az algoritmust számos területen sikeresen alkalmazták, hibás eredményeket produkálhat. Az algoritmus megpróbálhatja megmagyarázni a tengely volatilitását egy tengelytranszformációval . Ez olyan igazodáshoz vezethet, amelyben az első sorozat egyik pontja a második szekvencia pontjainak nagy részhalmazához van leképezve. $y$ $x$

Egy másik probléma az, hogy az algoritmus nem találja két sorozat nyilvánvaló igazítását, mivel az egyik sorozat szinguláris pontja (csúcs, mélypont, plató, inflexiós pont ) valamivel a másik sorozat megfelelő szinguláris pontja felett vagy alatt helyezkedik el. [5] .

A DTW algoritmus változatai

A DTW algoritmus különféle finomításainak célja a számítások felgyorsítása, valamint a transzformációs utak lehetséges útvonalainak jobb szabályozása.

Általános (globális) korlátozások

A DTW algoritmus egyik elterjedt változata az általános (globális) korlátozó feltételek előírása a megengedett alakváltozási utakra [6] . Legyen egy részhalmaz , amely meghatározza a globális kényszer területét. Most az átalakítási útvonal a . Az optimális átalakítási útvonal az az útvonal, amely a -hoz tartozik , és minimalizálja az útvonal költségét a -ból származó összes átalakítási útvonal között . $R\subseteq [1:n]\times [1:m]$ $R$ $R$ $R$

Gyors DTW algoritmus

Ennek az algoritmusnak lineáris tér és idő összetettsége van . A gyors DTW algoritmus réteges megközelítést használ három kulcsművelettel [7] :

Részletezés csökkenése - a szomszédos pontpárok átlagolásával csökkentjük az idősor méretét. Az eredményül kapott idősor egy olyan sorozat, amely feleannyi pontot tartalmaz, mint az eredeti. Ezt a műveletet többször futtatjuk, hogy sok különböző idősor felbontást kapjunk.
Tervezés - az átalakítási utat alacsony részletességgel választjuk, és meghatározzuk, hogy a következő részletnél mely cellákon halad át az átalakulási út (egy nagyságrenddel magasabb, mint az előző). Mivel a felbontás megduplázódik, a transzformációs útvonalhoz tartozó egy pont alacsony felbontáson legalább négy pontnak felel meg nagyobb felbontáson. Ezt a tervezett útvonalat ezután heurisztikaként használják a feldolgozás során a nagy felbontású útvonal megtalálásához.
A feldolgozás az optimális alakváltozási út keresése a tervezett út környezetében.

Ritka DTW algoritmus

Ennek a módszernek az a fő gondolata, hogy dinamikusan használja a hasonlóság jelenlétét és/vagy az adatok összehasonlítását két időszekvenciára vonatkozóan. Ennek az algoritmusnak három konkrét előnye van [8] :

A transzformációs mátrix ritka mátrixokkal van ábrázolva , ami az átlagos térkomplexitás csökkenését eredményezi más módszerekhez képest.
A ritka DTW algoritmus mindig az optimális transzformációs utat állítja elő.
Mivel az algoritmus optimális igazítást hoz létre, könnyen használható más módszerekkel kombinálva.

Alkalmazások

Jegyzetek

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Újszerű megközelítés a dinamikus idővetemítés felgyorsítására Archiválva : 2019. október 13. a Wayback Machine -nél
↑ Eamonn J. Keogh, Michael J. Pazzani származtatott dinamikus idővetemítés, 1. szakasz Archiválva : 2016. július 30. a Wayback Machine -nél
↑ Stan Salvador és Philip Chan Fast DTW: A pontos dinamikus idővetemítés felé lineáris időben és térben Archiválva : 2014. október 31. a Wayback Machine -nél
↑ Eamonn J. Keogh, Michael J. Pazzani származtatott dinamikus idővetemítés, 2. szakasz Archiválva : 2016. július 30. a Wayback Machine -nél
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, 1. szakasz, 2. oldal Archivált 2016.07.30 . (Angol)
↑ DTW algoritmus áttekintése. 3.3 szakasz archiválva : 2014. december 17. a Wayback Machine -nél
↑ Stan Salvador és Philip ChanFast DTW: A pontos dinamikus idővetemítés felé lineáris időben és térben Archiválva : 2014. október 31. a Wayback Machine -nél
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Újszerű megközelítés a gyorsításhoz, 1.1. szakasz Archiválva : 2019. október 13. a Wayback Machine -nél