Un sistema per l'apprendimento di modelli predittivi in reti di sensori

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);