INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
6
PREFAZIONE
L’interpretazione delle mappe topografiche è uno dei principali contesti applicativi
per GIS (Sistemi Informativi Geografici). Sfortunatamente ad ora la maggior parte dei
GIS in commercio appare inefficace in molteplici contesti applicativi a causa della
complessità dei processi spaziali e della necessità di processare voluminosa
conoscenza del dominio che solo gli esperti del settore possono avere. La ricerca
nell’ambito del data mining spaziale ha portato negli ultimi anni alla realizzazione di
prototipi che consentono di estendere la conoscenza di dominio e la capacità di
ragionamento, ma incappando in molte limitazioni, quali le definizioni di alcuni
concetti ambientali, sono difficili da inserire in interrogazioni verso database, le
definizioni di alcuni oggetti geografici dipendono dal modello dei dati utilizzato
(relazioni come la densità sono possibili con un modello di tipo raster mentre
l’orientamento di elementi morfologici con modelli topologici), il riconoscimento di
elementi geografici nelle mappe richiederebbe tutta la conoscenza del dominio
dell’applicazione impensabile per grandi progetti riguardanti questo settore.
INGENS (INductive GEographic Information System) è un prototipo di GIS che
mette a disposizione degli utenti strumenti di data mining al fine di supportare
l’interpretazione automatica di mappe topografiche. L’integrazione tra le varie
tecnologie, tra le quali anche database spaziali, è facilitata dall’utilizzo di un
particolare spatial data mining language: SDMOQL (Spatial Data Mining Object
Query Language). Questo linguaggio prevede delle primitive che permettono agli
utenti di specificare solo le informazioni a cui egli è interessato, la tipologia di
conoscenza da scoprire, le informazioni sul dominio (background knowledge) utile al
processo di scoperta, le misure interessanti nella elaborazione delle informazioni e
come visualizzare i risultati.
INGENS offre la possibilità di scegliere tra due tipologie di task: scoperta di
regole di associazione e regole di classificazione spaziali. Una regola di associazione
spaziale descrive associazioni frequenti tra proprietà di oggetti spaziali che
interagiscono (spazialmente) tra loro. Ad esempio, la regola «l'80% delle grosse città
canadesi sono confinanti con gli USA» è una regola di associazione spaziale. Un
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
7
processo di classificazione spaziale assegna un insieme di oggetti spaziali ad una
precisa classe, fra quelle fissate, utilizzando un insieme di caratteristiche spaziali e
non. Un esempio di regola di classificazione spaziale è: «se un ipermercato è
collocato nei pressi di un cinema ed è facilmente accessibile da una strada statale,
allora i suoi profitti sono alti».
Scopo della tesi è l’estensione del linguaggio di interrogazione al fine di
supportare query deduttive per regole di associazione.
Nel primo capitolo si presenta una panoramica sui linguaggi di interrogazione di
Data Mining. Verrano quindi illustrati alcuni dei linguaggi più studiati nel campo di
Knowledge Discovery on Databases.
Nel secondo capitolo si descrive il linguaggio SDMOQL (Spatial Data Mining
Object Query Language), un linguaggio che supporta i due task di data mining:
induzione di regole di classificazione e scoperta di regole di associazione.
Nel terzo capitolo si presenta l’estensione del linguaggio SDMOQL al fine di
potere formulare query deduttive per regole di associazione. Viene specificato
l’estensione in dettaglio, le produzioni aggiunte per poter supportare tali query.
Vengono inoltre presentate le modifiche al QueryInterpreter per poter supportare tali
query, le modifiche ai singoli elementi del QueryInterpreter. Si spiega l’uso di ATRE
nell esecuzione delle interrogazioni e poi viene presentato anche il Progetto delle
Modifiche con i relativi illustrato da schemi UML.
Nel quarto capitolo, invece, vengono spiegate le diverse forme delle query
deduttive con regole di associazione. Viene spiegato la loro esecuzione prendendo
sotto esame tutti i passi necessari.
Infine in appendice, si presenta uno degli strumenti utilizzati per la tesi, SableCC.
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
8
I LINGUAGGI DI INTERROGAZIONE DI DATA MINING
I.1 I DATA BASE MANAGEMENT SYSTEMS
I Data Base Management Systems (DBMS) e le loro tecnologie abilitate sono
evolute al scopo di affrontare con successo la maggior parte dei dati ad alta intensità,
appartenenti a diversi campi di applicazioni, che sono emerse nel corso degli ultimi
venti anni. Ad esempio, in risposta a la crescente importanza delle applicazioni di
supporto decisionale, i DBMS relazionali e SQL sono stati rapidamente estesi per
supportare le query OLAP da punti di vista sia tecnico che commerciale.
Un altro aspetto molto importante dei DBMS è la ricerca di conoscenza
(Knowledge Discovery in Databases) la quale è basata sui processi “From Data to
Knowledge”. Tali processi, per via della crescita della quantità dei dati, è
umanamente impossibile gestirli. Per questo motivo è in aumento la richiesta di
sistemi Software per gestire i processi di ricerca di conoscenza.
Dal momento della prima definizione di Knowledge Discovery in Databases
(KDD) (Piatetsky-Shapiro e Frawley, 1991), sono state proposte molte tecniche al
fine di sostenere questi processi complessi e iterativi di scoperta della conoscenza.
In pratica, la deduzione della conoscenza si basa sulla estrazione di insiemi di
“modelli di dati”, le quali possono essere globali (ad esempio, alberi di decisione)
oppure locali (esempio, regole di associazione). Alla ricerca di una maggiore
integrazione tra i dati e i “modelli di dati”, Imielinski e Mannila hanno proposto in
(Imielinski e Mannila, 1996) il concetto di database induttivi (IDB). In un IDB, le query
ordinarie possono essere utilizzate per accedere e manipolare i dati, mentre le query
induttive possono essere usate per generare , manipolare, e applicare modelli. KDD
diventa un ampio processo di interrogazione in cui l'analista può controllare l'intero
processo specificando i modelli e l’insieme di dati di interesse.
Per via del motivo che il KDD si sta applicando in diversi campi della scienza
si nota anche un aumento di richiesta per linguaggi di interrogazione di Data Mining.
Lo sviluppo di linguaggi di interrogazione si sta evolvendo sia in ambito generale,
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
9
facendo nascere linguaggi di interrogazione complessi e adatti a diverse tipologie di
compiti di Data Mining (DMQL), ma anche in ambito più specifico creando cosi dei
linguaggi adatti a dei compiti ben specifici, come la scoperta di sole regole di
associazione (MSQL) ,etc.
I.2 LINGUAGGI DI INTERROGAZIONE DI DATA MINING:
STATO DELL’ARTE
Un linguaggio di interrogazione di Data Mining, dovrebbe fornire le necessarie
primitive da poter:
(1) selezionare i dati che devono essere estratti e di eseguire il pre-trattamento
di questi dati,
(2) specificare il tipo di modelli che viene estratto,
(3) specificare il background necessario di conoscenza (come elementi di
gerarchie)
(4) definire i vincoli sui modelli desiderati
(5) post-processare i modelli estratti
Inoltre, è importante che il linguaggio di interrogazione di data mining soddisfi le
proprietà di chiusura, vale a dire, il fatto che il risultato di una interrogazione può
essere interrogato come una nuova interrogazione. Seguendo un approccio classico
nella teoria dei database, è anche necessario che il linguaggio sia basato in una ben
definita (operazionale o ancora meglio dichiarativa) semantica. Esso è l'unico modo
per rendere il linguaggio di interrogazione adatto per poter progettare strategie per
l'ottimizzazione delle interrogazioni (query).
Cercheremo di spiegare in modo più specifico il concetto di linguaggio di
interrogazione di Data Mining prendendo in considerazione alcuni di loro. Più in
dettaglio spiegheremo SDMOQL un linguaggio basato su OQL (Object Query
Language), il quale è stato progettato per formulare query di Spatial Data Mining,
cioè estrarre conoscenza da dati spaziali.
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
10
I.2.1 DMQL
DMQL, è stato progettato per formulare interrogazioni (query) al scopo di scoprire
diversi tipi di conoscenza nei database relazionali. Consiste nella specifica delle 4
primitive più importanti nei compiti di Data Mining.
(1) l’insieme di dati rilevanti ad un processo di data mining,
(2) il tipo di conoscenza da scoprire,
(3) la conoscenza di base (background knowledge)
(4) parametri di interesse per la scoperta di conoscenza (ad esemp., soglie).
La prima primitiva, l’insieme di dati rilevanti, può essere specificato in un modo
simile a quello di una interrogazione (query) relazionale, che viene utilizzata per
recuperare insiemi di dati dal database.
La seconda primitiva, il tipo di conoscenza da scoprire, può comprendere relazioni
generalizzate, regole caratteristiche, regole discriminanti, regole di classificazione,
regole di associazione, ecc, che sono dettagliate come segue.
1. Una relazione generale è una relazione ottenuta generalizzando da un ampio
insieme di dati a basso livello. Una relazione generale può quindi essere
utilizzata per l'estrazione di tipi di differenti di regole.
2. Una regola caratteristica è un affermazione che caratterizza un concetto che
soddisfatto da parte di tutti o da la maggior parte degli esempi nella classe che
viene presa in esame (chiamato “target” della classe).
3. Una regola discriminante è un affermazione che mette in evidenza un
concetto della classe in esame (la classe di destinazione) da altre classi
(chiamate classi contrastanti). Ad esempio, per distinguere una malattia da un
altra, una regola discriminante dovrebbe riassumere i sintomi che distinguono
questa malattia da altre.
4. Una regola di classificazione è un insieme di regole che classifica l'insieme
dei dati rilevanti al interrogazione, che di solito è ottenuta classificando prima i
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
11
dati.
5. Una regola di associazione descrive rapporto di associazione fra un insieme
di dati.
La terza primitiva, la conoscenza di base (background knowledge), è una serie di
gerarchie concetto o operatori generali che forniscono la definizione di concetti di
livelli più alti, inoltre assiste il processo di generalizzazione.
La quarta primitiva, i parametri di interesse per la scoperta di conoscenza
possono essere specificati come un insieme di soglie o parametri di data mining a
seconda del tipo di regole che devono essere cercate.
DMQL adotta un sintassi SQL-like per facilitare gli alti livelli di data mining e
l’integrazione naturale con linguaggi di interrogazione relazionali, come SQL. Il
linguaggio DMQL è definito tramite una grammatica BNF estesa, dove [ ]
rappresenta 0 o al più una occorrenza, mentre { } rappresenta 0 o più occorrenze.
<DMQL>::=
use database <database _name>
{use hierarchy <hierarchy_name> for <attribute>}
<rule_spec>
related to <attr_or_agg_list>
from <relation(s)>
[where <condition>]
[order by <order_list>]
{with [<kinds_of>] threshold = <threshold_value>
[for <attribute(s)>]}
In <DMQL>, “use database <database_name>” indirriza l'attività di data mining a
un database specifico identificato da <database_name>, e l'istruzione opzionale,
“use hierarchy <hierarchy> for <attribute>”, assegna la gerarchia rapresentata con
<hierarchy> a un particolare attributo rappresentato da <attribute> (in caso contrario,
una gerarchia di default è utilizzata). La dichiarazione, <rule_spec>, specifica il tipo
di regole da scoprire. Per scoprire differenti tipi di regole, la specifica di regola
dovrebbe essere in formati differenti. Il “related to <att_or_agg_list>”, seleziona una
lista di attributi rilevanti e / o aggregazioni di generalizzazione. Le clausole “from” e
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
12
“where”, formano una query SQL per poter raccogliere l'insieme dei dati pertinenti. La
clausola “order by” specifica semplicemente l'ordine delle righe da stampare. Infine
l’istruzione “with-threshold” soglie diverse necessarie per l’esecuzione della query.
Abbiamo spiegato in modo generale la sintassi del linguaggio DMQL, perche la
maggior parte dei linguaggio di interrogazione di Data Mining è un estensione di tale
linguaggio.
I.2.2 ODMQL
Il linguaggio ODMQL (Object Data Mining Query Language) permette all'utente
(Data Miner) di scrivere query di data mining e specificare ogni primitiva in una
sintassi di OQL. Il principale utilizzo è per la scoperta di conoscenza da database
orientati agli oggetti. Il processore ODMQL include un parser che analizza le
istruzioni, un gestore di gerarchia che manipola i concetti di gerarchia, e tecniche di
data mining per la ricerca di diverse tipologie di regole. Il processore utilizza la
sintassi OQL per recuperare il set di oggetti utili che parteciperanno alla estrazione di
dati.
Sotto venogno discusse le principali caratteristiche del linguaggio ODMQL:
1. Tipi di Regole: L’ODMQL supporta la specificazione del tipo di regole che
devono essere estratte nella query corrente. La formulazione della query
includere il nome di questo tipo di regola che vogliamo scoprire e di altre
specifiche a seconda delle necessità del compito di data mining. Per esempio,
l'estrazione di regole discriminanti deve specificare le due classi contrastanti.
2. Dati Rilevanti: L'insieme dei dati rilevanti è specificato nel ODMQL come viene
specificato anche in OQL, tramite la sostituzione. La parola "select" viene
sostituita con "with relevance to".
3. Parametri: L’ODMQL supporta la specificazione delle soglie precedentemente
discusse. E’ da notare che ogni attributo potrebbe avere una diversa soglia.
Citare solo un attributo soglia significa che questa soglia viene applicato per
tutti gli attributi.
4. Gerarchia di Concetti: Il ODMQL consente all'utente di specificare le gerarchie
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
13
di concetto per gli attributi della schema. La specifica comprende sia la
definizione di una nuova gerarchia, o la modifica di una già predefinita.
I.2.3 STDMQL
I dispositivi mobili stanno diventando molto popolari negli ultimi anni, e grandi
quantità di dati in forma traiettoria di spostamento sono generati da questi dispositivi.
Traiettorie lasciate dietro da automobili, da esseri umani, da uccelli o altri oggetti
sono un nuovo tipo di dati che possono essere molto utili nel processo decisionale in
domini di applicazioni diversi. Questi dati, tuttavia, sono normalmente disponibili
come punti di campionamento, e quindi hanno poche o nessuna semantica. L'analisi
e l'estrazione di conoscenza dal campionamento di traiettorie è molto di difficile dal
punto di vista dell'utente, e vi è un bisogno emergente di nuovi modelli di dati,
tecniche di manipolazione, e di strumenti per estrarre modelli significativi da questi
dati.
Per le necessità esprese precedentemente è nato il linguaggio : STDMQL (Spatio-
Temporal Data Mining Query Language). Il linguaggio fornisce degli operatori di pre-
elaborazione dei dati per poter integrare facilmente le traiettorie con le informazioni
geografiche, al fine di generare traiettorie semantiche. Questi dati possono poi
essere estratti e gli schemi estratti vengono memorizzati per essere interrogate e
selezionate nei passi di post-processing.
I compiti di data mining supportati da STDMQL sono modelli frequenti di traiettorie,
regole di associazione, e modelli sequenziali. Questi compiti di data mining
genereranno i seguenti modelli di traiettorie: soste frequenti e spostamenti frequenti;
soste sequenziali e spostamenti sequenziali e inoltre anche soste in modo associato
e spostamenti associati a un differente evento.
Noi definiamo le operazioni di scoperta di modelli di dati, in modo generale, in
modo che una o più degli algoritmi proposti nell campo di Data Mining possono
essere implementati per svolgere questi compiti di data mining. In altre parole, le
operazioni non sono limitate ad un algoritmo specifico, e pertanto, possono essere
forniti parametri di input differenti.
Una grammatica espressa in BNF, per precisare i compiti di data mining, è data
come segue:
INGENS : UNA ESTENSIONE DEL LINGUAGGIO DI INTERROGAZIONE AL FINE DI FORMULARE QUERY DEDUTTIVE
PER REGOLE DI ASSOCIAZIONE
14
<mining_function> ::= <pattern_type> <left_par> <mining_parameters>
<right_par>
<pattern_type> ::= FREQUENTSTOPS | FREQUENTMOVES |
ASSOCIATESTOPS | ASSOCIATEMOVES |
SEQUENTIALSTOPS | SEQUENTIALMOVES
<left_par> ::= (
<mining_parameters> ::= <item> [<coma> <timeG>] <coma> <stopG> <coma>
<minSup>
[{<coma> <other_parameter>}...]
<coma> ::= ,
<item> ::= ITEM <equal> <item_def>
<item_def> ::= NAME | NAMESTART | NAMEEND | NAMESTARTEND
<minSup> ::= MINSUP <equal> real
<other_parameter> ::= <parameter_name> <equal> <parameter_value>
<parameter_name> ::= string
<parameter_value> ::= string | real | integer
<right_par> ::= )
Per le tre funzioni di data mining sono necessari due parametri fondamentali :
<item> e <minSup>. Il parametro <item> è l'attributo che sara preso in
considerazione nella fase di data mining, ad esempio, può essere un elemento che
comporra il modello. Noi chiamerremo questa voce “attributo”, perché questo termine
è ben noto nella letteratura di data mining. Nel contesto delle traiettorie, un attributo
rappresenta un insieme di informazioni. Al contrario di data mining transazionali,
dove un attributo è un singolo elemento, un attributo di traiettoria contiene
informazioni sullo spazio e il tempo.
I.2.4 SDMOQL
SDMOQL è un linguaggio creato per eseguire compiti di data mining spaziale
(come classificazione e scoperta di regole di associazione) in INGENS.