Exact Indexing of Dynamic
Time Warping
Eamonn Keogh
Computer Science & Engineering Department
University of California - Riverside
Riverside,CA 92521
[email protected]
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Argomenti trattati
• A cosa serve il confronto delle Serie
Temporali?
• Dynamic Time Warping
• Confronto tra Distanze
• Lower Bound del Dynamic Time Warping
• Indicizzazione del Dynamic Time Warping
• Valutazioni Sperimentali
• Conclusioni
• Applicazioni
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
A cosa serve il confronto delle
Serie Temporali?
Clustering
Classificazione
Regole Associative
Query
10

s = 0.5
c = 0.3
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
MATCH
G. Fregnan, T. Splendiani
Confronto  Misura:
Euclidea VS Dynamic Time Warping
Le Sequenze sono allineate “uno-a-uno”
Asse Temporale Fisso
Limiti della distanza Euclidea:
Non permette allineamenti per serie fuori fase
Il tasso medio di errore per clustering e
classificazione è più elevato
(un ordine di grandezza nelle valutazioni
empiriche presenti nell’articolo)
Dynamic Time Warping
Sono possibili allineamenti non-lineari
(uno-molti e molti-uno).
17/03/06
Asse Temporale “Warped”
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Calcolo della DTW (1)
wp(i,j) = d(qi,cj) + min{wp(i-1,j-1) , wp(i-1,j ) , wp(i,j-1) }
Si costruisce una matrice per
Allineare le due serie cercando
il percorso ottimale che soddisfi
i vincoli di:
•Inizio-Fine
•Continuità
•Monotonicità
i,j-1
i-1,j-1
C
Q
i,j
i-1,j
Percorso di Warping w
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Calcolo della DTW (2)
E’ possibile determinare un numero esponenziale di warping paths
che soddisfino i vincoli suddetti.
E’ interessante solo il path che minimizza i warping cost:
DTW (Q, C )  min   w
K
k 1
k
Percorso
di Warp w
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Alcune applicazioni
Foglie
Profili
4
3
2
1
0
Motion
Capture
-1
-2
-3
-4
0
10
20
30
40
50
60
70
80
Linguaggio dei Segni
0 10 20 30 40 50 60 70 80 90
4
3
2
Controllo
Tracciati
1
0
-1
-2
-3
0
50
100
150
200
250
300
2-Pattern
Rilevamento Parole
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Le Prestazioni
Valutazioni con query 1NN
Errore Normalizzato
Tasso di Errore
Euclidea
DTW
Euclidea
1.
DTW
Abbiamo una lista di N oggetti, con una etichetta di
classe.
Estraiamo il primo, e fingiamo di non conoscere la sua
etichetta di classe
Ricerchiamo il suo NN, nella lista degli N-1 oggetti
restanti.
Se il NN è nella stessa classe, lo abbiamo selezionato
correttamente, se non lo è la ricerca da esito errato
Ripetiamo la ricerca per ogni item nella lista di N
oggetti, il numero medio di NN selezionati
correttamente è la nostra precisione "leaving one out."
100%
35
3075%
25
2050%
15
1025%
5
00%
2.
3.
4.
5.
Parole
Parole
Segni
Segni
MC
MC
Tracciati
Tracciati
Foglie
Foglie
Prof ili
Profili
Controllo
2-
Pattern
Controllo 2-Pattern
Tempo di esecusione
Euclidea
La DTW è migliore della distanza
Euclidea ma ha complessità:
È quindi necessario migliorare le
prestazioni del calcolo della DTW
1000000
100000
10000
msec [log]
O(nm)≈O(n2) :(
DTW
1000
100
10
1
Parole
17/03/06
Segni
“Exact Indexing of Dynamic Time Warping” di E.Keogh
MC
Tracciat i
Foglie
Prof ili
Cont rollo
2-Pat t ern
G. Fregnan, T. Splendiani
Migliorare le prestazioni (0):
Indici
Gli indici per gestire oggetti in uno spazio metrico devono
rispettare i seguenti assiomi:
d(x,y) ≥ 0, d(x,y) = 0  x=y (positività)
d(x,y) = d(y,x) (simmetria)
d(x,y) ≤ d(x,z) + d(z,y) (disuguaglianza triangolare)
La DTW non rispetta la disuguaglianza triangolare
Impossibile usare indici metrici!!
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Migliorare le prestazioni (1): Vincoli Globali
I vincoli globali limitano gli indici del percorso di warping
wk = (i,j)k tale che j-r  i  j+r
C
Q
C
Parziale riduzione del tempo di calcolo
Q
Prevengono warping “patologici”
r=cost
Fascia di Sakoe-Chiba
17/03/06
r=f(i)
r=
Parallelogramma di Itakura
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Migliorare le prestazioni (2):
Lower Bounding
Scan_Sequenziale_Lower_Bounding(Q)
1. migliore_temporaneo= infinito;
Scandisce tutte sequenze e
calcola una misura di LB
2. for tutte le sequenze nel database
3. dist_LB = misura_lower_bound(Ci,Q);
Se dist_LB è una “buon” LB,
4.
if (dist_LB < migliore_temporaneo)
calcola la DTW della sequenza
5.
vera_dist = DTW(Ci,Q);
Se la DTW è la “migliore”,
individua il miglior match
6.
if (vera_dist < migliore_temporaneo)
7.
migliore_temporaneo = vera_dist;
8.
indice_confronto_migliore = i;
9.
endif
10.
endif
11. endfor
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Misure di Lower Bound:
Kim et al.
C
C
A
D
Q
B
Estrae una tupla di 4 valori {A,B,C,D} calcolati nei punti notevoli
Il lower bound è il massimo delle differenze tra il primo, l’ultimo,
il massimo e il minimo valore delle due serie
LB_Kim=max {A,B,C,D}
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Misure di Lower Bound:
Yi et al.
max(Q)
C
Q
min(Q)
La somma delle linee verticali rappresenta il contributo minimo
per punti corrispondenti al calcolo della DTW
Tutti i punti di Ci>max(Q) e Ci<min(Q) contribuiscono al LB_Yi
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Un nuovo Lower Bound:
LB_Keogh
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Definizioni preliminari : Ui,Li
Q
C
U
Sakoe-Chiba Band
Ui = max(qi-r : qi+r)
Li = min(qi-r : qi+r)
L
Q
Q
C
U
Q
L
Itakura Parallelogram
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Definizione del LB_Keogh
Cj
Il LB_Keogh(Q,C) è ottenuto
in due modi a seconda
che si utilizzi la banda con r
costante o il parallelogramma
con r funzione di i
U
(c  U ) se c U Q

LB_Keogh(Q,C )    (c  L ) se c  L
 0 altrimenti

2
i
i
n
j
i 1
i
L
i
2
i
i
i
i
Cj
U
Si può dimostrare che:
LB_Keogh(Q,C) ≤ DTW(Q,C)
LB_Keogh è definito solamente per |Q|=|C|
17/03/06
Q
“Exact Indexing of Dynamic Time Warping” di E.Keogh
L
G. Fregnan, T. Splendiani
Approssimazione di U ed L
Approssimiamo U ed L con
una versione alternativa
della Piecewise Aggregate
Approximation (PAA), per
ridurne la dimensione, e li
indichiamo con Û e L̂

Uˆ i  max U n i11 ,..., U n i 

N
N
Lˆi  min L n i11 ,..., L n i 
17/03/06
N
N

U
Q

L
Û
passo 
n
N
L̂
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Calcolo del LB approssimato
per i candidati
A questo punto è possibile indicizzare i
“picewise” di una serie candidata con un
generico indice metrico
Ci  Nn
(c  Uˆ ) se c  Uˆ
n
LB_PAA(Q,C )    (c  Lˆ ) se c  Lˆ
N
 0 altrimenti
n
N
j
i
c
n
N
j
( i 1) 1
C
2
i
i
N
j
i 1
i
i
i
i
i
i
Si può dimostrare che:
LB_PAA(Q,C ) ≤ LB_Keogh(Q,C)
17/03/06
C
2
“Exact Indexing of Dynamic Time Warping” di E.Keogh
0
20
40
60
80
100
120
140
c1
c2
c3
c4
c5
c6
c7
c8
G. Fregnan, T. Splendiani
Indicizzazione (1)
Applichiamo la PAA ad ogni serie da indicizzare
hi
h1
Sia R il più piccolo rettangolo che
contiene spazialmente ogni punto di C.
h2
li
l1
l2
17/03/06
Indichiamo con U il generico nodo foglia
del nostro albero.
Ad ogni nodo foglia U è associato il
minimun bounding rectangle R = (L, H).
R è il MBR in cui L = {l1, l2, …, lN} e H =
{h1, h2, …, hN} sono gli estremi inferiore
e superiore della diagonale di R.
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Indicizzazione (2)
L’ultimo passo per l’indicizzazione è la definizione di una distanza che
restituisca un lower bound della misura tra la query Q ed R
Definiamo la funzione MINDIST che restituisce la distanza tra la query Q
ed R (MBR definito precedentemente).
In questo modo possiamo “navigare” l’abero calcolando le MINDIST dei
nodi, fino ad attivare alle foglie in cui risiedono le serie approssimate C
 (l  Uˆ ) se l  Uˆ
MINDIST(Q, R)  n ( h  Lˆ ) se h  Lˆ

N
 0 altrimenti
2
i
i
N
i 1
17/03/06
i
i
2
i
i
i
i
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Cosa abbiamo visto
• Come si determina un lower bound per
la DTW
• Come si indicizzano le serie temporali
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Query che utilizzano
le strutture proposte
K-NNSearch (Q,K)
Algorithm KNNSearch(Q,K)
RangeSearch(Q, ε, T)
Algorithm RangeSearch(Q,
ε, T)
if T is a non-leaf node
1.
2. for each child U of T
3. if MINDIST(Q,R) ε RangeSearch(Q, ε, U);
4. else
// R is MBR of U
// T is a leaf node
5. for each PAA point C in T
6. if LB_PAA(Q, C) ε
Retrieve full sequence C from database;
7.
8. if DTW(Q,C)  ε Add C to result;
L’indice così definito può
essere utilizzato in una
classica struttura R-Tree
17/03/06
Variable queue: MinPriorityQueue;
Variable list: temp;
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
queue.push(root_node_of_index, 0);
while not queue.IsEmpty() do
top = queue.Top();
for each time series C in temp
such that DTW(Q,C)  top.dist
Remove C from temp;
Add C to result;
if |result| = K return result ;
queue.Pop();
if top is an PAA point C
Retrieve full sequence C from database;
temp.insert(C, DTW(Q,C));
else if top is a leaf node
for each data item C in top
queue.push(C, LB_PAA(Q, C));
else
// top is a non-leaf node
for each child node U in top
queue.push(U, MINDIST(Q,R)) // R is
MBR associated with U.
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Valutazioni Empiriche
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Prestazioni di pruning (1)
P
Numero di oggettiche non richiedonoil calcolo della DTW
Numero di oggettinel database
0≤P≤1
Calcolo di P per ogni dataset (di 32):
1. Estrazione di 50 serie di lunghezza 256
2. Selezione di una query tra le 50 serie
3. Ricerca del “best match” tra le 49 restanti usando l’algoritmo di scan sequenziale
(in realtà non esegue lo scan sequenziale delle serie ma ne fa prima un sorting)
G. Fregnan, T. Splendiani
“Exact Indexing of Dynamic Time Warping” di E.Keogh
17/03/06
Dimensione del Database
Prestazioni di Pruning P
Prestazioni di Pruning P
Prestazioni di pruning (2)
Lunghezza della Query
LB_Keogh
LB_Yi
LB_Kim
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Prestazioni temporali di scan (1)
Sistema:
processore AMD Athlon
1.4 GHZ, con 512 MB di memoria
fisica e 57.2 GB di memoria
L’indice usato
risiede in un R-Tree
secondaria.
Costo di CPU
=
Normalizzato
Algoritmi: Sono stati
comparate le tecniche di scan
lineari proposte.
LB_Yi non ha un metodo di
indicizzazione.
LB_Kim non supera mai lo
scan lineare
Temp o med io d i esecu zio n ed ella q u eryu san d ol'in d ice
Temp o med io d i esecu zio n ed ella q u eryco n scan seq u en zial
e
Datasets:
Mixed Bag: Tutti i 32 datasets raccolti insieme. 763,270 oggetti
Random Walk: Il più comune dataset di test in letteratura. 1,048,576 oggetti
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Costo di CPU Normalizzato
Prestazioni temporali di scan (2)
1
Random Walk
0.8
Mixed Bag
LScan
LB_Keogh
0.6
LScan
LB_Keogh
0.4
0.2
0
210
212
214
216
218
220
210
212
214
216
218
220
Numero di Oggetti nel Database
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Conclusioni
Il DTW è una misura di distanza migliore
della distanza Euclidea.
Abbiamo illustrato un Lower Bound efficiente
ed efficace per il DTW.
Abbiamo mostrato come indicizzare la
tecnica di LB.
La completa valutazione empirica ha
dimostrato la validità dell’approccio.
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Implementazioni di Successo
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
CASO I
La tecninca di lower
bounding è stata usata
per supportare
l’indicizzazione di
enormi archivi di testi
manoscritti.
Sorprendentemente il DTW
ha prestazioni migliori di
modelli più complessi.
R. Manmatha, T. M. Rath: Indexing of Handwritten Historical Documents - Recent Progress.
In: Proc. of
the 2003 Symposium on Document Image Understanding Technology (SDIUT), Greenbelt, MD, April 9-11, 2003, pp. 77-85.
T. M. Rath and R. Manmatha (2002): Lower-Bounding of Dynamic Time Warping Distances for
Multivariate Time Series. Technical Report MM-40, Center for Intelligent Information Retrieval, University of Massachusetts Amherst.
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
CASO II
La tecnica di
lower bounding
è stata
utilizzata dalla
ChevronTexaco
per confrontare
dati sismici.
Grazie a Steve Zoraster
per l’immagine
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Grease is
the word…
CASO III
La tecnica di lower
bounding è stata
usata per supportare
le “query by
humming”, da
numerosi gruppi di
ricerca.
I migliori 3 riscontri
• Bee Gees: Grease
• Robbie Williams: Grease
• Sarah Black: Heatwave
Ning Hu, Roger B. Dannenberg (2003). Polyphonic Audio Matching and Alignment for Music Retrieval
Yunyue Zhu, Dennis Shasha (2003). Query by Humming: a Time Series Database Approach, SIGMOD
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
CASO IV
La tecnica di
lower
bounding è
stata utilizzata
per indicizzare
i clip ottenuti
dal motion
capture.
Grazie a Marc
Cardle per questo
esempio
Marc Cardle :“Automate Motion Editing” (2004) University of Cambridge, Computer Laboratory, Technical Report
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani
Un ringraziamento speciale a
Eamonn Keogh per il
supporto ed il materiale che
ci ha fornito.
17/03/06
“Exact Indexing of Dynamic Time Warping” di E.Keogh
G. Fregnan, T. Splendiani