HYBRID GENETIC ALGORITHM APPLIED TO THE CLUSTERING PROBLEM

Resumen

ABSTRACT

Clustering is a task, whose main objective is dividing a data set into partitions, so that patterns belonging t o the same partition are similar to one another and dissimilar to patterns belonging to other partitions. It falls into the category of optimization tasks, since clustering ultimately aims at finding the best combination of partitions among all possible combinations. Metaheuristics, which are general heuristics capable of escaping local optima, can be applied to solve the clustering problem. This paper proposes a Hybrid Genetic Clustering Algorithm (HGCA) ─ whose initial population is generated partly by clustering algorithms ─ that combines a local search heuristic to the global search procedure. Such improvements are intended to provide solutions for search problems closer to the global optimum. Experiments are performed in real data sets I order to verify if the proposed approach presents any improvement in comparison with other algorithms evaluated in this work: agglomerative hierarchical; three versions of K-means, differing only in terms of initialization methods (Random, K-means + + and PCA_Part); Tabu Search and Genetic Clustering Algorithm

KEYWORDS. Metaheuristics. Clustering. Optimization.

RESUMEN

El agrupamiento de datos es una tarea, cuyo principal objetivo es dividir un conjunto de datos en particiones, por lo que los patrones que pertenecen a la misma partición son similares entre sí y diferentes a los patrones que pertenecen a otras particiones. El agrupamiento de datos debe incluirse en la categoría de tareas de optimización, ya que en última instancia, agrupación aspira a encontrar la mejor combinación de particiones entre todas las combinaciones posibles.  Metaheurísticas, que son heurísticos generales capaz de escapar de óptimos locales, se puede aplicar para resolver el problema de agrupamiento. Este trabajo propone un Algoritmo de Agrupamiento Genético Híbrido (HGCA) ─ cuya primera población se genera en parte por algoritmos de agrupamiento ─ que combina una heurística de búsqueda local para el procedimiento de búsqueda global. Estas mejoras están destinadas a proporcionar soluciones a los problemas de búsqueda más cerca del óptimo global. Los experimentos se realizan en conjuntos de datos reales que el fin de comprobar si el enfoque propuesto presenta una mejora en comparación con otros algoritmos evaluados en este trabajo:  aglomeración jerárquica, tres versiones del K-means, difiriendo sólo en cuanto a los métodos de inicialización (al azar, K-means ++ y PCA_Part); Búsqueda Tabú y Algoritmo de Agrupamiento Genético