| Περίληψη: | Η παρούσα εργασία πραγματεύεται το πρόβλημα της εξόρυξης γνώσης μέσα από μεγάλες βάσεις δεδομένων. Πιο συγκεκριμένα αναλύονται τεχνικές εύρεσης συχνών συνόλων αντικειμένων και κανόνων συσχέτισης (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 γράφος
|
|---|
