Diario delle lezioni

Totale: 21 lezioni da 2 ore (2*21 = 42 ore) e 2 lezioni da 3 ore (2*3 = 6 ore) per un totale di 48 ore (corrispondenti a 6 CFU).

27 settembre 2022 (Lezione n° 1 da 2 ore)

• Presentazione del corso
• Introduzione al Data Mining
• Introduzione ai Big Data
• Principio di Bonferroni
• Introduzione agli algoritmi

3 ottobre 2022 (Lezione n° 2 da 2 ore)

• Introduzione alla computazione distribuita e concorrente
• MapReduce e sua implementazione Hadoop: introduzione
• File system distribuito HDFS: files e chunck
• Architettura distribuita multirack
• Gestione dei fallimenti
• MapReduce: progettazione di algoritmi distribuiti
• Map task
• Reduce task

4 ottobre 2022 (Lezione n° 3 da 2 ore)

• Combiners
• Funzione di partizione
• Rappresentazione di matrici sparse
• MapReduce: prodotto matrice vettore
• Introduzione ai grafi
• Rappresentazione di grafi tramite matrici di adiacenza
• MapReduce: cammini di lunghezza 2 in grafi

11 ottobre 2022 (Lezione n° 4 da 2 ore)

• MapReduce: prodotto di matrici in 2 step
• MapReduce: prodotto di matrici in un unico step
• Estensioni di MapReduce: i Workflow
• Spark: RDD, trasformazioni, azioni, Lazy evaluation, Lineage

17 ottobre 2022 (Lezione n° 5 da 2 ore)

• Modello di costo di comunicazione in MapReduce
• Reducer Size e Replication Rate
• Mapping schema: grafo bipartito input/output
• Similarity join con MapReduce
• Lower bound al replication rate (prima parte)

18 ottobre 2022 (Lezione n° 6 da 2 ore)

• Lower bound al replication rate (seconda parte)
• Esercizi su MapReduce
• Introduzione a Similar items
• Jaccard similarity
• Shingling di documenti di testo

24 ottobre 2022 (Lezione n° 7 da 2 ore)

• Introduzione a funzioni Hash
• Compressione di shingles con funzioni Hash
• Minhashing e Jaccard similarity

25 ottobre 2022 (Lezione n° 8 da 2 ore)

• Minhash signature
• Locality-Sensitive Hashing: dividere la matrice in bande
• Il procedimento completo per la similarità di documenti di testo

8 novembre 2022 (Lezione n° 9 da 2 ore)

• Misure di distanza: distanze euclidee, distanza di Jaccard, distanza coseno, Edit distance, distanza di Hamming
• Teoria Locality-Sensitive Hashing
• AND-construction, OR-constriction, S-curve

10 novembre 2022 (Lezione n° 10 da 2 ore)

• LSH per distanza di Hamming
• LSH per distanze euclidee
• Matching di impronte digitali

14 novembre 2022 (Lezione n° 11 da 2 ore)

• Tecniche per item con alto grado di similarità: filtro per lunghezza
• Tecniche per item con alto grado di similarità: indicizzazione del prefisso
• Frequent itemset: introduzione e applicazioni
• Supporto, frequenza

15 novembre 2022 (Lezione n° 12 da 2 ore)

• Regole di associazione: confidenza, interesse
• Algoritmo A-Priori

21 novembre 2022 (Lezione n° 13 da 2 ore)

• Esempio esecuzione Algoritmo A-Priori
• Algoritmo di Park-Chen-Yu (PCY)

22 novembre 2022 (Lezione n° 14 da 2 ore)

• Varianti multi-stage e multi-hash dell’algoritmo PCY
• Esempio di prestazioni migliorate con la variante multi-hash PCY
• Algoritmo randomizzato “semplice”
• Algoritmo distribuito di Savarese-Savasere-Omiecinski-Navathe (SON) (I parte)

24 novembre 2022 (Lezione n° 15 da 2 ore)

• Algoritmo distribuito di Savarese-Savasere-Omiecinski-Navathe (SON) (II parte)
• Algoritmo di Tovoinen
• Introduzione al problema del Clustering

28 novembre 2022 (Lezione n° 16 da 2 ore)

• Clustering gerarchico e valutazione della sua efficienza
• Algoritmo K-means di assegnamento di punti

29 novembre 2022 (Lezione n° 17 da 2 ore)

• Scelta del parametro k per il clustering
• Algoritmo di Bradley, Fayyad e Reina

5 dicembre 2022 (Lezione n° 18 da 3 ore)

• Algoritmo CURE
• Algoritmo GRGPF
• Introduzione all’analisi dei link nel Web

6 dicembre 2022 (Lezione n° 19 da 2 ore)

• PageRank
• Teleporting
• Calcolo del PageRank (prima parte)
• Esercizi in preparazione all’esonero

12 dicembre 2022 (Lezione n° 20 da 3 ore)

• Calcolo del PageRank (seconda parte)
• Topic-specific PageRank
• TrustRank e Spam mass
• Cenni a HITS
• Esercizi in preparazione al parziale

13 dicembre 2022 (Lezione n° 21 da 2 ore)

• Reti sociali: edge-betweeness per clustering
• Algoritmo di Girvan-Newman
• Modularità come misura della qualità di un clustering
• SimRank

19 dicembre 2022 (Lezione n° 22 da 2 ore)

• Ricerca di comunità in grafi sociali: grafi bipartiti completi
• Correlazione con il problema degli itemset frequenti
• Modelli generativi per la determinazione di comunità: AGM e BigCLAM

20 dicembre 2022 (Lezione n° 23 da 2 ore)

• Panoramica dei tool per big data: import.io, Scraper API, RawGraphs, Gephi, Carto, Tableau
• Esercizi in preparazione all’esame

9 gennaio 2023 (Lezione aggiuntiva da 1 ora)

• Correzione esonero
• Esercizi in preparazione all’esame