3.Rendiconto scientifico delle attivitą presso le sedi partecipanti

Unità di       Politecnico di TORINO

Responsabile ELENA BARALIS

Quota Cofinanziamento Murst  34.920.000

Quota Cofinanziamento Ateneo  40.000.000 (RD+RA certificata)

Fondi complessivi utilizzati il primo anno  22.625.552

Illustrazione dell'attivita' svolta

L'unita' del Politecnico di Torino e' coinvolta nel tema 4 (Analisi delle informazioni estratte dal WWW). I risultati ottenuti nel primo anno sono quelli previsti nella proposta e sono descritti nei rapporti T4-R04, T4-R05 e T4-R10. Il tema 4 e' dedicato all'elaborazione dei dati estratti dal Web sia per individuare informazioni rilevanti per applicazioni specifiche, sia per fornire un supporto efficace alle decisioni da intraprendere. I dati estratti dal Web sono integrati all'interno di appositi magazzini di dati detti "data warehouse", contenenti collezioni integrate di dati di tipo storico-temporale, provenienti da sorgenti informative distribuite ed eterogenee. L'attivita` di ricerca del Politecnico di Torino e` volta alla definizione di linguaggi e algoritmi per l'analisi dei dati, facendo uso di tecniche di "data mining" e "knowledge discovery" per estrarre informazioni nascoste sotto forma di regolarita` ricorrenti. In particolare, obiettivo dell'attivita` di ricerca e` una trattazione di tipo generale del problema, che offra all'utente sia un linguaggio di alto livello per esprimere le caratteristiche delle informazioni da estrarre, sia un insieme di strumenti efficaci e potenti per eseguire l'analisi, che siano mirati alle caratteristiche dei dati da analizzare. Il primo passo dell'attivita` di ricerca e` stato lo studio delle proposte presenti in letteratura. Sono state esaminate e classificate le diverse tipologie di metodi di estrazione di conoscenza e le proposte di linguaggi per l'estrazione di conoscenza da basi di dati. Questa attivita` ha evidenziato che la ricerca nel campo del data mining e` stata focalizzata prevalentemente sulla definizione di algoritmi efficienti per la risoluzione di problemi specifici, quali la classificazione di dati in gruppi disgiunti, la scoperta di associazioni, schemi ripetuti e similarita` in sequenze di dati ordinate. Poca attenzione e` stata invece dedicata alla definizione di linguaggi di alto livello che permettano di specificare in modo astratto le caratteristiche dell'operazione di analisi dei dati da eseguire. Il risultato dell'attivita` di studio e` stato il rapporto tecnico T4R05 "Techniques for Knowledge Extraction and Representation", a cura di E. Baralis, R. Meo e G. Psaila, che descrive le diverse tipologie di metodi di estrazione di conoscenza. In parallelo, sempre durante la prima fase, in collaborazione con le unita` di Bologna e di Roma 3, e` stato definito un modello logico per la descrizione della struttura dei dati estratti dal Web. Questo modello e` basato sulla definizione di schemi a stella (o star schema), caratteristici dei data warehouse. In questo tipo di modello, la tabella che occupa il centro stella, detta tabella dei fatti, contiene gli eventi oggetto dell'analisi (per esempio, vendite); le caratteristiche degli eventi memorizzati nella tabella dei fatti sono descritti nelle tabelle delle dimensioni, che rappresentano le punte della stella (per esempio, prodotti, tempo, ecc.). Il modello puo' essere ulteriormente esteso considerando gerarchie sulle dimensioni (per esempio, gerarchia merceologica dei prodotti) e costellazioni (insiemi di tabelle dei fatti che condividono le stesse dimensioni). Il modello a stella e' stato adottato come modello di riferimento per la definizione delle caratteristiche del linguaggio di specifica e degli algoritmi di estrazione di regole di associazione. Le caratteristiche del modello sono state descritte diffusamente nel rapporto T4R04 "Il modello logico dei dati per la rappresentazione dei dati estratti da WWW", a cura di E. Baralis, L. Cabibbo, R. Meo, G. Psaila, S. Rizzi, R. Torlone. Durante la seconda fase del progetto e` stata definita un'architettura di riferimento per l'analisi delle informazioni contenute nel data warehouse. In particolare, si e` deciso di circoscrivere l'ambito dell'analisi all'estrazione di regole di associazione, che descrivono collegamenti tra i dati che abbiano una sufficiente rilevanza dal punto di vista statistico. L'integrazione di tecniche di data mining con la tecnologia di data warehousing permette di migliorare sia le capacita` di analisi fornite dagli attuali prodotti per data warehousing, sia il potere espressivo e la flessibilita` degli strumenti per l'analisi dei dati. Infatti, i prodotti commeciali ROLAP (Relational OLAP) attuali forniscono sia i servizi efficienti di reperimento dell'informazione caratteristici dei DBMS server relazionali, sia tecniche specifiche di ottimizzazione di interrogazioni OLAP. Queste considerazioni hanno ispirato la definizione dell'architettura del prototipo AMORE-DW (Advanced Mining On Relational Environments - Data Warehousing). L'obiettivo principale e` lo sviluppo di uno strumento di data mining strettamente integrato con il data warehouse e il suo server ROLAP: i dati estratti dal Web e memorizzati nel data warehouse costituiscono le sorgenti informative analizzate e le regole estratte sono memorizzate sotto forma di relazioni nella base di dati relazionale. In questo contesto, la descrizione di una interrogazione di data mining e` eseguita mediante un linguaggio simile a SQL, che permette una specifica flessibile delle istruzioni di data mining ed estende la semantica di altri linguaggi proposti in letteratura. In particolare, il linguaggio di estrazione di regole di associazione proposto, benche' fornisca alcuni costrutti specifici per gli schemi a stella dei data warehouse, non e` legato ad alcuno schema di base di dati specifico; esso permette quindi di analizzare agevolmente informazioni nell'intero schema del data warehouse. Inoltre, il linguaggio permette di specificare criteri di estrazione complessi; in questo modo, aumentando progressivamente la complessita` dei criteri specificati, e` possibile raffinare progressivamente l'istruzione di estrazione delle regole di associazione, fino ad ottenere un risultato che raggiunga la precisione voluta. Infatti, l'operatore MINE RULE permette di specificare (a) espressioni relazionali per circoscrivere l'insieme dei dati da analizzare, (b) gli attributi su cui eseguire il raggruppamento, con eventuali condizioni di filtraggio sui gruppi, (c) gli attributi su cui eseguire un raggruppamento di tipo ulteriore, detto clustering, con eventuali condizioni di filtraggio e accoppiamento dei cluster (d) condizioni di mining, che vincolano il modo in cui sono costruite le coppie testa/corpo delle regole di associazione (e) attributi e cardinalita` delle regole di associazione (f) valori di supporto e confidenza minimi E` stata definita in seguito l'architettura del server di data mining, che esegue l'estrazione delle regole di associazione. Il mining server e` caratterizzato da un'architettura strettamente accoppiata al DBMS server relazionale sottostante, che fornisce servizi efficienti di memorizzazione e reperimento dei dati contenuti nel data warehouse. Un aspetto importante della definizione dell'architettura e` stato la delimitazione del confine tra le attivita` da eseguire all'interno dell'algoritmo di estrazione e quelle da affidare al server relazionale. In particolare, una soluzione estrema prevede di limitarsi a leggere i dati dal DBMS ed affidare tutte le elaborazioni agli algoritmi di estrazione; in questo caso, pero`, la complessita` dell'algoritmo di estrazione, che deve eseguire la valutazione di complessi predicati SQL, diverrebbe eccessiva. L'estremo opposto prevede di affidare al DBMS server tutte le attivita` di estrazione; in questo caso, il DBMS server si troverebbe a svolgere in modo inefficiente attivita` che richiedono strutture dati specializzate in memoria e algoritmi specializzati. E` stata prescelta una soluzione intermedia, che prevede di affidare al DBMS server tutte le attivita` di valutazione di predicati SQL complessi, mentre la fase di estrazione e` eseguita da algoritmi specificamente progettati per il costrutto MINE RULE. I dettagli del linguaggio di specifica dei criteri di estrazione di regole di associazione, la descrizione dell'architettura e degli algoritmi di estrazione sono contenuti nel rapporto T4R10 "The Architecture of the AMORE-DW Prototype", a cura di E. Baralis, R. Meo e G. Psaila. Durante il primo anno sono state svolte prevalentemente attivita` di ricerca di tipo analitico, che non hanno richiesto l'acquisizione di strumentazione di tipo particolare. I risultati ottenuti, oltre ad essere descritti nei rapporti tecnici elencati alla fine della presente relazione, hanno portato a 3 pubblicazioni su riviste internazionali e 5 pubblicazioni in atti di convegni internazionali con revisione. Prodotti (rapporti e prototipi) T4R05 "Techniques for Knowledge Extraction and Representation", E. Baralis, R. Meo e G. Psaila T4R04 "Il modello logico dei dati per la rappresentazione dei dati estratti da WWW", E. Baralis, L. Cabibbo, R. Meo, G. Psaila, S. Rizzi, R. Torlone T4R10 "The Architecture of the AMORE-DW Prototype", E. Baralis, R. Meo e G. Psaila

Schema riassuntivo dei fondi utilizzati (cifre spese o impegnate)
 

Voce di spesa	Cifra spesa o impegnata	Descrizione
Materiale inventariabile	0.000
Grandi Attrezzature	0.000
Materiale di consumo	1.012.172
Spese per calcolo ed elaborazione dati	1.813.560	Manutenzione
Personale a contratto	7.132.000
Servizi esterni	5.950.000
Missioni	6.717.820	Partecipazione a convegni e riunioni di progetto
Altro	0.000