Eureka! Institutional Repository

Οι διαδικασίες κατηγοριοποίησης συναντιούνται σε ένα ευρύ φάσμα των ανθρώπινων δραστηριοτήτων. Με τον όρο κατηγοριοποίηση εννοούμε το να πραγματοποιηθεί μια πρόβλεψη για ένα νέο στιγμιότυπο με βάση τα διαθέσιμα δεδομένα εκπαίδευσης. Στόχος είναι το να δημιουργηθεί ένας κατηγοριοποιητής βάσει ενός συνόλου στιγμιοτύπων εκπαίδευσης ο οποίος θα είναι σε θέση να προβλέψει την κατηγορία ενός νέου στιγμιοτύπου με όσο το δυνατόν μεγαλύτερη ακρίβεια [5]. Σε μεγάλα σύνολα δεδομένων, είναι επιτακτική ανάγκη να μειώσουμε τα αρχικά δεδομένα, ώστε να μειωθεί και ο χρόνος επεξεργασίας ενώ παράλληλα να μην χαθεί πολύτιμη πληροφορία που θα καθιστά τον κατηγοριοποιητή λιγότερο αποτελεσματικό. Με άλλα λόγια, θα πρέπει η διαδικασία της κατηγοριοποίησης να παράγει τα ίδια ή και καλύτερα αποτελέσματα (προβλέψεις) χρησιμοποιώντας το νέο μειωμένο σύνολο δεδομένων σε σχέση με το αρχικό. Υπάρχουν πολλές τεχνικές μείωσης δεδομένων εκπαίδευσης διαθέσιμες στη βιβλιογραφία για προβλήματα κατηγοριοποίησης. Οι τεχνικές αυτές είτε επιλέγουν πρότυπα (αντιπροσωπευτικά στιγμιότυπα) (Prototype Selection) είτε παράγουν πρότυπα συνοψίζοντας παρόμοια στιγμιότυπα (Prototype Generation). Η συντριπτική πλειοψηφία των τεχνικών αυτών αφορά προβλήματα κατηγοριοποίησης μονής κατηγορίας όπου κάθε στιγμιότυπο ανήκει σε μια και μόνο κατηγορία. Ελάχιστες ερευνητικές προσπάθειες έχουν πραγματοποιηθεί που να αφορούν τη μείωση δεδομένων εκπαίδευσης πολλαπλών ετικετών, δηλαδή στιγμιοτύπων που να ανήκουν σε περισσότερες από μια κατηγορίες. Ωστόσο, η απόδοση των τεχνικών μείωσης δεδομένων πολλαπλών ετικετών εξαρτάται σε μεγάλο βαθμό από παραμέτρους που προσδιορίζει ο χρήστης μέσω υπολογιστικά κοστοβόρων διαδικασιών. Επιπρόσθετα, οι τεχνικές μείωσης δεδομένων μονής κατηγορίας δεν μπορούν να εφαρμοστούν σε συνδυασμό με τις διαδεδομένες μεθόδους μετασχηματισμού προβλήματος πολλαπλών ετικετών σε πρόβλημα μονής κατηγορίας. Αυτές οι παρατηρήσεις αποτελούν το κίνητρο της παρούσας διπλωματικής εργασίας. Η παρούσα διπλωματική εργασία συνεισφέρει στην ανάπτυξη νέων τεχνικών μείωσης δεδομένων εκπαίδευσης πολλαπλών ετικετών που δεν περιλαμβάνουν παραμέτρους. Για να επιτευχθεί ο στόχος χρησιμοποιήθηκε η βασική λειτουργία του αλγορίθμου συσταδοποίησης Kmeans ο οποίος όμως εκτελείται επαναληπτικά στις μη ομοιογενείς συστάδες που παράγονται. Στα σύνολα πολλαπλών ετικετών, μια συστάδα θεωρείται ομοιογενής όταν όλα τα στιγμιότυπα της συστάδας έχουν τουλάχιστον μια κοινή ετικέτα. Στο τέλος της επαναληπτικής διαδικασίας συσταδοποίησης όλες οι συστάδες γίνονται ομοιογενείς και τα κέντρα των συστάδων αποτελούν τα πρότυπα που συνθέτουν το μειωμένο σύνολο δεδομένων. Με βάση αυτή τη λειτουργία επαναληπτικής συσταδοποίησης δημιουργήσαμε δυο τεχνικές μείωσης δεδομένων που ανήκουν στην κατηγορία παραγωγής προτύπων. Οι τεχνικές που αναπτύχθηκαν ονομάστηκαν MRHC1 και MRHC2 και παράγουν αντιπροσωπευτικά στιγμιότυπα του αρχικού συνόλου, μειώνοντας έτσι σε μεγάλο βαθμό το αρχικό σύνολο δεδομένων σε προβλήματα πολλαπλών ετικετών. Επίσης, στα πλαίσια της παρούσας διπλωματικής εργασίας αναπτύχθηκαν παραλλαγές του γνωστού αλγορίθμου των Κ πλησιέστερων γειτόνων (KNN). Οι παραλλαγές ονομάστηκαν MKNN1 και MKNN2 και χρησιμοποιήθηκαν για να επιτύχουμε αποτελεσματική κατηγοριοποίηση σε σύνολα δεδομένων πολλαπλών ετικετών που έχουν παραχθεί από τεχνικές μείωσης δεδομένων. Η απόδοση των προτεινόμενων αλγόριθμων ελέγχθηκε εκτελώντας πειράματα σε εννέα σύνολα δεδομένων εκπαίδευσης πολλαπλών ετικετών και για την αξιολόγηση τους μετρή4 θηκε η απώλεια Hamming Loss χρησιμοποιώντας 5fold cross validation. Απο τα αποτελέσματα των πειραμάτων προκύπτει οτι οι προτεινόμενοι αλγόριθμοι επιτυγχάνουν δυο στόχους. Ο πρώτος είναι η σημαντική μείωση του αρχικού συνόλου δεδομένων πολλαπλών ετικετών που ισοδυναμεί με μείωση του χρόνου επεξεργασίας. Ο δεύτερος στόχος που επιτεύχθει είναι η διατήρηση της ακρίβειας (απώλεια Hamming Loss) στα ίδια επίπεδα με αυτή που επιτυγχάνει ο κατηγοριοποιητής που χρησιμοποιεί το αρχικό, μεγάλο σε μέγεθος, σύνολο δεδομένων εκπαίδευσης ενώ σε κάποιες περιπτώσεις παρατηρείται και βελτίωση της ακρίβειας.