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.

Eukleidiline kauguse ja dünaamilise ajadeformatsiooni erinevust illustreeriv pilt.

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 $D{ij}=|y{i}-x{j}|+\min(D[{i-1},{j-1}],D[{i-1},{j}],D[{i},{j-1}])$. Y ja x telgede äärmiste elementide jaoks kasutatakse vastavalt $D{ij}=|y{i}-x{j}|+D[{i-1},0]$ ja $D{ij}=|y{i}-x{j}|+D[0,{j-1}]$. 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:

1. tee algab alati maatriksi ülevalt paremast nurgast ja lõppeb all vasakul nurgas
2. lubatud on liikuda ainult alla, vasakule või alla-vasakule
3. 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.

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_matrix

Esmalt valmistatakse ette massiiv, kuhu hakatakse väärtuseid sisse arvutama. Järgmise for tsükliga hakatakse maatriksisse väärtuseid arvutama. Esmalt leitakse valemi $D{ij}=|y{i}-x{j}|+\min(D[{i-1},{j-1}],D[{i-1},{j}],D[{i},{j-1}])$ esimene pool, ehk $|y{i}-x{j}|$.

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 $[i,j]$ 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:

1. aegrida muudetakse võimalikult väikeseks, proovides samas hoida graafiku kõveraid võimalikult sarnasena originaaliga
2. 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)
3. 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.