Una metaheurística para el problema de clustering automático.

Abstract

El problema de clustering consiste en subdividir un conjunto de datos en una cantidad determinada de grupos e identificar cuales datos tienen la similitud necesaria para pertenecer a un mismo grupo. Para resolver este problema es necesario saber de ante mano la cantidad exacta de grupos a asignar, esto en la práctica, generalmente, no sucede con exactitud sobre todo con conjuntos grandes de datos. Dada esta problemática surge el problema de clustering automático (PCA), que consiste en determinar automáticamente la cantidad de grupos en que se deben subdividir datos de naturaleza desconocida, además de asignar el grupo idóneo para cada uno de estos. Por tanto, el presente trabajo tiene como objetivo resolver el PCA. Para ello, se propone un algoritmo genético multioperador con cuatro operadores de mutación y cuatro operadores de cruzamiento sobre una estructura novedosa de representar la solución, que comprende la aplicación del módulo de la cantidad de grupos sobre la presolución generada. El algoritmo propuesto es validado en un conjunto de diez instancias de la literatura de distintas dimensiones. Además, se utilizan las métricas del índice Davies-Boulding, índice de separación compacta y el índice de la silueta para medir el rendimiento en comparación al estado del arte. Los experimentos computacionales muestran resultados prometedores, puesto que el algoritmo propuesto es competitivo con algoritmos de la literatura en las instancias consideradas y las tres métricas.

The clustering problem consists of subdividing a set of data into a certain number of groups and identifying which data have the necessary similarity to belong to the same group. To solve this problem it is necessary to know in advance the exact number of groups to assign, but in practice, this generally does not happen accurately, especially with large data sets. Given this problem arises the automatic clustering problema (ACP), which consists of automatically determining the number of groups in which data of unknown nature should be subdivided, in addition to assigning the ideal group for each of these. Therefore, the present work aims to solve the ACP. For this purpose, a multioperator genetic algorithm with four mutation operators and four crossover operators is proposed on a novel structure of representing the solution, which comprises the application of the modulus of the number of groups on the generated presolution. The proposed algorithm is validated on a set of ten literature instances of different dimensions. In addition, the metrics of Davies-Boulding index, compact separation index and silhouette index are used to measure the performance in comparison to the state-of-the-art. The computational experiments show promising results, since the proposed algortim is competitive with the algorithms from the literature in the considered instances and the three metrics.