Episode Mining

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home HMM Alberi Decisionali

In molte applicazioni di data mining i dati vengono visti come sequenze di eventi, dove ogni evento ha associato un tipo e un tempo in cui accade. Un problema fondamentale nell'analisi di sequenze di eventi è trovare episodi frequenti, cioè collezioni di eventi che accadono frequentemente insieme. Gli episodi, in generale, sono insiemi parzialmente ordinati di eventi.
Dato un insieme E di tipi di evento, un evento è una coppia (A,t), dove A è un tipo di evento e t è un intero che rappresenta il tempo in cui un evento occorre.
Una sequenza di eventi s su E è una tripla (s, TS, Te) dove s = {(A1, t1),(A2, t2), ...,(An, tn)} è una sequenza ordinata di eventi tali che Ai sta in E per i = 1,...,n, ti<=ti+1 per i = 1, ..., n-1. TS e Te sono rispettivamente il tempo di inizio e il tempo di fine e TS <=ti<=Te per i = 1, ..., n.
Una finestra su una sequenza di eventi s = (s, TS, Te) è una sequenza di eventi w = (w, tS, te) dove tSTS, e w consiste di quelle coppie (A,t) tali che tS <= t <= te. La lunghezza della finestra w è te – tS.
Un episodio a è una tripla (V, <=, g) dove V è un insieme di nodi, <= è un ordinamento parziale su V, g:V --> E è una funzione che associa ogni nodo con un tipo di evento. Un episodio quindi si può interpretare come un insieme di eventi g(V) che devono accadere nell'ordine descritto da <=.
Un episodio a è parallelo se non vale x <=y per ogni x,y in V tali che x diverso da y. Un episodio a è seriale se l'ordinamento è totale, cioè si può sempre dire se x<=y o se y<=x per ogni x,y in V.
Sapendo che la frequenza di un episodio è la frazione di finestre dove esso accade, sia data una certa lunghezza di finestra e sia s una frequenza di soglia, allora un episodio è frequente se accade in almeno s finestre.
Gli episodi frequenti sono monotoni, cioè se a è un episodio frequente allora lo è anche ogni suo sottoepisodio ottenuto cancellando alcuni eventi. Allora procederemo con una tecnica Apriori:

1. Siano Ci gli episodi candidati di dimensione i e Li quelli frequenti di dimensione i.
2. Sia C1 l'insieme di tutti gli eventi.
3. Costriamo Ci+1 da Li mettendo quegli episodi E di dimensione i+1 tali che cancellando un qualunque evento da E si ottiene un elemento di Li.

1. Per ogni evento A
   1. A.count = numero di volte in cui A è stato visto nella finestra considerata
   2. A.contains = lista concatenata di tutti gli episodi che contengono A.
2. Per ogni episodio E
   1. E.starting_time = tempo in cui inizia una sequenza di finestre consecutive nella quale E è stato sempre presente
   2. E.support = numero di finestre nelle quali E è apparso escluso le finestre da E. starting_time
   3. E.missing = numero di eventi A di E che non sono presenti nella finestra corrente. E è presente nella finestra se E.missing = 0.

1. Se A scompare dalla finestra:
   A.count --;
   if (A.count == 0) // abbiamo perso A
   for (all E in A.contains) {
   E.missing++;
   if(E.missing == 1) // abbiamo perso E
   E.support + = (currentTime-E.startingTIme);
   }
2. Se B entra nella finestra:
   B.count++;
   if(B.count==1) //abbiamo guadagnato B
   for(all E in B.contains) {
   E.missing--;
   if(E.missing==0) //abbiamo guadagnato E
   E.startingTime = currentTime;
   }

1. L'istante corrente se lo stato è q0.
2. L'istante di qi-1 se entriamo in qi avendo visto A.
3. Lo stesso istante se entriamo in qi avendo visto qualcosa di diverso da Ai.

Home HMM Alberi Decisionali