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.
Al termine dell’insegnamento lo studente:
• avrà una buona conoscenza delle problematiche legate all’organizzazione dei dati in memoria esterna;
• avrà compreso i meccanismi principali di organizzazione e gestione di grandi quantità di dati;
• avrà compreso il funzionamento degli algoritmi per l’analisi e la ricerca di regolarità nei dati e li saprà utilizzare nei contesti specifici al fine di estrarre nuova conoscenza;
• sarà in grado di scegliere l’organizzazione dei dati più idonea a rappresentare le informazioni di un dato problema
• sarà in grado di scegliere l’algoritmo di data mining più idoneo all’analisi di dataset reali;
• sarà in grado di esporre i risultati di un algoritmo in funzione dei parametri scelti, aiutandosi anche con strumenti per la visualizzazione dei risultati;
• sarà in grado di applicare le tecniche viste a problemi nuovi, modificando gli algoritmi e/o i loro parametri.
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
Il corso è organizzato in lezioni frontali ed esercitazioni pratiche. Le lezioni frontali prevedono anche esempi di organizzazioni dei dati e simulazioni di applicazioni di algoritmi. Le esercitazioni pratiche utilizzeranno il software WeKA e altri software open-source, per mostrare l’applicazione di algoritmi su insiemi di dati campione
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
I metodi previsti di accertamento delle conoscenze e competenze acquisite sono:
• per i contenuti istituzionali del corso è previsto un esame scritto ed un esame orale. L’esame scritto prevede esercizi e domande sulle strutture dati e gli algoritmi presentati durante le lezioni: il superamento dell’esame scritto è condizione necessaria per accedere alla prova orale. L’esame orale prevede una interrogazione sugli argomenti in programma. Saranno valutati il rigore e la chiarezza dell’esposizione, la capacità di inquadrare i vari argomenti nei rispettivi contesti e di collegarli tra loro. La media aritmetica dei voti tra la prova scritta e la prova orale inciderà dell’80% sulla votazione finale;
• per i contenuti applicativi del corso deve essere realizzato un progetto (da svolgere in piccoli gruppi, massimo tre/quattro 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 o strumenti open source di data mining. Il gruppo presenterà il progetto e saranno valutati la scelta degli strumenti teorici più coerenti tra quelli proposti nel corso, il rigore nell'applicazione dei metodi scelti, la capacità di argomentare, spiegare e difendere i risultati raggiunti e confrontare i vari punti di vista. La valutazione del progetto e della sua presentazione inciderà del 20% sulla votazione finale.
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; introduzione sulla classificazione tramite Naive Bayes e ANN. Applicazione alla categorizzazione di testi. 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.