Discovering Frequent Episodes in sequences

Ένα επεισόδιο ορίζεται σαν μια συλλογή από γεγονότα τα οποία εμφανίζονται μέσα σε συγκεκριμένο χρονικό διάστημα , δοθέντος ενός μεγέθους και μιας μερικής διάταξης, μέσα από ακολουθίες γεγονότων.

Μεγάλα log files τα οποία συνήθως είναι μη ταξινομημένες συλλογές δεδομένων μπορούν να ειδωθούν ως ακολουθίες γεγονότων.

Ένα πράδειγμα ακολουθίας γεγονότων είναι το παρακάτω

(Α,123), (Β,125), (D,140), (Α,150), (C,151),

(Β,155), (D,201), (A,220), (D,222), (B,225).

Το βασικό πρόβλημα που τίθεται είναι να βρούμε τα συχνά επεισόδια

Γενικά μιλώντας τα επεισόδια είναι μερικά διατεταγμένα σύνολα από γεγονότα. Μπορούν ακόμα να περιγραφούν και σαν κατευθυνόμενοι ακυκλικοί γράφοι, όπως τα παρακάτω παράδειγμα

Σειριακα Επεισόδια

Το επεισόδιο του σχήματος (α) δηλώνει ένα σειριακό επεισόδιο και συμβαίνει όταν υπάρχουν γεγονότα Α, Β, C και τα οποία εμφανίζονται με αυτή την σειρά σχετικά κοντά το ένα με το άλλο.

Παράλληλα Επεισόδια

Το επεισόδιο Β είναι ένα παράλληλο επεισόδιο. Κανένας περιορισμός δεν υπάρχει για την σχετική σειρά εμφάνισης των επεισοδίων A,B, C.

Οσον αφορά το επεισόδιο (c) είναι μικτού τύπου και συμβαίνει όταν υπάρχουν εμφανίσεις των γεγονότων A και Β και αυτά προηγούνται των εμφανίσεων C και D. Κανένας περιορισμός δεν υπάρχει για την σχετική σειρά των A,B (η C,D). Και οι 4 εμφανίσεις πρέπει να είναι σχετικά κοντά μεταξύ τους. Το πόσο κοντά είναι αρκετό αυτό το κανονίζει ο χρήστης ορίζοντας το time window.

Στην ανάλυση των ακολουθιών δεδομένων ο χρήστης ενδιαφέρεται για την εύρεση όλων των συχνών επεισοδίων από μια κλάση επεισοδίων. Μια κλάση επεισοδίων θα μπορούσε πχ να ήταν όλα τα σειριακά επεισόδια, όλα τα παράλληλα επεισόδια ή όλα τα επεισόδια των οποίων η μερική διάταξη ταιριάζει σε ένα τμήμα τοπολογίας δικτύου κ.λ.π

Εύρεση συχνών επεισοδίων

Σχετικά με την εύρεση των συχνών επεισοδίων το πρόβλημα έχει ως εξής.

Δοθείσης μιας κλάσης επεισοδίων , μια ακολουθία εισόδου από γεγονότα , ένα πλάτος παραθύρου και ένα κατώφλι συχνότητας. Βρείτε όλα τα επεισόδια από την κλάση τα οποία συμβαίνουν συχνά.

Παρακάτω θα περιγράψουμε ένα γενικό αλγόριθμο που λύνει αυτό το πρόβλημα. Ο αλγόριθμος έχει δύο εναλλακτικές φάσεις: Κατασκευή νέων υποψήφιων επεισοδίων και Υπολογισμός του πόσο συχνά αυτά συμβαίνουν στην ακολουθία. Η αποδοτικότητα του αλγορίθμου βασίζεται σε τρείς παρατηρήσεις.

1) Ενώ πραγματικά υπάρχει ένας πολύ μεγάλος αριθμός επεισοδίων για έλεγχο, ο αριθμός αυτός μπορεί να μειωθεί δραστικά κατασκευάζοντας μεγαλύτερα επεισόδια από μικρότερα με ένα συγκεκριμένο τρόπο. Εάν το σειριακό επεισόδιο ABC είναι συχνό, τότε μέσα στο ίδιο πλάτος παραθύρου και τα σειριακά υποεπεισόδια AB, BC και AC είναι και αυτά συχνά. Αυτό ισχύει γενικά : Όλα τα υποεπεισόδια ενός υπερεπεισοδίου είναι τουλάχιστο τόσον συχνά όσο το υπερεπεισόδιο. Ο αλγόριθμος αυτό το χρησιμοποιεί από την αντίθετη κατεύθυνση. Αρκεί να ελέγξουμε ως συχνά εκείνα τα επεισόδια των οποίων όλα τα υποεπεισόδια είναι συχνά.

2) Τα επεισόδια μπορούν να αναγνωρισθούν αποτελεσματικά ολισθαίνοντας ένα χρονικό παράθυρο πάνω στην ακολουθία εισόδου. Τυπικά δύο γειτονικά παράθυρα έχουν πολλά κοινά επικαλυπτόμενα σημεία και επομένως είναι πολύ όμοια το ένα με το άλλο. Παίρνουμε πλεονέκτημα από αυτή την παρατήρηση: Μετά την αναγνώριση των επεισοδίων σε ένα παράθυρο αρκει μόνο να κάνουμε κάποιες αυξητικές αλλάγές στα δεδομένα μας για να αναγνωρίσουμε τα επεισόδια στο επόμενο παράθυρο.

3) Η αναγνώριση σύνθετων επεισοδίων μπορεί να αναχθεί στην αναγνώριση απλών συστατικών πεδίων. Κάθε επεισόδιο μπορεί να ειδωθεί σαν ένας αναδρομικός συνδυασμός από παράλληλα και σειριακά επεισόδια.

Φορμαλισμός

Δοθείσης μιας κλάσης Εο από στοιχειώδεις τύπους γεγονότων, ένα γεγονός είναι ένα ζευγάρι (e,t) , όπου e € Eo και t είναι ένας ακέραιος. Μια ακολουθία γεγονότων S είναι μια τριπλέτα (Ts, T^s, S) όπου Τs είναι ο χρόνος έναρξης, T^s είναι ο χρόνος κλεισίματος και S είναι μια διατεταγμένη ακολουθία από γεγονότα, δηλ.

S = (e₁,t₁), (e₂,t₂), ..., (e_n,t_n),

Όπου e_i € Eo και Τs ≤ t_i < T^s για όλα τα i =1,..,n, και t_i ≤ t_i+1 για όλα τα I=1,…,n-1.

Ένα παράθυρο πάνω σε μια ακολουθία γεγονότων S=(Ts, T^s, S) είναι μια ακολουθία γεγονότων W=(T_w,T^w,W) , όπου Ts≤T_w , T^w ≤ T^s και το W αποτελείται από όλα εκείνα τα ζευγάρια (e_i,t_i) από το S όπου Tw≤t_i<T_w. Το πλάτος του παραθύρου είναι width(W)=T^w-T_w . Δοθείσης μιας ακολουθίας γεγονότων S και ενός ακεραίου w συμβολίζουμε με aw(S,w) όλα τα παράθυρα W απάνω στο S τέτοια ώστε width(W)=w.

Επεισόδια

Ένα στοιχειώδες επεισόδιο φ=(V, ≤,g) είναι ένα σύνολο από κόμβους, μια μερική διάταξη ≤ επάνω στο V και μια απεικόνιση g:V→Eo που συνδέει κάθε κόμβο με ένα τύπο γεγονότος. Η ερμηνεία ενός επεισοδίου είναι ότι τα γεγονότα στο g(V) πρέπει να συμφωνούν με την διάταξη που περιγράφεται από την σχέση ≤.

Ένα επεισόδιο είναι παράλληλο εάν η σχέση μερικής διατάξεως ≤ είναι τετριμμένη (δηλ. x ≤ y για όλα χ≠y). Το επεισόδιο φ είναι σειριακό εάν η σχέση μερικής διατάξεως είναι σχέση και ολικής διατάξεως.

Συχνά Επεισόδια.

Ένα παράλληλο επεισόδιο φ=(V, ≤,g) συμβαίνει σε μια ακολουθία γεγονότων S εάν όλα τα επεισόδια στο g(V) συμβαίνουν διαζευκτικά στο S, Ενώ ένα σειριακό επεισόδιο φ= (V, ≤,g) συμβαίνει σε μια ακολουθία S εάν υπάρχουν απεικονίσεις

h₁,h₂ : V→ {1,2,…,n} τέτοιες ώστε για όλα τα υ € V το υποεπεισόδιο g(υ) συμβαίνει στην ακολουθία (t_h1(υ),t_h2(υ)+1,((e_h1(υ), t_h1(υ)) ,…,(e_h2(υ), t_h2(υ)))) και για όλα τα υ,w € V με υ≤w έχουμε h₂(υ)<h₁(w).

Eάν ένα επεισόδιο συμβαίνει στο S γράφουμε SÜ φ . Η συχνότητα του φ στο σύνολο aw(S,w),όλων των παραθύρων στο S μεγέθους w είναι

fr(φ,S,w) =( |{W Î aw(S,w) | WÜ φ } | ) / ( | aw(S,w) | )

Δοθέντος ενός κατωφλίου συχνότητας min_f_r για την συχνότητα , ένα επεισόδιο φ είναι συχνό εάν fr(φ,S,w) ³ min_f_r , φυσικά εάν το φ είναι συχνότότε όλα τα υποεπεισόδιά του είναι συχνά. Το πρόβλημα τώρα είναι το ακόλουθο. Εάν μας δίδεται μια ακολουθία S , μια κλειστή κλάσση C από επεισόδια , ένα πλάτος παραθύρου w και ένα κατώφλι συχνότητας min_f_r να βρεθούν όλα τα συχνά επεισόδια.

O Αλγόριθμος

Παρουσιάζουμε τώρα ένα Αλγόριθμο για την εύρεση όλων των συχνών επεισοδίων φ Î C σε μια δοθείσα ακολουθία γεγονότων S , δοθείσης μιας κλειστής κλάσσης C από επεισόδια και ένα κατώφλι συχνότητας min_f_r .

1. C₁:={{e} | e Î Eo };

2. i:=1;

3. while C_i ¹ 0 do

4. recognition: Διάβασε την ακολουθία S , και

έστω Li να είναι τα συχνά στοιχεία του Ci

σε σχέση με το min_f_{r ;}

5. building: Υπολόγισε C_i+1 Ì C από το Li ;

6. i:=i+1;

7. od;

8. for all i, τύπωσε Li ;

Ο αλγόριθμος δουλεύει επαναληπτικά εναλάσσοντας μεταξύ των φάσεων building και recognition. Πρώτα στη φάση building κατά την διάρκεια μιας επανάληψης i , μια συλλογή C_i από νέα υποψήφια επεισόδια από i στοιχειώδη γεγονότα κατασκευάζεται, χρησιμοποιώντας την πληροφορία που είναι διαθέσιμη από μικρότερα συχνά επεισόδια. Τότε αυτά τα υποψήφια επεισόδια αναγνωρίζονται στην ακολουθία γεγονότων και οι συχνότητές τους υπολογίζονται. Η συλλογή L_i αποτελείται από όλα τα συχνά επεισόδια από το C_i . Εις την επόμενη επανάληψη i+1, υποψήφια επεισόδια στο C_i+1 χτίζονται χρησιμοποιώντας την πληροφορία για τα συχνά επαισόδια στο L_i . Ο αλγόριθμος ξεκινά κατασκευάζοντας το C₁ να περιέχει όλα τα επεισόδια που αποτελούνται από μονά στοιχειώδη γεγονότα. Στο τέλος τυπώνονται όλα τα συχνά επεισόδια από το L_i .

Κατασκευάζοντας νέα επεισόδια

Ας ενθυμηθούμε ότι όλα τα υποεπεισόδια φ¢ ενός συχνού επεισοδίου φ είναι επίσης συχνό. Αυτός είναι και πραγματικά ο ορισμός των υποψήφιων επεισοδίων. Σε κάθε επανάληψη υποψήφια είναι όλα εκείνα τα επεισόδια μεγέθους i του οποίου όλα τα υποεπεισόδια είναι συχνά.

Μια μέθοδος για να υπολογίσουμε την υποψήφια συλλογή C_i είναι γεννήσουμε επεισόδια φ μεγέθους i και έπειτα να ελέγξουμε ότι όλα τα άμεσα υποεπεισόδια ανήκουν στο L_{i –1}

Αναγνώριση Επεισοδίων σε ακολουθίες

Τα επεισόδια αναγνωρίζονται στις ακολουθίες κατά ένα αυξητικό τρόπο. Δύο γειτονικά παράθυρα Wi = (Ti , Ti+w, Wi ) και Wi+1 = (Ti+1, Ti+w+1, Wi+1) είναι τυπικά πολύ όμοια το ένα με το άλλο. Παίρνουμε πλεονέκτημα από αυτό : μετα την αναγνώριση επεισοδίων στο Wi , κάνουμε αυξητικές ενημερώσεις στις δομές δεδομένων μας , ώστε να επιτύχουμε ολίσθηση του παραθύρου ώστε να λάβουμε το Wi+1

Επίσης ένα σημαντικό που πρέπει να έχουμε υπ’ όψιν μας είναι ότι κάθε στοιχειώδες επεισόδιο μπορεί να ειδωθεί σαν ένα σύνθετο επεισόδιο που αποτελείται από σειριακά και παράλληλα επεισόδια που και αυτά με την σειρά τους μπορεί να είναι και σύνθετα. Αυτό μας επειτρέπει ένα ανδρομικό ορισμό των επεισοδίων. Ετσι λοιπόν κατά την φάση της αναγνώρισης των επεισοδίων στις ακολουθίες γεγονότων αποσυνθέτουμε αναδρομικά τα επεισόδια σε παράλληλα και σειριακά επεισόδια.

Για να ελέγξουμε εάν ένα παράλληλο επεισόδιο φ=p(φ₁,φ₂,…,φ_n) συμβαίνει, εφαρμόζουμε την μέθοδο για τα παράλληλα επεισόδια , ενώ για να ελέγξουμε εάν ένα σειριακό επεισόδιο φ=s(φ₁,φ₂,…,φ_n) συμβαίνει εφαρμόζουμε την μέθοδο για τα σειριακά επεισόδια.

Ελεγχος για παράλληλα Επεισόδια

Το μεγάλο πρόβλημα της μετατροπής των υποψήφιων γεγονότων Ci σε Li είναι με ένα πέρασμα στα δεδομένα να ελέγχουμε για το κάθε ένα τύπο επεισοδίου το πόσες φορές εμφανίζεται. Για να γίνει εφικτό αυτό χρησιμοποιούμε ένα τυπικό αλγόριθμο που κάνει τον έλεγχο σειριακά και ενημερώνει τους κατάλληλους μετρητές.

Η δομή δεδομένων που χρησιμοποιείται είναι :

1. Για κάθε τύπο γεγονότος Α χρησιμοποιούμε

1. Ένα μετρητή Α.count που μετράει τον αριθμό των εμφανίσεων του Α στο παράθυρο.
2. Μια συνδεδεμένη λίστα Α.contains που συνδέει όλα τα επισόδια Ε που περιέχουν το Α

2. Για κάθε υποψήφιο επεισόδιο Α έχουμε
1. Το χρόνο E.startingTime που είναι η αρχή μιας διαδοχικής σειράς παραθύρων μέχρι το τρέχον παράθυρο στα οποία εμφανίζεται διαδοχικά και ανελλιπώς το επεισόδιο.
2. Ένα ακέραιο E.support που μετράει τον αριθμό των εμφανίσεων του επεισοδίου στα παράθυρα μη συμπεριλαμβανομένων των παραθύρων πριν το E.startingTime
3. Έναν ακέραιο E.missing ο οποίος μετράει των αριθμό των γεγονότων που λείπουν από το επεισόδιο στο τρέχον παράθυρο. Προφανώς το Ε είναι παρόν (εμφανίζεται στο τρέχον παράθυρο) εάν E.missing = = 0.

Ελεγχος για Σειριακά Επεισόδια

Για να ελέγξουμε εάν το σειριακό επεισόδιο (Α₁,…,Αn) εξομοιώνουμε την λειτουργία ενός μη ντετερμινιστικού πεπερασμένου αυτόματου το οποίο αναγνωρίζει συμβολοσειρές του τύπου * Α₁,…,Αn όπως αυτό φαίνεται στην παρακάτω εικόνα.

Ένα μη Ντετερμινιστικό Πεπερασμένο αυτόματο (NFA) που αναγνωρίζει σειριακά επεισόδια.

Καθώς διατρέχουμε τα δεδομένα και και ελέγχουμε ένα προς ένα τα γεγονότα παρακολουθούμε και το σύνολο των καταστάσεων στις οποίες μεταβαίνει και το NFA.

Δινουμε τώρα μια περιγραφή του πώς δουλεύει το NFA .

• Το επεισόδιο μένει στην ίδια κατάσταση εάν η είσοδος είναι ένα γεγονός το οποίο δεν είναι μέρος του επεισοδίου.
• Καθώς εξομοιώνουμε την λειτουργία κρατάμε για κάθε κατάσταση στην οποία ευρίσκεται το αυτόματο, το πιο πρόσφατο σημείο από το οποιο μπορούμε να έχουμε ξεκινήσει το αυτόματο και να έχουμε φτάσει στην τρέχουσα κατάσταση. Το σημείο αυτό είναι ;
• Ο τρέχοντας χρόνος εάν μπαίνουμε στην κατάσταση q₁.
• O χρόνος του q_i-1 εάν μπαίνουμε στην κατάσταση q_i διαβάζοντας A_i.
• Το ίδιο χρόνο όπως προηγούμενα, εάν είμασταν ήδη στην κατάσταση q_i και η επόμενη είσοδος ήταν διαφορετική από το A_i.

• Εάν το NFA για το επεισόδιο Ε μπαίνει στην κατάσταση αποδοχής q_n , αλλά δεν ήταν προηγούμεναστην κατάσταση αυτή, τότε θέτουμε το E.startingTime με το χρόνο με τον οποίο εκείνη την στιγμή συνδέεται η κατάσταση q_n .
• Εάν κάθε συνδεόμενος χρόνος με μια συγκεκριμένη κατάσταση είναι μικρότερος από τον τρέχοντα χρόνο μείoν τo w (το μήκος του μπαραθύρου) τότε διγράφουμε αυτή την κατάσταση από το σύνολο των καταστάσεων στα οποία το NFA έχει μπεί. Εάν η αποδεκτή κατάσταση q_n χάνεται με αυτό τον τρόπο τότε προσθέτουμε το E.startingTime μείον τον τρέχοντα χρόνο στο Ε.support.

Πειραματικά Αποτελέσματα.

Εφαρμόσαμε τις μεθόδους αυτές σε μια βάση δεδομένων λαθών από ένα δίκτυο τηλεπικοινωνιών. Η βάση δεδομένων αποτελείτο από 73679 σήματα συναγερμού καλύπτοντας μια χρονική περίοδο 50 ημερών.

Αποδοτικότητα μεθόδων

Οι πίνακες 1,2 δίνουν μια συνόψιση της ανακάλυψης συχνών επεισοδίων με εμπιρικά δεδομένα

Πίνακας 1. Χαρκτηριστικά τρεξίματα με ένα σταθερό κατώφλι συχνότητας min_fr και μεταβαλλόμενο πλάτος παραθύρου

Πίνακας 2. Χαρακτηριστικά τρεξίματα με ένα σταθερό πλάτος παραθύρου w=60s και μεταβαλλόμενο κατώφλι συχνότητας min_fr

Ο πίνακας 3 παρουσιάζει τον αριθμό των υποψήφιων και συχνών επεισοδίων ανά επανάληψη κατά μέσο όρο πάνω σε ένα αριθμό δοκιμών τρεξιμάτων.

Πίνακας 2. Αριθμός των σειριακών υποψήφιων και συχνών επεισοδίων ανά επανάληψη με κατώφλι συχνότητας min_fr =0,003, κατά μέσο όρο πάνω σε παράθυρα με πλάτη w=10,20,40,60,80,100 και 120s. HS είναι το μέγεθος του υποθετικού χώρου. ‘match’ είναι το κλάσμα |Li|/|Ci|.

Η εικόνα 2 παρουσιάζει τον λόγο των χρόνων για την τετριμμένη έναντι της επαυξημένης μεθόδου για την αναγνώριση υποψήφιων επισοδίων. Η εικόνα δείχνει ότι οι εοπυξημένες μέθοδοι είναι γρογορότερες κατά ένα παράγοντα 1-20 προσεγγιστικά γραμμικά σε σχέση με το πλάτος παραθύρου( 10- 120) .

Eικόνα 2. Λόγος των χρόνων που απαιτούνται με την τετριμμένη μέθοδο έναντι της επαυξημένης μεθόδου για αναγνώριση παράλληλων (συνεχής γραμμή) και σεριακών επεισοδίων (εστιγμένη γραμμή) σαν συναρτήσεις του πλάτους παραθύρου w.

Δημιουργήσαμε και δοκιμές με αυξήσεις στη βάση δεδομένων αυξάνοντας τα κλασσέρ των δεδομένων από 1-8 με 74 έως 590 χιλιάδες γεγονότα το κέθε κλασσέρ και παρατηρούμε όπως δείχνει η εικόνα 3 ο χρόνος αυξάνεται γραμμικά.

Αποτελέσματα αύξησης κλίμακας για αναγνώριση παράλληλων (συνεχής γραμμή) και σεριακών επεισοδίων (εστιγμένη γραμμή) με w=60s και min_fr =0,01

Αναφορές

1) Agrawal, R., and Srikant, R. 1994. Fast algorithms for mining association rules in large Databases. International Conference on Very Large Databases.

2) Agrawal, R., Mannila, H.; Srikant.; Toivonen, H.; and Verkamo, A. I. 1995. Fast Discovery of Assotiation Rules

3) Aho, A. V. 1990 Algorithms for finding patterne in strings. Advances in Knowledge Discovery and Data Minimg. AAAI Press

4) Heikki Mannila and Hannu Toivonen and A. Inkeri Verkamo. Discovering Frequent Episodes in Sequences.

ΕΠΙΣΤΡΟΦΗ ΣΤΗΝ ΑΡΧΙΚΗ ΣΕΛΙΔΑ