Il Dynamic time warping, o DTW, è un algoritmo che permette l'allineamento tra due o più sequenze, e che può portare ad una misura di distanza tra le due sequenze allineate. Tale algoritmo è particolarmente utile per trattare sequenze in cui singole componenti hanno caratteristiche che variano nel tempo, e per le quali la semplice espansione o compressione lineare delle due sequenze non porta risultati soddisfacenti. È stato utilizzato in diversi campi di applicazione, dal riconoscimento vocale, al riconoscimento di attività motorie.
In generale, DTW è un metodo che permette di trovare una corrispondenza ottima tra due sequenze, attraverso una distorsione non lineare rispetto alla variabile indipendente (tipicamente il tempo). Alcune restrizioni per il calcolo della corrispondenza sono generalmente utilizzate: deve essere garantita la monotonicità nelle corrispondenze, ed il limite massimo di possibili corrispondenze tra elementi contigui della sequenza.
Esempio di implementazione Qui viene riportata una implementazione del calcolo di una misura di distanza basata su DTW, quando le due sequenze sono stringhe di simboli discreti. d(x, y) è la distanza tra i simboli, e.g. d(x, y) = | x - y |. int DTWDistance(int s[1..n], int t[1..m]) { declare int DTW[0..n, 0..m] declare int i, j, cost
for i := 1 to n for j := 1 to m DTW[i, j] := infinity
DTW[0, 0] := 0
for i := 1 to n for j := 1 to m cost:= d(s[i], t[j<nowiki>])</nowiki> DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match
return DTW[n, m] }
Riferimenti Bibliografici Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43– 49, 1978, ISSN 0096-3518
Altri progetti
Categoria:Analisi delle serie storiche Categoria:Algoritmi di ottimizzazione Categoria:Algoritmi per l'apprendimento automatico Categoria:Programmazione dinamica Categoria:Riconoscimento vocale