Συγγραφέας: Ντάλλα Μιρέλα
Λέξεις Κλειδιά: Εξόρυξη δεδομένων, Επαγωγικός λογικός προγραμματισμός

Σύνοψη: Η παρούσα εργασία έχει ως στόχο να παρουσιάσει έναν παράλληλο αλγόριθμο Εξόρυξης δεδομένων που μπορεί να εφαρμοστεί σε μεγάλες βάσεις δεδομένων με χρήση Επαγωγικού Λογικού Προγραμματισμού. Η κεντρική υπόθεση αυτής της εργασίας είναι πως είναι απαραίτητο αλλά και δυνατό να υιοθετηθούν παράλληλοι αλγόριθμοι στη διαδικασία της Εξόρυξης δεδομένων. Αποδεικνύεται ότι ο παραλληλισμός μπορεί να εφαρμοστεί αποδοτικά στον Επαγωγικό Λογικό Προγραμματισμό (Inductive Logic Programming - ILP). Η ολοκληρωμένη αναπαράσταση της γνώσης και η εξαιρετική ενσωμάτωση της υποκείμενης γνώσης του ILP αποδεικνύεται πολύ σημαντική μεταξύ των αλγορίθμων Εξόρυξης δεδομένων. Το Κεφάλαιο 1 αποτελεί μια εισαγωγή στην εξόρυξη δεδομένων. Παρουσιάζονται οι βασικές εργασίες που λαμβάνουν χώρα κατά την εξόρυξη δεδομένων καθώς και μερικοί από τους συνηθισμένους αλγορίθμους εξόρυξης δεδομένων. Στη συνέχεια, γίνεται μια εισαγωγή στη σχεσιακή εξόρυξη δεδομένων και δίνονται τα βασικά χαρακτηριστικά αλγορίθμων σχεσιακής εξόρυξης δεδομένων. Το Κεφάλαιο 2 αυτής της διπλωματικής εργασίας παρουσιάζει τη θεωρία του Eπαγωγικού Λογικού Προγραμματισμού (ΕΠΛ - ILP), μερικές δημοφιλείς μεθόδους ILP καθώς και τον τρόπο με τον οποίο εφαρμόζεται ο ILP για να επιλύσει προβλήματα που συναντώνται σε συστήματα βάσεων δεδομένων Παρουσιάζεται αναλυτικά μια συγκεκριμένη προσέγγιση στον ILP – η Mode Directed Inverse Entailment [60], καθώς αποτελεί τη βάση για την παράλληλη έκδοση της Progol που θα παρουσιαστεί σε επόμενο κεφάλαιο. Το Κεφάλαιο 3 είναι αφιερωμένο στην παρουσίαση διαφόρων συστημάτων ILP και την εφαρμογή τους στην Εξόρυξη δεδομένων. Στη συνέχεια του κεφαλαίου παρουσιάζεται ένας σειριακός αλγόριθμος ILP Εξόρυξης δεδομένων και η ανάλυση κόστους του. Γίνεται μια εισαγωγή στο Bulk Synchronous Parallelism (BSP) [46]. Το Κεφάλαιο 4, είναι μια σύνοψη της παράλληλης Επαγωγικής Λογικής. Στην αρχή αναφέρονται οι βασικές αρχές του παράλληλου επαγωγικού μοντέλου και στη συνέχεια ακολουθεί μια λεπτομερής περιγραφή. Εμφανίζονται τα προβλήματα μιας τέτοιας προσέγγισης και παρουσιάζεται μια ανάλυση κόστους. Τμήμα του Κεφαλαίου 4 είναι αφιερωμένο σε έναν παράλληλο αλγόριθμο ILP που χρησιμοποιεί το μοντέλο BSP. Για να υποστηριχθεί ο παράλληλος αλγόριθμος του Κεφαλαίου 4, το Κεφάλαιο 5 παρουσιάζει μερικά βασικά χαρακτηριστικά ενός παράλληλου συστήματος ILP – της παράλληλης Progol. Το σύστημα αυτό δημιουργήθηκε με βάση το μοντέλο BSP και βασίζεται στην Progol που υλοποιήθηκε (σε γλώσσα C) από το Muggleton. Παρέχονται πολλά παραδείγματα και επεξηγείται το φαινόμενο της υπεργραμμικής επιτάχυνσης (super-linear speedup). Στο Κεφάλαιο 6 έχουν συμπεριληφθεί τα αποτελέσματα των δοκιμών του αλγορίθμου του Κεφαλαίου 4 σε τρεις διαφορετικές περιπτώσεις προβλημάτων, στην ταξινόμηση των ζώων, στην εκμάθηση των κανόνων του σκάκι και στο πρόβλημα τερματισμού σε μια παρτίδα σκάκι. Το Κεφάλαιο 7 συνοψίζει τα αποτελέσματα της μεταπτυχιακής εργασίας.

Αρχείο Διπλωματικής Εργασίας