Εξόρυξη Δεδομένων και Μηχανική Μάθηση — Ιούνιος 2021 (Εκδοχή Β)¶
Μεταγραφή από το κείμενο της τυπωμένης εκφώνησης dm_themata_b.pdf (2 σελίδες).
dm_themata_b.pdf¶
Εξέταση Μαθήματος «ΕΞΟΡΥΞΗ ΔΕΔΟΜΕΝΩΝ ΚΑΙ¶
ΑΛΓΟΡΙΘΜΟΙ ΜΑΘΗΣΗΣ» (B)¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ Εαρινό Εξάμηνο 2020-21
Διδάσκοντες: Mεγαλοικονόμου Βασίλειος Μακρής Χρήστος, ΔΙΑΡΚΕΙΑ 2 ΩΡEΣ MAZI ME TO ANEBAΣΜΑ ΣΤΟ ECLASS
ΘΕΜΑ 1 Προεπεξεργασία δεδομένων (7 μονάδες)¶
Έστω τα ακόλουθα δεδομένα θερμοκρασίας (σε βαθμούς C): 4,8,9,15,18,20,28,30,33,35, 36,38,39,40. Εφαρμόστε δύο διαφορετικές μεθόδους Binning για την εξομάλυνση των παραπάνω δεδομένων (σε κάθε μέθοδο που θα εφαρμόσετε, θα πρέπει να υπάρχουν 3 bins).
ΘΕΜΑ 2 Κατηγοριοποίηση (25 μονάδες)¶
Έστω η παρακάτω βάση δεδομένων πελατών μιας εταιρίας. Κάθε πελάτης χαρακτηρίζεται από τρία χαρακτηριστικά: την ηλικία, το φύλο και την τελευταία ενέργεια (δηλ. αν ο πελάτης ανταποκρίθηκε θετικά σε προηγούμενη καμπάνια). Το τελευταίο χαρακτηριστικό περιγράφει αν ο πελάτης ήταν πρόθυμος να αγοράσει ένα προϊόν στην τρέχουσα καμπάνια. Κατασκευάστε ένα δέντρο απόφασης για την κατηγοριοποίηση των πελατών σε Αγοραστές ή μη. Περιγράψτε αναλυτικά τη διαδικασία κατηγοριοποίησης ενός νέου πελάτη.
| Ανεξάρτητες μεταβλητές | Εξαρτημένη μεταβλητή | ||
|---|---|---|---|
| Ηλικία | Φύλο | Τελευταία ενέργεια | Αγορά |
| 35 | Άνδρας | Ναι | Όχι |
| 26 | Γυναίκα | Όχι | Όχι |
| 22 | Άνδρας | Ναι | Ναι |
| 63 | Άνδρας | Όχι | Ναι |
| 47 | Γυναίκα | Όχι | Όχι |
| 54 | Άνδρας | Όχι | Όχι |
| 27 | Γυναίκα | Ναι | Ναι |
| 38 | Γυναίκα | Όχι | Ναι |
| 42 | Γυναίκα | Ναι | Ναι |
| 19 | Άνδρας | Όχι | Όχι |
ΘΕΜΑ 3 Ανάλυση Χρονικών και Χωρικών Δεδομένων (18 μονάδες)¶
α) Χρησιμοποιήστε τη μέθοδο Dynamic Time Warping (DTW) για τον υπολογισμό της απόστασης των χρονοσειρών Χ = {2,5,3,4} και Υ = {2,3,6,2}. Εντοπίστε το Warping Path για τις χρονοσειρές Χ και Υ.
β) Ποια είναι τα βασικά είδη ερωτήσεων σε χωρικά δεδομένα; Δώστε τα αναλυτικά;
γ) Δώστε τον μαθηματικό τύπο των τεχνικών για τον υπολογισμό της dis(A,B) όπου Α και Β είναι δύο μη σημειακά αντικείμενα.
ΘΕΜΑ 4 Ομαδοποίηση/Κανόνες συσχέτισης (25 μονάδες)¶
α. Περιγράψτε τεχνικές αρχικοποίησης του αλγορίθμου k-means και εξηγήστε τη σημασία
που έχει μία καλή αρχικοποίηση για την αποτελεσματική απόδοση του αλγορίθμου. Eξηγήστε επίσης πως μπορούμε να επιταχύνουμε την ταχύτητα σύγκλισης με δεδομένη μία αρχική επιλογή κέντρων.
- β. Εξηγήστε πως θα μπορούσαμε στην παραγωγή κανόνων συσχέτισης να ενσωματώσουμε και γνώση πεδίου (οντολογίες) και αρνητικές συσχετίσεις. Περιγράψτε τη βασική ιδέα πίσω από την έννοια ποσοτικοί κανόνες συσχέτισης. Τι εννοούμε και πως θα μπορούσαν να υπολογιστούν με χρήση κλασσικών αλγοριθμικών σχημάτων.
ΘΕΜΑ 5 (25 μονάδες) Θεωρήστε τον ακόλουθο πίνακα:
| Transaction ID | Items Bought |
|---|---|
| 1 | CE |
| 2 | ABD |
| 3 | ABDE |
| 4 | BD |
| 5 | CD |
| 6 | ABD |
| 7 | AD |
| 8 | ABE |
| 9 | CDE |
| 10 | ADE |
-
όπου minsup=20% (ή 2 αν ορίσουμε το κατώφλι σαν πλήθος συναλλαγών και όχι σαν ποσοστό.
-
α. Στο ανωτέρω σύνολο στοιχείων εφαρμόστε τον αλγόριθμο Εclat και επιδείξτε το αποτέλεσμα εκτέλεσης (o Eclat έχει διδαχθεί στο μάθημα και αναφέρεται και στις διαφάνειες του μαθήματος τις σχετικές με κανόνες συσχέτισης και στο online βιβλίο του eclass των Zaki, Meira).
-
β. Ποια είναι τα σημεία στα οποία υπερτερεί ο Εclat του Apriori;
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06-b¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
ΘΕΜΑ 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ταξινομημένα δεδομένα: \(4,8,9,15,18,20,28,30,33,35,36,38,39,40\). Για εξομάλυνση χρησιμοποιώ αντικατάσταση με τον μέσο κάθε bin.
1) Binning ίσου πλάτους (equal-width), 3 bins: εύρος \(40-4=36\), πλάτος \(36/3=12\). - \(B_1=[4,16)\): \(\{4,8,9,15\}\), μέσος \(=(4+8+9+15)/4=9\). - \(B_2=[16,28)\): \(\{18,20\}\), μέσος \(=(18+20)/2=19\). - \(B_3=[28,40]\): \(\{28,30,33,35,36,38,39,40\}\), μέσος \(=279/8=34.875\).
Εξομαλυμένα: \(9,9,9,9,19,19,34.875,34.875,34.875,34.875,34.875,34.875,34.875,34.875\).
2) Binning ίσης συχνότητας (equal-frequency), 3 bins: με \(14\) τιμές χρησιμοποιώ πλήθη \(5,5,4\). - \(B_1=\{4,8,9,15,18\}\), μέσος \(=54/5=10.8\). - \(B_2=\{20,28,30,33,35\}\), μέσος \(=146/5=29.2\). - \(B_3=\{36,38,39,40\}\), μέσος \(=153/4=38.25\).
Εξομαλυμένα: \(10.8,10.8,10.8,10.8,10.8,29.2,29.2,29.2,29.2,29.2,38.25,38.25,38.25,38.25\).
(Αν χρησιμοποιηθεί άλλη αποδεκτή κατανομή πλήθους bins, π.χ. \(4,5,5\), αλλάζουν μόνο οι μέσοι των bins, όχι η μέθοδος.)
ΘΕΜΑ 2¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
Χρησιμοποιώ δέντρο απόφασης με κριτήριο το information gain και, για τη συνεχή ηλικία, κατωφλιοποίηση τύπου C4.5.
Αρχικό σύνολο: \(5\) «Ναι» και \(5\) «Όχι», άρα \(H(S)=1\).
Κέρδη πληροφορίας: Τελευταία ενέργεια \(\approx 0.1245\), Ηλικία (βέλτιστο κατώφλι) \(\approx 0.108\), Φύλο \(\approx 0.029\). Άρα ρίζα: Τελευταία ενέργεια.
Ένα σωστό δέντρο είναι το εξής:
Τελευταία ενέργεια
├─ Ναι
│ ├─ Φύλο = Γυναίκα -> Αγορά = Ναι
│ └─ Φύλο = Άνδρας
│ ├─ Ηλικία ≤ 28.5 -> Αγορά = Ναι
│ └─ Ηλικία > 28.5 -> Αγορά = Όχι
└─ Όχι
├─ Ηλικία ≤ 26.5 -> Αγορά = Όχι
└─ Ηλικία > 26.5
├─ Ηλικία ≤ 38.5 -> Αγορά = Ναι
└─ Ηλικία > 38.5
├─ Ηλικία ≤ 54.5 -> Αγορά = Όχι
└─ Ηλικία > 54.5 -> Αγορά = Ναι
Για νέο πελάτη: ξεκινάμε από τη ρίζα ελέγχοντας την «Τελευταία ενέργεια». Αν είναι «Ναι», ελέγχουμε το φύλο· αν είναι γυναίκα προβλέπουμε «Ναι», αν είναι άνδρας ελέγχουμε την ηλικία ως προς \(28.5\). Αν η «Τελευταία ενέργεια» είναι «Όχι», ελέγχουμε διαδοχικά την ηλικία ως προς \(26.5\), \(38.5\) και \(54.5\) και ακολουθούμε το αντίστοιχο κλαδί μέχρι το φύλλο. Η πρόβλεψη είναι η ετικέτα του φύλλου.
ΘΕΜΑ 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α) Χρησιμοποιώ κόστος \(d(x_i,y_j)=|x_i-y_j|\) και αναδρομή [ D(i,j)=|x_i-y_j|+\min{D(i-1,j),D(i,j-1),D(i-1,j-1)}. ] Ο πίνακας \(D\) είναι: [ \begin{pmatrix} 0&1&5&5\ 3&2&2&5\ 4&2&5&3\ 6&3&4&5 \end{pmatrix}. ] Άρα η απόσταση DTW είναι [ DTW(X,Y)=D(4,4)=5. ] Ένα βέλτιστο warping path είναι: [ (1,1)\to(1,2)\to(2,3)\to(3,4)\to(4,4), ] δηλαδή τα ζεύγη [ (2,2),(2,3),(5,6),(3,2),(4,2). ] Το συνολικό κόστος είναι \(0+1+1+1+2=5\).
β) Βασικά είδη ερωτήσεων σε χωρικά δεδομένα: - Range query (ερώτηση εύρους/περιοχής): εύρεση όλων των αντικειμένων που βρίσκονται μέσα ή τέμνουν μια περιοχή \(Q\). Ειδική περίπτωση είναι το ορθογώνιο window query. - Point query / point location: εύρεση του αντικειμένου ή της περιοχής που περιέχει ένα δεδομένο σημείο. - Nearest-neighbor query (πλησιέστερου γείτονα): εύρεση του αντικειμένου με τη μικρότερη απόσταση από σημείο ή περιοχή· γενικεύσεις είναι τα \(k\)-NN, reverse NN, continuous NN. - Distance range query: εύρεση όλων των αντικειμένων σε απόσταση μικρότερη από δοσμένο κατώφλι από ένα σημείο/αντικείμενο. - Spatial join: συνένωση δύο χωρικών συνόλων με βάση χωρικό κατηγόρημα, π.χ. «όλα τα ζεύγη που τέμνονται/περιέχονται/απέχουν λιγότερο από \(d\)». - Spatial aggregate queries: υπολογισμός συναθροίσεων (count, sum, avg κ.λπ.) ανά περιοχή ή για αντικείμενα μέσα σε περιοχή. - Similarity/trajectory queries: εύρεση αντικειμένων ή τροχιών με παρόμοιο σχήμα/θέση/κίνηση, με μέτρα όπως Hausdorff, DTW, Fréchet.
γ) Για μη σημειακά αντικείμενα \(A,B\) και απόσταση σημείων \(d(a,b)\): - Ελάχιστη απόσταση: [ d_{\min}(A,B)=\min_{a\in A,\ b\in B} d(a,b). ] - Μέγιστη απόσταση: [ d_{\max}(A,B)=\max_{a\in A,\ b\in B} d(a,b). ] - Απόσταση κέντρων (centroid distance): [ d_c(A,B)=d(c_A,c_B),\qquad c_A=\frac{1}{|A|}\sum_{a\in A}a,\quad c_B=\frac{1}{|B|}\sum_{b\in B}b. ] - Απόσταση Hausdorff: [ d_H(A,B)=\max\left{\sup_{a\in A}\inf_{b\in B}d(a,b),\ \sup_{b\in B}\inf_{a\in A}d(a,b)\right}. ] Για ορθογώνια ή MBRs χρησιμοποιούνται επίσης οι παραλλαγές ελάχιστης/μέγιστης απόστασης με βάση τις συντεταγμένες των ορίων τους.
ΘΕΜΑ 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α) Αρχικοποίηση k-means. Συνήθεις τεχνικές: - Τυχαία επιλογή \(k\) σημείων/παρατηρήσεων ως αρχικά κέντρα. Απλή αλλά ασταθής. - k-means++: το πρώτο κέντρο επιλέγεται τυχαία· κάθε επόμενο επιλέγεται με πιθανότητα ανάλογη του τετραγώνου της απόστασής του από το πλησιέστερο ήδη επιλεγμένο κέντρο. Μειώνει πολύ την πιθανότητα κακής τοπικής λύσης. - Farthest-first / max-min: διαλέγουμε διαδοχικά τα πιο απομακρυσμένα σημεία από τα ήδη επιλεγμένα κέντρα. - Ιεραρχική/συσσωρευτική προ-ομαδοποίηση σε δείγμα και χρήση των κέντρων των ομάδων ως αρχικών κέντρων. - Δειγματοληψία και επαναλήψεις (π.χ. Bradley–Fayyad): τρέχουμε k-means σε δείγματα και κρατάμε την καλύτερη λύση ή τα μεγαλύτερα clusters. - Τεχνικές βασισμένες σε PCA/πυκνότητα/πλέγμα για πιο αντιπροσωπευτικά αρχικά κέντρα.
Καλή αρχικοποίηση είναι σημαντική γιατί η αντικειμενική συνάρτηση του k-means δεν είναι κυρτή και ο αλγόριθμος συγκλίνει σε τοπικό ελάχιστο. Καλά κατανεμημένα κέντρα αποφεύγουν κενά ή πολύ άνισα clusters, μειώνουν τις επαναλήψεις και δίνουν πιο σταθερή και ποιοτική ομαδοποίηση.
Με δεδομένη αρχική επιλογή κέντρων, η σύγκλιση επιταχύνεται με: - χρήση τριγωνικών ανισοτήτων και έλεγχο φραγμάτων (Elkan, Hamerly) ώστε να αποφεύγονται περιττοί υπολογισμοί αποστάσεων, - χρήση kd-trees/ball trees για ταχύτερη εύρεση πλησιέστερου κέντρου, - mini-batch ή δειγματοληψία, - διατήρηση αραιών αναπαραστάσεων, μείωση διαστάσεων ή PCA, - τερματισμό όταν η μετακίνηση κέντρων είναι μικρότερη από ανοχή \(\varepsilon\), - μαζικές/διανυσματικές ενημερώσεις και caching αποστάσεων.
β) Γνώση πεδίου (οντολογίες) σε κανόνες συσχέτισης. Η βασική ιδέα είναι να μην αντιμετωπίζονται τα είδη ως εντελώς ανεξάρτητα, αλλά να αξιοποιείται ιεραρχία/οντολογία. Π.χ. αν το «μήλο» και το «αχλάδι» ανήκουν στο «φρούτο», προσθέτουμε γενικευμένα στοιχεία ή χρησιμοποιούμε κανόνες πολλαπλών επιπέδων. Το support ενός γενικευμένου στοιχείου είναι το πλήθος συναλλαγών που περιέχουν τουλάχιστον έναν από τους απογόνους του. Έτσι παράγονται κανόνες όπως «φρούτο \(\to\) γάλα» και φιλτράρονται τετριμμένοι/υπερ-γενικοί κανόνες.
Αρνητικές συσχετίσεις. Επιτρέπουμε στοιχεία της μορφής \(\neg x\). Για κανόνα \(X\to\neg Y\): [ supp(X\cup\neg Y)=supp(X)-supp(X\cup Y), ] [ conf(X\to\neg Y)=\frac{supp(X)-supp(X\cup Y)}{supp(X)}. ] Γενικότερα, για ένα σύνολο \(Z\) που περιέχει θετικά και αρνητικά στοιχεία, το support είναι το πλήθος συναλλαγών που περιέχουν όλα τα θετικά και δεν περιέχουν κανένα από τα αρνητικά. Επειδή χάνεται η απλή μονοτονία του Apriori, χρησιμοποιούνται επεκτάσεις: πρώτα εξορύσσονται θετικά συχνά σύνολα και μετά παράγονται αρνητικά, ή ορίζονται κατάλληλα φίλτρα/πολλαπλά κατώφλια και μέτρα ενδιαφέροντος για να αποφευχθούν παραπλανητικοί αρνητικοί κανόνες.
Ποσοτικοί κανόνες συσχέτισης. Είναι κανόνες που περιέχουν ποσοτικά χαρακτηριστικά, π.χ. [ Age\in[20,30]\land Gender=F \Rightarrow Income>50K. ] Βασική ιδέα: διακριτοποιούμε κάθε ποσοτικό χαρακτηριστικό σε διαστήματα (equal-width, equal-frequency, clustering κ.λπ.), μετατρέπουμε κάθε διάστημα σε δυαδικό «item» και εφαρμόζουμε κλασικούς αλγορίθμους συσχέτισης (Apriori, FP-Growth, Eclat). Υπολογίζουμε support/confidence των κανόνων στο αρχικό ή στο μετασχηματισμένο σύνολο. Με παρόμοιο τρόπο ενσωματώνονται οντολογίες (προσθήκη γενικευμένων items) και αρνήσεις (προσθήκη αρνητικών items με κατάλληλο υπολογισμό support).
ΘΕΜΑ 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Με \(minsup=20\%\) και \(10\) συναλλαγές, το κατώφλι είναι \(2\) συναλλαγές. Τα vertical tidsets (Eclat) είναι: [ \begin{aligned} A&={2,3,6,7,8,10}, &B&={2,3,4,6,8},\ C&={1,5,9}, &D&={2,3,4,5,6,7,9,10},\ E&={1,3,8,9,10}. \end{aligned} ] Όλα τα singleton είναι συχνά: \(A:6,\ B:5,\ C:3,\ D:8,\ E:5\).
α) Εκτέλεση Eclat. Με τομές tidsets προκύπτουν τα εξής συχνά σύνολα: - Συχνά 2-σύνολα: [ \begin{aligned} AB&:{2,3,6,8},& supp=4,\ AD&:{2,3,6,7,10},& supp=5,\ AE&:{3,8,10},& supp=3,\ BD&:{2,3,4,6},& supp=4,\ BE&:{3,8},& supp=2,\ CD&:{5,9},& supp=2,\ CE&:{1,9},& supp=2,\ DE&:{3,9,10},& supp=3. \end{aligned} ] Τα \(AC\) και \(BC\) έχουν support \(0\), άρα απορρίπτονται.
- Συχνά 3-σύνολα: [ \begin{aligned} ABD&:{2,3,6},& supp=3,\ ABE&:{3,8},& supp=2,\ ADE&:{3,10},& supp=2. \end{aligned} ] Τα \(BDE\), \(CDE\) και \(ABDE\) έχουν support \(1\), άρα δεν είναι συχνά.
Συνολικά συχνά σύνολα: [ \begin{aligned} &1\text{-itemsets}: A,B,C,D,E,\ &2\text{-itemsets}: AB,AD,AE,BD,BE,CD,CE,DE,\ &3\text{-itemsets}: ABD,ABE,ADE. \end{aligned} ] Δεν υπάρχουν συχνά 4-itemsets.
β) Πλεονεκτήματα Eclat έναντι Apriori. - Χρησιμοποιεί κάθετη διάταξη δεδομένων (tidsets) και υπολογίζει supports με τομές συνόλων, χωρίς επαναλαμβανόμενες σαρώσεις της βάσης όπως ο Apriori. - Αποφεύγει την πλήρη, επίπεδη παραγωγή υποψηφίων του Apriori· χρησιμοποιεί depth-first αναζήτηση και κλάσεις ισοδυναμίας προθεμάτων. - Είναι συνήθως ταχύτερος, ειδικά όταν τα tidsets είναι διαχειρίσιμα, γιατί μειώνει δραστικά το κόστος μέτρησης support. - Μπορεί να συνδυαστεί με βελτιστοποιήσεις όπως diffsets, και κ送B pruning πάνω στις κλάσεις προθεμάτων.