Mobility User Profile per lo studio delle deviazioni dai comportamenti di mobilità sistematici.

Mobility User Profile:

per lo studio delle deviazioni dai

comportamenti di mobilità sistematici

Relatore:

Chiar.mo Prof.

Mirco Nanni

Candidata:

Paola Barra

matr. 510537

Anno Accademico 2015/2016

Abstract

Le tecnologie di localizzazione e raccolta dei dati permettono oggi di avere a disposizione grandi quantità di informazioni sugli spostamenti di oggetti in movimenti; in particolare in questo lavoro ci concentriamo sugli spostamenti di autoveicoli e quindi spostamenti urbani. In questo contesto i Big Data della mobilità umana saranno chiamati a fornire i dati essenziali per la costruzione di nuovi percorsi di spostamento e di nuove modalità di fruizione dello spazio cittadino. Il Trajectory Data Mining è la disciplina che si occupa di analizzare i dati di traiettorie spaziali. In questo lavoro viene affrontato il problema di sviluppare un metodo specifico di analisi delle traiettorie proiettate sulla rete stradale (Map-matching). Questo metodo prende il nome di Mobility User Profiling, ed ha lo scopo di estrarre il profilo di mobilità rappresentativo di ciascun utente, ovvero i relativi comportamenti sistematici di mobilità. Sulla base di questi ultimi viene svolto un lavoro di analisi sui comportamenti di mobilità che deviano dai percorsi sistematici dell’uten-te, alla ricerca di cause (ad esempio eventi che hanno generato queste variazioni) e/o regolarità.

Indice

1 Introduzione 4

2 Trajectory data mining. 6

2.1 GPS Coordinates . . . 7

2.2 Trajectory Preprocessing. . . 8

2.2.1 Noise Filtering - filtraggio del rumore . . . 8

2.2.2 Stay Point Detection - individuazione dei punti di sosta . . . 9

2.2.3 Compression - Compressione delle traiettorie . . . 9

2.2.4 Segmentation - Segmentazione delle traiettorie. . . 10

2.2.5 Map-matching . . . 11

2.3 Trajectory Data Mining . . . 16

2.3.1 Metodi primari di mining. . . 17

2.3.2 Metodi secondari di mining. . . 19

3 Mobility user profiles da traiettorie proiettate. 26 3.1 Definizioni per il mobility profile. . . 27

3.1.1 User history . . . 27 3.1.2 Stay Point . . . 28 3.1.3 Stop Reale . . . 28 3.1.4 Trip . . . 29 3.1.5 Trip Group . . . 29 3.1.6 Mobility profile . . . 30

3.2 Costruzione del mobility profile . . . 31

3.4 SelectGroups : Proposta dell’algoritmo di Clustering per la creazione dei

trip group . . . 33

4 Ricerca delle variazioni ai profili. 37 4.1 Algoritmo per la costruzione dell’insieme delle variazioni delle routine . . 38

5 Un caso di studio: il dataset Octo Telematics 40 5.1 Descrizione del DataSet . . . 40

5.1.1 La tabella derivata alltraj . . . 44

5.1.2 Scelta degli utenti da profilare . . . 46

5.2 Tuning dei parametri . . . 48

5.2.1 Suddivisione della user history in trip . . . 49

5.2.2 Identificazione dei trip group . . . 49

5.2.3 Selezione dei profili rappresentativi . . . 53

5.3 Analisi delle variazioni . . . 55

5.4 Risultati . . . 55

Capitolo 1

Introduzione

E’ noto che la gran parte della popolazione mondiale vive concentrata nelle città e che ad oggi in molti dei centri urbani la mobilità non è sostenibile; basti pensare ai livelli di traffico, all’inquinamento, alla scarsa vivibilità, per cui risulta chiaro come una riorga-nizzazione dei trasporti potrebbe essere centrale per un miglioramento delle condizioni degli abitanti.

I Big Data potrebbero essere in questo senso fondamentali. Raccogliere i dati provenienti da sensori di localizzazione GPS consentirebbe di analizzare i comportamenti degli uten-ti, così da poter approntare opportune strategie, quali la individuazione di un trasporto pubblico ridisegnato sulle esigenze dei potenziali utenti, o la ridefinizione dell’intero as-setto viario urbano. Si tratta ovviamente di sfide ambiziose, che coinvolgeranno non solo i data scientist ma molte altre figure professionali, come ad esempio quelle degli urbanisti o dei sociologi. Il futuro degli spostamenti urbani andrà sicuramente di pari passo con la Big Data Mobility, che sarà chiamata a fornire i dati essenziali per la costruzione di nuovi percorsi di spostamento e di nuove modalità di fruizione dello spazio cittadino. Le tecnologie di comunicazione mobile pervadono l’attuale società in cui reti wireless rilevano gli spostamenti delle persone generando grandi volumi di dati di mobilità, quali record che registrano chiamate di telefonia cellulare e record di tracce GPS. L’analisi del-la quantità notevole di dati di traiettorie può contribuire a scoprire del-la complessità deldel-la mobilità umana. Il processo di scoperta di conoscenza contenuto in questi dati risponde a domande su alcuni temi fondamentali poste dagli analisti della mobilità: quali sono i pattern frequenti dei viaggi della gente? quali sono i grandi attrattori e gli eventi

straor-dinari che influenzano la mobilità? in che modo si possono prevedere zone di traffico intenso nell’immediato futuro? Come è possibile caratterizzare ingorghi di traffico? Il Mobility Data Mining, vale a dire l’estrazione di dati di movimento, è un campo di ricerca che è emerso solo di recente. Questo campo di ricerca si adatta e si estende al-l’ambito dei dati di traiettorie diversi problemi e soluzioni originariamente studiate per contesti transazionali e dati tabellari, quali il clustering, la ricerca di pattern frequenti e la classificazione.

In questo lavoro di tesi è stato affrontato il problema dell’estrazione di traiettorie frequenti da un dataset di dati di mobilità rilevati da sensori di mobilità di veicoli. I dati analizzati sono stati raccolti dalla società Octo Telematics SpA, e sono stati utilizzati su loro concessione per studiare e sperimentare tecniche di Mobility Data Mining per l’e-strazione di conoscenza sulle abitudini di mobilità degli utenti, in un arco temporale dal 1/5/2011 al 31/5/2011. A partire dai dati grezzi, oggetto di lavori precedenti era stata la estrazione e decomposizione di traiettorie in termini di segmenti stradali. Dopo questa prima riorganizzazione dei dati sono state sviluppate tecniche per il riconoscimento di pattern (percorsi) simili rispetto a una misura di somiglianza basata sulla distanza di Levenshtein.

La tesi è organizzata come segue: nel capitolo 2 vengono riportati i concetti di base e i risultati stato dell’arte relativi al Trajectory Data Mining. Nel capitolo 3 sono descritte in dettaglio le tecniche per l’estrazione dei profili utente, in base ai loro comportamenti di mobilità sistematici (Mobility User Profile) estratti grazie all’utilizzo dell’algoritmo di clustering presentato. Nel capitolo 4, sulla base dei risultati prodotti nel capitolo precedente per l’estrazione dei Mobility User Profile, vengono effettuate analisi relative alle deviazioni sui comportamenti di mobilità sistematici. Nel capitolo 5 viene presen-tato un caso di studio, applicando le tecniche discusse nei capitoli precedenti al dataset della Octo Telematics. Infine nel capitolo 6 vengono tracciate le conclusioni e presentati possibili sviluppi futuri.

Capitolo 2

Trajectory data mining.

L’analisi del movimento è stata favorita dalla diffusione di tecnologie wireless come il GPS (Global Positioning System) e le reti mobili cellulari. Queste reti infrastrutturali permettono di registrare e collezionare grandi insiemi di dati spazio-temporali, che rap-presentano la mobilità umana. Questi database sono un nuovo potente strumento sociale in grado di aiutare a capire pattern nascosti nell’insieme delle traiettorie umane registra-te costanregistra-temenregistra-te. Il Trajectory data mining è un campo di ricerca che ha attratto rappresentanti delle più diverse discipline, fornendo non solo una interessante sfida ma anche una potenzialità per campi come l’urbanistica, la mobilità sostenibile, l’ingegne-ria dei trasporti, la salute pubblica e l’economia. L’interesse è una diretta conseguenza dell’importanza dei dati di movimento; infatti, grazie ad essi ed anche grazie alle tec-nologie a loro supporto, è possibile studiare fenomeni che in passato erano di difficile comprensione. Di seguito verranno esposte le tecniche e i processi attualmente applicati nel Data Mining applicati ai dati di movimento. Introduciamo i concetti fondamentali e le tecniche che rappresentano la base del Trajectory data mining. Seguendo lo schema in figura 2.1 saranno discusse le fasi principali:

-GPS Coordinates.

-Trajectory Preprocessing. -Trajectory Data Mining. -Mining Mobility User Profile.

Figura 2.1: I concetti e le tecniche fondamentali che rappresentano il Trajectory Data mining.

2.1 GPS Coordinates

Inizialmente i dati in input sono punti GPS con timestamp, che formano le traiettorie. Diamo ora alcune definizioni [48] che ci saranno utili nel seguito.

DEFINIZIONE: traiettoria GPS. Una traiettoria GPS di un oggetto in

movi-mento è una traccia discreta che l’oggetto in movimovi-mento percorre nello spazio geografico. In generale è una sequenza di punti GPS geo-localizzati in un istante di tempo (time-stamp) in un dominio spazio-temporale, cioè T = {Èp1, t1Í, Èp2, t2Í, ..., Èpn, tnÍ} dove ogni

elemento Èpi, ti_{Í indica che l’oggetto in movimenti si trova nella locazione p}i nell’istante ti. Inoltre gli elementi sono ordinati per timestamp, quindi tj < tk per 1 Æ j < k Æ n.

Una traiettoria GPS è un cammino generato da un oggetto in movimento nello spazio geografico, solitamente rappresentato da una serie di punti ordinati geograficamente t =

p1 ≠æ p2 ≠æ ... ≠æ pn dove ciascun punto p = {x, y, t} consiste di un insieme di

DEFINIZIONE: Road network. Una rete stradale, o road network, è un grafo

diretto G = (V, E) dove V ed E sono rispettivamente l’insieme dei vertici e l’insieme degli archi. Un vertice vi œ V , è un incrocio tra strade o il termine di una strada. Un

arco, ek = vp, vq œ E, denota un segmento di strada orientato su cui la direzione di

viaggio degli oggetti in movimento è da vp a vq.

DEFINIZIONE: Path. Un percorso stradale, path, P = Èe1, e2, ..., enÍ

rappresen-ta una sequenza di archi in una rete stradale, dove n = |P| e ei ”= ej per i ”= j, con ei, ej œ E e 1 Æ i, j Æ n. In particolare, archi consecutivi devono condividere un vertice, e.g., ei e ei+1, condividono il vertice che è la destinazione di ei e il punto di partenza di ei+1.

DEFINIZIONE: Arco stradale Un arco, o segmento, stradale e è una coppia di

punti GPS consecutivi Èpi, tiÍ, Èpi+1, ti+1Í con ti < ti+1 e

2.2

Trajectory Preprocessing.

La fase di preprocessing delle traiettorie, o Trajectory Preprocessing, ha lo scopo di trasformare i dati geografici, rappresentati da coordinate spaziali GPS, in segmenti su una rete stradale. Questa fase ha lo scopo di preparare i dati alle analisi, ed è articolata nei seguenti passi:

- Noise Filtering (filtraggio del rumore nei dati);

- Stay-point detection (individuazione dei punti di sosta); - Compression (compressione delle traiettorie);

- Segmentation (segmentazione delle traiettorie);

- Map-matching (abbinamento dei punti GPS con la rete stradale).

2.2.1 Noise Filtering - filtraggio del rumore

Le traiettorie spaziali non sono mai perfettamente accurate, a causa del rumore nel segnale dei sensori o alla ricezione di segnali deboli di posizionamento. Talvolta, l’errore è accettabile (ad esempio quando pochi punti GPS di un veicolo cadono fuori dalla strada su cui il veicolo sta procedendo); un tale errore può essere corretto da algoritmi

di Map-matching introdotti nel seguito. In altre situazioni l’errore di un punto è troppo grande (ad esempio dista di varie centinaia di metri rispetto alla posizione effettiva in cui l’oggetto si trova) per consentire di derivare informazione utile, quali per esempio la velocità. Perciò abbiamo bisogno di filtrare tali punti dalle traiettorie prima di avviare un task di mining. Sebbene questo problema non è mai stato completamente risolto, i metodi esistenti cadono in tre categorie principali:

- il filtro della media (o mediana), - i filtri di Kalman e

- la detezione degli outlier basati su euristiche. Per approfondimenti sulle tecniche di filtraggio si rinvia a [2].

2.2.2 Stay Point Detection - individuazione dei punti di sosta

I punti spaziali non hanno tutti la stessa importanza in una traiettoria. Alcuni punti indicano locazioni in cui le persone hanno sostato per un po’, quali grandi magazzini e attrazioni turistiche o distributori di benzina dove un veicolo si è fermato a fare riforni-mento. Questi tipi di punti sono chiamati punti di sosta (Stay Point). Li ed altri [45] per primi hanno proposto un algoritmo per individuare i punti di sosta. Il loro algoritmo verifica se la distanza spaziale e la distanza temporale tra un punto e i suoi successori è maggiore di una data soglia. La scelta della soglia spaziale e la scelta della soglia temporale sono gli elementi da sintonizzare che consentono di determinare se un punto è uno Stay Point. Yuan ed altri [10] [11] hanno migliorato l’algoritmo utilizzando un’idea di clustering basato sulla densità.

2.2.3 Compression - Compressione delle traiettorie

E’ relativamente problematico memorizzare o trasmettere una grande quantità di dati geografici creati con le tecniche di acquisizione di localizzazioni. Fondamentalmente, noi potremmo registrare una coordinata con timestamp1 _{ogni secondo per un dato oggetto}

in movimento, ma questo costa moltissima potenza di batteria e rappresenta un sovrac-carico per la comunicazione, l’elaborazione e la memorizzazione dei dati. Inoltre, molte applicazioni non hanno bisogno effettivamente di una tale precisione di localizzazione.

1_{stringa con le informazioni relative al tempo (data e ora), dell’istante in cui è stata acquisita}

Un algoritmo di compressione spesso cerca il miglior compromesso tra il rapporto di com-pressione e l’errore: generalmente, più alto è il rapporto di comcom-pressione e più bassa è la qualità dei dati compressi. Per affrontare questo problema sono state proposte due cate-gorie di strategie di compressione di traiettorie basate sulla forma di una traiettoria; tali strategie mirano a ridurre la dimensione di una traiettoria, senza compromettere troppo la precisione nella rappresentazione dei nuovi dati [46]. Una categoria di strategie è la compressione offline (anche detta batch) che riduce la dimensione della traiettoria dopo che questa è stata pienamente generata. Data una traiettoria, che consiste in una serie completa di punti geografici con timestamp, un algoritmo di compressione batch mira a generare una traiettoria approssimata scartando alcuni punti con errore trascurabile dalla traiettoria originaria2_.

L’altra categoria di strategie è la compressione online che comprime una traiettoria istan-taneamente man mano che l’oggetto viaggia, questo perché molte applicazioni richiedono che i dati di traiettorie siano trasmessi prontamente.

2.2.4 Segmentation - Segmentazione delle traiettorie.

In molti scenari quali il clustering e la classificazione di traiettorie, abbiamo bisogno di suddividere la traiettoria in sotto-traiettorie [48], o segmenti di traiettoria, per le elaborazioni successive. Generare sotto-traiettorie è razionale, poiché corrisponde a sot-tolineare strutture nei dati di traiettoria, ad esempio un Path con multipli segmenti di strada. Un approccio partition-and-summarization (partizionamento e somma) [49] che prova a generare una descrizione dei dati di traiettorie leggibili dall’uomo, divide una traiettoria in diverse partizioni a seconda dei comportamenti degli oggetti in movimento. Le traiettorie sono partizionate in frames [50] [51] per memorizzare efficientemente punti campione di un oggetto in movimento, allineati agli intervalli di tempo. Per ulteriori approfondimenti sulle tecniche di segmentazione delle traiettorie si rinvia a [2].

2_{Questo studio è molto simile al "line simplification problem", studiato dalle comunità informatiche}

2.2.5 Map-matching

Il Map-matching è un processo che associa una sequenza di punti GPS a una sequenza connessa di segmenti di strada. La conoscenza della strada su cui un veicolo è/era, è importante per valutare il flusso di traffico, predire dove il veicolo sta andando e trova-re il cammino di viaggio più ftrova-requente tra un’origine e una destinazione e così via. Il Map-matching non è un problema banale, date strade parallele, cavalcavia e ponti [46]. Ci sono due approcci per classificare i metodi di Map-matching esistenti, in base al-l’informazione aggiuntiva utilizzata o all’intervallo di punti campione considerati in una traiettoria.

Inoltre il Map-matching può essere trattato a due differenti scale, a seconda della fre-quenza di campionamento dei dati: alta o bassa frefre-quenza. Un argomento rilevante introdotto dal campionamento a bassa frequenza è la ricostruzione del percorso. Dopo aver mappato i punti singoli sulla rete stradale, tra due locazioni consecutive ci deve essere un gap significativo per cui occorrono strategie per ricostruire il cammino percor-so. Una tecnica usata per il Map-matching a bassa frequenza tiene in considerazione in particolare la stima dei tempi di viaggio di un segmento stradale piuttosto che la sua lunghezza, quindi mettendo in discussione l’assunzione che il percorso più breve/più ve-loce sia è il migliore.

A partire dal Map-matching, in [28] è stata sviluppata una metodologia per l’estrazione dei profili di mobilità degli utenti, vale a dire il comportamento di mobilità sistematica di un utente. La metodologia viene descritta e discussa in dettaglio nel capitolo 3.

Map-matching Time Aware

Map-matching Time-Aware [13], è un algoritmo di Map-matching per dati GPS a basso campionamento dipendente dal tempo. La figura 2.2 mostra il flusso di lavoro generale dell’algoritmo di Map-matching Time-Aware.

Abbinando i punti sulla mappa otteniamo una rete stradale arricchita con una stima precisa, dipendente dal tempo, dei tempi di viaggio (vedi parte alta della figura 2.2 ).

L’ algoritmo di Map-matching Time-Aware usa i tempi di viaggio per trasformare una traiettoria GPS con timestamp, in una sequenza di segmenti stradali con un tempo di viaggio simile al timestamp. L’attenzione è concentrata nel trovare il cammino tra punti consecutivi che meglio approssimano il tempo di viaggio reale. La figura 2.3 mostra

Figura 2.2: Una rappresentazione grafica del processo di Map-matching Time-Aware

Figura 2.3: Un esempio dal dataset reale, sul problema che stiamo affrontando: dati due punti GPS A e B con i loro relativi timestamp, noi cerchiamo il percorso che più si può approssimare con il tempo di viaggio dei punti in input. Come raffigurato, in questo caso il percorso più corto è anche il più veloce.

l’idea alla base di questo approccio. La traiettoria GPS grezza composta dai punti A e B ha un tempo di viaggio di 78 secondi. Una volta abbinati A e B ai corrispondenti seg-menti stradali, e ottenendo partenza e destinazione del cammino, ci sono due opzioni: il cammino più corto è anche il più veloce con un tempo di viaggio di 60 secondi. Un cam-mino alternativo, chiamato Time-Aware, sarebbe più ragionevole da selezionare perché avrenbbe tempo di viaggio più simile (72 secondi) al tempo impiegato nella traiettoria grezza.

L’algoritmo utilizzato: matching to-segment L’algoritmo matching

point-to-segment, che descriviamo in questa sezione, è quello proposto in [13].

La prima fase dell’algoritmo di Map-matching utilizzato considera ogni punto sepa-ratamente, facendo il matching con un segmento della rete stradale:

DEFINIZIONE: matching point-to-segment Data una traiettoria GPS T =

Èp1, t1Í...Èpn, tnÍ e una rete stradale N = (V, E) con insieme di vertici V e un insieme

di archi E, si definisce matching-point-to-segment(pi) la coppia Èsk, tÕkÍ, con sk calcolata

dall’algoritmo matching-point-to-segment, tÕ

k ottenuta dalla funzione Timecost.

DEFINIZIONE: Projected trajectory, traiettoria proiettata Data una

tra-iettoria GPS T = Èp1, t1Í...Èpn, tnÍ e una rete stradale N = (V, E) con insieme di vertici

V e un insieme di archi E, si definisce la traiettoria proiettata, o projected trajectory, di T, P T (T ) la sequenza

P T = Ès1, tÕ1Í...Èsm, tÕmÍ con Èsi, tÕiÍ œ {matching-point-to-segment(pi)|1 Æ i Æ n} .

Il principale argomento del matching point-to-segment è rappresentato dall’errore di localizzazione di ciascun punto; tale errore è variabile, da pochi metri a decine di metri, in funzione delle condizioni meteo e di visibilità dei satelliti. Nel dataset analizzato nel lavoro in [13], l’errore varia in funzione di diversi fattori; ad esempio, nel centro della città, la presenza di grossi fabbricati modifica la precisione della localizzazione. Un effet-to collaterale del matching point-effet-to-segment è che, dove disponibile, ogni informazione contestuale associata a ciascun punto può essere trasferita ai corrispondenti segmenti di strada, quindi arricchendo la conoscenza di background esistente sulla rete stradale.

L’applicazione di base utilizzata trae vantaggio dalla velocità istantanea dei veicoli, as-sociata a ciascun punto GPS, per stimare velocità reali e quindi tempi di viaggio sui segmenti di strada. E’ stato anche applicato il modello di gravità, proposto in [19], sia per il matching point-to-segment per ciascuna traiettoria, sia per stimare i tempi di viaggio per ciascun segmento della rete stradale. Per velocizzare i calcoli, i segmenti candidati sono i k segmenti più vicini per p. I risultati in [19] mostrano che k = 8 è un buon compromesso.

Euristica della ricostruzione dei cammini. I metodi allo stato dell’arte per

Map-matching sui dati a basso campionamento si basano sull’assunzione del cammino minimo: il cammino più verosimile fra due punti consecutivi abbinati è sempre quello più corto. Ciò chiaramente proviene da varie assunzioni, quali il fatto che il viaggio eseguito ha l’unico obiettivo di raggiungere la destinazione, e l’assunzione che il guidatore sappia realmente quale sia il cammino più efficiente. Questo algoritmo mira ad un’euristica più realistica. Utilizzando i risultati in [19], ogni segmento di strada è associato con il suo tempo di viaggio stimato, con un errore del 10,4%. Si fa leva su questa informazione per costruire un’euristica Time-Aware che associa ogni coppia di punti ad un tempo di viaggio. Il problema di trovare un insieme di segmenti stradali il cui tempo di viaggio si avvicina al tempo di viaggio di due punti GPS ricorda il problema dello zaino, che è NP-hard e risolubile con un approccio di programmazione lineare. Ancora, in questo caso ci sono vincoli e requisiti addizionali. Innanzitutto, i segmenti di strada scelti de-vono essere connessi l’un l’altro, per formare un cammino nella rete stradale. Inoltre, il requisito di compatibilità del tempo di viaggio da solo potrebbe non essere sufficiente per ottenere una ricostruzione ragionevole di cammini. Per esempio se il cammino reale è più lento di quanto atteso (rispetto ai tempi stimati di viaggio sui segmenti) utilizzare solo la differenza del tempo di viaggio come criterio di ottimizzazione potrebbe portare a risultati casuali: per poter raggiungere l’ottimo, segmenti sbagliati potrebbero essere aggiunti solo per creare deviazioni artificiali che accrescono i tempi di viaggio globali, per meglio adattarli a quelli reali. Per tener conto di tali comportamenti estremi, così come per fornire soluzioni computazionalmente sostenibili, è stata proposta un’euristica basata su un approccio di routing: infatti gli algoritmi di routing tengono implicitamente conto della topologia della rete stradale, e la loro complessità è più bassa di quella degli approcci della programmazione lineare. il metodo proposto in [13] è basato

sull’algorit-mo dei cammini minimi di Dijkstra, utilizzando un’euristica Time-Aware per valutare il costo di ogni segmento di strada in accordo a quanto esso si approssima al tempo di viaggio reale della traiettoria. Il cuore del nostro approccio è l’introduzione di una fun-zione Time-cost . Dati un nodo sorgente e un nodo target, l’algoritmi di Dijkstra utilizza Time-cost per valutare il costo di ogni segmento esaminato per trovare il cammino mini-mo. Quindi otteniamo un cammino che è il più corto in termini di Time-cost . Possiamo definire la soluzione che abbiamo trovato come un cammino con due vincoli: l’aciclicità e la velocità lineare con la più alta similarità rispetto alla velocità lineare reale. L’aciclità nella soluzione è garantita dall’algoritmo di Dijkstra, mentre la velocità lineare reale è il risultato della minimizzazione dell’algoritmo Time-cost .

In altre parole la soluzione trovata è il cammino con il tempo di viaggio più simile rispetto al tempo di viaggio GPS reale, in accordo ai vincoli di rete e di velocità. Nel seguito vengono descritti i dettagli su come Time-cost è calcolata e viene dimostrato come la scelta del cammino meno costoso in accordo con Time-cost trova una soluzione per il problema che abbiamo affrontato, soddisfacendo anche i vincoli che abbiamo introdotto. Viene dimostrato che la minimizzazione di Time-cost produce il cammino più simile nella rete stradale, in accordo alla velocità lineare GPS reale. Come risultato, il tempo di viaggio del cammino approssimerà il tempo di viaggio reale, pur rispettando i vincoli di rete.

L’algoritmo Dijkstra Time-Aware per ciascun arco analizzato viene calcolato timeleft come la differenza tra il tempo di viaggio del cammino fino al nodo padre e il tempo di viaggio reale. Questo consente di costruire una soluzione che meglio approssima la velocità lineare reale a ciascun percorso, o path. Un caso di particolare interesse sorge quando timeleft è minore di 0, cioè il caso in cui l’auto sta viaggiando a una velocità più alta della velocità usuale degli archi della rete stradale. In questa situazione l’algo-ritmo usa la velocità lineare globale come velocità lineare obiettivo per approssimare il cammino rimanente, questo soddisfa anche i vincoli della soluzione che cerchiamo. Più formalmente, se timeleft è minore di 0, Time-cost per l’arco è calcolato usando la linea retta dal nodo correntemente esaminato e il tempo rimanente per valutare la velocità lineare diretta corrente. Altrimenti, viene utilizzata la velocità sorgente-destinazione lineare diretta.

Dettagli di implementazione L’algoritmo Map-matching Time-Aware è basato

sul-l’algoritmo dei cammini minimi di Dijkstra. E’ stato scelto questo algoritmo al posto di altre opzioni più veloci per alcune importanti proprietà. L’algoritmo A* è un algoritmo euristico per trovare il cammino minimo: grazie all’approccio euristico l’algoritmo può limitare il numero di nodi visitati, ottenendo così una complessità più bassa rispetto a quello di Dijkstra O(E). Tuttavia, per essere ottimale, A* richiede una funzione euristica che non sovrastimi la distanza dal nodo target. Questo rende impossibile l’uso dell’algo-ritmo A* con l’approccio Time-Aware. In altre parole Time-cost è già una stima ed essa cambia anche in funzione delle caratteristiche della rete stradale: per utilizzarla come funzione euristica per A* dovremmo essere in grado di stimare, in termini di Time-cost , la distanza tra due nodi. Per definizione di Time-cost , questo valore cambia in funzione di alcuni parametri reali quali la velocità lineare dell’auto. Poi, nel nostro scenario Time-Aware l’algoritmo di Dijkstra assicura risultati affidabili, poichè non essendo dipendente da alcuna euristica, restituisce il cammino minimo dopo aver visitato tutti i nodi. Un altro dettaglio particolare è relato al task point-matching. Come spiegato, questo task è eseguito mediante un modello di gravità che restituisce il segmento più probabile per abbinare sulla mappa il punto GPS in input, senza alcuna indicazione riguardo il punto esatto del segmento di strada in cui il punto GPS dovrebbe ricadere. Poichè questa in-formazione è utile, noi utilizziamo l’approccio introdotto in [52]: Il punto GPS in input appartiene al punto più vicino del segmento di strada abbinato, permettendo quindi di creare un nuovo nodo nella rete stradale che connette il punto abbinato e il target del segmento abbinato, preservando tutte le caratteristiche del segmento abbinato. Natural-mente, il tempo di viaggio è modificabile in accordo alla nuova lunghezza del segmento. Questa procedura garantisce una stima ancora migliore di Timecost, risultando in un’ac-curatezza globale migliore per l’algoritmo Time-Aware. Per una migliore valutazione del lavoro, è stato sviluppato un plug-in QGIS basato sull’algoritmo Time-Aware. Il plug-in permette di abbinare un layer delle traiettorie al layer della rete stradale, ottenendo i dati map matchati relati alle traiettorie in input.

2.3 Trajectory Data Mining

Alla fase di preprocessing segue la fase di mining, per estrarre conoscenza dalle infor-mazioni sugli oggetti in movimento. Seguendo la caratterizzazione di [1], i metodi di

mining possono essere divisi in due categorie: metodi primari e metodi secondari. Dato un dataset di traiettorie, i metodi primari mirano a categorizzare le traiettorie in base alle loro proprietà; invece i metodi secondari di mining sono metodi composti, nel senso che consistono di una sequenza di metodi primari di mining o di metodi statistici classici o di una combinazione dei due.

2.3.1 Metodi primari di mining.

I metodi primari di mining sono usati per categorizzare le traiettorie in base alle loro proprietà. L’applicazione dei metodi primari di mining, seguita dall’interpretazione dei risultati può essere intesa per la sola analisi dei dati oppure per il preprocessing dei dati. I metodi primari di mining includono:

- clustering di traiettorie;

- la classificazione delle traiettorie.

Clustering.

Il trajectory data clustering (clustering di dati di traiettorie) ha l’obiettivo di descrivere il dataset raggruppando le traiettorie in insiemi finiti di categorie, anche chiamati cluster, basati sulle loro caratteristiche di movimento. Le traiettorie dello stesso cluster mostrano caratteristiche di movimento simili tra loro ma differenti rispetto alle traiettorie di altri cluster. Sono stati sviluppati approcci di clustering specifici per le traiettorie soprattutto adattando modelli statistici e probabilistici che tengono in conto le caratteristiche delle traiettorie. Per esempio, gli approcci di clustering basati su modelli misti proposti da Gaffney e Smyth [3] raggruppano insieme traiettorie che sono verosimilmente generate da una traiettoria comune con l’aggiunta di rumore Gaussiano. Sulla stessa linea, Alon e altri[4] modellano le traiettorie come sequenze di transizioni attraverso le posizioni e usa un Hidden Markov Model (HMM) che meglio si adatta alle traiettorie per modellare un cluster. Anche se esistono approcci di clustering specifici per le traiettorie, gli algoritmi di clustering per le traiettorie allo stato attuale sono estensioni di tradizionali algoritmi di clustering attraverso una definizione adeguata di funzione di similarità o di distanza. Uno studio degli attuali algoritmi di clustering può essere trovato in [5]. A seconda dell’obiettivo dell’analisi, alcune funzioni di similarità o di distanza quali rotte simili,

destinazioni simili, punti di partenza simili o direzioni simili, sono usate per determinare quali traiettorie appartengono allo stesso cluster. Una discussione dettagliata di come le funzioni di distanza e di similarità sono applicate per determinare l’appartenenza a un cluster può essere trovata in Rokach [6]. Tra gli algoritmi che sono stati estesi, possiamo menzionare i due più noti: il DBSCAN (Density Based Clustering of Applications with Noise) [7] e OPTICS (Ordering Points To Identify the Clustering Structure)[9]. Inoltre, è stato sviluppato T-OPTICS [12] che è un algoritmo che estende OPTICS definendo una distanza spazio-temporale per il confronto e il clustering di traiettorie, mentre ST-DBSCAN (Statial-Temporal ST-DBSCAN) [14] usa due parametri per misurare la similarità al fine di migliorare l’identificazione dei cluster e del rumore.

Classificazione.

L’obiettivo della classificazione è quello di trovare le regole per assegnare gli oggetti in classi precedentemente definite. La conoscenza sull’assegnamento delle classi è disponi-bile nella forma di un insieme di classi predefinite e un insieme campione (training set) di oggetti già etichettati con la classe a cui appartengono. In analogia alla classificazio-ne usuale, la classificazioclassificazio-ne di traiettorie ha l’obiettivo di determinare l’etichetta della classe delle traiettorie da un insieme predefinito di etichette in base alle caratteristiche delle traiettorie. Per esempio, la classificazione delle traiettorie può avere lo scopo di etichettare ogni traiettoria da un grande insieme con le modalità di trasporto, a partire da un piccolo insieme di traiettorie etichettate manualmente con la modalità di trasporto utilizzata. I metodi che seguono sono stati comunemente applicati nella classificazione delle traiettorie. Un algoritmo di classificazione basato sull’albero decisionale è stato usato da Zheng ed altri [15] per classificare le traiettorie a seconda di diverse modalità di trasporto. Prima vengono divise le traiettorie in segmenti ed estratte le caratteristiche discriminatorie quali velocità media di un segmento, tasso di cambiamento di direzione, tasso di cambiamento di velocità; successivamente queste caratteristiche sono date in input a un modello di inferenza per la classificazione basato su un albero decisionale. Le Support Vector Machines (SVMs) sono state usate da Bolbol ad altri [16] per risolvere lo stesso problema di classificazione delle traiettorie sulla modalità di trasporto. At-traverso una valutazione statistica, viene analizzato il potere discriminatorio di quattro caratteristiche (velocità, accelerazione, distanza e tasso di cambiamento di direzione) su

6 modalità di trasporto (bus, auto, bicicletta, treno, metropolitana e cammino). Dopo aver identificato la velocità e l’accelerazione come migliori caratteristiche discriminatorie, essi hanno applicato l’algoritmo SVM su queste caratteristiche per studiare le istanze di uguale misura di vari segmenti di traiettorie per classificarle. In molte di queste applica-zioni, la classificazione di traiettorie viene eseguita dopo altre operazioni di analisi quali segmentazione e clustering, che preparano le caratteristiche sulle quali la classificazione sarà basata. Per esempio, il TraClass framework [17] applica la segmentazione e cluste-ring di traiettorie per estrarre le caratteristiche delle regioni e delle sotto-traiettorie che sono poi usate per una SVM basata sulla classificazione delle traiettorie.

2.3.2 Metodi secondari di mining.

Mentre i metodi primari di mining hanno lo scopo di categorizzare le traiettorie, i metodi secondari di mining generalmente hanno lo scopo di analizzare l’organizzazione spaziale, temporale, o spazio-temporale delle traiettorie individuali, in una categoria o tra le ca-tegorie. Esistono molti metodi secondari di mining; in questa sezione verranno discusse le tecniche:

- Pattern mining; - Outlier detection; - Predizione.

Pattern mining.

Il Trajectory Pattern Mining ha lo scopo di scoprire e descrivere i pattern di movimento nascosti nelle traiettorie. Questo fornisce informazioni su dove e quando sono il pattern ricorre, e sulle entità coinvolte. Un gran numero di tipi di pattern di movimento sono stati riportati nella letteratura. Una vista integrata può essere trovata nel lavoro [18]

Se si considera ogni traiettoria come una sequenza, un pattern sequenziale è spesso definito come una sottosequenza in cui almeno n sequenze condividono la sottosequenza, dove n è una soglia definita dall’utente.

I metodi possono essere suddivisi in 3 categorie: Repetitive pattern mining, Frequent pattern mining e Group pattern mining.

Il Repetitive pattern mining si applica alle traiettorie di un singolo oggetto in mo-vimento, mentre il frequent pattern mining si applica alle traiettorie di più oggetti in movimento, ma in un tempo relativo; cioè, gli oggetti possono non muoversi contempora-neamente e la sola condizione è che essi visitino approssimativamente gli stessi posti nella stessa sequenza. Analogamente al frequent pattern mining, il group pattern mining si applica a traiettorie di più oggetti ma il movimento è considerato in un tempo assoluto; cioè gli oggetti si muovono contemporaneamente.

- Il Repetitive pattern mining riguarda pattern di movimento regolari, qua-li il movimento di una navetta, che è ripetuta ogni giorno, o il movimento di un uccello migratore, che è ripetuto ogni stagione. Un pattern ripetitivo è anche chiamato pattern periodico poiché l’oggetto segue approssimativamente lo stesso percorso dopo un periodo di tempo approssimativamente costante. La scoperta di pattern periodici è resa com-plesso dalla natura approssimata dei pattern in termini di spazio e tempo; cioè, l’oggetto non visita esattamente lo stesso punto in corrispondenza di un dato istante del periodo e il periodo non ha esattamente lo stesso valore in diversi cicli. Un approccio comune per scoprire pattern di movimento periodici è quello di applicare il mining su sequenze di locazioni. In uno studio recente, Cao ed altri [20] richiedono che il periodo sia specificato in input e le locazioni siano clusterizzate in corrispondenza allo stesso spiazzamento del periodo per scoprire regioni frequenti. Poi, iterativamente vengono combinate regioni frequenti scoperte per ottenere pattern periodici completi. Il lavoro presentato da Cao ed altri [20] ha esteso l’approccio presentato in uno studio precedente [21], ma entrambi gli studi richiedono che il periodo sia dato in input al processo di mining. L’algoritmo Periodica [22] supera il requisito di dover specificare il periodo in anticipo. Questo al-goritmo all’inizio trova automaticamente il periodo usando un approccio che combina la trasformata di Fourier e l’auto-correlazione. L’algoritmo trova i punti di riferimen-to (reference spots), che sono regioni dense che contengono più punti di traietriferimen-toria di altre, e individua i periodi differenti in ognuna di queste. Successivamente l’algoritmo poi trova i pattern periodici da sequenze di movimento tra punti di riferimento con lo stesso periodo usando un clustering gerarchico per il quale la misura di distanza si basa su un modello probabilistico. Rispetto alla gran parte dei lavori correlati, l’algoritmo Periodica presenta due caratteristiche importanti: l’individuazione automatica di periodi e la considerazione di diversi periodi durante la scoperta di pattern periodici.

- Il Frequent pattern mining si occupa dell’estrazione di rotte o parti di rotte che sono state frequentemente seguite da oggetti in movimento nel dataset delle traiettorie. Pattern frequenti di traiettorie possono essere definiti usando caratteristiche spaziali o spazio-temporali delle traiettorie [23]. La definizione basata su caratteristiche spaziali considera solo la sequenza delle locazioni visitate. I pattern frequenti sequenziali spazio-temporali [24] e i pattern sequenziali generalizzati [25] sono esempi di questa casi-stica. La definizione basata su caratteristiche spazio-temporali considera sia la sequenza delle locazioni visitate che il tempo di transizione tra le locazioni. I T-Patterns (Tra-jectory Patterns) [26] sono un esempio di questo secondo caso. Un T-Pattern è definito come un insieme di traiettorie che condivide la proprietà di visitare la stessa sequenza di posti con tempi di viaggio simili. In [26] sono stati sviluppati due approcci per estrarre T-Pattern; il primo approccio implica una discretizzazione dello spazio per identificare le regioni di interesse. Successivamente il passo effettivo di mining individua le sequenze di regioni di interesse con annotazioni temporali. Il secondo approccio deriva dinami-camente le regioni di interesse dai segmenti di traiettorie e poi traduce le traiettorie in una sequenza di regioni da cui costruisce iterativamente i T-Pattern. I T-Pattern sono un’evoluzione dei TAS (Temporally Annotated Sequences) introdotti in [27]. La figura 2.4 mostra tre tipi di sequenze che rendono diversi i pattern frequenti:

pattern sequenziali spazio-temporali (a), si considera solo la sequenza di locazioni men-tre per T-Pattern (c) viene considerato anche il tempo di transizione tra le locazioni (ad esempio, dalla locazione a alla locazione b occorrono tra i 10 e i 12 minuti). I T-Pattern (c) combinano la caratteristica di sequenza di locazione da pattern spazio-temporali se-quenziali (a) con la caratteristica del tempo di transizione da TAS (b).

- Il Group pattern mining mira a estrarre pattern di movimento che coinvol-gono gruppi di oggetti che si muovono insieme. Una condizione generale è che gli oggetti che formano un gruppo siano vicini nello spazio per un periodo considerevole di tempo. Vari group pattern e loro varianti sono stati definiti in base alla condizione generale di vicinanza spazio-temporale, in base alla struttura interna del gruppo e alle caratteristiche dei membri del gruppo. I pattern più studiati sono flocks [29] [32], convoy[33] e swarm [34], mostrati in figura 2.5.

Figura 2.4: Tre tipi di sequenze che rendono diversi i pattern frequenti: pattern sequen-ziali spazio-temporali (a), si considera solo la sequenza di locazioni mentre per T-Pattern (c) viene considerato anche il tempo di transizione tra le locazioni (ad esempio, dalla lo-cazione a alla lolo-cazione b occorrono tra i 10 e i 12 minuti). I T-Pattern (c) combinano la caratteristica di sequenza di locazione da pattern spazio-temporali sequenziali (a) con la caratteristica del tempo di transizione da TAS (b).

k timestamp consecutivi tale che a ciascuno di questi timestamp si trovano all’interno di

un cerchio di raggio r. Il pattern è definito dai 3 parametri: r, m, k.

Il pattern convoy rilassa il vincolo di forma circolare, usato per i pattern flock, per rappresentare un gruppo di oggetti in movimento che formano qualsiasi forma. E’ un gruppo di almeno m oggetti che viaggiano insieme per almeno k timestamp consecutivi tale che in ciascuno di questi timestamp il gruppo può essere trovato utilizzando un clustering basato sulla densità con parametri d come distanza di vicinanza ed m come numero minimo di oggetti.

Il pattern swarm è un’estensione del pattern convoy che ulteriormente rilassa il vincolo di timestamp consecutivi; è definito dagli stessi parametri del pattern convoy eccetto che in uno swarm k è il numero minimo di timestamp in cui il gruppo è trovato senza tener conto che i timestamp siano consecutivi oppure no. Per esempio, con m = 4 e k = 2 il pattern di figura 3.c) non è un convoy poiché solo tre oggetti (O1, O2 e O3) sono trovati nel gruppo per almeno due timestamp consecutivi. Tuttavia, questo pattern è uno swarm perché ai due timestamp (t1 e t3) il gruppo include il minimo richiesto di 4 oggetti e il

pattern swarm non richiede che i timestamp siano consecutivi. I comuni approcci di mining di group pattern coinvolgono i metodi di clustering e il controllo delle condizioni sui parametri che definiscono il pattern come il minimo numero di membri dei gruppi e la durata minima del pattern. Per esempio, in [35] viene applicato il density-based clustering per trovare i flock, in [36] e [33] per trovare i convoy, e in [37] [38] per trovare i swarm.

Outlier detection.

L’obiettivo dell’outlier detection è trovare le traiettorie che non si attengono completa-mente al comportamento generale del dataset di traiettorie. Mentre il pattern mining si focalizza sui pattern che sono comuni nel dataset di traiettorie, l’outlier detection si foca-lizza sui pattern rari, ad esempio che seguono un percorso differente dal percorso comune seguito dalla maggior parte delle traiettorie. Analogamente alla classificazione di traiet-torie, l’outlier detection di traiettorie può essere eseguita estraendo o traiettorie intere o parti di traiettorie. Il lavoro presentato in [39] è un esempio di outlier detection applica-to su traietapplica-torie intere, mentre esempi di outlier detection applicati a sotapplica-to-traietapplica-torie si possono trovare in [40], [41] e [42]. Per l’outlier detection applicato a parti di traiettorie,

ogni traiettoria è prima divisa in sotto-traiettorie e poi sono applicate alcune funzioni di distanza o metodi di clustering per identificare le sotto-traiettorie outliers. Infine le tra-iettorie alle quali appartengono le sotto-tratra-iettorie outlier sono identificate come outliers. Questo approccio è stato seguito nell’algoritmo TRAOD [40]. Molti approcci di outlier detection nella letteratura utilizzano algoritmi di clustering e identificano come outlier quegli oggetti che non sono racchiusi in nessun cluster. Quindi, il problema principale è quello di trovare la misura di distanza appropriata per discriminare queste traietto-rie anomale. Un approccio base per trovare gli outlier delle traiettotraietto-rie analizza i vicini di ogni traiettoria contando il numero dei vicini o utlizzando un metodo di clustering density-based. In questo approccio, le traiettorie che hanno troppo pochi vicini sono ca-tegorizzate come outliers. Nell’ambito dell’outlier detection, iBat[39] segue una variante estesa di questo approccio. In iBat, l’area di studio è partizionata in una struttura a griglia e le traiettorie che attraversano la stessa coppia di celle origine-destinazione so-no raggruppate. Infine, l’approccio usa un meccanismo di isolamento che identifica le traiettorie outlier sfruttando la proprietà che esse sono poche e diverse nei loro grup-pi. Un’altra categoria di approccio all’outlier detection di traiettorie segue le procedure utilizzate nei metodi di classificazione. Per esempiosi possono estrarre caratteristiche predefinite dalle traiettorie e poi applicare una misura di distanza standard ai vettori estratti. In questo approccio, seguito in [42], la misura di distanza è stata applicata a quattro caratteristiche (direzione, velocità, angolo e locazione) per scoprire le traiettorie outlier. Alternativamente, le traiettorie outlier possono essere scoperte con un modello di classificazione con un training set con due etichette, in cui una etichetta corrisponde alle traiettorie normali mentre l’altra corrisponde alle traiettorie anormali in base alle caratteristiche considerate. Questo approccio è seguito in [43].

Predizione.

La predizione che usa i dati delle traiettorie, mira principalmente ad estrarre la locazione futura di un oggetto in movimento basandosi su traiettorie esistenti. Questa è stata motivata specialmente dalla veloce crescita dei servizi basati sulla localizzazione, una delle maggiori aree di applicazione in [44]. L’obiettivo di molti degli studi di predizione basata su traiettorie è di predire una locazione (destinazione o locazione successiva); ma ci sono molti studi il cui scopo è predire l’intera rotta basata sulla rete stradale. La

Capitolo 3

Mobility user profiles da traiettorie

proiettate.

In questo capitolo viene presentata una metodologia per l’analisi di mobilità che mira in particolare a riconoscere utenti in base al loro comportamento individuale di mobili-tà. La metodologia presentata lavora su traiettorie proiettate, vale a dire su traiettorie espresse in termini di segmenti di strada e timestamp, che potrebbero essere state otte-nute a partire da traiettorie GPS, a valle di elaborazioni di Map-matching che ne hanno trasformato la rappresentazione con riferimenti alla rete stradale.

Il Mobility data Mining [8] è un campo recente di ricerca ed esistono già molti lavori che perseguono obiettivi comuni. Una parte di ricerca vicina può essere trovata nella letteratura sul mobility clustering che mira a trovare insiemi di traiettorie simili. L’ap-proccio standard adatta algoritmi basati su distanza classici e definisce distanze ad hoc per dati di traiettorie [57], eventualmente con limitati raffinamenti ad hoc [58]. Rispetto alle soluzioni esistenti, nella metodologia proposta in [28] la valutazione di similarità tra individui non è realizzata come un confronto diretto di traiettorie. Invece, viene eseguita un’analisi in due fasi, che prima trova i comportamenti tipici per ogni singolo utente (tipicamente un’attività di clustering di traiettorie), e poi confronta coppie di utenti at-traverso un confronto tra i corrispondenti insiemi di comportamenti. I risultati di [28] vengono rivisti per considerare traiettorie proiettate.

Figura 3.1: Processo di estrazione dei profili: a) suddivisione della user history in trip; b) identificazione dei trip group,; c) selezione dei profili rappresentativi

3.1 Definizioni per il mobility profile.

La mobilità giornaliera di ogni utente può essere essenzialmente sintetizzata come l’insie-me dei singoli viaggi che l’utente percorre durante il giorno. Quando si cerca di estrarre un profili di mobilità di utenti, l’interesse è nei viaggi che sono parte delle loro abitudini, perciò trascurando variazioni occasionali che divergono dal loro comportamento tipico. Pertanto, per identificare i profili di mobilità individuali di utenti dalle tracce GPS sa-ranno seguiti i seguenti passi, vedi figura 3.1:

1. dividere l’intera storia dei viaggi dell’utente (user history) in trip (figura 3.1 a)). 2. raggruppare i trip simili in trip group, scartando gli outlier (figura 3.1 b)).

3. da ogni trip group, estrarre un insieme di trip rappresentativi, da utilizzare come profili di mobilità (figura 3.1 c)).

3.1.1 User history

. La user history è definita come una sequenza ordinata di punti spazio-temporali

H = Èp1...pnÍ dove pi = (x, y, t), con x, y coordinate spaziali e t il timestamp

La user history contiene differenti traiettorie, o trip, effettuate dall’utente. Per distin-guerle, abbiamo bisogno di definire gli Stay Point, ovvero i punti di sosta che determinano la fine di un trip e l’inizio del trip successivo. In letteratura ci sono due principali ap-procci: clustering based [30] ed heuristic-based [31]. In [28] viene utilizzato il secondo, per scopi di efficienza. Quindi cerchiamo punti che cambiano solo nel tempo, cioè che mantengono la stessa posizione spaziale per un certo tempo, determinato da una soglia temporale thstop

temporal. Specularmente, una soglia spaziale th stop

spatial viene utilizzata per

ri-muovere sia il rumore introdotto dall’imprecisione della device sia i piccoli movimenti che non sono di interesse per una particolare analisi.

3.1.2 Stay Point

Data una user history H e le soglie thstop

temporal e th stop

spatial, uno Stay Point, o stop potenziale,

è definito come una sotto-sequenza massimale S della user history H avente i punti all’interno di un’area spaziale entro un certo periodo di tempo:

S = Èpm...pk_{Í|0 < m Æ k Æ n · ’}mÆiÆkDist(pm, pi) Æ thstopspatial· Dur(pm, pk) Ø th stop temporal.

dove Dist è la funzione di distanza Euclidea definita tra le coordinate spaziali tra i punti, e Dur è la differenza nelle coordinate temporali dei punti. I potenziali stop possono sovrapporsi l’un l’altro (tuttavia, nessuno di essi può contenere completamente l’altro, per la condizione di massimalità), rendendo difficile il loro uso come base per ulteriori analisi.

Per poter evitare ciò, un criterio di selezione precoce è adottato per rimuovere qual-siasi sovrapposizione.

3.1.3 Stop Reale

Data una sequenza di stop potenziali Sset = ÈS1, ..., SNÍ ordinata per tempo di inizio (i.e., S _{Æ S}Õ _{… S = È(x, y, t), ...Í · S}Õ = È(xÕ_{, y}Õ_{, t}Õ), ...Í · t Æ tÕ ) la sequenza corrispondente di

stop reali ActS è definita come la sequenza minima di stop potenziali tali che: 1. S1 œ ActS

2. se Si œ ActS · k = min{j|j > i · SjuSj = ÿ} < Œ ∆ Skœ ActS

Indichiamo con S = ÈS1...StÍ l’insieme di tutti gli stop reali su H. Una volta che

3.1.4 Trip

Un trip è definito come la sotto-sequenza T della user history H tra due stop reali con-secutivi nell’insieme ordinato S e il primo/ultimo punto di H (i.e., p1 o pn):

- T = Èpm, ..., pkÍ|0 < m Æ k Æ n · ÷i(Si = È..., pmÍ · Si+1 = Èpk, ...Í), o

- T = Èp1, ..., pmÍ|0 < m Æ n · ÷i(Si = Èpm, ...Í), o

- T = Èpk, ..., pnÍ|0 < k Æ n · ÷i(Si = È..., pkÍ).

L’insieme di trip estratti T = ÈT1...TcÍ sono i passi di base per creare l’user mobility

profile. Si noti che le soglie thstop

spatial e th stop

temporal sono le manopole per sintonizzare i

requisiti analitici specifici.

3.1.5 Trip Group

Il nostro obiettivo è di utilizzare un insieme di trip di un utente individuale per trovare i suoi comportamenti di routine. Per fare ciò raggruppiamo insieme trip simili basati suoi concetti di distanza spaziale ” e allineamento temporale –, con soglie s e t corrispondenti per entrambi le componenti spaziali e temporali dei trip. Per poter essere definita come routine, un comportamento ha bisogno di essere supportato da un numero significativo di trip simili min. Le suddette idee sono formalizzate come segue:

Dati un insieme di trip T , una soglia spaziale s, un allineamento temporale t, una funzione di distanza spaziale ” : T2 æ R, un vincolo di allineamento temporale – :

T2_{◊ R æ B tra coppie di trip, e una soglia supporto minimo di trip min,}

un trip group per T è definito come il sottinsieme di trip g ™ T tale che: 1. ’t1, t2 œ g : ”(t1, t2) Æ s · –(t1, t2, t);

2. |g| Ø min

La condizione 1 richiede che i trip in un gruppo siano approssimativamente localizzati nello stesso spazio e nello stesso tempo;

Le soglie s, t e min sono le manopole utilizzate dall’analista per regolare il processo di estrazione dei dati.

3.1.6 Mobility profile

Ogni gruppo ottenuto nel precedente passo rappresenta l’abitudine di mobilità tipica di un utente, i.e., uno dei suoi movimenti di routine. Qui sommarizziamo l’intero gruppo scegliendo l’elemento centrale di un gruppo.

DEFINIZIONE: Routine

Ogni gruppo ottenuto dai passi precedenti corrisponde a un comportamento abitudinario dell’utente. Per essere definito routine, un comportamento deve essere supportato da un numero significativo di trip. Il passo successivo sarà quello di estrarre una routine per ogni trip group, che sintetizza il comportamento dell’intero gruppo.

Dato un trip group g e la funzione di distanza ” utilizzata per calcolarlo, la sua rou-tine è definita dalla funzione:

routine(g, ”) = arg mintœgqtÕ_œg\{t}”(t, tÕ)

Si noti che l’allineamento temporale è sempre soddisfatto su ogni coppia di trip in un gruppo, perciò la relazione di allineamento temporale – non appare nella definizione. Ora siamo pronti per definire lo user mobility profile.

DEFINIZIONE: Mobility profile

Dato un insieme di trip group G di un utente e una funzione di distanza ” usata per calcolarli, il profilo di mobilità di un utente è definito come il suo corrispondente insieme di routine:

3.2 Costruzione del mobility profile

L’intera estrazione di un profilo di mobilità - dalla storia utente iniziale ai profili di mobilità finali - è sommarizzato nell’algoritmo 1. La definizione fornita nella precedente sezione è stata mantenuta generica rispetto alla funzione di distanza ”. Differenti scelte possono soddisfare differenti bisogni, sia concettualmente (quali criteri definiscono un buon assegnamento gruppo/routine) che praticamente (per esempio, criteri più semplici potrebbero essere preferiti per salvare la scalabilità). Ovviamente, i risultati ottenuti da differenti istanziazioni possono variare molto. Quindi rispetto all’algoritmo 1 il punto cruciale è la procedura SelectGroups. La nostra proposta è di usare un metodo di clustering per compiere questo task.

Algorithm 1 Costruzione di un mobility profile

INPUT

Osservazioni utente D

Funzione di distanza spaziale ”

Relazione di allineamento temporale –

Soglie per gli stop potenziali thstop_spatial, thstop_temporal

Soglie per i trip group s, t

Numero minimo di trip per gruppo min

OUTPUT = Mobility profile di un utente P

Procedimento

1: H = OrderByT ime(D);

2: T = BuildT rips(H, thstop_spatial, thstop_temporal); 3: C= SelectGroups(T , ”, –, s, t, min); 4: P = ÿ

5: for each g œ C do 6: if size(g) > s

7: then P = P fi routine(g, ”)

La funzione OrderByT ime(D) restituisce la user history H dell’utente, a partire dal-le osservazioni dei suoi comportamenti di mobilità D.

La funzione BuildT rips(H, thstop spatial, th

stop

temporal) prende in input la user history

dell’u-tente H, le soglie spaziali e temporali thstop spatial, th

stop

temporale per dividere la user history in

trip, e restituisce l’insieme dei trip dell’utente.

La funzione SelectGroups(T , ”, –, s, t, min) prende in input l’insieme delle sue traiet-torie, le funzioni di distanza spaziale e allineamento temporale ” e – e le rispettive soglie

s e t, e restituisce l’insieme dei trip group dell’utente.

La funzione routine(g, ”), introdotta nella sezione precedente, estrae da ogni trip group g œ C la traiettoria che ha la minima somma di distanza da tutte le altre traiet-torie del trip group.

Nelle sezioni successive sono presentati: - la funzione di distanza ” tra due traiettorie. - l’algoritmo di clustering SelectGroups.

3.3 Scelta della funzione di distanza: Edit Distance

La funzione di distanza ” scelta per misurare la similarità tra trip è la Edit Distance. La Edit Distance, o distanza di Levenshtein1 _{è una misura che serve a misurare quanto due}

stringhe siano simili. Questa funzione viene utilizzata per il controllo ortografico e per la ricerca di similarità tra immagini, suoni e testi.

La Edit Distance tra due stringhe A e B è data dal numero minimo di modifiche ele-mentari necessarie per trasformare la stringa da A a B. Le modifiche eleele-mentari previste sono:

-cancellazione di un carattere,

-sostituzione di un carattere con un altro, -inserimento di un carattere.

Ad esempio, per trasformare la stringa "bar" in "biro" occorrono due modifiche: "bar" ≠æ "bir" (sostituzione di ’a’ con ’i’)

"bir" ≠æ "biro" (inserimento di ’o’)

Quindi la Edit Distance tra le due stringhe è 2.

La Edit Distance tra due stringhe ha i seguenti limiti, superiore ed inferiore: - il limite superiore è dato dalla lunghezza della stringa più lunga.

- il limite inferiore è la differenza fra la lunghezza delle due stringhe Il valore della Edit Distance per due stringhe identiche è 0.

La Edit Distance è una distanza tra stringhe; nel caso specifico andremo ad applicare la Edit Distance a coppie di stringhe che rappresentano trip, dove un trip nel nostro caso è una traiettoria proiettata, definita nella sezione 2.2.5.

L’algoritmo usato comunemente per calcolare la Edit Distance di due stringhe str1 e str2 richiede l’uso di una matrice d di dimensione (n + 1) ◊ (m + 1), dove n e m rappresentano rispettivamente le lunghezze delle stringhe str1 e str2. L’Algoritmo 2 presenta la descrizione in pseudocodice della funzione per il calcolo della Edit Distance.

3.4

SelectGroups : Proposta dell’algoritmo di

Clu-stering per la creazione dei trip group

Bisogna costruire i gruppi di trip effettuando una clusterizzazione che pone nello stesso gruppo traiettorie che distano, secondo la distanza di Levenshtein, di un valore Æ s. Le condizione dell’algoritmo proposto, seguono la linea di quello proposto nella sezione 3.1.5 con la differenza che non è stato considerato il vincolo di allineamento temporale; la condizione 1 diventa:

1. ’t1,t2 œ g|EditDistance(t1, t2) Æ s

La condizione 2 resta invariata: 2. |g| Ø min.

Dati: T l’insieme di tutte le traiettorie di un dato utente, la funzione di distanza spa-ziale ”, la soglia spaspa-ziale s e un numero minimo di trip all’interno di un trip group min, per ogni coppia di traiettorie t1, t2 œ T con distanza minore della soglia, ”(t1, t2) Æ s, sia:

Algorithm 2 Calcolo di Edit Distance su due stringhe

INPUT

Stringa contenente la prima parola Str1 Stringa contenente la seconda parola Str2 lunghezza della prima parola lenStr1 lunghezza della seconda parola lenStr2

OUTPUT = Edit Distance tra le due stringhe date in input

Procedimento

1: for i1 from 0 to lenStr1 2: d[ i1, 0 ] := i1 3: for i2 from 0 to lenStr2 4: d[ i2, 0 ] := i2 5: for i1 from 0 to lenStr1 6: for i2 from 0 to lenStr2

7: if str1[ i1 - 1 ] = str2[ i2 - 1 ] then cost := 0 8: d[ i1, i2 ] := d[ i1-1, i2-1 ]

9: else cost := 1 10: d[ i1, i2 ] := minimum( 11: d[ i1 - 1, i2 ] + 1, // inserimento 12: d[ i1 , i2 - 1 ] + 1, // cancellazione 13: d[ i1 - 1, i2 - 1 ] + cost // sostituzione 14: )

Algorithm 3 Algoritmo di Clustering: creazione dei Trip Group

INPUT

Insieme di traiettorie proiettate (trip) T

Funzione di distanza spaziale ”

Soglia spaziale per i trip group s

Numero minimo di trip per group min

OUTPUT = Insieme dei trip group dell’utente C

Procedimento

T1 = {t œ T : ”(t1, t) Æ s}t{t1}

T1 l’insieme di tutte le traiettorie di T con distanza ”(t1, t) minore della soglia s, inclusa

la traiettoria t1

T2 = {t œ T : ”(t2, t) Æ s}t{t2}

T2 l’insieme di tutte le traiettorie di T con distanza ”(t2, t) minore della soglia s, inclusa

la traiettoria t2

Calcoliamo: g = {tA, tB œ (T1uT2) : ”(tA, tB) Æ s}

g l’insieme di tutte le traiettorie appartenenti sia a T1 che a T2, aventi tra loro una

distanza minore della soglia s

Se il numero delle traiettorie nell’insieme è minore di min, l’insieme generato è un trip group e lo aggiungo a C: l’insieme dei trip group.

Questo algoritmo genera un insieme C, che contiene trip group di dimensione Ø min, in cui ogni coppia di traiettorie ha una distanza ” minore della soglia s.

Capitolo 4

Ricerca delle variazioni ai profili.

Lo scopo dell’algoritmo proposto in questo capitolo è quello di trovare i segmenti di strada che deviano dal percorso frequente (sistematico) di un utente. Questi segmenti di strada appartengono a P , l’insieme dei percorsi sistematici dell’utente, ma non vengono percorse da trip che sono simili a questo percorso entro una soglia v.

Data una traiettoria t in input, questa viene confrontata con le routine all’interno dell’insieme profilo P e ne viene calcolata la distanza. Una traiettoria può essere: - una routine, se la traiettoria t è uguale a una routine all’interno di P .

- una variazione alla routine, se la distanza dalla routine più simile è minore della soglia v,

- una traiettoria anomala, se la distanza dalla routine più simile è maggiore della soglia v.

La soglia s è la distanza massima tra due traiettorie utilizzata nei passi precedenti per il calcolo dei trip group.

La soglia v è maggiore di s ed è la distanza oltre la quale la traiettoria è cosiddetta anomala.

Se la distanza tra la traiettoria e la routine rientra tra le soglie v e s allora il percorso della traiettoria contiene una variazione alla sua routine più simile.

Dopo aver determinato se una traiettoria è una variazione, viene estratto l’insieme dei segmenti della routine che non vengono percorsi, e che quindi sono considerati variazioni

del percorso sistematico.

Come per la soglia s, anche la scelta di v consente di sintonizzare la migliore perfor-mance per questo algoritmo, e la tipologia di risultati estratti.

4.1 Algoritmo per la costruzione dell’insieme delle

variazioni delle routine

Data una routine p e una traiettoria proiettata t, definiamo variazione var(p, t) l’insieme dei segmenti di strada percorsi dalla routine p e non da t.

var(p, t) = {sj|sj œ p·sj œ t}; la routine p scelta è quella più simile, cioè avente minima/

distanza dalla traiettoria t.

Il seguente algoritmo consente di costruire l’insieme dei segmenti che sono variazione alla routine.

Una volta trovate le variazioni alle routine di tutti gli utenti possiamo analizzarne la causa e l’eventuale regolarità. In base alla regolarità, la suddetta traiettoria può essere considerata una variazione periodica alla routine.

Algorithm 4 Algoritmo per la costruzione dell’insieme delle variazioni delle routine

INPUT

Insieme delle routine dell’utente P

Insieme dei traiettorie proiettate (trip) T

Soglia spaziale per determinare le variazioni v

OUTPUT = Insieme di segmenti di traiettorie proiettate che sono variazioni di

routine V ar

Procedimento

1: V ar= ÿ

2: for each t œ T

3: p= arg mint1œP”(t, t1)

4: // p è la routine in P avente distanza minima da t 5: 6: if ”(p, t) = 0 7: then t is a routine 8: else if ”(p, t) > v 9: then t is an outlier 10: else t is a variation 11: var(p, t) = {sj|sj œ p · sj œ t}/ 12: add var(p, t) to Var

Capitolo 5

Un caso di studio: il dataset Octo

Telematics

Il mobility dataset preso in esame raccoglie i dati relativi alle traiettorie effettuate da-gli utenti della compagnia Octo Telematics S.p.a.1_{, una compagnia privata che fornisce}

servizi per le compagnie assicurative. I dati a mia disposizione hanno già subìto un’e-laborazione preliminare e i punti GPS sono già stati trasformati in segmenti discreti della rete stradale, nella fase di preprocessing, in particolare la fase di map-matching ha provveduto a trasformare le traiettorie in traiettorie proiettate. Per ogni traiettoria noi abbiamo la sequenza di segmenti che la compongono, accompagnate dal timestamp.

5.1 Descrizione del DataSet

I dati raccolti ricoprono 5 settimane nell’arco temporale che va dal 1¶ maggio 2011 al

31 maggio 2011, relativi a 9088 veicoli. In particolare sono stati isolati tutti i dati in un quadrato geografico centrato sulla Toscana. Il dataset è composto di quattro tabelle: ways, ta_matched, traj2date e user2traj.

La tabella ways La tabella ways contiene il grafo stradale orientato; ogni segmento

fa riferimento ai dati geografici presenti all’interno di Open Street Map 2_.

OpenStreet-Map (OSM) è una mappa liberamente modificabile dell’intero pianeta. OpenStreetOpenStreet-Map

1_{http://www.octotelematics.com} 2_{info su openstreetmap.it}

Figura 5.1: Visualizzazione dei segmenti stradali contenuti nella tabella ways permette a chiunque sulla Terra di visualizzare, modificare ed utilizzare dati geografici con un approccio collaborativo.

Ogni tupla ha un id univoco che corrisponde a un segmento stradale che ha origine nel nodo indicato dalle coordinate x1, y1 e destinazione nel nodo indicato dalle coordinate x2, y2.

La tabella ways contiene 5.139.184 tuple, ognuna delle quali rappresenta un segmento all’interno della mappa stradale dell’Italia. E’ composta da 21 attributi; tra quelli più rilevanti abbiamo:

- id, che rappresenta un id univoco per ogni segmento stradale; - osm_id è l’id della via a cui si riferisce il segmento;

- osm_name è il nome della via a cui si riferisce il segmento; - x1 e y1, rappresentano le coordinate di origine del segmento; - x2 e y2, rappresentano le coordinate di destinazione del segmento; - km rappresenta la lunghezza in km del tratto stradale;

- geom_ways conserva la geometria del segmento, ovvero la forma della traiettoria;

Gli attributi con prefisso osm (OpenStreetMap) ci permettono di visualizzare il segmento stradale nella mappa attraverso il software Qgis3_.

3_{QGIS è un sistema informativo geografico desktop, open source e cross-platform free che offre}