Αλγοριθμική Επιστήμη Δεδομένων
Περιγραφή εβδομάδας
- Γενικά
Γενικά
Το μάθημα προσφέρεται στα πλαίσια του ΔΠΜΣ "Επιστήμη Δεδομένων και Μηχανική Μάθηση", στους Υ.Δ. της ΣΗΜΜΥ, καθώς και σε άλλα μεταπτυχιακά προγράμματα (ΑΛΜΑ, ΕΜΕ).
Οι διαλέξεις για φέτος (2020-21) ξεκινούν 1/3 και θα γίνονται κάθε Δευτέρα, ώρα 18:00-21:00 διαδικτυακά (WebEx link εδώ)
Διδάσκοντες
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Δώρα Σούλιου, ΕΔΙΠ (dsouliou@mail.ntua.gr)
- Βασίλης Νάκος, Επισκέπτης ερευνητής από Ινστιτούτο Max Planck
Βοηθός διδασκαλίας
- Σταύρος Πετσαλάκης, Υ.Δ. (stpetsalakis@gmail.com)
Βιβλιογραφία
- [MMDS] Mining of Massive Datasets, Jure Leskovec, Anand Rajaraman, and Jeff Ullman
www.mmds.org (book, slides, videos, etc.) - [FDS] Foundations of Data Science, Avrim Blum, John Hopcroft, and Ravindran Kannan
https://www.cs.cornell.edu/jeh/book.pdf - [TSKK] Introduction to Data Mining (2nd ed.), Pang-Ning Tan, Michael Steinbach, Anuj Karpatne, and Vipin Kumar
https://www-users.cs.umn.edu/~kumar001/dmbook/index.php
Εδώ θα υποβάλετε τις απαντήσεις σας
- 1/3
1/3
- Εισαγωγή - διαδικαστικά.
- Εξόρυξη κανόνων συσχέτισης και συνόλων στοιχείων που εμφανίζονται συχνά σε μεγάλα δεδομένα. Αλγόριθμοι A-priori και FP-growth.
Βίντεο διάλεξης [ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο. Ισχύουν περιορισμοί προστασίας προσωπικών δεδομένων.]Προτεινόμενη μελέτη: [MMDS] κεφ. 6 (link) (ενότητες 6.1, 6.2).Δείτε ακόμη: [TSKK] κεφ. 6 (link) (ενότητες 6.1, 6.2, 6.6). - 8/3
8/3
- Εξόρυξη συχνών συνόλων στοιχείων (μέρος 2), διαφάνειες (έμφαση σε 48-105) από μάθημα Π. Τσαπάρα (Παν. Ιωαννίνων).
- Παραγωγή και αξιολόγηση κανόνων συσχέτισης.
- Χρήση hashing, αλγόριθμοι PCY, SON, Toivonen.
Βίντεο της διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (δείτε παραπάνω).]Προτεινόμενη μελέτη: [MMDS] κεφ. 6 (link) [ενότητες 6.3, 6.4].Δείτε ακόμη: [TSKK] κεφ. 6 (link) (ενότητες 6.3, 6.4, 6.7). - Εξόρυξη συχνών συνόλων στοιχείων (μέρος 2), διαφάνειες (έμφαση σε 48-105) από μάθημα Π. Τσαπάρα (Παν. Ιωαννίνων).
- 22/3
22/3
- Κατακερματισμός (hashing) (slides U. Zwick, από μάθημα Advanced Algorithms, Tel Aviv University): κλειστή και ανοιχτή διευθυνσιοδότηση. Universal hash families. Αλυσίδωση.
- Γραμμική και τετραγωνική διερεύνηση (probing). Διπλός κατακερματισμός (double hashing).
- Παράγοντας φόρτου και ανάλυση χρόνου εκτέλεσης βασικών πράξεων.
Προτεινόμενη μελέτη: σημειώσεις (και αναφορές που περιέχονται)
- 29/3
29/3
Αλγόριθμοι Ροών Δεδομένων, εφαρμογές και αφαιρετική αρχιτεκτονική τους, Διακριτά στοιχεία, AMS σκιαγράφημα.
Προτεινόμενη Μελέτη: Μάθημα του Jelani Nelson στο Berkeley. Υποκεφάλαιο 2.2 για το πρόβλημα των Διακριτών Στοιχείων, και υποκεφάλαιο 4.3 για το AMS σκιαγράφημα.
Εναλλακτικά, δείτε και τις διαλέξεις του Jelani Nelson στο Harvard.
Για πρακτικά ζητήματα και εφαρμογές, δείτε μία σύντομη έκθεση εδώ.
Βίντεο της διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)]
- 5/4
5/4
Μείωση διαστάσεων (dimensionality reduction). Λήμμα Johnson-Lindenstrauss.Βίντεο της διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)] - 12/4
12/4
Βασικά στοιχεία μηχανικής μάθησης, βελτιστοποίηση, μέθοδος gradient descent και projected gradient descent.
Βίντεο της διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)]
- 23/4
23/4
Σύντομη επισκόπηση του clustering
Clustering Techniques, The curse of dimensionality, Hierarchical clustering, K-means, BFR algorithm. (Διαφάνειες, 1-47).
Η διάλεξη πραγματοποιήθηκε διαδικτυακά. - 14 May
14 May
Clustering, Link Analysis
Clustering
CURE (Διαφάνειες, 48-56)
Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.1, 7.2, 7.3 και 7.4.
Περαιτέρω μελέτη: [TSKK] Κεφάλαιο 7
Link Analysis
Definition of Page Rank, Structure of the Web, Avoiding Dead Ends, Spider Traps and Taxation, Efficient Computation of Page Rank, Efficient Approaches to Page Rank Iteration (Διαφάνειες, 1-32)
Προτεινόμενη μελέτη: [MMDS] Ενότητες: 5.1,5.2
Η διάλεξη πραγματοποιήθηκε διαδικτυακά.
Βίντεο της Διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)]
- 21 ΜΑΥ
21 ΜΑΥ
LINK ANALYSIS, RECOMMENDATION SYSTEMS
Link Analysis
Efficient Computation of Page Rank, Efficient Approaches to Page Rank Iteration (Διαφάνειες, 33-60)
Προτεινόμενη μελέτη: [MMDS] Ενότητες: 5.1,5.2
Recommendation Systems
The long Tail, Utility Matrix, Content Based Recommendation Systems, Item Profile, User Profile (Διαφάνειες, 1-13)
Προτεινόμενη μελέτη: [MMDS] Κεφάλαιο: 9
Η διάλεξη πραγματοποιήθηκε διαδικτυακά.
Βίντεο της Διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)] - 28 MAY
28 MAY
Recommendation Systems
Collaborative Filtering, Finding Similar Users, Rating prediction, User - User , Item - Item
Hybrid Methods, Combining Global Baseline estimate and Collaborative Filtering (Διαφάνειες, 14-43)
Προτεινόμενη μελέτη: [MMDS] Κεφάλαιο: 9
Η διάλεξη πραγματοποιήθηκε διαδικτυακά.
Βίντεο της Διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)] - 1 JUNE - 5 JUNE
1 JUNE - 5 JUNE
Διάλεξη 4/6: Community Detection
- Εισαγωγή σε community detection. Edge Betweeness και Modularity. Αλγόριθμος Girvan-Newman.
Διαφάνειες (1-23).
Προτεινόμενη μελέτη: [MMDS] 10.1 και 10.2 - Αλγόριθμος Louvain (σύντομη αναφορά).
Προτεινόμενη μελέτη (προαιρετική): σχετικό paper. - Εντοπισμός κοινοτήτων μέσω ιδιοτιμών γράφων, spectral clustering (σύντομη αναφορά).
Διαφάνειες (24-56).
Προτεινόμενη μελέτη: [MMDS] 10.4
Βίντεο της διάλεξης [Απαιτείται συνθηματικό. Ισχύουν περιορισμοί χρήσης (βλ. παραπάνω)] - Εισαγωγή σε community detection. Edge Betweeness και Modularity. Αλγόριθμος Girvan-Newman.