Μανθάνοντα συστήματα ταξινομητών για εποπτευόμενα προβλήματα κατηγοριοποίησης

Abstract

Learning Classifier Systems (LCS) belong to a class of Genetics-Based Machine Learning (GBML) systems, designed to work for both sequential and single-step problems. Although modern research in the LCS field has mainly focused on the case of sequential decision problems, during the 15 years, there has been a shift of interest toward applying LCS to single-step decision tasks, such as predictive Data Mining (DM), which has come to be considered one of the most important application domains for this class of systems. At the same time, while developments in the LCS research field have led to the maturity of associated technologies and promising implementations of new systems, it is clear that DM applications have not yet fully exploited the potential of LCS. The present thesis aims at addressing the corresponding challenges through a fruitful merging of both research areas, LCS and DM, especially focusing on the study of strength-based fitness in LCS. In this direction, the thesis presents a generalized supervised learning framework based on LCS (*S-LCS), independent of the employed fitness calculation schema, that is later equipped with a set of extensions to the traditional strength-based LCS framework, thus defining the SS-LCS algorithm. The behavior and performance of SS-LCS is studied in depth and compared to this of accuracy-based approaches, especially focusing on problems with extreme class imbalances. This study contributes to a better understanding of the learning dynamics involved in single-step classification problems and reveals the potential of supervised LCS in general, and strength-based ones more specifically, as real-world DM tools inducing tractable rule-based classification models, even in the presence of highly skewed class distributions. The present thesis also specifies and implements a general-use initialization component for the class of supervised LCS algorithms that extracts information about the structure of studied problems through a pre-training clustering phase and exploits this information by transforming it into rules suitable for the initialization of the learning process. The potential and robustness of our proposed approach are experimentally evaluated, revealing that it can lead to a significant improvement of the studied supervised LCS’ predictive and expressive abilities, as well as the required times for their training. In the last part of the thesis, we integrate the findings of all previous steps and, with the ultimate goal of revealing LCS potential for effective classification in real-world applications domains, we address the problems of: (a) predicting sparse episodes in environmental datasets and (b) multi-label classification. In both cases, it is experimentally proven that the proposed LCS approach presents clear advantages over conventional approaches, in terms of the predictive accuracy and understandability of the evolved knowledge representations.

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