Αλγόριθμος αύξησης συχνών προτύπων (FP) στην εξόρυξη δεδομένων

frequent pattern growth algorithm data mining

Λεπτομερής οδηγός για τον αλγόριθμο συχνής ανάπτυξης μοτίβων που αντιπροσωπεύει τη βάση δεδομένων με τη μορφή Δέντρου FP. Περιλαμβάνει FP Growth Vs Apriori Σύγκριση:

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

δωρεάν προστασία τείχους προστασίας για τα Windows 10

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

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

Τι θα μάθετε:

• Αδυναμίες του αλγορίθμου Apriori
• Αλγόριθμος συχνής ανάπτυξης μοτίβου
• Δέντρο FP
• Βήματα αλγορίθμου συχνών προτύπων
• Παράδειγμα αλγόριθμου FP-Growth
• Πλεονεκτήματα του αλγόριθμου ανάπτυξης FP
• Μειονεκτήματα του αλγόριθμου FP-Growth
• FP Growth vs Apriori
• ΛΑΜΨΗ
• συμπέρασμα
• Συνιστώμενη ανάγνωση

Αδυναμίες του αλγορίθμου Apriori

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

Αυτές οι ελλείψεις μπορούν να ξεπεραστούν χρησιμοποιώντας τον αλγόριθμο ανάπτυξης FP.

Αλγόριθμος συχνής ανάπτυξης μοτίβου

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

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

Δέντρο FP

Το Frequent Pattern Tree είναι μια δομή που μοιάζει με δέντρο που έχει δημιουργηθεί με τα αρχικά σύνολα στοιχείων της βάσης δεδομένων. Ο σκοπός του δέντρου FP είναι η εξόρυξη του πιο συνηθισμένου μοτίβου. Κάθε κόμβος του δέντρου FP αντιπροσωπεύει ένα στοιχείο του σετ αντικειμένων.

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

Βήματα αλγορίθμου συχνών προτύπων

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

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

# 1) Το πρώτο βήμα είναι να σαρώσετε τη βάση δεδομένων για να βρείτε τις εμφανίσεις των αντικειμένων στη βάση δεδομένων. Αυτό το βήμα είναι το ίδιο με το πρώτο βήμα του Apriori. Ο αριθμός των 1-στοιχειών στη βάση δεδομένων ονομάζεται αριθμός υποστήριξης ή συχνότητα του 1-itemet.

#δύο) Το δεύτερο βήμα είναι η κατασκευή του δέντρου FP. Για αυτό, δημιουργήστε τη ρίζα του δέντρου. Η ρίζα αντιπροσωπεύεται από το null.

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

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

Αυτό σημαίνει ότι το κοινό σύνολο αντικειμένων συνδέεται με τον νέο κόμβο άλλου αντικειμένου σε αυτήν τη συναλλαγή.

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

# 6) Το επόμενο βήμα είναι η εξόρυξη του δέντρου FP που δημιουργήθηκε. Γι 'αυτό, εξετάζεται πρώτα ο χαμηλότερος κόμβος μαζί με τους συνδέσμους των χαμηλότερων κόμβων. Ο χαμηλότερος κόμβος αντιπροσωπεύει το μήκος μοτίβου συχνότητας 1. Από αυτό, διασχίστε τη διαδρομή στο δέντρο FP. Αυτή η διαδρομή ή οι διαδρομές ονομάζονται βάση υπό όρους.

Η υπό όρους βάση μοτίβου είναι μια υπο-βάση δεδομένων που αποτελείται από διαδρομές προθέματος στο δέντρο FP που εμφανίζεται με τον χαμηλότερο κόμβο (επίθημα).

# 7) Κατασκευάστε ένα δέντρο υπό όρους FP, το οποίο διαμορφώνεται από έναν αριθμό αντικειμένων στη διαδρομή. Τα σύνολα στοιχείων που πληρούν την υποστήριξη κατωφλίου λαμβάνονται υπόψη στο δέντρο υπό όρους FP.

# 8) Συχνά μοτίβα δημιουργούνται από το δέντρο υπό όρους FP.

Παράδειγμα αλγόριθμου FP-Growth

Όριο υποστήριξης = 50%, Εμπιστοσύνη = 60%

Τραπέζι 1

Λύση:

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

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

1. Καταμέτρηση κάθε αντικειμένου

Πίνακας 2

2. Ταξινόμηση του αντικειμένου σε φθίνουσα σειρά.

Πίνακας 3

3. Κατασκευάστε το δέντρο FP

1. Λαμβάνοντας υπόψη τον μηδενικό κόμβο ρίζας.
2. Η πρώτη σάρωση της Συναλλαγής T1: I1, I2, I3 περιέχει τρία στοιχεία {I1: 1}, {I2: 1}, {I3: 1}, όπου το I2 συνδέεται ως θυγατρικό στη ρίζα, το I1 συνδέεται με το I2 και το I3 συνδέεται με το I1.
3. T2: I2, I3, I4 περιέχει I2, I3 και I4, όπου το I2 συνδέεται με τη ρίζα, το I3 συνδέεται με το I2 και το I4 συνδέεται με το I3. Αλλά αυτός ο κλάδος θα μοιραζόταν τον κόμβο I2 τόσο κοινό όσο χρησιμοποιείται ήδη στο T1.
4. Αυξήστε την καταμέτρηση του I2 από το 1 και το I3 συνδέεται ως παιδί με το I2, το I4 συνδέεται ως παιδί με το I3. Η μέτρηση είναι {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Παρομοίως, ένας νέος κλάδος με το I5 συνδέεται με το I4 καθώς δημιουργείται ένα παιδί.
6. T4: I1, I2, I4. Η ακολουθία θα είναι I2, I1 και I4. Το I2 είναι ήδη συνδεδεμένο με τον ριζικό κόμβο, επομένως θα αυξηθεί από το 1. Παρομοίως, το I1 θα αυξηθεί από το 1 καθώς είναι ήδη συνδεδεμένο με το I2 στο T1, επομένως {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Η ακολουθία θα είναι I2, I1, I3 και I5. Έτσι, {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Η ακολουθία θα είναι I2, I1, I3 και I4. Έτσι, {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Η εξόρυξη FP-δέντρου συνοψίζεται παρακάτω:

1. Το χαμηλότερο στοιχείο κόμβου I5 δεν θεωρείται επειδή δεν έχει ελάχιστο αριθμό υποστήριξης, επομένως διαγράφεται.
2. Ο επόμενος κάτω κόμβος είναι το I4. Το I4 εμφανίζεται σε 2 κλάδους, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Επομένως, θεωρώντας το I4 ως επίθημα, οι διαδρομές προθέματος θα είναι {I2, I1, I3: 1}, {I2, I3: 1}. Αυτό σχηματίζει τη βάση υπό όρους.
3. Η βάση υπό όρους θεωρείται μια βάση δεδομένων συναλλαγών, κατασκευάζεται ένα δέντρο FP. Αυτό θα περιέχει {I2: 2, I3: 2}, το I1 δεν θεωρείται ότι δεν πληροί τον ελάχιστο αριθμό υποστήριξης.
4. Αυτή η διαδρομή θα δημιουργήσει όλους τους συνδυασμούς συχνών μοτίβων: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Για το I3, η διαδρομή προθέματος θα ήταν: {I2, I1: 3}, {I2: 1}, αυτό θα δημιουργήσει έναν FP-δέντρο 2 κόμβων: {I2: 4, I1: 3} και δημιουργούνται συχνά μοτίβα: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Για το I1, η διαδρομή προθέματος θα ήταν: {I2: 4} αυτό θα δημιουργήσει έναν μόνο κόμβο FP-δέντρο: {I2: 4} και δημιουργούνται συχνά μοτίβα: {I2, I1: 4}.

Το διάγραμμα που δίνεται παρακάτω απεικονίζει το δέντρο υπό όρους FP που σχετίζεται με τον υπό όρους κόμβο I3.

Πλεονεκτήματα του αλγόριθμου ανάπτυξης FP

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

Μειονεκτήματα του αλγόριθμου FP-Growth

1. Το FP Tree είναι πιο δύσκολο και δύσκολο να κατασκευαστεί από το Apriori.
2. Μπορεί να είναι ακριβό.
3. Όταν η βάση δεδομένων είναι μεγάλη, ο αλγόριθμος ενδέχεται να μην χωράει στην κοινόχρηστη μνήμη.

FP Growth vs Apriori

ΛΑΜΨΗ

Η παραπάνω μέθοδος, η αύξηση του Apriori και του FP, ορυχεία συχνά σετ αντικειμένων χρησιμοποιώντας οριζόντια μορφή δεδομένων. Το ECLAT είναι μια μέθοδος εξόρυξης συχνών συνόλων αντικειμένων χρησιμοποιώντας την κάθετη μορφή δεδομένων. Θα μετατρέψει τα δεδομένα σε οριζόντια μορφή δεδομένων σε κάθετη μορφή.

Για παράδειγμα,Χρήση αύξησης Apriori και FP:

Το ECLAT θα έχει τη μορφή του πίνακα ως:

Αυτή η μέθοδος θα σχηματίσει 2-σετ αντικειμένων, 3 σετ αντικειμένων, κιτ σετ σε κάθετη μορφή δεδομένων. Αυτή η διαδικασία με το k αυξάνεται κατά 1 έως ότου δεν βρεθούν υποψήφια σύνολα ειδών. Ορισμένες τεχνικές βελτιστοποίησης όπως το diffset χρησιμοποιούνται μαζί με το Apriori.

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

συμπέρασμα

Ο αλγόριθμος Apriori χρησιμοποιείται για τους κανόνες συσχετισμού εξόρυξης. Λειτουργεί με την αρχή, «τα μη κενά υποσύνολα των συχνών αντικειμένων πρέπει επίσης να είναι συχνά». Σχηματίζει υποψήφιους k-itemset από (k-1) σύνολα αντικειμένων και σαρώνει τη βάση δεδομένων για να βρει τα συχνά σύνολα αντικειμένων.

Ο Αλγόριθμος Συχνής Ανάπτυξης Μοτίβου είναι η μέθοδος εύρεσης συχνών μοτίβων χωρίς δημιουργία υποψηφίων. Κατασκευάζει ένα δέντρο FP αντί να χρησιμοποιεί τη στρατηγική δημιουργίας και δοκιμής του Apriori. Το επίκεντρο του αλγορίθμου FP Growth είναι ο κατακερματισμός των διαδρομών των αντικειμένων και η εξόρυξη συχνών προτύπων.

πώς να φτιάξετε ένα δοκιμαστικό σχέδιο

Ελπίζουμε αυτά τα σεμινάρια στη Σειρά Εξόρυξης Δεδομένων να εμπλουτίσουν τις γνώσεις σας σχετικά με την Εξόρυξη Δεδομένων !!

Εκπαιδευτικό πρόγραμμα PREV | Πρώτο σεμινάριο

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

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