Γενετικοί Αλγόριθμοι και Δένδρα Απόφασης στην εκτίμηση της επιτυχίας σε γραπτές εξετάσεις / Μ. Δίγκας
Decision trees are a widespread and easy-to-use way of organizing and displaying knowledge bases for experienced systems. Both in the study and during their use, many interesting theoretical and experimental problems arise. The construction of optimal decision trees is a NP-complete problem and we have considerable mobility in the development of heuristic algorithms to solve it - we usually use heuristics to respond to decent times - but they do not guarantee the optimum solution. The GATree system we use makes decision trees with genetic algorithms and its characteristic advantage is that it produces smaller decision trees than "classical" algorithms for several interesting problems, however it lacks speed. Extending the application to handle a variety of data types effectively involves a good understanding of the already existing implementation as well as robust scientific understanding of the problem. At the same time, we shall explore the possibility of some work being done in a grid environment, utilizing the inherent parallelism of genetic algorithms. The proposed work is part of a research effort aimed at developing libraries for the development of decision trees management algorithms. This dissertation deals with an application that creates decision trees using genetic algorithms. The application is written in C++ utilizing outdated data structure management libraries. The goal is to develop it by integrating numerical data management techniques, evaluate it over widely used datasets, refactor it in a modern programming environment and consider the possibility of turning it into a network service either by usage of distributed computing clusters or a high-performance server (implementation of parallelism).
Τα δέντρα απόφασης είναι ένας διαδομένος και εύχρηστος τρόπος οργάνωσης και απεικόνισης βάσεων γνώσης για έμπειρα συστήματα. Τόσο κατά τη μελέτη όσο και κατά τη χρήση τους προκύπτουν πολλά ενδιαφέροντα θεωρητικά και πειραματικά προβλήματα. Η κατασκευή βέλτιστων δένδρων απόφασης είναι πρόβλημα NP-complete και υπάρχει σημαντική κινητικότητα στην ανάπτυξη ευρετικών αλγορίθμων για τη λύση του - συνήθως χρησιμοποιούμε ευρετικά που δίνουν απάντηση σε «αξιοπρεπείς» χρόνους - αλλά δεν εγγυώνται την βέλτιστη λύση. Το σύστημα GATree που θα χρησιμοποιήσουμε κατασκευάζει δέντρα απόφασης με γενετικούς αλγόριθμους και χαρακτηριστικό του πλεονέκτημα είναι το γεγονός πως παράγει μικρότερα δένδρα απόφασης, σε σχέση με «κλασσικούς» αλγορίθμους για μία σειρά από ενδιαφέροντα προβλήματα. Όμως υστερεί σε ταχύτητα. Η επέκταση της εφαρμογής ώστε να χειρίζεται αποτελεσματικά πληθώρα τύπων δεδομένων άπτεται της καλής κατανόησης της ήδη υπάρχουσας υλοποίησης καθώς και στιβαρής επιστημονικής κατανόησης του προβλήματος. Ταυτόχρονα, θα διερευνηθεί η δυνατότητα κάποιες εργασίες να γίνονται σε περιβάλλον υπολογιστικού πλέγματος (grid), αξιοποιώντας τον εγγενή παραλληλισμό των γενετικών αλγορίθμων. Η προτεινόμενη εργασία εντάσσεται σε μία ερευνητική προσπάθεια με στόχο την ανάπτυξη βιβλιοθηκών για την κατασκευή αλγορίθμων διαχείρισης δέντρων απόφασης. Η εργασία αφορά σε μία εφαρμογή που κατασκευάζει δέντρα απόφασης χρησιμοποιώντας γενετικούς αλγόριθμους. Η εφαρμογή είναι γραμμένη σε C++ αξιοποιώντας παρωχημένες βιβλιοθήκες διαχείρισης δομών δεδομένων. Το ζητούμενο είναι η εξέλιξή της με ενσωμάτωση τεχνικών διαχείρισης αριθμητικών δεδομένων, η αξιολόγησή της πάνω σε ευρέως χρησιμοποιούμενα σύνολα δεδομένων, η μεταγραφή της (σε νέα περιβάλλοντα ανάπτυξης) και η διαθεσιμότητά της είτε δικτυακής υπηρεσίας ή μέσω της χρήσης υπολογισμών πλέγματος ή υπολογιστών υψηλών επιδόσεων (υλοποίηση παραλληλισμού).
Hellenic Open University
Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.
