Resolución del problema de clustering utilizando algoritmos evolutivos

Abstract

Este proyecto estudia el problema de clustering, donde se busca encontrar una agrupación óptima de elementos. Se analizan dos variantes del problema: una variante monoobjetivo donde se busca maximizar la sumatoria de las similitudes de los elementos al centro del grupo al que pertenecen y una variante multiobjetivo del problema, donde además de maximizar la sumatoria de las similitudes, se plantea minimizar simultáneamente la cantidad de grupos. Se implementan doce algoritmos evolutivos diferentes para la variante monoobjetivo del problema y un algoritmo evolutivo para la variante multiobjetivo del problema. Los algoritmos evolutivos implementados son evaluados utilizando un conjunto de instancias, dos de ellas generadas por colegas de la Universidad de Luxemburgo y once obtenidas de un repositorio público con instancias de pruebas específicas para el problema de clustering. Los resultados experimentales muestran que para la variante monoobjetivo del problema, los algoritmos evolutivos implementados alcanzan mejoras de hasta un 156.2% respecto a una estrategia ávida que resuelve el mismo problema. En relación al algoritmo de referencia de la literatura relacionada, se alcanzan mejoras de hasta un 9.5 %. Para la variante multiobjetivo del problema, los resultados experimentales muestran que el algoritmo evolutivo implementado logra mejorar hasta un 31.4% el mejor resultado del algoritmo de referencia para igual cantidad de grupos. El algoritmo evolutivo que resuelve la variante monoobjetivo obtiene resultados un 2% en promedio por encima de los resultados obtenidos por el algoritmo evolutivo en su variante multiobjetivo, considerando que el primero es un algoritmo específico para encontrar una agrupación optima dada una cantidad de grupos.

This project studies the clustering problem, where the goal is to organize information by grouping individuals. Two different variants of the problem are studied: a single objective variant with the goal of maximizing the sum of the similarities between the elements and the center of the group to which they belong to and a multiobjective variant, which proposes the simultaneous minimization of the number of groups. Twelve different evolutionary algorithms are implemented for the single objective variant of the problem and one evolutionary algorithm is implemented for the multiobjective problem variant. The evolutionary algorithms implemented are evaluated using a set of instances, two of them generated by colleagues from the University of Luxembourg and eleven obtained from a public repository with speci c instances for the clustering problem. The experimental results show that the evolutionary algorithms developed for the single objective variant of the problem are able to improve up to 156.2% upon the results reached using a greedy algorithm. While regarding a reference algorithm from the literature, improvements of up to 9.5% are achieved. Regarding the multiobjective variant of the problem, the experimental results show that the evolutionary algorithms are able to obtain solutions that improve up to 31.42% over the best result of the reference algorithm for the same amount of groups. The evolutionary algorithm that solves the single objective variant of the problem obtained results 2% on average above the results obtained by the evolutionary algorithm in its multi objective variant, where the rst one is a speci fic algorithm aimed at nding an optimal grouping when a number of groups are given.