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 formula_1. Y ja x telgede äärmiste elementide jaoks kasutatakse vastavalt formula_2 ja formula_3. 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: 
Õigesti ja valesti lahendamise näited on näha alloleval pildil.
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_matrix
Esmalt valmistatakse ette massiiv, kuhu hakatakse väärtuseid sisse arvutama. Järgmise for tsükliga hakatakse maatriksisse väärtuseid arvutama. 
Esmalt leitakse valemi formula_1 esimene pool, ehk formula_5. 
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 formula_6 viimase kahe arvutuse summa.
dtw_matrix[i, j] = cost + last_min
Seda 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:
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.