Paralelizacija algoritma indukcije stabala odluke za procesiranje Big Data primjenom Hadoop i MapReduce

master's thesis

• Title (english): Parallelization of a tree induction algorithm for big data processing with Hadoop and MapReduce
• Author: Iris Veronika Ćelić
• Mentor: David Nettleton (mentor); ISVU oznaka: DN038
• Committee member: David Nettleton (član povjerenstva); ISVU oznaka: DN038
• Committee member: Vladimir Estivill-Castro (član povjerenstva); ISVU oznaka: VE005
• Committee member: Jorge Lobo (član povjerenstva); ISVU oznaka: JL065
• Committee member: Rafael Pous (član povjerenstva); ISVU oznaka: RP062
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Protekle godine svjedocile su vidljivom rastu big data i data mining tehnologija. Takoder, mnoge polemike vodile su se u vezi zaštite privatnosti u navedenoj domeni. Big data se ponajviše veže uz društvene mreže koje svakodnevno generiraju velike kolicine privatnih podataka milijuna korisnika. Analiza spomenutih podataka donosi iznimnu korist za pružatelje usluga te same korisnike, npr. poboljšanje kvalitete usluge. Sukladno tome, korisnici mogu profitirati dijeljenjem privatnih podataka, no s druge strane, takoder, dio tih podataka potrebno je zaštiti. Glavni cilj ovog diplomskog rada jest paralelizacija algoritma razvijenog za pružanje izvještaja korisnicima društvenih mreža o potencijalnim kršenjima privatnosti. Algoritam se temelji na poznatoj data mining tehnici - stablima odluke. Na temelju relevantnosti atributa, algoritam informira korisnika o informacijama koje mogu biti razotkrivene od trece strane. S obzirom na cinjenicu da algoritam generira model za svakog korisnika te šumu pravila za svaki atribut, uocen je problem performansi programa. Osnovni zadatak jest optimizacija navedenog algoritma kako bi se omogucilo procesiranje velikih kolicina podataka odnosno big data. Rješenje ovog problema pronašli smo u paralelizaciji
cjelokupnog algoritma. Uocena su razlicita uska grla unutar programa koji se slijedno izvršava te su te komponente zasebno promatrane kao kanidati za paralelizaciju. Paralelizacija je ostvarena korištenjem alata Apache Hadoop te odgovarajuce MapReduce paradigme namjenjene big data obradi. Optimizacija algoritma potkrijepljena je razlicitim mjerenjima na grozdu racunala te testovima validacije.

Abstract (english)

Recent years have witnessed a phenomenal growth of big data and data mining techniques but also fueled a lot of debate about related privacy issues. One of the main producers of big data nowadays are on-line social networks which collect private data of millions of users every day. Analyzing this data can provide numerous benefits for the providers and the users, e.g. improving the quality of service. Therefore, users could benefit from sharing some of their personal information, but on the other hand, they would surely like to keep some of the personal information private. The main goal of this thesis is a parallelization of the algorithm developed to provide users with a meaningful report regarding potential privacy risks on social networks. The algorithm is based on decision tree learning, a well-known data mining technique. This tool will inform the user which concealed information can be subject to disclosure by identifying attribute relevance. Considering the fact that the algorithm builds a predictive model for each user and the forest of rules for each attribute we addressed the problem of the computational cost. The aim of this thesis is optimizing the algorithm and making the algorithm feasible for big data processing. As a solution to the addressed problems we proposed a parallel versions of the initial algorithm. Different bottlenecks are detected in the original sequential algorithm and were considered as candidates for the parallelization. The parallelism is obtained using Apache Hadoop, the open source MapReduce implementation for processing large data sets. Finally, various tests are
run with different data sizes that can prove the reduction of computational complexity in a distributed environment.

• Keywords: paralelizacija; MapReduce; Hadoop; big data; data mining; stabla odluke; privatnost
• Keywords (english): parallelization; MapReduce; Hadoop; big data; data mining; decision tree learning; privacy
• Language: english
• URN:NBN: urn:nbn:hr:168:388595
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-19 18:48:07