Diario delle lezioni

Ogni lezione è da 2 ore.

Totale: 24 lezioni (2*24 = 48 ore) per 6 CFU.

27 settembre 2021 (Lezione n° 1)

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

28 settembre 2021 (Lezione n° 2)

• 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 2021 (Lezione n° 3)

• Combiners
• Funzione di partizione
• MapReduce: prodotto matrice vettore
• MapReduce: cammini di lunghezza 2 in grafi

5 ottobre 2021 (Lezione n° 4)

• 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
• Modello di costo di comunicazione in MapReduce

11 ottobre 2021 (Lezione n° 5)

• Reducer Size e Replication Rate
• Mapping schema: grafo bipartito input/output
• Similarity join con MapReduce
• Lower bound al reoplication rate

12 ottobre 2021 (Lezione n° 6)

• Esercizi su MapReduce
• Introduzione a Similar items
• Jaccard similarity
• Shingling di documenti di testo
• Introduzione a funzioni Hash
• Compressione di shingles con funzioni Hash

18 ottobre 2021 (Lezione n° 7)

• Minhashing e Jaccard similarity
• Minhash signature
• Locality-Sensitive Hashing: dividere la matrice in bande (I parte)

19 ottobre 2021 (Lezione n° 8)

• Locality-Sensitive Hashing: dividere la matrice in bande (II parte)
• Il procedimento completo per la similarità di documenti di testo
• Misure di distanza: distanze euclidee, distanza di Jaccard, distanza coseno, Edit distance, distanza di Hamming

25 ottobre 2021 (Lezione n° 9)

• Teoria Locality-Sensitive Hashing
• AND-construction, OR-constriction, S-curve
• LSH per distanza di Hamming
• LSH per distanze euclidee

26 ottobre 2021 (Lezione n° 10)

• Matching di impronte digitali
• Tecniche per item con alto grado di similarità: filtro per lunghezza

2 novembre 2021 (Lezione n° 11)

• Tecniche per item con alto grado di similarità: indicizzazione del prefisso
• Frequent itemset: introduzione e applicazioni
• Supporto, frequenza
• Regole di associazione: confidenza, interesse

8 novembre 2021 (Lezione n° 12)

• Algoritmo A-Priori
• Esempio esecuzione Algoritmo A-Priori
• Algoritmo di Park-Chen-Yu (PCY)
• Varianti multi-stage e multi-hash dell’algoritmo PCY

9 novembre 2021 (Lezione n° 13)

• Algoritmo di Park-Chen-Yu (PCY)
• Varianti multi-stage e multi-hash dell’algoritmo PCY
• Esempio di prestazioni migliorate con la variante multi-hash PCY

15 novembre 2021 (Lezione n° 14)

• Algoritmo randomizzato “semplice”
• Algoritmo distribuito di Savarese-Savasere-Omiecinski-Navathe (SON)
• Algoritmo di Tovoinen

16 novembre 2021 (Lezione n° 15)

• Introduzione al problema del Clustering
• Clustering gerarchico

22 novembre 2021 (Lezione n° 16)

• Efficienza del clustering gerarchico migliorata con Heap
• Algoritmo K-means di assegnamento di punti
• Scelta del parametro k per il clustering (prima parte)

23 novembre 2021 (Lezione n° 17)

• Scelta del parametro k per il clustering (seconda parte)
• Algoritmo di Bradley, Fayyad e Reina

29 novembre 2021 (Lezione n° 18)

• Algoritmo CURE
• Algoritmo GRGPF

30 novembre 2021 (Lezione n° 19)

• Introduzione all’analisi dei link nel Web
• PageRank
• Teleporting

6 dicembre 2021 (Lezione n° 20)

• Soluzione alternativa al problema dei dead-end
• Calcolo del PageRank
• Topic-specific PageRank
• TrustRank e Spam mass
• Cenni a HITS

7 dicembre 2021 (Lezione n° 21)

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

13 dicembre 2021 (Lezione n° 22)

• 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 (I parte)

13 dicembre 2021 (Lezione aggiuntiva – ore 14)

• Esercizi in preparazione all’esonero

14 dicembre 2021 (Lezione n° 23)

• Esercizi su MapReduce
• Modelli generativi per la determinazione di comunità: AGM e BigCLAM (II parte)
• SimRank

20 dicembre 2021 (Esonero)

• Esonero

21 dicembre 2021 (Lezione n° 24)

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