Introduzione 2
Il contesto di ricerca
Spesso, infatti, le informazioni che cerchiamo sono “nascoste” in grossi volumi di
dati che sono di per se poco significativi. Per ottenere questa informazione è quindi
necessaria una chiave di lettura ad hoc.
Per questo motivo, la ricerca si è spinta negli ultimi anni verso un settore
dell’informatica ed in particolare dei sistemi per la gestione dei dati conosciuto con
l’acronimo di KDD (Knowledge Discovery in Databases). Mentre gli attuali
DBMS si occupano di memorizzare ed organizzare i dati di interesse della
corporazione, il KDD si propone di mettere a disposizione dell’analista gli strumenti
per analizzare, capire e visualizzare la conoscenza contenuta in tali dati.
Una definizione piuttosto imprecisa del KDD che è stata trovata nel repository
informativo più provvisto ed allo stesso tempo confuso, internet, è la seguente:
<Il KDD è un metodo per “torturare” i dati finché questi non confessano>.
Anche se la definizione data è poco tecnica, rende almeno parzialmente l’idea
del target annunciato da questo settore di ricerca. Il KDD può pertanto essere visto
come la naturale evoluzione delle tecnologie che trattano l’informazione.
Nella letteratura, con il termine KDD si denota un processo di estrazione di
conoscenza utile ad alto livello con lo scopo di soddisfare le esigenze dell’utente
che può utilizzare le informazioni estratte all’interno di un DSS. Il termine processo
va inteso come una serie di stadi sequenziali ed interattivi; il passo principale è
comunemente noto come Data Mining (DM) e si occupa dello sviluppo di modelli
predittivi sui dati per evidenziarne regolarità e similitudini.
Introduzione
3
L’idea …
Uno dei progetti più caldi nell’ambito del Knowledge Discovery è la creazione di un
ambiente in cui sia possibile esprimere l’intero processo KDD. La ricerca ha infatti
prodotto un buon numero di tools ottimizzati per le varie fasi del processo, ma questi
sono rimasti isolati a causa dell’assenza di un frame-work generale di supporto
all’intero processo KDD. Soprattutto per quanto riguarda la fase di DM si avverte
poi la mancanza di un ambiente che permetta di combinare e condividere vari
modelli sui dati definiti a livelli di astrazione differenti.
Questa realtà può essere paragonata a quella dei primi anni ‘60, quando non
esisteva un insieme di primitive di supporto al trattamento dei dati che solo
successivamente sarebbero state fornite dal linguaggio SQL.
Allo stato attuale, numerosi ricercatori sono stati in grado di porre le basi per
trattare il KDD come processo di query e hanno dettato le condizioni che dovrebbe
soddisfare un query language (QL) in grado di supportarlo. In questo contesto, l’idea
è di realizzare un QL che permetta di combinare e condividere modelli differenti per
l’estrazione della conoscenza. Ogni modello di dati che rappresenta l’informazione
estratta non è vincolato quindi ad essere trattato separatamente, ma attraverso un
frame-work unico si consente di confrontare e manipolare informazione
appartenente a modelli di dati differenti.
Alla base di questo concetto, il linguaggio deve quindi fornire un principio di
chiusura simile a quello offerto dai databases relazionali, per mezzo del quale sia
possibile combinare, all’interno di una stessa query, operatori che utilizzano modelli
di dati differenti.
Introduzione 4
… e com’è stata realizzata
I punti di partenza per raggiungere l’implementazione del QL appena descritto sono
stati realizzati per mezzo di due lavori che sono stati sviluppati in altrettante tesi:
1. Un ambiente di supporto all’estrazione della conoscenza, KDDML, definito
e implementato in [Tesi1], interamente basato su XML, un meta-linguaggio
che consente di definire linguaggi di mark-up per la rappresentazione di
particolari classi di oggetti.
2. La formalizzazione del linguaggio che considereremo in questa tesi,
battezzato con l’acronimo MQL (Mining Query Language) [Tesi2], la cui
specifica ha avuto come punto di partenza il linguaggio KDDML.
Lo scopo di questa tesi è stato quello di trovare un punto di incontro tra KDDML
e MQL attraverso la costruzione di un modulo che opera da interfaccia fra i due
linguaggi.
Più precisamente, l’utente interagisce con l’ambiente utilizzando la specifica di
MQL, ma la base per la rappresentazione dei dati e l’esecuzione delle queries rimane
XML. L’ambiente finale utilizzerà quindi KDDML come una componente esterna
cui fornire queries nel formato richiesto dalla sua specifica e da cui attendere i
risultati prodotti. Il passaggio MQL Æ KDDML è stato ottenuto attraverso un
processo compilativo che ha comportato gli impegni più onerosi.
L’obiettivo prefissato è stato raggiunto ponendo una netta distinzione tra la fase
di progettazione del sistema che supporta MQL e la fase implementativa vera e
propria attuata attraverso il linguaggio di programmazione Java. La separazione
della progettazione e della scrittura del codice ha infatti rappresentato uno dei più
significativi progressi nella programmazione negli ultimi dieci anni, e i linguaggi
orientati agli oggetti come Java implementano tale forma di separazione.
Ci occuperemo della fase di definizione del sistema nei capitoli 2 e 3, mentre
l’implementazione sarà interamente oggetto del capitolo 4.
Introduzione
5
Organizzazione della tesi
I capitoli che seguono sono organizzati nel seguente modo:
ξ Capitolo 1. Viene presentata una panoramica sullo stato dell’arte. In
particolare, viene trattato il processo KDD, i suoi obiettivi, le aree
applicative, soffermandoci, per quanto riguarda la fase di Data Mining, sui
modelli utilizzati nell’ambito del sistema realizzato (regole di associazione,
clustering e classificazione). Infine, viene mostrata una breve rassegna dei
principali ambienti di supporto al processo KDD che sono attualmente
disponibili nell’ambito della ricerca.
ξ Capitolo 2. In questo capitolo, dopo aver descritto gli strumenti a nostra
disposizione che ci hanno consentito di raggiungere il traguardo richiesto,
viene presentata la fase di progettazione e definizione del sistema
complessivo, per il quale verrà fornita una descrizione con un alto livello di
astrazione e privata di ogni dettaglio implementativo. In particolare, il
capitolo è strutturato nel seguente modo:
i) Vengono illustrate le funzionalità del sistema KDDML e del suo
linguaggio di definizione XML (paragrafo 2.1).
ii) Si introduce il query language MQL. Ci soffermeremo in particolare sul
confronto tra i linguaggi KDDML e MQL (paragrafo 2.2).
iii) Viene disegnata l’architettura complessiva del sistema ottenuta durante la
fase di progettazione (paragrafo 2.3).
ξ Capitolo 3. Viene proseguita la fase di definizione del sistema con una
descrizione più dettagliata del modulo che si occupa della traduzione delle
queries MQL in queries XML nel formato richiesto da KDDML.
Introduzione 6
ξ Capitolo 4. Si occupa della realizzazione dell’ambiente definito e presentato
nei due capitoli precedenti. L’implementazione è stata realizzata interamente
in Java. La fase implementativa è stata suddivisa in sottofasi successive che
verranno descritte singolarmente.
ξ Capitolo 5. Viene presentato un esempio completo di estrazione della
conoscenza che ha il duplice obiettivo di mostrare tutte le funzionalità offerte
dal sistema per quanto riguarda l’interazione con l’utilizzatore (Graphics
User Interface) e di illustrarne il suo funzionamento dal punto di vista del
codice implementato.
Capitolo 1 – Stato dell’arte: KDD
7
Capitolo 1
Stato dell’arte: Knowledge Discovery in
Databases
Negli ultimi vent’anni la disponibilità di dati ed informazioni digitali è cresciuta
vertiginosamente grazie alla progressiva ed inesorabile diffusione dei computer ed al
drastico abbassamento del rapporto prezzo/capacità dei supporti di memorizzazione
unito ad un aumento della potenza di calcolo dei moderni processori.
Per citare qualche esempio, l’osservatorio terrestre della NASA ha stimato di
dover raccogliere ed elaborare dati provenienti dai suoi sistemi radar di decine di
gigabytes ogni ora [WS91]; il più grande database del mondo, Wall-Mart, a sua
volta, gestisce oltre 20 milioni di transazioni al giorno [B94].
Ma raccogliere ed organizzare i dati non è sufficiente; i dati devono anche essere
analizzati, compresi e trasformati in informazione utile. La situazione attuale viene
riassunta da J. Han e M. Kamber [HK00] con questa frase:
“Siamo ricchi di dati ma poveri di informazione”
che mette in evidenza la necessità di disporre di una visione dei dati più astratta e
sintetica possibile, in modo che questi possano essere compresi dall’uomo che può
quindi utilizzarli come supporto alle decisioni (DSS).
Capitolo 1 – Stato dell’arte: KDD 8
Le informazioni utili, infatti, sono spesso nascoste in grossi volumi di dati, di per
se poco significativi o incompleti. Per raggiungere l’informazione desiderata è
quindi necessario correggere, ripulire e soprattutto analizzare questi dati.
Questa realtà può essere paragonata all’attuale mondo del web: l’enorme mole di
dati in esso contenuti sarebbe un vero e proprio “pantano” senza l’ausilio di
strumenti che ci guidano verso l’informazione cercata. La ricerca si è quindi spinta
verso lo studio di sistemi per il trattamento dei dati che giocano lo stesso ruolo dei
motori di ricerca per internet.
I sistemi classici di memorizzazione dei dati, i DBMS (Data Base
Management System), offrono un’ottima possibilità per memorizzare ed accedere
ai dati con sicurezza, efficienza e velocità, ma tuttavia non permettono un’analisi per
l’estrazione di informazioni utili da impiegare per il DSS. Solo negli ultimi anni
sono apparse tecnologie in grado di svolgere questo compito, grazie al contributo di
diverse discipline tra cui intelligenza artificiale, reti neurali, statistica, e
apprendimento automatico. Queste tecnologie, applicate alle basi di dati, sono
conosciute con i seguenti termini: knowledge discovery, knowledge extraction, data
archaeology, data dredging, data mining. Questi termini descrivono, almeno in parte,
il concetto di knowledge discovery in databases (KDD) inteso come un processo
per l’estrazione di informazioni, o meglio di conoscenze, da grosse quantità di dati.
Il KDD è un processo costituito da una serie di stadi interattivi che manipolano e
trasformano i dati per riuscire ad estrarre informazione utile. Il Data Mining (DM) è
il passo principale del processo KDD che si occupa della scoperta automatica di
patterns e dello sviluppo di modelli predittivi. Alcuni ricercatori usano i termini
KDD e data mining come sinonimi; in queste pagine, invece, si farà riferimento ad
un modello di KDD che identifica gli elementi necessari e sufficienti per supportare
le operazioni richieste per un processo di acquisizione delle conoscenze, e si
considererà il data mining come l’insieme delle tecniche, dei tools e degli algoritmi
utilizzati per la presentazione e l’analisi dei dati.
Precisa è la distinzione tra un DBMS e un sistema che supporta il processo KDD
(KDDMS – KDD Management System). Ad esempio, con riferimento al settore
del marketing (nel quale il DM ha un forte impatto), mentre un linguaggio per
DBMS (come ad esempio SQL) cerca di risolvere problemi del tipo:
1.1 – Settori applicativi del KDD
9
“trasferisci il prodotto X dal magazzino 1 al magazzino 2”
“inserisci un ordine nel database, aggiornando lo stato dell’ordine nel tempo”
“trova il nome di tutti i clienti che hanno acquistato il prodotto X in data Y”
il DM cerca di rispondere a domande del tipo:
“Come sono incrementate le vendite dei prodotti alcolici nel Canada rispetto alle
vendite negli USA nel 1998?”
“Con quale probabilità due prodotti vengono acquistati congiuntamente e da quali
tipi di clienti?”
“Quali sono i fattori che influenzano un cliente e come ottenere nuove offerte?”
“Qual è il prossimo prodotto che il cliente vorrà acquistare?”
Questi esempi, mettono in evidenza la differenza tra una transazione basata sui
database tradizionali (OLTP: On Line Transaction Processing) da una basata sul
supporto alle decisioni (OLAP: On Line Analytic Processing): il disegno del
database è ora orientato al soggetto e non più all’applicazione; le query sono spesso
più complesse rispetto ad una transazione OLTP e l’accesso è ottimizzato per il tipo
di informazione che si desidera ottenere; l’informazione richiesta è spesso frutto di
stime e predizioni e le dimensioni dei database sono dell’ordine dei 100GB-TB
contro i 100MB-GB dei DBMS tradizionali.
Capitolo 1 – Stato dell’arte: KDD 10
1.1 Settori applicativi del KDD
La ragione principale per cui il KDD ha attratto una grande parte dell’attenzione
nell’industria dell’informazione nei recenti anni è dovuta alla disponibilità di grosse
quantità di dati e all’imminente bisogno di trasformare questi dati in conoscenza
utile. Il KDD può essere dunque visto come la naturale evoluzione delle tecnologie
che trattano l’informazione.
C'è infatti molto entusiasmo che ruota attorno al data mining ed in generale al
processo di knowledge discovery e molti sono i settori dove queste tecniche sono
state utilizzate. Questi settori, o domini applicativi, spaziano dalla gestione degli
investimenti di una finanziaria all’astronomia, dal rilevamento di possibili mal
funzionamenti in un sistema alla classificazione di oggetti presenti in un ambiente da
parte di un robot. L'importanza del data mining è particolarmente riconosciuta in
settori quali assicurazioni (per lo studio del comportamento dei clienti), sanità (per
la diagnosi e il monitoraggio dei pazienti), sistemi di telecomunicazioni, banche,
vendita al dettaglio e marketing, finanza (supporto agli investimenti), ingegneria
(simulazione ed analisi). Di seguito riportiamo alcuni esempi di utilizzo del DM.
Una tipica applicazione che si ha nel settore del marketing è quella utilizzata per
scoprire i comportamenti dei clienti. L’obiettivo richiesto è trovare “modelli” di
consumatori che sono suddivisi in classi comuni (ad esempio per interesse o livello
di guadagni) per identificare così il miglior prodotto associato a clienti diversi
oppure per individuare le associazioni tra prodotti acquistati in un supermercato
(market basket analisi) al fine di pianificare campagne promozionali.
Un altro importante esempio di applicazione si ha nel settore assicurativo per la
costruzione di modelli di comportamento fraudolenti (fraud detection) atti ad
individuare inganni ed imbrogli da parte dei clienti.
Nel settore bancario l’uso delle tecniche di data mining può risultare utile per
molti scopi. In quest’area si può scoprire, mediante il data mining, l’uso di carte di
credito false, identificare i clienti fedeli, effettuare controlli sui prestiti concessi ai
clienti o prevedere quelli che probabilmente cambieranno la loro affiliazione ad una
carta di credito. E’ possibile, inoltre, determinare che tipo di uso della carta di
1.1 – Settori applicativi del KDD
11
credito è stato fatto da gruppi di clienti o cercare delle correlazioni nascoste tra
differenti indicatori finanziari.
Negli ultimi anni, la vertiginosa espansione di internet ha generato nuovi domini
applicativi per il data mining. Il commercio elettronico e le altre attività ad esso
correlate stanno creando, e continueranno a creare, enormi quantità di dati
utilizzabili per scopi commerciali e sociali. Alcune applicazioni di text-mining, ad
esempio, analizzano pagine di testo da siti web a carattere finanziario per prevedere
gli andamenti dei titoli in borsa. L’utilizzo del DM applicato al mondo di Internet
non si ferma al text-mining, ma coinvolge anche la ricerca di strumenti per rendere i
motori di ricerca più efficienti e veloci o per la scoperta di nuovi algoritmi di proxy
catching intelligente (Web Mining).
Anche l’area dei dati rilevati in maniera remota rappresenta un’altra possibile
applicazione del data mining essendo la più vasta sorgente di dati disponibile. Una
gran parte di questi dati deriva dalle immagini satellitari; altri dati provengono da
rilevamenti effettuati sulla terra e sul mare o dai radar. Il loro impiego è nato
dall’esigenza di monitorare e capire le principali cause di inquinamento del nostro
pianeta. Nel campo satellitare, le reti neurali sono correntemente utilizzate come
strumento di riconoscimento e di ricostruzione di immagini.
Addirittura il mondo dello sport può essere interessato all’applicazione di
tecniche di DM. In [IEEE96] viene presentato un esempio di sistema KDD
sviluppato per l’NBA (National Basketball Association) che è stato utilizzato da ben
14 delle 29 squadre della lega americana. Il sistema memorizza informazioni
statistiche sui dati degli eventi di ogni singolo incontro (passaggi, tiri liberi, falli
commessi, ecc) che vengono inseriti durante il gioco. Usando il sistema, gli
allenatori possono, in tempo reale, porre quesiti al sistema per trovare risposte che li
guidino verso una strategia vincente.
Capitolo 1 – Stato dell’arte: KDD 12
1.1.1 Argomenti correlati
Per definizione il KDD è un campo interdisciplinare che riunisce ricercatori ed
esperti da una grande varietà di campi. I maggiori campi correlati includono
statistica, apprendimento automatico, intelligenza artificiale (AI), ragionamento
probabilistico, pattern recognition e naturalmente sistemi per la gestione delle
informazioni (DBMS) da cui il KDD deriva. Ogni settore elencato gioca un ruolo
importante nel DM e in generale nell’intero processo KDD.
Ad esempio, il campo della statistica [EP96] offre metodi per effettuare la pulizia
di dati, necessaria prima della fase di DM, per individuare eccezioni o dati affetti da
errori oppure per stimare valori mancanti.
L’intelligenza artificiale e l’apprendimento automatico forniscono invece validi
algoritmi applicabili al clustering e alla classificazione.
1.1 – Settori applicativi del KDD
13
1.2 Il processo KDD
Il processo di acquisizione di conoscenze da dati può essere scomposto in 4 passi
che sono mostrati in figura 1.1.
Come si può osservare, adottiamo la convenzione che il Data Mining si riferisca
all’estrazione di patterns o modelli dai dati e, costituisca quindi solo un passo del
processo KDD. Non ci si preoccupi per il momento dei concetti di pattern o
modello; questi concetti saranno concretizzati nel paragrafo 1.3 quando tratteremo in
dettaglio la fase di DM. Basti sapere, al momento, che un modello denota una
qualche rappresentazione astratta di un sottoinsieme di dati.
Figura 1.1 – Il processo KDD
Il processo è interattivo in quanto necessita di un intervento umano su alcune
decisioni, soprattutto sulla fase di DM durante la scelta del modello di dati da
utilizzare e dell’algoritmo specifico.
Consolidamento
dei dati
Selezione e
preprocessing
Data Mining
Interpretazione
e valutazione
Sorgenti Dati
Dati
consolidati
Dati
preparati
Patterns e
modelli
warehouse
Conoscenza
Capitolo 1 – Stato dell’arte: KDD 14
Come si può osservare, il processo KDD riceve come input dei dati grezzi
provenienti da sorgenti diverse e produce come output informazioni utili, impiegate
nel DSS, che sono acquisite come il risultato dei passi che andiamo di seguito a
descrivere.
1.2.1 Consolidamento dei dati
L’obiettivo è di prelevare i dati da sorgenti eterogenee (DB relazionali, DB
deduttive, files di testo, ecc) per costruire una visione uniforme degli stessi a
prescindere da quale tipo di sorgente siano stati prelevati. Il risultato di questo passo
è la creazione di un database, detto data warehouse, utilizzato per il supporto alle
decisioni e mantenuto separato rispetto al database operazionale dell’organizzazione
che è invece utilizzato per le normali operazioni di transaction processing.
Tra le caratteristiche che deve avere un data warehouse per garantire alte
performances spiccano le seguenti [HK00]:
ξ Orientato al soggetto: ossia alle aree di principale interesse della
corporazione per modellare il dominio di analisi.
ξ Integrato: le inconsistenze introdotte nella codifica e rappresentazione da
sorgenti diverse devono essere eliminate nel data warehouse.
ξ Time variant: - I dati contenuti nei databases che vengono analizzati possono
essere variabili nel tempo. Se si pensa ad esempio ad un database che
contiene tutti gli scontrini fiscali di un grosso centro commerciale, si può
ipotizzare che i dati in esso contenuti varino quasi continuamente durante
l’orario di apertura. Quindi, nell’analizzare tali tipi di dati, è necessario
“fotografare” il database in un certo istante ed utilizzare tale “foto” per
compiere le analisi tramite un sistema KDD. La struttura di un data
warehouse deve quindi contenere sempre la dimensione temporale.
ξ Non volatile: a causa della separazione con il database operativo, è
importante che il data warehouse non richieda frequenti aggiornamenti.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
