Εξόρυξη Δεδομένων και Μηχανική Μάθηση — Ιούνιος 2017

Μεταγραφή από τη φωτογραφία 2017.jpg, χειρόγραφο αντίγραφο της εκφώνησης με την ένδειξη «Ιούνιος 2017».

2017.jpg

Ιούνιος 2017

Εξόρυξη Δεδομένων

Θέμα 1

α) Δώστε τα βασικά χαρακτηριστικά του BIRCH και του DBSCAN

β) Δώστε τα βασικά χαρακτηριστικά του PAM και k-means. Συγκρίνετε τους 2 αλγόριθμους αναφέροντας τα πλεονεκτήματα και τα μειονεκτήματα τους.

γ) Στο πρόβλημα δυναμικής ομαδοποίησης έχουμε να χειριστούμε μια συλλογή από συστάδες για ένα σύνολο στοιχείων που δυναμικά ενημερώνονται με ενθέσεις κ' διαγραφές συναλλαγών. Εξηγήστε τα προβλήματα κατά την εφαρμογή των κλασικών αλγορίθμων σε ένα τέτοιο σενάριο χρήσης και δώστε τρόπους αντιμετώπισής τους.

Θέμα 2

α) Single κ' Complete link με πίνακα ομοιότητας:

	P1	P2	P3	P4	P5
P1	1	0.15	0.43	0.57	0.35
P2	0.15	1	0.64	0.47	0.95
P3	0.43	0.64	1	0.44	0.8
P4	0.57	0.47	0.44	1	0.7
P5	0.35	0.95	0.8	0.7	1

β) Πως ένας αλγόριθμος συσταδοποίησης μπορεί να χρησιμοποιηθεί σαν ένα βήμα προεπεξεργασίας για έναν άλλο. Πως η ολοκλήρωση των 2 μεθόδων μπορεί να οδηγήσει σε βελτίωση ποιότητας κ' αποτελεσματικότητας;

γ) Περιγραφή της διαδικασίας συσταδοποίησης με νευρωνικά δίκτυα. Πως εμφανίζονται οι όροι ανταγωνιστική μάθηση κ' αυτοοργάνωση σε αυτή;

Θέμα 3

α) Δώστε τα 4 βήματα προεπεξεργασίας και τα επιπέρους αυτών. Ποια είναι τα πιο χρονοβόρα

β) Δώστε τα χαρακτηριστικά αξιολογ. μεθόδων κατηγοριοποίησης κ' ποιά είναι τα πιο σημαντικά απ' αυτά.

γ) Μείωση διαστατικότητας κ' πλεονεκτήματα της κ' συνοδεύεται από απώλεια πληροφορίας;

Θέμα 4 : Naive Bayes

Θέμα 5:

α) Quad Tree

β) Δομή του Sting. κ' βασικές αρχές λειτουργίας κ' ποια ερωτήματα ενδεικνύονται

γ) DTW

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2017-06

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) BIRCH και DBSCAN

• BIRCH: Ιεραρχικός/αυξητικός αλγόριθμος για μεγάλα σύνολα δεδομένων. Χρησιμοποιεί Clustering Features \(CF=(N,LS,SS)\), όπου \(N\) πλήθος σημείων, \(LS=\sum x_i\), \(SS=\sum x_i^2\), και κατασκευάζει ένα ισορροπημένο CF-tree με παραμέτρους branching factor και threshold. Συνήθως λειτουργεί σε φάσεις: κατασκευή CF-tree, συμπύκνωση, τελική ομαδοποίηση των CF. Πλεονεκτήματα: κλιμακωτό, μία σάρωση, αυξητικό, κατάλληλο για μεγάλα δεδομένα. Μειονεκτήματα: ευαισθησία στο threshold/σειρά εισαγωγής, καλή απόδοση κυρίως σε κυρτές/σφαιρικές συστάδες, πιθανή επίδραση θορύβου.
• DBSCAN: Αλγόριθμος βασισμένος στην πυκνότητα με παραμέτρους \(\varepsilon\) και \(MinPts\). Σημείο είναι core αν η \(\varepsilon\)-γειτονιά του έχει τουλάχιστον \(MinPts\) σημεία. Οι συστάδες σχηματίζονται μέσω density-reachability/connectivity· σημεία που δεν ανήκουν σε καμία συστάδα θεωρούνται θόρυβος. Πλεονεκτήματα: βρίσκει συστάδες αυθαίρετου σχήματος, ανιχνεύει θόρυβο, δεν απαιτεί εκ των προτέρων πλήθος συστάδων. Μειονεκτήματα: ευαισθησία στις παραμέτρους, δυσκολία με διαφορετικές πυκνότητες και σε υψηλές διαστάσεις, χειρότερη περίπτωση \(O(n^2)\).

β) PAM και k-means

• k-means: Κάθε συστάδα αντιπροσωπεύεται από το μέσο των σημείων. Επαναλαμβάνει ανάθεση κάθε σημείου στο κοντινότερο κέντρο και επαναϋπολογισμό κέντρων, ελαχιστοποιώντας το SSE. Πλεονεκτήματα: απλός, γρήγορος, κλιμακωτός, κατάλληλος για μεγάλα αριθμητικά δεδομένα. Μειονεκτήματα: απαιτεί \(k\), ευαίσθητος σε αρχικοποίηση και ακραίες τιμές, προτιμά σφαιρικές/παρόμοιου μεγέθους συστάδες, συνήθως Ευκλείδεια απόσταση.
• PAM (k-medoids): Κάθε συστάδα αντιπροσωπεύεται από ένα πραγματικό σημείο, το medoid. Ελαχιστοποιεί το άθροισμα αποστάσεων προς τα medoids και βελτιώνει μέσω ανταλλαγών medoid/non-medoid. Πλεονεκτήματα: πιο ανθεκτικός σε θόρυβο/ακραίες τιμές, λειτουργεί με οποιονδήποτε πίνακα αποστάσεων, ερμηνεύσιμα αντιπροσωπευτικά σημεία. Μειονεκτήματα: ακριβός, τυπικά \(O(k(n-k)^2)\) ανά επανάληψη, όχι κατάλληλος για πολύ μεγάλα \(n\), απαιτεί \(k\) και μπορεί να κολλήσει σε τοπικό βέλτιστο.

γ) Δυναμική ομαδοποίηση με ενθέσεις/διαγραφές

Οι κλασικοί αλγόριθμοι θεωρούν στατικό σύνολο δεδομένων. Σε δυναμικό σενάριο, κάθε ένθεση/διαγραφή μπορεί να αλλάξει τις συστάδες. Το πλήρες re-run είναι συχνά πολύ ακριβό, μη σταθερό και ευαίσθητο σε αρχικοποίηση/σειρά. Οι διαγραφές είναι ιδιαίτερα προβληματικές όταν το μοντέλο βασίζεται σε αθροιστικά στατιστικά ή σε αντιπροσώπους που δεν ενημερώνονται εύκολα αφαιρετικά. Επίσης εμφανίζεται concept drift και μεταβολή πυκνοτήτων.

Τρόποι αντιμετώπισης: αυξητικοί/online αλγόριθμοι, ενημέρωση επαρκών στατιστικών (π.χ. CF σε BIRCH, κέντρα/μετρητές), τοπική ενημέρωση μόνο των επηρεαζόμενων συστάδων, split/merge συστάδων, δομές ευρετηρίου, microclusters, παράθυρα/χρονική εξασθένηση, lazy deletion, περιοδικό batch re-clustering με σταθερή αρχικοποίηση, ανίχνευση drift και επανεκπαίδευση.

Θέμα 2

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) Single και Complete link

Με πίνακα ομοιότητας, γίνονται συγχωνεύσεις με βάση τη μέγιστη ομοιότητα. Στο single link η ομοιότητα δύο συστάδων είναι το μέγιστο των ομοιοτήτων μεταξύ των μελών τους· στο complete link είναι το ελάχιστο.

Single link: 1. Συγχώνευση \(P_2,P_5\) με ομοιότητα \(0.95\). 2. Το \(\{P_2,P_5\}\) ενώνεται με \(P_3\): \(\max(0.64,0.80)=0.80\). 3. Το \(\{P_2,P_5,P_3\}\) ενώνεται με \(P_4\): \(\max(0.47,0.70,0.44)=0.70\). 4. Το \(\{P_2,P_5,P_3,P_4\}\) ενώνεται με \(P_1\): \(\max(0.15,0.35,0.43,0.57)=0.57\).

Άρα: \((((P_2,P_5),P_3),P_4),P_1\) με ύψη ομοιότητας \(0.95,0.80,0.70,0.57\).

Complete link: 1. Συγχώνευση \(P_2,P_5\) με ομοιότητα \(0.95\). 2. Το \(\{P_2,P_5\}\) ενώνεται με \(P_3\): \(\min(0.64,0.80)=0.64\). 3. Σχηματίζεται το \(\{P_1,P_4\}\) με ομοιότητα \(0.57\), καθώς είναι η μεγαλύτερη διαθέσιμη μεταξύ των τρεχουσών συστάδων. 4. Τελικά ενώνονται \(\{P_2,P_5,P_3\}\) και \(\{P_1,P_4\}\) με ομοιότητα \(\min(0.15,0.47,0.35,0.70,0.43,0.44)=0.15\).

Άρα: \(((P_2,P_5),P_3)\) και \((P_1,P_4)\) ενώνονται τελικά στο \(0.15\).

β) Συσταδοποίηση ως προεπεξεργασία

Η συσταδοποίηση μπορεί να χρησιμοποιηθεί πριν από άλλον αλγόριθμο για: μείωση πλήθους δειγμάτων μέσω αντιπροσώπων/πρωτοτύπων, δημιουργία νέων χαρακτηριστικών (cluster membership), τοπικά μοντέλα ανά συστάδα, ημι-επιβλεπόμενη μάθηση, ανίχνευση ακραίων τιμών και μείωση θορύβου. Η ολοκλήρωση μπορεί να βελτιώσει την ποιότητα (π.χ. τοπικά μοντέλα ή χρήση συστάδων ως επιπλέον χαρακτηριστικών) και την αποδοτικότητα (π.χ. εκπαίδευση σε αντιπροσώπους ή παράλληλη επεξεργασία ανά συστάδα). Επίσης, ένας ταξινομητής μπορεί να καθοδηγήσει τη συσταδοποίηση μέσω constraints/ημι-επιβλεπόμενης μάθησης, ή να συνδυαστούν επαναληπτικά (π.χ. EM-style).

γ) Συσταδοποίηση με νευρωνικά δίκτυα

Η τυπική διαδικασία χρησιμοποιεί νευρώνες ως πρωτότυπα/κέντρα συστάδων. Για κάθε είσοδο \(\mathbf{x}\) βρίσκεται ο νικητής νευρώνας \(j^*=\arg\min_j \|\mathbf{x}-\mathbf{w}_j\|\) και ενημερώνεται το βάρος του, π.χ. \(\mathbf{w}_{j^*}\leftarrow \mathbf{w}_{j^*}+\eta(\mathbf{x}-\mathbf{w}_{j^*})\). Σε ανταγωνιστική μάθηση οι νευρώνες ανταγωνίζονται για το ποιος θα ενεργοποιηθεί (winner-take-all). Στα Self-Organizing Maps (SOM) ενημερώνεται και γειτονιά του νικητή· με μείωση του ρυθμού μάθησης και της γειτονιάς επιτυγχάνεται αυτοοργάνωση, δηλαδή διατήρηση τοπολογίας των εισόδων στον χάρτη. Έτσι προκύπτουν συστάδες από ομάδες κοντινών νευρώνων/πρωτοτύπων.

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) Τέσσερα βήματα προεπεξεργασίας

1. Καθαρισμός δεδομένων (data cleaning): συμπλήρωση ελλιπών τιμών, εξομάλυνση θορύβου, εντοπισμός/αφαίρεση ακραίων τιμών, διόρθωση ασυνεπειών, αφαίρεση διπλοτύπων.
2. Ολοκλήρωση δεδομένων (data integration): συνδυασμός πολλαπλών πηγών, ενοποίηση σχήματος, εντοπισμός πλεονασμού/συσχέτισης, επίλυση διπλοεγγραφών.
3. Μετασχηματισμός δεδομένων (data transformation): κανονικοποίηση, συγκέντρωση, γενίκευση, κατασκευή χαρακτηριστικών, διακριτοποίηση.
4. Μείωση δεδομένων (data reduction): μείωση διαστάσεων (feature selection, PCA), μείωση πλήθους (δειγματοληψία, ιστογράμματα, clustering), συμπίεση.

Πιο χρονοβόρα στην πράξη είναι συνήθως ο καθαρισμός και η ολοκλήρωση δεδομένων, με τον καθαρισμό (ελλιπείς/θορυβώδεις/ασυνεπείς τιμές και χειροκίνητοι έλεγχοι) να καταναλώνει συχνά το μεγαλύτερο μέρος της προσπάθειας.

β) Χαρακτηριστικά αξιολόγησης μεθόδων κατηγοριοποίησης

Συνήθη κριτήρια: προβλεπτική ακρίβεια, ταχύτητα/υπολογιστικό κόστος, κλιμακωσιμότητα, ανθεκτικότητα σε θόρυβο/ακραίες τιμές/ελλιπή δεδομένα, ερμηνευσιμότητα, ευαισθησία σε παραμέτρους και πολυπλοκότητα μοντέλου. Ως μετρικές αξιολόγησης χρησιμοποιούνται confusion matrix, accuracy, precision, recall, F1, sensitivity/specificity, ROC-AUC, cross-validation/holdout.

Πιο σημαντική θεωρείται συνήθως η προβλεπτική ακρίβεια, ακολουθούμενη από την ταχύτητα/κλιμακωσιμότητα· η ερμηνευσιμότητα μπορεί να είναι κρίσιμη σε εφαρμογές όπου απαιτείται εξήγηση αποφάσεων.

γ) Μείωση διαστατικότητας

Περιλαμβάνει επιλογή χαρακτηριστικών (filter/wrapper/embedded) και εξαγωγή χαρακτηριστικών (PCA, LDA, SVD, autoencoders, t-SNE για οπτικοποίηση). Πλεονεκτήματα: αντιμετώπιση της κατάρας της διαστατικότητας, μείωση χρόνου/μνήμης, μείωση overfitting και θορύβου, καλύτερη γενίκευση, δυνατότητα οπτικοποίησης. Συνήθως συνοδεύεται από απώλεια πληροφορίας, εκτός αν αφαιρούνται μόνο πλεονάζοντα/άχρηστα χαρακτηριστικά ή αν ο μετασχηματισμός είναι αντιστρέψιμος. Η απώλεια μπορεί να είναι αποδεκτή αν διατηρείται η πληροφορία που είναι χρήσιμη για την εκάστοτε εργασία.

Θέμα 4

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια

Η μεταγραφή δίνει μόνο τον τίτλο «Naive Bayes»· με την παραδοχή ότι ζητείται περιγραφή του αλγορίθμου, παρατίθεται η βασική θεωρία. Αν ζητείται αριθμητική εφαρμογή σε συγκεκριμένο σύνολο δεδομένων, αυτά τα δεδομένα λείπουν.

Ο Naive Bayes είναι πιθανοτικός ταξινομητής που εφαρμόζει το θεώρημα Bayes: [ P(C\mid \mathbf{x})=\frac{P(C)P(\mathbf{x}\mid C)}{P(\mathbf{x})} ] και κάνει την υπόθεση δεσμευμένης ανεξαρτησίας των χαρακτηριστικών δεδομένης της κλάσης: [ P(\mathbf{x}\mid C)\approx \prod_{i=1}^{d}P(x_i\mid C). ] Η ταξινόμηση γίνεται ως: [ \hat{C}=\arg\max_C P(C)\prod_{i=1}^{d}P(x_i\mid C). ] Οι πιθανότητες \(P(C)\) και \(P(x_i\mid C)\) εκτιμώνται από τα δεδομένα εκπαίδευσης: για κατηγορικά χαρακτηριστικά με σχετικές συχνότητες (και συνήθως Laplace smoothing), για συνεχή με κατανομή Gauss ανά κλάση/χαρακτηριστικό, για κείμενο με multinomial μοντέλο. Πλεονεκτήματα: απλός, γρήγορος, χαμηλή μνήμη, καλός σε υψηλές διαστάσεις και κείμενο. Μειονεκτήματα: η ανεξαρτησία συχνά δεν ισχύει, οι πιθανότητες μπορεί να είναι κακώς βαθμονομημένες, συσχετισμένα χαρακτηριστικά διπλομετρώνται.

Θέμα 5

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) Quad Tree

Το Quad Tree είναι δενδρική χωρική δομή που διαιρεί αναδρομικά τον δισδιάστατο χώρο σε τέσσερα τεταρτημόρια (π.χ. NE, NW, SE, SW). Κάθε εσωτερικός κόμβος έχει έως τέσσερα παιδιά· τα φύλλα αποθηκεύουν σημεία/αντικείμενα μέχρι κάποια χωρητικότητα, και όταν αυτή ξεπεραστεί γίνεται διάσπαση. Χρησιμοποιείται για χωρική ευρετηρίαση, range queries, nearest-neighbor αναζήτηση, spatial joins, αναπαράσταση/συμπίεση εικόνων, collision detection και χωρική ομαδοποίηση. Η απόδοση εξαρτάται από την κατανομή των δεδομένων και το βάθος του δέντρου· πολύ ανισομερής κατανομή μπορεί να το εκφυλίσει.

β) STING

Το STING είναι ιεραρχική, grid-based μέθοδος συσταδοποίησης. Ο χώρος χωρίζεται σε ορθογώνια κελιά πολλαπλών επιπέδων· κάθε κελί γονέας διαιρείται σε παιδιά. Κάθε κελί αποθηκεύει στατιστικά: πλήθος σημείων, μέση τιμή, τυπική απόκλιση, ελάχιστο, μέγιστο, τύπο κατανομής κ.λπ. Η επεξεργασία ερωτήματος γίνεται top-down: με βάση διαστήματα εμπιστοσύνης για τα στατιστικά, κελιά που σίγουρα δεν ικανοποιούν το κριτήριο κλαδεύονται· σχετικά κελιά εξετάζονται βαθύτερα. Ενδείκνυται για χωρικά δεδομένα, region queries, aggregate/statistical queries (π.χ. «περιοχές με μέση τιμή μεγαλύτερη από \(X\)»), συσταδοποίηση και παράλληλη/κατανεμημένη επεξεργασία. Μειονεκτεί σε συστάδες αυθαίρετου σχήματος και η ποιότητα εξαρτάται από το μέγεθος του grid.

γ) DTW

Το Dynamic Time Warping (DTW) μετρά την ομοιότητα δύο ακολουθιών \(Q=(q_1,\dots,q_n)\) και \(C=(c_1,\dots,c_m)\) που μπορεί να έχουν διαφορετικό μήκος ή χρονικές μετατοπίσεις/επιταχύνσεις. Χρησιμοποιεί δυναμικό προγραμματισμό: [ D(i,j)=|q_i-c_j|+\min{D(i-1,j),\,D(i,j-1),\,D(i-1,j-1)}, ] με αρχικές συνθήκες και τελική απόσταση \(D(n,m)\). Επιτρέπει μονοτονική, μη γραμμική αντιστοίχιση των ακολουθιών, γι' αυτό χρησιμοποιείται σε χρονοσειρές, αναγνώριση ομιλίας/χειρονομιών και ταξινόμηση/ομαδοποίηση ακολουθιών. Κύριο μειονέκτημα είναι το κόστος \(O(nm)\) και η ανάγκη περιορισμών (π.χ. band, κανονικοποίηση) για αποφυγή υπερβολικής «παραμόρφωσης».

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

---

✖ Βρήκα λάθος στη μεταγραφή