Tidslinje dynamisk transformationsalgoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 december 2014; kontroller kräver 11 redigeringar .

Algoritm för dynamisk transformation av tidsskalan ( DTW-algorithm , från engelskan dynamic time warping ) är en algoritm som låter dig hitta den optimala matchningen mellan tidssekvenser. Tillämpas först i taligenkänning , där det används för att bestämma hur två talsignaler representerar samma ursprungliga talade fras. Därefter hittades tillämpningar inom andra områden [1] .

Tidsserier är en mycket använd datatyp[ förtydliga ] förekommer inom praktiskt taget vilket vetenskapligt område som helst, och att jämföra två sekvenser är en standarduppgift. För att beräkna avvikelsen räcker det med en enkel mätning av avståndet mellan komponenterna i två sekvenser (euklidiskt avstånd). Ofta har dock två sekvenser ungefär samma allmänna former, men dessa former är inte inriktade på x-axeln. För att fastställa likheten mellan sådana sekvenser måste vi "förvränga" tidsaxeln för en (eller båda) av sekvensen till uppnå bättre anpassning. [2]

Algoritm

Att mäta avståndet mellan två tidsserier är nödvändigt för att bestämma deras likhet och klassificering. En sådan effektiv mätning är den euklidiska metriken . För två tidssekvenser är detta helt enkelt summan av de kvadratiska avstånden från varje n:te punkt i en sekvens till n:te punkten i den andra. Användningen av det euklidiska avståndet har dock en betydande nackdel: om två tidsserier är lika, men en av dem är något förskjuten i tid (längs tidsaxeln), kan den euklidiska metriken anse att serierna skiljer sig från varandra . DTW-algoritmen introducerades för att övervinna denna brist och ge en visuell mätning av avståndet mellan raderna, utan att ta hänsyn till både globala och lokala förändringar på tidsskalan . [3]

Klassisk algoritm

Tänk på två tidsserier - längder och längder [4] : $F$ $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)

Det första steget i algoritmen är som följer. Vi konstruerar en ordningsmatris ( avståndsmatris ) där elementet är avståndet mellan två punkter och . Vanligtvis används det euklidiska avståndet: , eller . Varje element i matrisen motsvarar inriktningen mellan punkterna och . $d$ $n\ gånger m$ $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))$

I det andra steget bygger vi en transformations (deformation) matris , vars varje element beräknas baserat på följande förhållande: $D$

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

Efter att ha fyllt i transformationsmatrisen går vi vidare till det sista steget, som är att bygga någon optimal transformationsväg (deformation) och DTW-avstånd ( vägkostnad ).
En transformationsbana är en uppsättning intilliggande matriselement som mappar mellan och . Den representerar vägen som minimerar det totala avståndet mellan och . Det e elementet i sökvägen definieras som . På det här sättet: $W$ $F$ $C$ $F$ $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,

var är vägens längd. $K$

Transformationsvägen måste uppfylla följande villkor:

Gränsförhållanden : början av vägen , dess slut- . Denna begränsning säkerställer att transformationsvägen innehåller alla punkter i båda tidsserierna. $w_{1}=(1,1)$ $w_{K}=(n,m)$
Kontinuitet (villkor på steglängd): två intilliggande element i banan , och , uppfyller följande ojämlikheter: , . Denna begränsning säkerställer att transformationsvägen rör sig ett steg i taget. Det vill säga både indexerar och kan bara öka med 1 vid varje steg på vägen. $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$
Monotonicitet : alla två angränsande delar av banan , och , uppfyller följande ojämlikheter: , . Denna begränsning säkerställer att transformationsvägen inte går tillbaka till den punkt den har passerat. Det vill säga, båda indexen och antingen förbli oförändrade eller öka (men aldrig minska). $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$

Även om det finns ett stort antal transformationsvägar som uppfyller alla ovanstående villkor, är vi dock bara intresserade av vägen som minimerar DTW-avståndet ( path cost ).

DTW-avståndet ( vägkostnad ) mellan två sekvenser beräknas baserat på den optimala transformationsvägen med hjälp av formeln:

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

$K$ i nämnaren används för att redogöra för det faktum att transformationsvägar kan vara av olika längd.

Algoritmens rumsliga och tidsmässiga komplexitet är kvadratisk, eftersom DTW-algoritmen måste undersöka varje cell i transformationsmatrisen. $På M)$

Nackdelar med algoritmen

Även om algoritmen har använts framgångsrikt på många områden, kan den ge felaktiga resultat. Algoritmen kan försöka förklara axelvolatiliteten med en axeltransformation . Detta kan leda till en inriktning där en punkt i den första sekvensen mappas till en stor delmängd av punkter i den andra sekvensen. $y$ $x$

Ett annat problem är att algoritmen kanske inte hittar en uppenbar anpassning av två serier på grund av det faktum att singularpunkten (topp, dal, platå, böjningspunkt ) för en serie ligger något över eller under motsvarande singularpunkt i den andra serien [5] .

Variationer av DTW-algoritmen

Olika förbättringar av DTW-algoritmen är avsedda att påskynda dess beräkningar, såväl som att bättre kontrollera de möjliga vägarna för transformationsvägar.

Allmänna (globala) restriktioner

En av de vanliga varianterna av DTW-algoritmen är införandet av allmänna (globala) begränsande villkor på tillåtna deformationsvägar [6] . Låt vara en delmängd som definierar området för den globala begränsningen. Nu är transformeringsvägen den sökväg som finns i . Den optimala transformationsvägen är den väg som hör till och minimerar kostnaden för vägen bland alla transformationsvägar från . $R\subseteq [1:n]\ gånger [1:m]$ $R$ $R$ $R$

Snabb DTW-algoritm

Denna algoritm har linjär rums- och tidskomplexitet . Den snabba DTW-algoritmen använder en skiktad metod med tre nyckeloperationer [7] :

Minska i detalj - vi minskar storleken på tidsserien genom att beräkna ett medelvärde av angränsande poängpar. Den resulterande tidsserien är en serie som har hälften så många poäng som den ursprungliga. Vi kör den här operationen flera gånger för att få många olika tidsserieupplösningar.
Planering - vi tar transformationsvägen vid låg detalj och bestämmer genom vilka celler transformationsvägen kommer att passera vid nästa detalj (en storleksordning högre än den föregående). Eftersom upplösningen fördubblas kommer en punkt som hör till transformationsvägen vid låg upplösning att motsvara minst fyra punkter med högre upplösning. Denna planerade väg används sedan som en heuristik under bearbetning för att hitta vägen med hög upplösning.
Bearbetning är sökandet efter den optimala deformationsvägen i närheten av den planerade banan.

Gles DTW-algoritm

Huvudidén med denna metod är att dynamiskt använda närvaron av likhet och/eller jämförelse av data för två tidssekvenser. Denna algoritm har tre specifika fördelar [8] :

Transformationsmatrisen representeras med glesa matriser , vilket resulterar i en minskning av den genomsnittliga rymdkomplexiteten jämfört med andra metoder.
Den glesa DTW-algoritmen producerar alltid den optimala transformationsvägen.
Eftersom algoritmen ger optimal anpassning kan den enkelt användas i kombination med andra metoder.

Applikationer

Anteckningar

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Ett nytt tillvägagångssätt för att snabba upp Dynamic Time Warping Arkiverad 13 oktober 2019 på Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, avsnitt 1 Arkiverad 30 juli 2016 på Wayback Machine
↑ Stan Salvador och Philip Chan Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Arkiverad 31 oktober 2014 på Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, avsnitt 2 Arkiverad 30 juli 2016 på Wayback Machine
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Avsnitt 1, sida 2 Arkiverad 2016-07-30 . (Engelsk)
↑ DTW Algorithm Review. Avsnitt 3.3 Arkiverad 17 december 2014 på Wayback Machine
↑ Stan Salvador och Philip ChanFast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space Arkiverad 31 oktober 2014 på Wayback Machine
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up, avsnitt 1.1 Arkiverad 13 oktober 2019 på Wayback Machine