Aikajanan dynaamisen muunnosalgoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. joulukuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Algoritmi aika-asteikon dynaamiseen muunnokseen ( DTW-algoritm , englanninkielisestä dynaamisesta aikavääristyksestä ) on algoritmi , jonka avulla voit löytää optimaalisen vastaavuuden aikajaksojen välillä. Ensin sovellettiin puheentunnistuksessa , jossa sitä käytetään määrittämään, kuinka kaksi puhesignaalia edustavat samaa alkuperäistä puhuttua lausetta. Myöhemmin sovelluksia löydettiin muilta alueilta [1] .

Aikasarjat ovat laajalti käytetty tietotyyppi[ selventää ] esiintyy käytännössä millä tahansa tieteenalalla, ja kahden sekvenssin vertailu on tavallinen tehtävä. Poikkeaman laskemiseksi riittää yksinkertainen kahden sekvenssin komponenttien välisen etäisyyden mittaus (euklidinen etäisyys). Usein kahdella sekvenssillä on kuitenkin suunnilleen samat yleiset muodot, mutta nämä muodot eivät ole kohdakkain x-akselilla. Sellaisten sekvenssien samankaltaisuuden määrittämiseksi meidän on "väännettävä" sekvenssin toisen (tai molempien) aika-akseli saavuttaa parempi kohdistus. [2]

Algoritmi

Kahden aikasarjan välisen etäisyyden mittaaminen on tarpeen niiden samankaltaisuuden ja luokituksen määrittämiseksi. Tällainen tehokas mittaus on euklidinen metriikka . Kahdella aikajaksolla tämä on yksinkertaisesti neliöityjen etäisyyksien summa yhden sekvenssin kustakin n:nnestä pisteestä toisen n:nnen pisteen välillä. Euklidisen etäisyyden käytössä on kuitenkin merkittävä haittapuoli: jos kaksi aikasarjaa ovat samat, mutta toinen niistä on hieman ajallisesti siirtynyt (aika-akselia pitkin), niin euklidinen metriikka voi katsoa sarjan eroavan toisistaan. . DTW-algoritmi otettiin käyttöön tämän puutteen poistamiseksi ja rivien välisen etäisyyden visuaalisen mittauksen saamiseksi kiinnittämättä huomiota sekä globaaleihin että paikallisiin aika-asteikon siirtymiin . [3]

Klassinen algoritmi

Tarkastellaan kahta aikasarjaa - pituudet ja pituudet [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)

Algoritmin ensimmäinen vaihe on seuraava. Rakennamme järjestysmatriisin ( etäisyysmatriisi ) , jossa elementti on kahden pisteen välinen etäisyys ja . Yleensä käytetään euklidista etäisyyttä: , tai . Jokainen matriisin elementti vastaa pisteiden ja :n välistä kohdistusta . $d$ $n\ kertaa 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))$

Toisessa vaiheessa rakennamme muunnos- (muodonmuutos)matriisin , jonka jokainen elementti lasketaan seuraavan suhteen perusteella: $D$

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

Muunnosmatriisin täyttämisen jälkeen siirrytään viimeiseen vaiheeseen, jossa rakennetaan optimaalinen muunnospolku (muodonmuutos) ja DTW-etäisyys ( polun hinta ).
Muunnospolku on joukko vierekkäisiä matriisielementtejä, jotka kartoitetaan välillä ja . Se edustaa polkua, joka minimoi kokonaisetäisyyden välillä ja . Polun th elementti on määritelty . Tällä tavalla: $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,

missä on polun pituus. $K$

Muunnospolun on täytettävä seuraavat rajoitusehdot:

Rajaehdot : polun alku , sen loppu - . Tämä rajoitus varmistaa, että muunnospolku sisältää kaikki pisteet molemmista aikasarjoista. $w_{1}=(1,1)$ $w_{K}=(n,m)$
Jatkuvuus (ehto askelpituudella): mitkä tahansa kaksi vierekkäistä polun elementtiä , ja , täyttävät seuraavat epäyhtälöt: , . Tämä rajoitus varmistaa, että muunnospolku liikkuu askel kerrallaan. Eli molemmat indeksit ja voivat kasvaa vain yhdellä polun jokaisessa vaiheessa. $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$
Monotonisuus : mitkä tahansa kaksi vierekkäistä polun , ja , elementtiä , täyttävät seuraavat epäyhtälöt: , . Tämä rajoitus varmistaa, että muunnospolku ei palaa siihen pisteeseen, jonka se on ohittanut. Toisin sanoen molemmat indeksit pysyvät samoina tai kasvavat (mutta ei koskaan laske) . $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$

Vaikka on olemassa suuri määrä muunnospolkuja, jotka täyttävät kaikki yllä olevat ehdot, olemme kuitenkin kiinnostuneita vain polusta, joka minimoi DTW-etäisyyden ( polun kustannus ).

Kahden sekvenssin välinen DTW-etäisyys ( polkukustannus ) lasketaan optimaalisen muunnospolun perusteella kaavalla:

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

$K$ nimittäjässä käytetään huomioimaan, että muunnospolut voivat olla eripituisia.

Algoritmin spatiaalinen ja ajallinen monimutkaisuus on neliöllinen, koska DTW-algoritmin on tutkittava jokainen muunnosmatriisin solu. $O (nm)$

Algoritmin haitat

Vaikka algoritmia on käytetty menestyksekkäästi monilla alueilla, se voi tuottaa virheellisiä tuloksia. Algoritmi voi yrittää selittää akselin volatiliteetin akselimuunnolla . Tämä voi johtaa kohdistukseen, jossa yksi piste ensimmäisessä sekvenssissä on kartoitettu suureen osajoukkoon toisen sekvenssin pisteitä. $y$ $x$

Toinen ongelma on, että algoritmi ei välttämättä löydä kahden sarjan ilmeistä kohdistusta johtuen siitä, että yhden sarjan singulaaripiste (huippu, pohja, tasanne, käännepiste ) sijaitsee hieman toisen sarjan vastaavan singulaaripisteen ylä- tai alapuolella. [5] .

DTW-algoritmin lajikkeet

DTW-algoritmin eri parannuksilla on tarkoitus nopeuttaa sen laskemista sekä ohjata paremmin muunnospolkujen mahdollisia reittejä.

Yleiset (globaalit) rajoitukset

Yksi yleisimmistä DTW-algoritmin muunnelmista on yleisten (globaalien) rajoittavien ehtojen asettaminen sallituille muodonmuutospoluille [6] . Olkoon osajoukko , joka määrittää globaalin rajoitteen alueen. Nyt muunnospolku on polku, joka sisältyy . Optimaalinen muunnospolku on polku, joka kuuluu ja minimoi polun kustannukset kaikkien muunnospolkujen joukossa kohteesta . $R\subseteq [1:n]\times [1:m]$ $R$ $R$ $R$

Nopea DTW-algoritmi

Tällä algoritmilla on lineaarinen tila ja aika monimutkaisuus . Nopea DTW-algoritmi käyttää kerrostettua lähestymistapaa, jossa on kolme avaintoimintoa [7] :

Vähennä yksityiskohtia - pienennämme aikasarjan kokoa laskemalla vierekkäisten pisteparien keskiarvon. Tuloksena oleva aikasarja on sarja, jossa on puolet alkuperäisestä pisteestä. Suoritamme tämän toiminnon useita kertoja saadaksemme monia erilaisia aikasarjaresoluutioja.
Suunnittelu - otamme muunnospolun alhaisella tarkkuudella ja määritämme, minkä solujen läpi muunnospolku kulkee seuraavassa yksityiskohdassa (suuruusluokkaa korkeampi kuin edellinen). Koska resoluutio on kaksinkertainen, yksi muunnospolkuun kuuluva piste pienellä resoluutiolla vastaa vähintään neljää pistettä korkeammalla resoluutiolla. Tätä suunniteltua polkua käytetään sitten heuristisena käsittelyn aikana korkean resoluution polun löytämiseksi.
Prosessointi on optimaalisen muodonmuutospolun etsimistä suunnitellun polun läheisyydestä.

Harva DTW-algoritmi

Tämän menetelmän pääideana on käyttää dynaamisesti kahden aikajakson tietojen samankaltaisuuden ja/tai vertailun olemassaoloa. Tällä algoritmilla on kolme erityistä etua [8] :

Muunnosmatriisi esitetään harvoilla matriiseilla , mikä johtaa tilan keskimääräisen monimutkaisuuden vähenemiseen verrattuna muihin menetelmiin.
Harva DTW-algoritmi tuottaa aina optimaalisen muunnospolun.
Koska algoritmi tuottaa optimaalisen kohdistuksen, sitä voidaan helposti käyttää yhdessä muiden menetelmien kanssa.

Sovellukset

Muistiinpanot

↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Uusi lähestymistapa dynaamisen aikavääristyksen nopeuttamiseen Arkistoitu 13. lokakuuta 2019 Wayback Machinessa
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, jakso 1 Arkistoitu 30. heinäkuuta 2016 Wayback Machinessa
↑ Stan Salvador ja Philip Chan Fast DTW: Kohti tarkkaa dynaamista aikavääristystä lineaarisessa ajassa ja avaruudessa Arkistoitu 31. lokakuuta 2014 Wayback Machinessa
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, jakso 2 Arkistoitu 30. heinäkuuta 2016 Wayback Machinessa
↑ Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, jakso 1, sivu 2 Arkistoitu 30.7.2016 . (Englanti)
↑ DTW-algoritmin tarkistus. Osio 3.3 Arkistoitu 17. joulukuuta 2014 Wayback Machinessa
↑ Stan Salvador ja Philip ChanFast DTW: Kohti tarkkaa dynaamista aikavääristymistä lineaarisessa ajassa ja avaruudessa Arkistoitu 31. lokakuuta 2014 Wayback Machinessa
↑ Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: Uusi lähestymistapa nopeuttamiseen, osa 1.1 Arkistoitu 13. lokakuuta 2019 Wayback Machinessa