Algoritmi di base e avanzati di data mining su dati di tipo relazionale e transazionale: mining attraverso la ricerca di regole associative, pattern sequenziali, clustering e classificazione.
Strutture dati e algoritmi in memoria secondaria: B-alberi, B+-alberi, metodi hash, ordinamento, rappresentazione di dati multidimensionali, gestione dei flussi di dati.
- J. Leskovec, A. Rajaraman, J. D. Ullman, Mining of Massive Datasets, Stanford InfoLab, 2010
- P.-N. Tan, M. Steinbach, V. Kumar, Introduction to Data Mining, Pearson, 2006
- J.S. Vitter, Algorithms and Data Structures for External Memory, nowPublishers Inc. 2008
Obiettivi Formativi
Lo scopo di questo corso è quello di introdurre gli studenti alle principali strutture dati per memoria esterna, alle principali tecniche di data mining su dati di tipi relazionale e transazionale e alla loro sperimentazione.
Conoscenze - Alla fine del corso gli studenti avranno una buona conoscenza delle strutture per l'organizzazione dei dati in memoria secondaria e degli algoritmi per l'analisi e la ricerca di regolarità nei dati.
Competenze acquisite - Lo studente acquisisce le competenze per comprendere le problematiche di gestione di dati su memorie di massa e per la loro elaborazione ai fini di estrarre nuova conoscenza.
Capacità acquisite alle fine del corso - Gli studenti saranno in grado di scegliere la struttura dati più adatta per l'organizzazione di informazioni e l'algoritmo di data mining più idoneo all'analisi di dataset reali.
Prerequisiti
Concetti di base di algoritmi, strutture dati e basi di dati. Concetti di base di analisi degli algoritmi. Linguaggio SQL.
Metodi Didattici
CFU: 12
Numero di ore totali del corso: 300
Numero di ore per studio personale e altre attività formative di tipo individuale: 204
Numero di ore relative alle attività in aula: 96
Le attività in aula includono lezioni frontali ed esercitazioni pratiche con il software WeKA e altri software open-source.
Altre Informazioni
Orario di ricevimento:
Prof. Donatella Merlini
Previo Appuntamento via e-mail:
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni 65
50134 Firenze (FI)
Tel. 055 2751509
E-Mail: donatella.merlini@unifi.it
Prof. M.Cecilia Verri
Previo Appuntamento via e-mail:
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni 65
50134 Firenze (FI)
Tel. 055 2751513
E-Mail: mariacecilia.verri@unifi.it
Modalità di verifica apprendimento
L'esame consiste nelle seguenti attività:
- Esame scritto, con esercizi e domande sulle strutture dati e gli algoritmi presentati durante le lezioni.
- Esame orale, che include la discussione di un progetto con una presentazione di gruppo e la discussione degli argomenti presentati durante le lezioni.
- Un progetto (da svolgere in piccoli gruppi, massimo tre persone) che consiste in esercizi che richiedono l'utilizzo di strumenti di data mining per l'analisi dei dati. Gli esercizi includono: comprensione dei dati, analisi di clustering, estrazione di regole e pattern frequenti e classificazione. Il progetto deve essere eseguito utilizzando il software Weka.
Per accedere all'esame orale i candidati devono aver superato la prova scritta.
Il voto finale sarà calcolato come media del voto dell'esame scritto e dell'esame orale.
Programma del corso
Data Mining - Algoritmi di base e avanzati di data mining su dati di tipo relazionale e transazionale: mining attraverso la ricerca di regole associative, pattern sequenziali, clustering e classificazione. In particolare nel corso verranno presentati l'algoritmo di clustering K-means e alcune sue varianti, gli algoritmi di clustering gerarchico agglomerativo single link, complete link, group average e Ward; l'algoritmo di clustering basato su densità DBscan; gli algoritmi per la ricerca di regole associative Apriori (con struttura hash tree per la generazione degli itemset candidati) e FP-Growth; algoritmi Apriori-like per la ricerca di pattern sequenziali; algoritmi di classicazione basati su alberi decisionali, su regole e nearest-neighbor. Verranno presentate tecniche per il preprocessing, postprocessing, l'esplorazione e la visualizzazione dei dati. Tutti gli algoritmi e le metodologie presentati durante il corso verranno sperimentate con il software WeKA e altri software open-source.
Data Organization - Introduzione ai big data. Organizzazione delle memorie esterne: gerarchie di memoria, gestione delle gerarchie di memoria
Algoritmi e strutture dati per memoria esterna: operazioni fondamentali e limiti di complessità. Ordinamento esterno: mergesort.
Ricerca in memoria esterna: tecniche basate su strutture ad albero (B-trees, B+-trees), tecniche hash (statico, dinamico, estendibile, virtuale, lineare). Organizzazione di dati multidimensionali (Kd-trees, R-trees, R*-trees). Indici bitmap. Gestione di data streams.