Αλγόριθμος Apriori στην Εξόρυξη Δεδομένων: Υλοποίηση με Παραδείγματα

apriori algorithm data mining

Εκμάθηση σε βάθος σχετικά με τον αλγόριθμο Apriori για την εύρεση συχνοτήτων στοιχείων στην εξόρυξη δεδομένων. Αυτό το σεμινάριο εξηγεί τα βήματα στο Apriori και πώς λειτουργεί:

Σε αυτό Σειρά σεμιναρίου εξόρυξης δεδομένων , ρίξαμε μια ματιά στο Αλγόριθμος Tree Tree στο προηγούμενο σεμινάριό μας.

Υπάρχουν διάφορες μέθοδοι για την Εξόρυξη Δεδομένων, όπως συσχέτιση, συσχέτιση, ταξινόμηση και ομαδοποίηση.

sql ερωτήσεις συνέντευξη ερωτήσεων και απαντήσεις για έμπειρο pdf

Αυτό το σεμινάριο επικεντρώνεται κυρίως στην εξόρυξη χρησιμοποιώντας κανόνες συσχέτισης. Σύμφωνα με τους κανόνες συσχέτισης, προσδιορίζουμε το σύνολο στοιχείων ή χαρακτηριστικών που εμφανίζονται μαζί σε έναν πίνακα.

Τι θα μάθετε:

• Τι είναι ένα στοιχείο;
  • Τι είναι ένα συχνό σύνολο στοιχείων;
  • Συχνή εξόρυξη προτύπων (FPM)
  • Κανόνες σύνδεσης
• Γιατί η συχνή εξόρυξη στοιχείων;
  • Αλγόριθμος Apriori - Αλγόριθμοι συχνών προτύπων
    • Βήματα στο Απρίριο
    • Πλεονεκτήματα
    • Μειονεκτήματα
• Μέθοδοι για τη βελτίωση της αποτελεσματικότητας του Apriori
• Εφαρμογές του αλγορίθμου Apriori
• συμπέρασμα
  • Συνιστώμενη ανάγνωση

Τι είναι ένα στοιχείο;

Ένα σύνολο στοιχείων μαζί ονομάζεται itemet. Εάν οποιοδήποτε σύνολο αντικειμένων έχει k-item, ονομάζεται k-itemset. Ένα σύνολο αντικειμένων αποτελείται από δύο ή περισσότερα στοιχεία. Ένα σύνολο στοιχείων που εμφανίζεται συχνά ονομάζεται συχνό σύνολο αντικειμένων. Έτσι, η συχνή εξόρυξη αντικειμένων είναι μια τεχνική εξόρυξης δεδομένων για τον εντοπισμό των στοιχείων που συμβαίνουν συχνά μαζί.

Για παράδειγμα , Ψωμί και βούτυρο, λογισμικό φορητού υπολογιστή και λογισμικό προστασίας από ιούς κ.λπ.

Τι είναι ένα συχνό σύνολο στοιχείων;

Ένα σύνολο στοιχείων καλείται συχνό εάν ικανοποιεί μια ελάχιστη τιμή κατωφλίου για υποστήριξη και εμπιστοσύνη. Η υποστήριξη δείχνει συναλλαγές με αντικείμενα που αγοράστηκαν μαζί σε μία μόνο συναλλαγή. Η εμπιστοσύνη δείχνει συναλλαγές όπου τα αντικείμενα αγοράζονται το ένα μετά το άλλο.

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

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

Συχνή εξόρυξη προτύπων (FPM)

Ο αλγόριθμος εξόρυξης συχνών προτύπων είναι μια από τις πιο σημαντικές τεχνικές εξόρυξης δεδομένων για την ανακάλυψη σχέσεων μεταξύ διαφορετικών στοιχείων σε ένα σύνολο δεδομένων. Αυτές οι σχέσεις παρουσιάζονται με τη μορφή κανόνων σύνδεσης. Βοηθά στον εντοπισμό των παρατυπιών στα δεδομένα.

Το FPM έχει πολλές εφαρμογές στον τομέα της ανάλυσης δεδομένων, σφάλματα λογισμικού, cross-marketing, ανάλυση καμπάνιας πώλησης, ανάλυση καλαθιού αγοράς κ.λπ.

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

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

Κανόνες σύνδεσης

Η εξόρυξη κανόνα σύνδεσης ορίζεται ως:

'Αφήστε I = {…} να είναι ένα σύνολο δυαδικών χαρακτηριστικών που ονομάζονται στοιχεία. Αφήστε το D = {….} Να είναι ένα σύνολο συναλλαγών που ονομάζεται βάση δεδομένων. Κάθε συναλλαγή στο D έχει ένα μοναδικό αναγνωριστικό συναλλαγής και περιέχει ένα υποσύνολο των αντικειμένων στο I. Ένας κανόνας ορίζεται ως επιρροή της φόρμας X-> Y όπου X, Y; I και X? Y = ?. Το σύνολο των στοιχείων X και Y ονομάζεται προηγούμενο και συνεπές του κανόνα αντίστοιχα. '

Η εκμάθηση κανόνων σύνδεσης χρησιμοποιείται για την εύρεση σχέσεων μεταξύ χαρακτηριστικών σε μεγάλες βάσεις δεδομένων. Ένας κανόνας συσχέτισης, A => B, θα έχει τη μορφή 'για ένα σύνολο συναλλαγών, κάποια τιμή του αντικειμένου Α προσδιορίζει τις τιμές του αντικειμένου Β υπό την προϋπόθεση στην οποία πληρούνται η ελάχιστη υποστήριξη και εμπιστοσύνη'.

Η υποστήριξη και η εμπιστοσύνη μπορούν να αναπαρασταθούν με το ακόλουθο παράδειγμα:

Η παραπάνω δήλωση είναι ένα παράδειγμα ενός κανόνα συσχέτισης. Αυτό σημαίνει ότι υπάρχει μια συναλλαγή 2% που αγόρασε ψωμί και βούτυρο μαζί και υπάρχει το 60% των πελατών που αγόρασαν ψωμί καθώς και βούτυρο.

Η υποστήριξη και η εμπιστοσύνη για τα στοιχεία Α και Β αντιπροσωπεύονται από τους τύπους:

Η εξόρυξη κανόνων σύνδεσης αποτελείται από 2 βήματα:

1. Βρείτε όλα τα συνηθισμένα σετ αντικειμένων.
2. Δημιουργήστε κανόνες συσχέτισης από τα πιο συχνά σύνολα στοιχείων.

Γιατί η συχνή εξόρυξη στοιχείων;

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

Αλγόριθμος Apriori - Αλγόριθμοι συχνών προτύπων

Ο αλγόριθμος Apriori ήταν ο πρώτος αλγόριθμος που προτάθηκε για συχνή εξόρυξη αντικειμένων. Αργότερα βελτιώθηκε από τους R Agarwal και R Srikant και έγινε γνωστός ως Apriori. Αυτός ο αλγόριθμος χρησιμοποιεί δύο βήματα 'join' και 'prune' για τη μείωση του χώρου αναζήτησης. Είναι μια επαναληπτική προσέγγιση για να ανακαλύψετε τα πιο συχνά είδη αντικειμένων.

Ο Απρίρι λέει:

Η πιθανότητα ότι το στοιχείο I δεν είναι συχνό είναι εάν:

• ΠΙ)
• P (I + A)
• Εάν ένα σύνολο αντικειμένων έχει τιμή μικρότερη από την ελάχιστη υποστήριξη, τότε όλα τα υπερσύνολά του θα πέσουν επίσης κάτω από την ελάχιστη υποστήριξη και έτσι μπορεί να αγνοηθεί. Αυτή η ιδιότητα ονομάζεται ιδιοκτησία Antimonotone.

Τα βήματα που ακολουθούνται στον αλγόριθμο Apriori της εξόρυξης δεδομένων είναι:

1. Εγγραφείτε στο βήμα : Αυτό το βήμα δημιουργεί (K + 1) σετ αντικειμένων από το K-itemsets ενώνοντας κάθε στοιχείο με το ίδιο.
2. Βήμα κλαδέματος : Αυτό το βήμα σαρώνει τον αριθμό κάθε στοιχείου στη βάση δεδομένων. Εάν το υποψήφιο στοιχείο δεν πληροί την ελάχιστη υποστήριξη, τότε θεωρείται σπάνιο και έτσι αφαιρείται. Αυτό το βήμα εκτελείται για τη μείωση του μεγέθους των υποψήφιων αντικειμένων.

Βήματα στο Απρίριο

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

# 1) Στην πρώτη επανάληψη του αλγορίθμου, κάθε στοιχείο λαμβάνεται ως υποψήφιος 1-itemets. Ο αλγόριθμος θα μετρήσει τις εμφανίσεις κάθε στοιχείου.

#δύο) Ας υπάρχει κάποια ελάχιστη υποστήριξη, min_sup (π.χ. 2). Προσδιορίζεται το σετ 1 - σετ αντικειμένων των οποίων η εμφάνιση ικανοποιεί το ελάχιστο sup. Μόνο εκείνοι οι υποψήφιοι που μετράνε περισσότερο ή ίσο με το min_sup, προκρίνονται για την επόμενη επανάληψη και οι άλλοι κλαδεύονται.

# 3) Στη συνέχεια, ανακαλύπτονται συχνά αντικείμενα 2-αντικειμένων με min_sup. Για αυτό στο βήμα σύνδεσης, το σύνολο 2 στοιχείων δημιουργείται σχηματίζοντας μια ομάδα 2 συνδυάζοντας στοιχεία με τον εαυτό του.

# 4) Οι υποψήφιοι 2-itemet κλαδεύονται χρησιμοποιώντας ελάχιστη τιμή κατωφλίου. Τώρα ο πίνακας θα έχει 2 –ομάδες με ελάχιστο sup.

# 5) Η επόμενη επανάληψη θα σχηματίσει 3 –στοιχεία χρησιμοποιώντας το βήμα join και prune. Αυτή η επανάληψη θα ακολουθήσει την ιδιότητα antimonotone όπου τα υποσύνολα των 3-itemets, δηλαδή τα υποσύνολα 2 -setet κάθε ομάδας πέφτουν στο min_sup. Εάν όλα τα υποσύνολα 2-itemet είναι συχνά, τότε το υπερσύνολο θα είναι συχνό αλλιώς είναι κλάδεμα.

# 6) Το επόμενο βήμα θα ακολουθήσει τη δημιουργία 4-itemset με τη σύνδεση 3-itemet με τον εαυτό του και το κλάδεμα εάν το υποσύνολο του δεν πληροί τα κριτήρια min_sup. Ο αλγόριθμος διακόπτεται όταν επιτυγχάνεται το πιο συχνό σύνολο αντικειμένων.

(εικόνα πηγή )

Παράδειγμα Απρίρι:Όριο υποστήριξης = 50%, Εμπιστοσύνη = 60%

ΤΡΑΠΕΖΙ 1

Λύση:

Όριο υποστήριξης = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Πλήθος κάθε είδους

ΠΙΝΑΚΑΣ-2

δύο. Βήμα κλαδέματος: ΠΙΝΑΚΑΣ -2 δείχνει ότι το στοιχείο I5 δεν πληροί το min_sup = 3, επομένως διαγράφεται, μόνο το I1, I2, I3, I4 πληροί το πλήθος min_sup.

ΠΙΝΑΚΑΣ-3

3. Εγγραφείτε στο βήμα: Φόρμα 2-είδη. Από ΤΡΑΠΕΖΙ 1 μάθετε τα περιστατικά του 2-itemet.

ΠΙΝΑΚΑΣ-4

Τέσσερις. Βήμα κλαδέματος: ΠΙΝΑΚΑΣ -4 δείχνει ότι το σύνολο στοιχείων {I1, I4} και {I3, I4} δεν πληροί το min_sup, επομένως διαγράφεται.

ΠΙΝΑΚΑΣ-5

5. Βήμα εγγραφής και κλαδέματος: Έντυπο 3-σετ. Από το ΤΡΑΠΕΖΙ 1 ανακαλύψτε τις εμφανίσεις του 3-itemet. Από ΠΙΝΑΚΑΣ-5 , ανακαλύψτε τα υποσύνολα 2 αντικειμένων που υποστηρίζουν min_sup.

Μπορούμε να δούμε για το σύνολο στοιχείων {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} ΠΙΝΑΚΑΣ-5 έτσι {I1, I2, I3} είναι συχνή.

Μπορούμε να δούμε για τα σύνολα αντικειμένων {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} δεν είναι συχνό, καθώς δεν συμβαίνει σε ΠΙΝΑΚΑΣ-5 Επομένως {I1, I2, I4} δεν είναι συχνή, ως εκ τούτου διαγράφεται.

ΠΙΝΑΚΑΣ-6

Μόνο οι {I1, I2, I3} είναι συχνές .

δωρεάν λογισμικό ελέγχου έκδοσης για Windows

6. Δημιουργήστε κανόνες σύνδεσης: Από το συχνό σύνολο αντικειμένων που ανακαλύφθηκε παραπάνω, ο συσχετισμός θα μπορούσε να είναι:

{I1, I2} => {I3}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Εμπιστοσύνη = υποστήριξη {I1, I2, I3} / υποστήριξη {I3} = (3/4) * 100 = 75%

Αυτό δείχνει ότι όλοι οι παραπάνω κανόνες συσχέτισης είναι ισχυροί εάν το ελάχιστο όριο εμπιστοσύνης είναι 60%.

Ο αλγόριθμος Apriori: Ψευδοκώδικας

C: Σύνολο υποψηφίων μεγέθους k

L: Συχνό σύνολο αντικειμένων μεγέθους k

(εικόνα πηγή )

Πλεονεκτήματα

1. Εύκολος κατανοητός αλγόριθμος
2. Τα βήματα εγγραφής και κοπής είναι εύκολο να εφαρμοστούν σε μεγάλα σύνολα αντικειμένων σε μεγάλες βάσεις δεδομένων

Μειονεκτήματα

1. Απαιτεί υψηλό υπολογισμό εάν τα σύνολα ειδών είναι πολύ μεγάλα και η ελάχιστη υποστήριξη διατηρείται πολύ χαμηλή.
2. Πρέπει να σαρωθεί ολόκληρη η βάση δεδομένων.

Μέθοδοι για τη βελτίωση της αποτελεσματικότητας του Apriori

Υπάρχουν πολλές μέθοδοι για τη βελτίωση της αποτελεσματικότητας του αλγορίθμου.

1. Τεχνική βασισμένη σε Hash: Αυτή η μέθοδος χρησιμοποιεί μια δομή βασισμένη σε κατακερματισμό που ονομάζεται πίνακας κατακερματισμού για τη δημιουργία του k-itemets και του αντίστοιχου αριθμού του. Χρησιμοποιεί μια συνάρτηση κατακερματισμού για τη δημιουργία του πίνακα.
2. Μείωση συναλλαγής: Αυτή η μέθοδος μειώνει τον αριθμό των συναλλαγών σάρωσης σε επαναλήψεις. Οι συναλλαγές που δεν περιέχουν συχνά στοιχεία επισημαίνονται ή καταργούνται.
3. Διαμέριση: Αυτή η μέθοδος απαιτεί μόνο δύο σαρώσεις βάσεων δεδομένων για την εξόρυξη των συχνών συνόλων στοιχείων. Λέει ότι για κάθε στοιχείο που είναι δυνητικά συχνό στη βάση δεδομένων, θα πρέπει να είναι συχνό σε τουλάχιστον ένα από τα διαμερίσματα της βάσης δεδομένων.
4. Δειγματοληψία: Αυτή η μέθοδος επιλέγει ένα τυχαίο δείγμα S από τη βάση δεδομένων D και έπειτα αναζητά συχνό σύνολο αντικειμένων στο S. Μπορεί να είναι δυνατόν να χάσετε ένα καθολικό συχνό σύνολο αντικειμένων. Αυτό μπορεί να μειωθεί μειώνοντας το min_sup.
5. Δυναμική καταμέτρηση στοιχείων: Αυτή η τεχνική μπορεί να προσθέσει νέα υποψήφια αντικείμενα σε οποιοδήποτε σημείο έναρξης της βάσης δεδομένων κατά τη σάρωση της βάσης δεδομένων.

Εφαρμογές του αλγορίθμου Apriori

Ορισμένα πεδία στα οποία χρησιμοποιείται το Apriori:

1. Στον τομέα της εκπαίδευσης: Εξαγωγή κανόνων συσχέτισης στην εξόρυξη δεδομένων των μαθητών που γίνονται δεκτοί μέσω χαρακτηριστικών και ειδικοτήτων.
2. Στον ιατρικό τομέα: Για παράδειγμα Ανάλυση της βάσης δεδομένων του ασθενούς.
3. Στη δασοκομία: Ανάλυση πιθανότητας και έντασης δασικής πυρκαγιάς με τα δεδομένα δασικής πυρκαγιάς.
4. Το Apriori χρησιμοποιείται από πολλές εταιρείες όπως το Amazon στο Σύστημα Προτεινόμενων και από την Google για τη λειτουργία αυτόματης συμπλήρωσης.

συμπέρασμα

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

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

Ρίξτε μια ματιά στο επερχόμενο σεμινάριό μας για να μάθετε περισσότερα σχετικά με τον Αλγόριθμο Συχνής Ανάπτυξης Μοτίβου !!

Εκπαιδευτικό πρόγραμμα PREV | ΕΠΟΜΕΝΟ Φροντιστήριο

Συνιστώμενη ανάγνωση

• Τεχνικές Εξόρυξης Δεδομένων: Αλγόριθμος, Μέθοδοι & Κορυφαία Εργαλεία Εξόρυξης Δεδομένων
• Εξόρυξη δεδομένων: Διαδικασία, τεχνικές και σημαντικά ζητήματα στην ανάλυση δεδομένων
• Παραδείγματα εξόρυξης δεδομένων: Οι πιο κοινές εφαρμογές της εξόρυξης δεδομένων 2021
• Παραδείγματα αλγορίθμου δέντρων απόφασης στην εξόρυξη δεδομένων
• Διαδικασία εξόρυξης δεδομένων: Συμπεριλαμβάνονται μοντέλα, βήματα διαδικασίας και προκλήσεις
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning
• Κορυφαία 15 καλύτερα δωρεάν εργαλεία εξόρυξης δεδομένων: Η πιο περιεκτική λίστα
• Παράμετρος δεδομένων JMeter με χρήση μεταβλητών καθορισμένων από τον χρήστη