Capitolo 4 L’algoritmo MNP-CUSUM

Capitolo 4

L’algoritmo MNP-CUSUM

L’algoritmo CUSUM (CUmulative SUM chart) è uno dei metodi per monitorare l’evoluzione temporale delle serie: infatti questa tecnica si prefigge di osservare come cambiano alcune caratteristiche statistiche dei dati in ingresso, timebin dopo timebin.

Solitamente, le serie sono memorizzate in una matrice chiamata “sketch”. A ogni dato in ingresso, attraverso l’uso di funzioni hash, sono associate alcune celle, i cui valori sono aggiornati in base all’ algoritmo di anomaly detection applicato alla chiave.

La funzione dell’algoritmo è identificare l’esistenza di un cambiamento in una delle celle, ed anche in che cella esso è avvenuto. Un’anomalia, infatti, determina un brusco aumento dei valori in alcune celle dello sketch, per cui il valore di questi bucket è significativamente diverso dal comportamento normale. Inoltre, l’algoritmo stabilisce anche un criterio per decidere quando prendere provvedimenti.

L’approccio presenta ottime proprietà in termini di probabilità di falso allarme, di ritardi e di probabilità di falsa localizzazione.

Supponiamo di dover monitorare sequenzialmente, cioè timebin dopo timebin, un flusso di dati y0, y1, y2… yn. Lo scopo

principale dell’algoritmo CUSUM, e più in generale di ogni algoritmo di change detection, è di individuare con il ritardo più piccolo possibile il momento in cui si verifica un cambiamento nella distribuzione dei dati yi.

Esponiamo adesso una possibile implementazione.

Ipotizziamo che inizialmente si conosca la distribuzione dei dati prima e dopo un brusco cambiamento (cioè che l’algoritmo sia parametrico) e siano f_θ

 

y_k

1 e fθ2

 

yk le

funzioni densità di probabilità.

Come suggerisce il nome, CUSUM implica il calcolo di una somma cumulata (caratteristica che lo rende sequenziale). Definiamo gk come la statistica di prova, che può essere

calcolata sequenzialmente attraverso questa somma:

 

 

         k θ k θ k k y f y f + g = g = g 1 2 1

che, prima del cambiamento, la quantità

 

 

k θ k θ y f y f 1 2 log ha media

negativa, mentre dopo il cambiamento positiva: di conseguenza, la statistica sotto osservazione gk si mantiene

intorno a 0 in condizioni normali, e cresce linearmente con pendenza positiva dopo un cambiamento, fino a quando la differenza tra due valori successivi gk-gk-1 raggiunge la soglia

h, momento in cui l’allarme scatta. Infatti, l’istante in cui viene

generato un allarme è definito come t_a =min



k  :1 g_k h



. La formula presentata per ottenere gk rileva soltanto i

cambiamenti che determinano un aumento della statistica di prova. Quando invece si deve trovare un cambiamento negativo, si deve utilizzare l'operazione di min invece che di

max nella definizione della variabile di test, e sarà rilevato un

cambiamento quando il valore di gk andrà sotto il valore

(negativo) di soglia.

La figura 12 mostra la rilevazione di un cambiamento nel valor medio di una serie temporale gaussiana. In figura, Sk

indica il logaritmo del rapporto di verosimiglianza cumulato

che è definito come

 

 

k θ 1 k k y f y f + S = S = S 2 0 0,  log , e

 

 

k θ k θ k y f y f = s 1 2

log rappresenta il logaritmo del rapporto di

verosimiglianza.

Si può osservare da questa figura che Sk ha una pendenza

negativa prima dell’istante di cambiamento e positiva dopo che il cambiamento è avvenuto. Infatti, la funzione è normalmente monotona decrescente, ma in corrispondenza di un'anomalia la sua pendenza assume un valore positivo.

Figura 12. Derivazione intuitiva di CUSUM.

L’operazione di massimizzazione consente di aggiornare correttamente il valore di gk nel caso di anomalia - quando cioè

la funzione Sk risale rispetto al valore del minimo relativo di

cioè lasciarlo pari a 0, se la funzione di distribuzione non ha subito alcun cambiamento significativo.

Supponiamo adesso di dover monitorare tutti i bucket di una hash table contemporaneamente: definiamo per esempio

yk(i) come il numero di flussi che cadono nel bucket i di una

certa hash table nell’intervallo di tempo k. Ipotizziamo ancora che fino al tempo t0, non noto, ogni valore ha un

comportamento statistico che segue una distribuzione

 



y i



i,

f _k

θ₁ ; dopo t0 avviene un cambiamento, di conseguenza

la distribuzione f_θ,i



y_k

 

i



degli yk(i) viene a modificarsi.

L’algoritmo CUSUM in questo caso prevede che l'istante di allarme sia definito come t_a=min_1iNt_a

 

i dove



k g (i) h



= (i)

ta min  :1 k  e gk(i) è la statistica per il bucket i:

 

 

 



 



 





         i y i, f i y i, f + i g = i g = i g k θ k θ k k 1 2 1 0 0, max 0, log . (13)

Viene quindi rilevata un’anomalia nel bucket i quando la variabile sotto analisi gk(i) raggiunge la soglia h.

Vediamo alcune caratteristiche di questo algoritmo di anomaly detection.

L’algoritmo CUSUM è asintoticamente ottimo, nel senso che

 se h = log



N



, allora il tempo medio prima di un falso allarme è maggiore di γ e il ritardo medio massimo di rilevazione è asintoticamente lineare con log

 

γ (quando γ);

 il ritardo medio di rivelazione di un cambiamento è asintoticamente lineare con h (per

 

h ) con una pendenza che è legata all’entropia della distribuzione prima del cambiamento.

Tuttavia, nel mondo reale, la distribuzione dei dati non è nota a priori. Quindi, sarà necessario sfruttare la versione non parametrica del multi - chart CUSUM, il Multi - chart Non - parametric CUSUM, proposto in [5] poiché essa richiede soltanto una quantità di informazioni minima sulla distribuzione delle serie temporali del traffico prima e dopo il cambiamento. Infatti, per realizzare l'approccio MNP-CUSUM è sufficiente stimare per ogni timebin alcune statistiche del primo e del secondo ordine, mentre non è necessaria la conoscenza delle intere funzioni di distribuzione a priori. Nell’MNP-CUSUM, infatti, si sostituisce il logaritmo del

rapporto di verosimiglianza

 





 



y i



i, f i y i, f k θ k θ 1 2

log della formula (13)

con una funzione L_i



y_k

 

i



, scelta in modo che il suo valor medio Ε



L_i



y_k

 

i





sia negativo prima del cambiamento e positivo dopo: si può ad esempio scegliere, per il bucket i dell’hash table considerata

 



k



k

  

i i



i y i = y i μ +cσ

L  . (14)

Con questa definizione, dove μi e σi sono il valor medio e

la deviazione standard prima del cambiamento e supponendo che il valor medio delle serie temporali dopo il cambiamento sia maggiore di μ_i+cσ_i , l’algoritmo CUSUM non parametrico risulta sensibile ai cambiamenti del valor medio delle serie temporali.

Il traffico di rete è variabile per sua natura: anche se non è presente alcuna anomalia, esso è soggetto ad alcune variazioni naturali, dovute, per esempio, agli effetti giorno/notte; a causa di tale variabilità naturale, i parametri statistici variano lentamente nel tempo. Queste variazioni avvengono tuttavia su una scala temporale significativamente più lunga rispetto a quelle relative alle anomalie, che possono

essere descritte come cambiamenti bruschi negli schemi del traffico.

Al fine di seguire i lenti andamenti dei parametri del traffico sul lungo termine, si stimano ricorsivamente il valor medio μi e la deviazione standard σi, relativi al bucket i-esimo

al tempo k, usando la stima EWMA (Exponentially Weighted Moving Average):

 

i α)y ( + ) (k αμ = (k) μ_{i i} 1 1 _k (15) e

 

2 2 1 1)+( α)(y i μ (k)) (k ασ = (k) σ 2 _{k i} i i    (16).

Per trovare le grandi variazioni, sarà necessario monitorare l’evoluzione temporale di cella con l’algoritmo CUSUM.

L'algoritmo EWMA, esposto in [4], è infatti una tecnica di predizione, che impiega i campioni degli sketch osservati negli intervalli precedenti So(t') (t' < t) per calcolare lo sketch

stimato Sf(t); opzionalmente, insieme ad esso, è possibile

ottenere l'errore Se(t) tra i due sketch osservato e stimato.

Questa tecnica è solitamente usata in applicazioni come la predizione delle serie temporali e la rivelazione dei cambiamenti.

In generale, la stima dello sketch al tempo t corrisponde alla media, pesata dal parametro α, delle predizioni precedenti e del campione appena osservato al tempo t-1:

Sf(t)= αSo



t1

 

+ 1α

 

Sf t1



,t>2

S₀

 

1,t=2

Il parametro α

 

0,1 è chiamato costante di smoothing, e stabilisce quanto peso assegnare ai nuovi campioni rispetto alla storia precedente. Tuttavia, l’algoritmo non è molto sensibile al peso α, che dovrebbe essere scelto vicino a 1, destinando maggiore importanza ai nuovi valori piuttosto che agli sketch precedenti.

Notare che la stima della media e della varianza secondo EWMA può risentire di variazioni stagionali (ore di lavoro, notte, giorno della settimana, ecc.) se si aggiornano lentamente i parametri della distribuzione di traffico μi e σi.