Diario delle lezioni

Totale: 24 lezioni da 2 ore (2*24 = 48 ore), corrispondenti a 6 CFU.

30 settembre 2024 (Lezione n° 1 da 2 ore)

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

1° ottobre 2024 (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
• Backup Tasks
• Combiners
• Funzione di partizione

7 ottobre 2024 (Lezione n° 3 da 2 ore)

• 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

8 ottobre 2024 (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
• MapReduce: cammini di lunghezza 3 in grafi

14 ottobre 2024 (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

15 ottobre 2024 (Lezione n° 6 da 2 ore)

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

21 ottobre 2024 (Lezione n° 7 da 2 ore)

• Introduzione a funzioni Hash
• Compressione di shingles con funzioni Hash
• Vettore caratteristico e matrice caratteristica
• Minhashing e Jaccard similarity
• Minhash signature e matrice delle firme

22 ottobre 2024 (Lezione n° 8 da 2 ore)

• Locality-Sensitive Hashing: dividere la matrice in bande
• Il procedimento completo per la similarità di documenti di testo
• Misure di distanza: distanze euclidee, distanza di Jaccard.

28 ottobre 2024 (Lezione n° 9 da 2 ore)

• Misure di distanza: distanza coseno, Edit distance, distanza di Hamming
• Teoria Locality-Sensitive Hashing
• AND-construction, OR-constriction, S-curve
• LSH per distanza di Gaming
• LSH per distanze euclidee (parte prima)

29 ottobre 2024 (Lezione n° 10 da 2 ore)

• LSH per distanze euclidee (parte seconda)
• Matching di impronte digitali
• Tecniche per rilevare item identici
• Tecniche per item con alto grado di similarità: filtro per lunghezza
• Tecniche per item con alto grado di similarità: indicizzazione del prefisso (prima parte)

4 novembre 2024 (Lezione n° 11 da 2 ore)

• Tecniche per item con alto grado di similarità: indicizzazione del prefisso (seconda parte)
• Frequent itemset: introduzione e applicazioni
• Supporto, frequenza
• Regole di associazione: confidenza, interesse
• Introduzione all’algoritmo A-Priori

5 novembre 2024 (Lezione n° 12 da 2 ore)

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

11 novembre 2024 (Lezione n° 13 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)

12 novembre 2024 (Lezione n° 14 da 2 ore)

• Algoritmo di Tovoinen
• Argomenti per esonero
• Esercizi in preparazione all’esonero

18 novembre 2024 (Lezione n° 15 da 2 ore)

• Esercizi in preparazione all’esonero
• Introduzione al problema del Clustering

19 novembre 2024 (Lezione n° 16 da 2 ore)

• Clustering gerarchico e valutazione della sua efficienza
• Algoritmo K-means di assegnamento di punti
• Scelta del parametro k per il clustering (prima parte)

2 dicembre 2024 (Lezione n° 17 da 2 ore)

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

3 dicembre 2024 (Lezione n° 18 da 2 ore)

• Algoritmo CURE (seconda parte)
• Algoritmo GRGPF

9 dicembre 2024 (Lezione n° 19 da 2 ore)

• Introduzione all’analisi dei link nel Web
• PageRank
• Teleporting
• Calcolo del PageRank (prima parte)

10 dicembre 2024 (Lezione n° 20 da 2 ore)

• Calcolo del PageRank (seconda parte)
• Topic-specific PageRank
• TrustRank e Spam mass
• Cenni a HITS
• Esercizi su PageRank

16 dicembre 2024 ore 9:00-11:00 (Lezione n° 21 da 2 ore)

• Reti sociali: problema dell’individuazione di comunità
• Edge-betweeness per clustering: Algoritmo di Girvan-Newman
• Modularità come misura della qualità di un clustering
• SimRank

16 dicembre 2024 ore 11:00-13:00 (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

17 dicembre 2024 (Lezione n° 23 da 2 ore)

• Esercizi su reti sociali
• Esercizi in preparazione all’esame

7 gennaio 2025 (Lezione n° 24 da 2 ore)

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