Algoritmos de agrupamento particionais baseados na Meta-heurística de otimização por busca em grupo

CNPQA 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