Εξόρυξη Δεδομένων και Μηχανική Μάθηση — Σεπτέμβριος 2021¶
Μεταγραφή από το κείμενο της τυπωμένης εκφώνησης ex_2021.pdf (2 σελίδες).
ex_2021.pdf¶
ΕΞΟΡΥΞΗ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ ΜΑΘΗΣΗΣ ΔΙΑΡΚΕΙΑ ΩΡΑΣ: 1:30¶
ΘΕΜΑ 1 (25%)¶
- α. Θεωρήστε τον ακόλουθο πίνακα:
| Transaction ID | Items Bought |
|---|---|
| 1 | {a,e} |
| 2 | {a,d, e} |
| 3 | {a, b,c,e} |
| 4 | {a,b,c,d} |
| 5 | {b,c} |
| 6 | {b} |
| 7 | {a,b,c} |
| 8 | {a,d} |
| 9 | {a,e} |
| 10 | {a,b,d,e} |
όπου minsup=20%.
Στο ανωτέρω σύνολο στοιχείων εφαρμόστε τον αλγόριθμο Εclat και επιδείξτε το αποτέλεσμα εκτέλεσης (o Eclat έχει διδαχθεί στο μάθημα και αναφέρεται και στις διαφάνειες του μαθήματος τις σχετικές με κανόνες συσχέτισης και στο online βιβλίο του eclass των Zaki, Meira).
- β. Οι χωρικές δομές δεδομένων είναι ιεραρχικές δομές αποθήκευσης με τη δυνατότητα να χειρίζονται αντικείμενα σε πολυδιάστατους γεωμετρικούς χώρους και να απαντούν σε ερωτήματα γεωμετρικής φύσεως (λ.χ. αναφοράς αντικειμένων που εμπεριέχονται σε περιοχές ερώτησης). Εξηγήστε τη χρησιμότητα των δομών αυτών σε αλγόριθμους συσταδοποίησης.
ΘΕΜΑ 2 (25%)¶
α. Χρησιμοποιήστε τον ακόλουθο πίνακα ομοιότητας για να πραγματοποιήσετε single link hierarchical clustering. Επιδείξτε τα αποτελέσματά σας σχεδιάζοντας ένα δενδρόγραμμα.
| p1 | p2 | p3 | p4 | p5 | |
|---|---|---|---|---|---|
| p1 | 1.00 | 0.6 | 0.2 | 0.15 | 0.2 |
| p2 | 0.6 | 1.00 | 0.9 | 0.5 | 0.9 |
| p3 | 0.2 | 0.9 | 1.00 | 0.4 | 0.3 |
| p4 | 0.15 | 0.5 | 0.4 | 1.00 | 0.1 |
| p5 | 0.2 | 0.9 | 0.3 | 0.1 | 1.00 |
- β. O αλγόριθμος k-means παράγει συστάδες που εκ φύσεως έχουν συμπαγές σχήμα. Επιδείξτε, πως ο αλγόριθμος μπορεί να τροποποιηθεί ώστε να παράγει και συστάδες με ελλειπτικό σχήμα.
ΘΕΜΑ 3 - Προεπεξεργασία Δεδομένων (15%)¶
Α) Ένα από τα στάδια της προεπεξεργασίας είναι η συμπλήρωση των ελλειπών τιμών. Για τη συμπλήρωση αυτών των τιμών έχουν προταθεί διάφορες τεχνικές. Συμπληρώστε τις 5 ελλειπείς πλειάδες, με τρεις διαφορετικές μεθόδους:
| Class | **Attribute_1 ** | **Attribute_2 ** | **Attribute_3 ** | |
|---|---|---|---|---|
| Item_1 | 0 | 119 | 34 | |
| Item_2 | 0 | 143 | 5 |
| Item_3 | 0 | 128 | 7 | 42 |
|---|---|---|---|---|
| Item_4 | 1 | 153 | 35 | |
| Item_5 | 1 | 121 | 3 |
Β) Αναφέρετε επιπλέον δυο τεχνικές συμπλήρωσης ελλειπών τιμών.
ΘEMA 4 - Χρονοσειρές (15%)¶
α. Αναφέρετε ομοιότητες και διαφορές μεταξύ της Ευκλείδειας απόστασης και της τεχνικής της Δυναμικής Παραμόρφωσης Χρόνου (Dynamic Time Warping) ως μετρικές ομοιότητας μεταξύ χρονοσειρών.
β. Πως μπορεί να χρησιμοποιηθεί ένα Βιβλίο Κώδικα (CodeBook) για τη σύγκριση δύο χρονοσειρών;
ΘEMA 5 - Κατηγοριοποίηση (20%)¶
Για την πιστοποίηση κατά ISO ενός τραπεζικού ομίλου συνυπολογίζονται πολλές παράμετροι μεταξύ των οποίων είναι ο μέσος χρόνος εξυπηρέτησης των πελατών και η ποιότητα της εξυπηρέτησης. Ο ακόλουθος πίνακας παρουσιάζει τα αποτελέσματα που προέκυψαν κατά τον έλεγχο πιστοποίησης σε διάφορους τραπεζικούς ομίλους. Το γνώρισμα ποιότητα εξυπηρέτησης πελατών είναι ένα διάνυσμα μήκους 2, το οποίο αντιπροσωπεύει την αξιολόγηση δύο εμπειρογνωμόνων. Οι τράπεζες, ανάλογα με τις τιμές των χαρακτηριστικών τους, κατηγοριοποιούνται σε 2 κλάσεις (πιστοποίηση ISO ή όχι).
| Τράπεζα | Μέσος Χρόνος Εξυπηρέτησης Πελατών (σε min) |
Ποιότητα Εξυπηρέτησης Πελατών |
ISO |
|---|---|---|---|
| Τ1 | 3 | [8,6] | NAI |
| Τ2 | 7 | [3,4] | OXI |
| Τ3 | 2 | [10,10] | NAI |
| Τ4 | 5 | [4,3] | OXI |
| Τ5 | 10 | [6,8] | OXI |
Με βάση τις πλειάδες του παραπάνω πίνακα και χρησιμοποιώντας τον αλγόριθμο κατηγοριοποίησης k-πλησιέστερων γειτόνων (k-NN), όπου k=3, να κατηγοριοποιήσετε τις τράπεζες Τα και Τβ i. χρησιμοποιώντας μόνο το γνώρισμα «μέσος χρόνος εξυπηρέτησης» για τον υπολογισμό της ομοιότητας και θεωρώντας μέτρο απόστασης την απόλυτη απόσταση
- ii. χρησιμοποιώντας μόνο το γνώρισμα «ποιότητα εξυπηρέτησης» για τον υπολογισμό της ομοιότητας και θεωρώντας μέτρο ομοιότητας τη μετρική συνημίτονου .
| Τράπεζα | Μέσος Χρόνος Εξυπηρέτησης Πελατών (σε min) |
Ποιότητα Εξυπηρέτησης Πελατών |
|---|---|---|
| Τα | 3 | [10,10] |
| Τβ | 8 | [8,9] |
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Το κατώφλι είναι \(minsup=20\%\cdot 10=2\) συναλλαγές. Ο Eclat χρησιμοποιεί κάθετα σύνολα transactions IDs (tidsets).
Αρχικά tidsets:
- \(a:\{1,2,3,4,7,8,9,10\}\) (8)
- \(b:\{3,4,5,6,7,10\}\) (6)
- \(c:\{3,4,5,7\}\) (4)
- \(d:\{2,4,8,10\}\) (4)
- \(e:\{1,2,3,9,10\}\) (5)
Με τομές tidsets προκύπτουν τα συχνά σύνολα:
- 1-itemsets: \(\{a\}:8,\ \{b\}:6,\ \{c\}:4,\ \{d\}:4,\ \{e\}:5\)
- 2-itemsets:
\(\{a,b\}:4,\ \{a,c\}:3,\ \{a,d\}:4,\ \{a,e\}:5,\ \{b,c\}:4,\ \{b,d\}:2,\ \{b,e\}:2,\ \{d,e\}:2\)
- 3-itemsets:
\(\{a,b,c\}:3,\ \{a,b,d\}:2,\ \{a,b,e\}:2,\ \{a,d,e\}:2\)
- Δεν υπάρχουν συχνά 4-itemsets ή 5-itemsets.
Ενδεικτικές τομές: - \(a\cap b=\{3,4,7,10\}\). - \((a\cap b)\cap c=\{3,4,7\}\) άρα \(\{a,b,c\}:3\). - \(a\cap d=\{2,4,8,10\}\) και \((a\cap d)\cap e=\{2,10\}\) άρα \(\{a,d,e\}:2\). - \(b\cap d=\{4,10\}\) άρα \(\{b,d\}:2\)· επίσης \((b\cap d)\cap e=\{10\}\) οπότε το \(\{b,d,e\}\) απορρίπτεται.
Άρα τα συχνά itemsets είναι τα παραπάνω \(5+8+4=17\) σύνολα. Μέγιστα συχνά σύνολα: \(\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,d,e\}\).
β. Οι χωρικές δομές δεδομένων (π.χ. \(kd\)-trees, \(R\)-trees, quadtrees, grids) επιταχύνουν ερωτήματα εύρους, εύρεσης πλησιέστερων γειτόνων και χωρικών συνενώσεων. Σε αλγορίθμους συσταδοποίησης βοηθούν στην ταχύτερη εύρεση γειτόνων/πυκνότητας (π.χ. DBSCAN, OPTICS, \(k\)-NN clustering), στον υπολογισμό περιοχών ερωτήματος, στην αποφυγή περιττών συγκρίσεων όλων-με-όλα και στην κλιμάκωση σε μεγάλα πολυδιάστατα σύνολα.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Με single link και πίνακα ομοιότητας, ενώνουμε τις συστάδες με τη μέγιστη ομοιότητα μεταξύ στοιχείων τους. Οι μέγιστες αρχικές ομοιότητες είναι \(s(p2,p3)=0.9\) και \(s(p2,p5)=0.9\). Επιλέγοντας πρώτα τη \((p2,p3)\), έχουμε:
- \((p2,p3)\) στο \(0.90\).
- Το \(p5\) έχει ομοιότητα με το \(\{p2,p3\}\): \(\max(0.9,0.3)=0.9\), άρα ενώνεται στο \(0.90\).
- Το \(p1\) έχει ομοιότητα με το \(\{p2,p3,p5\}\): \(\max(0.6,0.2,0.2)=0.6\), άρα ενώνεται στο \(0.60\).
- Το \(p4\) έχει ομοιότητα με το \(\{p1,p2,p3,p5\}\): \(\max(0.15,0.5,0.4,0.1)=0.5\), άρα ενώνεται στο \(0.50\).
Με άλλη επιλογή στην ισοπαλία, π.χ. πρώτα \((p2,p5)\), προκύπτει ισοδύναμο δενδρόγραμμα: \(((((p2,p5),p3),p1),p4)\).
Σε μορφή δενδρογράμματος με στάθμες ομοιότητας:
p2 ┐
├─0.90─┐
p3 ┘ │
p5 ────────┘ 0.90
│
p1 ────────┘ 0.60
│
p4 ────────┘ 0.50
β. Το πρόβλημα του \(k\)-means είναι ότι χρησιμοποιεί Ευκλείδεια απόσταση, άρα παράγει κυρτές/σφαιρικές περιοχές. Για ελλειπτικές συστάδες μπορεί να τροποποιηθεί ώστε η ανάθεση να γίνεται με απόσταση Mahalanobis ανά συστάδα: [ (x-\mu_j)^T\Sigma_j^{-1}(x-\mu_j), ] όπου \(\Sigma_j\) είναι ο πίνακας συνδιακύμανσης της συστάδας \(j\). Σε κάθε επανάληψη ενημερώνονται τόσο τα κέντρα \(\mu_j\) όσο και οι πίνακες \(\Sigma_j\). Αυτό ισοδυναμεί με hard assignment έκδοση μείγματος Gaussians με πλήρεις πίνακες συνδιακύμανσης (EM με σκληρή ανάθεση), επιτρέποντας επιμήκεις/ελλειπτικές συστάδες.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Από τον πίνακα υπάρχουν 4 ελλιπείς τιμές: Item_1.Attribute_2, Item_2.Attribute_3, Item_4.Attribute_2, Item_5.Attribute_3. Χρησιμοποιώ τρεις μεθόδους.
Μέθοδοι:
1. Γενικός μέσος όρος κάθε χαρακτηριστικού (από τις υπάρχουσες τιμές):
\(\bar{x}_{A2}=(5+7+3)/3=5\), \(\bar{x}_{A3}=(34+42+35)/3=37\).
2. Μέσος όρος ανά κλάση:
Κλάση 0: \(\bar{x}_{A2}^{(0)}=(5+7)/2=6\), \(\bar{x}_{A3}^{(0)}=(34+42)/2=38\).
Κλάση 1: \(\bar{x}_{A2}^{(1)}=3\), \(\bar{x}_{A3}^{(1)}=35\).
3. Γενική διάμεσος κάθε χαρακτηριστικού:
\(median(A2)=5\), \(median(A3)=35\).
Άρα: | Κελί | Μέθοδος 1: γενικός μέσος | Μέθοδος 2: μέσος ανά κλάση | Μέθοδος 3: γενική διάμεσος | |---|---:|---:|---:| | Item_1.Attribute_2 | 5 | 6 | 5 | | Item_2.Attribute_3 | 37 | 38 | 35 | | Item_4.Attribute_2 | 5 | 3 | 5 | | Item_5.Attribute_3 | 37 | 35 | 35 |
Οι υπόλοιπες τιμές παραμένουν ως έχουν.
Β. Επιπλέον τεχνικές συμπλήρωσης ελλιπών τιμών: - Συμπλήρωση με παλινδρόμηση (regression imputation), χρησιμοποιώντας τα άλλα χαρακτηριστικά ως ανεξάρτητες μεταβλητές. - Συμπλήρωση με \(k\) πλησιέστερους γείτονες (\(k\)-NN imputation) ή hot-deck imputation. - Πολλαπλή συμπλήρωση (multiple imputation) ή μέθοδοι βασισμένες σε EM.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Ομοιότητες Ευκλείδειας απόστασης και DTW: - Και οι δύο είναι μετρικές/βαθμοί απόστασης μεταξύ χρονοσειρών και μπορούν να χρησιμοποιηθούν σε ταξινόμηση, συσταδοποίηση και αναζήτηση ομοίων χρονοσειρών. - Και οι δύο απαιτούν συνήθως κανονικοποίηση κλίμακας/μετατόπισης όταν συγκρίνονται χρονοσειρές διαφορετικού πλάτους. - Η Ευκλείδεια απόσταση είναι ειδική περίπτωση χωρίς στρέβλωση του χρόνου.
Διαφορές: - Η Ευκλείδεια υπολογίζει διαφορές στις ίδιες χρονικές θέσεις, άρα απαιτεί ίσο μήκος και καλή ευθυγράμμιση. - Η DTW επιτρέπει μη γραμμική ευθυγράμμιση/χρονική στρέβλωση, επαναλήψεις χρονικών σημείων και χειρίζεται καλύτερα μετατοπίσεις φάσης ή διαφορετικές ταχύτητες. - Υπολογιστικά, η Ευκλείδεια είναι \(O(n)\) για ίσο μήκος, ενώ η DTW είναι συνήθως \(O(nm)\) ή \(O(n^2)\) με δυναμικό προγραμματισμό. - Η DTW είναι πιο ευαίσθητη σε υπερβολική στρέβλωση και συχνά δεν ικανοποιεί την τριγωνική ανισότητα, ενώ η Ευκλείδεια είναι μετρική.
β. Ένα βιβλίο κώδικα (codebook) περιέχει αντιπροσωπευτικά πρότυπα/κωδικολέξεις, π.χ. κέντρα συστάδων από υποακολουθίες χρονοσειρών. Για σύγκριση δύο χρονοσειρών: 1. Τεμαχίζουμε κάθε χρονοσειρά σε παράθυρα/υποακολουθίες. 2. Αναθέτουμε κάθε παράθυρο στην πλησιέστερη κωδικολέξη του codebook (vector quantization). 3. Μετατρέπουμε έτσι κάθε χρονοσειρά σε ακολουθία συμβόλων ή σε ιστόγραμμα συχνοτήτων κωδικολέξεων. 4. Συγκρίνουμε τις δύο χρονοσειρές με απόσταση ακολουθιών (π.χ. edit distance, DTW πάνω στα σύμβολα) ή με ομοιότητα ιστογραμμάτων (π.χ. cosine, Euclidean στα διανύσματα συχνοτήτων).
Έτσι το codebook μειώνει τη διάσταση, αφαιρεί θόρυβο και επιτρέπει σύγκριση ακολουθιών με διαφορετικό μήκος/χρονικές παραμορφώσεις.
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Δεδομένα εκπαίδευσης: - \(T_1:(x=3,\ q=[8,6])\), κλάση NAI. - \(T_2:(7,[3,4])\), OXI. - \(T_3:(2,[10,10])\), NAI. - \(T_4:(5,[4,3])\), OXI. - \(T_5:(10,[6,8])\), OXI.
i. Μόνο μέσος χρόνος, απόλυτη απόσταση, \(k=3\).
Για \(T_\alpha\) με χρόνο \(3\): [ |3-3|=0\ (T_1,\text{NAI}),\quad |3-2|=1\ (T_3,\text{NAI}),\quad |3-5|=2\ (T_4,\text{OXI}), ] οι τρεις πλησιέστεροι είναι \(T_1,T_3,T_4\): ψήφοι NAI, NAI, OXI. Άρα \(T_\alpha\to\) NAI.
Για \(T_\beta\) με χρόνο \(8\): [ |8-7|=1\ (T_2,\text{OXI}),\quad |8-10|=2\ (T_5,\text{OXI}),\quad |8-5|=3\ (T_4,\text{OXI}), ] οι τρεις πλησιέστεροι είναι \(T_2,T_5,T_4\): όλοι OXI. Άρα \(T_\beta\to\) OXI.
ii. Μόνο ποιότητα εξυπηρέτησης, ομοιότητα συνημίτονου, \(k=3\).
Για \(T_\alpha=[10,10]\): [ s(T_\alpha,T_3)=1\quad(\text{NAI}), ] και [ s(T_\alpha,T_1)=s(T_\alpha,T_2)=s(T_\alpha,T_4)=s(T_\alpha,T_5) =\frac{7}{5\sqrt2}\approx 0.98995. ] Άρα πρώτος είναι ο \(T_3\) και ακολουθεί ισοπαλία τεσσάρων σημείων για τις υπόλοιπες δύο θέσεις. Με τη συνήθη ντετερμινιστική επίλυση ισοπαλίας (σειρά εμφάνισης/μικρότερο index) επιλέγονται \(T_3,T_1,T_2\), δηλαδή NAI, NAI, OXI, οπότε \(T_\alpha\to\) NAI. Χωρίς συγκεκριμένο tie-breaking, η κλάση του \(T_\alpha\) δεν ορίζεται μονοσήμαντα (με άλλη επιλογή από την τετράδα θα μπορούσε να προκύψει OXI).
Για \(T_\beta=[8,9]\): [ s(T_\beta,T_3)=\frac{17}{\sqrt{290}}\approx0.99827\quad(\text{NAI}), ] [ s(T_\beta,T_2)=s(T_\beta,T_5)=\frac{12}{\sqrt{145}}\approx0.99655\quad(\text{OXI}), ] [ s(T_\beta,T_1)=s(T_\beta,T_4)=\frac{59}{5\sqrt{145}}\approx0.9800. ] Οι τρεις πλησιέστεροι είναι \(T_3,T_2,T_5\): NAI, OXI, OXI. Άρα \(T_\beta\to\) OXI.
Συνοπτικά: - \(T_\alpha\): (i) NAI, (ii) NAI υπό τη δηλωθείσα επίλυση ισοπαλίας· αλλιώς μη μονοσήμαντο. - \(T_\beta\): (i) OXI, (ii) OXI.