Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/0569DC4B-8A26-4026-9964-7F802533074C | ||
| Έτος | 2021 | ||
| Τύπος | Διπλωματική Εργασία | ||
| Άδεια Χρήσης |
|
||
| Βιβλιογραφική Αναφορά | Ιωάννα Κυριακίδου, "Κατανεμημένοι αλγόριθμοι Κ-Μέσων στο σύστημα Spark", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.89431 | ||
| Εμφανίζεται στις Συλλογές |
Ο αλγόριθμος K-means είναι ένας από τους πιο αποτελεσματικούς αλγόριθμους για την ομαδοποίηση (clustering) πολυδιάστατων δεδομένων σε ένα προκαθορισμένο αριθμό ομάδων (clusters). Όταν τα δεδομένα έρχονται σε stream, θέλουμε να υπολογίζουμε με δυναμικό τρόπο τις ομάδες που έχουμε και να τις ενημερώνουμε για κάθε νέα εισαγωγή. Σε αυτή τη διπλωματική εργασία, εφαρμόζουμε μια τεχνική δειγματοληψίας (sampling) χρησιμοποιώντας ως δομή δεδομένων τα Coreset Trees πριν εφαρμόσουμε κάποιον αλγόριθμο προσέγγισης δεδομένων. Τα coresets χρησιμοποιούνται για να δημιουργήσουμε ένα μικρό σταθμισμένο δείγμα από μια ροή δεδομένων. Επιπλέον, όταν χρησιμοποιήσουμε τα coresets ως μια δενδρική δομή καταφέρνουμε να επιταχύνουμε την διαδικασία δημιουργίας μιας σύνοψης των αρχικών δεδομένων. Η χρήση των coresets μας δίνει το πλεονέκτημα να εφαρμόσουμε έναν αλγόριθμο ομαδοποίησης σε ένα πολύ μικρότερο δείγμα και να υπολογίσουμε το αποτέλεσμα του αρχικού stream ταχύτερα. Στο αποτέλεσμα της σύνοψης που δημιουργήσαμε με χρήση των coreset trees εφαρμόζουμε τον k-means αλγόριθμο για να εξάγουμε τα clusters. Αξιολογούμε τον αλγόριθμο ως προς τον βαθμό παραλληλισμού και την ακρίβεια των κέντρων της σύνοψης. Τέλος, καταλήγουμε σε συμπεράσματα για την χρήση των coreset trees ως κατανεμημένη μέθοδο δειγματοληψίας.
Copyright © DIAS 2013
