Σε αρκετές εφαρμογές (μελέτη συμπεριφοράς καταναλωτών, ανάλυση βιοδεικτών, εντοπισμός λογοκλοπής, κ.λπ.) χρειάζεται να βρούμε συχνά στοιχειοσύνολα. Ένας τρόπος εύρεσής τους είναι με τον αλγόριθμο των Agrawal και Srikant. Στη συγκεκριμένη εργασία, καλείστε να υλοποιήσετε τον αλγόριθμο αυτό.
Τα καλάθια αντικειμένων, με τα οποία θα εργαστείτε, θα περιέχονται μέσα σε ένα αρχείο CSV
. Κάθε γραμμή του αρχείου αυτού θα έχει τη μορφή:
item_1, item_2, ..., item_n
Για παράδειγμα, ένα τέτοιο αρχείο μπορεί να είναι το παρακάτω:
Cat, and, dog, bites
Yahoo, news, claims, a, cat, mated, with, a, dog, and, produced, viable, offspring
Cat, killer, likely, is, a, big, dog
Professional, free, advice, on, dog, training, puppy, training
Cat, and, kitten, training, and, behavior
Dog, &, Cat, provides, dog, training, in Eugene, Oregon
"Dog, and, cat", is, a, slang, term, used, by, police, officers, for, a, male-female, relationship
Shop, for, your, show, dog, grooming, and, pet, supplies
Το πρόγραμμά σας θα πρέπει να διαβάζει ένα τέτοιο αρχείο, να βρίσκει συχνά στοιχειοσύνολα σύμφωνα με το κατώφλι που θα δίνει ο χρήστης, και να εξάγει αποτελέσματα σε μορφή CSV
.
Κάθε φοιτητής θα εργαστεί στο προσωπικό του αποθετήριο στο GitHub. Για να αξιολογηθεί μια εργασία θα πρέπει να πληροί τις παρακάτω προϋποθέσεις:
-
Όλη η εργασία θα πρέπει να βρίσκεται σε έναν κατάλογο
assignment-2015-3
μέσα στο αποθετήριο του φοιτητή. -
Το πρόγραμμα θα πρέπει να έχει όνομα
a_priori.py
. -
Το πρόγραμμα θα μπορεί να καλείται ως εξής:
python a_priori.py [-n] [-p] [-o OUTPUT] support filename
Οι αγκύλες δεν αποτελούν μέρος των πραγμάτων που δίνει ο χρήστης, απλώς χρησιμεύουν για να μας υπενθυμίζουν στην περιγραφή του προγράμματος ότι η συγκεκριμένη παράμετρος είναι προαιρετική. Έτσι έχουμε:
- Η παράμετρος
-n
είναι προαιρετική. Αν δίνεται η παράμετρος-n
, το πρόγραμμα θα θεωρεί ότι τα αντικείμενα είναι αριθμητικά (όχι strings). Αλλιώς θα τα θεωρεί strings. - Η παράμετρος
-p
είναι προαιρετική. Αν δίνεται η παράμετρος-p
, το πρόγραμμα θα θεωρεί ότι η ελάχιστη τιμή υποστήριξης που δίνεται μέσω της παραμέτρου-s
είναι το ποσοστό των καλαθιών στα οποία θα πρέπει να βρίσκεται ένα συνολοστοιχείο για να θεωρηθεί σημαντικό. - Η παράμετρος
-o OUTPUT
είναι προαιρετική. Αν δίνεται η παράμετρος-o
το πρόγραμμα θα σώζει τα αποτελέσματα στο αρχείοOUTPUT
. Αλλιώς θα τα εμφανίζει στην οθόνη. - Η παράμετρος
support
είναι υποχρεωτική. Με αυτήν δίνεται η ελάχιστη τιμή υποστήριξης (support) που θα χρησιμοποιεί ο αλγόριθμος για τον χαρακτηρισμό των συχνών συνολοστοιχείων. - Η παράμετρος
filename
είναι υποχρεωτική. Με αυτήν δίνεται το όνομα του αρχείου εισόδου του προγράμματος.
Για παράδειγμα, μπορούμε να καλέσουμε το πρόγραμμα ως εξής:
python a_priori.py -n 2 a_priori_example_2.csv
το οποίο σημαίνει ότι θα διαβαστεί το αρχείο a_priori_example_2.csv
, τα περιεχόμενα του οποίου θα ερμηνευτούν ως αριθμητικά, η υποστήριξη θα έχει κατώφλι το 2, και τα αποτελέσματα θα εμφανιστούν στην οθόνη.
Αν δώσουμε:
python a_priori.py -p -o a_prior_example_1_results.csv 20 a_priori_example_1.csv
θα διαβαστεί το αρχείο a_priori_example_1.csv
, τα περιεχόμενα του οποίου θα ερμηνευτούν ως string, η υποστήριξη θα έχει κατώφλι το 20% του συνόλου των εγγραφών, και τα αποτελέσματα θα αποθηκευτούν στο αρχείο a_prior_example_1_results.csv
.
Το πρόγραμμα θα παράγει το αποτέλεσμα με μορφή CSV
, όπου ο διαχωριστής θα είναι ο χαρακτήρας ;
. Κάθε γραμμή θα είναι της μορφής:
itemset_1:support;itemset_2:support;...itemset_n:support
όπου κάθε itemset
θα είναι της μορφής:
(item,)
(αν αποτελείται από ένα αντικείμενο)(item_1, item_2, ..., item_n)
αν αποτελείται απόn
αντικείμενα.
Προσοχή: ο λόγος που ζητείται το κάθε itemset να είναι της μορφής (item,)
αν πρόκειται για μόνο ένα αντικείμενο είναι για τη διευκόλυνσή σας. Είναι πιθανό ότι για την καταμέτρηση των συχνοτήτων των itemsets θα χρησιμοποιήσετε λεξικά. Στα λεξικά τα κλειδιά δεν μπορεί να είναι λίστες ή σύνολα, μπορεί να είναι όπως tuples. Ένα tuple με ένα μόνο στοιχείο item μέσα του αναπαρίσταται στην Python ως (item,)
.
Έτσι αν στο αρχείο που δώσαμε παραπάνω ως παράδειγμα ζητούσαμε στήριξη 3, θα παίρναμε στην έξοδο:
('a',):3;('and',):4;('cat',):5;('dog',):6;('training',):3
('and', 'cat'):3;('and', 'dog'):3;('cat', 'dog'):4
Δείγματα αρχείων εισόδου και εξόδου του προγράμματος:
- example_1.csv, με στήριξη 3 θα δώσει έξοδο:
('a',):3;('and',):4;('cat',):5;('dog',):6;('training',):3
('and', 'cat'):3;('and', 'dog'):3;('cat', 'dog'):4
- example_2.csv, με στήριξη 2 και θεωρώντας τα αντικείμενα αριθμητικά θα δώσει έξοδο:
(1,):2;(2,):3;(3,):3;(5,):3
(1, 3):2;(2, 3):2;(2, 5):3;(3, 5):2
(2, 3, 5):2
- example_3.csv, με στήριξη 2 και θεωρώντας τα αντικείμενα αριθμητικά θα δώσει έξοδο:
(1,):3;(2,):6;(3,):4;(4,):5
(1, 2):3;(1, 4):2;(2, 3):3;(2, 4):4;(3, 4):3
(1, 2, 4):2;(2, 3, 4):2