Introduzione
2
6. Valutazione, i pattern estratti vengono valutati secondo determinate misure di
interesse;
7. Rappresentazione, la conoscenza estratta deve venire opportunamente
presentata all’utente, in modo chiaro e non ambiguo.
Un sistema di data mining cerca di calcolare una descrizione sintetica della classe che
fornisca un conciso sommario della collezione dei dati e li distingua dagli altri; questo
sommario è chiamato caratterizzazione della classe. I modelli di informazione sintetica
estratta sono di varia natura: uno dei modelli più diffusi rappresenta regole associative o
correlazioni tra un insieme di entità. Una regola associativa della forma YX è
interpretata come “le tuple di un database che soddisfano X, soddisfano anche Y”.
Questo tipo di analisi è utile in operazioni di marketing, realizzazione di cataloghi e
altre decisioni commerciali nel processo di marketing. Anche la classificazione e la
previsione sono tecniche di data mining. Nella prima si analizza un insieme di dati di
addestramento e si costruisce un modello per ogni classe basato sulla caratteristica dei
dati. Ad esempio, si possono classificare malattie e predire il tipo di disturbo in base ai
sintomi del paziente. La previsione prende in esame i possibili valori di alcuni dati
omessi o il valore della distribuzione di certi attributi in un insieme di oggetti; per
esempio, il salario potenziale di un impiegato può essere previsto sulla base della
distribuzione dei salari di impiegati simili in una certa compagnia.
Un altro tipo di analisi molto diffusa è il clustering. Questa tipologia di analisi si
focalizza sull’identificare cluster inclusi nei dati, dove un cluster è una collezione di
dati oggetto simili tra loro. Nel corso della tesi parleremo più in dettaglio di quali siano
le tipologie di clustering e gli algoritmi ad esse associati, discutendo i vantaggi e gli
svantaggi nell’adottarne una o l’altra.
Il clustering è una tecnica diffusa in molti settori, in particolare nei database spaziali;
questi tipi di database contengono informazioni su oggetti spaziali ed eventualmente
altre informazioni topologiche e di distanza e memorizzano un gran numero di dati
spaziali correlati, come mappe, dati derivanti da telerilevamento o immagini mediche.
Le informazioni sono generalmente accessibili attraverso metodi di accesso su oggetti
spaziali e richiedono ragionamenti di tipo spaziale, calcoli geometrici e tecniche di
rappresentazione della conoscenza di tipo spaziale.
Introduzione
3
L’applicazione di tecniche di mining e database spaziali prende il nome di data mining
spaziale e richiede l’integrazione di data mining con tecnologie proprie di database
spaziali.
Questo tipo di data mining può essere usato per scorrere/leggere database spaziali,
capire i dati stessi, scoprire le relazioni spaziali e quelle tra dati spaziali e non, costruire
una base di conoscenza e ottimizzare le query. L’aspettativa, citata in [HK00], è quella
di vedere un grande uso del data mining nei sistemi informativi geografici, GIS
(Geographic Information System).
Noi ci focalizzeremo proprio sul come applicare il data mining a sistemi GIS e in
particolare esamineremo come e in che modo aggiungere e trattare la componente
temporale associata alle informazioni spaziali. Tratteremo, cioè, il data mining spazio-
temporale.
Ma perché abbiamo deciso di aggiungere la componente temporale? Indubbiamente
perché il tempo è molto importante, esso è un costrutto umano con cui descriviamo e
stabiliamo i cambiamenti del sistema e degli oggetti in esame. Il tempo è una parte
integrante delle proprietà degli oggetti spaziali ed è solitamente poco trattato, anzi non
considerato, nell’ambiente Geographical Information System (GIS) commerciale,
mentre lo studio di questa componente è molto attivo come settore di ricerca. E’
importante trasferire questo risultato di ricerca nella applicazioni, visto che con le tre
dimensioni più quella temporale è possibile descrivere qualsiasi entità in movimento e
qualsiasi fenomeno come i cambiamenti della traiettoria di un ciclone, di un gruppo di
animali, di una costa, di un fiume; possiamo cioè modellare più “naturalmente” la realtà
e i fenomeni ad essa connessi.
Il data mining spazio-temporale può essere visto come una componente più generale del
ragionamento spazio-temporale e il nostro lavoro è proprio stato inserito in un progetto
di questo tipo. Il motivo per cui è stata scelta una realizzazione basata su un linguaggio
logico è proprio per mantenere l’uniformità e l’integrazione col progetto di partenza
come sarà trattato ampiamente nel capitolo 2.
Introduzione
4
Obiettivi della tesi
La tesi ha lo scopo di studiare la fattibilità e, di conseguenza, realizzare un
ambiente logico per fare clustering spazio-temporale. Le entità con caratteristiche
spaziali e temporali su cui ci siamo concentrati sono le traiettorie di oggetti in
movimento.
Il lavoro svolto in questa tesi ha una doppia valenza:
ξ di ricerca: conducendo un attento studio della letteratura e cercando,
successivamente, soluzioni nuove per affrontare i problemi legati a questa
tipologia di clustering. Non esistono infatti approcci logici, e quindi dichiarativi,
al clustering spazio-temporale.
ξ di progetto: implementando un’applicazione completa per il data mining spazio-
temporale che permetta di applicare tecniche di clustering a traiettorie, al fine di
valutare la fattibilità e l’efficacia di un siffatto strumento in relazione ai
problemi reali.
Organizzazione della tesi
Questo elaborato si divide essenzialmente in due sezioni, la prima dedicata allo
studio e alla ricerca e la seconda più tecnica, dedicata alla progettazione e allo sviluppo
di una applicazione. Vediamo in sintesi, gli argomenti trattati nei capitoli.
Nel capitolo 1 presentiamo una rassegna completa e dettagliata degli approcci attuali ai
metodi e agli strumenti per affrontare i ragionamenti spaziali, temporali e spazio-
temporali. In particolare, spieghiamo lo scopo del data mining spaziale e di quello
temporale, soffermandoci sulle varie metodologie esistenti in letteratura. Inoltre
introduciamo tutta la parte teorica riguardante il clustering spazio-temporale e gli
aspetti e i metodi di risoluzione.
Introduzione
5
Nel capitolo 2 descriviamo le caratteristiche dei linguaggi logici MuTACLP (Multy–
theory Temporal Annotated Constraint Logic Programming) e STACLP (Spatio
Temporal Annotated Constraint Logic Programming). Questi linguaggi forniscono
costrutti spaziali e temporali e sono stati sperimentati per esprimere ragionamento
spazio-temporale su dati GIS. L’approccio al problema del clustering su traiettorie è
mostrato mediante i modelli a spezzate, a rettangoli e a quadrati da noi realizzati, e
completato dalle definizioni di misure di distanza per questa tipologia di clustering.
Nel capitolo 3 descriviamo gli aspetti inerenti alla progettazione della nostra
applicazione, (modello a spezzate – algoritmo – interfaccia), mostrando anche tutti i
dettagli dell’architettura software utilizzata.
Nel capitolo 4, dopo una rassegna di potenziali aree applicative in cui utilizzare il nostro
approccio al clustering su traiettorie, descriviamo il comportamento dell’applicazione
sviluppata nei confronti di una base di conoscenza sintetizzata che abbiamo progettato
ad-hoc.
Il capitolo 5 raccoglie le conclusioni del nostro lavoro e propone una serie di possibili
sviluppi futuri e ottimizzazioni da realizzare.
Nell’appendice A è presentato tutto il dettaglio del codice dell’applicazione e le scelte
implementative.
Nell’appendice B mostriamo invece come procedere all’installazione di tutto il
necessario per l’esecuzione dell’applicazione.
Capitolo 1 – Stato dell’arte
6
Capitolo 1
Stato dell’arte
In questo capitolo illustreremo i principali strumenti esistenti in letteratura per
affrontare ragionamenti spaziali, temporali e spazio-temporali. In questa rassegna
cercheremo di analizzare, in modo critico, i più importanti e quelli più attinenti
all’argomento della nostra tesi.
Nella prima illustreremo i concetti chiave del data mining spaziale, di quello temporale
e di quello spazio-temporale in correlazione al mondo dei Geographic Information
Systems (GIS).
Nell’ambito del data mining, l’argomento che andremo ad affrontare nella tesi è quello
dell’estensione spazio-temporale di uno dei suoi strumenti: il clustering, per questo
nella seconda parte ne faremo una esaustiva trattazione sottolineando vantaggi e
svantaggi della loro applicazione.
Capitolo 1 – Stato dell’arte
7
1.1 Data Mining Spaziale
Il data mining spaziale è un importante processo per capire ed usare dati spaziali e
basi di conoscenza [KHA98]. Un punto critico riguardo al data mining è l’utilizzo di
tecniche efficienti per estrarre conoscenza da un grande numero di dati spaziali che sono
complessi da rappresentare e trattare.
Con l’avvento dei sistemi satellitari si sono venuti a creare database che contengono un
grande ammontare di dati spaziali e quindi si sono rese necessarie nuove tecnologie per
il knowledge discovery (KD) in database spaziali. Queste nuove tecnologie devono
cercare di estrarre conoscenza implicita, relazioni spaziali, o altri elementi di interesse
non memorizzati esplicitamente nei database spaziali.
Il processo di data mining spaziale, in via del tutto generale, può essere modellato
usando l’architettura descritta in figura 1.1.
Durante il processo di mining deve essere data la possibilità all’utente di supervisionare
tutti i passi di KD. Per prima cosa si memorizzano in una base di conoscenza, la
conoscenza di base, quella implicita e la gerarchia concettuale spaziale e non spaziale.
Poi si prelevano i dati da una struttura di memorizzazione usando l’interfaccia al
database che abilita l’ottimizzazione delle query. Le componenti fondamentali decidono
quali parti dei dati siano utili per la fase di pattern recognition; per esempio, si può
decidere che solo alcuni attributi siano rilevanti per le operazioni di KD o si possono
estrarre oggetti il cui utilizzo promette buoni risultati. I pattern e le regole sono trovate
dal modulo di “Estrazione dei Pattern”. Questo modulo può usare diversi approcci, che
vedremo nel seguito del capitolo, per trovare le regole e le relazioni. Il risultato del
lavoro di questo modulo viene passato al “Modulo di Valutazione” per eliminare
possibilmente la conoscenza ridondante e ovvia.
I componenti comunicano tra di loro attraverso la parte di controllo, che fornisce anche
un feedback per il raffinamento delle query.
Capitolo 1 – Stato dell’arte
8
Figura 1.1: Processo di data mining spaziale
Mostriamo, di seguito quali sono, al momento, i metodi principali usati dalla comunità
GIS per implementare il modulo di Estrazione dei Pattern e quindi per realizzare il data
mining spaziale.
1.1.1 L’analisi statistica
Il primo approccio, che è anche quello più comune per l’analisi dei dati spaziali, è
quello statistico.
L’analisi statistica è un’area molto ben studiata ed esistono un gran numero di algoritmi
e varie tecniche di ottimizzazione; essa tratta con successo dati numerici e fornisce
modelli realistici di fenomeni spaziali. I dati spaziali sono interrelazionati, cioè sono
influenzati dagli oggetti vicini. Sebbene questo tipo di assunzione sia troppo forte,
questo approccio si basa sull’assunzione di indipendenza statistica tra dati spazialmente
distribuiti. Lo stesso Han ha affermato in [HK00] che l’assunzione di indipendenza
statistica tra dati spazialmente distribuiti non modella esattamente la realtà, visto che nel
mondo reale gli oggetti sono spesso correlati. Un’altra critica scaturisce dal fatto che
Capitolo 1 – Stato dell’arte
9
molti modelli statistici possono essere realizzati e manipolati solo da esperti che hanno
una buona conoscenza del dominio ed esperienza nel campo della statistica. I metodi
statistici non lavorano bene con valori simbolici o incompleti o dati imprecisi, e sono
computazionalmente costosi nei database di grandi dimensioni.
1.1.2 Data Mining Spaziale Generalization-Based
Il secondo approccio che mostriamo è quello che per prima cosa astrae un gran
numero di dati rilevanti da un livello concettualmente basso ad uno corrispondente alto
e realizza un’astrazione di conoscenza sui dati generalizzati.
Il Data Mining Spaziale Generalizaztion-Based, [HNKW98], riassume la conoscenza in
forma di relazioni tra attributi spaziali e non spaziali ad un alto livello concettuale; in
altre parole, le regole generalizzate sono espresse ad alto livello. Senza il concetto di
generalizzazione, la scoperta di conoscenza sarebbe espressa in termini di basso livello
(i dati memorizzati nel database) spesso nella forma di dipendenze funzionali, regole
associative o vincoli di integrità di basso livello.
Al contrario, tramite il concetto di generalizzazione, la scoperta di conoscenza può
essere espressa in termini concisi, espressivi e ad un alto livello di astrazione, nella
forma di regole o restrizioni generalizzate, ed associate ad informazioni statistiche.
Formalmente, definiamo la generalizzazione di una certa componente p di un oggetto
O
i
, è definita in modo astratto, come Gen(O
i
.p), dove Gen è l’operatore astratto di
generalizzazione. Inoltre, la componente generalizzata di un oggetto può essere
ulteriormente generalizzata riapplicando l’operatore Gen.
Se la generalizzazione fosse realizzata applicando la solita sequenza di operatori di
generalizzazione su una componente p di O
i
, avremmo che
Gen
n-1
(Gen(O
i
.p)) ≡ Gen(Gen
n-1
(O
i
.p)).
Per esempio, l’indirizzo di una certa persona P
1
potrebbe essere generalizzato da un
indirizzo dettagliato formato da componenti come il numero della strada, il distretto di
appartenenza, la città, la provincia e la contea, tramite l’applicazione dell’operatore Gen
in instanti diversi come Gen(Gen(….Gen(P
1
.address)….).
Questo approccio assume l’esistenza di conoscenza di background nella forma di
gerarchia concettuale.
Capitolo 1 – Stato dell’arte
10
Le gerarchie concettuali possono essere date in modo esplicito da persone esperte o
essere generate automaticamente dall’analisi dei dati. Questo tipo di conoscenza viene
percorsa dal basso verso l’alto, ottenendo informazioni sempre più generali che sono,
tuttavia, consistenti con i livelli più bassi.
Il concetto più generale, che corrisponde al livello zero della gerarchia, è la descrizione
nulla, cioè quella che indica qualsiasi cosa, e la maggior parte di concetti specifici
corrispondono a valori specifici degli attributi nel database.
Esempio 1.1. Alcuni tipi di gerarchia.
In ambito agricolo l’avena può essere generalizzata con il concetto di grano, che a sua
volta include il frumento.
In una gerarchia concettuale per il territorio geopolitico le regioni che rappresentano le
contee possono essere fuse in stati e gli stati in regioni più grandi (come nell’esempio in
figura 1.2).
Figura 1.2: Gerarchia concettuale Geopolitica
□
Capitolo 1 – Stato dell’arte
11
La generalizzazione di una classe di oggetti può essere vista come una sequenza di
processi di generalizzazione orientati agli insiemi dove ognuno trasforma una classe in
classi relativamente più generalizzate. La classe costruita dal processo di
generalizzazione è chiamata classe di lavoro L, mentre la classe iniziale (quella formata
dagli elementi ritenuti importanti) è chiamata classe di lavoro iniziale, L
k
. La classe
generata dall’applicazione dell’operatore di generalizzazione è chiamata classe
risultante, R.
L’idea chiave di questa tipologia di data mining è l’induzione orientata agli attributi.
Questa è una tecnica efficiente di generalizzazione dei dati [FSP96], che presa una
query espressa in SQL-like, raccoglie l’insieme dei dati rilevanti in un database. A
questo punto viene fatta la generalizzazione dei dati risalendo le gerarchie concettuali e
riassumendo le relazioni generali tra dati spaziali e non spaziali ad un più alto livello
concettuale. L’induzione può essere applicata ai dati non spaziali in vari modi:
a. risalendo la gerarchia concettuale quando i valori di una tupla sono rimpiazzati da
valori generalizzati;
b. rimuovendo gli attributi quando non è possibile un ulteriore passo di
generalizzazione e ci sono troppi valori distinti per ogni attributo e
c. fondendo le tuple identiche.
Il processo di induzione continua fin quando tutti gli attributi sono generalizzati al
livello desiderato.
Per esempio, “età” può essere vista come un attributo ottenuto attraverso l’applicazione
del metodo “calcolo_età” basato sulla data di sistema corrente ed il valore contenuto
nell’attributo “data_di_nascita” di un oggetto “persona”.
Per la generalizzazione basata su classi, si seleziona un insieme di operatori di
generalizzazione e lo si applica ad un attributo contenuto in L
k
, senza considerare le
interrelazioni tra differenti attributi prima che i concetti in ogni attributo siano
generalizzati ad livello ragionevolmente alto.
L’induzione orientata agli attributi, che considera le relazioni tra attributi solo quando i
dati sono stati generalizzati ad un alto livello concettuale, ha lo scopo di ridurre
notevolmente la complessità computazionale nel processo di generalizzazione del
database.
Capitolo 1 – Stato dell’arte
12
Formalmente, l’operatore di generalizzazione Gen può essere applicato ad un attributo
a
i
su ciascun oggetto nella classe di lavoro L
K
, fornendo una nuova classe R
k
. In questo
modo, si introduce un operatore di generalizzazione di classe, ClassGen, che applica
l’operatore Gen ad un attributo a
i
di ogni oggetto contenuto nella classe di lavoro.
⊥
( , ) :( ) (. (.) (( ). . )
kkikii jj
R ClassGen L a o o L o a Gen oa j i o a oaχ χ χ ζ
Il processo di scoperta di conoscenza può essere visto come l’applicazione di una
sequenza di operatori di generalizzazione, ClassGen, su differenti attributi fin quando la
classe risultante contenga un piccolo numero di oggetti generalizzati che possono essere
riassunti attraverso una regola concisa e generalizzata ad alto livello.
Esistono due estensioni dell’algoritmo generale di induzione orientata agli attributi
[LH93]. La prima consente la descrizione di regioni spaziali usando predicati di alto
livello e si chiama spatial data-dominant generalisation. Qui l’algoritmo prima fonde
regioni spaziali in accordo con la gerarchia spaziale, poi produce una descrizione non
spaziale di ogni area usando la tecnica di induzione orientata agli attributi come visto
precedentemente. La risposta alla query è la descrizione di tutte le regioni usando la
disgiunzione di alcuni predicati che caratterizzano tutte le regioni da generalizzare.
La seconda estensione, non spatial data-dominant generalisation, crea una mappa che
consta in un certo numero, relativamente piccolo, di regioni che condividono la stessa
descrizione non spaziale ad alto livello. L’algoritmo parte con un’induzione orientata
agli attributi, generalizzandoli ad un più alto livello concettuale, più generale e prosegue
fondendo le aree vicine con gli stessi valori degli attributi generalizzati.
1.1.3 L’analisi associativa spaziale
Il terzo approccio al data mining spaziale è l’analisi associativa spaziale. Come
definito in [KH00], questo tipo di analisi è simile all’estrazione di regole associative in
database relazionali o transazionali. Una regola associativa spaziale è della forma
%]%,[ csBA , dove A e B sono insiemi di predicati spaziali e non spaziali, s% è il
supporto alla regola, detto anche funzione di utilità, e c% è la confidenza della regola o,
in altre parole, la misura di certezza. Questi due parametri qualitativi sono molto
importanti: il supporto (Supp) per un insieme di voci I, dove I = A B, è definito come
il numero di transazioni che contengono I, ( ) ( )Supp A B Supp A B . Esso misura
Capitolo 1 – Stato dell’arte
13
l’impatto della regola sull’insieme dei dati, quindi la parte delle transazioni dove la
regola è applicata [Nan02]. La confidenza è calcolata come il rapporto tra il supporto
della regola e il supporto di A,
)(
)(
)(
ASupp
BASupp
BAConf
. Questo parametro è la
probabilità condizionale che B appaia nella transazione dopo che si è verificato A. Un
valore di confidenza pari ad 1 indica che la regola è sempre corretta nei confronti dei
dati analizzati; queste regole sono chiamate esatte.
Esempio 1.2. Regola associativa spaziale.
La seguente regola è associativa spaziale:
is_a(X, “school”) close_to(X, “sport_centre”) close_to(X, “park”) [0.5%,80%]
La regola esprime il fatto che l’80% delle scuole che sono vicine a centri sportivi sono
anche vicine ai parchi e lo 0.5% dei dati fanno parte di questo caso.
□
Poiché il numero di regole cresce esponenzialmente con il numero delle voci possibili a
tal punto da diventare intrattabile a causa del costo computazionale, l’utente deve
specificare due soglie minime per il supporto e la confidenza prima che l’algoritmo di
mining possa partire.
Il processo di mining inizia con una query che descrive la classe di oggetti S usando
altre classi rilevanti di oggetti e un insieme di relazioni rilevanti. Per esempio, un utente
può voler descrivere parchi urbani presentando la descrizione delle relazioni tra i parchi
e altri oggetti come strade, ferrovie, ristoranti, zoo, ecc.
Un interessante metodo di ottimizzazione per il mining è quello del raffinamento
progressivo, che parte facendo un mining grossolano su grandi insiemi di dati usando
un algoritmo veloce e successivamente migliora la qualità del mining operando con un
algoritmo più costoso su un insieme di dati “filtrato”. E’ importante notare che per
assicurare la copertura dell’insieme filtrato rispetto a tutte le risposte possibili,
l’algoritmo di mining grossolano applicato allo stadio iniziale deve soddisfare la
proprietà di copertura del superset [HK00], cioè deve preservare tutte le risposte
potenziali.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
