<jupyter_start><jupyter_text>Dynamic Time Warping![DTW](https://databricks.com/wp-content/uploads/2019/04/Euclidean_vs_DTW.jpg)[Image Credits](https://databricks.com/blog/2019/04/30/understanding-dynamic-time-warping.html) Definizione**Dynamic Time Warping** (DTW) è un algoritmo utilizzato per misurare la similarità tra due o più serie temporali, andando a leggere su [Wikipedia](https://en.wikipedia.org/wiki/Dynamic_time_warping) troviamo la seguente definizione:> *"Il Dynamic time warping, o DTW, è un algoritmo che permette l'allineamento tra due 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."*Che casi d'uso ci suggerisce la definizione? Prendiamo ad esempio il riconoscimento vocale, una persona potrebbe parlare più velocemente o più lentamente della voce campione preregistrata, il DTW non risente di questo problema a differenza di una distanza che venga applicata "punto per punto".Il DTW è molto utilizzato in ambito *IoT* dove gli stream di dati proveninenti da video, audio, sensori, possono essere trasformati in una sequenza lineare per essere analizzati con questa tecnica, in particolare è molto efficace con serie ad alta frequenza di campionamento, pensiamo ad esempio al mercato delle utilities o dell'automotive.L'idea di base è calcolare la distanza tra due vettori/serie storiche **indipendentemente dalla loro lunghezza** e per farlo bisogna che i vettori rispettino le seguenti regole:* ogni indice della prima sequenza deve poter essere confrontato con tutti gli indici delle altre e viceversa* il primo indice della prima sequenza deve essere associato al primo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza)* l'ultimo indice della prima sequenza deve corrispondere all'ultimo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza) Algoritmo> Per illustrare il DTW userò in parte un breve esempio con due sequenze di pochi elementi preso da [riptutorial](https://riptutorial.com/it/algorithm/example/24981/introduzione-al-dynamic-time-warping).L'algoritmo di base è molto semplice, vedremo la differenza della similarità tra serie con DTW e distanza euclidea, partiamo creando gli array.<jupyter_code>import numpy as np
serie_1 = np.array([1, 2, 3, 5, 5, 5, 6], ndmin = 2)
serie_2 = np.array([1, 1, 2, 2, 3, 5], ndmin =2)
serie_2New = serie_2.copy()
serie_2New = np.append(serie_2New, 0)<jupyter_output><empty_output><jupyter_text>Le due serie hanno lunghezza diversa quindi un confronto punto per punto con distanza euclidea (o altra distanza) non sarebbe del tutto corretto. Supponiamo che le due serie partano nello stesso periodo e che la serie_2 finisca prima, quindi aggiungiamo un elemento per calcolare la distanza (*non rispetta le regole sugli indici del DTW*).$$  d\left( p,q\right)   = \sqrt {\sum _{i=1}^{n}  \left( q_{i}-p_{i}\right)^2 } $$La distanza calcolata è 7.14.<jupyter_code>distance = np.sqrt(np.sum((serie_1-serie_2New)**2))
distance<jupyter_output><empty_output><jupyter_text>Passiamo ora al calcolo della distanza mediante DTW, per farlo ci servirà una matrice di dimensione *n x m* dove *m* ed *n* sono la lunghezza della serie più 1.<jupyter_code>n = serie_1.shape[1]+ 1
m = serie_2.shape[1]+ 1
DTW = np.zeros([n,m])<jupyter_output><empty_output><jupyter_text>Il primo elemento della matrice *DTW[0,0]* deve essere pari a 0, mentre prima riga e prima colonna pari ad infinito. Quanto fatto serve per il ***cold start*** dell'algoritmo. Il cold start è il confronto con i periodi precedenti quando si è al primo passo dell'algoritmo, impostando una riga fittizia ad infinito non si incorre in situazioni anomale e si evita di implementare condizioni sullo start che appesantirebbero ulteriormente il calcolo.> ecco spiegato perchè la dimensione della serie più 1.<jupyter_code>DTW[0,1:] = np.inf
DTW[1:,0] = np.inf
print(DTW)<jupyter_output><empty_output><jupyter_text>Per ogni posizione della matrice verrà calcolata la distanza euclidea di ogni punto di una serie da tutti i punti delle altre partendo dalla posizione *DTW[1,1]*. Ad ogni distanza viene aggiunto il minimo tra:* il valore precedente sulle righe: **cancellazione*** il valore precedente sulle colonne: **inserimento*** il valore precedente in diagonale: **corrispondenza**<jupyter_code>for i in range(1,n):
    for j in range(1, m):
        dist = abs(serie_1[:,i-1] - serie_2[:,j-1]) 
        DTW[i,j] = dist + min([DTW[i-1,j], DTW[i,j-1], DTW[i-1,j-1]])

print(DTW)<jupyter_output><empty_output><jupyter_text>L'algoritmo restituisce una matrice con tutte le posizioni valorizzate.Arrivati a questo punto partendo da *DTW[0,0]* bisogna costruire un percorso che tocchi il valore minimo più vicino a quello nella posizione in cui ci troviamo muovendoci da sinistra verso destra in orizzontale/verticale/obliquo, questo è il **Warping Path**.* uno spostamento orizzontale significa che *serie_2* è accelerata durante questo intervallo.* uno spostamento verticale significa che *serie_2* è decelerata durante questo intervallo.* una mossa diagonale significa che durante questo periodo le serie camminano di pari passo**Il valore finale del path è la distanza tra le serie.**Dalla matrice si nota che il calcolo non è stato influenzato dalla diversa dimensione delle sequenze e che il valore finale è molto più piccolo di quello calcolato punto per punto con la distanza euclidea.![matrice2](https://i.imgur.com/OqkHF5t.png)  Window ConstraintLa complessità di calcolo del DTW è ***O(m * n)*** dove *m* e *n* rappresentano la lunghezza di ciascuna sequenza quindi se avessimo sequenze molto lunghe il confronto tra le due risulterebbe complesso, ed anche inutile, perchè alcuni confronti verrebbero effettuati su posizioni lontanissime.Prendiamo l'esempio della serie storica, vorrebbe dire confrontare periodi molto distanti temporalmente che non hanno nessuna relazione ed influenza tra loro.Per questo motivo viene inserita un parametro *w*, una **finestra temporale** su cui calcolare le differenze.La finestra temporale è il valore minimo tra un intero definito dall'utente (io ho utilizzato 1) e la differenza in valore assoluto tra *m* ed *n*.<jupyter_code>w = max([1, abs(n-m)])
w<jupyter_output><empty_output><jupyter_text>Di seguito come cambia l'algoritmo per il calcolo della distanza.<jupyter_code>for i in range(1,n):
    for j in range(max([1,i-w]), min([m, i+w])):
        dist = abs(serie_1[:,i-1] - serie_2[:,j-1]) 
        DTW[i,j] = dist + min([DTW[i-1,j], DTW[i,j-1], DTW[i-1,j-1]])

print(DTW)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08055269733940909, 'fraction_numerical': 0.013964427458474203, 'mean_word_length': 5.573913043478261, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 32, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '319936', 'license': 'MIT', 'n_tokens_mistral': 2326, 'n_tokens_neox': 2332, 'n_words': 852, 'path': 'appunti-time-series/006_DTW.ipynb', 'repo_name': 'nickprock/appunti_data_science', 'size': '6803'}