Περιγραφή εβδομάδας

• Γενικά
  

  Γενικά

  Το μάθημα προσφέρεται στα πλαίσια του ΔΠΜΣ "Επιστήμη Δεδομένων και Μηχανική Μάθηση" και στους Υ.Δ. της ΣΗΜΜΥ ως "Θεωρητική Πληροφορική ΙΙ", καθώς και σε άλλα μεταπτυχιακά προγράμματα (ΑΛΜΑ, ΕΜΕ).
  

  Οι διαλέξεις για φέτος (2018-19) ξεκίνησαν στις 28/2 και γίνονται κάθε Πέμπτη στην αίθουσα 007 του Ν. Κτ. Ηλεκτρολόγων ώρα 5:00μμ-8:00μμ. 

  
  

  Διδάσκοντες
  

  • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής (fotakis@cs.ntua.gr)
  • Άρης Παγουρτζής, Αναπλ. Καθηγητής (pagour@cs.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

  
  

  • Ανακοινώσεις Φόρουμ
  • Διαφάνειες Φάκελος
  • Εκφωνήσεις Ασκήσεων Φάκελος
• 27 February - 5 March
  

  27 February - 5 March

  28/2

  • Εισαγωγή - διαδικαστικά. 
  • Εξόρυξη κανόνων συσχέτισης και συνόλων στοιχείων που εμφανίζονται συχνά σε μεγάλα δεδομένα. Αλγόριθμοι A-priori και FP-growth. 
    Προτεινόμενη μελέτη: [MMDS] κεφ. 6.
    
    

  
  
• 6 March - 12 March
  

  6 March - 12 March

  7/3

  • Εξόρυξη συχνών συνόλων στοιχείων (συνέχεια). Αλγόριθμοι PCY, Multistage, Multihash, Toivonen.
    Προτεινόμενη μελέτη: [MMDS] κεφ. 6.
  • Κατακερματισμός (hashing): κλειστή και ανοιχτή διευθυνσιοδότηση. Γραμμική και τετραγωνική βολιδοσκόπηση (probing). Διπλός κατακερματισμός (double hashing).
    Σημειώσεις (κεφ. 1).
• 13 March - 19 March
  

  13 March - 19 March

  14/3

  • Κατακερματισμός (hashing): Universal hash families. Παράγοντας φόρτου και ανάλυση χρόνου εκτέλεσης βασικών πράξεων.
    Σημειώσεις (κεφ. 1).
  • Επεξεργασία ροών δεδομένων (streams): αλγόριθμοι προσεγγιστικής μέτρησης Morris και DGIM (διαφάνειες).
    Προτεινόμενη μελέτη: [FDS] 6.2.2, [MMDS] 4.6.
    

  
  
• 20 March - 26 March
  

  20 March - 26 March

  21/3: Ροές Δεδομένων

  • Επεξεργασία ροών δεδομένων (streams): εξόρυξη συχνών συνόλων στοιχείων με φθίνοντα παράθυρα (διαφάνειες, 25-31).
    Προτεινόμενη μελέτη: [MMDS] 4.7.
  • Επεξεργασία ροών δεδομένων (streams): Bloom φίλτρα, εκτίμηση διαφορετικών στοιχείων, εκτίμηση ροπών διανύσματος εμφανίσεων στοιχείων (διαφάνειες, 1-36).
    Προτεινόμενη μελέτη: [MMDS] 4.3, 4.4, 4.5. [FDS] 6.2.
    
    
• 27 March - 2 April
  

  27 March - 2 April

  28/3: Ροές Δεδομένων

  • Επεξεργασία ροών δεδομένων (streams): Δειγματοληψία από ροή δεδομένων, reservoir sampling (διαφάνειες, 11-21), εκτίμηση συχνότητας εμφάνισης συχνών στοιχείων, αλγόριθμοι lossy counting και count-min sketch (μελετήστε τις σημειώσεις εδώ και εδώ, και τις διαφάνειες εδώ και εδώ).
  • Εύρεση παρόμοιων αντικειμένων: επεξεργασία κειμένων, shingling (διαφάνειες, 1-24). 
    Προτεινόμενη μελέτη: [MMDS] 3.1, 3.2. 

  
  

  Περαιτέρω μελέτη για ροές δεδομένων:

  • Σημειώσεις και βιβλίο του S. Muthukrishnan.
  • Η εργασία των Manku και Motwani όπου παρουσιάζεται ο αλγόριθμος lossy counting. 
  • Η εργασία των Cormode και Muthukrishnan όπου παρουσιάζεται ο αλγόριθμος count-min sketch. 
• 3 April - 9 April
  

  3 April - 9 April

  4/4: Εύρεση παρόμοιων αντικειμένων

  • Εύρεση παρόμοιων αντικειμένων: shingling, min-hashing, locality sensitive hashing (διαφάνειες, 25-59).
    Προτεινόμενη μελέτη: [MMDS] 3.3 - 3.8 και σημειώσεις Jeff Philips για Min Hashing, Locality Sensitive Hashing, και αποστάσεις.
  • Αναλυση συνδέσμων στο WWW, η μέθοδος PageRank (διαφάνειες, 1-25).
    Προτεινόμενη μελέτη: [MMDS] 5.1. 
• 10 April - 16 April
  

  10 April - 16 April

  11/4: Ανάλυση συνδέσμων στο WWW, η μέθοδος PageRank. 

  • Αναλυση συνδέσμων στο WWW, η μέθοδος PageRank (1ο σετ διαφανειών (26-60), και 2ο σετ διαφανειών (1-60)).
    
  • Προτεινόμενη μελέτη: [MMDS] Κεφ. 5. Δείτε ακόμη τις παρακάτω σημειώσεις για αλυσίδες Markov, για το PageRank, και για την υλοποίηση του PageRank.

  
  
• 17 April - 23 April
  

  17 April - 23 April

  18/4:  

  • Αλγοριθμικά προβλήματα πίσω από τη διαφήμιση στο Web (σετ διαφανειών). 
    Προτεινόμενη μελέτη: [MMDS], Κεφ. 8. Δείτε ακόμη αυτές τις σημειώσεις για το πρόβλημα του Online Bipartite Matching, και αυτή την εργασία για το Generalized Second Price auction. Μπορείτε ακόμη να δείτε την ενδιαφέρουσα μονογραφία του Aranyak Mehta για αλγοριθμικά προβλήματα πίσω από τα sponsored search auctions. 
  • Σύντομη επισκόπηση του clustering (διαφάνειες, 1-21).
    Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.1 και 7.2. 
• 8 May - 14 May
  

  8 May - 14 May

  9/5:  

  • Σύντομη επισκόπηση του clustering (συνέχεια από προηγούμενη διάλεξη, διαφάνειες).
    Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.3 και 7.4.
  • Recommendation Systems: Content based recommendation, collaborative filtering (διαφάνειες 1ο μέρος, και διαφάνειες 2ο μέρος, 1-16). 
    Προτεινόμενη μελέτη: [MMDS] Ενότητες: 9.1, 9.2, 9.3 και 9.5.
• 15 May - 21 May
  

  15 May - 21 May

  16/5:  

  • Εισαγωγή σε community detection. Edge Betweeness και Modularity. Αλγόριθμος Girvan-Newman. Διαφάνειες (1-23).
    Προτεινόμενη μελέτη: [MMDS] 10.1 και 10.2
  • Αλγόριθμος Louvain. Προτεινόμενη μελέτη: σχετικό paper.
  • Εύρεση συσχετίσεων μέσω frequent itemset mining. Διαφάνειες (57-64). Προτεινόμενη μελέτη: [MMDS] 10.3
  • Τριαδικές σχέσεις, μέτρηση τριγώνων σε γράφο. Προτεινόμενη μελέτη: [MMDS] 10.7 (έως 10.7.3)

  
  
• 22 May - 28 May
  

  22 May - 28 May

  23/5:  

  • Εντοπισμός κοινοτήτων μέσω ιδιοτιμών γράφων, spectral clustering. Διαφάνειες (24-56).
    Προτεινόμενη μελέτη: [MMDS] 10.4
    
  • Εντοπισμός επικαλυπτόμενων κοινοτήτων με μεγιστοποίηση πιθανοφάνειας (MLE). Διαφάνειες (1-25). 
    Προτεινόμενη μελέτη: [MMDS]  10.5
  • Ομοιότητες σε γράφους μέσω τυχαίων περιπάτων (Simrank).
    Προτεινόμενη μελέτη: [MMDS] 10.6
    
• 29 May - 4 June
  

  29 May - 4 June

  30/5

  • Εισαγωγή σε Blockchain & Consensus
    Slides

  • Εισαγωγή στο Bitcoin (transactions, blocks, proof-of-work)
    Slides