Corso di Sistemi Informativi per le Decisioni L-S
Anno accademico 2006-2007
Prof. M. Patella
Time Series Discords
Algoritmi e Applicazioni
De Benedetto Benedetta
Giombetti Nicola
Time series
sequenze di rilevazioni effettuate nel tempo
Esempio di serie temporale: Elettrocardiogramma
In letteratura l’analisi delle serie temporali è mirata alla ricerca
della similarità tra sequenze di valori allo scopo di:
• Predire ed estrapolare valori futuri
• Ricercare occorrenze di pattern conosciuti
• Individuare nuovi pattern
•…
Finding Time series discords
Ricerca di sottosequenze che si discostano
maggiormente da tutte le altre
Applicazioni per DM:
 Clustering improving quality
 Data cleaning
 Anomaly Detection
Alcune definizioni

Time Series: una time series T = t1,…,tm è un set ordinato
di m variabili a valori reali

Subsequence: una subsequence C di T è un campione di
elementi contigui appartenenti a T di lunghezza n ≤ m:
C = tp,…,tp+n-1 con 1 ≤ p ≤ m – n + 1

Sliding Window: finestra di dimensione n che individua
tutte le possibili subsequence scorrendo su T

Dist(C,M): funzione distanza tra due subsequence C ed
M che supponiamo simmetrica
Discords e Trivial Matches
La ricerca di Time series discord implica:
 Il confronto di ogni subsequence con la sua subsequence più
simile
 l’identificazione della coppia di subsequence più differente
abcabcabcabcXXXabcabcabacab
Problema:
Tipicamente i valori minori di Dist si rilevano tra subsequence
slittate tra loro di pochi punti (Trivial Matches)
XXX è “vicino” a XXa!!
Esempio
Utilizziamo la distanza di Hamming
abcabcabcabcXXXabcabcabacab
Min(3 0 3 3 . . . . . . ) = 0
a b c a b0c a b c a b c X X X a b c a b c a b a c ab
Ripetendo il procedimento per tutte le subsequence otteniamo…
a0b0c0a0b0c0a0b0c0a0b1c1X1X1X1a0b0c0a0b0c0a1b2a1c0ab
COME ELIMINARE I TRIVIAL MATCHES?!
Esempio(2)
Non-Self Match: data una serie T, contenete due subsequence
C ed M di lunghezza n, che iniziano rispettivamente alle
posizione p e q, M è un Non-Self Match di C alla distanza
Dist(M,C) se |p-q|>=n
a0b0c0a0b0c0a0b0c0a0b1c1X1X1X1a0b0c0a0b0c0a1b2a1c0ab
Non_Self Match:
Applicazione del Non_Self Match:
a0b0c0a0b0c0a0b0c0a0b1c2X3X2X1a0b0c0a0b0c0a1b2a1c0abc
I confronti fuorvianti (trivial matches) sono così eliminati!!
Definizione formale:
Time Series Discord
Data una time series T, si definisce Discord di T la subcequence D
che ha la distanza maggiore con il suo non-self match più vicino.
Ovvero:
Data ogni subsequence C di T,
ogni non-self match MD di D
ogni non-self match MC di C
Vale:
min(Dist(D, MD)) > min(Dist(C, MC))
Indicheremo con
 D.l: posizione del Discord
 D.dist: distanza rispetto al non-self match più vicino
 Dn: lunghezza del Discord
Discords e densità
Immaginiamo di proiettare tutte le subsequence di
lunghezza 50 in uno spazio vettoriale 50-dimensionale
e di misurare la densità di ciascuna
Le discords non si trovano in regioni a bassa densità!!!
Al contrario la non-self distance riesce ad identificarle chiaramente
Brute Force algorthm
Function [dist,loc] = Brute_Force(T.n)
best_so_far_dist = 0
best_so_far_loc = NaN
For p=1 to |T|-n+1
//Begin Outer loop
nearest_neighbor_dist = infinity
For q=1 to |T|-n+1
//Begin Inner loop
IF |p-q| ≥ n
//Non self match
IF Dist(tp,...,tp+n-1.tq,...,tq+n-1) < nearest_neighbor_dist
nearest_neighbor_dist = Dist(tp,...,tp+n-1.tq,...,tq+n-1)
End
End
//End of non self match
End
//End of Inner loop
IF nearest_neighbor_dist > best_so_far_dist
best_so_far_dist = nearest_neighbor_dist
best_so_far_loc = p
End
End
//End of Outer loop
Return[best_so_far_dist, best_so_far_loc]
Caratteristiche del Brute Force



Richiede un unico parametro (n)
L’algoritmo non è combinabile
Complessità O(m2)
INSOSTENIBILE!
Come migliorare l’algoritmo??
Osservazione1: nell’inner loop non è necessario trovare il miglior
match, non appena troviamo un segmento tale che
Dist<best_so_far_dist possiamo abbandonare l’istanza
Osservazione2: l’utilità della precedente ottimizzazione dipende
dall’ordine di valutazione dei segmenti nell’outerloop
Heuristic algorithm
Function [dist,loc] = Heuristic_Search(T.n,Outer,Inner)
best_so_far_dist = 0
best_so_far_loc = NaN
For Each p in T ordered by heuristic Outer
//Begin Outer loop
nearest_neighbor_dist = infinity
For Each q in T ordered by heuristic Inner
//Begin Inner loop
IF |p-q| ≥ n
//Non self match
IF Dist(tp,...,tp+n-1.tq,...,tq+n-1) < best_so_far_dist
Break
End
IF Dist(tp,...,tp+n-1.tq,...,tq+n-1) < nearest_neighbor_dist
nearest_neighbor_dist = Dist(tp,...,tp+n-1.tq,...,tq+n-1)
End
End
//End of non self match
End
//End of Inner loop
IF nearest_neighbor_dist > best_so_far_dist
best_so_far_dist = nearest_neighbor_dist
best_so_far_loc = p
End
End
//End of Outer loop
Return[best_so_far_dist, best_so_far_loc]
Strategie di ordinamento
Random
Magic
Perverse
O(m)÷O(m2)
ordinamento richiede
O(m) Tale
almeno O(mlogm)!!
O(m2)
Come approssimare l’ordinamento “Magic”??
Osservazione3: nell’outer loop è sufficiente trovare un valore di distanza
abbastanza grande nelle prime iterazioni
Osservazione4: nell’inner loop è sufficiente trovare un valore di distanza
minore del valore corrente di best_so_far_dist nelle prime iterazioni
SAX (Symbolic Aggregate approXimation)
Rappresenta una time series C di lunghezza n in uno
spazio vettoriale w-dimensionale ottenendo un
vettore C  c1 ,...., c w
w
ci 
n
n
i
w
c
j
n
j  ( i 1) 1
w
 A ciascuna partizione α è associato un simbolo
 Ogni subsequence sarà rappresentata da una parola di w
simboli equiprobabili
Approssimare “Magic” tramite SAX
Outer loop:
 Individuare subsequence
meno frequenti
Vettore delle occorrenze
delle parole individuate
Inner loop:
 Trovare subsequence simili a
quella considerata nel punto
precedente
Albero per la mappatura
Scelte le prime subsequence le altre
possono essere ordinate casualmente
Quanti bit per simbolo? Solo
log 2  
Strutture significativamente piccole rispetto alla serie temporale di partenza
Perfezionamento dell’algoritmo

Per simmetricità della funzione distanza:
individuato nell’inner loop un item Cj sufficientemente vicino al
candidato dell’outer loop possono essere scartati entrambi

Scelta dei parametri α e w :


α ottimale: 3 o 4 (empiricamente)
w ottimale: dipende dai dati
 Per dataset con valori relativamente piatti  w ridotto
 Per dataset con maggiore complessità  w elevato
Si osservi che
La velocità dell’algoritmo dipende solo marginalmente da w
variando w dal 60% al 150% otteniamo un decremento della
velocità del 12%
Applicazioni (1)
Trovare anomalie nella Telemetria Spaziale
Rilevazione di enormi quantità di dati mediante sensoristica
Problemi più o meno evidenti ad occhio nudo sono facilmente individuati
dall’algoritmo con velocità decisamente superiore rispetto al precedente
brute force
Applicazioni (2)
Monitoraggio delle fasi del sonno dei pazienti
Problema: non si tratta della classica anomaly detection!!!
Al passare del paziente da uno stato all’altro il segnale si modifica
 individuare i punti di transizione
L’algoritmo di anomaly detection è utilizzabile in quanto vi
saranno forme d’onda ‘inusuali’ al passaggio da uno stato all’altro
Applicazioni (3)
Anomaly detection in ECG
Complessità dell’andamento… semplicità nell’individuare le discord
Grande aiuto per l’analisi di lunghe serie di dati
…specialmente in caso di
riduzioni significative del
passo di campionamento!!!
Utilità dell’ordinamento euristico
Il confronto delle distanze tra subsequence corrente e
best _so_far_dist occupa più del 99% del tempo di
entrambi gli algoritmi
Calcolando il numero di
chiamate di tale operazione
nei 2 algoritmi…
Nota: nell’heuristic search consideriamo trascurabile
il tempo impiegato dall’algoritmo di ordinamento
Guadagno di almeno 3 ordini di grandezza sulla velocità di esecuzione!
Il guadagno aumenta al crescere della dimensione del dataset
Conclusioni
L’algoritmo Heuristic search:
 Richiede un solo parametro d’ingresso: n
 Riduce notevolmente i tempi grazie all’ordinamento
 Richiede un’ulteriore complessità O(m) per
l’ordinamento, tuttavia eseguito una sola volta
 Nella pratica, ha dato risposte concordanti con le
annotazioni dei tecnici
Future direzioni di sviluppo:
 Estensione alla multidimensionalità
 Utilizzo di diverse misure di distanza
Grazie per l’attenzione…