Εξόρυξη Δεδομένων και Μηχανική Μάθηση — Ιούνιος 2021 (Εκδοχή Α)¶
Μεταγραφή από το κείμενο της τυπωμένης εκφώνησης dm_themata_a.pdf (3 σελίδες).
dm_themata_a.pdf¶
Εξέταση Μαθήματος «ΕΞΟΡΥΞΗ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ ΜΑΘΗΣΗΣ» (Α)¶
ΕΞΕΤΑΣΤΙΚΗ ΙΟΥΝΙΟΥ Εαρινό Εξάμηνο 2020-21
Διδάσκοντες: Mεγαλοικονόμου Βασίλειος Μακρής Χρήστος,
ΔΙΑΡΚΕΙΑ 2 ΩΡEΣ MAZI ME TO ANEBAΣΜΑ ΣΤΟ ECLASS
ΘΕΜΑ 1 Προεπεξεργασία δεδομένων (10 μονάδες)
α) Δώστε έναν ορισμό για τη μείωση της διαστατικότητας των δεδομένων (dimensionality reduction). Ποια τα πλεονεκτήματα που πηγάζουν από αυτή τη διαδικασία;
β) Η κανονικοποίηση εντάσσεται στις μεθόδους προεπεξεργασίας των δεδομένων. Ποια είναι η χρησιμότητα της κανονικοποίησης αριθμητικών δεδομένων; Εφαρμόζοντας την min-max κανονικοποίηση, το παλαιό διάστημα τιμών [80, 100] ανάγεται στο νέο διάστημα τιμών [0,1]. Εφαρμόζοντας τον κατάλληλο τύπο, τα στοιχεία 85 και 97 του παλαιού διαστήματος σε ποιους αριθμούς του νέου διαστήματος ανάγονται;
ΘΕΜΑ 2 Κατηγοριοποίηση (25 μονάδες)¶
Έστω η παρακάτω βάση δεδομένων με ζώα. Περιέχει 18 παραδείγματα εκπαίδευσης. Το κάθε ζώο μπορεί να είναι θηλαστικό ή όχι (μεταβλητή κλάσης Class). Οι 5 ανεξάρτητες μεταβλητές καθορίζουν την κλάση στην οποία θα κατηγοριοποιηθεί κάθε δείγμα. Με βάση τα δεδομένα του πίνακα, να κατηγοριοποιήσετε το δείγμα X = { eel, yes, no, yes, no} , χρησιμοποιώντας τον Naive Bayesian Classifier.
| Ανεξάρτητες μεταβλητές | Κλάση | ||||
|---|---|---|---|---|---|
| Name | Give birth | Can fly | Live in water | Have legs | Class |
| Python | no | no | no | no | Non- mammals |
| Salmon | no | no | yes | no | Non- mammals |
| Human | yes | no | no | yes | mammals |
| Whale | yes | no | yes | no | mammals |
| Frog | no | no | sometimes | yes | non-mammals |
| Komodo | no | no | no | yes | non-mammals |
| Bat | yes | yes | no | yes | Mammals |
| Pigeon | no | yes | no | yes | Non- mammals |
| Cat | yes | no | no | yes | mammals |
| Leopard shark |
yes | no | yes | no | Non- mammals |
| Turtle | no | no | sometimes | yes | Non- mammals |
| Penguin | no | no | sometimes | yes | Non- mammals |
| porcupine | yes | no | no | yes | mammals |
| salamander | no | no | sometimes | yes | Non- mammals |
|---|---|---|---|---|---|
| Gila monster | no | no | no | yes | Non- mammals |
| Platypus | no | no | no | yes | mammals |
| Owl | no | yes | no | yes | mammals |
| Dolphin | yes | no | yes | no | mammals |
| Eagle | no | yes | no | yes | Non- mammals |
ΘΕΜΑ 3 Ανάλυση Χρονικών και Χωρικών Δεδομένων (15 μονάδες)¶
α) Δίνονται οι χρονοσειρές Α = {1, 3, 5, 7, 6, 4, 3} και Β = {1, 2, 5, 7, 4}. Εφαρμόζοντας τη μέθοδο Minimal Variance Matching, να συμπληρώσετε τον ακόλουθο πίνακα διαφορών και να προσδιορίσετε το συντομότερο μονοπάτι.
| Β Α |
1 | 3 | 5 | 7 | 6 | 4 | 3 |
|---|---|---|---|---|---|---|---|
| 1 | |||||||
| 2 | |||||||
| 5 | |||||||
| 7 | |||||||
| 4 |
- β) Περιγράψτε τα κύρια σημεία του αλγορίθμου εξόρυξης χωρικών δεδομένων STING.
ΘΕΜΑ 4 Ομαδοποίηση/Κανόνες συσχέτισης (25 μονάδες)¶
-
α. Εξηγήστε πως θα μπορούσαμε με χρήση αλγορίθμων εύρεσης συχνών συνολοστοιχείων όπως ο Apriori ή ο Eclat να ομαδοποιήστε γραφήματα σε υπογραφήματα ισχυρά συνεκτικά. Η μορφή των υπογραφημάτων αυτών είναι δική σας επιλογή ώστε να προκύψει το αλγοριθμικό σχήμα.
-
β. Οι παραδοσιακοί συσσωρευτικοί ιεραρχικοί αλγόριθμοι συσταδοποίησης συγχωνεύουν δύο συστάδες σε κάθε βήμα. Είναι πιθανό ότι μία τέτοια προσέγγιση θα καταγράψει επακριβώς την εμφωλευμένη δομή ομαδοποίησης ενός συνόλου ομαδοποίησης; Εάν όχι εξηγήστε πως θα μπορούσατε να μεταεπεξεργαστείτε τα δεδομένα για να απακτήσετε μία πιο επακριβή εικόνα της δομής συσταδοποίησης. Αναφέρετε και τη σχέση τέτοιων προσεγγίσεων με ιεραρχικές συσταδοποίησει συσταδοποίησης από πάνω προς τα κάτω.
ΘΕΜΑ 5 Κανόνες συσχέτισης (25 μονάδες) Θεωρήστε το κάτωθι σύνολο συναλλαγών:
| Κωδικός | Προϊόντα |
|---|---|
| Συναλλαγής |
| 1 | ACD |
|---|---|
| 2 | BCE |
| 3 | ABCE |
| 4 | BDE |
| 5 | ABCE |
| 6 | ABCD |
| 7 | BCDE |
| 8 | CDE |
| 9 | ADE |
| 10 | BCE |
-
α. Υπολογίστε την τιμή υποστήριξης και εμπιστοσύνης για όλους τους κανόνες που προκύπτουν από το συνολοστοιχείο ΑΒΕ.
-
β. Εκτελέστε τον αλγόριθμο Apriori για minsum 30%
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α) Μείωση διαστατικότητας είναι η διαδικασία μείωσης του αριθμού των χαρακτηριστικών/μεταβλητών που περιγράφουν τα δεδομένα, διατηρώντας κατά το δυνατόν τη χρήσιμη πληροφορία, τη δομή ή τη διακύμανσή τους. Πλεονεκτήματα: μικρότερο υπολογιστικό κόστος και απαιτήσεις μνήμης, αντιμετώπιση της «κατάρας της διαστατικότητας», μείωση θορύβου και κινδύνου υπερπροσαρμογής, καλύτερη οπτικοποίηση/ερμηνεία και συχνά βελτίωση της απόδοσης αλγορίθμων εξόρυξης.
β) Η κανονικοποίηση φέρνει αριθμητικά χαρακτηριστικά σε κοινή κλίμακα, ώστε χαρακτηριστικά με μεγάλες τιμές να μην κυριαρχούν σε μέτρα απόστασης ή σε αλγορίθμους βελτιστοποίησης. Στην min-max κανονικοποίηση από \([80,100]\) σε \([0,1]\): [ v'=\frac{v-80}{100-80}(1-0)+0=\frac{v-80}{20}. ] Άρα: [ 85\mapsto \frac{85-80}{20}=\frac{5}{20}=0.25,\qquad 97\mapsto \frac{97-80}{20}=\frac{17}{20}=0.85. ]
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Ο πίνακας της εκφώνησης περιέχει 19 γραμμές, ενώ η εκφώνηση αναφέρει 18· χρησιμοποιώ τις γραμμές όπως δίνονται. Θεωρώ ότι το πρώτο στοιχείο του δείγματος, «eel», είναι όνομα/αναγνωριστικό και δεν χρησιμοποιείται ως χαρακτηριστικό. Έτσι τα χαρακτηριστικά είναι: Give birth \(=\) yes, Can fly \(=\) no, Live in water \(=\) yes, Have legs \(=\) no.
Από τον πίνακα: mammals \(=8\), non-mammals \(=11\), σύνολο \(19\): [ P(\text{mammals})=\frac{8}{19},\qquad P(\text{non-mammals})=\frac{11}{19}. ] Για τα mammals: [ P(\text{yes birth}\mid m)=\frac{6}{8},\quad P(\text{no fly}\mid m)=\frac{6}{8},\quad P(\text{yes water}\mid m)=\frac{2}{8},\quad P(\text{no legs}\mid m)=\frac{2}{8}. ] Για τα non-mammals: [ P(\text{yes birth}\mid n)=\frac{1}{11},\quad P(\text{no fly}\mid n)=\frac{9}{11},\quad P(\text{yes water}\mid n)=\frac{2}{11},\quad P(\text{no legs}\mid n)=\frac{3}{11}. ] Επομένως: [ P(m\mid X)\propto \frac{8}{19}\frac{6}{8}\frac{6}{8}\frac{2}{8}\frac{2}{8}\approx 0.01480, ] [ P(n\mid X)\propto \frac{11}{19}\frac{1}{11}\frac{9}{11}\frac{2}{11}\frac{3}{11}\approx 0.002135. ] Επειδή \(P(m\mid X)>P(n\mid X)\), ο Naive Bayes κατατάσσει το δείγμα στην κλάση mammals.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α) Στο MVM αντιστοιχίζουμε όλα τα στοιχεία της μικρότερης χρονοσειράς \(B\) σε αύξουσα υποακολουθία της \(A\). Ο πίνακας απόλυτων διαφορών \(|B_i-A_j|\) είναι:
| \(B\backslash A\) | 1 | 3 | 5 | 7 | 6 | 4 | 3 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 4 | 6 | 5 | 3 | 2 |
| 2 | 1 | 1 | 3 | 5 | 4 | 2 | 1 |
| 5 | 4 | 2 | 0 | 2 | 1 | 1 | 2 |
| 7 | 6 | 4 | 2 | 0 | 1 | 3 | 4 |
| 4 | 3 | 1 | 1 | 3 | 2 | 0 | 1 |
(Αν στο κόστος χρησιμοποιούνται τετραγωνικές διαφορές, ο βέλτιστος δρόμος είναι ο ίδιος και το ελάχιστο κόστος παραμένει \(1\).)
Το συντομότερο μονοπάτι είναι: [ (1,1)\rightarrow(2,2)\rightarrow(3,3)\rightarrow(4,4)\rightarrow(5,6), ] δηλαδή: [ B_1=1\to A_1=1,\quad B_2=2\to A_2=3,\quad B_3=5\to A_3=5, ] [ B_4=7\to A_4=7,\quad B_5=4\to A_6=4. ] Το κόστος είναι [ |1-1|+|2-3|+|5-5|+|7-7|+|4-4|=0+1+0+0+0=1. ] Αν επιβάλλεται να χρησιμοποιηθεί και το τελευταίο στοιχείο της \(A\), τότε το μονοπάτι καταλήγει στο \((5,7)\) με κόστος \(2\).
β) Κύρια σημεία του STING: - Χωρίζει τον χώρο σε ιεραρχικό πλέγμα ορθογώνιων κελιών πολλών επιπέδων. - Κάθε κελί αποθηκεύει προϋπολογισμένα στατιστικά στοιχεία, όπως πλήθος σημείων, μέση τιμή, τυπική απόκλιση, ελάχιστο/μέγιστο και κατανομή. - Η επεξεργασία ερωτημάτων γίνεται από πάνω προς τα κάτω: εξετάζονται πρώτα κελιά ανώτερου επιπέδου, απορρίπτονται μη σχετικά κελιά και η αναζήτηση συνεχίζεται μόνο στα σχετικά παιδιά τους. - Είναι αποδοτικός επειδή το κόστος εξαρτάται κυρίως από τον αριθμό των κελιών και όχι από το πλήθος των σημείων· υποστηρίζει ενημερώσεις και παράλληλη επεξεργασία. - Μειονεκτήματα: η ποιότητα εξαρτάται από την ανάλυση του πλέγματος και δεν ανιχνεύει καλά συστάδες με μη ορθογώνια/πλάγια όρια.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α) Ένα αλγοριθμικό σχήμα με Apriori/Eclat μπορεί να βασιστεί σε «υπογραφές προσβασιμότητας». Για κάθε κορυφή \(v\) ενός κατευθυνόμενου γραφήματος ορίζουμε τη συναλλαγή [ T_v={u: \text{υπάρχει μονοπάτι από το } v \text{ προς το } u}. ] Τα «items» είναι κορυφές και κάθε \(T_v\) είναι το σύνολο των κορυφών που προσεγγίζονται από την \(v\). Εφαρμόζουμε Apriori ή Eclat στις συναλλαγές \(T_v\) για να βρούμε συχνά σύνολα κορυφών. Ένα σύνολο \(S\) παριστάνει ισχυρά συνεκτικό υπογράφημα αν για κάθε \(u,v\in S\) ισχύει ότι η \(u\) προσεγγίζει την \(v\) και αντίστροφα· πρακτικά ελέγχουμε αν \(S\subseteq T_u\) για κάθε \(u\in S\), δηλαδή αν το \(S\) είναι «αυτο-υποστηριζόμενο» ως προς τη σχέση αμοιβαίας προσβασιμότητας. Κρατάμε τα μέγιστα τέτοια συχνά σύνολα ως συστάδες/υπογραφήματα. Ο Apriori παράγει υποψήφια σύνολα από συχνά υποσύνολα και τα φιλτράρει με τη στήριξη· ο Eclat χρησιμοποιεί κάθετα σύνολα συναλλαγών και τομές για ταχύτερη απαρίθμηση. Με κατάλληλο κατώφλι στήριξης ελέγχουμε και μη τετριμμένες συστάδες μεγέθους τουλάχιστον \(2\).
β) Όχι κατ’ ανάγκη. Οι παραδοσιακοί συσσωρευτικοί αλγόριθμοι κάνουν μη αναστρέψιμες συγχωνεύσεις και παράγουν ένα δένδρο από αμοιβαία αποκλειόμενες, ένθετες συστάδες. Αν η πραγματική δομή έχει επικαλυπτόμενες συστάδες, συστάδες με διαφορετικά σχήματα/πυκνότητες ή υποσυστάδες μέσα σε μεγαλύτερες, ένα απλό δενδρόγραμμα μπορεί να μην την αποτυπώσει επακριβώς.
Μεταεπεξεργασία για ακριβέστερη εικόνα: - Χρήση πολλών επιπέδων/αποκοπών του δενδρογράμματος και ανάλυση της εσωτερικής δομής κάθε συστάδας, π.χ. επαναληπτική συσταδοποίηση μέσα σε μεγάλες συστάδες. - Κατασκευή γράφου σχέσεων μεταξύ μικρο-συστάδων ή συστάδων από διαφορετικές εκτελέσεις και εφαρμογή δεύτερης συσταδοποίησης/consensus clustering πάνω σε αυτόν. - Αφαίρεση ασθενών συνδέσεων ή χρήση γράφου \(k\)-πλησιέστερων γειτόνων/shared nearest neighbors πριν από την ιεραρχική συγχώνευση, ώστε να αποκαλυφθούν φυσικές υποσυστάδες. - Συνδυασμός bottom-up συγχώνευσης με top-down διάσπασης.
Οι προσεγγίσεις αυτές σχετίζονται άμεσα με την ιεραρχική συσταδοποίηση από πάνω προς τα κάτω (divisive): η συσσωρευτική είναι bottom-up συγχώνευση, ενώ η divisive ξεκινά από μία συστάδα και τη διασπά αναδρομικά. Μια πιο ακριβής εικόνα της ένθετης δομής προκύπτει συχνά με εναλλαγή ή συνδυασμό των δύο κατευθύνσεων.
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Σύνολο συναλλαγών: [ \begin{aligned} &1:ACD,\ 2:BCE,\ 3:ABCE,\ 4:BDE,\ 5:ABCE,\ &6:ABCD,\ 7:BCDE,\ 8:CDE,\ 9:ADE,\ 10:BCE. \end{aligned} ]
α) Για το σύνολο στοιχείων \(ABE\), η στήριξη είναι: [ \mathrm{supp}(ABE)=2/10=20\%. ] Οι κανόνες που προκύπτουν από το \(ABE\) είναι:
| Κανόνας | \(\mathrm{supp}(X)\) | \(\mathrm{supp}(ABE)\) | Confidence |
|---|---|---|---|
| \(A,B\rightarrow E\) | 3 | 2 | \(2/3=66.7\%\) |
| \(A,E\rightarrow B\) | 3 | 2 | \(2/3=66.7\%\) |
| \(B,E\rightarrow A\) | 6 | 2 | \(2/6=33.3\%\) |
| \(E\rightarrow A,B\) | 8 | 2 | \(2/8=25.0\%\) |
| \(A\rightarrow B,E\) | 5 | 2 | \(2/5=40.0\%\) |
| \(B\rightarrow A,E\) | 7 | 2 | \(2/7\approx 28.6\%\) |
β) Για minsup \(30\%\) και \(10\) συναλλαγές, ελάχιστη στήριξη είναι \(3\) συναλλαγές.
Συχνά 1-σύνολα: [ A:5,\quad B:7,\quad C:8,\quad D:6,\quad E:8. ] Άρα \(L_1=\{A,B,C,D,E\}\).
Συχνά 2-σύνολα: [ \begin{aligned} &AB:3,\ AC:4,\ AD:3,\ AE:3,\ &BC:6,\ BD:3,\ BE:6,\ &CD:4,\ CE:6,\ DE:4. \end{aligned} ] Όλα τα ζεύγη έχουν στήριξη \(\ge 3\), άρα και τα \(10\) είναι συχνά.
Υποψήφια 3-σύνολα και στηρίξεις: [ \begin{aligned} &ABC:3,\quad ABD:1,\quad ABE:2,\quad ACD:2,\quad ACE:2,\ &ADE:1,\quad BCD:2,\quad BCE:5,\quad BDE:2,\quad CDE:2. \end{aligned} ] Άρα: [ L_3={ABC:3,\ BCE:5}. ] Από ένωση των \(ABC\) και \(BCE\) προκύπτει υποψήφιο \(ABCE\), με στήριξη: [ \mathrm{supp}(ABCE)=2<3, ] άρα απορρίπτεται. Ο Apriori σταματά.
Τελικά συχνά σύνολα: [ {A},{B},{C},{D},{E}, ] όλα τα ζεύγη \(AB,AC,AD,AE,BC,BD,BE,CD,CE,DE\), και [ {A,B,C}\ \text{με στήριξη }3,\qquad {B,C,E}\ \text{με στήριξη }5. ]