Dünaamiline ajadeformatsioon

Dünaamiline ajadeformatsioon (inglise keeles dynamic time warping) on aegridade analüüsi algoritm, mida kasutatakse kahe aegrea sarnasuste leidmiseks. See algoritm on loodud analüüsimaks aegridu, mis on omavahel faasist väljas. Näiteks kasutatakse dünaamilist ajadeformatsiooni kõneanalüüsis. Kui soovime tuvastada sõna "kana", kuid kõneleja ütleb seda sõna kui "kaanaaaa", on aegread erineva pikkusega. See tähendab, et kahte aegrida ei saa otse võrrelda. Just selliste juhtude jaoks kasutataksegi dünaamilist ajadeformatsiooni. See analüüsimisalgoritm suudab tuvastada sarnasusi isegi kui aegread on erineva pikkusega, leides millised elemendid esimesest aegreast on kõige sarnasemad elementidega teisest aegreast. Teisteks kasutusaladeks on veel näiteks kõnelejatuvastus, allkirjatuvastus ja aktsiaturu analüüs. 

 Loogika 
Kahest aegreast luuakse maatriks, kus ühe väärtused pannakse y-teljele ja teise väärtused pannakse x-teljele. Järgmisena arvutatakse maatriksisse väärtused kasutades valemit . Y ja x telgede äärmiste elementide jaoks kasutatakse vastavalt  ja . Kui maatriksis on igale kohale väärtus leitud, tuleb leida lühim tee läbi maatriksi. Selle jaoks on 3 reeglit, mida tuleb jälgida: 

 tee algab alati maatriksi ülevalt paremast nurgast ja lõppeb all vasakul nurgas
 lubatud on liikuda ainult alla, vasakule või alla-vasakule
 liikuma peab alati kõige väiksema elemendi poole. Näiteks kui saab liikuda 3, 5 või 2 poole, tuleb liikuda 2 poole.

Õigesti ja valesti lahendamise näited on näha alloleval pildil.pisi|alt=|keskel|Näide õigest teekonna leidmisest(a) ja näited valesti teekonna leidmisest(n, c, d).

Leitud tee läbi maatriksi näitab meile, millised elemendid signaalist x on kõige sarnasemad elementidega signaalist y. Samuti saame lühima tee elementidega hinnata signaalide erinevust. Seda saab teha liites kokku kõik leitud teekonna väärtused. See näitab meile kui erinevad on signaalid peale nihutamist. Mida väiksem on summa, seda sarnasemad on signaalid.  

 Realiseerimine 
Dünaamilise ajadeformatsiooni algoritmi Python3 näitekood. See kood võtab sisendiks kaks jada ja tagastab arvutatud dünaamilise ajadeformatsiooni maatriksi.  def dtw(s, t):
    n, m = len(s), len(t)
    dtw_matrix = np.zeros((n+1, m+1))
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0

    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrixEsmalt valmistatakse ette massiiv, kuhu hakatakse väärtuseid sisse arvutama. Järgmise for tsükliga hakatakse maatriksisse väärtuseid arvutama.  

Esmalt leitakse valemi  esimene pool, ehk . cost = abs(s[i-1] - t[j-1])Järgmisena leitakse ümber olevatest väärtustest väikseim valemi teise poole järgi.last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])Lõpuks liidetakse maatriksis kohale  viimase kahe arvutuse summa.dtw_matrix[i, j] = cost + last_minSeda protsessi korratakse iga elemendi peal maatriksis. 

 Kiiremad algoritmid 
Kuna suurte andmemassiivide vaheliste sarnasuste otsimine dünaamilise ajadeformatsiooniga on aeganõudev, on välja töötatud erinevaid meetodeid algoritmi kiirendamiseks. 

 FastDTW 
FastDTW põhimõte seisneb dünaamilise ajadeformatsiooni võimalikult väikesteks alamdeformatsioonideks tegemises. Alustatakse väikseima võimaliku resolutsiooniga, ehitades üles originaalse resolutsioonini.

FastDTW algoritm töötab kolmes etapis:

 aegrida muudetakse võimalikult väikeseks, proovides samas hoida graafiku kõveraid võimalikult sarnasena originaaliga
 leitakse väiksema resolutsiooniga maatriksist lühim teekond ja kasutatakse seda veidi suurema resolutsiooniga maatriksis teekonna leidmiseks, ehitades üles originaalse resolutsioonini (maatriksi resolutsioonid kasvavad kahe korrutisena)
 leitud teekonnas tehakse väikeseid parandusi nii, et see sobiks optimaalselt originaalsesse maatriksisse.

 PrunedDTW 
PrunedDTW põhimõte seisneb maatriksi elementide, mis kindlalt ei saa lühima teekonna osaks, mitte arvutamisel. Nii jäetakse ära paljud muidu kasutud arvutused.

 Piiride seadmine 
Üheks populaarseks dünaamilise ajadeformatsiooni kiirendamise viisiks on seada mööda maatriksi diagonaali kindlad piirid. Need piirid määravad ära, mis piirkonnas lühimat teed otsitakse. See töötab kuna tihti läheb lühim tee mööda diagonaali või selle lähedalt. Selle meetodi jaoks peavad olema mõlemad andmemassiivid ühe pikkusega. Populaarsemateks piirikujudeks on Sakoe-Chiba ja Itakura. 

 Viited 

Kategooria:Algoritmid