Εξόρυξη Δεδομένων και Αλγόριθμοι Μάθησης — Σεπτέμβριος 2020¶
thema_2_2020.pdf¶
ΕΞΟΡΥΞΗ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ ΜΑΘΗΣΗΣ ΕΞΕΤΑΣΤΙΚΗ ΣΕΠΤΕΜΒΡΙΟΥ ΔΙΔΑΣΚΟΝΤΕΣ: Β. ΜΕΓΑΛΟΟΙΚΟΝΟΜΟΥ, Χ. ΜΑΚΡΗΣ ΔΙΑΡΚΕΙΑ ΩΡΑΣ: 1:30 (1)¶
ΘΕΜΑ 1 (2,5)¶
-
α. Περιγράψτε τεχνικές αρχικοποίησης του k-means. Εξηγήστε πως χωρικές δομές δεδομένων (δομές δεδομένων που απαντάνε ερωτήματα χωρικών περιορισμών) μπορούν να είναι χρήσιμες στη διαδικασία ομαδοποίησης.
-
β. Στο πρόβλημα της δυναμικής ομαδοποίησης, έχουμε να χειριστούμε μία συλλογή από συστάδες για ένα σύνολο στοιχείων που δυναμικά ενημερώνεται με ενθέσεις και διαγραφές συναλλαγών. Εξηγείστε τα προβλήματα που ανακύπτουν κατά την εφαρμογή των κλασσικών αλγορίθμων σε ένα τέτοιο σενάριο χρήσης και προτείνεται τρόπους αντιμετώπισης τους.
ΘΕΜΑ 2 (2,5)¶
-
a. Παρουσιάστε τρόπους με τους οποίους η εξαγωγή κανόνων συσχέτισης θα μπορούσε να λάβει υπόψη της και τη διάταξη των στοιχείων σε μία συναλλαγή (αυτή η διάταξη θα μπορούσε να αναπαριστά την χρονική σειρά με την οποία πραγματοποιήθηκαν οι διάφορες ενέργειες, όπως συμβαίνει για παράδειγμα στις συναλλαγές στα αρχεία πρόσβασης σε ένα δικτυακό τόπο).
-
β. Θεωρήστε τον ακόλουθο πίνακα:
| Transaction ID | Items Bought |
|---|---|
| 1 | {a,b,e} |
| 2 | {a,d,e} |
| 3 | {a,c} |
| 4 | {c,d} |
| 5 | {b,c} |
| 6 | {a,c.d} |
| 7 | {a,d} |
| 8 | {b,d,e} |
| 9 | {b,c,d} |
| 10 | {b,d} |
όπου minsup=20%.
Στο ανωτέρω σύνολο στοιχείων εφαρμόστε τον αλγόριθμο Apriori επιδεικνύοντας την μορφή του Hash Tree μετά από κάθε βήμα.
ΘΕΜΑ 3 (1,5)¶
3.1) Για τη συμπλήρωση ελλιπών τιμών που υπάρχουν στα δεδομένα έχουν προταθεί διάφορες τεχνικές. Να αναφέρετε τρεις από αυτές.
3.2) Έστω τα ακόλουθα δεδομένα θερμοκρασίας (σεο C): 4,8,9,13,19,21,26,30,32,35,38,39 . Εφαρμόστε δύο διαφορετικές μεθόδους Binning για την εξομάλυνση των παραπάνω δεδομένων (σε κάθε μέθοδο που θα εφαρμόσετε, θα πρέπει να υπάρχουν 3 bins).
ΘΕΜΑ 4 (1)¶
Έστω η παρακάτω βάση δεδομένων με αστυνομικούς, η οποία περιέχει 8 παραδείγματα
εκπαίδευσης. Ο κάθε αστυνομικός μπορεί να είναι άνδρας ή γυναίκα (μεταβλητή κλάσης Gender). Οι 4 ανεξάρτητες μεταβλητές καθορίζουν την κλάση στην οποία θα κατηγοριοποιηθεί κάθε δείγμα. Με βάση τα δεδομένα του πίνακα, να κατηγοριοποιήσετε το δείγμα X = {Drew, blue-eyed, over 170 tall, has long hair} , χρησιμοποιώντας τον Naïve Bayesian Classifier.
| Ανεξάρτητες Μ | εταβλητές | Κλάση | ||
|---|---|---|---|---|
| Name | Over 170 cm | Eyes | Hair Length | Gender |
| Drew | No | Blue | Short | Male |
| Claudia | Yes | Brown | Long | Female |
| Drew | No | Blue | Long | Female |
| Drew | No | Blue | Long | Female |
| Alberto | Yes | Brown | Short | Male |
| Karin | No | Blue | Long | Female |
| Nina | Yes | Brown | Short | Female |
| Sergio | Yes | Blue | Long | Male |
ΘΕΜΑ 5 (2,5)¶
5.1) Χρησιμοποιήστε τη μέθοδο Dynamic Time Warping (DTW) για τον υπολογισμό της απόστασης των χρονοσειρών Χ = {1,5,4,3,2,4,5,4,3} και Υ = {1,5,2,2,4,2}. Εντοπίστε το Warping Path για τις χρονοσειρές Χ και Υ.
5.2) Περιγράψτε τη μέθοδο LCSS και δώστε ένα παράδειγμα εφαρμογής της.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Τεχνικές αρχικοποίησης του \(k\)-means: - Τυχαία επιλογή \(k\) σημείων ως αρχικών κέντρων (απλή, αλλά ευαίσθητη σε τοπικά ελάχιστα). - \(k\)-means++: επιλογή κέντρων με πιθανότητα ανάλογη του τετραγώνου της απόστασης από το πλησιέστερο ήδη επιλεγμένο κέντρο. - Farthest-first: διαδοχική επιλογή του σημείου που απέχει περισσότερο από τα ήδη επιλεγμένα κέντρα. - Ιεραρχική ομαδοποίηση/δειγματοληψία για αρχικά κέντρα. - Χρήση ποσοστημορίων, πυκνότητας ή PCA για πιο αντιπροσωπευτική αρχικοποίηση. - Επανάληψη με πολλαπλές τυχαίες αρχικοποιήσεις και επιλογή λύσης με ελάχιστο σφάλμα.
Οι χωρικές δομές δεδομένων, όπως \(kd\)-trees, \(R\)-trees, grids και vantage-point trees, βοηθούν: - στην ταχύτερη ανάθεση κάθε σημείου στο πλησιέστερο κέντρο, - σε ερωτήματα εύρους/πλησιέστερων γειτόνων για αρχικοποίηση ή πυκνοτική εκτίμηση, - στο κ送λάδεμα υποψήφιων κέντρων, - σε ενημερώσεις όταν τα δεδομένα αλλάζουν δυναμικά.
β. Στη δυναμική ομαδοποίηση με ενθέσεις/διαγραφές συναλλαγών, οι κλασικοί αλγόριθμοι αντιμετωπίζουν: - μεταβολή των στατιστικών και των κέντρων με κάθε ενημέρωση, - υψηλό κόστος επαναϋπολογισμού από την αρχή, - εξάρτηση από τη σειρά των δεδομένων και αστάθεια λύσης, - μεταβολή της κατανομής (concept drift), - διαγραφές που μπορεί να αδειάσουν ή να διασπάσουν συστάδες, - δυσκολία διατήρησης συνεπών ορίων/αναθέσεων.
Τρόποι αντιμετώπισης: - ενημέρωση επαρκών στατιστικών (πλήθος, άθροισμα, άθροισμα τετραγώνων) χωρίς αποθήκευση όλων των σημείων, - χρήση μικροσυστάδων και δομών τύπου CluStream, DenStream, BIRCH CF-trees, - παράθυρα ολίσθησης ή χρονική απομείωση παλιών δεδομένων, - περιοδική ή κατά-απαίτηση επανασυστάδωση, με διατήρηση σταθερότητας, - τοπικές ενημερώσεις, συγχωνεύσεις/διασπάσεις συστάδων, - τυχαία/αντιπροσωπευτικά δείγματα και χωρικές δομές για γρήγορη ανάθεση.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α. Για να ληφθεί υπόψη η διάταξη στοιχείων σε μία συναλλαγή/ακολουθία: - Μετάβαση από απλά itemsets σε ακολουθιακά πρότυπα (sequential patterns), π.χ. GSP, SPADE, PrefixSpan. - Θεώρηση κάθε στοιχείου μαζί με θέση/χρόνο, π.χ. \((item,t)\). - Κανόνες μορφής “αν συμβεί πρώτα το \(A\) και μετά το \(B\)”, με χρονικά παράθυρα ή περιορισμούς απόστασης. - Μοντέλα επεισοδίων (episodes), \(n\)-grams, Markov/μεταβατικές πιθανότητες. - Ανάλυση συνεδριών web logs, όπου η σειρά σελίδων έχει σημασία. - Χρήση περιορισμών τύπου before/after, sliding window, lag constraints.
β. Διορθώνω το προφανές τυπογραφικό της συναλλαγής 6 ως \(\{a,c,d\}\). Το ελάχιστο πλήθος υποστήριξης είναι \(0.20\cdot 10=2\).
Πλήθη 1-στοιχείων: [ \begin{array}{c|ccccc} \text{Στοιχείο} & a & b & c & d & e\\hline \text{Πλήθος} & 5 & 5 & 5 & 7 & 3 \end{array} ] Άρα \(L_1=\{a,b,c,d,e\}\).
Υποψήφια 2-στοιχεία και πλήθη: [ \begin{array}{c|cccccccccc} & ab & ac & ad & ae & bc & bd & be & cd & ce & de\\hline &1&2&3&2&2&3&2&3&0&2 \end{array} ] Άρα [ L_2={ac,ad,ae,bc,bd,be,cd,de}. ]
Από το \(L_2\) παράγονται αρχικά [ C_3={acd,ace,ade,bcd,bce,bde}. ] Το \(ace\) και το \(bce\) απορρίπτονται επειδή περιέχουν το μη συχνό \(ce\). Άρα ελέγχονται: [ \begin{array}{c|cccc} & acd & ade & bcd & bde\\hline \text{Πλήθος} &1&1&1&1 \end{array} ] Κανένα δεν έχει πλήθος \(\ge 2\), άρα \(L_3=\varnothing\) και ο αλγόριθμος σταματά.
Hash tree. Επειδή δεν δίνεται συνάρτηση κατακερματισμού, για την επίδειξη θεωρώ [ h(a)=1,\ h(b)=2,\ h(c)=0,\ h(d)=1,\ h(e)=2. ] Συμβολίζω κόμβο με τη διαδρομή τιμών κατακερματισμού.
Μετά το βήμα \(C_1\): - bucket \(0\): \(\{c\}\) - bucket \(1\): \(\{a,d\}\) - bucket \(2\): \(\{b,e\}\)
Μετά το βήμα \(C_2\), πριν το κ送λάδεμα: [ \begin{array}{c|c} (h_1,h_2)&\text{υποψήφια}\\hline (0,1)&{cd}\ (0,2)&{ce}\ (1,0)&{ac}\ (1,1)&{ad}\ (1,2)&{ab,ae,de}\ (2,0)&{bc}\ (2,1)&{bd}\ (2,2)&{be} \end{array} ] Μετά την εύρεση του \(L_2\) μένουν: [ \begin{array}{c|c} (h_1,h_2)&\text{συχνά}\\hline (0,1)&{cd}\ (1,0)&{ac}\ (1,1)&{ad}\ (1,2)&{ae,de}\ (2,0)&{bc}\ (2,1)&{bd}\ (2,2)&{be} \end{array} ]
Μετά το βήμα \(C_3\), μετά το κ送λάδεμα: [ \begin{array}{c|c} (h_1,h_2,h_3)&\text{υποψήφια}\\hline (1,0,1)&{acd}\ (1,1,2)&{ade}\ (2,0,1)&{bcd}\ (2,1,2)&{bde} \end{array} ] Επειδή κανένα δεν είναι συχνό, το hash tree του \(L_3\) είναι κενό.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
3.1) Τρεις τεχνικές συμπλήρωσης ελλιπών τιμών: - Διαγραφή εγγραφών/γραμμών με ελλιπείς τιμές. - Συμπλήρωση με μέση τιμή, διάμεσο ή επικρατούσα τιμή (mean/mode/median imputation). - Προβλεπτική συμπλήρωση με παλινδρόμηση, \(k\)-NN, δέντρα ή EM. - (Εναλλακτικά: multiple imputation, hot-deck, σταθερή τιμή “unknown”.)
3.2) Δεδομένα: [ 4,8,9,13,19,21,26,30,32,35,38,39. ]
Μέθοδος 1: Equal-width binning. Εύρος \(=39-4=35\), πλάτος \(=35/3\approx 11.67\). [ \begin{array}{c|c|c} \text{Bin} & \text{Τιμές} & \text{Μέση τιμή}\\hline [4,15.67) & 4,8,9,13 & 8.5\ [15.67,27.33) & 19,21,26 & 22\ [27.33,39] & 30,32,35,38,39 & 34.8 \end{array} ] Εξομαλυμένη ακολουθία με μέσες τιμές bins: [ 8.5,8.5,8.5,8.5,22,22,22,34.8,34.8,34.8,34.8,34.8. ]
Μέθοδος 2: Equal-frequency binning. Χωρίζω σε 3 bins των 4 τιμών. [ \begin{array}{c|c|c} \text{Bin} & \text{Τιμές} & \text{Μέση τιμή}\\hline 1 & 4,8,9,13 & 8.5\ 2 & 19,21,26,30 & 24\ 3 & 32,35,38,39 & 36 \end{array} ] Εξομαλυμένη ακολουθία με μέσες τιμές bins: [ 8.5,8.5,8.5,8.5,24,24,24,24,36,36,36,36. ]
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Από τον πίνακα: \(P(\text{Male})=3/8\), \(P(\text{Female})=5/8\).
Για το δείγμα \(X=(\text{Drew}, \text{Yes over 170}, \text{Blue}, \text{Long})\), θεωρώντας και το Name ως μεταβλητή: [ P(X|\text{Male})=\frac13\cdot\frac23\cdot\frac23\cdot\frac13, ] [ P(X|\text{Female})=\frac25\cdot\frac25\cdot\frac35\cdot\frac45. ] Άρα: [ P(\text{Male})P(X|\text{Male}) =\frac38\cdot\frac13\cdot\frac23\cdot\frac23\cdot\frac13 =\frac1{54}\approx 0.01852, ] [ P(\text{Female})P(X|\text{Female}) =\frac58\cdot\frac25\cdot\frac25\cdot\frac35\cdot\frac45 =\frac6{125}=0.048. ] Κανονικοποιημένα: [ P(\text{Female}|X)=\frac{6/125}{6/125+1/54}=\frac{324}{449}\approx 0.722, ] [ P(\text{Male}|X)=\frac{125}{449}\approx 0.278. ] Εφόσον \(P(\text{Female}|X)>P(\text{Male}|X)\), το δείγμα ταξινομείται ως Female. Αν αγνοήσουμε το Name ως αναγνωριστικό, το αποτέλεσμα παραμένει Female.
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
5.1) Χρησιμοποιώ ως τοπικό κόστος \(d(i,j)=|x_i-y_j|\) και [ D(i,j)=d(i,j)+\min{D(i-1,j),D(i,j-1),D(i-1,j-1)}. ] Ο πίνακας δυναμικού προγραμματισμού είναι: [ \begin{array}{c|rrrrrr} &1&5&2&2&4&2\\hline 1&0&4&5&6&9&10\ 5&4&0&3&6&7&10\ 4&7&1&2&4&4&6\ 3&9&3&2&3&4&5\ 2&10&6&2&2&4&4\ 4&13&7&4&4&2&4\ 5&17&7&7&7&3&5\ 4&20&8&9&9&3&5\ 3&22&10&9&10&4&4 \end{array} ] Άρα [ DTW(X,Y)=D(9,6)=4. ] Ένα βέλτιστο warping path είναι: [ (1,1),(2,2),(3,2),(4,3),(5,4),(6,5),(7,5),(8,5),(9,6). ] Αντίστοιχα ζεύγη τιμών: [ (1,1),(5,5),(4,5),(3,2),(2,2),(4,4),(5,4),(4,4),(3,2), ] με συνολικό κόστος [ 0+0+1+1+0+0+1+0+1=4. ]
5.2) Η μέθοδος LCSS (Longest Common Subsequence) βρίσκει το μεγαλύτερο κοινό υποακολουθιακό πρότυπο δύο χρονοσειρών, επιτρέποντας ανοχή \(\varepsilon\) στις τιμές και παράβλεψη ακραίων σημείων. Ο αναδρομικός τύπος είναι: [ L(i,j)= \begin{cases} 0, & i=0 \text{ ή } j=0,\ 1+L(i-1,j-1), & |x_i-y_j|\le\varepsilon,\ \max{L(i-1,j),L(i,j-1)}, & \text{διαφορετικά}. \end{cases} ] Ως ομοιότητα συνήθως χρησιμοποιείται [ \text{sim}(X,Y)=\frac{LCSS(X,Y)}{\min(n,m)}. ]
Παράδειγμα με τις χρονοσειρές του 5.1 και \(\varepsilon=0\): [ X={1,5,4,3,2,4,5,4,3},\quad Y={1,5,2,2,4,2}. ] Ένα μέγιστο κοινό υποακολουθιακό πρότυπο είναι το [ (1,5,4,2), ] άρα \(LCSS(X,Y)=4\). Η ομοιότητα είναι [ \text{sim}(X,Y)=\frac{4}{\min(9,6)}=\frac46=\frac23. ]