Summary: 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.