Μέθοδοι μηχανικής μάθησης για αυτόματη ταξινόμηση κειμένων

Abstract

Applications of machine learning methods to text data present great commercial and research interest due to the high availability of information in unstructured text format. The utilization of machine learning enables the analysis and automated management of large amounts of text. The contribution of this thesis regards three challenging text classification problems: a) text stream classification, b) multilabel text classification and c) text classification in the world wide web. Concerning text stream classification, the problem of the appearance of new predictive features (words) over time is discussed. A computationally efficient approach is presented that combines an incremental feature selection method with a learning algorithm that can operate in a dynamic feature space. The proposed method is incorporated into a personalized news reader. Additionally, the problem of recurring contexts is confronted by exploiting stream clustering in order to dynamically build and update an ensemble of incremental classifiers. To achieve this, a transformation function that maps batches of examples into a new conceptual representation model is proposed. The clustering algorithm is then applied in order to group batches of examples into concepts and identify recurring contexts. The ensemble is produced by creating and maintaining an incremental classifier for every concept discovered in the data stream. Furthermore, two methods are proposed for multilabel text classification that focus on the problem of large number of labels. The first one constructs a hierarchy of multilabel classifiers, each one dealing with a much smaller set of labels and a more balanced example distribution. The second one proposes breaking the initial set of labels into a number of small random subsets, and employing a multilabel classifier for each one. The set of labels can be either disjoint or overlapping, depending on which of two strategies is used to construct them. Empirical evidence indicates that both approaches manage to improve substantially over the base multilabel classifier, especially in domains with large numbers of labels. Additionally the overlapping approach outperforms the disjoint one and exhibits competitive performance against other highperforming multilabel learning methods. Finally, two applications of text classification for the world wide web were studied. In the first one a multilabel classification algorithm is utilized in order to build an automated tag recommender for web bookmarks and bibliographic references. The second one tackles the problem of automated classification of semantic web services according to their application domain. The method represents each web service as a feature vector based on the text and the semantic annotations of the web service description. A number of different representations is proposed. The classification is achieved by applying machine learning algorithms to these representations. An increase in predictive accuracy is obtained by exploiting classifier combination.

Οι εφαρμογές μεθόδων μηχανικής μάθησης σε δεδομένα κειμένου παρουσιάζουν ι- διαίτερο ερευνητικό και εμπορικό ενδιαφέρον εξαιτίας της μεγάλης διαθεσιμότητας πληροφορίας σε μορφή κειμένου. Με τη χρήση της μηχανικής μάθησης είναι εφικτή η ανάλυση μεγάλου αριθμού κειμένων και η αυτόματη διαχείρισή τους. Σημαντικό ενδιαφέρον συγκεντρώνει η διεργασία της ταξινόμησης κειμένων την οποία πραγμα- τεύεται και η παρούσα διατριβή. Συγκεκριμένα, αντιμετωπίζονται τρία σημαντικά προ- ?λήματα της ταξινόμησης κειμένων : α) η ταξινόμηση ?οών κειμένων, ?) η ταξινόμηση κειμένων πολλαπλών ετικετών και γ) η ταξινόμηση κειμένων του παγκόσμιου ιστού. Αρχικά, η διατριβή επικεντρώνεται σε ένα πρόβλημα της ταξινόμησης ?οών κειμέ- νων, την εννοιολογική απόκλιση, και ειδικότερα στην εμφάνιση νέων χαρακτηριστικών με το πέρασμα του χρόνου. Παρουσιάζεται ένα πλαίσιο μάθησης το οποίο συνδυάζει μία επαυξητική μέθοδο επιλογής χαρακτηριστικών με έναν ταξινομητή που μπορεί να λειτουργήσει σε δυναμικούς χώρους χαρακτηριστικών με στόχο την αντιμετώπιση αυτού του προβλήματος. Το προτεινόμενο πλαίσιο εφαρμόζεται σε ένα προσαρμοστικό σύστημα ανάγνωσης ειδήσεων. Επίσης, προτείνεται μία μέθοδος ομάδας ταξινομητών κατά την οποία χρησιμο- ποιείται ένα νέο μοντέλο αναπαράστασης κατάλληλο για προβλήματα ταξινόμησης ?ο- ών δεδομένων που εμπεριέχουν επανεμφανιζόμενες έννοιες. Συγκεκριμένα, η ?οή διαχωρίζεται σε δέσμες δεδομένων οι οποίες μετασχηματίζονται σε διανύσματα που περιγράφουν τις έννοιες που εμπεριέχονται σε αυτά. Στην προκύπτουσα ?οή των διανυσμάτων αυτών εφαρμόζεται ένας αλγόριθμος ομαδοποίησης ?οών με στόχο την οργάνωσή τους σε ομάδες όπου επικρατούν οι ίδιες ή παρόμοιες έννοιες. Απώτερος σκοπός είναι η διατήρηση ενός ταξινομητή για κάθε έννοια της ?οής. Επιπλέον, προτείνονται δύο μέθοδοι για το πρόβλημα της ταξινόμησης πολλαπλών ετικετών με ιδιαίτερη έμφαση σε προβλήματα με μεγάλο αριθμό ετικετών. Η πρώτη, αντιμετωπίζει το πρόβλημα οργανώνοντας τις ετικέτες σε μία ιεραρχία με κύριο πλεονέ- κτημα τους μικρούς χρόνους ταξινόμησης αλλά και την ποιότητα πρόβλεψης. Για την οργάνωση των ετικετών στην ιεραρχία προτάθηκε ένας νέος αλγόριθμος ισορροπημέ- νης ομαδοποίησης. Στη δεύτερη μέθοδο, διασπάται τυχαία το αρχικό σύνολο ετικετών σε υποσύνολα. Σε κάθε ένα από αυτά εφαρμόζεται ένας ξεχωριστός ταξινομητής πολ- λαπλών ετικετών. Τέλος, παρουσιάζονται δύο μέθοδοι ταξινόμησης κειμένων στον παγκόσμιο ιστό. Η πρώτη χρησιμοποιεί έναν ταξινομητή πολλαπλών ετικετών για τη σύσταση λέξεων επισήμανσης σε σύστημα διαμοιρασμού ?ιβλιογραφικών αναφορών και σελιδοδεικτών ιστού. Η δεύτερη αφορά στην αυτόματη ταξινόμηση σημασιολογικών υπηρεσιών ιστού. Προτείνονται μέθοδοι για την αναπαράσταση των περιγραφών των υπηρεσιών ως δια- νύσματα χαρακτηριστικών στα οποία εφαρμόζονται αλγόριθμοι μηχανικής μάθησης. Παρουσιάζονται επίσης δύο μέθοδοι συνδυασμού αυτών των αναπαραστάσεων.