CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Clustering is a data mining technique that brings together elements of a data set such
so that the elements of a same group are more similar to each other than to those from
other groups. This thesis studied the problem of processing the clustering based on density
DBSCAN algorithm distributedly through the MapReduce paradigm. In the distributed processing
it is important that the partitions are processed have approximately the same size, provided that the total of
the processing time is limited by the time the node with a larger amount of data leads to
complete the computation of data assigned to it. For this reason we also propose a data set
partitioning strategy called G2P, which aims to distribute the data set in a balanced manner
between partitions and takes into account the characteristics of DBSCAN algorithm. More
Specifically, the G2P strategy uses grid and graph structures to assist in the division of
space low density regions. Distributed DBSCAN the algorithm is done processing
MapReduce two stages and an intermediate phase that identifies groupings that can
were divided into more than one partition, called candidates from merging. The first MapReduce
phase applies the algorithm DSBCAN the partitions individually. The second and checks
correcting, if necessary, merge candidate clusters. Experiments using data sets demonstrate that true
G2P-DBSCAN strategy overcomes the baseline adopted in all the scenarios, both
at runtime and quality of obtained partitions. / ClusterizaÃao à uma tÃcnica de mineraÃÃo de dados que agrupa elementos de um conjunto de dados de forma que os elementos que pertencem ao mesmo grupo sÃo mais semelhantes entre si que entre elementos de outros grupos. Nesta dissertaÃÃo nÃs estudamos o problema de processar o algoritmo de clusterizaÃÃo baseado em densidade DBSCAN de maneira distribuÃda atravÃs do paradigma MapReduce. Em processamentos distribuÃdos à importante que as partiÃÃes de dados a serem processadas tenham tamanhos proximadamente iguais, uma vez que o tempo total de processamento à delimitado pelo tempo que o nà com uma maior quantidade de dados leva para finalizar a computaÃÃo dos dados a ele atribuÃdos. Por essa razÃo nÃs tambÃm propomos uma estratÃgia de particionamento de dados, chamada G2P, que busca distribuir o conjunto de dados de forma balanceada entre as partiÃÃes e que leva em consideraÃÃo as caracterÃsticas do algoritmo DBSCAN. Mais especificamente, a estratÃgia G2P usa estruturas de grade e grafo para auxiliar na divisÃo do espaÃo em regiÃes de baixa densidade. Jà o processamento distribuÃdo do algoritmo DBSCAN se dà por meio de duas fases de processamento MapReduce e uma fase intermediÃria que identifica clusters que podem ter sido divididos em mais de uma partiÃÃo, chamados de candidatos à junÃÃo. A primeira fase de MapReduce aplica o algoritmo DSBCAN nas partiÃÃes de dados individualmente, e a segunda verifica e corrige, caso necessÃrio, os clusters candidatos à junÃÃo. Experimentos utilizando dados reais mostram que a estratÃgia G2P-DBSCAN se comporta melhor que a soluÃÃo utilizada para comparaÃÃo em todos os cenÃrios considerados, tanto em tempo de execuÃÃo quanto em qualidade
das partiÃÃes obtidas.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:10119 |
| Date | 17 August 2015 |
| Creators | AntÃnio Cavalcante AraÃjo Neto |
| Contributors | Javam de Castro Machado, Altigran Soares da Silva, Josà AntÃnio Fernandes de Macedo, Josà Neuman de Souza |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds