Κανόνες συσχέτισης

Οι κανόνες συσχέτισης αποτελούν μία από τις σημαντικότερες και νεότερες τεχνικές εξόρυξης γνώσης από μεγάλες βάσεις δεδομένων . Οι πληροφορίες που συγκεντρώνονται παράγουν ενδιαφέρουσες συσχετίσεις και πρότυπα, που βρίσκουν εφαρμογή από τους τομείς της ζωής και της ενασχόλησης του ανθρώπου μέχρι τα τηλεπικοινωνιακά δίκτυα, την αγορά και διαχείριση ρίσκου . Αυτό που έδωσε, όμως μεγάλη ώθηση στους κανόνες συσχέτισης ήταν η ανάγκη κατανόησης και ανάλυσης του καλαθιού αγοράς(market basket analysis).

Ορισμός

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

Έστω $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ ένα σύνολο από διακριτά στοιχεία, που αποκαλούνται items (αντικείμενα). Έστω ακόμα $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ ένα σύνολο από δοσοληψίες (transactions), όπου κάθε δοσοληψία $T$ είναι ένα σύνολο από αντικείμενα τα οποία ονομάζονται itemset, και όπου ισχύει $T\subseteq I$. Κάθε δοσοληψία ταυτίζεται με ένα μοναδικό αναγνωριστικό που καλείται TID.

Ένας κανόνας είναι μία συσχέτιση της μορφής $X\Rightarrow Y$ όπου $X\subseteq I$, $Y\subseteq I$ και $X\cap Y=\emptyset$. Το πρώτο μέλος του κανόνα ονομάζεται υπόθεση ενώ το δεύτερο ονομάζεται συμπέρασμα.

Υπάρχουν δύο βασικές μετρικές στον συσχετισμό κανόνων. Η υποστήριξη(support) που σημαίνει ότι ο κανόνας $X\Rightarrow Y$ έχει υποστήριξη s,αν το s% των δοσοληψιών στο D περιέχουν το $\mathrm {(} X\cup Y)$ και η εμπιστοσύνη που σημαίνει ότι ο κανόνας $X\Rightarrow Y$ ισχύει στο D, αν το c% των δοσοληψιών στο D που περιέχουν το X, περιέχουν επίσης και το Y. Άρα σύμφωνα και με το παράδειγμα του πίνακα η υποστήριξη για το στοιχειοσύνολο(itemset) {Milk, Bread,Butter} θα είναι s({Milk, Bread,Butter}) = 2/5 ενώ η υποστήριξη θα είναι c({Milk, Bread,Butter}) = 2/3.

Από τα παραπάνω προκύπτει ότι ο κανόνας $X\Rightarrow Y$ έχει υποστήριξη s, όταν $\mathrm {sup} (X\Rightarrow Y)={sup}(X\cup Y)$ και εμπιστοσύνη c, όταν $\mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)$.

Τύποι Κανόνων Συσχετίσεων

1. Boolean Κανόνες Συσχέτισης: Μία κλασική περίπτωση είναι οι κανόνες που αναζητούμε να σχετίζονται με την ύπαρξη ή απουσία αντικειμένων. Οι κανόνες σε αυτή τη περίπτωση ονομάζονται Boolean Κανόνες συσχέτισης. Oι κανόνες που προκύπτουν κατά τη Market Basket Analysis, είναι συνήθως τέτοιοι κανόνες.
2. Ποσοτικοί Κανόνες Συσχέτισης: Αν όμως οι κανόνες περιγράφουν συσχετίσεις μεταξύ ποσοτικών αντικειμένων ή ιδιοτήτων τότε ονομάζονται ποσοτικοί κανόνες συσχέτισης. Για παράδειγμα η ηλικία εκφράζει διαστήματα τιμών και θα υποστεί διακριτοποίηση- ομαδοποίηση των δεδομένων. Δεν έχουν μόνο μία τιμή.
3. Κανόνες μονής διάστασης ή πολλών: Αν οι κανόνες αναφέρονται σε μία διάσταση ή ιδιότητα τότε ονομάζονται κανόνες απλής (ή μονής) διάστασης. Τυπικό παράδειγμα της κατηγορίας αποτελεί ο παρακάτω κανόνας: αγοράζει(Χ, ‘μπύρα’)⇒ αγοράζει(Χ, ’πατατάκια’) Ο παραπάνω κανόνας είναι απλής διάστασης αφού αναφέρεται σε μία μόνο ιδιότητα (‘αγοράζει’).
4. Κανόνες Επιπέδου: Κάποιες μέθοδοι παραγωγής κανόνων συσχέτισης μπορούν να δημιουργήσουν κανόνες σε διαφορετικό επίπεδο αφαίρεσης. Για παράδειγμα με την ηλικία που έχει διάφορα στάδια. Μπορεί να προκύπτει διαφορετικός κανόνας για 30-39 και διαφορετικό για 30.

Πρόβλημα Εξαγωγής Κανόνων Συσχέτισης

Προκειμένου να εξάγουμε έναν κανόνα συσχέτισης, πρέπει να ικανοποιούνται κάποια κατώτατα όρια τόσο για την υποστήριξη όσο και για την εμπιστοσύνη. Ο κανόνας πρέπει να έχει υποστήριξη μεγαλύτερη από το όριο, που ονομάζεται ελάχιστη υποστήριξηminsup), και η εμπιστοσύνη πρέπει να είναι μεγαλύτερη από το όριο, που ονομάζεται ελάχιστη εμπιστοσύνη(minconf). Αυτοί οι δύο παράγοντες καθορίζουν τον αριθμό των κανόνων που θα προκύψουν και άρα πρέπει να επιλέγονται με τον τύπο του πίνακα δοσοληψιών. Τα στοιχειοσύνολα(itemsets) που έχουν υποστήριξη μεγαλύτερη από το minsup καλούνται συχνά ή μεγάλα.

Τα στάδια ανάπτυξης των Κανόνων Συσχέτισης είναι τα εξής:

• Στο πρώτο πραγματοποιείται η ανεύρεση όλων των συχνών στοιχειοσυνόλων και
• Στο δεύτερο εκτελείται η εξαγωγή των κανόνων συσχέτισης που υπακούν στο όριο του minconf.

Εφαρμόζοντας τα δύο παραπάνω, μπορούμε να εκτιμήσουμε για το αν ο κανόνας έχει ενδιαφέρον ή όχι. Η επίλυση του δεύτερου βήματος είναι απλή. Για κάθε ένα από τα συχνά στοιχειοσύνολα $l$, βρες όλα τα μη κενά υποσύνολά του. Για κάθε τέτοιο υποσύνολο $a$, παρουσίασε τον κανόνα $a\Rightarrow (l-a)$, αν ο λόγος sup(l)/sup(a), που αντιστοιχεί στην εμπιστοσύνη του κανόνα είναι τουλάχιστον minconf.

Η δυσκολία και η προσοχή των ερευνητών έχει επικεντρωθεί στο πρώτο βήμα, όπου έχουν παρουσιαστεί διάφοροι αλγόριθμοι για την επίλυση του. Ο σημαντικότερος από αυτούς είναι ο αλγόριθμος Apriori.

Αλγόριθμος Apriori

Ο τρόπος λειτουργίας του αλγόριθμου σε γενικές γραμμές έχει ως εξής:

Σε πρώτη φάση, γίνεται το πέρασμα(διάβασμα) του πίνακα D. Κατά το πρώτο πέρασμα μετριέται η υποστήριξη των 1-itemsets και υπολογίζεται ποια από αυτά ικανοποιούν την συνθήκη της ελάχιστης υποστήριξης. Σε κάθε επόμενη φάση υπολογίζονται τα καινούρια itemsets που στηρίζονται στα προηγούμενα. Τα itemsets που προκύπτουν ονομάζονται υποψήφια (candidate itemsets), επειδή δεν γνωρίζουμε την υποστήριξη και κατά συνέπεια αν είναι συχνά(frequent). Αυτός είναι ο λόγος που βρίσκεται η υποστήριξή τους μέσω ενός περάσματος από τον αρχικό πίνακα. Το πλεονέκτημα αυτού του αλγορίθμου είναι ότι σε κάθε φάση γίνεται ένα μόνο πέρασμα από τον αρχικό πίνακα. Η διάκριση για το ποια itemsets είναι συχνά γίνεται στο τέλος, ώστε να χρησιμοποιηθούν στην επόμενη φάση.

Δευτερεύοντες αλγόριθμοι

Άλλοι αλγόριθμοι για την εύρεση συχνών itemsets είναι ο Partition, ο FP-Growth, και ο Eclat.

Partition

• Ο Partition μοιάζει με τον apriori, αλλά μετρά την υποστήριξη των itemsets λαμβάνοντας υπόψη τις λίστες από TIDs που αποθήκευονται για κάθε itemset.

FP-Growth

• Ο FP-Growth παράγει αρχικά ένα δέντρο FP-tree, το οποίο αντικαθιστά τον πίνακα δοσοληψιών και εξάγει τα συχνά itemsets κατευθείαν από αυτή τη δομή. Το μέγεθος του FP-tree είναι συνήθως μικρότερο από το μέγεθος των δεδομένων σε αποσυμπιεσμένη μορφή.

Eclat

• Ο Eclat είναι αλγόριθμος, ο οποίος χρησιμοποιεί την κατά βάθος αναζήτηση στο δέντρο κλάσεων. Σε αυτόν τον αλγόριθμο, ο χωρισμός του πίνακα σε τμήματα δεν είναι αναγκαίος, αφού το κόστος στην μνήμη είναι χαμηλότερο.