ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-06252015-155514


Tipo di tesi
Tesi di laurea magistrale
Autore
DE MATTEIS, ADRIANO DONATO
URN
etd-06252015-155514
Titolo
Fuzzy Random Forest per Big Data su piattaforma Apache Hadoop
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA INFORMATICA
Relatori
relatore Dott. Bechini, Alessio
relatore Prof. Marcelloni, Francesco
Parole chiave
  • Machine Learning
  • Hadoop
  • Data Mining
  • Big Data
  • Mahout
Data inizio appello
24/07/2015
Consultabilità
Completa
Riassunto
Le tecniche di classificazione permettono di assegnare una categoria (detta classe) ad un oggetto descritto da un certo numero di attributi. Tali sistemi hanno la capacità di apprendere dai dati, analizzando un insieme di entità per le quali è nota la classe di appartenenza, al fine di dedurre regole di classificazione. In questo modo è possibile decidere se una data entità è parte o meno di una certa categoria e offrire un supporto alle decisioni strategiche in diversi ambiti lavorativi.
E' opinione ormai consolidata e comprovata da diversi studi teorici e sperimentali che gli alberi decisionali rappresentino una tecnica di machine learning efficiente per la risoluzione di problemi di classificazione. La semplicità dell'algoritmo di apprendimento, l'interpretabilità e la potenza predittiva rappresentano i principali vantaggi derivanti dal loro utilizzo. Tuttavia essi, come del resto molte delle tecniche convenzionali, risultano altamente instabili quando piccoli disturbi vengono introdotti nei dati . Errori strumentali e/o sorgenti di rumore possono alterare la misura di una o più variabili durante un esperimento, dando luogo ad informazioni non complete o imprecise.
A volte il grado di imprecisione è talmente influente da non poter essere semplicemente ignorato o modellato attraverso una distribuzione di probabilità. Situazioni di questo tipo sono inevitabili in molte applicazioni reali ed è pertanto necessario tener conto della presenza di una certa imprecisione nei dati raccolti. Negli ultimi decenni, una delle soluzioni più adottate per gestire la rumorosità dei dati, è sicuramente quella legata all'introduzione della logica fuzzy, in grado di trattare quantitativamente l'incertezza e l'imprecisione della realtà. Integrare gli alberi decisionali con il ragionamento approssimato dato dalla logica fuzzy permette di godere dei vantaggi di entrambi: da un lato la semplicità, l'interpretabilità e la popolarità del primo, dall'altro il trattamento efficace delle informazioni imprecise del secondo.
L'albero che ne risulta prende il nome di albero decisionale fuzzy o, in lingua inglese, fuzzy decision tree.
Una Random Forest è un multiclassificatore (o ensemble learning) che costruisce una moltitudine di alberi decisionali e che in uscita, come risultato, dá la moda delle decisioni prese in fase di classificazione dai singoli alberi. Ciascuno di essi viene costruito combinando insieme le tecniche di bagging e di random attribute selection al fine di creare alberi che siano diversi tra loro. Il bagging permette di generare ogni classificatore della foresta a partire da un diverso insieme di esempi (istanze o record), creato campionando con ripescamento dall'insieme dei dati originale. L'utilizzo della tecnica di random attribute selection, inoltre, consente di selezionare, per ogni nodo dell'albero, un sottoinsieme delle variabili del problema di classificazione che si intende risolvere, e di scegliere tra queste la migliore per proseguire la generazione del modello.
Negli ultimi anni, la crescita imponente della quantità di informazioni disponibili ed in possesso delle aziende, ha portato alla nascita del fenomeno dei Big Data. Con tale termine non si intende solo un grande volume di dati, ma anche un insieme di caratteristiche che li contraddistinguono dai classici concetti di massive data o very large data. Spesso, infatti, i Big Data si presentano in forma non strutturata e con una velocità superiore rispetto al passato, aspetti che non ne consentono una facile acquisizione. L'insieme di tali caratteristiche non permette un'analisi efficace se si utilizzano le tecniche tradizionali, ed è necessario pertanto definire una nuova generazione di strumenti ed architetture grazie alle quali effettuare in modo veloce ed efficace le operazioni di acquisizione ed estrazione della conoscenza. L'aggiornamento tecnologico, in tale direzione, è attualmente in corso, e ogni giorno sempre nuovi sforzi vengono compiuti nel campo della ricerca per proporre nuovi approcci di analisi.
Nell'ambito dell'apprendimento automatico (meglio noto in letteratura come machine learning) l'accuratezza degli algoritmi di classificazione è fortemente influenzata dal metodo utilizzato per discretizzare il dominio degli attributi numerici.
La presente tesi descrive il lavoro di ricerca condotto al fine di individuare un nuovo metodo, basato sulla logica fuzzy, di discretizzazione di tali attributi, da utilizzare per la costruzione di alberi decisionali fuzzy e, in particolar modo, per la definizione di un nuovo approccio per la generazione di una Fuzzy Random Forest (i.e. una Random Forest costituita da una moltitudine di fuzzy decision tree) nel contesto dei Big Data.
In letteratura fino ad oggi è possibile trovare altre proposte sullo stesso filone di studio. Tuttavia la maggior parte di esse presenta metodi che effettuano la discretizzazione del dominio degli attributi numerici solo prima della fase di addestramento del modello. L' approccio da noi proposto, invece, prevede che la discretizzazione venga effettuata contestualmente alla fase di costruzione degli alberi che costituiranno la foresta. Il partizionamento fuzzy dei domini degli attributi numerici è, pertanto, intrinseco all'algoritmo di generazione del modello.
La soluzione proposta è stata completamente integrata all'interno del framework Apache Mahout, nota libreria open-source per l'analisi di grandi moli di dati e l'esecuzione parallela di algoritmi di machine learning in un ambiente di calcolo distribuito.
I test sono stati condotti in tre fasi e hanno previsto il confronto del nuovo classificatore con la versione crisp dell'algoritmo.
La prima fase è stata effettuata utilizzando 28 dataset di piccole dimensioni (da 80 fino a 7200 istanze) e ha rivelato come le fuzzy random forest proposte siano statisticamente equivalenti alle classiche random forest.
Nella seconda fase è stata prevista l'aggiunta di rumore ai dataset precedentemente utilizzati: in questo caso è stato possibile osservare come le fuzzy random forest siano statisticamente superiori alle classiche, confermando quanto ci si aspettava, ovvero che l'utilizzo della logica fuzzy è in grado di garantire una maggiore robustezza nelle situazioni in cui si opera con dati incerti o rumorosi.
L'ultima fase di test ha previsto la valutazione del nuovo classificatore su Big Dataset, rumorosi e non rumorosi, utilizzando come strumento di calcolo distribuito Apache Hadoop su un cluster composto da quattro macchine.
Parte del lavoro di ricerca condotto per lo svolgimento di questa tesi, grazie ai buoni risultati raggiunti, ha permesso la stesura del paper ''A New Approach to Fuzzy Random Forest Generation'', accettato dall' IEEE International Conference on Fuzzy Systems (Agosto 2015).
La tesi è organizzata come segue. Nel Capitolo 2 verrà fornita una breve panoramica dello stato dell'arte, descrivendo le principali caratteristiche degli alberi decisionali, delle Random forest e delle rispettive versioni fuzzy proposte fin ad oggi in letteratura. Esporremo inoltre i concetti che identificano il quadro teorico nel quale è stata svolta la ricerca e affronteremo le problematiche derivanti dal cambiamento del contesto tecnologico dovuto al fenomeno dei Big Data.
Nel capitolo 3 verranno presentati gli strumenti utilizzati per lo svolgimento del lavoro di tesi, nello specifico descrivendo la libreria Random Forest di Mahout e l'architettura che permette di effettuare il processing distribuito di grandi moli di dati.
Nel Capitolo 4 entreremo nel dettaglio della soluzione proposta. Descriveremo inizialmente il particolare metodo adottato per la discretizzazione del dominio degli attributi numerici e come questo venga utilizzato per addestrare un fuzzy decision tree. Continueremo spiegando come viene generata la Fuzzy Random Forest proposta, quali sono i parametri scelti ed illustrando i diversi modi in cui è possibile ottenere la decisione finale nella fase di classificazione.
Nel Capitolo 5 verrà descritta l'implementazione dell'algoritmo, descrivendo nel dettaglio le principali soluzioni adottate per la sua realizzazione. Nel Capitolo 6 mostreremo i risultati dei test, effettuati su 28 dataset di piccole dimensioni (da 80 a 7200 istanze), su 6 Big dataset e sulle loro rispettive versioni rumorose, confrontando le performance ottenute con quelle raggiunte sugli stessi dalle Random Forest classiche.
Nel Capitolo 7 verrà descritto uno studio atto a valutare la scalabilità della nostra Fuzzy Random Forest ed, infine, il Capitolo 8 presenterà le conclusioni generali sul lavoro svolto.
File