Timeslice Cluster e Moving Cluster

Come accennato in precedenza l’analisi per l’individuazione di Moving Cluster (MC) pu`o partire dai risultati ottenuti dall’analisi precedente.

Prima di effettuare la ricerca vera e propria per`o `e necessario compiere un passo intermedio, questo perch´e con l’analisi precedente abbiamo individuato le zone dense, ma ogni cubo minimale `e fondamentalmente indipendente dagli altri. Quello che dobbiamo fare adesso `e una sorta di clusterizzazione dei cubi minimali che appartengono allo stesso intervallo temporale, ovvero individuare quei cluster che abbiamo denominato Timeslice Cluster.

La tecnica che abbiamo adottato per individuare i cluster appartenenti allo stesso timeslice `e una tecnica a “dispersione”, ovvero scelto un cubo denso all’interno di un intervallo temporale, si controlla se esistono cubi adiacenti che sono a loro volta densi.

Se tali cubi vengono individuati allora tutti i cubi minimali coinvolti en- trano a far parte di uno stesso insieme che rappresenta il cluster individuato.

60 3.3 Moving Cluster

Se poi, continuando la ricerca, si troveranno altri cubi densi adiacenti a quelli che formano il cluster, essi andranno ad aggiungersi a quelli individuati in precedenza.

Questa tecnica di clusterizzazione pu`o essere considerata come un’ap- prossimazione del risultato che si potrebbe ottenere effettuando clustering con DBSCAN nell’intervallo temporale dei cubi minimali.

Come DBSCAN inserisce nello stesso cluster un oggetto ed quelli che si trovano nel suo -intorno (purch´e in numero maggiore di MinPts), cosi il nostro algoritmo considera tutte le traiettorie appartenenti allo stesso cubo come facenti parte dello stesso cluster. Ma se due cubi sono adiacenti significa che esistono due cluster adiacenti, che data la loro prossimit`a possono essere considerati come facenti parte del medesimo cluster.

Lo stesso processo pu`o essere applicato a tutti i cubi minimali densi che sono adiacenti al cluster appena individuato, formando cos`ı un cluster di dimensioni ancora maggiori, ecc.

Si pu`o comprendere facilmente inoltre che tale metodo ci permette di individuare anche cluster di forma arbitraria.

I controlli necessari per fare questa aggregazione si rivelano abbastanza semplici se si predispongono le strutture dati appropriate. Abbiamo visto che durante la fase di inizializzazione della Cube Analysis, veniva calcolato il numero di cubi di dimensione minima che era possibile disporre lungo tutti e tre gli assi. Con queste informazioni `e possibile creare una numerazione fittizia in modo da sapere qual’`e la posizione del cubo minimale all’interno del cubo iniziale ed individuare velocemente i cubi adiacenti. Ad ogni cubo minimale quindi pu`o essere assegnato una sorta di “indirizzo”.

Se durante l’analisi della densit`a si ha l’accortezza di mantenere aggior- nata una lista di booleani, che chiameremo Lista di Presenza, in cui il va- lore all’indice i restituisca vero se l’i-esimo cubo `e denso, falso altrimenti, l’individuazione dei cluster non `e altro che la navigazione di questa lista.

Posto che Nt,Nx,Ny siano i numeri di cubi di dimensione minima che possono essere posizionati lungo i tre assi.

Dalla lista dei Cubi Minimi, creata durante la Cube Analysis, si estra un cubo denso, il cui “indirizzo” poniamo essere i. Per controllare la presenza o meno di altri cubi densi adiacenti, sar`a sufficiente andare a controllare nella Lista di Presenza i valori booleani contenuti negli indici: i-1, i+1, i+Nx, i-Nx; Gli cubi densi raggiunti, che non sono stati ancora visitati, vengono inseriti in una lista, da cui verr`a estratto il cubo successivo per proseguire l’analisi.

61 3.3 Moving Cluster

Figura 3.10: Individuazione Cluster tramite dispersione.

tit`a appena individuata, vengono conservate in un vettore per essere recu- perate in una fase successiva. Quando l’individuazione dei cluster per ogni timeslice `e terminata, si pu`o effettuare la ricerca di eventuali MCs.

Innanzitutto andr`a recuperato il parametro settato dall’ utente che indica il rapporto che deve essere mantenuto tra gli elementi dei cluster di timeslice consecutive, per poter essere definito il MC.

In seguito, a partire dalla prima timeslice, si selezioner`a un cluster e si andr`a a ricercare, nella timeslice successiva, la presenza o meno di un cluster che soddisfi la formula vista in 3.1. Di ogni cluster tramite le informazioni sui cubi minimi, sar`a possibile recuperare la lista delle traiettorie che contiene, da confrontare con quella del cluster del timeslice successivo.

Se, applicando la 4.1 su tali liste di elementi, la soglia impostata dall’u- tente `e soddisfatta, i due cluster entrano a far parte dello stesso MC. Se si individua un MC tra due Timeslice Cluster, e quello della timeslice preceden- te faceva gi`a parte di un MC, significa che a tale MC dovr`a essere aggiunto un’ulteriore elemento, il Timeslice Cluster della timeslice successiva.

A seguire sono mostrate tre immagini che rappresentano la sequenza delle analisi svolte: nella prima immagine `e riportato un dataset sintetico formato da 1000 traiettorie, costruito tramite il generatore di dataset sintetici di cui parleremo brevemente nel prossimo capitolo, nella seconda immagine invece `e visualizzato il risultato dell’analisi dinamica approssimata, ed infine nell’ulti- ma immagine `e rappresentato il risultato dell’analisi per l’individuazione dei MCs.

62 3.3 Moving Cluster

Figura 3.11: Visualizzazione Dataset da Analizzare

63 3.3 Moving Cluster

Capitolo 4

Test e valutazioni

In questo capitolo illustreremo le prove sperimentali che abbiamo effet- tuato allo scopo di testare il nostro metodo di analisi. I test effettuati sono stati eseguiti per valutare la correttezza dei risultati ottenuti nonch´e i livelli di performance.

Poich´e durante il percorso effettuato sono state implementate tre versio- ni dello stesso metodo, quello Statico, quello Dinamico e quello Dinamico Approssimato, ci `e sembrato opportuno paragonare i risultati ottenuti. Al termine di ogni test, o gruppo di test, abbiamo cercato di mettere in evidenza eventuali fenomeni significativi.

Il capitolo inizier`a con la descrizione dei dataset utilizzati per fare i te- st. Verranno poi illustrati i test effettuati, spiegando le motivazioni che ci hanno spinto ad effettuare ognuno di essi, e verranno mostrati i risultati. In particolare verranno effettuati test per valutare la completezza dei risultati forniti dal metodo e i livelli di performance ottenuti.

Il capitolo si concluder`a mettendo in evidenza alcune problematiche che sono sorte durante la fase di test, e le soluzioni adottate per porvi rimedio.

4.1

Descrizione del Dataset

Al termine della fase di sviluppo del metodo siamo passati ad effettuare tutta una serie di prove per verificare se le soluzioni proposte portassero ad ottenere dei risultati significativi, ma soprattutto osservare se, concretamen- te, le migliorie proposte tra le varie versioni per aumentare l’efficienza del metodo a livello computazionale avessero l’effetto desiderato, e se si, in che quantit`a.

65 4.1 Descrizione del Dataset