Capitolo 1 Knowledge Discovery e Data Mining (KDD)

Capitolo 1

Knowledge Discovery e Data

Mining (KDD)

Il processo di Knowledge Discovery e Data Mining consiste nell'estrarre (mi-ning) conoscenza dai dati contenuti in un database di medie/grandi dimen-sioni. Tale processo è articolato in vari fasi:

• Data Cleaning - nella quale viene eliminato il rumore (noise) o i dati non rilevanti

• Data Integration - nella quale vengono combinati i dati provenienti da vari dataset

• Data Selection - nella quale si recuperano i dati, rilevanti per l'analisi da eettuare, dal database

• Data Transformation - nella quale i dati vengono trasformati o con-solidati in una forma appropriata (ad esempio utilizzando funzioni di aggregazione) per essere gestiti nella fase seguente di Data mining • Data Mining - il processo essenziale di estrazione di conoscenza dai

dati che utilizza vari metodi volti ad individuare dei pattern nel dataset • Pattern Evaluation - nella quale si identicano i pattern realmente interessanti - fra quelli individuati nella fase precedente - rispetto ad alcune misure di interesse, relativamente al nostro processo di analisi • Knowledge Presentation - nella quale si utilizzano graci, immagini

e tecniche per presentare i risultati ottenuti dall'analisi, agli utenti. 1

1.1 Dataset

Per lo svolgimento dei nostri esperimenti abbiamo fatto uso di vari dataset:

OctoTelematics

OctoTelematics è il dataset principale che abbiamo utilizzato nella nostra analisi e contiene per ogni utente (precedentemente reso anonimo) le traiet-torie che ha seguito con la propria auto. La traiettoria è descritta tramite una sequenza di tratte memorizzate nel database una per ogni record. In par-ticolare per ogni tratta di una traiettoria è indicato l'utente, il timestamp di inizio e quello di ne e le due zone di partenza e di arrivo. Per quan-to riguarda la zona, ne abbiamo considerate due tipi: sezione istat e zona di mobilità (aleph) [?]; la prima largamente conosciuta e la seconda rappre-senta un'aggregazione di sezioni istat che ci è stata gentilmente fornita da un'azienda, la Aleph S.r.l. appunto, che si occupa di ingegneria dei trasporti e pianicazione territoriale e con cui l'ISTI-CNR di Pisa ed in particolare il KDDLab[?] hanno una stretta collaborazione. Le informazioni necessarie per creare questo dataset ci sono state fornite dalla OctoTelematics[?], un'a-zienda che ha creato un sistema per il monitoraggio autostradale del traco OctoTelematics utilizzando esclusivamente i dati trasmessi dai dispositivi sa-tellitari dei propri clienti, nell'assoluto rispetto della privacy; anche questa azienda ha una stretta collaborazione con il KDDLab. Il dataset è ralativo ad un periodo di circa un mese (tra il 14 Giugno 2010 e il 19 Luglio 2010).

Aleph

Aleph è il dataset contenente le zone di mobilità, un aggregazione di sezioni istat creata utilizzando di informazioni sul traco veicolare della Toscana.

Istat

Istat è il dataset contenente le sezioni istat. Gli attributi presenti in questo dataset, relativi alla cella istat, sono l'identicativo, la geometria, la po-polazione, la zona aleph associata. Per ogni cella istat conosciamo anche una serie di attributi: codice regione, codice provincia, codice comune, sezione istat, regione, provincia, comune.

Comuni

Comuni è il dataset contenente i comuni della Toscana. Gli attributi presenti in questo dataset sono: identicativo comune, codice regione, codice provincia, nome comune, nome comune (italiano), nome comune (tedesco), geometria del comune.

Prima di poter utilizzare i dataset sopracitati nel nostro processo di Da-ta Mining, sono sDa-tate necessarie alcune delle fasi introdotte all'inizio del capitolo.

1.2 Data Preparation: Data Cleaning e Data

Integration

La fase di Data Preparation può essere suddivisa in due passi: Data Cleaning e Data Integration.

Nella fase di Data Cleaning è stato necessario decidere come trattare il ru-more, i valori anomali (outliers), i valori mancanti, i valori inconsistenti e i valori duplicati. Nelle sezioni seguenti sarà approfondito caso per caso come tali valori sono stati gestiti.

Per quanto riguarda la Data Integration è stato necessario combinare il da-taset octoTelematics, contenente le traiettorie veicolari, con il dada-taset con-tenente le zone di mobilità (aleph o istat). Questo ci ha permesso di visua-lizzare le traiettorie consentendoci di utivisua-lizzare degli strumenti per eettuare delle analisi; ad esempio per accorpare delle traiettorie a seconda della loro similarità, per individuare aree di passaggio comuni a più traiettorie, sele-zionare traiettorie rispetto a soglie spazio/temporali, identicare le aree di partenza/ne delle traiettorie, ecc.

Noise (rumore)

Il noise è una componente casuale dell'errore fatto durante la misurazione. Può coinvolgere la distorsione di un valore o l'aggiunta di falsi oggetti. Fin-ché il rumore rimane entro una certa soglia, che dipende dalle circostanze, i risultati dell'analisi non subiscono un'inuenza rilevante. Se, al contrario, il rumore è eccessivo questo ha ripercussioni su l'analisi stessa in quanto è mol-to problematico distinguerlo dai dati e quindi dicile da isolare e ridurre o eliminare. Esistono tecniche che permettono di ridurre il rumore, permetten-do quindi di individuare patters non identicati in precedenza perché coperti da questo. Tuttavia, l'individuazione del rumore è solitamente dicile ed un obiettivo del data mining è quello di ideare degli algoritmi robusti che permettono di ottenere risultati accettabili anche in presenza di rumore. Nel nostro caso il rumore oltre ad essere dovuto ad errori di acquisizione e ta-ratura degli strumenti di rilevazione, può derivare da una scelta erronea della soglia temporale utilizzata per separare una traiettoria da un altra. Facendo un'analisi statistica, utilizzando anche strumenti per valutare la similarità sia temporale che spaziale fra le traiettorie, abbiamo ricavato il valore ottimale per tale soglia. La soglia individuata permette di non frammentare troppo le traiettorie in tratte ma consente nello stesso tempo anche di non unire troppe

traiettorie in una sola traiettoria. La soglia individuata è stata approssimata a 30 minuti: entro tale intervallo di tempo le tratte percorse da un utente sono considerate relative una stessa traiettoria; oltre i 30 minuti, la tratta viene assegnata ad una nuova traiettoria.

Outliers

Gli outliers sono oggetti che, in qualche modo, hanno caratteristiche che sono dierenti dalla maggior parte degli altri oggetti del dataset; oppure valori di un attributo che sono inusuali rispetto ai tipici valori di quel dato attribu-to. Gli outliers sono riferiti quindi ad oggetti e valori anomali. Non è ben denito cosa si intenda con il termine outlier e nel campo della statistica e del data mining sono state proposte varie denizioni. E' importante però non confondere gli outliers con il rumore (noise): gli outliers possono essere oggetti o valori legittimi, quindi a dierenza del rumore gli outliers possono essere interessanti. Ad esempio gli outliers sono molto utilizzati per indi-viduare le frodi e le intrusioni, in quanto l'obiettivo è quello di scoprire gli eventi inusuali fra tutti quelli normali.

Nel nostro caso gli outliers corrispondono a traiettorie, dei veicoli octoTele-matics, che non sono comuni a molti utenti. Essendo i dati utilizzati nell'a-nalisi cumulativi, per preservare la privacy degli utenti, gli outliers saranno caratterizzati da un numero molto ridotto di traiettorie fra due aree di mo-bilità. Ai ni della nostra analisi tali valori, pur non essendo da confondere con il rumore, saranno comunque poco signicativi in quanto inuenzeranno solo marginalmente i conni derivati a partire dalla mobilità veicolare.

Valori mancanti

Non è inusuale per un oggetto avere uno o più attributi mancanti. Il alcuni casi, l'informazione non è stata collezionata (ad esempio attributi come il peso e l'età spesso non sono dichiarati dalle persone). In altri casi, alcuni attributi non sono applicabili a tutti gli oggetti (ad esempio in alcuni form ci sono delle parti che sono opzionali ma che, per semplicità, vengono memorizzati tutti i campi). Nonostante tutto, durante il processo di analisi si dovrebbe tenere conto di tali valori mancanti. Ci sono varie strategie per trattare i valori mancanti, la scelta appropriata dipende dalle circostanze. Le strategie sono elencate nei paragra seguenti, indicando per ciascuna i vantaggi e gli svantaggi.

Nel nostro caso, eventuali valori mancanti, dovuti ad esempio a problemi di acquisizione dei dispositivi installati sui veicoli, possono essere trattati in vari modi a seconda della rilevanza dell'attributo mancante e alla possibilità di poterlo stimare.

In particolare tali oggetti possono essere:

• eliminati se senza tali attributi non è possibile ricostruire una traiet-toria o almeno una parte di essa (tratta).

• stimati se i dati mancanti sono riferiti ad una traiettoria intermedia, che può essere inferita a partire dalla tratta precedente e successiva, considerando anche le traiettorie simili percorse nei giorni precedenti e successivi a tale data.

• ignorati se gli attributi mancanti non inuenzano notevolmente il tipo di analisi che si vuole fare, ad esempio in caso di clusterizzazione, non possono mancare gli attributi utilizzati nella funzione di distanza.

Eliminare gli Oggetti o gli Attributi mancanti

Una semplice ed ecace strategia è eliminare gli oggetti che hanno valori mancanti. Tuttavia, anche gli oggetti con attributi specicati solo parzial-mente, contengono delle informazioni e se ci sono molti oggetti con valori mancanti allora l'analisi ottenuta eliminando tutti questi oggetti potrebbe non essere signicativa o addirittura non possibile. Se, contrariamente, ci sono pochi oggetti con valori mancanti, l'eliminazione di tali oggetti non ha ripercussioni sull'analisi. Una strategia analoga consiste nell'eliminazione degli attributi che hanno valori mancanti, ma anche in questo caso bisogna far attenzione nell'eliminare tali attributi in quanto potrebbero inuenzare l'analisi.

Stima dei Valori mancanti

A volte i valori mancati possono essere stimati in modo attendibile. Per esempio, consideriamo una serie temporale che cambia in modo ragionevol-mente regolare ma che presenta pochi valori mancanti distribuiti su larga scala. In questi casi, i valori mancanti possono essere stimati (interpolati) utilizzando gli altri elementi. In questa situazione, il valore dell'attributo, dell'elemento più vicino all'elemento che ha il valore mancante, è utilizzato

per dare un valore all'attributo mancante. Nel caso in cui l'attributo sia continuo, si considera la media dei valori degli attributi degli elementi vicini; se l'attributo è categorico, allora si prende il valore dell'attributo che occorre più comunemente. Come esempio concreto immaginiamo di considerare il numero di precipitazioni che sono state registrate dalle stazioni meteo. Per le aree che non hanno stazioni meteo le precipitazioni possono essere stimate usando i valori osservati nelle stazioni meteo vicine.

Ignorare i Valori mancanti durante l'analisi

Molti processi di Data Mining possono essere modicati per ignorare i valori mancanti. Per esempio, supponiamo di avere degli oggetti da clusterizzare e che sia necessario calcolare la similarità fra coppie di oggetti. Se uno o entrambi gli oggetti di una coppia hanno valori mancati per alcuni attributi, allora la similarità può essere calcolata utilizzando solo gli 'attributi che non hanno il valori mancanti. E' vero che in tal caso la similarità sarà approssimativa, ma a meno che il numero di attributi sia piccolo o il numero dei valori mancanti sia alto, il grado di accuratezza non sorirà molto tale approssimazione. Con questo procedimento, molti schemi di classicazione possono essere modicati per tenere conto dei valori mancanti.

Valori inconsistenti

Il dataset può contenere valori inconsistenti. Consideriamo ad esempio un campo indirizzo che contiene il c.a.p. e la città, ma che il c.a.p. indicato non sia relativo a quella città. Il motivo di questa inconsistenza potrebbe essere dovuto al fatto che la persona che ha inserito i dati abbia invertito due cifre del c.a.p. oppure ad un errore nella scansione del form scritto a mano. Indipendentemente dalla causa del valore inconsistente, è importante individuare l'errore e se possibile correggerlo. Alcuni tipi di inconsistenze sono semplici da individuare, per esempio, l'altezza di una persona dovrebbe essere non negativa. In altri casi, potrebbe essere necessario consultare delle informazioni esterne, ad esempio, quando una compagnia di assicurazioni esegue una richiesta di rimborso, confronta il nome e l'indirizzo del form per il rimborso con quelli presenti nel proprio database dei clienti. Una volta che una inconsistenza è stata individuata, alcune volte è possibile correggere i dati erronei. Per inserire un codice prodotto si potrebbe controllarne l'esattezza rispetto ad un lista di codici prodotto e suggerire il codice prodotto più simile durante la digitazione. La correzione di una inconsistenza richiede informazioni addizionali o ridondanti.

Nel nostro caso, quando individuavamo dei valori inconsistenti nei dataset che ci hanno fornito, non essendo in possesso di informazioni aggiuntive per correggere tali inconsistenze, le abbiamo fatte presente alle azienda che hanno raccolto tali dati.

Valori duplicati

Un dataset può includere oggetti duplicati. Per individuare e eliminare i du-plicati, bisogna tener presente due cose. Primo, se ci sono due oggetti che in realtà rappresentano uno stesso oggetto, allora potrebbero esserci degli attri-buti corrispondenti con valore dierente e questi valori inconsistenti devono essere corretti. Secondo, bisogna far attenzione per evitare di combinare i da-ti di due oggetda-ti che sono simili ma non duplicada-ti, come due persone disda-tinte con lo stesso nome. Il termine deduplication è spesso usato con riferimento a queste due questioni. In alcuni casi, due o più oggetti sono identici rispet-to agli attributi presenti nel database ma, in realtà, rappresentano oggetti dierenti. In questi casi i duplicati sono legittimi ma questo può causare problemi con alcuni algoritmi se non è stata data la possibilità, in fase di progetto, di trattare oggetti identici.

Figura 1.2: Esempio di geometria perfetta

Nel nostro caso i valori inconsistenti sono dovuti all'utilizzo di oggetti geo-metrici che hanno una geometria imperfetta, ossia i bordi delle aree non coincidono esattamente (vedi Figura 1.1), questo se per una rappresentazio-ne topologica non crea grossi problemi, a livello numerico, dovendo fare delle intersezioni, delle unioni e considerare l'appartenenza di un punto ad una data regione, crea un'incongruenza nei dati. Il problema della geometria im-perfetta può essere dovuto anche ad una non corretta acquisizione dei dati dove le aree sono acquisite una alla volta indipendentemente l'una dall'altra senza considerare la correlazione fra esse. A tale problema si può, in generale, porre rimedio in due modi:

• controllando scrupolosamente, il processo di acquisizione, tramite stru-menti di editing e algoritmi specici (snap, completamento automatico, ecc.)

• intervenendo con software appositi che controllano e correggono "a po-steriori" un insieme di dati geometricamente non corretti. Questi stru-menti eseguono ulteriori operazioni sui dati come la costruzione della topologia.

La Figura 1.2 mostra la gura precedente in cui però è stata corretta la geometria.

Noi abbiamo potuto utilizzare solamente il secondo metodo avendo già a disposizione i dati acquisiti da terzi.

1.3 Data Consolidation: Data Selection e Data

Transformation

La fase di Data Consolidation può essere suddivisa in due passi: Data Selec-tion e Data TransformaSelec-tion.

La Data Selection consiste nel reperire dal database i dati di interesse per l'analisi che dobbiamo eettuare mentre la Data Transformation permette - appunto - di trasformare tali dati (ad esempio consolidandoli attraverso funzioni di aggregazione) in modo da renderli adatti ad essere gestiti nella fase successiva di Data Mining.

1.4 Data Mining

Per il nostro processo di Data Mining sono stati utilizzati due tradizionali algoritmi di clustering, il clustering gerarchico e OPTICS, un clustering basato sulla densità ed un algoritmo randomizzato, il Simulated Annealing. Come funzione obiettivo per tali algoritmi è stata adottata la modularità, una misura di dissimilarità che applicata ad un partizionamento dà un'indi-cazione di quanto questo sia "buono" in termine di numero di collegamenti che permette di preservare tra gli oggetti appartenenti ai vari moduli della partizione. Per una denizione dettagliata della modularità si rimanda alla Sezione ??, mentre nella Sezione ?? si prenderanno in considerazione i limiti della modularità e vedremo come è stato possibile superarli. Abbiamo consi-derato due tipi di aree in cui suddividere il territorio: sezioni istat e zone aleph. Le sezioni istat sono le zone in cui viene ripartito il territorio italia-no per eettuare i censimenti demograci e sondaggi mentre le zone aleph sono delle aggregazioni di sezioni istat eettuate da una azienda, la Aleph S.r.l.[?] sulla base delle informazioni relative al traco veicolare. Fondamen-tale è stata anche la scelta della funzione da utilizzare come similarità negli algoritmi di clustering e nel Simulated Annealing, in particolare ne abbiamo considerate sei tipi nei nostri esperimenti.. Nel Capitolo ?? saranno indicate le funzioni utilizzate spiegando nei dettagli le motivazioni che hanno portato a tali scelte.

Per quanto riguarda la metodologia utilizzata, abbiamo ripreso il metodo adottato nell'articolo The Structure of Borders in a Small World [?] da Brockmann ed altri, adattandolo in modo da poter essere utilizzato con il dataset di mobilità in nostro possesso.

1.5 Pattern Evaluation

In questa fase si utilizzano tipicamente delle misure per individuare, a par-tire dalla fase precedente (Data Mining), i pattern di interesse in modo da valutare i risultati ottenuti. Per ottenere buoni risultati è necessario che il modulo adibito all'individuazione e alla valutazione dei pattern interessanti abbia accesso al processo di Data Mining in profondità in modo da focaliz-zare la ricerca e la presentazione dei risultati della fase successiva solamente concentrandosi sui pattern interessanti. Per tale motivo a seconda del meto-do utilizzato per la fase di Data Mining, il Pattern Evaluatation può essere integrato nel modulo di Data Mining stesso.Tale fase è necessaria per iden-ticare i pattern o le regole realmente interessanti a partire dalle migliaia o spesso milioni generate potenzialmente dal processo di data mining. Infatti un dato utente è interessato solo ad una piccola frazione dei pattern generati, relativamente all'analisi che vuole svolgere. Per meglio capire cosa si inten-da per pattern interessante proviamo a individuare le caratteristiche che lo rendono tale. Un pattern è interessante se: 1) é facilmente comprensibile da un umano; 2) è valido rispetto a dati di test o nuovi con un certo grado di supporto e condenza; 3) potenzialmente utile per l'analisi che vogliamo eettuare; 4) nuovo, ossia non sia stato ricavato in precedenza. Un pattern è particolarmente interessante se conferma dei risultati ottenuti precedente-mente o delle ipotesi che si cerca di vericare, anche se risultasse in contrasto con questi, permette comunque di dare una interpretazione alternativa dei risultati ottenuti; un pattern deve, in qualche modo rappresentare la cono-scenza acquisita a partire dai dati. Esistono varie misure che permettono al processo di data mining di individuare i pattern potenzialmente interessanti, queste sono basate sulla struttura dei pattern trovati e su alcune statistiche che li riguardano. Una misura oggettiva per le regole di associazione della forma X ⇒ Y è il supporto, che rappresenta la percentuale del dataset che soddisfa la regola; un'altra misura oggettiva per le regole associative è la condenza, che valuta il grado di certezza della regola individuata ed è denita come la probabilità condizionata che un pattern Y sia vero dato un pattern X vero. Più formalmente il supporto e la condenza sono deniti come:

support(X ⇒ Y ) = P (X ∪ Y )

1.6 Knowledge Presentation

L'ultima fase del processo di knowledge discovery è la rappresentazione dei risultati ottenuti agli utenti. Solitamente esiste un modulo che fa da trami-te (intrami-terfaccia) fra l'utrami-tentrami-te e il data mining systrami-tem, permettrami-tendo all'utrami-tentrami-te di interagire tramite query o task e fornendo informazioni che lo aiutino a focalizzare la propria ricerca solo su determinati aspetti anche sulla base di ri-sultati intermedi ottenuti precedentemente. Inoltre tale modulo permette al-l'utente di navigare gli schemi del database e del data warehouse, la struttura dei dati e valutare i pattern individuati anche tramite varie visualizzazioni.