Introduzione
Presentazione del problema
La compartimentazione (suddivisione) geogra ca delle mappe in unità terri-toriali coerenti è essenziale, non solo per la gestione e la distribuzione delle competenze amministrative e l'assegnazione delle risorse pubbliche, ma anche come un importante quadro di riferimento per comprendere una serie di feno-meni legati all'attività umana. Le frontiere esistenti sono spesso correlate ai con ni culturali e linguistici o a caratteristiche topogra che; rappresentano fattori essenziali nel trasferimento tecnologico e commerciale e hanno indi-rettamente modellato l'evoluzione dei processi dinamici dell'umanità come la propagazione di malattie infettive emergenti. La maggior parte degli attuali con ni amministrativi e politici, ad esempio negli Stati Uniti ed in Europa, si è evoluto nel corso dei secoli e si è tipicamente stabilizzato molti decenni fa, in un momento in cui le interazioni fra le persone relative alla mobilità era-no prevalentemente locali e l'ampia separazione geogra ca della popolazione umana in una gerarchia di aree geogra camente coerenti era signi cativa e plausibile. Tuttavia la moderna comunicazione umana e la mobilità hanno subito enormi cambiamenti strutturali negli ultimi decenni. E centi reti di comunicazione, su larga scala, l'ampia diusione delle reti sociali e lunghi viaggi sempre più accessibili hanno generato modelli (pattern) di connetti-vità molto complessi tra gli individui della popolazione umana. Sebbene la prossimità geogra ca ancora domini le attività umane, aumentando le inte-razioni su lunghe distanze e attraverso frontiere culturali e politiche si ha un'ampli cazione dell'eetto small world e una diminuzione dell'importanza relativa delle interazioni locali.
Introduzione 3
Contenuto della tesi
In questa tesi mostreremo come sia possibile ride nire i con ni territoriali utilizzando le informazioni di mobilità - nel nostro caso relative al tra co veicolare della Toscana. Per fare questo tipo di analisi, abbiamo utilizzato tre algoritmi: clustering gerarchico (si veda la sezione ??), OPTICS (si veda la sezione ??) e Simulated Annealing (si veda il capitolo ??). I primi due algoritmi sono largamente utilizzati nell'ambito del Data Mining per suddi-videre insieme di oggetti in partizioni; il Simulated Annealing invece è un algoritmo probabilistico utilizzato per risolvere problemi di ottimizzazione, iterando per cercare di migliorare la soluzione corrente rispetto ad una data metrica. Per calcolare la distanza fra gli oggetti - nel nostro caso aree di mobilità - richiesta dagli algoritmi di clustering per decidere come eettuare la suddivisione, abbiamo utilizzato varie misure di dissimilarità. Tali misu-re considerano il usso veicolamisu-re tra coppie di amisu-ree (origine e destinazione), in termini di numero di traiettorie che intercorrono fra queste; tengono di conto della popolazione, della densità di popolazione o della distanza fra due aree, misurata rispetto ai centroidi o ai bordi delle aree. Come funzione obiettivo da massimizzare, abbiamo scelto di utilizzare la modularità; questa solitamente viene usata come indicatore per quanti care la bontà di una par-tizione ottenuta, ma invece nel nostro metodo avrà un ruolo fondamentale per cercare di ottenere il partizionamento ottimale.
Introduzione 4
Organizzazione della tesi
Nel capitolo ?? consideriamo alcuni articoli, presenti in letteratura, che trat-tano temi analoghi a quello oggetto della tesi, ne descriveremo brevemente il contesto, la metodologia utilizzata e i risultati ottenuti. Nel capitolo ?? descriveremo i dataset utilizzati per la nostra analisi, le problematiche e le assunzioni fatte e le varie fasi del processo di Knowledge Discovery e Data Mining. Nel capitolo ?? viene presentata una classi cazione degli algoritmi di clustering, evidenziando i punti di forza e di debolezza, inoltre si mostrano le tipologie di cluster identi cati in letteratura. Verranno poi approfonditi maggiormente i due algoritmi considerati: OPTICS e clustering gerarchico. Il capitolo ?? introduce l'algoritmo del Simulated Annealing, che è un ria-dattamento dell'algoritmo di Metropolis-Hastings.; in questo capitolo viene introdotta anche la modularità, spesso utilizzata come indicatore per quan-ti care la bontà di un partizionamento, ma che invece nel nostro metodo avrà un ruolo centrale essendo la metrica utilizzata dall'algoritmo del Simu-lated Annealing per determinare il partizionamento ottimale. Si rimanda alla Sezione ?? per avere maggiori informazioni sulla modularità, mentre nella Se-zione ?? si prenderanno in consideraSe-zione i limiti della modularità e vedremo come è possibile superarli. Gli esperimenti da noi svolti per determinare la metodologia proposta, a partire dalle informazioni di mobilità in nostro pos-sesso, e i risultati ottenuti applicando tale metodologia, saranno mostrati e analizzati nel capitolo ??.
