Προσεγγιστικές μέθοδοι για τον εντοπισμό εξωκείμενων αντικειμένων σε ροές δεδομένων
Creators: name: Δεσύλλας, Σπυρίδων Αλφρέδος Κωνσταντίνου
Publisher: name: Aristotle University of Thessaloniki
Year: 2013
Subjects: ανίχνευση
εξώκοιλο
ροή
detection
outlier
stream

description: Το ισχύον επίπεδο της τεχνολογίας προσφέρει τη δυνατότητα και ταυτόχρονα δημιουργεί την ανάγκη, για τη γρήγορη επεξεργασία μεγάλων όγκων δεδομένων. Έτσι, σε πολλούς τομείς, παρατηρείται μία στροφή από τα κλασικά μοντέλα επεξεργασίας δευτερεύουσας μνήμης προς τα μοντέλα επεξεργασίας ροών. Ένα από τα πεδία εφαρμογής τέτοιων αλγόριθμων, είναι η εύρεση εξώκοιλων αντικειμένων (outliers) σε ροές δεδομένων. Η εύρεση των outliers, διαισθητικά, αφορά την ανίχνευση αντικειμένων που δεν «ταιριάζουν», με βάση κάποια προκαθορισμένα κριτήρια, σε ένα (δυναμικό) σύνολο στοιχείων. Η διαδικασία αυτή βρίσκει εφαρμογή σε ποικίλες περιπτώσεις. Τυπικά παραδείγματα τέτοιων περιπτώσεων είναι τα αρχεία καταγραφής (log files) των web servers, τα στοιχεία συναλλαγών σε τραπεζικούς οργανισμούς ή ακόμα κι η πληροφορία που καταφτάνει σε ένα κέντρο επεξεργασίας από ένα δίκτυο αισθητήρων (π.χ. θερμοκρασίας, σε κάποιον ωκεανό) σε πραγματκό χρόνο. Το φάσμα χρήσης της εξαγώμενης πληροφορίας, σε αυτά τα σενάρια περιέχει περιπτώσεις από την απλή στατιστική ανάλυση, για ακαδημαϊκούς ή κι εμπορικούς σκοπούς, μέχρι τη διασφάλιση ευαίσθητων προσωπικών πληροφοριών από οργανισμούς, όπως οι τραπεζικοί, μέσω της ανίχνευσης επικίνδυνης δραστηριότητας ή κι απάτης. Οι εκάστοτε απαιτήσεις, βεβαίως, μπορεί να διαφέρουν αλλά οι αρχές χρήσης παραμένουν ίδιες κι όσο περνάει ο καιρός κι η τεχνολογία προοδεύει, τόσο πιο επιτακτική γίνεται η ανάγκη για πιο αποδοτικούς κι αξιόπιστους αλγόριθμους. Η παρούσα εργασία υλοποιεί κι επεκτείνει δύο αλγόριθμους για την εύρεση εξωκείμενων αντικειμένων σε ροές δεδομένων, ονομαστικά, τους COD και MCOD. Τους επεκτείνει εισάγοντας την έννοια της προσεγγιστικότητας στον τρόπο λειτουργίας τους, έτσι ώστε να εκτελούνται πιο γρήγορα, χρησιμοποιώντας λιγότερους πόρους και ταυτόχρονα, προσφέροντας εγγυήσεις σχετικά με το περιθώριο λάθους που εισάγεται από την προσεγγιστική διαδικασία. Η μεθοδολογία της βασίζεται στις εργασίες [1] και [2], κάθε μία από τις οποίες περιγράφεται λεπτομερώς στο κείμενο που ακολουθεί.
description: The current level of technology offers the possibility and at the same time, creates the need, to quickly process large volumes of data. Thus, in several domains there exists a turn from the classical models of data processing, pertaining to secondary storage, towards processing models in the domain of data streams. One of the possible fields of application of such algorithms is outlier detection in streams of data. Intuitively, outlier detection refers to the process of revealing objects that “don't fit”, based on an array of predefined characteristics, in a (dynamic) set of elements. This process has proven to be effective in a broad variety of situations. Typical examples of such situations are the log files of web servers, transaction data regarding financial entities, such as banks, as well as information sent from a sensor network to a data processing center (e.g. temperature registring sensors floating in the middle of an ocean) in real time. The spectrum of usefulness of the extracted information, in scenarios such as the above, contains cases ranging from simple statistical analysis, for academic or commercial purposes, to securing sensitive personal information from organizations, such as banks, through the detection of dangerous or even fraudulent activity. Even though the requirements may vary in each scenario, the principles remain the same and the more time passes and technology advances, the more intense the need for more efficient and trustworthy algorithms. This boost in efficiency is often acheived by turning an existing algorithm to an approximate equivalent. This generally means that precision is, in some controlled way, sacrificed in order to increase speed or/and to decrease the consumption of resources. The present thesis implements and extends two algorithms for outlier detection in data streams, namely COD and MCOD. It extends them by introducing the notion of approximation in their logic, so that they run faster, using less resources and at the same time, offering guaranties regarding the error introduced by the approximation process. Its methodology is based on the work laid out in [1] and [2], each of which are described in detail in the text that follows.