Κανόνες συσχετίσεων και Εύρεση συχνών στοιχειοσυνόλων από βάσεις δεδομένων συναλλαγών με τον αλγόριθμο Apriori για εφαρμογές data mining

Abstract

Ο όρος data mining χρησιμοποιείται για να περιγράψει την εξόρυξη γνώσης από μεγάλες βάσεις δεδομένων, δηλαδή τις διαδικασίες ανακάλυψης χρήσιμων προτύπων και καλά κρυμμένων πληροφοριών από τα δεδομένα με χρήση αλγορίθμων. Η ανάλυση κανόνων συσχετίσεων (association rules), αναφέρεται στην διαδικασία εκείνη της εξαγωγής γνώσης από βάσεις δεδομένων που αποκαλύπτει συγκεκριμένο τρόπο με τον οποίο τα δεδομένα είναι δυνατόν να συνδέονται. Το ευρύτερα γνωστό παράδειγμα αυτού του είδους τις εφαρμογής είναι ο προσδιορισμός κανόνων συσχέτισης από την ανάλυση του καλαθιού αγοράς (market basket analysis) ή δεδομένων συναλλαγών. Για παράδειγμα ο κανόνας Α⇒{Β, Γ} δηλαδή οι πελάτες που αγοράζουν το προϊόν Α, αγοράζουν ταυτόχρονα και τα προϊόντα Β και Γ είναι ένας κανόνας συσχέτισης. Εδώ τα δεδομένα που αναλύονται αποτελούνται από πληροφορίες σχετικές με τα προϊόντα που αγοράζουν οι πελάτες, δηλαδή τις συναλλαγές τους. Η ανάλυση κανόνων συσχετίσεων είναι ένα ενεργό πεδίο έρευνας και εκτός από το market basket analysis, χρησιμοποιείται σε πληθώρα άλλων εφαρμογών, από το Web usage mining, τη συσχέτιση υπόπτων εγκληματικών ενεργειών, την πρόβλεψη αποτυχίας της λειτουργίας τηλεπικοινωνιακών διακόπτων, το intrusion detection καθώς και σε άλλες τεχνικές όπως graph mining, clustering with links, και bioinformatics. Η κύρια προσέγγιση για την ανάλυση κανόνων συσχέτισης είναι η διάσπαση του προβλήματος σε δύο μέρη: πρώτον την εύρεση συχνών στοιχειοσυνόλων (frequent itemsets) ο αριθμός συχνότητας εμφάνισης των οποίων είναι πάνω από ένα κατώφλι και δεύτερον τη δημιουργία κανόνων συσχέτισης από αυτά. Ο αλγόριθμος Apriori είναι ο γνωστότερος αλγόριθμος εύρεσης συχνών στοιχειοσυνόλων και εξαγωγής συσχετίσεων από αυτά. Σε κάθε σάρωση των δεδομένων δημιουργεί τα υποψήφια στοιχειοσύνολα και εξετάζει τη συχνότητά τους. Επιλέγοντας τα συχνότερα, όπως τα {A,C,D} και {A,B} υπολογίζει την εμπιστοσύνη και παράγει τους κανόνες συσχετίσεων A ⇒{C,D} και Α⇒Β. Η παρούσα μελέτη αποσκοπεί στην κατανόηση του αλγόριθμου apriori και την υλοποίηση του σε περιβάλλον προγραμματισμού Borland C++ Builder. Ως εφαρμογή του αλγορίθμου αυτού θα γίνει προσδιορισμός κανόνων συσχέτισης από την ανάλυση του καλαθιού αγοράς.