Algoritmo BRKGA multipopulacional (MultiPop-BRKGA-PCA) para o problema de clusterização automática

Abstract

he process of grouping data is known as clustering. In the literature, the clustering process, or grouping, has two variations: (i) if the number of clusters is predefined, this process is known as the Clustering Problem (CP) or k -Clustering Problem , and (ii) when the number of clusters is not defined, the process becomes known as Automatic Clustering Problem (ACP). The importance of having well-grouped data is crucial to making more assertive decisions. The data grouping technique has applicability in the most diverse areas of knowledge, such as: engineering, administration, economics, biology, physics, among others. Genetic algorithms are based on Darwinian evolution processes, selecting the best solutions within a population. The BRKGA (Bised Random Key Genetic Algorithm), is presented as a variation of the genetic algorithms, in which the solutions of a problem are represented as vectors of real keys, generated randomly, in the continuous interval of [0.1). The suitability of a viable solution is determined by the decoder that maps this vector to a real value. This work proposes a multi-population BRKGA to identify the ideal number of clusters, according to the silhouette index — a measure of clustering efficiency widely used in the literature. In the proposed algorithm, the solution space is partitioned so that each subpopulation the algorithm represents solutions with a k number of cluster. Thus, for each subpopulation, an independent BRKGA is applied. Computational experiments were carried out in fifty-five instances of the literature.The instances used in this work have dimensions ranging from 30 to 2,000 objects and 2 to 13 attributes, with different degrees of difficulty and characteristics, for example, group cohesion, separation, shapes and densities.The proposed algorithm is compared with existing methods in the literature, presenting superior results, leading to the understanding that the algorithm is promising.