Density-based clustering di traiettorie di oggetti mobili focalizzato sul tempo

2 CAPITOLO 1. INTRODUZIONE
Tuttavia, visto che solo recentemente e` nata l’esigenza di dover trattare dati
spazio-temporali, i modelli esistenti non sono ancora del tutto efficienti poiche´
non forniscono meccanismi di ragionamento espliciti e flessibili di cui l’infor-
mazione spazio-temporale necessita. Tra le varie limitazioni e` importante il
fatto che non e` presente un meccanismo ad alto livello che renda semplice
l’interrogazione della base di dati: per raggiungere un alto grado di perfor-
mance, l’utente deve essere un esperto del sistema e deve essere in grado di
usare primitive efficienti e di basso livello.
Anche il data mining su dati spazio-temporali e` ancora nella sua infanzia,
e i problemi che sono alla base di questo campo applicativo sono ancora
largamente irrisolti: che genere di pattern possono essere estratti da traiet-
torie? Quali metodi ed algoritmi dovrebbero essere applicati per estrarli?
Come possono essere usati efficacemente per migliorare la comprensione del
dominio applicativo e rendere migliori i servizi?
Una tecnica di base che potrebbe essere applicata alle traiettorie e`ilcluste-
ring, cioe` , la scoperta di gruppi di traiettorie simili, e di un rappresentante
per ogni gruppo. Conoscere quali sono i percorsi stradali principali (rappre-
sentati dai cluster) piu` frequentati dalle persone durante il giorno, puo`rap-
presentare un’informazione preziosa per migliorare molti servizi ai cittadini.
Cluster di traiettorie, possono ad esempio rilevare la presenza di importanti
percorsi stradali non adeguatamente coperti dal servizio di trasporto pubbli-
co.
Il clustering di dati spazio-temporali (nel nostro caso di traiettorie di oggetti
mobili) richiede la scoperta di un appropriato livello di granularita` spaziale
e di un dominio temporale significativo (per esempio, e` probabile che un cer-
to processo di clustering su dati del traffico automobilistico individui facil-
mente tramite dei cluster ore di traffico intenso, mentre e` probabile che gli
altri perio-di di tempo aggiungano semplicemente rumore al processo). Tut-
tavia, non e` ovvio identificare il metodo di clustering piu` adeguato fra i tanti
esistenti in letteratura (data mining e statistica); ne´e` ovvio scegliere, fra
le varie opzioni, come rappresentare le traiettorie di oggetti in movimento
e forma-lizzarne la nozione di (dis)similarita` (o distanza). Lo stato della
ricerca in questo campo, descritto nel prossimo capitolo, e` assai limitato.
1.2. SCOPO DELLA TESI 3
1.2 Scopo della tesi
In questo contesto, focalizziamo la nostra attenzione sul problema del cluste-
ring di traiettorie. La nostra assunzione di base sui dati e` che le traiettorie di
oggetti mobili possano essere ricostruite in un modo approssimato sulla base
dei log lasciati dagli oggetti mentre si muovono all’interno dell’infrastruttura
di rete. Per esempio, un telefono mobile che si muove fra le varie celle,
durante le sue interazioni con la rete, lascia un insieme di triplette (id, loc, t),
che specificano la localizzazione spaziale loc,altempot, del telefono id.
Utilizzando l’insieme di triplette di un determinato oggetto id e` possibile,
in principio, definire (approssimare) una funzione : f
id
: time → space,che
assegna una posizione all’oggetto id per ogni istante, in un intervallo di tempo
determinato. Noi chiamiamo tale funzione traiettoria, e ci concentriamo sul
problema del clustering su un insieme di finito di questo tipo di oggetti.
Questa assunzione di base e` conforme con la forma dei log chesono(opossono
essere) raccolti nell’infrastruttura della rete. Il nostro lavoro di ricerca fara`
affidamento sulla disponibilita` di un generatore [22] di traiettorie, sviluppato
nel nostro laboratorio per generare il dataset di traiettorie utilizzato per la
valutazione empirica dei risultati ottenuti.
In questa lavoro di tesi, ci siamo posti due domande distinte:
1. qual e` il metodo di clustering piu` adeguato per le traiettorie?
2. come possiamo sfruttare la semantica intrinseca della dimensione tem-
porale, per migliorare la qualita` del clustering?
Per quanto riguarda il primo problema, pensiamo che il clustering basato sul-
la nozione di densita` density-based,propostoin[6],e` particolarmente adatto
al clustering di traiettorie, per le seguenti caratteristiche distintive:
• la sua capacita` di determinare cluster non-sferici (non convessi), al
contrario dei metodi di partizionamento (k-means) e gerarchici,
• la sua robustezza rispetto al rumore,
• la sua capacita` di restituire un numero arbitrario di cluster, che meglio
descrivano la naturale struttura dei dati, come fanno i metodi gerarchici
ma con una complessita` minore (O(n log n) anziche´ O(n
2
)).
Le caratteristiche sopra descritte sono punti chiave nel clustering di traiet-
torie di oggetti mobili: e` probabile che traiettorie di macchine nel traffico
4 CAPITOLO 1. INTRODUZIONE
urbano tendano ad agglomerarsi in cluster dalla forma serpentina e non con-
vessa, che molte traiettorie non debbano essere incluse nei cluster, ma piut-
tosto essere considerate semplicemente noise data e che il numero dei cluster
non sia noto a priori.
Algoritmi basati sulla densita` risolvono i problemi citati raggruppando
gli oggetti in cluster solo in base alla densita`, ossia la quntita` di oggetti
all’interno di una determinata regione nello spazio.
Nel nostro approccio, la nozione spaziale di distanza tra oggetti viene
generalizzata con una nozione di distanza spatio-temporale fra traiettorie,
rendendo possibile cos`ı una naturale estensione del metodo density-based per
questo tipo di oggetti. Utilizzeremo un particolare algoritmo density-based,
OPTICS e mostreremo un confronto empirico con gli algoritmi gerarchici e
K-means: in particolare mostreremo come, su un particolare esperimento, il
nostro approccio basato sulla densita` riesce a trovare i cluster naturali, pre-
senti nei dati d’origine, mentre tutti gli altri metodi falliscono. Questa sorta
di evidenza empirica, mette in luce come OPTICS garantisca una migliore
qualita` dell’output, rispetto agli altri metodi tradizionali.
Il secondo contributo di questa tesi e`ilfocus temporale. Qui sottolinea-
mo che la dimensione temporale gioca un ruolo fondamentale nel cluste-
ring di traiettorie: due traiettorie, completamente differenti e distanti du-
rante l’intero intervallo temporale, possono diventare molto simili se ristrette
ad un sotto-intervallo - un esempio ovvio sono le traiettorie dei veicoli nel
traffico urbano.
`
E quindi interessante concentrare il processo di clustering
density-based sulla dimensione temporale - praticamente allargando lo spazio
di ricerca dei cluster interessanti considerando le traiettorie d’origine definite
su sotto-intervalli di tempo.
L’algoritmo proposto, per il focus temporale, percorre gli intervalli di
tempo piu` significativi che permettono di isolare cluster (density-based) di
qualita` migliore. La capacita` del metodo proposto di produrre clustering di
migliore qualita`e` messa in luce da uno specifico esperimento.
1.3 Organizzazione della tesi
La tesi segue la seguente organizzazione:
1.3. ORGANIZZAZIONE DELLA TESI 5
Capitolo 2: Database spazio-temporali e data mining
Il capitolo si articola principalmente in tre sezioni. Nella prima sezione ven-
gono descritti in breve quelli che sono i principali metodi di modellazione
di dati spazio-temporali. Nella seconda parte vengono introdotte le tecniche
di Data Mining piu` diffuse con particolare attenzione al Clustering di dati
vettoriali e ai suoi campi applicativi. L’ultima sezione e` dedicata a una breve
rassegna sui metodi di clustering su traiettorie.
Capitolo 3: OPTICS
Questo capitolo offre una panoramica sull’algoritmo di clustering OPTICS,
oggetto di questa tesi
Capitolo 4: OPTICS su traiettorie
Questo capitolo e` dedicato al primo contributo di questa tesi: l’implemen-
tazione di OPTICS su traiettorie. La prima parte e` dedicata alla descrizione
del modello dei dati e della distanza spazio-temporale adottata. Seguono una
serie di esperimenti effettutati e la valutazione dei risultati ottenuti.
Capitolo 5: Focus Temporale
In questo capitolo e` descritto il secondo e piu` importante contributo della
nostra ricerca: il disegno e l’implementazione di un algoritmo che realizza il
focus temporale su clustering di traiettorie.
Capitolo 6: Conclusioni e lavori futuri
La tesi si conclude con un riassunto degli aspetti trattati e una sezione in cui
vengono mostrati i progetti futuri ispirati alle tematiche affrontate in questo
lavoro.
Capitolo 2
Database spazio-temporali e
data mining
In questo capitolo illustreremo i principali strumenti esistenti in letteratura
per effettuare ragionamenti di tipo spaziale, temporale e spazio-temporale.
In questa rassegna cercheremo di analizzare, in modo critico, i piu` importanti
e quelli piu` attinenti all’argomento della nostra tesi.
Nella prima parte saranno illustrati i concetti chiave della modellazione
di dati spazio-temporali.
Nella seconda parte presenteremo una introduzione al clustering, un meto-
do di analisi delle informazioni per l’interpretazione delle stesse mediante il
loro raggruppamento. Introdurremo inizialmente il Data Mining, un impor-
tante passo del processo conosciuto come Knowledge Discovery, nel quale il
clustering ha una diffusa applicazione. Faremo successivamente una panora-
mica sui principali campi applicativi in cui le tecniche di clustering sono uti-
lizzate con una particolare attenzione per il Data Mining. Infine proporremo
una lista di requisiti che un algoritmo di clustering deve soddisfare affinche´
possa considerarsi valido e, dopo averne introdotto i concetti di base, pre-
senteremo una rassegna delle principali tecniche di clustering fornendo per
ciascuna di esse esempi degli algoritmi piu` rappresentativi. In particolare ci
concentreremo su metodi di clustering density-based (DBSCAN e OPTICS).
La terza ed ultima parte del capitolo e` dedicata ad una rassegna dei
principali metodi di data mining su traiettorie di oggetti mobili.
7
8 CAPITOLO 2. DATABASE SPAZIO-TEMPORALI E DATA MINING
2.1 Modellazione Spazio-Temporale
In questo paragrafo presentero` una rassegna sui vari metodi di rappresen-
tazione dei dati spazio-temporali.
La modellazione e il trattamento di dati spazio-temporali e` alla base di
molte attivita` umane e quindi si sono sviluppate numerose ricerche in questo
campo negli ultimi anni. La manipolazione di dati complessi, come quelli
spazio-temporali di grandi dimensioni, richiede una certa esperienza e com-
petenza per memorizzare e manipolare i dati geometrici e temporali, cio`e`
dovuto alla particolare mancanza di un formalismo ad alto livello che tratti
questo genere di informazioni in modo piu` astratto. I database tradizionali,
infatti, non sono in grado di manipolare questi dati complessi ad un alto
livello d’astrazione. Solitamente un tipico sistema GIS (Geographic Informa-
tion system: Sistema Informativo Geografico) incorpora parecchi database
differenti ed e` capace di analizzare i dati sia in modalita` raster che vettoriale.
`
E proprio questa possibilita` di combinare o dividere in differenti livelli (layer)
i dati spaziali o planimetrici (generalmente in forma vettoriale) che da`aiGIS
potenza e flessibilita`. I dati spaziali presentano una struttura complessa che
varia dal singolo punto all’insieme di poligoni, essi sono spesso dinamici, sono
esigenti in termini di spazio, gli operatori spesso non sono chiusi, il costo delle
operazioni e`, in genere, molto maggiore rispetto a quelle su dati relazionali e
le cancellazioni e le inserzioni vengono alternate ad aggiornamenti. Esistono
diversi metodi per la rappresentazione spazio-temporale, noi ne descriveremo
alcuni per averne un’idea generale.
Modello Snapshot (Armstrong)
In questo modello di Armstrong l’informazione temporale e` associata a par-
ticolari strati contrassegnati nel tempo (time-stamped). Lo stato del mondo
e` dato ad intervalli regolari o irregolari in differenti mappe, una distinta per
ogni stato. Questo approccio porta ad una certa ridondanza e ad inconsis-
tenza di dati. Ogni layer e` una collezione di unita` temporali omogenee di
un soggetto (come descritto in figura 2.1) , dove sono rappresentati gli strati
di una distribuzione geografica in differenti istanti temporali, senza esplicite
relazioni relative al tempo, lungo i layer.
2.1. MODELLAZIONE SPAZIO-TEMPORALE 9
Figura 2.1: Esempio di modello snapshot
Modello Space-Time Composite (Langran)
Langran e Chrisman, in [47], nel loro modello Space-Time Composite, costrui-
scono tabelle tematiche e attributi temporali ogni volta che delle operazioni
provocano un qualsiasi cambiamento negli oggetti spaziali. Quindi le entita`
geografiche tendono ad essere decomposte in frammenti di oggetti spaziali.
Per esempio, un incendio violento potrebbe essere rappresentato da un in-
sieme di poligoni con descrizioni sull’intensita` ed il tempo dell’incendio, come
in figura 2.2. Il mondo e` rappresentato come un insieme di oggetti spazial-
Figura 2.2: Esempio di layer STC nel caso di un incendio
mente omogenei e temporalmente uniformi in uno spazio 2D che e` discreto e
costituito da atomi spazio-temporali. Le entita` geografiche tendono ad essere
decomposte in frammenti di oggetti spaziali. Questo modello e` in grado di
memorizzare i cambiamenti negli attributi di un oggetto sia nella dimensione
spaziale che in quella temporale, ma non riesce a rappresentare i cambia-
10 CAPITOLO 2. DATABASE SPAZIO-TEMPORALI E DATA MINING
menti graduali nello spazio attraverso il tempo proprio perche´ gli atomi sono
discreti.
ST-simplexes (Worboys)
Modello unificato per l’informazione spaziale e temporale, che rappresenta
le informazioni basandosi su un approccio a tre dimensioni (x, y, t), dove x
e y sono posizioni nello spazio e t e` la componente temporale [69]. L’idea
di base e` quella di associare ad ogni oggetto spaziale elementare un ele-
mento bitemporale ad esempio, un set di coppie d’intervalli di tempo che
rappresentano rispettivamente il database e l’evento temporale dell’ogget-
to. Gli oggetti sono modellati come traslazione lungo l’asse temporale e
collocati costruttivamente in una struttura a tre dimensioni, come in figura
2.3. L’oggetto spaziale elementare e` detto simplex e puo` essere un punto
Figura 2.3: Modellazione di Workboys
singolo, un’area triangolare o delle semirette. Per ogni dimensione d,un
d − simplex e` l’oggetto minimo in quella dimensione, (1 − simplex e` una
linea, un 2 − simplex e` un triangolo, ecc). Un complex e` invece un insieme
finito di simplex, tale che l’intersezione di qualsiasi 2− simplex nell’insieme
e` una faccia. L’ ST − simplex e` una coppia <simplex, insieme di elementi
bitemporali>. Un oggetto spaziale complesso referenziato temporalmente e`
chiamato ST − complex, modellato da un insieme finito di ST-simplex.
2.1. MODELLAZIONE SPAZIO-TEMPORALE 11
Figura 2.4: Esempio di 1-complex e di 2-complex
Figura 2.5: ST-complex
Modello K-spaghetti (Chomicki-Revesz)
Questo modello proposto da Chomicki e Revesz [9], e` molto popolare per
rappresentare i databases spaziali in applicazioni come il CAD (Computer
Aided Design) e il GIS.
Secondo la dimensionalita` dei dati K e` possibile essere piu` specifici e
chiamarlo modello di dati K-Spaghetti. Noi ci occuperemo soprattutto dello
studio del modello 2-spaghetti parametrico (con K=2), poiche´ nelle appli-
cazioni GIS, gli oggetti di interesse sono rappresentati solitamente sul piano.
Nel modello Spaghetti si possono rappresentare solo gli oggetti spaziali che
sono composti da un insieme finito di poligoni chiusi. Ogni oggetto spaziale
puo` essere decomposto in un insieme di triangoli rappresentati dai loro tre
vertici, in una tabella relazionale singola.