Έμβλημα Πολυτεχνείου Κρήτης
Το Πολυτεχνείο Κρήτης στο Facebook  Το Πολυτεχνείο Κρήτης στο Instagram  Το Πολυτεχνείο Κρήτης στο Twitter  Το Πολυτεχνείο Κρήτης στο YouTube   Το Πολυτεχνείο Κρήτης στο Linkedin
Προβολή ημερολογίου Προβολή ημερολογίου
Προβολή λίστας Προβολή λίστας
iCal - Εκδηλώσεις μήνα iCal - Εκδηλώσεις μήνα
iCal - Εκδηλώσεις 6 μηνών iCal - Εκδηλώσεις 6 μηνών
RSS - Εκδηλώσεις μήνα RSS - Εκδηλώσεις μήνα
RSS - Εκδηλώσεις 6 μηνών RSS - Εκδηλώσεις 6 μηνών

14
Ιουν

Παρουσίαση Διπλωματικής Εργασίας κας Κυριακίδου Ιωάννας- Σχολή ΗΜΜΥ
Κατηγορία: Παρουσίαση Διπλωματικής Εργασίας  
ΤοποθεσίαΗ παρουσίαση θα γίνει με τηλεδιάσκεψη
Ώρα14/06/2021 09:00 - 10:00

Περιγραφή:

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

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

θέμα
Κατανεμημένοι Αλγόριθμοι κ-Μέσων στο Σύστημα Spark
Distributed k-Means Streaming Algorithms in Spark

Εξεταστική Επιτροπή
Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης

Περίληψη
Ο αλγόριθμος K-means είναι ένας από τους πιο αποτελεσματικούς αλγόριθμους για την ομαδοποίηση (clustering) πολυδιάστατων δεδομένων σε ένα προκαθορισμένο αριθμό ομάδων (clusters). Όταν τα δεδομένα έρχονται σε stream, θέλουμε να υπολογίζουμε με δυναμικό τρόπο τις ομάδες που έχουμε και να τις ενημερώνουμε για κάθε νέα εισαγωγή. Σε αυτή τη διπλωματική εργασία, εφαρμόζουμε μια τεχνική δειγματοληψίας (sampling) χρησιμοποιώντας ως δομή δεδομένων τα Coreset Trees πριν εφαρμόσουμε κάποιον αλγόριθμο προσέγγισης δεδομένων. Τα coresets χρησιμοποιούνται για να δημιουργήσουμε ένα μικρό σταθμισμένο δείγμα από μια ροή δεδομένων. Επιπλέον, όταν χρησιμοποιήσουμε τα coresets ως μια δενδρική δομή καταφέρνουμε να επιταχύνουμε την διαδικασία δημιουργίας μιας σύνοψης των αρχικών δεδομένων. Η χρήση των coresets μας δίνει το πλεονέκτημα να εφαρμόσουμε έναν αλγόριθμο ομαδοποίησης σε ένα πολύ μικρότερο δείγμα και να υπολογίσουμε το αποτέλεσμα του αρχικού stream ταχύτερα. Στο αποτέλεσμα της σύνοψης που δημιουργήσαμε με χρήση των coreset trees εφαρμόζουμε τον k-means αλγόριθμο για να εξάγουμε τα clusters. Αξιολογούμε τον αλγόριθμο ως προς τον βαθμό παραλληλισμού και την ακρίβεια των κέντρων της σύνοψης. Τέλος, καταλήγουμε σε συμπεράσματα για την χρήση των coreset trees ως κατανεμημένη μέθοδο δειγματοληψίας.

Abstract
K-means is one of the most commonly used clustering algorithms that clusters the multi-dimensional data points into a predefined number of clusters. When data arrives in a stream, there is a need to estimate clusters dynamically, updating them on arrival. In this thesis, we will apply a sampling technique using a data structure called coreset trees, before any approximation algorithm is applied. Coresets are used to obtain a small weighted sample from the data stream. Using coresets in a tree-like form we successfully speed up the process of computing a summary of the original data. The advantage of such a coreset is that we can apply any clustering algorithm on a much smaller sample to compute a solution for the original dataset faster. In the second step, we are using a StreamKM++ to estimate the cluster centres of the summary. We evaluate the algorithm on how the parallelism level impacts the time needed to extract the clusters, finally we compare the consistency within clusters of data conclusions about the usage of coreset trees as a distributed sampling method.

 

Meeting ID: 842 0332 4168
Password: 221573

Προσθήκη στο ημερολόγιό μου
© Πολυτεχνείο Κρήτης 2012