BRKGA applied to the cluster ensemble problem

​Clustering algorithms are used to partition datasets associated with various real-world applications. However, in addition to the adopted algorithm, the obtained partition depends on the data distribution. Consequently, applying a single algorithm can result in a poor-quality partition. Cluster Ensemble (CE) is an alternative to produce a good quality partition, as it combines different dataset partitions into a single consensus partition. According to the literature, the consensus partition is generally less sensitive to noise when compared to that produced by a single algorithm. This work proposes a CE algorithm (BRKGA-CE) that combines: (i) three different strategies for producing base partitions; (ii) the BRKGA metaheuristic; (iii) the mean silhouette index, and (iv) an iterative method applied in the final phase of BRKGA-CE that allocates each object into a cluster. The core idea of BRKGA-CE is to find the representative objects of each cluster in order to maximize the mean silhouette index. To evaluate BRKGA-CE, computational experiments were carried out using the main algorithms from the literature on 20 datasets, applying two well-known external validation indices (NMI and AR) and performing hypothesis tests. As a result, BRKGA-CE presented good quality solutions in the three strategies compared to the other algorithms.