Algoritmo de Enxame de Partículas Híbrido Aplicado a Clusterização de Dados
Resumo
Clusterização é uma importante ferramenta de mineração de dados e tem sido extensivamente explorada por diversos pesquisadores de diferentes áreas de aplicação, tais como mineração de texto e bio-informática. O Particle Swarm Optimization (PSO) é uma técnica baseada no comportamento social que vem sendo aplicada com sucesso a diversos tipos de problemas. Neste trabalho, propomos a utilização de um novo algoritmo para agrupamento de dados que chamamos de Hybrid Particle Swarm Optimization with Mutation (HPSOM), que é baseado no PSO. O HPSOM utiliza basicamente PSO e incorpora o processo de mutação, muitas vezes usados em Algoritmos Genéticos, para escapar de ótimos locais. É mostrado como o PSO/HPSOM pode ser usado para localizar o centroides de um número de clusters especificado pelo usuário. A nova proposta de método é avaliada em dados reais de referência clustering (benchmarks). O método proposto é comparado com a técnica de agrupamento K-means, com o algoritmo Particle Swarm Optimization padrão, e com um algoritmo híbrido que usa o algoritmo K-means para preencher o enxame inicial do PSO. Os resultados mostram que o algoritmo é eficiente e produz clusters compactos.
Referências
Carlantonio, L. M. (2001). Novas metodologias para clusterização de dados, coordenação de programas de pós-graduação em engenharia. Master’s thesis, COPPE/UFRJ.
Cohen, S. C. M. and Castro, L. N. (2006). Data clustering with particle swarms. Congress on Evolutionary Computation, Proceedings of IEEE Congress on Evolutionary Computation 2006:1792–1798.
Esmin, A. A. A., Pereira, D. L., and Araújo, A. F. R. (2008). Study of different approach to clustering data by using the particle swarm optimization algorithm. In IEEE Congress on Evolutionary Computation, pages 1817–1822.
Esmin, A. A. A., Torres, G. L., and Alvarenga, G. B. (2006). Hybrid evolutionary algorithm based on pso and ga mutation. 6th International Conference on Hybrid Intelligent Systems & 4th Conference on Neuro-Computing and Evolving Intelligence. Auckland - Nova Zelândia, pages 57–60.
Kennedy, J. and Eberhart, R. C. (1995). Particle swarm optimization. IEEE International Conference on Neural Networks, 1995, Perth. Proceedings of IEEE International Conference on Neural Networks.
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability., volume 1. University of California Press.
Merwe, D. W. and Engelbrecht, A. P. (2003). Data clustering using particle swarm optimization. Congress on Evolutionary Computation, 2003. Proceedings of IEEE Congress on Evolutionary Computation, pages 215–220.
Pereira, D. L. (2007). Estudo do pso na clusterização de dados. Monografia apresentada na UFLA (Universidade Federal de Lavras).
Saramago, S. F. and Prado, J. R. (2005). Otimização por colônia de partículas. FAMAT em Revista (UFU), pages 87–103.
van der Bergh, F. (2001). An Analysis of Particle Swarm Optimizers. PhD thesis, (PhD in the Faculty of Natural and Agricultural Science) – University of Pretoria.
Zhang, B., Hsu, M., and Dayal, U. (1999). K-harmonic means -a data clustering algorithm. Hewlett-Packard Research Laboratory.
