Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-13T12:57:14Z
No. of bitstreams: 1
texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) / Made available in DSpace on 2016-09-13T12:57:14Z (GMT). No. of bitstreams: 1
texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5)
Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A cada dia mais dados são gerados das mais diversas fontes. A extração de conheci- mento das bases de dados torna-se cada vez mais desafiadora, visto que os processos utilizados não são triviais. O agrupamento de dados usa técnicas que são capa- zes de trabalhar com dados pouco conhecidos de forma não supervisionada. Essas técnicas dividem os dados em grupos tentando capturar a estrutura presente nos dados para obter um conhecimento que servirá de ponto inicial para seu estudo. Poucos algoritmos de agrupamentos conseguem trabalhar em um contexto escalá- vel. Um dos algoritmos mais influentes no agrupamento é o k -médias, que possui complexidade linear e duas fases bem distintas, facilmente adaptada para modelos escaláveis. Porém, k -médias possui limitações, como sensibilidade à inicialização e especificação do número de grupos k, que geralmente é desconhecido. O obje- tivo desta pesquisa é estudar e desenvolver algoritmos de agrupamento para este contexto escalável. Especificamente, procura-se trabalhar com meta-heurísticas que proporcionem o agrupamento escalável sem a necessidade de especificação do nú- mero de grupos k. Essa dissertação propõe dois novos algoritmos de agrupamento que encontram um valor para k automaticamente em um modelo escalável chamado MapReduce. Adicionalmente, foi estudado um algoritmo com o mesmo propósito encontrado na literatura. Todos os algoritmos foram desenvolvidos e comparados de duas maneiras: pela sua complexidade assintótica e através de experimentos em bases artificiais e reais. Com base em testes estatísticos, foi possível verificar as principais diferenças entre a performance dos algoritmos. / Everyday more data are generated from several sources. The knowledge extraction from datasets becomes more and more challenging as the applied techniques are not trivial. Data clustering techniques are able to work with little knowledge about the data in a totally unsupervised manner. These techniques divide data into clusters trying to capture the structure of the data to obtain knowledge that will serve as a starting point for further studies. Few clustering algorithms are able to work in a scalable scenario. One of the most influential clustering algorithms is k -means, which has linear asymptotic complexity and two distinct phases, which can be easily adapted for scalable models. However, k -means has limitations such as sensitivity to initialization and previous specification of the numbers of clusters k, which is generally unknown, specially for real world scenarios. The objective of this rese- arch is to study and develop scalable clustering algorithms. Specifically, the use of meta-heuristics for scalable clustering to automatically determine the number of k clusters. This dissertation proposes two new clustering algorithms that are able to automatically find the value k in a scalable programing model called MapRe- duce. Additionally, an state-of-art algorithm from the literature has been studied and compared. All algorithms were developed and compared in two ways: based on their asymptotic complexity and through experiments in artificial and real datasets. Based on statistical tests, is was possible to find the main differences among quality and performance of all compared algorithms.
Identifer | oai:union.ndltd.org:IBICT/oai:localhost:123456789/8555 |
Date | 26 February 2016 |
Creators | Oliveira, Gilberto Viana de |
Contributors | Naldi, Murilo Coelho |
Publisher | Universidade Federal de Viçosa |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | English |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Source | reponame:Repositório Institucional da UFV, instname:Universidade Federal de Viçosa, instacron:UFV |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds