UNIVERSITÀ DI PISA Dipartimento di Informatica Data Science and Business Informatics
TESI DI LAUREA
Identificazione di anomalie del traffico urbano e estrazione di patterns di correlazione (causa-effetto).
RELATORI
Prof. Roberto TRASARTI
CANDIDATO Antonio LOCONTE
Sommario
I dati di mobilità sono dati che incorporano il comportamento spazio-temporale dei singoli individui, molti lavori nel campo della mobilità impostano lo studio su un approccio locale a livello di individui, tuttavia allargando la prospettiva i dati di mobilità possono essere visti come il comportamento di un’area urbana.
Il seguente studio si pone di analizzare dati di mobilità derivanti da sensori montati su auto private, di identificare feature interessanti per lo studio del traffico urbano e l’identificazione di anomalie tramite tecniche di statistiche e/o outlier detection.
Il set di anomalie verrà poi utilizzato per l’identificazione di correlazioni spazio-temporali allo scopo di determinare correlazioni con l’obiettivo finale di generare candidati di causalità. La tesi si inquadra all’interno del progetto Track & Know (H2020 EU Project - GA No. 780754) come modulo per l’estrazione di pattern di
Indice
1 Introduzione 1
1.1 Presentazione del problema . . . 1
1.2 Rassegna della letteratura . . . 2
1.3 Contenuto della tesi . . . 3
2 Principi, processi e tecniche 5 2.1 Data Mining . . . 5
2.2 Processo del Knowledge Discovery in DataBase . . . 6
2.2.1 Step del KDD-process . . . 7
2.3 Tecniche: Data Mining Task . . . 8
3 Comprensione del dominio 11 3.1 Input di analisi . . . 12
3.1.1 Punti gps degli utenti . . . 12
3.1.2 Seeds delle Voronoi Cell . . . 14
3.1.3 Vicinato delle Voronoi Cell . . . 16
3.2 Output, classificazione, e processo dell’analisi . . . 16
3.3 Vincoli tecnologici . . . 17
4 Pulizia e selezione dei dati 19 4.1 Selezione dei dati . . . 19
4.2 Comprensione del grado di incertezza temporale . . . 21
4.3 Riduzione del rumore . . . 24
5 Dati di mobilità e costruzione feature 25 5.1 Stop Detection . . . 25
5.2 Enumerazione delle traiettorie . . . 26
5.3 Inferenza della velocità . . . 27
5.3.1 Sfruttare la velocità come noise detector . . . 29
5.4 Interpolazione Lineare . . . 31
5.5 Calcolo dell’ Accelerazione . . . 33
5.7 Disorder Ability . . . 34
5.8 Costruzione dei dataset derivati . . . 37
6 Identificazione delle anomalie delle celle voronoi 40 6.1 Outlier detection . . . 40
6.1.1 Costruzione della tabella delle deviazioni . . . 43
6.1.2 Identificazione delle anomalie . . . 43
6.1.3 Distribuzioni delle anomalie . . . 47
7 Analisi associativa 54 7.1 Problema del mining delle analisi associative . . . 54
7.2 Trasformazione degli eventi in tabella di transazioni . . . 57
7.3 Sperimentazione sulla misura moving car . . . 59
7.3.1 Sperimentazione secondo l’ambiente 1 di moving car . . . 60
7.3.2 Sperimentazione secondo l’ambiente 2 di moving car . . . 62
7.3.3 Sperimentazione secondo l’ambiente 3 di moving car . . . 62
7.4 Sperimentazione sulla misura speed . . . 64
7.5 Sperimentazione sulla misura stopped car . . . 66
7.6 Sperimentazione sulla misura disorder-ability . . . 67
7.7 Sperimentazione sulla misura accelerazione . . . 68
7.8 Punti salienti dei risultati . . . 68
Conclusioni 70
Appendice 72
Capitolo 1
Introduzione
Nel terzo secolo a.C, la frontiera fisica di divulgazione dell’informazione era rappre-sentata dalla Biblioteca di Alessandria in cui era conservata la più vasta collezione di libri del mondo antico, oggi la frontiera è rappresentata dall’informatica, la cosiddetta rete internet. L’odierna frontiera "di tipo informatico" ha reso l’informazione più accessibile, e la comunicazione più istantanea, fino a lavoro stesso globale. Dunque, oggi nella nostra vita quotidiana, nulla può funzionare senza la rete.
Il risultato di questa permanente interconnessione fra l’umanità e la rete consente il proliferare di una enorme quantità di dati che descrivono gli aspetti di interazione sociali. Un esempio classico di diffusione di notevole quantità di dati riguarda le tecnologie afferenti alla rete GPS e GSM.
Tali tecniche, si basano sulla acquisizione della localizzazione del consumatore collezionando grandi quantità di dati spazio-temporali, aprendo nuovi scenari, nella scoperta di comportamenti di mobilità, con il grande vantaggio di ridurre i costi per l’implementazione di architetture ( dedicate alla rilevazione della mobilità) che ad oggi sono stati sostenuti.
1.1
Presentazione del problema
Partendo da tali sorgenti, la letteratura ha dato vita a una serie di opere di ricerca che studiano il come, quando, dove e perché oggetti si muovono, trasformando il dato grezzo in informazione utile per lo sviluppo di nuovi servizi e applicazioni. Ad esempio in [30] si studiano i profili di mobilità da dati GPS dei singoli utenti per eseguire un processo di matching di traiettorie simili, considerato come base per un servizio di car pooling.
Partendo da quest’ultimo esempio, un aspetto interessante sarebbe applicare tecniche di outlier detection al profilo di mobilità dell’utente, osservare come queste cambiano nel tempo, e applicare la scoperta di anomalie secondo un approccio locale. Una approccio simile ma a livello più alto, globale, può essere applicato su tutta
la mobilità di un’intera area, in particolare su un territorio, si può osservare il comportamento globale degli utenti e su di esso scoprire anomalie. Lo studio oggetto del seguente elaborato ha come obiettivo la risoluzione di quest’ultima problematica, in altre parole bisogna progettare, realizzare un sistema di scoperte delle anomalie di mobilità, con un approccio globale su un territorio urbano.
Chiaramente, tali anomalie sono relazionate alla rete stradale, una anomalia in un punto x (ad esempio un incremento del traffico) potrebbe causare un’altra anomalia in un punto y vicino spazialmente(classico esempio di propagazione del traffico), oppure ancora più interessante alcune anomalie possono scatenarsi in "butterfly effect" contemporaneamente in zone opposte. Il secondo obiettivo dell’analisi è identificare correlazioni fra anomalie, così da produrre, in maniera esplicativa, una serie di associazioni nascoste.
Il lavoro che si presenta è stato realizzato nell’ambito del progetto Track & Know [https://trackandknowproject.eu], gli aspetti di ricerca,le proposte metodologiche e i risultati analitici saranno destinati alla valorizzazione di una parte del suddetto progetto. Infatti la scoperta di associazioni nascoste tra le anomalie è il primo passo per la generazione di pattern candidati di causalità della dispersione di un evento anomalo sulla rete infrastrutturale di una città.
Il progetto Track & Know è un progetto, con focus sui Big Data che pone diversi obiettivi di ricerca e sviluppo di un nuovo framework che ha lo scopo di incrementare l’efficienza dei Big Data, nel settore dei trasporti, mobilità, assicurazioni di auto e sanità. Il progetto ha ricevuto fondi dal programma: ’European Union’s Horizon 2020 Research and Innovation Programme under Grant Agreement No 780754’.
1.2
Rassegna della letteratura
Per la risoluzione del problema, è necessario applicare un processo metodologico articolato in più fasi, come si vedrà nel capitolo 2. Un’ opera cardine che da una panoramica generale dell’approccio e le problematiche che sussistono è Mobility Data [25], dove sono enunciati la definizione di traiettoria, le diverse tecniche di rappresentazione discreta e continua. Molti importanti sono i concetti di trip e stop, l’opera [30] fornisce un’ottima definizione formale per la scoperta dei trip e stop, che è il punto di partenza per definire le traiettorie e conseguentemente il profile matching. Altre tecniche di stop sono applicate in [15] [14]. Il concetto di velocità in mobilty data mining viene spesso usato sia come noise detector [32], sia per inferire il comportamento di guida dell’utente[6]. Inoltre[32] approfondisce il mining sulle traiettorie e affronta argomenti come la riduzione del rumore, dell’incertezza delle traiettorie.
L’argomento outlier detection è ampiamente discusso in letteratura, un’ottima rassegna sul funzionamento di algoritmi non supervisionati è [19], diversamente in [10] si approfondisce lo studio degli outlier detection in funzione del tempo. Proprio quest’ultimo delinea in maniera chiara e inequivocabile la differenza che sussiste tra anomalia come punto in una timeseries; anomalia come finestra di timeseries; e ancora timeseries anomala. In [13] viene adoperata la combinazione dtw-lof per identificare anomalie nella timeseries.
Il problema delle mining delle regole associative è molto diffuso nella letteratura, a causa delle sue innumerevoli applicazioni, come ad esempio il martket basket analysis, software bug detection, web mining, analisi chimiche e nei dati spazio-temporali. L’opera[2] è stato il primo lavoro su pattern frequenti e regole associative, successivamente approcci diversi per la stessa soluzione sono stati studiati, come ad esempio strategie verticale[26] e strategie che evitano la costruzione dei candidati Fp-growth[24].
Lavorare su dati di mobilità, pone una sfida dal punto di vista visuale, le tecniche classiche 2D non mostrano in maniera opportuna i dati. L’opera [9] fornisce alcuni spunti per le tecniche più opportune per rappresentare dati spatio-temporali.
Un opera molto importante da cui si è preso spunto progettuale ma che usa dati GSM è [29].
1.3
Contenuto della tesi
Dalla premessa fatta in 1.1 l’obiettivo della tesi pone in essere l’identificazione delle anomalie di un’area urbana e la scoperta di pattern frequenti correlati.
L’organizzazione della tesi è la seguente:
• il testo si apre con un capitolo introduttivo che introduce il processo, i principi e le metodologie tecniche, usati come base per lo sviluppo dell’analisi, discute le differenti strategie, aspetti ed esamina alcuni aspetti critici, per la comprensione dell’intero processo.
• il terzo capitolo riguarda la comprensione del dominio, in particolare si descri-vono le sorgenti dati, per ogni sorgente si descrive sia il carattere analitico dei dati, che quello semantico. Successivamente si definisce l’output di analisi da una prospettiva più tecnica.
• la selezione e pulizia dei dati, nonché l’analisi della qualità, aspetto importante per assicurare un elevato livello dei risultati, sono riportati nel capitolo quarto;
• la fase di costruzione delle misure propedeutiche a valorizzare il comportamento di una area urbana, è descritta nel capitolo 5. Vengono descritte in modo particolarmente approfondito, le fasi di derivazione delle feature.
• il capitolo 6 è incentrato sull’identificazione delle anomalie. Il capitolo ruota intorno a una breve spiegazione di alcune tecniche di outlier detection, quindi alla spiegazione del processo e all’implementazione della strategia adoperata, con successiva analitica degli outlier scoperti.
• il capitolo 7 presenta i più diffusi approcci al modeling di pattern frequenti. Particolare focus viene posto all’analisi associativa e quindi alla valutazione delle regole.
Capitolo 2
Principi, processi e tecniche
L’analisi che si delinea, risulta essere di carattere descrittivo, per meglio interpre-tare il processo, le metodologie, e le definizioni usati. In questo testo, si racconta di seguito, una serie di concetti preliminari che aiutano l’interpretazione e la compren-sione di tutto il processo di analisi. Pertanto in questo capitolo in primis, si chiarisce che cosa è il data mining che risulta essere alla base dell’analisi, Successivamente si affrontano i processi e task che compongono la materia della scoperta di conoscenza, infine si descrivono le diverse tipologie di tecniche knowledge-driven.
2.1
Data Mining
In passato, i cosiddetti decision-makers avevano un ruolo di decisione delle politiche di una azienda (o organizzazione o istituzione). Tali scelte si basavano sulla discrezionalità di questi ultimi, quindi di carattere soggettivo, e soprattutto lente. Con l’incremento della competizione economica, le scelte si son fatte sempre più indispensabili e importanti, è risultato di assoluta necessità uno strumento di supporto, che meglio interpreti la realtà attraverso lo studio dei dati.
In questo ruolo si pone il data mining, la pervasività della frontiera informatica ha garantito la possibilità di collezionare dati e di sfruttarli per diverse utilità, come ad esempio le previsioni di vendita, il rischio di concessione di un prestito, la possibilità di scoprire associazioni nascoste fra diversi prodotti di un supermercato. Per questo motivo il data mining, potrebbe essere interpretato come il processo di scoperta di informazioni di grande valore, da una grosso volume di dati memorizzato nelle data ware-house.
Mentre la statistica, formale è guidata da assunzione nel senso che l’ipotesi è formata e validata contro i dati, il data mining è guidata dalla scoperta nell’ottica di scoprire pattern e previsioni direttamente e automaticamente dai dati. Per converso, mentre l’intelligenza artificiale e il maching learning, si concentra sugli algoritmi di ricerca, tecniche di modellazione e teorie di apprendimento, il data mining usa tali
idee e tecniche per l’estrazione di conoscenza. Poiché tutta il processo di scoperta fa uso di grosse quantità di dati affinché si possa far buon uso del data mining, sono necessari le conoscenze di tecniche di gestione di data base, retrieve dell’informazione e programmazione distribuita. In altre parole, il data mining si colloca fra la statistica formale, l’intelligenza artificiale e le tecniche di gestione di database, nonché di computazione distribuita.
2.2
Processo del
Knowledge Discovery in
Data-Base
Il concetto di data mining ben presto ha raggiunto alti livelli di popolarità fra statistici, analisti e gestori di sistemi informativi, nel 1989, con lo stesso significato, ma con una maggiore enfasi per impostata sulla logica di fondo di scoprire conoscenza, fu coniato il nuovo termine Knowledge discovery in database da Piatestsky-Shapiro. Sulla base di questa terminologia Usama Fayad nel 1996 nell’opera [8] definisce il processo KDD (c.d. KDD-process).
L’obiettivo del KDD-process è quello di trasformare i dati da un low-level: (1) in una forma più compatta, come ad esempio un report; (2) in una forma più astratta, come una descrittiva approssimazione del modello; (3) o una modello di previsione per futuri casi.
La definizione più diffusa di KDD process è: "The nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data” [8].
Se ci si basa sul concetto che i dati sono espressioni di fatti, e quindi piccole porzioni di verità (o realtà) chiaramente le applicazioni del KDD-process non potevano che essere variegate. In particolare, nel marketing risulta essere l’applicazione principe, l’impostazione del modello economico guidato dal marketing, si pone come primo obiettivo quello di studiare il mercato, così da fornire la base per produrre sulle esigenze di quest’ultimo, in altre parole studiare i consumatori, identificarli, clusterizzarli, scoprire associazioni nascoste. Nel campo delle detenzioni delle frodi, si pensi alle ingenti perdite delle banche a seguito di frodi delle carte di credito. Nel campo della manifattura il cambio di paradigma a produzione on demand necessità la condizione che la produzione non si possa fermare per un malfunzionamento, per tal motivo risulta fondamentale scoprire in anticipo possibili malfunzionamenti. Infine nel campo della telecomunicazione, le applicazioni sono variegate, si va dalla previsione di fault di una antenna, alla scoperta di frodi di clienti che sottoscrivono un contratto in maniera ’viziata’, sino alla profilazione degli utenti a scopi commerciali. In tutti questi ambiti si colloca il ruolo del KDD-process e del Data Mining.
Figura 2.1: Kdd-process
2.2.1
Step del KDD-process
Il KDD-process è rappresentato in Figura 2.1 prende in input una o più sorgenti dati e porta in output la conoscenza, è caratterizzato da 5 step. La logica è sequenziale, con la possibilità di ripetere più volte un singolo step, nel senso che è possibile effettuare un review dello step precedente, nel caso i risultati non siano soddisfacenti. Ogni step è caratterizzato da un input e un output e da una serie di applicazione che vengono effettuate sui dati.
L’intero processo è articolato in diverse fasi:
• la prima fase, risulta essere una attività preliminare volta a produrre la com-prensione del dominio applicativo e conoscenze di base, grazie agli esperti del dominio che (fornendo meta-dati) spiegano i dati e ,al contempo, interpretano informazioni spiegabili da situazioni pregresse che emergono dai dati. Il team di data scientist si approccia al contesto di business del cliente e identifica obiettivi del progetto. Questi devono essere ben chiari e confermati dal cliente finale.
• successivamente la fase di selezione è indispensabile per selezionare solo i dati che servono per il raggiungimento dell’obiettivo. Inoltre occorre verificare eventuali integrazioni di dati da sorgenti open-data. Non bisogna dimenticare che l’eventuale comportamento e previsione che si mostra dall’analisi dei dati potrebbe essere affetta da macro fattori, condizioni meteorologiche, e altri indici statistici forniti da banche dati aperte potrebbero aiutare a comprendere meglio i dati.
• lo step di preprocessing prevede l’incremento della qualità dei dati raccolti, vengono adoperate operazioni di pulizia, vengono gestiti la gestione dei dati mancanti, in particolare occorre pulire missing values. Particolare focus ri-guarda la scoperta di anomalie in base all’obiettivo di del progetto gli outlier possono essere scartati, o alternativamente possono essere oggetto di analisi. Si pensi a un goal di analisi volto a trovare i profili utenti di una catena di
supermercati, gruppi composti da pochi elementi (outlier) vengono esclusi dall’analisi, per converso si pensi al caso della scoperta di detenzioni delle frodi delle carte di credito di una banca, in questo caso gli outlier sono necessari per l’analisi e diventano oggetto della stessa;
• prima di dare in pasto i dati alle tecniche di data mining, innanzitutto occorre capire il data mining task che meglio incorpora le esigenze degli obiettivi, i metodi, e gli algoritmi utilizzabili. Ad esempio se l’analisi è di carattere descrittiva si opterà per scoperta di pattern e descrizione dei medesimi, in maniera opposta se carattere predittivo si useranno i modelli ad approccio supervisionato. Una volta capito che tecniche usare allora si può applicare la fase di trasformazione dei dati riducendo i dati alla struttura del modello di applicare. Nella fase di trasformazione viene preparato il set di datti ottimale per gli algoritmi di Data Mining. Questo step è molto importante per il raggiungimento dell’obiettivo di analisi.
• nella fase di modellazione e applicazioni delle tecniche di data mining vengono decisi i parametri e i modelli che rispondono meglio, quindi vengono scelti i pattern di interesse particolare. Anche in questa fase in combinazione con la precedente, si effettuano delle scelte circa le tecniche da usare, particolare focus viene impostato sulla flessibilità contro la comprensibilità dell’outuput del modello.
• nella fase finale i pattern vengono interpretati e valutati, è possibile che la fase di valutazioni porti alla re-iterazione della fase di applicazione degli algoritmi di data mining con diversi parametri, o alternativamente, il processo può essere re-iterato anche sulla fase di trasformazione, integrando diverse misure di similarità.
• i pattern vengono poi mostrati all’utente, tramite tecniche di visualizzazione con lo scopo di creare, migliorare e consolidare le scelte fatte dai decision-maker. Quindi vengono integrate nel sistema di reportistica del sistema informativo aziendale, diventando elementi attivi del processo decisionale di business. Sa-rebbe opportuno sottolineare che i modelli creati richiedono manutenzione, in quanto, la conoscenza estratta potrebbe non incorporare nuovi fenomeni temporali, o alternativamente, le strutture dati potrebbero cambiare.
2.3
Tecniche: Data Mining Task
Dal paragrafo precedente, risultano due fattori evidenti: il primo rappresenta la doppia faccia del data mining la descrittiva e la predittiva, in secondo luogo la
presenza di una moltitudine di data mining task, ovvero tecniche, modelli e algoritmi con pregi e difetti che risolvono determinate problematiche.
La natura descrittiva e predittiva del data mining è sintetizzata dai i due approcci più diffusi nel campo del data mining, l’approccio supervisionato e l’approccio non-supervisionato. L’approccio supervisionato basa il suo funzionamento sulla presenza di un attributo target, cosiddetto classe su cui il comportamento delle restante feature del dataset vengono modellate. La relazione che viene scoperta, prende forma attraverso il cosiddetto modello. L’obiettivo del modello in questo caso è di carattere predittivo, in altre parole, le relazioni che vengono scoperte servono per prevedere valori futuri della classe.
In maniera opposta, l’approccio non-supervisionato non possiede la presenza dell’attributo classe , un esempio classico è la profilazione degli utenti, a priori, non si possiede l’attributo classe che indica il profilo di appartenenza, la natura dell’approccio non supervisionato è di carattere descrittivo. Chiaramente, questi due approcci possono essere combinati, il risultato è detto approccio semi-supervisionato, quest’ultimo usa le osservazioni supervisionate, per la costruzione del modello e le osservazioni non-supervisionate per migliorare il tradeoff tra le classi. Sussistono anche approcci attivi che prevedono l’utilizzo dell’utente finale per migliorare la qualità dei risultati.
Il secondo aspetto importante è rappresentato dalla moltitudine di tecniche che risolvono determinate problematiche:
• Analisi di clustering identifica cluster all’interno dei dati. Un cluster è una collezione di data object che sono simili fra loro, tale similarità può essere espressa sotto forma di funzione di distanza. In particolare, più è alta la bontà del clustering più, la similarità inter-cluster è bassa, per converso, la similarità intra-cluster è bassa. Appartiene alla famiglia degli approcci non supervisionati, il più importante algoritmo è il Kmeans. La combinazione clustering e classificatori produce la creazioni di profili e la loro descrizione. Un esempio di analisi clustering è dato il comportamento di acquisto dei consumatori costruire dei profili di acquisto.
• Classificazione: La classificazione analizza un set di dati per cui esiste una classe di appartenenza del data object (training data) e costruisce un modello per ogni classe, in base alle feature presenti nei dati. Tipicamente la struttura usata è il cosiddetto decision tree, un albero, che in ogni nodo, effettua una scelta, che taglia lo spazio dei valori delle feature e ne associa una classe. La classificazione comprende uno spazio di algoritmi piuttosto ampio, classici decision tree, knn-decision-tree, classificatori bayesani, classificatori rule-based, SVM e reti neurali. La tecnica appartiene alla famiglia degli approcci supervisionati, tuttavia hanno
un duplice scopo, possono essere usati sia in campo predittivo, usando un train set per prevedere le class label del test set, che descrittivo, si pensi all’esempio precedente, dove in combinazione con la tecnica di cluster è possibile descrivere il comportamento degli utenti di un particolare cluster.
• Analisi associative: Le analisi associative vanno a scoprire interessanti relazioni o correlazioni lungo un set di items, chiamati pattern frequenti, spesso tali pattern vengono chiamati regole associative. Una regola associativa è nella forma X −→ Y , questa regola viene interpretata come il set di tuple (all’interno del database) che soddisfano X soddisfano anche Y . Tale tecnica è tipicamente usata nei transactional database per direzionare le scelte di marketing, si pensi all’esempio applicativo del marketing. Un classico esempio è la catena di supermercato che ha bisogno di capire, quali prodotti nel database degli acquisti sono correlati. Gli algoritmi che scoprono le regole associative prendono spunto dall’algoritmo fautore Apriori-algorthm. La tecnica appartiene alla famiglia degli approcci non supervisionati.
• Analisi temporali: Le time-series analysis vanno a prevedere lo studio delle timeseries per determinare (1) caratteristiche cicliche delle serie (2) forecasting e previsioni delle serie temporali, si pensi ad esempio alla previsioni di vendita di uno store (3) ricerca ti timeseries simili, o alternativamente pattern sequenziali, periodicità e deviazioni. L’analisi può appartenere alla famiglia supervisionata ma anche a quella non supervisionata. Le tecniche usate sono tipicamente i regressori. Molto importante risulta essere la scoperta di anomalie nelle time-series.
Capitolo 3
Comprensione del dominio
Nel seguente capitolo verrà approfondita la comprensione del dominio, nonché saranno snodati diversi punti utili sia descrittivi sia vincolanti. I punti descrittivi porteranno a maggior conoscenza in fase di sviluppo dell’analisi, i punti vincolanti rappresenteranno le specifiche con cui impostare l’analisi.
I dati oggetto di analisi sono stream di dati gps collezionati per un intero anno, nel dettaglio fanno riferimento a segnalazioni di scatole nere (c.d ricevitore gps) installate sulle autovetture, tali scatole interagiscono con diversi satelliti gps, grazie ai quali si ottiene la localizzazione della scatola.
Il principio di funzionamento della localizzazione gps è di proprietà militare degli Stati Uniti di America e si basa sul metodo della trilaterazione. Nel dettaglio la Terra viene orbitata da diversi satelliti gps, ogni satellite orbita a una distanza d dalla Terra. Conoscendo tutte e distanze dei satelliti, è possibile tracciare una sfera di raggio d per ogni satellite, infine trovando il punto di intersecazione delle sfere generate dai satelliti e la Terra si ottiene la localizzazione del punto. Maggiore è la quantità di satelliti gps con cui viene effettuata la trilaterazione maggiore, sarà l’accuratezza del punto gps.
Chiaramente, non tutti i satelliti gps sono visibili da una data posizione sulla terra, un satellite che si trova nell’Emisfero Australe difficilmente potrà tracciare una sfera per un punto presente nel Nord Europa, questo vuol dire che il ricevitore gps non sempre ha un numero di satelliti gps che gli consentono di avere una posizione accurata. Nella sezione 5.3 è possibile osservare errori dovuti in parte a questa problematica.
La segnalazione della scatola nera, è collezionata nella DW di un fornitore nazionale di assicurazioni, nel dettaglio la segnalazione ha un carattere temporale e un carattere spaziale. Tecnicamente, la dimensione temporale è espressa dall’attributo tempo (di tipo time), e dall’attributo data (di tipo date). In maniera analoga, il carattere spaziale è sintetizzata dagli attributi latitudine e longitudine.
Attributo Tipo Logico Tipo Analitico
id_utente integer nominale
data date ordinale
time time without zone ordinale
latitudine float nominale
longitudine float nominale
Tabella 3.1: Schema del dataset contenente lo stream dei punti gps delle scatole nere delle autovetture
3.1
Input di analisi
Le sorgenti input di analisi sono tre: (1)Il dataset contenete i punti gps degli utenti (2) Il dataset contenete i seed delle Voronoi Cell (3) Il dataset contenete il vicinato di ogni Voronoi Cell.
3.1.1
Punti gps degli utenti
Il dataset contenete i punti gps degli utenti è un file in formato csv, ha cardinalità pari a 32.868.790 record analogamente possiede 5 attributi, è distribuito su un anno intero, nel dettaglio l’anno posto in essere è il 2017. Il primo giorno di analisi è il 31-12-2016, l’ultimo giorno del dataset è 01-01-2018.
Come già detto, il fattore temporale è caratterizzato dalla data e dall’attributo tempo, mentre il fattore spaziale possiede due attributi latitudine e longitudine che caratterizzano la posizione. Infine l’istanza della segnalazione è collegata all’utente, o se si vuole esprimere in termini giuridici, all’interessato "il soggetto in cui i dati formano oggetto di trattamento". I dati che si andranno a trattare, sono dati anonimi in quanto l’interessato è rappresentato da un intero incrementale non riconducibile (direttamente o indirettamente) alla persona fisica, al contempo non rappresentano dati sensibili (origine razziale, etnica, convinzioni religiose, filosofiche e di altro genere).
Tecnicamente parlando, l’attributo che collega la segnalazione all’autovettura è id_utente, il tipo logico di dato è integer, mentre il tipo analitico del dato è nominale; per converso l’attributo data è di tipo logico date la forma è 01-01-2018, mentre il tipo analitico risulta essere ordinale; affine a quest’ultimo l’attributo timerisulta anch’esso ordinale, mentre il tipo logico è time without zone, inoltre il formato dell’attributo è 24H; mentre gli attributi caratterizzanti lo spazio latitudine e longitudine sono di tipo float. Analogamente i due attributi vanno osservanti insieme, caratterizzando la distinzione tra due punti gps in locazioni diverse, il tipo analitico è nominale, per semplicità questi ultimi due attributi verranno considerati come un unico attributo. La tabella 3.1 sintetizza quanto appena enunciato.
Figura 3.1: Esempio di user history di un utente random del dataset, ogni punto gps è caratterizzato dalla triade (x, y, t) dove i primi due attributi rappresentano le coordinate gps, il terzo attributo rappresenta il tempo.
Formalmente il dataset dei punti gps degli utenti è rappresentato da D1, in
particolare tale relazione può essere vista come la storia di tale utente, richiamando la definizione in [30]
Definizione 3.1 (User History). The user history is defined as an ordered sequence of spatio-temporal points H = hp1, ..., pmi where pi = (x, y, t) and x, y are spatial
coordinates and t is an absolute timepoint.
La suddetta definizione risulta essere la base di partenza su come vengono interpretati i dati presenti nel dataset D1, infatti supponendo di prendere tutti i
punti gps di uno utente random, e ordinarli per gli attributi data e time si ottiene appunto la user history. La storia dell’utente verrà poi trattata e raffinata nel capitolo 5, tale definizione è propedeutica alla costruzione dei dati di mobilità. Un esempio di user history si può osservare nell’immagine 3.1 nella quale si può osservare la distribuzione spaziale. Si noti come nella Figura 3.1 non si riesca a caratterizzare l’aspetto temporale, tuttavia eseguendo un 3D-lineplot della triade (x, y, t) dei primi 25 punti di una user-history si ottiene il risultato in Figura 3.2. A tal proposito si noti come da una user-history si possono delineare momenti in cui l’auto si muove in tempi ristretti e momenti in cui l’utente non si muove in tempi lunghi, infatti la Figura 3.2 suggerisce tre istanti (livelli) di movimento (anche molto simili). Da questa premessa e possibile citare la definizione presente in [25] di traiettoria. Definizione 3.2 (Traiettoria). A trajectory is the part of the movement of an object that is delimited by a given time interval [t , t ]. It is a continuous function
Figura 3.2: Rappresentazion 3D di un esempio dei primi 25 punti di una user history, ogni punto gps è caratterizzato dalla triade (x, y, t) dove i primi due attributi rappresentano le coordinate gps, il terzo attributo rappresenta il tempo.
from the time interval [tBegin, tEnd] to Space. The spatio-temporal position of the
object at tBegin (resp. tEnd) is called the Begin (resp. End) of the trajectory.
Il concetto di traiettoria verrà poi usato nella fase di inferenza dei dati di mobilità e costruzione delle feature derivate, tuttavia in questa parte iniziale dell’analisi l’aspetto cruciale è comprendere se il dataset D1 possiede gli elementi indispensabili
al raggiungimento degli obiettivi preposti. Quanto visto con gli esempi 3.1 e 3.2 dimostra come D1 possa essere visto come un dataset contenente l’user-history di
2.285 utenti ciascuno avente un numero specifico di traiettorie.
3.1.2
Seeds delle Voronoi Cell
Esistono diversi tipi di suddivisione in aree dello spazio, una delle possibili strategie è applicare una suddivisione dello spazio nei quartieri più vicini di un determinato insieme di punti. Questa approccio è chiamato Voronoi Diagram. La Figura 3.3 e la Figura 3.4 presentano un esempio. Con tale premessa si introduce l’ulteriore sorgente dati fornita come input di analisi. La medesima rappresenta la suddivisione in Voronoi Celle del territorio della toscana il formato è csv. Le istanze rappresentano i seed delle Vornoi Celle. Il numero di istanze è 216.766 mentre la dimensionalità è di 3 attributi. Il primo attributi rappresenta l’identificativo della cella, il tipo numerico è integer, mentre il tipo analitico risulta essere nominale, gli altri due attributi risultano essere la longitudine e latitudine, per questi ultimi ci si rifà alla tipizzazione mostrata nel precedente dataset. La tabella 3.2 sintetizza lo schema. Formalmente il dataset dei seed delle Voroni cell è rappresentanto da D2.
Figura 3.3: Esempio di una suddivisione dello spazio di 9 punti su un piano cartesiano
Figura 3.4: Esempio di una suddivisione della città di Londra secondo il metodo Voronoi
Attributo Tipo Logico Tipo Analitico
tcell integer nominale
longitudine float nominale latitudine float nominale
Attributo Tipo Logico Tipo Analitico
tcell integer nominale
tcell_nn integer nominale
Tabella 3.3: Matrice adiacenza tra Cella e Neighborhood
3.1.3
Vicinato delle Voronoi Cell
L’ultima sorgente di dati è la matrice di adiacenza delle Vornoi Celle, in altre parole la relazione Cella - Vicino, un attributo caratterizza la Cella di osservazione, mentre il secondo attributo caratterizza la cella vicina. Entrambi gli attributi sono di tipo analitico nominale, mentre di tipo logico integer, infine la cardinalità di questo set di dati è 1.300.541. La tabella 3.3 mostra la struttura. Formalmente il dataset del vicinato delle Voronoi Cell è rappresentanto da D3.
3.2
Output, classificazione, e processo dell’analisi
Osservati le tre diverse sorgente dati, si conferma il goal dell’analisi presentato in 1.1, nello specifico l’analisi si pone di partire dai dati grezzi di mobilità, quindi successivamente costruire misure quantificabili che incorporano il comportamento di zone della città. Sulla base di tali comportamenti, distribuiti in un anno, si vanno a identificare anomalie. Una volta eseguita l’anomaly detection tali anomalie devono essere associate, per verificare eventuali correlazioni.
Dalla premessa consegue che l’orientamento di business è quello volto a iden-tificare le anomalie, piuttosto che il normale comportamento, ciò significa che gli outlier diventano oggetto di analisi, mentre i comportamenti normali vengono esclusi dall’analisi. Un ulteriore conseguenza è il fatto della necessità di una analisi asso-ciativa, volta a scoprire collegamenti nascosti fra le anomalie identificate. L’ultima conseguenza è che l’analisi delinea un carattere puramente descrittivo, pertanto l’approccio posto in essere è quello non supervisionato.
Come detto nel paragrafo 2.2 uno dei processi di sviluppo di una analisi risulta essere il kdd-process, esistono altre wokrflow come il CRISP-DM e il SEMMA. In questo progetto sia adopera il Kdd-process. Poiché i dati afferiscono a dati di mobilità il kdd-process è stato modificato per tenere conto del carattere dei dati. La Figura 3.5 mostra il processo che è stato usato per l’analisi. Il processo si sviluppa nel seguente modo:
• nella prima fase i dati grezzi di mobilità vengono filtrati, selezionati e puliti di eventuali rumori e valori mancanti, successivamente si procede con la carat-terizzazione dei dati di mobilità, si costruiscono le traiettorie, e informazioni importanti come velocità e accelerazione
Figura 3.5: Kdd-process usato nell’analisi
• nella seconda fase, vengono costruite le feature che caratterizzano le aree della città
• successivamente, viene eseguita la scoperta di anomalie sulle linee temporali delle celle secondo le diverse feature derivate
• infine, si esegue una analisi associativa per scoprire link nascosti fra le anomalie.
3.3
Vincoli tecnologici
L’analisi è stata prodotta in collaborazione con l’Università di Pisa e l’istituto ISTI del CNR di Pisa, unico vincolo è l’uso di strumentazioni non commerciali in modo da garantire il riuso del codice sviluppato, per tal motivo le tecnologie scelte per lo sviluppo dell’analisi sono:
1. Python: linguaggio di programmazione di alto livello, dinamico e orientato ad oggetti. L’ampio uso della comunità di Data scientist ha consentito la rapida popolarità non di meno una serie di librerie che hanno lo scopo di facilitare la manipolazione e il modeling dei dati
2. Ipython è la shell interattiva di Python è ampiamente usato dalla comunità scientifica, supporta il tab completion e un sistema di documentazioni dei moduli attraverso utili magic commands .
3. Jupyter Notebook è la shell interattiva di Ipython fornita attraverso il web, di fatto è un Web-Ide, consente eseguire codice Python, e scrivere documenti di analisi attraverso Markdown. In altre parole unisce la scrittura computazionale con quella narrativa.
4. NumPy è il pacchetto fondamentale per la computazione scientifica con Py-thon, consente di eseguire operazioni su array N-dimensionali, inoltre possiede sofisticate funzioni broadcasting; tool per l’integrazione con C/C++, infine utili funzioni di algebra Lineare
5. Scipy è il pacchetto open-source ideato per matematici, scienziati e ingegneri, consente di applicare una serie di algoritmi matematici e di modeling.
6. Pandas è una libreria di alto livello costruita su Numpy che fornisce tool per il data wrangling, l’estrazione, la preparazione e la pulitura risultano estremamente
facili con pandas.
7. MatPlotlib e Seaborn, sono le librerie visuali con cui è possibile eseguire operazioni di Visual Analytics
8. Folium è una libreria che consente la visualizzazione interattiva di dati spaziali. 9. Java: è un linguaggio di programmazione ad alto livello orientato ad oggetti.
Java possiede un’enorme libreria di classi standard ben documentate.
10. SPMF è una libreria opensource specializzata nel mining di pattern è basata su Java.
11. PostgreSQL: è un RDBMS opensource progettato per essere esteso e custo-mizzato, possiede molte estensioni tra cui PostGis, che è l’estensione usata in questa analisi, che mette a disposizione una serie di primitive che hanno l’obiettivo di facilitare le computazioni spaziali.
Capitolo 4
Pulizia e selezione dei dati
Qualsiasi collezione di dati presenta errori, rumore, dunque una fase di pulizia e controllo risulta necessaria prima di effettuare qualsiasi modellazione e apprendimento automatico. Ad esempio, la frequenza di un valore potrebbe essere non veritiera se ci fossero valori duplicati. Inoltre per ogni analisi è goal-driven, a seconda dell’obiettivo si necessita di selezionare porzioni diversi di dati o di abbassare o alzare la granularità delle sorgenti.
In questo capitolo verranno affrontati tali tematiche, tenendo come orientamento strategico di fondo il raggiungimento del goal espresso in 3.2.
4.1
Selezione dei dati
La città oggetto di analisi risulta essere la città di Lucca, risulta pertanto inutile tener conto di punti gps, Voronoi Celle di zone non presenti nella città di Lucca. Pertanto, la prima operazione risulta essere quella selezioni delle tre sorgenti dati.
In primis, è stato ottenuto il poligono gps rappresentante le boundaries della città di Lucca. Tale poligono è stato scaricato dal servizio openstreetmap l’immagine 4.1 mostra la forma delle boundaries della città oggetto di analisi.
Successivamente, il poligono è stato importato in postgis, infine sono state eseguite le query sql che selezionano sia i punto gps sia le Vornoi Cell entro i confini della città. A titolo esemplificativo, si mostra la query che estrae i punti entro una determinata area.
Sia a la tabella contente i punti gps (o le vornoi celle) che si vogliono filtrare, sia b la tabella contente le boundaries, i punti di a presenti in b sono:
SELECT a.* FROM a JOIN b
Figura 4.1: Boundaries della città di lucca
Figura 4.2: Seeds delle Voronoi Cell nella città di Lucca
Dove wkb_geometry rappresenta la geometria in postgres (una geometria può essere un punto, una linea o un poligono, per una approfondimento su tale concetto si consiglia la lettura della documentazione di Postgis [https://postgis.net/docs/].
La cardinalità del dataset contenente i punti gps al termine dell’operazione di selezione risulta essere 10.588.519, per converso la cardinalità delle dataset contenente le Voronoi Cell è 1.705, infine il numero di istanze del terzo dataset (matrice di adiacenza) risulta essere 9.762.
Il filtro ha portato a una riduzione del 67% nella prima sorgente dati e dell 99% nelle altre due sorgenti dati. La Figura 4.2 mostra i seeds rimanenti dopo il filtro applicato.
Nella Figura 4.3 si può osservare la distribuzione spaziale delle auto per cella. Nel dettaglio da D1 e D2 sono stati associati ai punti gps le celle più vicine in
termini spaziali, su questo risultato sono stati conteggiate le distinte auto per cella. Quindi i conteggi sono stati discretizzati in 5 bin: (0,200], (200,1400], (1400,6800] (6800,15000], infine maggiore 15000 auto. Si osservi come il downtown cittadino e le arterie principali della città siano più frequentata rispetto al periferie e strade
Figura 4.3: Distribuzione spaziali delle auto per celle
secondarie.
4.2
Comprensione del grado di incertezza
tempora-le
I dati di mobilità si sviluppano in due dimensioni principali: una spaziale e una temporale, e di fatto ereditano dallo Spatial Data Mining incertezza spaziale, e sulla riva opposta dal Temporal Data Mining incertezza temporale. In seguito vedremo la comprensione dell’incertezza spaziale, ciò su cui occorre soffermarsi è l’incertezza temporale.
Il sampling rate è la frequenza con cui il ricevitore gps manda il segnale di localizzazione, e il medesimo segnale viene registrato nella Dw. In altre parole è la frequenza con cui l’autovettura viene localizzata. Tale frequenza potrebbe essere incostante, infatti questo intervallo potrebbe avere un minimo di alcune secondi o un massimo di alcuni giorni. Inoltre i dati possono essere affetti da sparsità, una segnalazione può essere registrata ogni 3 giorni.
Per comprendere il grado di incertezza temporale del sampling rate occorre eseguire un analisi su di esso, per tal motivo occorre costruire il delta time dal punto precedentee il il delta distanza dal punto precedente. Questi ultimi di definiscono nel seguente modo:
Definizione 4.1 (∆t−1). Sia U = {u1, u2, . . . , un} il set di utenti in D1. Sia
Pu = {p1, p2, . . . , pm} il set di punti di un utente u. Sia Tp = {t1, t2, . . . , tm}il set dei
tempi in cui Pu occorrono. Si definisce
∆t−1(i) = 0 if i = 1 tpi − tpi−1 otherwise (4.1)
id_utente id_punto_gps time_delta_prec dist_delta_prec 1 1 0 0 1 2 00:06:53 1035.561662 1 3 04:42:45 1.683694 1 4 00:02:27 1826.486920 1 5 00:05:55 606.877660 Tabella 4.1
Figura 4.4: Frequenza del tempo che intercorre in ogni segnalazione gps
dove 1 ≤ i ≤ m
Definizione 4.2 (∆d−1). Sia U = {u1, u2, . . . , un} il set di utenti in D1. Sia
Pu = {p1, p2, . . . , pm} il set di punti di un utente u. Sia la funzione dist(u, q) che
esprime la differenza in metri tra i punti u e q Si definisce:
∆d−1(i) =
0 if i = 1
dist(pi, pi−1) otherwise
(4.2)
dove 1 ≤ i ≤ m
Con l’ausilio delle funzioni finestra di Postgres, sono state derivate ∆t−1 e ∆d−1.
In particolare usando lag e Partition By sono stati ottenuti i record ’tipo’ presenti in tabella 4.1. Trasformando la terza colonna in secondi e conteggiandone la frequenza si osserva il risultato nelle figure 4.4, 4.5 4.6. Non essendo visualmente esaustiva la Figura 4.4 è stata zoomata nelle successive due. In particolare, si può notare come il valore più frequente sia 30 secondi, analogamente, il secondo più frequente risulta essere 37 secondi (Figura4.6), inoltre si notano fluttuazioni tra i 100 e 200 secondi, ovvero da 1 minuto e 30 secondi ai 3 minuti. Infine si notano valori poco frequenti (basse frequenze intorno 1) dai 200 secondi in poi.
Questi grafici mostrano come D1 erediti incertezza temporale, si può affermare
Figura 4.5: Frequenza del tempo che intercorre in ogni segnalazione gps (zoom da 0 a 800 secondi)
0-200 secondi, ancora più probabile che sia di 30 secondi, tuttavia non si escludono gap temporali più alti. Addirittura il massimo gap temporale registrato è di 167 giorni.
Infatti da un confronto con chi possiede la titolarità giuridica dei dati (octo-telematics), e in particolare con l’esperto del dominio, è stato riscontrato, che le blackbox installate sulle auto non possono spedire continuamente segnalazioni. Il motivo principale è la saturazione della larghezza di banda concessa, nel dettaglio, secondo politiche di compattazione dei dati, impostate su scelte interne aziendali, le scatole nere possono accumulare informazioni e trasmetterle tutte in un istante. La politica di compattazione può scegliere di compattare i dati fino a un percorso totale dell’auto di 2Km.
Inoltre molti punti possono essere caratterizzati come stop, ad esempio se la macchina rimane ferma per un ora il time delta dal punto gps precedente è molto alto, mentre la distanza rimane prossima allo 0 (si osservi la Figura 3.2) . Come si vedrà nel Capitolo della costruzione delle feature, queste situazioni verranno trattate. Inoltre per le situazioni non caratterizzabile come stop il sample rate sarà omologato a una soglia definita.
4.3
Riduzione del rumore
I dati di mobilità possono contenere rumore, un esempio potrebbe essere punti gps presenti in mare di un dataset afferente a mobilita terrestre [22], questo tipo di problematica è stata risolta inserendo le boundaries della città di Lucca nella sezione 4.1. Un altro tipo di problematica è rappresentata dalla presenza di valori duplicati. Due sono le problematiche legate ai valori duplicati: (1) valori duplicati che afferiscono allo stesso data object; (2) valori duplicati che afferiscono a diversi data object ma che per caso sono identici nei valori (ad esempio due persone con nomi simili)[27]. Il caso affrontato di seguito risolve la prima problematica.
Il punti gps possono avere elementi duplicati, questo occorre soprattutto quando i dati vengono esportati manualmente da un collezione di più files [16]. Partendo dalla tabella 4.1 risulta facile scoprire attraverso una selezione, i punti gps che hanno ∆t−1 = 0 ∧ ∆d−1 > 0, questi punti gps sono rappresentazioni in diverse zone di spazio,
ma nello stesso tempo, della stessa auto. I record duplicati risultano essere 73, anche se rappresentano una bassissima percentuale di D1, la presenza di questi duplicati
potrebbe portare a valori non veritieri delle features derivate, per tal motivo sono stati eliminati.
Capitolo 5
Dati di mobilità e costruzione feature
Per raggiungere l’obiettivo di analisi occorre che siano derivate delle misure per ogni cella. Alcune misure possono essere il numero di auto ferme, o il numero di auto in movimento in una determinata aera(cella). Per poter quantificare tali misure, è necessario costruire da D1, le traiettorie degli utenti e da tali traiettorie eseguire,costruire un serie di feature quindi l’associarle alla 1-nn cella Voronoi. Questa procedura richiede alcune preliminari fasi come la scoperta degli stop, l’enumerazione delle traiettorie, l’interpolazione lineare, propedeutiche alla costruzioni delle feature derivate. In altre parole vanno costruiti i dati di mobilità In questa capitolo verranno spiegate le feature estratte e le strategie usate per derivarle.
5.1
Stop Detection
Nel capitolo di comprensione del dominio è stato introdotto il concetto di user History che verrà usato di seguito per definire il concetto di stop. La letteratura è colma di strategie per identificare punti gps qualificabili come stop, in particolare dal punto di vista della densità i punti di stop possono essere tutti quelli presenti in vicinato denso rispetto ad altri [14]; dal punto di vista del tempo, gli stop possono essere punti il cui differenziale temporale è più alto di una soglia predefinita[21][23]. In sintesi possono essere raggruppati in due macro famiglie cluster based e heuristic based in questo progetto si adotta la strategia presente in [29].
Definizione 5.1 (Stop). Data H la user history di utente u uno stop è un set {pk, . . . , pq}con 1 ≤ k ≤ m e 1 ≤ q ≤ m tale che dist(pk, pq) ≤ tshd∧ time(pk, pq) ≥
tsht . Dove la funzione dist(pk, pq) che esprime la differenza in metri tra i punti pk
e pq, e la funzione time(pu, pq) esprime la differenza in secondi tra i punti pk e pq.
In questo progetto le treshold sono fisse tshd = 50 e tsht = 300 ∗ 6000, tuttavia
sussiste consapevolezza che una parametrizzazione delle stesse in base all’utenza migliorerebbe lo stop detection. L’immagine in Figura 5.1 mostra un esempio di
Figura 5.1: Esempio di uno stop(rosso) dei primi 9 punti di una user history. Il primo punto è arancio, l’ultimo punto in verde.
punto interpretato come stop. Lo start point è in arancio l’utente arriva nella zona indicata dalla circonferenza rossa la densità di punti gps in quell’area è 3, quest’ultimo set di punti risponde alla logica della definizione 5.1, quindi è etichettato come stop, successivamente dopo un gap temporale di 5 ore l’utente riparte per finire in un end point (in verde). Bisogna precisare che gli start e gli end point, ai fini del conteggio delle macchine ferme in una data cella, vengono caratterizzati anch’essi come stop.
5.2
Enumerazione delle traiettorie
Individuati gli stop, risulta abbastanza facile comprendere la definizione di trip come sequenza contigua di punti tra due stop [22]. La Figura 5.2 mostra l’esempio di due trip in due colorazioni diverse, in particolare il primo trip risulta essere un set di punti che iniziano dallo start point fino al primo punto considerato come stop pk,
mentre il secondo trip va dall’ultimo punto considerato come stop pq, fino all’end
point.
La Figura 5.2 fa osservare una nuova problematica, circa i gap spaziali che vengono posti essere tra i vari punti, infatti ricordiamo come la Figura 4.5 mostrava incertezza temporale circa il sample rate con cui veniva segnalata la posizione dell’auto. Esistono diversi tipi di strategie applicabili (i) free (ii) constrained movement nel primo caso
Figura 5.2: Esempio di due trip
si traccia una linea non vincolante dalla rete stradale, nel secondo caso è necessario in primis associare il punto gps al più vicino segmento stradale, quindi applicare lo shortest path o il time o il time-aware. Per semplicità e rapidità nella realizzazione del primo prototipo funzionante, si opta per la soluzione più semplice, pertanto, in questo progetto si adotta la strategia free. Si applica sul segmento tracciato uniform speed. Il dettaglio di come viene calcolata la velocità è presentato nel seguente sezione.
5.3
Inferenza della velocità
Dopo la fase di scoperta dei punti GPS qualificabili come stop e dopo l’enume-razione delle traiettorie per tutti gli utenti del dataset, un ulteriore feature utile a scoprire eventuali errori, e caratterizzare una nuova dimensione di analisi la velocità (speed).
La velocità di una traiettoria è spesso usata nella letteratura della mobilità, ad esempio in [6] è usata per inferire il comportamento di guida dell’auto. In questo progetto la strategia utilizzata è quella di associare al punto GPS la media delle velocità del segmento precedente e del segmento successivo. In altre parole, la velocità di un punto corrisponde alla media tra la velocità in entrata e quella in uscita.
Figura 5.3: Esempio di 5 punti gps di una traiettoria
u,q dist time p0,p1 30 10
p1,p2 7 5
p2,p3 7 5
p3,p4 26 11
Tabella 5.1
Volendo formalizzare il concetto potremmo dire che dato P = {p1, p2, ..., pm}il set
di punti GPS di una traiettoria x, data la funzione dist(u, q) che esprime la differenza in metri tra i punti u e q, data la funzione time(u, q) che esprime la differenza in secondi tra i punti u e q, si definiscono velocità in entrata sin e velocità in uscita sout
di un elemento i in P : sin(i) = dist(pi,pi−1) time(pi,pi−1), if i > 0 0 otherwise (5.1) sout(i) = dist(pi+1,pi) time(pi+1,pi), if i ≤ n − 1 0 otherwise (5.2)
Quindi si definisce la speed dell’elemento i in P come
s(i) = sin(i) + sout(i)
2 (5.3)
Ad esempio osservando la Figura 5.3 il set di punti P ha lunghezza n pari a 5 analogamente il set di punti P è {p0,p1,p2,p3,p4}, osservando invece la tabella 5.1 si possono osservare le distanze in metri e in secondi fra i diversi punti. Supponendo di voler calcolare s(0) da formula 5.3 questa sarà uguale alla media fra velocità in entrata e velocità in uscita. La velocità in uscita sin(0)sarà uguale a 0 in quanto i
non risulta essere maggiore a 0, per converso sout(0) risulta essere il rapporto tra la
distanza in metri tra l’attuale punto e il punto successivo dist(p0, p1) che è uguale a 30 e la differenza in termini di secondi tra time(p0, p1) che è 10, pertanto sout(0) = 3.
Conseguentemente s(0) = 1.5 in quanto è la media sin(0) e sout(0). Secondo questa
logica s(1) sarà la media fra sin(1)che è uguale a 3 e tra sout(1) che è uguale a 1,4.
Infine s(4) sarà la media fra sin(4) che è uguale a 2,36 etra sout(6)che è uguale a 0
Figura 5.4: Ilustrazione concettuale di uno spike all’interno di una traiettoria
u,q dist time p0,p1 30 10 p1,p2 7 5 p2,p3 100 1 p3,p4 112 1 p4,p5 10 5 p5,p6 30 15 Tabella 5.2
5.3.1
Sfruttare la velocità come noise detector
Spesso le traiettorie non sono perfettamente accurate bensì possono contenere errori, tali errori sono causati da diversi fattori:
1. mancato aggancio dei satelliti, il dispositivo GPS tipicamente necessita di ricevere segnali da almeno 7 o 8 satelliti per calcolare la locazione, quando il numero di satelliti non è sufficiente l’accuratezza della posizione decresce. 2. limite minimo di satelliti in particolare quando il numero di satelliti è al
limite minimo si osservano diverse triangolazioni dovute a diversi agganci di satelliti che soddisfano il limite minimo, provocando moltitudine di punti a distanze diverse.
3. cold start problem: quando il dispositivo viene acceso, richiede 5 minuti per il settaggio del sistema(timing, satelliti) che aiuterà a richiedere il segnale più velocemente durante il viaggio.
4. segnale ostacolato: alberi, costruzioni, tunnel, montagne possono ostacolare il segnale
5. errore multipath: quando i segnali gps rimbalzano sugli edifici il ricevitore viene confuso dal tempo extra impiegato, in questo caso si verificano grandi errori di posizionamento.
Anche il dataset oggetto di analisi è affetto da questi fattori, nello specifico è possibile ricondurre il rumore scoperto nel dataset a due casi.
Il primo caso è riconducibile alla scoperta di spike nelle traiettorie. Come si osserva dalla Figura 5.4 la traiettoria risulta, lineare fino al p3, in particolare si nota come dal p2 al p3 ci sia una distanza di 100 metri e passi solo 1 secondo, il caso si ripete dal p3 al p4. Calcolando la s(3) secondo la logica descritta nel paragrafo precedente, la velocità risulterebbe 111 metri al secondo (o 399 km/h).
Questo caso sembrerebbe riconducibile al fattore 3, sarebbe ipotizzabile che il dispositivo essendo al limite minimo di satelliti agganciati, dovuto a presenza di edifici cerchi nuovi satelliti in una frazione di tempo abbastanza piccola causando la registrazione di due registrazioni molto vicine, temporalmente ma distanti nello spazio, in quanto agganciando diversi satelliti si registra una diversa posizione GPS.
Nel secondo caso non sussiste uno spike tuttavia il valore della velocità nel punto 3 è comunque anomalo. Infatti, come si osserva in Figura 5.5 il p3 è molto vicino in termini di distanza al p2 e al contempo molto vicino in termini del tempo al p4. Calcolando la s(3) con i dati della tabella 5.3 si ottiene una velocità in entrata sin(4)
pari a 0,0001, mentre la velocità in uscita sout(4) è pari a 1000 metri al secondo,
conseguentemente si ottiene una velocità nel punto 4 pari a circa 500 metri al secondo (o 1800 km/h).
Figura 5.5
u,q dist time
p0,p1 30 10
p1,p2 7 5
p2,p3 0,001 10 p3,p4 1000 1
Tabella 5.3
Il secondo caso invece sembrerebbe dovuto a un malfunzionamento del dispositivo è come se registri la posizione precedente solo quando arrivi nel punto successivo.
Essendo il tempo espresso in secondi risulta evidente che nessuno del set di punti in Figura 5.5 possa essere uno stop, in quanto non si supera la soglia temporale dei 30 minuti. Fatta questa premessa è possibile sfruttare la velocità come detective nel far emergere punti che non sono in linea con una velocità ragionevolmente idonea al tracciato cittadino. Con questo orientamento di fondo si sceglie una soglia permissiva 300Km/h che corrisponde a circa 83m/s, ponendo l’assunzione che tutti quei punti aventi velocità maggiore di 83m/s sono noise e quindi vanno eliminati, questa strategia prende spunto dal noise filtering Heuristics-Based Outlier Detection in [32], tuttavia
Figura 5.6: Il punto in rosso rappresenta un rumore da eliminare, la velocità in quel punto è troppo alta.
occorre ricordare che esistono altri tipi di noise filtering come Mean (or Median) Filter e Kalman and Particle Filters.
Il filtro legato alla noise ha portato a cancellare l’0,3% di punti GPS affetti dalle suddette problematiche. La Figura 5.6 mostra l’esempio di un punto eliminato.
5.4
Interpolazione Lineare
Si è già avuto modo di osservare nella sezione 4.2 che le osservazioni gps della mobilità di una auto, possono essere affette da incertezza temporale, nell’ambito della frequenza delle osservazioni. Infatti, come si osserva nella Figura 4.6, anche se il picco delle osservazione risulta essere ogni 30 secondi, è anche vero che sussistono molte osservazioni con intervallo temporale maggiore di 30 secondi.
Per risolvere questa problematica, è opportuno omologare la frequenza delle osservazioni (sample rate) a 30 secondi, è necessario pertanto stimare la posizione di utente tra due osservazioni, il cui intervallo temporale sia maggiore di 30 secondi. Una definizione formale e chiarificatrice di come stimare la locazione di un punto è espressa in [11] "For a given trajectory tr, the expected location of the moving object at a point in time t between ti and ti+1 with 1 ≤ i < n is obtained by linear
interpolation between the positions (xi, yi) and (xi+1, yi+1)".
Il novero della stima di punti è ampio, l’opera [12] enuncia ulteriori due tecniche oltre l’interpolazione lineare: (1) interpolazione basata sul più vicino punto Nearest-neighbor Interpolation; (2) Piecewise Cubic Hermite Interpolation, la scelta di una tecnica piuttosto che un altra è fortemente condizionata dalle caratteristiche della mobilità dell’auto osservata. Nella sezione 5.2 con riferimento alla Figura 5.2 è stato mostrato l’alveo delle strategie di collegamento fra due punti di una traiettoria, riportando la scelta progettuale impostata sulla tecnica free (l’applicazione di una linea retta tra due punti) la strategia che meglio si sposa con tale scelta risulta essere
p q
timestamp 10:05:00 10:07:00
velocità 10 19
Tabella 5.4: Timestamp e velocità di due punti gps
l’interpolazione lineare. Tale tecnica prevede l’inserimento di punti stimati in base a una soglia temporale prescelta che in questo caso risulta essere 30 secondi, ciò significa che per ogni coppia di punti della traiettoria si vanno a inserire una set di punti fittizi tale che il sample rate risulta essere ≤ 3000. Ogni punto gps possiede
come attributo anche la velocità, occorre pertanto distribuire linearmente anche quest’ultima. Il processo di interpolazione lineare prende in input una coppia di punti gps p e q e ritorna un set di punti p ∪ P F ∪ q dove P F = {pf1, pf2, ..., pfn} è
il set di punti fittizi creati dall’interpolazione lineare. Nel dettaglio:
1. per ogni coppia p e q in primo luogo si calcola quanti pf inserire. Data time(p) la funzione che ritorna il timestamp di un punto gps, il numero n di punti fittizi da inserire tra p e q risulta essere time(q)−time(p)
δ − 1 dove δ rappresenta la
soglia temporale prescelta per l’omologazione delle traiettorie a un sample rate univoco, in questo caso 30 secondi.
2. Scoperti quanti punti fittizi, inserire occorre capire come distribuire linearmente la velocità, quindi si calcola il differenziale di velocità ∆V tra il punto p e il punto q.
3. Si procede nel calcolare l’incremento di velocità iv che bisogna aggiungere a
ogni punto fittizio in modo da ottenere la velocità distribuita linearmente, pertanto iv = ∆Vn
4. Iterando il processo n volte si imposta il punto di partenza in p, quindi si innesta il primo punto fittizio pf1, il quale avrà timestamp time(p) + δ e
velocità speed(p) + iv. Avendo tempo e velocità risulta semplice calcolare i
metri percorsi fino a pf1, quindi si posiziona spazialmente il punto fittizio lungo
la linea che collega p e q. Nel’iter successivo il nuovo punto di partenza risulta essere pf1, e così via fin quando tutti i punti fittizi sono stati inseriti.
Ad esempio supponendo che bisogna interpolare due punti p e q con δ = 3000 la
tabella 5.4 mostra il timestamp e la velocità. Il numero di pf da inserire risulta essere n = 302000 − 1 = 3. Il differenziale di velocità ∆V risulta essere 9, mentre l’incremento
risulta essere iv = 93 = 3. Iterando n volte si imposta il punto di partenza in p, quindi
il primo punto fittizio pf1 avrà timestamp 10:05:30 e velocità 13, nel punto pf1 si è
arrivati in 3000 a una velocità di di 13m/s quindi sono stati percorsi 390m, pertanto
Figura 5.7: Esempio di una traiettoria pre interpolazione
Figura 5.8: Esempio di una traiettoria post interpolazione
successivo il nuovo punto di partenza sarà pf1 il prossimo punto fittizio sarà pf2, il
processo è ripetuto fin quanto tutti i punti fittizi sono stati inseriti.
La Figura 5.7 e la Figura 5.8 mostrano un esempio di applicazione del processo di interpolazione.
5.5
Calcolo dell’ Accelerazione
Una volta ottenuta la velocità è possibile inferire l’accelerazione. L’accelerazione può essere quantificata con valori positivi e valori negativi. In particolare un valore positivo indica che sussiste una accelerazione, mentre un valore negativo indica che esiste decelerazione. L’accelerazione può essere calcolata secondo diverse strategie:
1. calcolando lo slope dell’incremento della velocità nel tempo
2. migliorando lo slope con una crescita e decrescita che segue la distribuzione esponenziale
3. integrando da sorgenti esterne le elevazioni del terreno e migliorando la funzione di accelerazione con fluttuazioni legati alle elevazioni del terreno spaziale. In questo progetto è stata usata la prima strategia settando al punto gps il rapporto dello slope ∆V
∆t.
5.6
Map Cell Matching
Individuate gli stop, individuati i punti appartenenti ai trips, calcolata la velocità e infine l’accelerazione, per poter legare tali misurazioni alle celle spaziali è necessario associarle.
Ogni punto gps viene associato alla vornoi cell più vicina in termini spaziali, volendo esemplificare da un ottica tecnica, la seguente istruzione sql è usata per associare i punti gps alle celle più vicine. Sia D1 la relazione contenete tutte i punti gps, sia D2 la relazione contenente i seed delle Celle Voronoi.
SELECT D1.id_punto_gps, nn.tcell from D1
CROSS JOIN LATERAL (
SELECT D2.tcell, D2.wkb_geometry from D2
order by D1.gps_point <->D2.wkb_geometry limit 1
) AS nn;
5.7
Disorder Ability
Le misure costruite sino ad ora, caratterizzano con un valore quantitativo il comportamento di tale cella al suo interno, ad esempio il numero di macchine ferme (stopped car) o ancora la velocità al suo interno (ad esempio la speed). Tuttavia ciò che queste misure non incorporano, è come la cella si comporta in relazione alle altre celle limitrofe, o cosiddetti neighborhood. Una possibile misura che incorpora la relazione di una cella i con le sue k celle limitrofe è l’overlap ratio degli utenti che passano suddetta cella i, in relazione con i suoi k vicini spaziali. L’ispirazione deriva dalla misura di overlap ratio usata nella branchia delle Analisi delle Reti Sociali, tale misura parte dal concetto che un utente tendenzialmente può appartenere a più comunità, in questo caso l’overlap ratio è calcolato come numero medio di comunità a cui l’utente (c.d. nodo) appartiene [7].
Figura 5.9: Due utenti che passano attraverso le celle, l’utente u1 in nero, l’utente u2 in rosso celle utenti c1 {u1,u2} c2 {u1} c3 {u1,u2} c4 {u2} c6 {}
Tabella 5.5: Esempio di un conteggio degli utenti
In questo contesto ogni cella può essere vista come una comunità, pertanto dire che una in una cella i, di un determinato giorno e specifico timeslot temporale, è passata una specifica autovettura (utente), equivale a dire che la medesima autovettura appartiene alla suddetta cella i. Chiaramente l’autovettura muovendosi lungo i propri trips passa in più celle pertanto teoricamente le celle condividono un certo numero di autovetture, in un determinato giorno e timeslot temporale.
La Figura 5.9 e la tabella 5.5 mostrano un esempio. Nella Figura 5.9 le linee trattegiate delimitano l’area delle vornoi cell i trip di due utenti u1 e u2 mostrano tre punti gps che ricadono in tre celle diverse, ricordiamo l’associazione del punto gps alla cella è basata sulla minima distanza, nel senso il punto gps è associato alla cella più vicina. Osservando la Figura in questione si nota la cella c1 condivide con la cella c2 l’utente u1, analogamente la cella c1 condivide con la c4 l’utente u2, infine la cella c1 condivide con la cella c6 nessun utente. In sintesi la cella c1 condivide un utente con c4, un utente con c2 e zero utenti con c6, mentre il totale t degli utenti condivisi con altre celle per la cella c1 equivale a 2, per un dato giorno e timeslot.
Da un ottica semi formale è possibile dire che siano Up e Uq il set di utenti di
appartenenti rispettivamente alla cella p e alla cella q il conteggio di utenti condivisi fra p e q risulta essere |Up∩ Uq|. Dove | · | rappresenta il numero di item nel set.
Nodo N1 Count Classe 0 1 Classe 1 5 c1 Count c2 1 c4 1 c6 0 c2 Count c1 1 c3 1 c4 0 c6 0
Tabella 5.6: Da sinistra verso destra (a) un esempio di conteggio di istanze di un nodo di un classificatore binario; (b) il conteggio degli utenti condivisi dalla cella c1 con le rispettive celle limitrofe; (c) il conteggio degli utenti condivisi dalla cella c2 con le rispettive celle limitrofe
Esattamente come nei classificatori binari [27] un nodo può avere due classi di appartenenza e può essere espresso conteggiando le istanze appartenenti alla classe positiva e quella negativa, così in questo contesto si osservano le celle limitrofe ((c2,c4,c6)) come classi di appartenenza e il nodo di osservazione rappresenta la cella analizzata (c1), mentre il conteggio risultano essere gli utenti in comune. La Tabella 5.6 mostra la logica della trasformazione.
Con riferimento alla tabella 5.6, si noti come tra il conteggio degli utenti condivisi della cella c1 e il conteggio degli utenti condivisi della cella c2, il numero delle classi (celle limitrofe) sia diverso, sia quantitativamente (nel primo ci sono 3 classi, nel secondo caso ce ne sono 4), che qualitativamente. Questo succede perché la cella analizzata viene confrontata esclusivamente con le sue celle limitrofe, ciò porta a due considerazioni:
1. non tutte le celle hanno lo stesso numero di vicini
2. non è conveniente confrontare le celle con celle non limitrofe, sia per motivi computazionale, sia perché la feature derivata vuole incorporare la relazione fra la cella analizzata e il vicinato.
Nei classificatori binari si misura la bontà dello split attraverso l’entropia, quanto più le la probabilità di appartenenza di istanze a classi diverse è simile tanto più l’entropia sarà alta. Analogamente in questo contesto quando sussiste equiprobabilità fra classi(celle limitrofe) allora l’entropia sarà vicino a 1 viceversa 0. Se una cella ha entropia alta allora vorrà dire che direziona il proprio traffico in tutte le celle vicine, per converso se una cella ha entropia bassa vorrà dire che direziona il proprio traffico in poche celle vicine.
Disorder-ability significa proprio questo se la cella direziona il traffico sempre nella stessa direzione, oppure c’è maggiore disordine e quindi lo direziona in più celle limitrofe. La motivazione è spiegata di seguito. Supponiamo di avere una cella che direziona il traffico sempre nelle stesse celle limitrofe, conseguentemente avrà una disorder-ability bassa, supponiamo che in seguito a dei lavori il vicinato su cui si direziona il traffico sia bloccato, teoricamente quella cella direzionerà il proprio traffico in altre celle aumentando il proprio disordine. Vedremo in seguito come questo aumento anomalo potrà essere scoperto.
