Paralelni algoritmi za problem grupiranja podataka

master's thesis

• Author: Anto Čabraja
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Franka Miriam Bruckler (član povjerenstva)
• Committee member: Željka Milin-Šipuš (član povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Grupiranje podataka jedna je od najbitnijih metoda analize podataka te je u gotovo svim slučajevima prvi korak daljnje analize. U današnje vrijeme veliki servisi kao što su Google i Facebook u svojim bazama spremaju terabajte podataka. Podaci pristižu u prirodnom poretku, to jest bez definiranog redoslijeda te ih je potrebno grupirati u smislene cjeline. Problem grupiranja trivijalno je rješiv iscrpnom pretragom. Međutim, rezultati analize podataka potrebni su u realnom vremenu sto nikako nije izvedivo iscrpnom pretragom budući da je problem grupiranja NP-težak problem. Rad započinje s definiranjem osnovnih pojmova i matematičkim modeliranjem problema grupiranja. Nakon uvodnih definicija opisane su osnovne metode grupiranja: hijerarhijsko i particijsko grupiranje. Osim osnovnih metoda uveden je pojam evolucijske metode. Navedena metoda danas se gotovo uvijek koristi kada se na efikasan nčcin pokušavaju pronaći rješenja teških problema. Posebna cjelina posvećena je upravo evolucijskoj metodi te su definirani osnovni operatori potrebni za razvoj algoritma. Evolucijske metode zajednički je naziv za skup algoritama inspiriranih prirodnim procesima. U radu je posebno opisan genetski algoritam kao predstavnik metode. Uveden je pojam heuristike te su konstruirani iterativni i evolucijski algoritam za problem grupiranja. Implementirane metode dobro rješavanju zadane probleme što je prikazano analizom. Vremenska složenost sekvencijalnih algoritama je prilično velika te su zbog toga paralelizirani. Nakon uvodnih napomena, opisana je tehnologija MPI te sve prednosti koje odlikuju paralelizaciju. Na kraju su uvedene razne topologije mreža procesora: topologija povezane mreže, topologija povezanosti u grupi te topologija s vodom. Objašnjeni su osnovni pojmovi sinkronizacije paralelnih procesora te opisane konkretne implementacije paralelnih algoritama. Iterativni sekvencijalni algoritam paraleliziran je korištenjem topologije s vodom, dok je za paralelizaciju evolucijske metode korištena topologija povezanosti u grupi. Implemenacije su testirane te su analizirani dobiveni rezultati.

Abstract (english)

Data clustering is one of the most important methods for data analysis and in most cases the first step in further analysis. Nowadays big services like Google and Facebook store terabytes of data. Data arrives in natural order, usually without a defined sequence and they need to be grouped into meaningful clusters. The problem of data clustering is trivial if we use thorough examination. However, we need a result in real time, which thorough examination can’t offer since data clustering is an NP-hard problem. This thesis offers basic definitions for data clustering and introduces mathematical modeling of data clustering problems. After definitions we describe basic methods for clustering: hierarchical and partitional clustering. In addition, we introduce the concept of evolutionary programming which represents the most popular method in solving NP-hard problems efficiently. In section two particular attention is dedicated to genetic algorithms as a representative of the evolutionary algorithms class. Evolutionary method is a common name for methods inspired by natural processes. A description of heuristic algorithms concept and a construction of sequential algorithms for data clustering problem is given in section three. It is shown that the implemented methods are good in solving problems, but the big time complexity of sequential algorithms leads to parallel processes. Therefore, after the sequential solution, we introduce the concept of parallel programming via MPI technologies and the benefits it offers. These technologies allow many types of network topologies for processors. This thesis describes three topological concepts: connected network, network with a master and group network. Also, we explain the synchronization among processors and demonstrate some parallel algorithm solutions for real-life problems. Synchronization is a hard problem because of a restricted set of functions (send, receive and broadcast). Using those functions we implemented all parallel algorithms in section five. After the implementation and testing we conducted a thorough analysis of results.

• Keywords: grupiranje podataka; analiza podataka; hijerarhijsko grupiranje; particijsko grupiranje; evolucijska metoda; heuristika
• Keywords (english): data clustering; data analysis; hierarchical clustering; partitional clustering; evolutionary programming; heuristic algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:217:660082
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-07 12:24:06