Corso di Laurea Magistrale in
Ingegneria Informatica
Grandi Moli di Dati (9 CFU)
A.A. 2010/2011

LEZIONI GIORNALIERE

Introduzione al Corso

  • 7 marzo: Trend relativi alla quantità di dati prodotti e alla capacità di memorizzare, comunicare ed elaborare dati. Organizzazione del corso
Materiale di riferimento: Articolo M. Hilbert, P. Lopez. The World's Technological Capacity to Store, Communicate, and Compute Information. Science Express, 10/02/2011

Algoritmica per Memoria Esterna

  • 8 marzo: Gerarchia di memoria. Nozioni di località (temporale e spaziale). Introduzione all'algoritmica per grosse moli di dati. Modelli di calcolo: definizione generale, modello RAM, Disk Model (DM). Motivazione tecnologica. Sorting su DM: 2-Mergesort.
  • 10 marzo: Analisi di 2-Mergesort (Complessità di I/O e Work). MB-Mergesort: pseudocodice e impostazione delle relazioni di ricorrenza.
  • 14 marzo: Analisi di MB-Mergesort (Complessità di I/O e Work). Confronto di prestazioni e località tra 2-Mergesort e MB-Mergesort. Esempio numerico. Problema 3 della dispensa di esercizi su algoritmica su memoria esterna.
  • 15 marzo: Problema 3 della dispensa di esercizi su algoritmica su memoria esterna (analisi). Trasposizione di una matrice A pXq: definizione del problema; soluzione tramite ordinamento; soluzione efficiente nei casi: (1) N<=M; e (2.1) N>M e p,q >=B.
  • 21 marzo: Trasposizione di una matrice A pXq: soluzione efficiente nei casi (2.2, 2.3) N>M e min(p,q) < B <= max(p,q); e (2.4) N>M e B> max(p,q); formule finali. Problema 4 della dispensa di esercizi.
  • 22 marzo: Problemi 5 e 6 della dispensa di esercizi. Esempi di domande teoriche sull'Algoritmica per Memoria Esterna.
  • 24 marzo: Discrete Fourier Transform di ordine N su un vettore A: definizione del problema; algoritmo di Cooley-Tukey con N=pxq (FFT(a,q)); analisi della complessità di I/O e work per q=2; analisi della complessità di I/O per q=M.
  • 28 marzo: Analisi del work di FFT(A,q) con q=M. Confronto della località di FFT(A,2) e FFT(A,M). Esercizio: analisi di FFT(A,q) con q=sqrt(M).
  • 29 marzo: Introduzione agli indici: definizioni di record e chiave; definizione di indice; indici primari e secondari. Realizzazione di indici primari con chiave che non ammette duplicati tramite B+-Tree: definizione e calcolo del numero di livelli; ricerca di un record.
  • 31 marzo: Realizzazione di indici primari con chiave che non ammette duplicati tramite B+-Tree: inserimento in un record; cancellazione di un record.
  • 4 aprile: Realizzazione di indici primari con chiave che non ammette duplicati tramite B+-Tree: metodi per Range Query, Next; esercizio sulla costruzione (dalle dispense). Realizzazione di indici primari con chiave che ammette duplicati tramite B+-Tree: modifiche alla definizionel di B+-Tree; metodo di ricerca.
  • 5 aprile: Realizzazione di indici primari con chiave che ammette duplicati tramite B+-Tree: metodi di inserimento e cancellazione. Realizzazione di indici secondari tramite B+-Tree: cenni. Esercizi (I compitino 2010).
Materiale di riferimento:
  1. Dispensa su Algoritmica per Memoria Esterna.
  2. Nota sulle prestazioni del B+-Tree.
  3. Esercizi d'esame.
  4. I Compitino 2010

Datamining

  • 7 aprile: Definizione di Data Mining e Knowledge Discovery in Databases (KDD). Problemi di Data Mining: Predittivi (Classification, Regression); Descrittivi (Association Analysis, Cluster Analysis, Anomaly Detection). Distinzione tra OLTP, OLAP e Data mining. OLAP: nozioni di Data Warehouse (DW) e Data Mart.
  • 11 aprile: OLAP: modello multidimensionale; fact table; architettura ROLAP, architettura MOLAP; operazioni (contrazione di dimensioni, slice, dice, cube operator. Regole Associative: definizione del problema computazionale; applicazioni; numero di regole distinte per un insieme di d item; nozione di itemset frequente.
  • 12 aprile: I Compitino
  • 14 aprile: Association Analysis: strategia generale per la determinazione delle R.A.; reticolo degli itemset frequenti; antimonotonicità del supporto, algoritmo APRIORI (pseudocodice; funzione APRIORI-GEN; correttezza; esempio).
  • 18 aprile: Association Analysis: Hast Tree (definizione, funzione SEARCH, esempi).
  • 19 aprile: Association Analysis: algoritmo di generazione delle R.A. a partire dagli itemset frequenti e dai loro supporti; correttezza dell'algoritmo.
  • 21 aprile: Association Analysis: esercizi 6.3.b, 6.3.d, 6.4.a del libro di testo; prestazioni di APRIORI e dell'algoritmo di generazione delle regole associative (esercizio) nel Disk Model.
  • 28 aprile: Association Analysis: nozioni di itemset chiuso, itemset chiuso e frequente, itemset massimale, e loro proprietà.
  • 2 maggio: Association Analysis: esempio in cui il numero di itemset massimali e il numero di itemset chiusi e frequenti è esponenziale nella taglia dell'input; problema 3 della dispensa di esercizi; nozioni di Top-K frequent itemset e Top-K frequent closed itemset. Richiamo del concetto di Trie.
  • 3 maggio: Association Analysis: capacita' del parametro K di limitare il numero dei Top-K frequent itemset e Top-K frequent closed itemset.
  • 5 maggio: Association Analysis: Significatività statistica degli itemset frequenti (hypothesis testing, paradosso del compleanno, multiple hypthesis testing, metodo Bonferroni).
  • 9 maggio: Association Analysis: esercizio sull significatività statistica degli itemset frequenti; nozioni di Lift e Interest Factor; esercizio 6.17 (p.413) dal libro di testo.
  • 10 maggio: Association Analysis: esercizio 6.17 (p.413) dal libro di testo; problemi relativi a realtà segmentate (paradosso di Simpson) e a cross-support pattern. Problemi 1 e 5.b della dispensa di esercizi.
  • 12 maggio: Association Analysis: Problemi 4 e 5.a della dispensa di esercizi; esempi di domande da I parte; Regole associative generalizzate
  • 16 maggio: Association Analysis: Regole associative generalizzate; Sequential Patterns (definizione del problema, strategia APRIORI).
  • 17 maggio: Association Analysis: Sequential Pattern (correttezza della strategia APRIORI); esercizio 7.10 (p. 479) del testo; Subgraph Pattern (definizione del problema).
  • 19 maggio: Association Analysis: Subgraph Pattern (nozione di uguaglianza e contenimento per grafi, strategia APRIORI).
  • 23 maggio: Association Analysis: Subgraph Pattern (strategia APRIORI, esercizio 7.19 (p. 483) del testo, correttezza di APRIORI-GEN).
  • 24 maggio: Classification: definizione del problema; tipologie di attributi (nominal, ordinal, interval, ratio); approccio generale; definizione di albero di decisione; tipi di test; Algoritmo di Hunt per decision tree induction.
  • 30 maggio: Discussione questionario di valutazione. Classification: applicazione dell'Algoritmo di Hunt (con Gini) all'esempio di Figura 4.6 del testo; esercizio 4.6 del testo.
  • 31 maggio: Classificazione: esercizio 4.4 del testo; esercizi vari; misure per valutare la qualità di un classification model (training error, training error rate, generalization error, accuracy); fenomeni di underfitting e overfitting;
  • 6 giugno: Classificazione: modi per evitare l'overfitting (pre-pruning, post-pruning con il Minimum Description Length principle); metodi per valutare la qualità di una classification technique (holdout, random subsampling, cross-validation);
  • 7 giugno: Classificazione: stima di un intervallo di confidenza per l'accuracy (o per l'error rate); confronto tra due modelli basta sugli intervalli di confidenza per l'error rate; classificazione basata su regole (idea, nozioni di insieme di regole mutuamente esclusive ed esaustive, relazioni con gli alberi di decisione); esercizio 5.1 del testo.
  • 9 giugno: Classificazione: metodi diretti per l'induzione di un insieme di regole (algoritmo RIPPER); esercizi 5.2.(c) e 5.4.(b) del testo; classificazione Bayesiana (idea, teorema di Bayes, approccio naive).
  • 14 giugno: Classificazione: classificazione Bayesiana (calcolo delle conditional probability per le diverse tipologie di attributi, uso dell'm-estimate approach); esercizio 5.7 del testo; esercizio ispirato al 5.9 del testo.
  • 16 giugno: Riepilogo su: regole associative generalizzate, sequential pattern, subgraph pattern, classificazione. Esercizi vari, tra cui 7.18 (parti c e d), ed esempi di domande da I parte.
Materiale di riferimento:
  1. Testo: Introduction to Data Mining di P.N. Tan, M. Steinbach e V. Kumar. Cap.1, Cap.3 (3.4), Cap.4, Cap.5 (5.1, 5.3.1, 5.3.2, 5.3.3), Cap.6 (6.1, 6.2, 6.3, 6.4, 6.7, 6.8), Cap.7 (7.1, 7.2.1, 7.4.1, 7.4.2, 7.5), Appendice C.
  2. Esercizi d'esame.
  3. Paragrafo 12.3 sui Trie del testo di Goodrich e Tamassia (Data Structures and Algorithms in Java, 4th Ed., 2006).
  4. Nota su Top-K Frequent (Closed) Itemset.
  5. Pagina wiki su statistical hyptothesis testing; Pagina wiki sul metodo Bonferroni.


Ultimo aggiornamento: 29 giugno 2011 Vai alla pagina iniziale