Αλγόριθμοι Εξόρυξης Συχνών Συνόλων Αντικειμένων

Abstract

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