Συσταδοποίηση με την γλώσσα R (Bachelor thesis)

Νέϊκος, Αναστάσιος


Η ανάλυση συστάδων ομαδοποιεί αντικείμενα των δεδομένων χρησιμοποιώντας ως μοναδικό μέσο, τη πληροφορία που παρέχουν τα ίδια τα δεδομένα. Ο στόχος της είναι η ομαδοποίηση αυτή να γίνει με έναν τέτοιο τρόπο, ώστε αντικείμενα της ίδια ομάδας, που αποκαλεί συστάδα, να είναι όμοια μεταξύ τους και παράλληλα διαφορετικά από αντικείμενα άλλων συστάδων. Με βάση τις σχέσεις που έχουν μεταξύ τους τα αντικείμενα, ορίστηκαν τύποι συσταδοποίησης, οι οποίοι επιχειρούν να δώσουν έμφαση σε διαφορετική πτυχή των σχέσεων αυτών. Εφαρμόζοντας τεχνικές συσταδοποίησης στη πράξη, προέκυψαν και διάφοροι τύποι συστάδων. Τα βήματα για την ανάλυση συστάδων είναι η προετοιμασία των δεδομένων, η επιλογή του μέτρου ομοιότητας ή απόστασης μεταξύ των αντικειμένων, η επιλογή της μεθόδου συσταδοποίησης και η αξιολόγηση της συσταδοποίησης. Έγινε η περιγραφή των σημαντικότερων μέτρων απόστασης και παράλληλα δόθηκε η ευκαιρία ορισμού δύο γνωστών διαδικασιών μετασχηματισμού στο πλαίσιο της προετοιμασίας των δεδομένων. Στην συνέχεια ακολουθώντας την προσέγγιση ιεραρχικών και διαιρετικών μεθόδων συσταδοποίησης, περιγράψαμε διάφορα μέτρα διασύνδεσης ιεραρχικών συστάδων και επιλέχθηκε ο αλγόριθμος CURE για περαιτέρω ανάλυση. Αυτός, διατηρώντας τα πλεονεκτήματα του μέτρου διασύνδεσής single link αποφεύγει τα μειονεκτήματα της χρήσης του. Από την πλευρά των διαιρετικών μεθόδων συσταδοποίησης έγινε ανάλυση του αλγόριθμου K-means και αναζητήθηκαν τεχνικές και παραλλαγές του για την αντιμετώπιση των αδυναμιών του. Αναλύθηκαν τεχνικές αρχικοποίησης των κέντρων του και μέθοδοι εντοπισμού του κατάλληλου αριθμού συστάδων. Στο πλαίσιο του δεύτερου δόθηκαν μερικά από τα μέτρα εγκυρότητας συσταδοποίησης με kmeans. Το πρώτο μέτρο και το οποίο είναι το πιο διαδεδομένο υπολογίζει τη συνολική συνοχή της συσταδοποίησης βάση της διασποράς όλων των δεδομένων, ενώ τη συνολική διαφοροποίηση βάση της διασποράς των κέντρων των συστάδων. Τα υπόλοιπα που περιγράφονται είναι επίσης χαρακτηριστικά μέτρα εγκυρότητας που μπορούν να χρησιμοποιηθούν για τον K means. Επίσης περιγράφονται οι αλγόριθμοι PAM, CLARA, CLARANS οι οποίοι χρησιμοποιούν τα medoids αντί των μέσων ως πρωτότυπα συστάδων. Τέλος παρουσιάζεται ο αλγόριθμος DBSCAN ο οποίος είναι μια μέθοδος συσταδοποίησης βάση πυκνότητας. Ο τελευταίος δεν αποτελεί χαρακτηριστική περίπτωση βάση κατάτμησης δεδομένου ότι στην τελική συσταδοποίηση δεν συμμετέχουν όλα τα δεδομένα. Τέλος δίνεται μια κατηγοριοποίηση των μέτρων εγκυρότητας ανεξαρτήτως μεθόδου συσταδοποίησης. Στο δεύτερο κεφάλαιο παρουσιάζονται τα χαρακτηριστικά της γλώσσας R. Περιγράφονται τα βασικά της αντικείμενα καθώς και η λειτουργικότητά της. Στο δεύτερο τμήμα του κεφαλαίου περιγράφονται οι δυνατότητες μεθόδων συσταδοποίησης που προσφέρει η R και παράλληλα αναλύονται μερικά από τα βασικότερα πακέτα που αφορούν μεθόδους ιεραρχικής συσταδοποίησης και την εφαρμογή του αλγόριθμου K-means. Τέλος στο τρίτο κεφάλαιο αποτελεί μια μελέτη περίπτωσης μείωσης δεδομένων μέσω μεθόδου DRT η οποία χρησιμοποιεί τον K-means για το σκοπό αυτό. Συγκεκριμένα μελετά την επίδοση της τεχνικής RHC σε ένα σύνολο δεκατεσσάρων datasets.
Institution and School/Department of submitter: Σχολή Μηχανικών / Τμήμα πληροφορικής και ηλεκτρονικών συστημάτων
Subject classification: Ανάλυση συστάδων -- Προγράμματα υπολογιστών
Cluster analysis -- Computer programs
R (Γλώσσα προγραμματισμού υπολογιστή)
R (Computer program language)
Ανάλυση συστάδων
Cluster analysis
Keywords: Ανάλυση συστάδων;Γλώσσα προγραμματισμού R;Cluster analysis;R computer program language
Description: Μεταπτυχιακή διατριβή - Σχολή μηχανικών - Τμήμα μηχανικών πληροφορικής και ηλεκτρονικών συστημάτων , 2016 α.α 7458
URI: http://195.251.240.227/jspui/handle/123456789/14455
Item type: bachelorThesis
General Description / Additional Comments: Μεταπτυχιακή διατριβή
Subject classification: Ανάλυση συστάδων -- Προγράμματα υπολογιστών
Cluster analysis -- Computer programs
R (Γλώσσα προγραμματισμού υπολογιστή)
R (Computer program language)
Ανάλυση συστάδων
Cluster analysis
Item language: el
Item access scheme: account
Institution and School/Department of submitter: Σχολή Μηχανικών / Τμήμα πληροφορικής και ηλεκτρονικών συστημάτων
Publication date: 2016-02-17
Bibliographic citation: Νέϊκος, Α. (2016). Συσταδοποίηση με την γλώσσα R. Θεσσαλονίκη: Διεθνές Πανεπιστήμιο Ελλάδος.
Abstract: Η ανάλυση συστάδων ομαδοποιεί αντικείμενα των δεδομένων χρησιμοποιώντας ως μοναδικό μέσο, τη πληροφορία που παρέχουν τα ίδια τα δεδομένα. Ο στόχος της είναι η ομαδοποίηση αυτή να γίνει με έναν τέτοιο τρόπο, ώστε αντικείμενα της ίδια ομάδας, που αποκαλεί συστάδα, να είναι όμοια μεταξύ τους και παράλληλα διαφορετικά από αντικείμενα άλλων συστάδων. Με βάση τις σχέσεις που έχουν μεταξύ τους τα αντικείμενα, ορίστηκαν τύποι συσταδοποίησης, οι οποίοι επιχειρούν να δώσουν έμφαση σε διαφορετική πτυχή των σχέσεων αυτών. Εφαρμόζοντας τεχνικές συσταδοποίησης στη πράξη, προέκυψαν και διάφοροι τύποι συστάδων. Τα βήματα για την ανάλυση συστάδων είναι η προετοιμασία των δεδομένων, η επιλογή του μέτρου ομοιότητας ή απόστασης μεταξύ των αντικειμένων, η επιλογή της μεθόδου συσταδοποίησης και η αξιολόγηση της συσταδοποίησης. Έγινε η περιγραφή των σημαντικότερων μέτρων απόστασης και παράλληλα δόθηκε η ευκαιρία ορισμού δύο γνωστών διαδικασιών μετασχηματισμού στο πλαίσιο της προετοιμασίας των δεδομένων. Στην συνέχεια ακολουθώντας την προσέγγιση ιεραρχικών και διαιρετικών μεθόδων συσταδοποίησης, περιγράψαμε διάφορα μέτρα διασύνδεσης ιεραρχικών συστάδων και επιλέχθηκε ο αλγόριθμος CURE για περαιτέρω ανάλυση. Αυτός, διατηρώντας τα πλεονεκτήματα του μέτρου διασύνδεσής single link αποφεύγει τα μειονεκτήματα της χρήσης του. Από την πλευρά των διαιρετικών μεθόδων συσταδοποίησης έγινε ανάλυση του αλγόριθμου K-means και αναζητήθηκαν τεχνικές και παραλλαγές του για την αντιμετώπιση των αδυναμιών του. Αναλύθηκαν τεχνικές αρχικοποίησης των κέντρων του και μέθοδοι εντοπισμού του κατάλληλου αριθμού συστάδων. Στο πλαίσιο του δεύτερου δόθηκαν μερικά από τα μέτρα εγκυρότητας συσταδοποίησης με kmeans. Το πρώτο μέτρο και το οποίο είναι το πιο διαδεδομένο υπολογίζει τη συνολική συνοχή της συσταδοποίησης βάση της διασποράς όλων των δεδομένων, ενώ τη συνολική διαφοροποίηση βάση της διασποράς των κέντρων των συστάδων. Τα υπόλοιπα που περιγράφονται είναι επίσης χαρακτηριστικά μέτρα εγκυρότητας που μπορούν να χρησιμοποιηθούν για τον K means. Επίσης περιγράφονται οι αλγόριθμοι PAM, CLARA, CLARANS οι οποίοι χρησιμοποιούν τα medoids αντί των μέσων ως πρωτότυπα συστάδων. Τέλος παρουσιάζεται ο αλγόριθμος DBSCAN ο οποίος είναι μια μέθοδος συσταδοποίησης βάση πυκνότητας. Ο τελευταίος δεν αποτελεί χαρακτηριστική περίπτωση βάση κατάτμησης δεδομένου ότι στην τελική συσταδοποίηση δεν συμμετέχουν όλα τα δεδομένα. Τέλος δίνεται μια κατηγοριοποίηση των μέτρων εγκυρότητας ανεξαρτήτως μεθόδου συσταδοποίησης. Στο δεύτερο κεφάλαιο παρουσιάζονται τα χαρακτηριστικά της γλώσσας R. Περιγράφονται τα βασικά της αντικείμενα καθώς και η λειτουργικότητά της. Στο δεύτερο τμήμα του κεφαλαίου περιγράφονται οι δυνατότητες μεθόδων συσταδοποίησης που προσφέρει η R και παράλληλα αναλύονται μερικά από τα βασικότερα πακέτα που αφορούν μεθόδους ιεραρχικής συσταδοποίησης και την εφαρμογή του αλγόριθμου K-means. Τέλος στο τρίτο κεφάλαιο αποτελεί μια μελέτη περίπτωσης μείωσης δεδομένων μέσω μεθόδου DRT η οποία χρησιμοποιεί τον K-means για το σκοπό αυτό. Συγκεκριμένα μελετά την επίδοση της τεχνικής RHC σε ένα σύνολο δεκατεσσάρων datasets.
Table of contents: 1. Εισαγωγή στην Ανάλυση Συστάδων.................................................................................. 5 1.1 Τι είναι ανάλυση συστάδων ............................................................................................ 5 1.2 Τύποι συσταδοποίησης.................................................................................................... 7 1.3 Τύποι συστάδων .............................................................................................................. 8 1.4 Βήματα ανάλυσης συστάδων ........................................................................................ 10 1.5 Μέτρα απόστασης, συναρτήσεις ομοιότητας................................................................ 11 1.5.1 Μέτρα απόστασης-ανομοιότητας........................................................................... 11 1.5.2 Μέτρα ανομοιότητας δυαδικών χαρακτηριστικών................................................. 12 1.5.3 Μέτρα ανομοιότητας κατηγορικών χαρακτηριστικών χωρίς διάταξη.................... 13 1.5.4 Μέτρο ανομοιότητας-απόστασης κατηγορικών χαρακτηριστικών με διάταξη...... 13 1.5.5 Μετρικές απόστασης χαρακτηριστικών μεικτών τύπων ........................................ 14 1.5.6 Συναρτήσεις ομοιότητας......................................................................................... 15 1.6 Επιλογή μεθόδου συσταδοποίησης.................................................................................. 16 1.6.1 Ιεραρχικοί μέθοδοι ................................................................................................. 17 1.6.2 Μέθοδοι κατάτμησης.............................................................................................. 21 1.6.3 Kmeans................................................................................................................... 22 1.6.4 Eκ των υστέρων τεχνικές........................................................................................ 29 1.6.5 Διαχείριση έκτοπων και ποιοτικών χαρακτηριστικών ........................................... 33 1.6.6 Αλγόριθμοι βάσει πυκνότητας................................................................................ 36 1.6.7 Εγκυρότητα συσταδοποίησης................................................................................. 39 2. Η Γλώσσα R....................................................................................................................... 41 2.1 Εισαγωγή....................................................................................................................... 41 2.2 Τύποι δεδομένων στην R............................................................................................... 41 2.2.1 Διανύσματα ............................................................................................................ 42 2.2.2 Vectorization .......................................................................................................... 44 2.2.3 Factors.................................................................................................................... 45 2.2.4 Aκολουθίες............................................................................................................. 46 2.2.5 Προσπέλαση διανυσμάτων..................................................................................... 47 2.2.6 Πίνακες................................................................................................................... 49 2.2.7 Λίστες..................................................................................................................... 50 2.2.8 Data frames............................................................................................................. 51 2.2.9 Συναρτήσεις............................................................................................................ 53 2.3 Συσταδοποίηση με την R............................................................................................... 56 2.3.1 Μέθοδοι ιεραρχικής συσταδοποίησης.................................................................... 57 2.3.2 Μέθοδοι κατάτμησης.............................................................................................. 69 2.3.3 Η συνάρτηση kmeans............................................................................................. 69 2.3.4 Παρατηρήσεις......................................................................................................... 73 2.3.5 Παράδειγμα ............................................................................................................ 73 2.4 Κατηγοριοποίηση με την R........................................................................................... 82 2.4.1 Ο αλγόριθμος knn................................................................................................... 82 2.4.2 Παρατηρήσεις......................................................................................................... 84 3. Μελέτη Περίπτωσης - Εφαρμογή του Αλγόριθμου Μείωσης Δεδομένων RHC.......... 86 3.1 Εισαγωγή....................................................................................................................... 86 3.2 Περιγραφή της μεθόδου RHC (Reduction through Homogeneous Clusters)............... 88 3.3 Περιγραφή των δεδομένων............................................................................................ 90 3.4 Ανάγνωση & διερεύνηση των keel datasets στην R..................................................... 94 3.5 Μεθοδολογία διεξαγωγής πειραμάτων - Αποτελέσματα............................................... 99
Advisor name: Καραμητρόπουλος, Λεωνίδας
Examining committee: Καραμητρόπουλος, Λεωνίδας
Publishing department/division: Σχολή Μηχανικών / Τμήμα μηχανικών πληροφορικής και ηλεκτρονικών συστημάτων
Publishing institution: ihu
Number of pages: 99
Appears in Collections:Μεταπτυχιακές Διατριβές

Files in This Item:
There are no files associated with this item.



 Please use this identifier to cite or link to this item:
http://195.251.240.227/jspui/handle/123456789/14455
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.