Warping the Time on Data Streams
Paolo Capitani Paolo Ciaccia
DEIS – IEIIT-BO/CNR, University of Bologna, Italy (Ottobre 2005)
GRUPPO 7
Federico Matteoni
Fabio Stefanini
Luca Tumidei
17 - 03 - 2006
Warping the Time on Data Streams
Possibili applicazioni
 Analisi finanziarie
 Sistemi di videosorveglianza
 Ricerche scientifiche
 Sistemi di riconoscimento vocale
17 - 03 - 2006
Warping the Time on Data Streams
Serie temporali
Le serie ora considerate non sono più costituite da un insieme finito n-elementi,
ma da insiemi di dati di notevoli dimensioni e in costante crescita
caso statico
evoluzione nel tempo
operando per
valore
Sliding window
R
S
tempo
istante attuale
17 - 03 - 2006
Warping the Time on Data Streams
Un nuovo Approccio …
Fino ad ora :
 Imprecisa in analisi con distorsioni temporali
 Distanza Euclidea
 Troppo dispendiosa in termini di Complessità Computazionale
 DTW
SDTW
17 - 03 - 2006
Warping the Time on Data Streams
Distanza Euclidea
L2(R1n, S1n)2 = Σi=1n (Ri - Si )2
81
2
72
1
1
R
63
0
59
1
43
3
34
2
1
d
•
Intuitiva
• Facile implementazione
• Calcolo rapido
• Non è adatta per la valutazione di serie temporali con
contrazione ed espansione
• Bassa complessità dell’aggiornamento nel tempo
17 - 03 - 2006
25
9
4
6
6
4
4
3
4
5
S
Warping the Time on Data Streams
Dynamic Time Warping
Il confronto
avviene anche
fra punti
corrispondenti a
istanti temporali
differenti!
Ogni punto di una serie può essere
allineato/confrontato con punti (precedenti o
successivi) di altre serie, corrispondenti a
differenti posizioni temporali,in modo da
compensare possibili sfasamenti temporali
S
R
t
17 - 03 - 2006
Warping the Time on Data Streams
Dynamic Time Warping
Ciascun percorso-W (Warping path) definisce l’allineamento tra le
serie R e S ed il conseguente costo da sopportare!
Matrice distanze
2
1
1
9
0
R
d
1
4
9
2
55 58 67
9
4
9 16
1
74 54 59 71
9
4
9 16
1
65 65 50 55 69
36 16 16 9 16
1
b
Matrice warping path
25 25 9
9
9
1
3
1
2
4 16 16 4
1
9 25 25
4
6
9
6
S
1
R
4
0
39 47 40 41 37
i-1,j-1 i,j-1
3 14 22 31 32 33
2 13 25 41 45
4
3
4
5
WP
Wopt
9 34 59
4
6
6
4
4
3
4
5
S
wpi,j = di,j + min { wpi-1,j , wp (i, j-1) , wp (i-1, j-1) }
La distanza DTW è rappresentata dal minimo costo
tra tutti i Warping Path, il Wopt
17 - 03 - 2006
i,j
75 56 56 46 53
1
1
4
i-1,j
Warping the Time on Data Streams
Dynamic Time Warping
precisione
l’allineamento al tempo t non è garantito al tempo t+1
R
1
2
3
2
1
1
0
1
3
2
1
D
44 45 58
41 42 47
37 41 42 42 43
35 39 49 49 49
43 35 40 52 53
34 34 31 36 52
25 25 27 48
9 18 22
Complessità
dell’aggiornamento
O(n) – O(n2)
n
4 6 6 4 4 3 4 5 2 3 5
1
S
9
1
1
b
d
9
4
9 16
9
4
9 16
25 25 9
9
9
1
3
1
2
4 16 16 4
1
9 25 25
4
b
17 - 03 - 2006
4
9
36 16 16 9 16
0
R
il DTW si può discostare dalla
diagonale della matrice di un numero b
di caselle (Sakoe-Chiba band)
1
2
6
9
6
1
4
4
4
3
4
5
S
Warping the Time on Data Streams
Ma quali sono le caratteristiche che stiamo
cercando?
Qualità dei risultati ottenuti
Velocità di update
Distanza euclidea
Distanza DTW
 Qualità dei risultati
 Qualità dei risultati


Velocità di update
17 - 03 - 2006
Velocità di update
Warping the Time on Data Streams
LB-KeoghSymm
Un possibile approccio…
Serie Q and suo sviluppo Env(Q)
{
Low(Q)
Up(Q)
LBKeogh(Env(Q), S)
LBKeogh(Env(R), S)
LBKeoghSymm(R, S) = max
17 - 03 - 2006
{
LBKeogh(Env(S), R)
LBKeogh(Env(R), S)
LBKeogh(Env(S), R)
Aggiornamento
in O(b)
precisione
Warping the Time on Data Streams
Un metodo per soddisfare entrambe i requisiti di:
precisione
efficienza
Stream dynamic time warping
Calcolo simile
E’ un’evoluzione del DTW
Diverse condizioni
“di confine”
Obj: Determinare il Warping Path ottimale
17 - 03 - 2006
Warping the Time on Data Streams
Concetti base (I)
5
Frontiera F: un insieme di
celle della matrice delle distanze
cumulative tale per cui per ogni
warping path W si ha W ∩ F = ø
Start frontier
5
17 - 03 - 2006
End frontier
5
Warping the Time on Data Streams
Concetti base (II)
2
1
1
Boundary-relaxed DTW: Date due serie di
dati nel tempo, R e S, e i generici istanti ts e
te, si possono calcolare il i DTW rilassati.
Partendo dalla matrice delle distanze…
9
0
R
D
2
4 16 16 4
1
9 25 25
4
6
6
1
35 23 26 34
1
35 23 26 34
1
31 31 22 25 34
1
31 31 22 25 34
R
35 27 27 21 26
0
10 21 18 19 17
1
5 14 15 16
2
1
5 14 15 16
2
1
5 14 15
2
1
5 14 15
1
4
9 16
1
4
9 16
3
4
3
4
3
4
S
DTW L : costo minimo del warping
path che inizia da una cella della
start-frontier
17 - 03 - 2006
9 16
1
4
4
4
3
4
5
10 21 18 19 17
1
2
4
35 27 27 21 26
2
3
9
S
23 24 28
3
9
1
2
5
9 16
9
9
23 24 28
1
4
9
1
2
0
9
25 25 9
3
…si ottengono
R
4
36 16 16 9 16
1
d
1
D
5
3
3
2
3
4
S
DTW L : costo minimo del warping path
che inizia da una cella della start-frontier e
termina in una cella della end-frontier
Warping the Time on Data Streams
Come funziona la distanza SDTW…
SDTW
=
DTWkL – [DTW L – d(Rts,Sts)] + DTW L
α
β
γ
ts
δ
n
α
te
δ
k+i
k
ts
γ
β
17 - 03 - 2006
Wopt SDTW
Warping the Time on Data Streams
Come funziona la distanza SDTW…
1
2
3
2
47 50 59
1
62 46 51 63
1
53 53 42 47 57
0
72 44 44 38 41
1
26 36 28 29 25
3 1 10 19 20 21
2 4 20 36 29
1 9 25 25
α = 47
1
2
3
2
1
1
0
1
26 36 28
3 1 10 19 20
2 4 20 36 29
1 9 25 25
4 6 6 4 4 3 4 5 2 3 5
4 6 6 4 4 3 4 5 2 3 5
1
2
3
2
1
1
0
1
3
2
1
1 4 17
0 1 9
1 0 4
β = 28
1
2
3
2
1
1
0
1
25 25 9
3 1 9 9 1
2 4 20 16 4
1 9 16 25
R
δ = 17
d
γ =9
4 6 6 4 4 3 4 5 2 3 5
S
k+1
k
4 6 6 4 4 3 4 5 2 3 5
17 - 03 - 2006
SDTW = α – (β – γ) + δ = 47
Warping the Time on Data Streams
Caratteristiche (I)
SDTW è un lower bound di DTW
SDTW può essere aggiornata con O(b)
operazioni ad ogni step
α = DTW L che può essere
calcolato con O(2b + 1)
operazioni = O(b)
17 - 03 - 2006
β
O(1)
γ
O(1)
δ
O(1)
Warping the Time on Data Streams
b
Caratteristiche (II)
La distanza SDTW può essere calcolata
usando uno spazio di complessità O(n)
Calcolo O(n) + Aggiornamento O(b) = O(n + b) = O(n)
17 - 03 - 2006
Warping the Time on Data Streams
Risultati Sperimentali e
Applicazioni pratiche di SDTW
17 - 03 - 2006
Warping the Time on Data Streams
Metodo:
Valutazione dello strumento in termini di:
1) Efficienza
2) Qualità
Confronto dei risultati ottenuti sugli stessi datasets da:
1) DTW
2) SDTW
3) LB-KeoghSymm
Prove sperimentali eseguite utilizzando :


Intel Pentium 4 a 1.60GHz con 512 MB di memoria principale
Sistema operativo Windows 2000 OS
17 - 03 - 2006
Warping the Time on Data Streams
Datasets utilizzati
17 - 03 - 2006
Warping the Time on Data Streams
1.
Velocità di processamento (I)
Velocità di processamento o Sampling Rate (Hz): Intervallo di tempo
che intercorre tra la lettura di una “Sliding window” e la successiva
n =128: dimensione della “Sliding window”
17 - 03 - 2006
Warping the Time on Data Streams
1. Velocità di processamento (II)
Miglioramento prestazioni SDTW rispetto a DTW, all’aumentare di n
 Lo “Speed Up” cresce come O(n)
17 - 03 - 2006
Warping the Time on Data Streams
2. Accuratezza (tightness)
100%
SDTW
90%
LBKeogh-symm
Accuracy
80%
70%
60%
50%
40%
30%
20%
10%
0%
Random walk
Burstin
Fluid dynamics
Network
EEG
Dataset
 L’accuratezza è misurata come rapporto SDTW / DTW e LB-Keoghsymm/ DTW
su 496 coppie di serie temporali
 Accuratezza di SDTW si pone sempre sopra al 90%
 L’accuratezza di LB-Keoghsymm non supera mai il 61% e raggiunge l’8% nel
caso del dataset Burstin
17 - 03 - 2006
Warping the Time on Data Streams
3. Numero di falsi allarmi
Obiettivo: determinare quando la DTW scende sotto un valore soglia Є
 Si utilizzano SDTW e LB-Keoghsymm che sono Lower Bound di DTW
 Per SDTW i falsi allarmi sono in media lo 0.85% e non sono mai più dell’1,5%
 Per LB-Keogh
17 - 03 - 2006
symm
la media raggiunge il 41,13% con un picco del 99%
Warping the Time on Data Streams
Conclusioni
 SDTW, un nuovo metodo per confrontare flussi di dati
capace di elevata Accuratezza e Velocità di
Processamento :
• SDTW permette un efficiente update sulla “sliding
window” analizzata con un costo pari a O(b).
• Il miglioramento in termini di efficienza di SDTW rispetto a
DTW cresce all’aumentare della dimensione della sliding
window.
• Grazie alla sua ridotta complessità computazionale e al
ridotto numero di falsi allarmi SDTW può essere utilizzato
con funzione di filtro.
17 - 03 - 2006
Warping the Time on Data Streams