2
Capitolo 1
Introduzione
In questa tesi si affronta il problema della predizione di caratteristiche numeriche e
categoriche misurate da una rete di sensori. Il contesto applicativo di riferimento è
quello di una rete di sensori. L'obiettivo del lavoro di tesi è definire un algoritmo di
stream data mining per l'apprendimento di modelli di predizione per dati numerici
e/o categorici che consideri la dimensione spaziale della rete e la dimensione
temporale del flusso (stream). Al riguardo è stato sintetizzato un algoritmo per
l'induzione di alberi in data stream spazialmente distribuiti.
Reti di sensori : cenni generali
Una rete di sensori è un insieme di dispositivi elettronici autonomi, in grado di
prelevare dati dall'ambiente circostante. Essa è caratterizzata da una architettura
distribuita asimmetrica, inoltre può usufruire della tecnologia wireless per la
comunicazione dei sensori.
I recenti progressi tecnologici nel campo microelettromeccanico, nelle comunicazioni
wireless e nell'elettronica digitale hanno portato allo sviluppo di piccoli apparecchi a
bassa potenza e costi contenuti, multifunzionali e capaci di comunicare tra loro
tramite tecnologia wireless a raggio limitato. Questi apparecchi, chiamati nodi
sensori, sono costruiti con componenti in grado di rilevare grandezze fisiche come:
posizione spaziale, temperatura, umidità, ecc., di elaborare tali rilevamenti e
comunicare tra loro. Un sensore è comunemente inteso come un semplice trasduttore
che si trova in diretta interazione con il sistema misurato. I sensori sono quindi
installati in prossimità oppure all'interno della superficie di azione del fenomeno da
osservare. I sensori, inoltre, sono prodotti e distribuiti in massa, con costo di
produzione trascurabile e con dimensioni e pesi molto ridotti. Ognuno di essi
possiede una riserva di energia limitata e non rinnovabile ed una volta messo in opera
deve lavorare autonomamente. Perciò, essi devono mantenere costantemente i
consumi molto bassi, in modo da avere un maggior ciclo di vita. Per ottenere la
maggior quantità possibile di dati occorre effettuare una massiccia distribuzione di
sensori (nell'ordine di migliaia o decine di migliaia) in modo da avere una alta densità
(fino a 20 nodi/ m
3
) e far sì che i nodi siano tutti vicini tra loro, condizione necessaria
affinché possano comunicare.
I nodi sensore all'interno di una rete hanno la possibilità di collaborare tra loro,
essendo questi provvisti di un processore on-board; grazie al quale, ciascun nodo,
invece di inviare dati grezzi ai nodi responsabili della raccolta dei dati, possa
effettuare delle semplici elaborazioni e trasmettere solo i dati richiesti e già elaborati.
Le reti di sensori sono oggi una intrascurabile sorgente di informazione: ad esempio,
possono garantire bassi errori di misurazione, fornire informazioni in tempo reale
anche da ambienti ostili e ridurre i costi di acquisizione/trasmissione dei dati
collezionati.
Esse possono essere utilizzate su una ampia schiera di applicazioni, come: militare,
scientifica, industriale, medica e domestica. Lo scopo fondamentale di una rete di
sensori è di produrre su un periodo esteso di tempo, una informazione globale
significativa ottenuta da una serie di dati locali provenienti dai singoli sensori.
3
Pertanto, essa deve essere realizzata in modo da garantirne l'integrità per un periodo
di tempo che sia il più lungo possibile, allo scopo di ottenere informazioni accurate
anche in caso di attacco alla rete da parte di organi esterni o di cedimenti hardware.
Il fatto che un singolo sensore sia dotato di una piccola quantità di energia non deve
impedirgli di inviare le informazioni elaborate, che verranno raccolte e unite alle
informazioni provenienti dagli altri sensori. Una importante via da seguire consiste
nel rilevare il maggiore quantitativo possibile di dati locali, evitando la trasmissione
di dati inefficienti attraverso la rete. Ci sono diverse possibili tecniche che possono
essere usate per connettere la rete con l'esterno, in particolare per trasmettere le
informazioni che essa raccoglie. Nelle reti sensoriali si assume che ci siano entità
speciali chiamate nodi sink, che agiscano come nodi gateway, a lungo raggio d'azione
e distribuiti accanto ai sensori.
Un utente specifica al nodo sink di quali informazioni ha bisogno. Il sink genera una
interrogazione che viene poi immessa nella rete. Una o più risposte sono rinviate
indietro al sink, il quale riunisce ed elabora queste risposte prima di fornire il risultato
finale all'utente. Le reti dei sensori sono modellate come dei database distribuiti. Il
recupero di informazioni è effettuato tramite un linguaggio simile all'SQL. Il flusso
delle informazioni dipende dal meccanismo di elaborazione interno al database.
I nodi sensore sono distribuiti in una area chiamata sensing area. Ciascun nodo
all'interno di questa area, ha la capacità di accumulare ed instradare dati fino al nodo
sink ed infine all'utente finale . Il nodo sink consiste in una antenna capace di
illuminare tutto il dominio occupato dai nodi sensori ovvero la sensing area. La
posizione dei nodi all'interno della rete non deve essere predeterminata in quanto
questo consente di utilizzare questa tecnologia in posti difficilmente accessibili o in
operazioni di soccorso in luoghi disastrati per i quali è necessaria una disposizione
random dei nodi.
Una rete di sensori può essere vista come un insieme di sensori di diverso tipo capaci
di rilevare grandezze come: temperatura, umidità, pressione e luminosità, ma anche
capaci di rilevare il movimento dei veicoli, la composizione del terreno, e molte altre
caratteristiche.
Uno dei campi di applicazione che fa uso di reti di sensori è quello ambientale. In
questo ambito, le reti di sensori potrebbero essere usate per alcuni applicazioni che
riguardano il monitoraggio del movimento di uccelli, piccoli animali o insetti.
È possibile anche usare una rete di sensori per effettuare il monitoraggio di una
foresta e rilevare prontamente eventuali incendi. Negli Stati Uniti è stato messo a
punto un sistema per la previsione e rilevazione di inondazioni. Il sistema si chiama
ALERT SYSTEM ed è formato da molti sensori in grado di rilevare la quantità di
pioggia caduta, il livello dell'acqua di un fiume e condizioni climatiche.
Le reti di sensori possono anche essere utilizzate nell'agricoltura di precisione. Tra gli
obiettivi che è possibile raggiungere c'è quello di monitorare il livello dei pesticidi
nell'acqua. Il livello di erosione del terreno e il grado d'inquinamento dell'aria. Il tutto
effettuato in tempo reale.
Inoltre, in ambito commerciale, i sensori potrebbero essere usati per le seguenti
applicazioni:
Rilevamento del furto di auto: nodi sensore sono stati disposti per scoprire ed
4
identificare minacce che avvengono in una determinata zona geografica. Tutte le
informazioni rilevate, sono poi inviate, tramite Internet, agli utenti finali per essere
analizzate e per prendere i giusti provvedimenti;
Rilevamento della posizione e del movimento dei veicoli (car tracking):
tramite una rete di sensori è possibile monitorare la posizione di un'auto in
movimento. È inoltre possibile monitorare il traffico su strade particolarmente
transitate;
Controllo dell'ambiente in ufficio: di solito il sistema di gestione del
riscaldamento o dell'aria condizionata è centralizzato e quindi la temperatura in
ufficio può essere diversa a seconda della zona.
Predizione: Regressione e Classificazione
I dati acquisiti dai sensori possono essere usati per apprendere un modello di
predizione. Tale modello può essere usato per stimare le caratteristiche misurate (per
esempio, temperatura, umidità, ecc.) da tali sensori anche in locazioni dello spazio e
istanti di tempo ove tali misure non siano disponibili.
Sulla base dei valori rilevati nell'istante T(i) si può apprendere un modello per
predire i valori nell'istante T(i+1) tenendo conto della arrangiamento spaziale dei dati
stessi.
Le variabili da misurare, che chiameremo attributi, potranno assumere valori
numerici (regressione) oppure categorici (classificazione). Per le due tipologie di
attributo c'è uno specifico modello di predizione. Assumendo una partizione della
superficie di interesse in sotto regioni che raggruppano dati simili, per ogni sotto
regione il modello di regressione è la media matematica dei valori acquisiti dai
sensori, mentre il modello di classificazione è la classe più frequente (moda) tra le
classi misurate dai sensori.
Il partizionamento della superficie di riferimento (sensing area) in regioni è realizzato
tramite una struttura ad albero. La scelta del nodo da introdurre a ciascun passo della
costruzione dell’albero è guidata da una funzione euristica che intende minimizzare la
stima dell’errore quadratico medio rispetto all’intero insieme di attributi da predire.
Alberi per predizione
Per mantenere traccia delle divisioni ricorsive nella sensing area, si ricorre alla
struttura dell'albero binario per il quale ogni nodo che non sia foglia abbia due figli.
L'albero è costruito con approccio dall'alto verso il basso (top-down), cioè dalla radice
alle foglie. Generalmente la struttura dati ad albero è costituita da nodi, che
contengono le informazioni, ed archi, che invece contengono i collegamenti tra
queste informazioni. Nel nostro caso un nodo è etichettato con una condizione di
partizionamento della superficie che denota implicitamente l'insieme di sensori che
ricadono nella regione di partizionamento. Questa regione (insieme di sensori che vi
ricadono) è partizionato fino a che non siano soddisfatti i criteri di terminazione che
impongo la definizione di una foglia. Considerando i dati misurati da sensori
raggruppati in una foglia, si apprende il modello di predizione (regressione e/o
classificazione) da associare alla foglia stessa.
5
Alberi multi-target
Gli alberi multi target consentono di indurre un unico albero di predizione che includa
modelli per diversi attributi (numerici e/o categorici) che sono collezionati
simultaneamente da ciascun sensore. In particolare, si è definito un algoritmo per
l'apprendimento di un albero di predizione multi-target come alternativa alla
possibilità di apprendere indipendentemente un albero distinto per ciascuna delle
variabili da predire (alberi single-target). L’obiettivo di ricerca perseguito nella tesi è
la sintesi di un algoritmo di predizione multi-target che consideri l'arrangiamento
spaziale di una rete di sensori e affronti il problema di predizione nella sua versione
multi-attributo in modo da ridurre i tempi di apprendimento (efficienza
dell’apprendimento) pur preservando (o addirittura migliorando) la accuratezza della
predizione.
Alberi multi-target in una rete di sensori
Una rete di sensori genera collezioni di dati (snapshot) continuamente nel tempo.
Tale collezione può cambiare nel tempo per effetto del fenomeno denominato concept
drift. L'albero di predizione multi-target appreso ad un istante di tempo deve essere
adattato non appena nuovi dati fluiscono dalla rete. L'obiettivo di ricerca perseguito
nella tesi è stato la sintesi di una tecnica per l'apprendimento incrementale di alberi
multi-target in una rete di sensori che sia efficiente ed accurato.
Conclusioni
Il problema della predizione (classificazione e regressione) in una rete di sensori è
affrontato ricorrendo alla induzione di alberi spaziali multi-target a partire da dati
sensoriali collezionati in un dato istante. L'albero appreso è quindi aggiornato ad ogni
nuova trasmissione di dati al fine di cogliere eventuali cambiamenti nella
distribuzione dei dati. Tale obiettivo è raggiunto tramite la sintesi di due sistemi di
data mining, GeoTreeLearner e GeoStreamLearner, rispettivamente per l'induzione di
alberi multi-target spaziale in una singola collezione di dati sensoriali e in uno stream
di dati sensoriali. Le due soluzioni computazionali sono state valutate empiricamente
al fine di provarne l'efficacia.
Predizione Dati
Si formalizzano i problemi di predizione considerati (classificazione e regressione) e
si descrivono brevemente modelli di predizione strutturati ad albero.
Classificazione: definizione del problema e applicazioni
La classificazione supervisionata, anche solo classificazione è un compito di data
mining, e definisce il caso in cui gli individui devono essere categorizzati in
determinate classi (buone/cattive, dannose/non dannose … ) sulla base delle loro
proprietà.
Un compito di classificazione prevede una fase di apprendimento, nella quale viene
fornito un insieme di esempi (training set) già classificati e solo successivamente,
utilizzando il modello di classificazione appreso, sarà possibile classificare gli oggetti
per i quali la classe sia sconosciuta. Un esempio di utilizzo della classificazione nel
campo finanziario è l'erogazione di prestiti, per la quale si ha la necessità di attribuire
6
agli individui richiedenti un prestito, una classe di rischio (alto, medio, buono) e cioè
classificare un cliente come rischioso, sia sulla base delle sue informazioni personali
e sia sulla storia di altri utenti come lui.
Per compiti di classificazione sono definite in letteratura diverse tecniche di
classificazione (alberi di classificazione, K-NN, reti neurali, Naive Bayes) per le quali
vi sono implementazioni disponibili open source nel sistema WEKA. Le applicazioni
per tali tecniche di classificazione includono:
• Market analysis
customer profiling, individuare potenziali nuovi clienti, individuare i clienti
più appropriati per una campagna promozionale, ecc.
• Risk analysis
individuare i clienti fedeli, controllo di qualità dei processi, ecc.
• Fraud detection
individuare simulatori di incidenti stradali, movimenti bancari sospetti,
acquisti con carta di credito sospetti, dichiarazioni dei redditi sospette, ecc.
• Web mining
categorizzare e-mail, personalizzazione di siti web, ecc.
• Altre applicazioni
medicina, astronomia, biologia, ecc.
Regressione: definizione del problema e applicazioni
Un compito di regressione differisce da un compito di classificazione solo per la
tipologia della variabile (proprietà) da predire, che è numerica piuttosto che
categorica.
Originariamente Galton utilizzava il termine come sinonimo di correlazione, tuttavia
oggi in statistica l'analisi della regressione è associata alla risoluzione del modello
lineare. Per la loro versatilità, le tecniche della regressione lineare trovano impiego
nel campo delle scienze applicate: chimica, biologia, fisica, ingegneria, medicina,
nonché nelle scienze sociali: economia, linguistica, psicologia e sociologia.
La regressione sotto-intende la ricerca di una relazione funzionale tra la variabile
risposta (da predire) e le variabili predittore (variabili osservate). Tale relazione va
appresa da un insieme di apprendimento per cui siano noti i valori delle variabili
predittore/risposta.
Più formalmente, in statistica la regressione lineare rappresenta un metodo di stima
del valore atteso condizionato di una variabile dipendente o endogena, Y, dati i valori
di altre variabili indipendenti o esogene, X
1
,..., X
k
: E[Y|X
1
,..., X
k
].
Il modello di regressione lineare è:
Y
i
= β
0
+ β
1
X
i
+ e
i
dove:
i varia tra le osservazioni, i = 1, …, n;
Y
i
è la variabile dipendente (o risposta);