Συντάχθηκε 14-09-2018 14:03
Ενημερώθηκε:
17-09-2018 10:04
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Χρήστου Ζιάκα
με θέμα
Υλοποίηση Δέντρων Αποφάσεων για Ροές Δεδομένων στην Πλατφόρμα Spark Streaming
Implementation of decision trees for data streams in the Spark Streaming platform
Δευτέρα 17 Σεπτεμβρίου 2018, 11 π.μ.
Αίθουσα 137.Π39, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Μίνως Γαροφαλάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Περίληψη
Στην εποχή των μεγάλων δεδομένων, τεράστιοι όγκοι δεδομένων δημιουργούνται, αναπαράγονται και μεταφέρονται καθημερινά. Η τρέχουσα τεχνολογία για το χειρισμό και την ανάλυση μεγάλων δεδομένων μας επιτρέπει να αναπτύξουμε εφαρμογές για διάφορα προβλήματα (π.χ. ανάλυση αλληλουχίας DNA, ιατρική απεικόνιση, έλεγχος κυκλοφορίας) που δεν μπορούσαν προηγουμένως να επιλυθούν αποτελεσματικά. Πιο συγκεκριμένα, ο χρόνος που απαιτείται για την ανάλυση μεγάλων όγκων δεδομένων μπορεί να μειωθεί αισθητά, χρησιμοποιώντας κατανεμημένες πλατφόρμες υπολογιστών όπως το Apache Spark. Το Apache Spark framework περιλαμβάνει διάφορες εφαρμογές για μεγάλης κλίμακας μηχανική μάθηση, επεξεργασία κατανεμημένων ροών δεδομένων και ανάλυση γράφων. Η πλατφόρμα Spark Streaming παρέχει κλιμακούμενη και ανεκτική σε σφάλματα επεξεργασία ροών δεδομένων. Ωστόσο, στην πλατφόρμα Spark Streaming υπάρχει διαθέσιμος μόνο ένας περιορισμένος αριθμός εφαρμοσμένων κατανεμημένων αλγορίθμων μηχανικής μάθησης.
Σε αυτή τη διατριβή, προτείνουμε μια παράλληλη εφαρμογή μιας βαθμιαίας και επεκτάσιμης μεθόδου εκμάθησης δέντρων αποφάσεων για ταξινόμηση στο Spark Streaming, το δέντρο απόφασης Hoeffding. Η προτεινόμενη υλοποίησή εκτελεί οριζόντιο παραλληλισμό των δεδομένων στην shared-nothing αρχιτεκτονική του Spark. To Hoeffding bound εγγυάται με μεγάλη σιγουριά ότι το δέντρο απόφασης Hoeffding είναι ασυμπτωτικά ταυτόσημο με ένα batch-learning δέντρο. Τα υψηλών διαστάσεων στατιστικά, που απαιτούνται για την εκπαίδευση του δέντρου, αποθηκεύονται ως αραιοί πίνακες στην κύρια μνήμη σε έναν Spark cluster. Αυτά τα στατιστικά ενημερώνονται άμεσα, όταν υπάρχουν διαθέσιμα νέα δεδομένα εκπαίδευσης. Επιπλέον, πραγματοποιούνται κατανεμημένοι υπολογισμοί προκειμένου να προσδιοριστεί η βέλτιστη διάσπαση ενός κόμβου και να αξιολογηθεί εάν πληρούται το κριτήριο διαχωρισμού. Το παραγόμενο μοντέλο χρησιμοποιείται για ταξινόμηση χρωμάτων βάσει της φασματικής υπογραφής κάθε χρώματος. Κάθε χρώμα έχει διαφορετική χημική σύνθεση και ως εκ τούτου διαφορετική φασματική υπογραφή.
Abstract
In the era of big data, enormous amounts of data are created, replicated and transferred every day. The current technology for handling and analyzing vast amounts of data allows us to develop applications for various problems (e.g., DNA sequence analysis, medical imaging, traffic control) that could not previously be solved efficiently. More precisely, the time required to process large volumes of data can be minimized by using distributed computing platforms such as Apache Spark. The Apache Spark framework includes various implementations for large-scale machine learning, distributed data streaming processing and parallel graph analytics. The Spark Streaming platform provides scalable and fault-tolerant data streaming processing. However, there is only a limited number of implemented distributed incremental machine learning algorithms available in the Spark Streaming platform.
In this thesis, we propose a parallel implementation of an incremental and scalable tree learning method for classification in Spark Streaming, the Hoeffding decision tree. Our proposed implementation performs horizontal data parallelism in the shared-nothing architecture of Spark. The Hoeffding bound guarantees with high confidence that the Hoeffding decision tree is asymptotically identical to a batch-learning one. The high dimensional statistics, required for evaluating splits, are stored as sparse matrices in main memory across the Spark cluster. These statistics are instantly updated, when new training instances are available. Furthermore, distributed computations are performed in order to identify the optimal split and assess whether the splitting criterion is satisfied. The generated model is used in order to make color classification based on the spectral signature of each color. Each color has a different chemical composition, and as a consequence a different spectral signature.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 137Π-39,-38, Πολυτεχνειούπολη
Έναρξη: 17/09/2018 11:00
Λήξη: 17/09/2018 12:00
