Tesina per il corso di Intelligenza · PDF fileTesina per il corso di Intelligenza Artificiale...

Tesina per il corso di Tesina per il corso di Intelligenza ArtificialeIntelligenza Artificiale

“ “ MissingMissing Data Data ManipulationManipulationwithwith MDT ”MDT ”

realizzato darealizzato da

Alfonso Isola & Filippo Alfonso Isola & Filippo GrassiaGrassia

Prof.Prof. IngIng. Alberto Faro. Alberto Faro

L’obiettivo del nostro lavoro è quello di effettuare uno L’obiettivo del nostro lavoro è quello di effettuare uno studio sulle più avanzate tecniche di manipolazionestudio sulle più avanzate tecniche di manipolazione

dei dati mancanti.dei dati mancanti.

Introduzione Introduzione (1.1)(1.1)

Spesso nei problemi reali di misurazione di grandezze Spesso nei problemi reali di misurazione di grandezze fisiche(elettriche,termiche,ecc.) si possono verificare dei fisiche(elettriche,termiche,ecc.) si possono verificare dei

malfunzionamenti dei dispositivi di misurazione malfunzionamenti dei dispositivi di misurazione (sensori,ecc.) a causa della loro usura o per l’azione di (sensori,ecc.) a causa della loro usura o per l’azione di agenti esterni , questo comporta la perdita di misure agenti esterni , questo comporta la perdita di misure

indispensabili per il monitoraggio in indispensabili per il monitoraggio in RealReal--TimeTime di un di un generico processo. generico processo.


Nel monitoraggio di un generico processo la fase di Nel monitoraggio di un generico processo la fase di PreprocessingPreprocessing dei dati è essenziale per la corretta dei dati è essenziale per la corretta

elaborazione dei dati misurati. elaborazione dei dati misurati. Quindi si rende necessario l’utilizzo di moderne tecniche Quindi si rende necessario l’utilizzo di moderne tecniche

di interpolazione in di interpolazione in RealReal--TimeTime dei dati mancanti. dei dati mancanti.


Questo è possibile mediante l’utilizzo di modernissimi Questo è possibile mediante l’utilizzo di modernissimi algoritmi e algoritmi e toolstools realizzati appositamente per queste realizzati appositamente per queste

problematiche. In particolare è stato di recente sviluppato problematiche. In particolare è stato di recente sviluppato un potente un potente toolboxtoolbox per per MatlabMatlab 6.5 (ed eventuali versioni 6.5 (ed eventuali versioni

successive) il quale permette di effettuare l’Interpolazione successive) il quale permette di effettuare l’Interpolazione dei dati mancanti mediante i metodi :dei dati mancanti mediante i metodi :


Interpolazione Lineare

Interpolazione Nearest NeighBour

Interpolazione Spline

Interpolazione Pchip

Interpolazione DRand

Interpolazione Som

Interpolazione Mlp


L’applicativo che permette tali elaborazioni è il L’applicativo che permette tali elaborazioni è il toolboxtoolbox ::

M.D.T.M.D.T.((MissingMissing Data Data ToolboxToolbox))

MissingMissing Data Data ToolboxToolbox (2.1)(2.1)

MissingMissing Data Data ToolboxToolbox (2.2)(2.2)

Riportiamo di seguito alcuniRiportiamo di seguito alcuni

confronti tra le interpolazioniconfronti tra le interpolazioni

possibili con il possibili con il ToolboxToolbox

MDT:MDT:

Esempio di StudioEsempio di Studio (3.1)(3.1)


Il Comune di Catania insieme con Il Comune di Catania insieme con OmnitelOmnitel hanno hanno sviluppato il primo progetto mondiale di monitoraggio sviluppato il primo progetto mondiale di monitoraggio

permanente dei campi elettromagnetici denominato permanente dei campi elettromagnetici denominato CassiopeaCassiopea; ; l’obiettivo è quello di attivare un servizio l’obiettivo è quello di attivare un servizio

semplice, affidabile, in grado di acquisire ed elaborare un semplice, affidabile, in grado di acquisire ed elaborare un insieme di dati comprensibili dalla cittadinanza, e di insieme di dati comprensibili dalla cittadinanza, e di fornire ai cittadini una maggiore informazione grazie fornire ai cittadini una maggiore informazione grazie all’apporto dei mass media; attraverso tali rilevazioni, all’apporto dei mass media; attraverso tali rilevazioni,

infatti, potrà essere verificata l’uniformità alla normativa infatti, potrà essere verificata l’uniformità alla normativa nazionale vigente dei livelli di campo elettromagnetico nazionale vigente dei livelli di campo elettromagnetico

presenti nell’area urbana.presenti nell’area urbana.


Il sistema consiste di 15 centraline di monitoraggio dei Il sistema consiste di 15 centraline di monitoraggio dei campi elettromagnetici in prossimità di luoghi ad alto campi elettromagnetici in prossimità di luoghi ad alto transito e all’interno di edifici pubblici e privati dove si transito e all’interno di edifici pubblici e privati dove si

possano verificare prolungate permanenze. I dati rilevati possano verificare prolungate permanenze. I dati rilevati dai siti di monitoraggio, in funzione 24 ore su 24, verranno dai siti di monitoraggio, in funzione 24 ore su 24, verranno quindi inviati attraverso la tecnologia GSM, ad un server quindi inviati attraverso la tecnologia GSM, ad un server gestito dal Comune di Catania che, a sua volta li renderà gestito dal Comune di Catania che, a sua volta li renderà

pubblici tramite i canali di informazione verso la pubblici tramite i canali di informazione verso la cittadinanza (internet, stampa,televideo, cittadinanza (internet, stampa,televideo, etcetc).).


Il sistema di monitoraggio CASSIOPEA Il sistema di monitoraggio CASSIOPEA èè composto da 10 composto da 10 postazioni indoor e da 5 postazioni outdoor. postazioni indoor e da 5 postazioni outdoor.

Le postazioni di misura sono state localizzate presso 8 Le postazioni di misura sono state localizzate presso 8 scuole elementari e/o materne,scuole elementari e/o materne, 1 scuola media, 3 parchi 1 scuola media, 3 parchi

gioco e/o giardini pubblici, 3 ospedali.gioco e/o giardini pubblici, 3 ospedali.Nella totalitNella totalitàà dei casi le sorgenti di emissione (in dei casi le sorgenti di emissione (in

particolare impianti di telefonia cellulare) siparticolare impianti di telefonia cellulare) si trovano "a trovano "a vista" rispetto alle postazioni dove sono collocati i sensori, vista" rispetto alle postazioni dove sono collocati i sensori, o comunque a distanze dell'ordine di poche centinaia di o comunque a distanze dell'ordine di poche centinaia di

metri.metri.


Un sistema di gestione dati, con unUn sistema di gestione dati, con un modem GSM modem GSM provvedono alla trasmissione periodica dei dati raccolti, provvedono alla trasmissione periodica dei dati raccolti,

mentre un appositomentre un apposito software di gestione archivia ed elabora software di gestione archivia ed elabora i dati acquisiti alli dati acquisiti all’’interno di un database Microsoft interno di un database Microsoft

Access.Access. I dati elementari che vengono raccolti per ogni I dati elementari che vengono raccolti per ogni stazione sono pari a 24 valoristazione sono pari a 24 valori orari giornalieri. Viene orari giornalieri. Viene

riportato come livello di riferimento quello pari a 6 V/m riportato come livello di riferimento quello pari a 6 V/m previsto come limiteprevisto come limite per i luoghi dove sostano persone per per i luoghi dove sostano persone per periodi superiori a 4 ore (Decreto Interministeriale nperiodi superiori a 4 ore (Decreto Interministeriale n.381.381 del del

10/9/1998). 10/9/1998).

Problema Problema (4.1)(4.1)

La postazione scelta per il nostro La postazione scelta per il nostro lavoro lavoro èè stata quella presente stata quella presente allall’’interno di Villa Bellini. Le interno di Villa Bellini. Le postazioni di rilevamento sono postazioni di rilevamento sono attrezzate con sensori (attrezzate con sensori (WavetekWavetekWandelWandel GoltermannGoltermannItaliaItalia modello EMR 30) con modello EMR 30) con campo di misura da 27 a 2000 campo di misura da 27 a 2000 MHzMHz. Può capitare per i motivi . Può capitare per i motivi precedentemente accennati che precedentemente accennati che vi siano mancanze di dati dovute vi siano mancanze di dati dovute a problemi di trasmissione dei a problemi di trasmissione dei dati del sistema GSM oppure a dati del sistema GSM oppure a malfunzionamenti del sensore malfunzionamenti del sensore succitato. succitato.

Problema Problema (4.2)(4.2)

La Direzione dello Sviluppo Sistemi Informati del Comune di La Direzione dello Sviluppo Sistemi Informati del Comune di Catania ci ha gentilmente fornito un database Access di Catania ci ha gentilmente fornito un database Access di misure relativo all’anno 1999, il quale presenta numerosi misure relativo all’anno 1999, il quale presenta numerosi dati mancanti. Il nostro studio consiste nello scegliere dati mancanti. Il nostro studio consiste nello scegliere

l’opportuna tecnica di interpolazione a seconda del tipo di l’opportuna tecnica di interpolazione a seconda del tipo di gap dei dati mancanti. Dove per tipo di “gap” intendiamo gap dei dati mancanti. Dove per tipo di “gap” intendiamo

la lunghezza dell’intervallo di dati mancanti. la lunghezza dell’intervallo di dati mancanti.

Formattazione Dati per MDTFormattazione Dati per MDT

Come detto le misure da elaborare sono memorizzate in Come detto le misure da elaborare sono memorizzate in Database Access. Per la loro elaborazione si è presentato il Database Access. Per la loro elaborazione si è presentato il

problema di dover convertire i dati in un formato problema di dover convertire i dati in un formato riconosciuto dall’MDT.riconosciuto dall’MDT.

Abbiamo realizzato un applicativo che svolgesse tale Abbiamo realizzato un applicativo che svolgesse tale funzione:funzione:

MDT MDT FileMakerFileMaker

MDT MDT FileMakerFileMaker (5.1)(5.1)


La funzione di questo applicativo è quella di inserire il La funzione di questo applicativo è quella di inserire il tagtagdi dato mancante (es. di dato mancante (es. NaNNaN) all’interno del file testo che ) all’interno del file testo che

verrà elaborato successivamente dall’MDT, e inoltre verrà elaborato successivamente dall’MDT, e inoltre permette di creare un file di Log in cui sono presenti date e permette di creare un file di Log in cui sono presenti date e orari in cui si sono verificate anomalie di orari in cui si sono verificate anomalie di funzionamentodelfunzionamentodel

sistema di misura o di trasmissione. Come illustrato di sistema di misura o di trasmissione. Come illustrato di seguito:seguito:


In figura In figura èè mostrato il mostrato il database Access database Access contenente le misure , contenente le misure , come si vede viene come si vede viene evidenziato un intervallo evidenziato un intervallo di misure mancanti da di misure mancanti da interpolare.interpolare.


Nella figura accanto si Nella figura accanto si riporta il risultato riporta il risultato ottenuto mediante ottenuto mediante ll’’elaborazione con MDT elaborazione con MDT FileMakerFileMaker , sotto si , sotto si riporta il relativo file di riporta il relativo file di Log.Log.

Grafico delle Misure Grafico delle Misure (6.1)(6.1)

Riportiamo di seguito il grafico delle misure non interpolate:Riportiamo di seguito il grafico delle misure non interpolate:

Grafico delle Misure Grafico delle Misure (6.2)(6.2)

Riportiamo di seguito uno zoom delle misure non interpolate Riportiamo di seguito uno zoom delle misure non interpolate nella fascia peggiore (Giugno 1999):nella fascia peggiore (Giugno 1999):

Tecniche di InterpolazioneTecniche di Interpolazione (7.1)(7.1)

Ecco la pagina di impostazione delle tecniche di Ecco la pagina di impostazione delle tecniche di interpolazione presenti in MDT:interpolazione presenti in MDT:


Interpolazione LineareInterpolazione Lineare

““L’interpolazione lineare è il procedimento mediante il quale si L’interpolazione lineare è il procedimento mediante il quale si calcola il valore di una grandezza y, dipendente da un’altra calcola il valore di una grandezza y, dipendente da un’altra

grandezza x, in corrispondenza di valori della x (x1,………, grandezza x, in corrispondenza di valori della x (x1,………, xnxn) diversi da ) diversi da quelli per i quali sono noti i valori di y (y1,………, yn)”.quelli per i quali sono noti i valori di y (y1,………, yn)”.

In senso stretto, il termine interpolazione indica il calcolo diIn senso stretto, il termine interpolazione indica il calcolo di valori di y per valori di y per valori di x “compresi” tra i valori anzidetti. Se si pensa x, y valori di x “compresi” tra i valori anzidetti. Se si pensa x, y come come coordinate cartesiane, il problema dell’interpolazione si traduccoordinate cartesiane, il problema dell’interpolazione si traduce e

graficamente nel problema di tracciare una curva “regolare”, detgraficamente nel problema di tracciare una curva “regolare”, detta curvata curvainterpolatrice, passante per i punti di coordinate (interpolatrice, passante per i punti di coordinate (xixi, , yiyi). ).


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione lineare dei dati :l’interpolazione lineare dei dati :


Interpolazione Interpolazione SplineSpline

L'interpolazione mediante L'interpolazione mediante SplineSpline prevede un approccio prevede un approccio diverso al problema dell'interpolazione. Le diverso al problema dell'interpolazione. Le SplineSpline sono sono funzioni polinomiali a tratti che interpolano quindi la funzioni polinomiali a tratti che interpolano quindi la funzione tenendo fisso il grado del polinomio ma funzione tenendo fisso il grado del polinomio ma dividendo l'intervallo di interpolazione in intervalli più dividendo l'intervallo di interpolazione in intervalli più piccoli e considerando un polinomio diverso per ognuno piccoli e considerando un polinomio diverso per ognuno di questi sottointervalli. di questi sottointervalli.


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione l’interpolazione SplineSpline dei dati :dei dati :


Interpolazione Interpolazione DRandDRand

L'interpolazione mediante L'interpolazione mediante DRandDRand prevede un approccio prevede un approccio del tutto casuale al problema dell'interpolazione. I dati del tutto casuale al problema dell'interpolazione. I dati mancanti vengono sostituiti da valori creati all’interno del mancanti vengono sostituiti da valori creati all’interno del range delle misure.range delle misure.


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione l’interpolazione DRandDRand dei dati :dei dati :


Interpolazione PChipInterpolazione PChip

Questo tipo di interpolazione viene effettuata sfruttando iQuesto tipo di interpolazione viene effettuata sfruttando il l Polinomio di Polinomio di HermiteHermite , note alcune misure permette di , note alcune misure permette di ricavare i dati mancanti.ricavare i dati mancanti.Riportiamo di seguito la formula del Polinomio di Riportiamo di seguito la formula del Polinomio di HermiteHermite::


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione Pchip dei dati :l’interpolazione Pchip dei dati :


Interpolazione Interpolazione NearestNearest NeighbourNeighbour

L'interpolazione mediante L'interpolazione mediante NearestNearest NeighbourNeighbour effettua un effettua un interpolazione dei punti utilizzando il valore del punto di interpolazione dei punti utilizzando il valore del punto di dati più vicino. Perciò, questo metodo non genera punti di dati più vicino. Perciò, questo metodo non genera punti di dati nuovi.dati nuovi.


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione l’interpolazione NearestNearest NeighbourNeighbour dei dati :dei dati :


Interpolazione MLP (Interpolazione MLP (MultilayerMultilayer PerceptronPerceptron))

Un multilayer perceptron è un esempio di rete con uno o piu strati di neuroni tra i nodi input e quelli output (unità

nascoste o hidden units). Lo strato nascosto riceve gli ingressi dallo strato precedente, e dipendentemente

dai pesi produce un’uscita che prosegue nello strato successivo. Per quanto riguarda il numero di nodi da

inserire, in linea generale, i neuroni dello strato nascosto devono essere almeno quante sono le classi di input

presentate durante l’apprendimento.


Ogni neurone ha un’uscita non lineare continua, data dalla funzione sigmoidale , essa è necessaria per correggere gli errori durante l’apprendimento.


L’aumento delle potenze di calcolo degli elaboratori risvegliò l’interesse, negli anni ottanta, verso queste reti. Si riuscì

infatti ad applicare con successo l’algoritmo di apprendimento del tipo “backpropagation”, ancora oggi

uno dei metodi più utilizzati. L’apprendimento è il processo mediante il quale vengono determinati i

parametri di una rete. Si può distinguere tra apprendimento “supervisionato” e apprendimento “non

supervisionato”.


Nel primo caso i parametri vengono costruiti sulla base di un insieme di esempi (il training set) consistenti in

coppie di ingresso/uscita desiderate. Lo scopo dell’addestramento è quello di costruire un modello del processo che genera i dati. Nel secondo caso la rete è dotata di una capacità di auto-organizzazione ed è in

grado di classificare gli ingressi autonomamente. il caso delle reti neurali di Kohonen (Mappe SOM) , che

verranno analizzate nel seguito.Noi abbiamo invece utilizzato entrambe le tecniche per effettuare

l’interpolazione delle misure mancanti.


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione MLP dei dati :l’interpolazione MLP dei dati :


Interpolazione mediante Mappe SOMInterpolazione mediante Mappe SOM

Nell’esempio del perceptron, e nelle reti da esso derivate, era necessaria l’implementazione di un insegnante che

sapesse a priori la classificazione dei pattern di input nel training set. L’obiettivo era quindi la generalizzazione da

questi ad altri input mai analizzati esplicitamente, lasciando il compito alla rete di decidere la risposta più corretta. Nelle reti di tipo non supervisionato, si lascia il compito alla rete stessa di ricercare una classificazione

logica dei dati di ingresso.


Le Reti di Kohonen (T. Kohonen, 1983) nascono dallo studio della topologia della corteccia del cervello

umano. Queste reti tengono conto non solodelle connessioni sinottiche tra neuroni ma anche dell’influenza che può avere un neurone sul vicino.

stato osservato che, nel caso biologico, i neuroni chesono fisicamente vicini a neuroni attivi hanno i legami

più forti, mentre quelli ad una particolare distanza hanno legami inibitori.


A questa caratteristica Kohonen attribuisce uno sviluppo nella capacità di realizzare delle mappe topologiche (ovvero che mantengono le relazioni di vicinanza)

localizzate nel cervello. Questa caratteristica è stata modellata da Kohonen restringendo la variazione dei

pesi soltanto ai neuroni giudicati “vicini” ad un neurone.


Una rete di Kohonen è costituita da una serie di neuroni di input (come per le reti multi-strato) e da una griglia n-

dimensionale di neuroni. Ciascun neurone di input è connesso a tutti i neuroni della griglia: la risultante

matrice dei pesi viene usata per propagare l’ingresso della rete ai neuroni della mappa. Inoltre, tutti i neuroni della mappa sono connessi tra loro. Queste connessioni servono per influenzare i neuroni adiacenti al neurone

con la più alta attivazione, dipendentemente dalla distanza da esso.


Riportiamo di seguito i risultati ottenuti effettuando Riportiamo di seguito i risultati ottenuti effettuando l’interpolazione Mappe SOM dei dati :l’interpolazione Mappe SOM dei dati :

ConclusioniConclusioni (8.1)(8.1)

Da un attenta analisi dei dati , abbiamo notato che i risultati ottenuti utilizzando le varie tecniche

d’interpolazione variano a seconda del gap di dati presente nelle misure. Ciò vuol dire che prima di

utilizzare una qualunque tecnica d’interpolazione è necessario capire quale sia la tecnica migliore da

applicare a seconda dei tipi di gap presenti all’interno dei nostri dati reali.

ConclusioniConclusioni (8.2)(8.2)

Abbiamo effettuato una classificazione del gap in:

• Corto (gap di ampiezza inferiore a 4 misure mancanti)• Medio (gap di ampiezza tra 4 e 20 misure mancanti) •• Lungo (gap di ampiezza superiore a 20 misure mancanti)Lungo (gap di ampiezza superiore a 20 misure mancanti)

N.B. Le ampiezze di tali gap si possono considerare variabili a secondo del problema reale affrontato.

Conclusioni Conclusioni (8.3)(8.3)

Gap CortoGap Corto

Dalle prove effettuate abbiamo notato che in questi casi si possono ritenere soddisfacenti i risultati ottenuti con tutte le tecniche di interpolazione prese in considerazione, fatta eccezione per l’interpolazione lineare la quale risulta soddisfacente nei casi più banali.


Gap LungoGap Lungo

Dalle prove effettuate abbiamo notato che in questi casi solo alcune tecniche più sofisticate di interpolazione come quella delle Mappe Som e del MLP permettono di ottenere risultati sufficenti. Comunque il fatto che i risultati si possano considerare sufficenti dipende fortemente dal caso reale che si sta studiando.


Gap MedioGap Medio

Nel nostro problema reale per questo tipo di gap abbiamo ottenuto ottimi risultati con le tecniche di interpolazione mediante Mappe Som , MLP e Pchip.

Sviluppi FuturiSviluppi Futuri

Quanto trattato nel nostro lavoro , ovvero la possibilità dipotere scegliere la tecnica di interpolazione più corretta a

secondo del tipo di gap , è possibile implementarlo modificando l’applicativo MDT FileMaker da noi

realizzato. Più precisamente si potrebbe realizzare una funzione che effettui una scansione delle misure reali e

consigli a seconda dei casi la migliore tecnica di interpolazione da eseguire. Oppure realizzare una

funzione che sezioni l’insieme delle misure utilizzando per lo stesso set di dati più tecniche d’interpolazione (se

necessario).

RingraziamentiRingraziamenti

Approfittiamo per ringraziare la Direzione dello Sviluppo a Direzione dello Sviluppo Sistemi Informati del Comune di Catania che ci ha Sistemi Informati del Comune di Catania che ci ha

gentilmente fornito le misure da elaborare.gentilmente fornito le misure da elaborare.

Tesina per il corso di Intelligenza · PDF fileTesina per il corso di Intelligenza Artificiale...

Documents

Transcript of Tesina per il corso di Intelligenza · PDF fileTesina per il corso di Intelligenza Artificiale...