Η παρούσα εργασία πραγματεύεται το πρόβλημα της εξόρυξης γνώσης μέσα από μεγάλες βάσεις δεδομένων. Πιο συγκεκριμένα αναλύονται τεχνικές εύρεσης συχνών συνόλων αντικειμένων και κανόνων συσχέτισης (association rules). Οι τεχνικές αυτές έχουν μεγάλη εφαρμογή σε τομείς της καθημερινής ζωής. Ένα παράδειγμα είναι το σύνολο των αντικειμένων που μπορεί να αγοράσει κάποιος από ένα πολυκατάστημα (market analysis). Η εύρεση συσχετισμού μεταξύ των αντικειμένων που περιέχει το καλάθι των προϊόντων μπορεί να βοηθήσει σε μεγάλο βαθμό την διεύθυνση της επιχείρησης ώστε να αναδιατάξει τη σειρά με την οποία τοποθετεί τα προϊόντα στα ράφια. Οι πιο δημοφιλείς αλγόριθμοι που επιλύουν το πρόβλημα είναι ο apriori και ο fp-growth, χρησιμοποιούν ένα κατώφλι εμπιστοσύνης πάνω από το οποίο πρέπει να είναι ο αριθμός εμφανίσεων των συνόλων αντικειμένων μέσα στην βάση δεδομένων. Αυτό όμως δεν ανταποκρίνεται στην πραγματικότητα γιατί στην καθημερινότητα υπάρχουν προϊόντα (items) τα οποία εμφανίζονται από τη φύση τους αρκετά σπάνια οπότε το όριο της υποστήριξης τους πρέπει να τεθεί αρκετά χαμηλά ώστε να αποκτήσουν σημασία οι λιγοστές εμφανίσεις τους. Αντίστοιχα τα προϊόντα που εμφανίζονται αρκετά συχνά μπορούν να έχουν όριο υποστήριξης σχετικά μεγάλο. Για το λόγο αυτό αναπτύχθηκαν αλγόριθμοι όπου αντί για ένα ενιαίο κατώφλι υποστήριξης, έχουμε πολλαπλά (multiple minimum support) και κάθε item έχει το δικό του. Έτσι υλοποιήθηκε ο αλγόριθμος apriori ενώ η παρούσα εργασία φιλοδοξεί να εφαρμόσει τον αλγόριθμο fp-growth και μάλιστα με δύο εναλλακτικές τεχνικές σε πολλαπλές υποστηρίξεις. Οι δύο τεχνικές διαφέρουν ως προς τον τρόπο κατασκευής της βασικής δομής δηλαδή του δέντρου fp-tree. Το δέντρο αυτό περιέχει τα υποσύνολα αντικειμένων, τα οποία θα διερευνήσουμε αν εμφανίζονται αρκετά συχνά ώστε να θεωρήσουμε ότι τα αντικείμενα τους συσχετίζονται μεταξύ τους. Στη συνέχεια μελετάμε τις τεχνικές εύρεσης αρνητικών κανόνων συσχέτισης (negative association rules). Οι κανόνες αυτοί είναι χρήσιμοι στην ανάλυση αγορών με στόχο να ανακαλυφθούν τα προϊόντα που ‘συγκρούονται’ μεταξύ τους ή αλληλοσυμπληρώνονται. Η μορφή τους είναι X→⌐Y και υποδηλώνει την απουσία κάποιων αντικειμένων (Υ) ως αποτέλεσμα της παρουσίας των συνόλου αντικειμένων Χ. Και σε αυτό τον τομέα έχει αναπτυχθεί ένας αλγόριθμος που εφαρμόζει apriori για την εύρεση των συνόλων από όπου θα προκύψουν τα Χ και Y και εισάγει μια μετρική συσχέτισης των δύο συνόλων αντικειμένων, που επιλέχθηκε να είναι το correlation coefficient . Αυτό που εμείς υλοποιήσαμε είναι η εφαρμογή του ίδιου αλγορίθμου αλλάζοντας όμως τεχνική χρησιμοποιώντας τον fp-growth αντί για apriori. Τέλος ασχοληθήκαμε με το πρόβλημα της εξόρυξης προτύπων με προαπαιτούμενο τη διατήρηση της σειράς των αντικειμένων (order preserving). Αναπτύχθηκε μια νέα τεχνική εξόρυξης η οποία βασίζεται στον υπάρχοντα αλγόριθμο fp-growth αλλά βασισμένη σε μια εναλλακτική μορφή τον λεγόμενο fp γράφο. Συμπερασματικά σε αυτήν την εργασία θα αναπτυχθούν τα παρακάτω: 1. Αλγόριθμος fp-growth σε πολλαπλές υποστηρίξεις όπου η βασική δομή- το δέντρο FP-tree- έχει στα φύλλα αντικείμενα με τις μεγαλύτερες υποστηρίξεις. 2. Αλγόριθμος fp-growth σε πολλαπλές υποστηρίξεις όπου η βασική δομή- το δέντρο FP-tree- έχει στα φύλλα αντικείμενα με τις μικρότερες υποστηρίξεις. 3. Αλγόριθμος fp-growth για την εύρεση αρνητικών κανόνων συσχέτισης. 4. Αλγόριθμος fp-growth για την εξόρυξη προτύπων με διατήρηση σειράς αντικειμένων όπου η βασική δομή είναι ο fp γράφος / The present work deals with the problem of data mining from databases. More specifically we analyze methods for detection of frequent itemsets and association rules. The most popular case study of data mining is the market analysis. The important here is the detection of relation among buying items. These relation could follow to a new different classification of items inside the super market.
The most popular algorithms of data mining – apriori and fp growth – use a single support threshold for the number of appearances of items inside the database.
This single threshold is not appropriate because of the different kind of items. This conclude to replacement of single threshold with multiple threshold, one for each concrete item.
We implement the algorithm fp growth for multiple minimum supports, using two different methods. These two methods differs in the way we build the fp tree. The fp tree contents the itemsets which we must examine if they are frequent or not.
Right after that we study methods for detection positive and negative association rules. Negative association rules have the form X→⌐Y. The symbol ⌐ indicate the absence of itemset Y. Our method also use a statistic method for calculate the relation between X and Y called ‘correlation coefficient’. This method leads to an algorithm fp growth for detection of positive and negative rules.
Finally we involve with the data mining problem using a semantic requirement: ‘The order of the items in an itemset cannot change’. We develop an fp growth algorithm for detect frequent itemsets with order preserving. This algorithm use a fp graph instead of fp tree.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/1230 |
| Date | 12 January 2009 |
| Creators | Γουρδουλής, Ιωάννης Πρόδρομος |
| Contributors | Μακρής, Χρήστος, Μακρής, Χρήστος, Τσακαλίδης, Αθανάσιος, Χατζηλυγερούδης, Ιωάννης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0033 seconds