Massively parallel unsupervised anomaly detection in data streams

Abstract

Outlier detection on data streams has seen a rise in popularity over the past years due to the advances of Internet of Things devices. Nevertheless, a distributed solution for distance-based outlier detection, which is one of the most widely used categories, has not been proposed for continuous data streams. This thesis proposes a solution to this problem, along with providing an efficient explanation for each outputted outlier, in contrast to the output of normal distance-based detectors. Additionally, it studies the self-adaptive problem for workload balancing on distributed streams and proposes a mechanism that works on the fly without any system interruptions.More specifically, the rationale behind the parallelization of the state-of-the-art centralized distance-based outlier detection algorithms for streams is presented along with the decisions for the partitioning phase of the ingested streams. The proposed techniques show significant improvements over their centralized counter-parts as well as a high throughput when processing an intense stream.Moreover, an explanatory labeling technique is proposed that transforms the binary output of a distance-based detector into an insightful result for the end user. By combining the explanatory process with a subspace exploration technique, the results can be further enhanced with a visualized output and insights into the subspaces and the features of the data stream that mostly contribute to or capture the outlierness. Additionally, the problem of adapting the workload of the partitioning phase has been investigated and a self-adaptive mechanism has been proposed. The mechanism uses metadata from the outlier detection phase to decide whether the value-based partitioning needs to be adapted on the fly. The process is transparent to the user and does not interrupt the system or incur any overhead on the process of outlier detection in real-time.Finally, the set of proposed techniques has been combined into a single complete open-source engine, called PROUD, that allows for distributed distance-based outlier detection for continuous and intense data streams out of the box. The solution is built on top of Apache Flink and supported by secondary open-source frameworks providing numerous extensibility points where the user can implement new techniques and algorithms.

Τις τελευταίες δεκαετίες, η εύρεση ακραίων τιμών αποτελεί ένα ενεργό ερευνητικό πεδίο με μία σωρεία εργασιών και πολλούς διαφορετικούς ορισμούς να υπάρχουν στην βιβλιογραφία. Η σημασία της ανίχνευσης ενός σημείου δεδομένων ως μία ακραία τιμή είναι διπλή. Πρώτον, τα ακραία σημεία μπορούν να αντιμετωπιστούν ως θόρυβος σε ένα σύνολο δεδομένων. Όταν ένα σύνολο δεδομένων περιλαμβάνει θόρυβο οι αλγόριθμοι επεξεργασίας μπορεί να βγάλουν λανθασμένα αποτελέσματα ή αποτελέσματα που θα οδηγήσουν σε λάθος ανάλυση από τον τελικό χρήστη. Δεύτερον, μία ακραία τιμή μπορεί να περιλαμβάνει μία σημαντική πληροφορία που θα εκμαιευθεί μέσω περαιτέρω ανάλυσης. Για παράδειγμα, ένα πρόσφατο σημείο δεδομένων σε μία συνεχή ροή δεδομένων, το οποίο ανιχνεύεται σαν ακραία τιμή, μπορεί να υποδεικνύει μία απότομη αλλαγή στην κατανομή των τιμών της ροής.Η εύρεση ακραίων τιμών έχει εδραιωθεί ως ένα σταθερό και βασικό εργαλείο στην ανάλυση δεδομένων σε πολλούς τομείς. Κάποιοι από αυτούς είναι η ανίχνευση απάτης σε τραπεζικές συναλλαγές, ανάλυση ιατρικών δεδομένων για διάγνωση ασθενειών, ανίχνευση κακόβουλης εισβολής σε υπολογιστικά συστήματα και εύρεση σημαντικών γεγονότων σε ροές δεδομένων από αισθητήρες. Κάθε τομέας και ακόμα περισσότερο κάθε ξεχωριστή περίπτωση χρήσης μπορεί να επωφεληθεί από διαφορετικούς αλγόριθμους εύρεσης ακραίων τιμών σε διαφορετικό βαθμό. Για παράδειγμα, στην ανίχνευση απάτης σε τραπεζικές συναλλαγές, διαφορετικοί αλγόριθμοι και διαφορετικοί ορισμοί ακραίων σημείων μπορούν να καλύψουν διαφορετικών ειδών απάτες από συνεχείς μικρές μέχρι μεμονωμένες μεγάλες συναλλαγές.Ταυτόχρονα, τα τελευταία χρόνια, έχουν αναπτυχθεί και εξελιχθεί απότομα οι αισθητήρες διαφόρων τύπων με αποτέλεσμα την παραγωγή όλο και μεγαλύτερων όγκων δεδομένων σε μεγαλύτερη συχνότητα. Αυτό δημιουργεί την ανάγκη για συνεχή ανάλυση δεδομένων σε έντονες και συνεχείς ροές δεδομένων που προέρχονται από πληθώρα αισθητήρων. Αυτό έχει σαν αποτέλεσμα να γίνει πιο έντονο το ερευνητικό ενδιαφέρον σε αυτό το πεδίο και πιο συγκεκριμένα στην συνεχή ανίχνευση ακραίων τιμών. Εφαρμογές όπως η έξυπνη γεωργία, η πρόγνωση της κυκλοφοριακής κατάστασης σε έναν δρόμο καθώς και η προληπτική συντήρηση μηχανημάτων σε εργοστάσια της τέταρτης βιομηχανικής επανάστασης χρησιμοποιούν κατά κόρον ένα μεγάλο αριθμό αισθητήρων που συνεχόμενα παράγουν τιμές για τις μετρικές που χρειάζονται κατά τη διάρκεια της ανάλυσης. Αυτό έχει σαν επακόλουθο την ανάγκη για υλοποιήσεις που μπορούν εύκολα να διαχειρίζονται πολλές πηγές δεδομένων και να αναλύουν τον αυξημένο όγκο μέσα σε ένα εύλογο χρονικό διάστημα. Συνδυάζοντας όλα τα παραπάνω, η παράλληλη ανάλυση σε κατανεμημένα περιβάλλοντα έχει αναδειχθεί ως η κύρια μορφή ανάλυσης λόγω της απότομης αύξησης παραγωγής δεδομένων από τους αισθητήρες που επηρεάζει τον όγκο δεδομένων αλλά και τη συχνότητα παραγωγής. Στην εύρεση ακραίων τιμών, μία οικογένεια αλγορίθμων και πιο συγκεκριμένα οι αλγόριθμοι με βάση την απόσταση έχουν προταθεί και αναπτυχθεί για την αποτελεσματική και αποδοτική ανάλυση σε συνεχείς ροές δεδομένων. Η απλότητα των συγκεκριμένων αλγορίθμων έχει αποτελέσει έναν καθοριστικό παράγοντα στην χρήση τους πάνω στην ανάλυση ροών δεδομένων. Οι συγκεκριμένοι αλγόριθμοι μπορούν να κατηγοριοποιηθούν σε δύο βασικές κατηγορίες. Τους κεντρικοποιημένους αλγόριθμους που εφαρμόζονται σε ροές δεδομένων και τους παράλληλους αλγόριθμους που εφαρμόζονται σε στατικά δεδομένα, όπως βάσεις δεδομένων.Ο συνδυασμός αυτών των δύο κατηγοριών είναι ο βασικός σκοπός της συγκεκριμένης διατριβής. Πιο συγκεκριμένα, μελετήθηκε και παρουσιάζεται η λογική πίσω από την παραλληλοποίηση των κεντρικοποιημένων αλγορίθμων εύρεσης ακραίων τιμών σε ροές δεδομένων με βάση την απόσταση. Μέσα από τη μελέτη εντοπίστηκε η πιο κατάλληλη τεχνική διαμοιρασμού δεδομένων σε μία συστοιχία υπολογιστικών πόρων που βοηθάει στην πιο αποδοτική και αυτόνομη εκτέλεση των αλγορίθμων εύρεσης ακραίων τιμών. Ταυτόχρονα, μέσα από τον συνδυασμό των διαφορετικών τεχνικών, που χρησιμοποιούνται στους κεντρικοποιημένους αλγόριθμους, υλοποιήθηκαν νέοι αλγόριθμοι κατάλληλοι για κατανεμημένα περιβάλλοντα.Ένα πρόβλημα που αντιμετωπίζουν οι αλγόριθμοι εύρεσης ακραίων τιμών με βάση την απόσταση είναι η αφαιρετικότητα των αποτελεσμάτων τους. Οι συγκεκριμένοι αλγόριθμοι συνήθως βγάζουν σαν αποτέλεσμα είτε έναν αυθαίρετο βαθμό ακραιότητας για κάθε σημείο δεδομένων είτε μόνο την κατάσταση για κάθε σημείο (ακραία ή φυσιολογική τιμή). Τέτοιου είδους αποτελέσματα δεν βοηθάνε τον τελικό χρήστη να καταλάβει καλύτερα το «γιατί» ανιχνεύθηκε ένα συγκεκριμένο σημείο ως ακραίο. Ταυτόχρονα, η επεξήγηση των αποτελεσμάτων από τους αλγόριθμους μηχανικής μάθησης έχει αποτελέσει πρόσφατα ένα πολύ σημαντικό ερευνητικό πεδίο.Το παραπάνω, αποτελεί και το δεύτερο πρόβλημα που μελετήθηκε και παρουσιάζεται στη διατριβή. Το αποτέλεσμα της μελέτης είναι η ανάπτυξη μίας τεχνική επεξήγησης των αποτελεσμάτων που βασίζεται στα μεταδεδομένα, τα οποία παράγουν ήδη οι συγκεκριμένοι αλγόριθμοι και πιο συγκεκριμένα τις αποστάσεις κάθε σημείου από τους γείτονές του. Η επεξηγηματική τεχνική έχει ως αποτέλεσμα να αποδίδει σε κάθε ακραίο σημείο μία κατηγορία με βάση την γειτονιά του. Επίσης, για την καλύτερη επεξήγηση των δεδομένων πολλών διαστάσεων έχει χρησιμοποιηθεί μία τεχνική εξερεύνησης των δισδιάστατων και τρισδιάστατων συνδυασμών που προκύπτουν από το πλήρες σύνολο διαστάσεων. Ο συνδυασμός των δύο παραπάνω τεχνικών δίνει περισσότερη έμφαση στην επεξήγηση με την βοήθεια της απεικόνισης των αποτελεσμάτων.Στη συνέχεια, ένα σύνηθες πρόβλημα στην ανάλυση ροών δεδομένων σε κατανεμημένα περιβάλλοντα είναι ο σωστός διαμοιρασμός του φόρτου εργασίας. Το πρόβλημα αυτό γίνεται περισσότερο αντιληπτό όταν αλλάζει απότομα η κατανομή των τιμών της εισερχόμενης ροής και όλα τα νέα δεδομένα διαμοιράζονται σε ένα διαμέρισμα. Το συγκεκριμένο πρόβλημα έχει ερευνηθεί ενδελεχώς στην βιβλιογραφία με κύριο αποτέλεσμα την ανάπτυξη τεχνικών για την ένωση και τον διαχωρισμό των διαμερισμάτων εργασίας με βάση τον φόρτο. Παρόλα αυτά, στις εφαρμογές που περιλαμβάνουν την ανάλυση των δεδομένων με βάση την εγγύτητά τους, όπως είναι οι αλγόριθμοι που έχουν μελετηθεί στην διατριβή, οι τεχνικές ένωσης και διαχωρισμού διαμερισμάτων δεν είναι αποδοτικές.Το παραπάνω πρόβλημα αποτελεί το τρίτο κεφάλαιο μελέτης της διατριβής. Πιο συγκεκριμένα, μελετήθηκαν και αναπτύχθηκαν τεχνικές διαμοιρασμού φόρτου εργασίας που αλλάζουν τα όρια των διαμερισμάτων εργασίας. Με αυτόν το τρόπο ο αριθμός των σημείων δεδομένων που διαμοιράζονται στα προβληματικά διαμερίσματα αλλάζει αποδοτικά. Ταυτόχρονα, οι τεχνικές δουλεύουν σε συνθήκες πραγματικού χρόνου, που σημαίνει ότι το σύστημα και η ανάλυση δεν χρειάζονται να σταματήσουν ή να διακοπούν κατά τη διάρκεια της αλλαγής των ορίων των διαμερισμάτων. Αντ’ αυτού η διαδικασία είναι διαφανής προς τον χρήστη και την ανάλυση δεδομένων και γίνεται στο φόντο χωρίς να δημιουργεί κώλυμα στο χρόνο εκτέλεσης.Τέλος, όλες οι τεχνικές και οι αλγόριθμοι που αναπτύχθηκαν κατά τη μελέτη των προηγούμενων προβλημάτων στο πλαίσιο της διατριβής έχουν συνδυαστεί και υλοποιηθεί σε ένα ολοκληρωμένο σύστημα ανοιχτού κώδικα. Το συγκεκριμένο σύστημα αποτελεί ένα αποδοτικό και αποτελεσματικό κατανεμημένο εργαλείο για την εύρεση ακραίων τιμών σε έντονες και συνεχείς ροές δεδομένων. Έχει χτιστεί πάνω από γνωστά και διαδεδομένα συστήματα ανοιχτού κώδικα, με τον πυρήνα ανάλυσης να αποτελείται από το Apache Flink. Το ολοκληρωμένο σύστημα περιέχει πολλά σημεία επεκτασιμότητας ώστε κάθε ενδιαφερόμενος χρήστης, πέρα από τους υλοποιημένους αλγόριθμους, να μπορεί να συμπεριλάβει και διαφορετικούς ανάλογα την περίπτωση.