Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-10-17T18:58:21Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
tese-ldsp-cin-ufpe.pdf: 2057113 bytes, checksum: 40e1baebc2bc4840cd9803fdc16d952f (MD5) / Made available in DSpace on 2016-10-17T18:58:21Z (GMT). No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
tese-ldsp-cin-ufpe.pdf: 2057113 bytes, checksum: 40e1baebc2bc4840cd9803fdc16d952f (MD5)
Previous issue date: 2016-08-26 / CNPQ / A Análise de Agrupamentos, também conhecida por Aprendizagem Não-Supervisionada,
é uma técnica importante para a análise exploratória de dados, tendo sido largamente
empregada em diversas aplicações, tais como mineração de dados, segmentação de imagens,
bioinformática, dentre outras. A análise de agrupamentos visa a distribuição de um
conjunto de dados em grupos, de modo que indivíduos em um mesmo grupo estejam mais
proximamente relacionados (mais similares) entre si, enquanto indivíduos pertencentes a
grupos diferentes tenham um alto grau de dissimilaridade entre si.
Do ponto de vista de otimização, a análise de agrupamentos é considerada como um caso
particular de problema de NP-Difícil, pertencendo à categoria da otimização combinatória.
Técnicas tradicionais de agrupamento (como o algoritmo K-Means) podem sofrer algumas
limitações na realização da tarefa de agrupamento, como a sensibilidade à inicialização
do algoritmo, ou ainda a falta de mecanismos que auxiliem tais métodos a escaparem de
pontos ótimos locais.
Meta-heurísticas como Algoritmos Evolucionários (EAs) e métodos de Inteligência de
Enxames (SI) são técnicas de busca global inspirados na natureza que têm tido crescente
aplicação na solução de uma grande variedade de problemas difíceis, dada a capacidade de
tais métodos em executar buscas minuciosas pelo espaço do problema, tentando evitar
pontos de ótimos locais. Nas últimas décadas, EAs e SI têm sido aplicadas com sucesso
ao problema de agrupamento de dados. Nesse contexto, a meta-heurística conhecida por
Otimização por Busca em Grupo (GSO) vem sendo aplicada com sucesso na solução de
problemas difíceis de otimização, obtendo desempenhos superiores a técnicas evolucionárias
tradicionais, como os Algoritmos Genéticos (GA) e a Otimização por Enxame de Partículas
(PSO). No contexto de análise de agrupamentos, EAs e SIs são capazes de oferecer boas
soluções globais ao problema, porém, por sua natureza estocástica, essas abordagens
podem ter taxas de convergência mais lentas quando comparadas a outros métodos de
agrupamento.
Nesta tese, o GSO é adaptado ao contexto de análise de agrupamentos particional. Modelos
híbridos entre o GSO e o K-Means são apresentados, de modo a agregar o potencial de
exploração oferecido pelas buscas globais do GSO à velocidade de exploitação de regiões
locais oferecida pelo K-Means, fazendo com que os sistemas híbridos formados sejam
capazes de oferecerem boas soluções aos problemas de agrupamento tratados.
O trabalho apresenta um estudo da influência do K-Means quando usado como operador
de busca local para a inicialização populacional do GSO, assim como operador para
refinamento da melhor solução encontrada pela população do GSO durante o processo
geracional desenvolvido por esta técnica.
Uma versão cooperativa coevolucionária do modelo GSO também foi adaptada ao contexto
da análise de agrupamentos particional, resultando em um método com grande potencial
para o paralelismo, assim como para uso em aplicações de agrupamentos distribuídos.
Os resultados experimentais, realizados tanto com bases de dados reais, quanto com o
uso de conjuntos de dados sintéticos, apontam o potencial dos modelos alternativos de
inicialização da população propostos para o GSO, assim como de sua versão cooperativa
coevolucionária, ao lidar com problemas tradicionais de agrupamento de dados, como a
sobreposição entre as classes do problema, classes desbalanceadas, dentre outros, quando
em comparação com métodos de agrupamento existentes na literatura. / Cluster analysis, also known as unsupervised learning, is an important technique for
exploratory data analysis, and it has being widely employed in many applications such as
data mining, image segmentation, bioinformatics, and so on. Clustering aims to distribute
a data set in groups, in such a way that individuals from the same group are more closely
related (more similar) among each other, while individuals from different groups have a
high degree of dissimilarity among each other.
From an optimization perspective, clustering is considered as a particular kind of NP-hard
problem, belonging in the combinatorial optimization category. Traditional clustering
techniques (like K-Means algorithm) may suffer some limitations when dealing with
clustering task, such as the sensibility to the algorithm initialization, or the lack of
mechanisms to help these methods to escape from local minima points.
Meta-heuristics such as EAs and SI methods are nature-inspired global search techniques
which have been increasingly applied to solve a great variety of difficult problems, given
their capability to perform thorough searches through a problem space, attempting to
avoid local optimum points. From the past few decades, EAs and SI approaches have
been successfully applied to tackle clustering problems. In this context, Group Search
Optimization (GSO) meta-heuristic has been successfully applied to solve hard optimization
problems, obtaining better performances than traditional evolutionary techniques, such as
Genetic Algorithms (GA) and Particle Swarm Optimization (PSO). In clustering context,
EAs an SIs are able to obtain good global solutions to the problem at hand, however,
according to their stochastic nature, these approaches may have slow convergence rates in
comparison to other clustering methods.
In this thesis, GSO is adapted to the context of partitional clustering analysis. Hybrid
models of GSO and K-Means are presented, in such a way that the exploration offered
by GSO global searches are combined with fast exploitation of local regions provided
by K-Means, generating new hybrid systems capable of obtaining good solutions to the
clustering problems at hands.
The work also presents a study on the influence of K-Means when adopted as a local
search operator for GSO population initialization, just like its application as an refinement
operator for the best solution found by GSO population during GSO generative process.
A cooperative coevolutionary variant of GSO model is adapted to the context of partitional
clustering, resulting in a method with great potential to parallelism, as much as for the
use in distributed clustering applications.
Experimental results, performed as with the use of real data sets, as with the use of
synthetic data sets, showed the potential of proposed alternative population initialization
models and the potential of GSO cooperative coevolutionary variant when dealing with
classic clustering problems, such as data overlapping, data unbalancing, and so on, in
comparison to other clustering algorithms from literature.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/18002 |
| Date | 26 August 2016 |
| Creators | PACÍFICO, Luciano Demétrio Santos |
| Contributors | LUDERMIR, Teresa Bernardar |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Breton |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds