Αλγοριθμική Επιστήμη Δεδομένων
Weekly outline
- Ακαδημαϊκό Έτος 2024-2025
Ακαδημαϊκό Έτος 2024-2025
Το μάθημα προσφέρεται στους σπουδαστές του ΔΠΜΣ "Επιστήμη Δεδομένων και Μηχανική Μάθηση", στους Υ.Δ. της ΣΗΜΜΥ, καθώς και σε άλλα μεταπτυχιακά προγράμματα (ΑΛΜΑ, ΕΜΕ, Μαθηματική Προτυποποίηση).
Διαλέξεις
- Παρασκευή, 13:15-16:00, αίθ. 003, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ
(οι φοιτητές του ΑΛΜΑ θα παρακολουθούν μία πρόσθετη ώρα, 16:15-17:00)
Έναρξη
- 14/02/2025
Διδάσκοντες
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Δώρα Σούλιου, ΕΔΙΠ (dsouliou@mail.ntua.gr)
Βιβλιογραφία
- [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
- Παρασκευή, 13:15-16:00, αίθ. 003, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ
- 1η διάλεξη
1η διάλεξη
Διάλεξη 14/2
- Εισαγωγή - διαδικαστικά (διαφάνειες)
Εισαγωγή στη Θεωρία Υπολογισμού (διαφάνειες)
Προτεινόμενη μελέτη:
- S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: Algorithms (κεφ. 0 και 8).
- Σημειώσεις Jeff Erickson για μη-ντετερμινισμό και για NP-πληρότητα.
- 2η Διάλεξη
2η Διάλεξη
- 3η διάλεξη
3η διάλεξη
Διάλεξη 10/3
Data Mining II
- Εξόρυξη συχνών συνόλων στοιχείων (μέρος 2): αλγόριθμοι με λιγότερες διασχίσεις βάσης. Διαφάνειες (έμφαση στις διαφ. 74-103) από μάθημα Π. Τσαπάρα (Παν. Ιωαννίνων).
Προτεινόμενη μελέτη: [MMDS] κεφ. 6 (link) [ενότητες 6.3, 6.4].
Δείτε ακόμη: [TSKK] κεφ. 6 (link) (ενότητα 6.5). - 4η Διάλεξη
4η Διάλεξη
Διάλεξη 14/3
Data Mining III
- Εξόρυξη συχνών συνόλων στοιχείων (μέρος 3): Εύρεση κανόνων συσχέτισης, η μέθοδος A-priori για κανόνες. Μετρικές σπουδαιότητας κανόνων. Διαφάνειες (έμφαση στις διαφ. 48-64 και 64-73) από μάθημα Π. Τσαπάρα (Παν. Ιωαννίνων).
Προτεινόμενη μελέτη: [MMDS] κεφ. 6 (link) [ενότητες 6.3, 6.4].
Δείτε ακόμη: [TSKK] κεφ. 6 (link) (ενότητα 6.5).Κατακερματισμός (hashing) I
(διαφάνειες U. Zwick [1-19] από μάθημα Advanced Algorithms, Tel Aviv University):
- Κλειστή και ανοιχτή διευθυνσιοδότηση. Universal hash families. Αλυσίδωση.
- Παράγοντας φόρτου και επίδρασή του στον χρόνο εκτέλεσης.
- 5η Διάλεξη
5η Διάλεξη
Διάλεξη 21/3
Κατακερματισμός (hashing) II
(διαφάνειες U. Zwick [20-54] από μάθημα Advanced Algorithms, Tel Aviv University):
- Επιθυμητές ιδιότητες. Καθολικότητα και k-ανεξαρτησία. Carter-Wegman Universal hash family.
- Ανάλυση χρόνου βασικών πράξεων στην κλειστή και ανοιχτή διεθυνσιοδότηση.
- Μέθοδοι διερεύνησης στην ανοιχτή διευθυνσιοδότηση: γραμμική, τετραγωνική, διπλός κατακερματισμός.
- Τέλειος κατακερματισμός (perfect hashing). Κατακερματισμός κούκου (Cuckoo hashing).
Προτεινόμενη μελέτη: σημειώσεις (και αναφορές που περιέχονται).
- 6η Διάλεξη
6η Διάλεξη
Διάλεξη 28/3
Σύντομη επισκόπηση του clustering
Clustering Techniques, The curse of dimensionality, Hierarchical clustering, K-means(Διαφάνειες, 1-31).
Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.1, 7.2, 7.3.Περαιτέρω μελέτη: [TSKK] Κεφάλαιο 7 - 7η Διάλεξη
7η Διάλεξη
Διάλεξη 4/4
Σύντομη επισκόπηση του clustering
- Clustering Techniques, BFR algorithm, Cure(Διαφάνειες, 32-56).
- Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.3, 7.4.
- Περαιτέρω μελέτη: [TSKK] Κεφάλαιο 7
Recommendation Systems I
- The long Tail, Utility Matrix, Content Based Recommendation Systems, Item Profile, User Profile.
Προτεινόμενη μελέτη: [MMDS] Κεφάλαιο: 9 - 8η Διάλεξη
8η Διάλεξη
Διάλεξη 11/4
Recommendation Systems II
Collaborative Filtering, Finding Similar Users, Rating prediction, User - User , Item - Item
Hybrid Methods, Combining Global Baseline estimate and Collaborative Filtering
Προτεινόμενη μελέτη: [MMDS] Κεφάλαιο: 9 - 9η Διάλεξη
9η Διάλεξη
Διάλεξη 2/5
Community Detection Ι
- Εισαγωγή σε community detection. Edge Betweeness και Modularity
- Αλγόριθμος Girvan-Newman
Προτεινόμενη μελέτη: [MMDS] 10.1 και 10.2
- Αλγόριθμος Louvain
Διαφάνειες (27-37)
Προτεινόμενη μελέτη: σχετικό paper- Trawling (Frequent itemsets based community detection)