Ministero dell'Universita' e della Ricerca Scientifica e Tecnologica
Dipartimento Affari Economici

RELAZIONE ANNUALE



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