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

Issue title: IBERAMIA '02

Article type: Research Article

Authors: Cano, J.R. | Cordón, O. | Herrera, F. | Sánchez, L.

Affiliations: Department of Software Engineering, University of Huelva, 21071 La Rabida (Huelva), Spain. E-mail: [email protected] | Department of Computer Science and A.I., University of Granada, 18071-Granada, Spain. E-mail: {ocordon,herrera}@decsai.ugr.es | Department of Computer Science, University of Oviedo, Oviedo, Spain. E-mail: [email protected]

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.

Keywords: clustering, greedy randomized adaptive search procedure, K-Means

Journal: Journal of Intelligent & Fuzzy Systems, vol. 12, no. 3-4, pp. 235-242, 2002