Ημερολόγιο Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ

Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών

Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

ΘΕΟΔΩΡΟΥ ΜΠΙΤΣΑΚΗ

με θέμα

Συσταδοποίηση Μεγάλων Ροών Δεδομένων στο Apache Flink

Clustering Big Data Streams in Apache Flink

Πέμπτη 11 Οκτωβρίου 2018, 10 π.μ.

Αίθουσα 145.Π58, Κτίριο Επιστημών, Πολυτεχνειούπολη

Εξεταστική Επιτροπή

Αναπληρωτής Καθηγητής  Δεληγιαννάκης Αντώνιος (επιβλέπων)

Καθηγητής Γαροφαλάκης Μίνως

Αναπληρωτής Καθηγητής Σαμολαδάς Βασίλειος

Περίληψη

Ζούμε στην εποχή των μεγάλων δεδομένων όπου τεράστιες ποσότητες πληροφοριών παράγονται συνεχώς από πολυάριθμους τύπους πηγών. Ο στόχος της σημερινής εποχής είναι η εφαρμογή τεχνικών που λαμβάνουν υπόψη τον όγκο, την ποικιλία και την ταχύτητα των δεδομένων, προκειμένου να αποκτήσουν γνώση που δεν θα μπορούσε να αποκαλυφθεί με παραδοσιακό λογισμικό επεξεργασίας δεδομένων. Η ανάλυση σε συστάδες είναι μια τεχνική που ομαδοποιεί ένα σύνολο αντικειμένων έτσι ώστε τα αντικείμενα που ανήκουν στην ίδια ομάδα να έχουν παρόμοιες ιδιότητες. Χρησιμοποιείται συνήθως στους τομείς της μηχανικής μάθησης, της εξόρυξης δεδομένων, της ανάλυσης στατιστικών δεδομένων, της αναγνώρισης προτύπων και της βιοπληροφορικής. Σε αυτή τη διατριβή, προτείνουμε μια παράλληλη υλοποίηση για τον γνωστό αλγόριθμο μηχανικής μάθησης χωρίς επίβλεψη, StreamKM++, για την συσταδοποίηση ροών δεδομένων με σειριακή επεξεργασία. Για τη φάση της ανάπτυξης, επιλέγουμε την πλατφόρμα Apache Flink ως μια κατανεμημένη μηχανή επεξεργασίας ροών που εκτελεί υπολογισμούς υψηλής απόδοσης, χαμηλής καθυστέρησης και αντοχής σε σφάλματα σε πεπερασμένα και άπειρα σύνολα δεδομένων. Αρχικά, εισάγουμε το θεωρητικό υπόβαθρο του υλοποιημένου αλγορίθμου και της κατανεμημένης πλατφόρμας. Στη συνέχεια, προτείνουμε μια παράλληλη υλοποίηση η οποία υπολογίζει το σύνολο των κέντρων των συστάδων μετά την κατανάλωση του συνόλου των δεδομένων εισόδου. Βασιζόμενοι σε αυτήν την υλοποίηση προτείνουμε μια εναλλακτική η οποία παράγει περιοδικά αιτήματα για επανεκτίμηση των κέντρων των συστάδων. Τέλος, αναπτύσσουμε ένα πρόγραμμα που εκμεταλλεύεται τη δυνατότητα Queryable State του Flink, προκειμένου να επιτρέψει στο χρήστη να διερευνήσει τις πιο πρόσφατες τιμές των κέντρων των συστάδων. Η πειραματική αξιολόγηση δείχνει ότι με την αύξηση του επιπέδου παραλληλισμού, ο χρόνος λειτουργίας μειώνεται σημαντικά και συγχρόνως η ποιότητα της συσταδοποίησης γίνεται ελαφρώς καλύτερη.

Abstract

We live in the era of Big Data where massive amounts of information are generated continuously from numerous types of sources. Today’s goal is to apply techniques that take into consideration the volume, the variety and the velocity of the data, in order to gain insight that couldn’t be revealed with traditional data processing application software. Cluster analysis is a technique that groups a set of objects such that objects in the same group have similar properties. It is commonly used in the fields of machine learning, data mining, statistical data analysis, pattern recognition and bioinformatics. In this thesis, we propose a parallel implementation for the well-known unsupervised learning algorithm, StreamKM++, for clustering data streams in an online fashion. For the development phase, Apache Flink framework is chosen as a distributed streaming engine with high-throughput, low-latency and fault-tolerant computations over unbounded and bounded data streams. Initially, we introduce the theoretical background of the implemented algorithm and the distributed framework. Afterwards, we propose a parallel implementation which computes the set of cluster centers after the consumption of the input dataset. In addition to that, we propose an alternative implementation which produces periodically requests for the re-evaluation of cluster centers. Finally, we develop a program that exploits the Queryable State feature of Flink, in order to allow the user to query the most up-to-date values of the cluster centers. Experimental evaluation shows that by increasing the level of parallelism the running time droops significantly and at the same time the quality of the clustering gets slightly better.