HYBRID GENETIC ALGORITHM APPLIED TO THE CLUSTERING PROBLEM

Abstract

Clustering is a task, whose main objective is dividing a data set into partitions, so that patterns belonging to 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