Selección de centroides para algoritmos de clustering a través de técnicas metaheurísticas

Abstract

Los algoritmos de clustering de tipo c-means son sensibles a los valores de inicialización de los centroides y pueden quedar atrapados en extremos locales. Planteado en estos términos, el uso de enfoques aproximados para obtener los centroides más adecuados puede ser de gran utilidad como herramienta complementaria durante ciertas fases del proceso de minería de datos, y en particular dentro de las tareas típicas de minería de datos, entre ellas la de clustering o agrupamiento. En esta dirección, los Algoritmos Genéticos (AGs) y la Optimización Basada en Cúmulo de Partículas (PSO)1 son dos técnicas metaheurísticas poblacionales que podrían utilizarse en este ámbito, más aún cuando los problemas pueden ser planteados como de optimización. En este trabajo se analiza el uso estas dos técnicas metaheurísticas para optimizar la inicialización de los valores de centroides en las funciones aplicadas en los algoritmos de clustering tipo c-means. Los respectivos resultados son comparados usando varios conjuntos de datos generados artificialmente.

The clustering algorithms like c-means are sensitive to the initialization values of the cluster centers and can be trapped by local extrema. In these terms, the use of estimated approaches to obtain the most appropriate cluster centers can be of great utility as a complementary tool during certain phases of the process of data mining; particulary, in some specific task of data mining, e.g., clustering. In this way, Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) are two population metaheuristic approaches that could be considered as optimization. In this work the use of these two metaheuristic approaches is analyzed to optimize the initialization of the cluster centers values in the functions applied in the c-means algorithms. The respective results are compared using several datasets artificially generated.