A greedy randomized adaptive search procedure applied to the clustering problem as an initialization process using K-Means as a local search procedure

Abstract

We present a new approach for Cluster Analysis based on a Greedy Randomized Adaptive Search Procedure (GRASP), with the objective of overcoming the convergence to a local solution. It uses a probabilistic greedy Kaufman initialization to get initial solutions and K-Means as a local search algorithm. The approach is a new initialization one for K-Means. Hence, we compare it with some typical initialization methods: Random, Forgy, Macqueen and Kaufman. Our empirical results suggest that the hybrid GRASP – K-Means with probabilistic greedy Kaufman initialization performs better than the other methods with improved results. The new approach obtains high quality solutions for eight benchmark problems.