Domains such as internet algorithms, computational biology or social link analysis deal with very large datasets, also called Big Data. In these scenarios, single machine learning algorithms cannot handle easily the entire data to produce models and MapReduce emerged as new paradigm to query data in distributed systems. Apache Hadoop is the result of the open source community in letting this technology available for everyone. There is a huge amount of information locked up in databases and these information can be exploited with machine learning techniques, which aim to find and describe structural patterns in data. Our work focused on feature selection algorithms because they generalize prediction models reducing the noise in input. We implemented two state-of-the-art feature selection algorithms (Ranking and mRMR) according to the MapReduce programming paradigm and we made them available to the open source Big Data community. In order to visualize and model the scalability of the approach, we ran several and extensive performance tests at the university computing center, where we first built a user friendly service which dynamically deploys Apache Hadoop in the cluster. The results mostly matched our expectations and theoretical analysis, when algorithms ran over large datasets.
In questa tesi esaminiamo quali sono le limitazioni dei tradizionali Database Management Systems nel gestire grandi collezioni di dati. Questi sono stati in passato la soluzione di riferimento per salvare in modo organizzato i dati, tuttavia nei sistemi distribuiti non rappresentano la migliore soluzione, a causa della complessità e dei vincoli introdotti. Con l'avvento del Big Data è stato necessario un nuovo paradigma per immagazzinare e interrogare i dati per superare i limiti di tali architetture. Le nuove applicazioni emerse sono state raggruppate sotto il termine NoSQL. Nel 2003 e 2004, Google ha pubblicato due articoli, Google file system e MapReduce, che sono le fondamenta del nuovo modo di immagazzinare e interrogare i dati. Apache Hadoop è il risultato della communità open source nel rendere tale tecnologia disponibile a tutti e un intero nuovo ecosistema di software proprietari e open è nato con lo scopo di arricchirne le funzionalità. Noi eravamo interessati nello studiare e implementare algoritmi di machine learning in MapReduce nel contesto del Big Data. Si parla di Big Data per esempio in biologia computazionale, analisi di social network e text mining, dove gli algoritmi tradizionali eseguibili localmente su singole macchine non riescono a produrre modelli in tempi ragionevoli. Abbiamo posto la nostra attenzione sugli algoritmi di feature selection per due motivi: perché sono tecniche per ridurre il rumore e informazioni irrilevanti dal dataset, permettendo una migliore generalizzazione del modello di predizione e perché non sono disponibili nei software open source, come Apache Mahout. Abbiamo implementato gli algoritmi di mRMR e Ranking in MapReduce come una libreria Java integrabile ad Apache Mahout e rilasciato il codice open source su GitHub. Il nostro scopo è stato quello di studiare la scalabilità di tali algoritmi e considerare quanto l'overhead di Apache Hadoop, nel gestire il cluster, incide nel tempo totale di esecuzione. Nonostante le ridotte risorse a disposizione, in relazione ad altre ricerche, abbiamo potuto fare le seguenti considerazioni: per piccoli dataset o nel caso in cui i parametri del cluster siano male impostati, l'overhead condiziona in modo significativo il tempo finale. Con grandi dataset i risultati sono stati coerenti con le nostre aspettative, ovvero che il tempo di esecuzione è proporzionale alla dimensione dell'input e inversamente proporzionale alla quantità di risorse computazionali disponibili, i.e al numero di nodi e core nel cluster. I test sono stati condotti utilizzando il centro di calcolo (HPC) universitario, nel quale abbiamo esplorato le possibili alternative per integrare Apache Hadoop nel cluster. Abbiamo deciso di sviluppare un servizio sul modello di Amazon Elastic MapReduce, user friendly e disponibile per qualsiasi utente. Tale servizio, in modo automatico e dinamico, installa e configura Apache Hadoop sui nodi ed esegue il job sottomesso. Gli unici parametri che l'utente deve impostare sono il numero di nodi del cluster e definire quale job eseguire.
Scaling feature selection algorithms using MapReduce on Apache Hadoop
REGGIANI, CLAUDIO
2012/2013
Abstract
Domains such as internet algorithms, computational biology or social link analysis deal with very large datasets, also called Big Data. In these scenarios, single machine learning algorithms cannot handle easily the entire data to produce models and MapReduce emerged as new paradigm to query data in distributed systems. Apache Hadoop is the result of the open source community in letting this technology available for everyone. There is a huge amount of information locked up in databases and these information can be exploited with machine learning techniques, which aim to find and describe structural patterns in data. Our work focused on feature selection algorithms because they generalize prediction models reducing the noise in input. We implemented two state-of-the-art feature selection algorithms (Ranking and mRMR) according to the MapReduce programming paradigm and we made them available to the open source Big Data community. In order to visualize and model the scalability of the approach, we ran several and extensive performance tests at the university computing center, where we first built a user friendly service which dynamically deploys Apache Hadoop in the cluster. The results mostly matched our expectations and theoretical analysis, when algorithms ran over large datasets.| File | Dimensione | Formato | |
|---|---|---|---|
|
2013_07_Reggiani.pdf
accessibile in internet per tutti
Descrizione: Thesis text
Dimensione
1.79 MB
Formato
Adobe PDF
|
1.79 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/81201