From Wikipedia, the free encyclopedia
Οι κανόνες συσχέτισης αποτελούν μία από τις σημαντικότερες και νεότερες τεχνικές εξόρυξης γνώσης από μεγάλες βάσεις δεδομένων[1] [2]. Οι πληροφορίες που συγκεντρώνονται παράγουν ενδιαφέρουσες συσχετίσεις και πρότυπα, που βρίσκουν εφαρμογή από τους τομείς της ζωής και της ενασχόλησης του ανθρώπου[1] μέχρι τα τηλεπικοινωνιακά δίκτυα, την αγορά και διαχείριση ρίσκου [2]. Αυτό που έδωσε, όμως μεγάλη ώθηση στους κανόνες συσχέτισης ήταν η ανάγκη κατανόησης και ανάλυσης του καλαθιού αγοράς(market basket analysis).[3]
TID | milk | bread | butter | beer |
---|---|---|---|---|
1 | 1 | 1 | 1 | 0 |
2 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 1 |
4 | 1 | 1 | 1 | 0 |
5 | 1 | 1 | 0 | 0 |
Έστω ένα σύνολο από διακριτά στοιχεία, που αποκαλούνται items (αντικείμενα). Έστω ακόμα ένα σύνολο από δοσοληψίες (transactions), όπου κάθε δοσοληψία είναι ένα σύνολο από αντικείμενα τα οποία ονομάζονται itemset, και όπου ισχύει . Κάθε δοσοληψία ταυτίζεται με ένα μοναδικό αναγνωριστικό που καλείται TID.
Ένας κανόνας είναι μία συσχέτιση της μορφής όπου , και . Το πρώτο μέλος του κανόνα ονομάζεται υπόθεση ενώ το δεύτερο ονομάζεται συμπέρασμα.
Υπάρχουν δύο βασικές μετρικές στον συσχετισμό κανόνων. Η υποστήριξη(support) που σημαίνει ότι ο κανόνας έχει υποστήριξη s,αν το s% των δοσοληψιών στο D περιέχουν το και η εμπιστοσύνη που σημαίνει ότι ο κανόνας ισχύει στο D, αν το c% των δοσοληψιών στο D που περιέχουν το X, περιέχουν επίσης και το Y. Άρα σύμφωνα και με το παράδειγμα του πίνακα η υποστήριξη για το στοιχειοσύνολο(itemset) {Milk, Bread,Butter} θα είναι s({Milk, Bread,Butter}) = 2/5 ενώ η υποστήριξη θα είναι c({Milk, Bread,Butter}) = 2/3.
Από τα παραπάνω προκύπτει ότι ο κανόνας έχει υποστήριξη s, όταν και εμπιστοσύνη c, όταν .
Προκειμένου να εξάγουμε έναν κανόνα συσχέτισης, πρέπει να ικανοποιούνται κάποια κατώτατα όρια τόσο για την υποστήριξη όσο και για την εμπιστοσύνη. Ο κανόνας πρέπει να έχει υποστήριξη μεγαλύτερη από το όριο, που ονομάζεται ελάχιστη υποστήριξηminsup), και η εμπιστοσύνη πρέπει να είναι μεγαλύτερη από το όριο, που ονομάζεται ελάχιστη εμπιστοσύνη(minconf). Αυτοί οι δύο παράγοντες καθορίζουν τον αριθμό των κανόνων που θα προκύψουν και άρα πρέπει να επιλέγονται με τον τύπο του πίνακα δοσοληψιών. Τα στοιχειοσύνολα(itemsets) που έχουν υποστήριξη μεγαλύτερη από το minsup καλούνται συχνά ή μεγάλα.
Τα στάδια ανάπτυξης των Κανόνων Συσχέτισης είναι τα εξής:
Εφαρμόζοντας τα δύο παραπάνω, μπορούμε να εκτιμήσουμε για το αν ο κανόνας έχει ενδιαφέρον ή όχι. Η επίλυση του δεύτερου βήματος είναι απλή. Για κάθε ένα από τα συχνά στοιχειοσύνολα , βρες όλα τα μη κενά υποσύνολά του. Για κάθε τέτοιο υποσύνολο , παρουσίασε τον κανόνα , αν ο λόγος sup(l)/sup(a), που αντιστοιχεί στην εμπιστοσύνη του κανόνα είναι τουλάχιστον minconf.
Η δυσκολία και η προσοχή των ερευνητών έχει επικεντρωθεί στο πρώτο βήμα, όπου έχουν παρουσιαστεί διάφοροι αλγόριθμοι για την επίλυση του. Ο σημαντικότερος από αυτούς είναι ο αλγόριθμος Apriori.
Ο τρόπος λειτουργίας του αλγόριθμου σε γενικές γραμμές έχει ως εξής:[1] [4]
Σε πρώτη φάση, γίνεται το πέρασμα(διάβασμα) του πίνακα D. Κατά το πρώτο πέρασμα μετριέται η υποστήριξη των 1-itemsets και υπολογίζεται ποια από αυτά ικανοποιούν την συνθήκη της ελάχιστης υποστήριξης. Σε κάθε επόμενη φάση υπολογίζονται τα καινούρια itemsets που στηρίζονται στα προηγούμενα. Τα itemsets που προκύπτουν ονομάζονται υποψήφια (candidate itemsets), επειδή δεν γνωρίζουμε την υποστήριξη και κατά συνέπεια αν είναι συχνά(frequent). Αυτός είναι ο λόγος που βρίσκεται η υποστήριξή τους μέσω ενός περάσματος από τον αρχικό πίνακα. Το πλεονέκτημα αυτού του αλγορίθμου είναι ότι σε κάθε φάση γίνεται ένα μόνο πέρασμα από τον αρχικό πίνακα. Η διάκριση για το ποια itemsets είναι συχνά γίνεται στο τέλος, ώστε να χρησιμοποιηθούν στην επόμενη φάση.
Άλλοι αλγόριθμοι για την εύρεση συχνών itemsets είναι ο Partition, ο FP-Growth, και ο Eclat.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.