TheK-Means Algorithm Evolution
Joaquín Pérez-Ortega, Nelva Nely Almanza-Ortega, Andrea Vega-Villalobos, Rodolfo A. Pazos-Rangel, Crispín Zavala-Díaz, Alicia Martínez · IntechOpen eBooks · 2019
Clustering is one of the main methods for getting insight on the underlying nature and structure of data.The purpose of clustering is organizing a set of data into clusters, such that the elements in each cluster are similar and different from those in other clusters.One of the most used clustering algorithms presently is K-means, because of its easiness for interpreting its results and implementation.The solution to the K-means clustering problem is NP-hard, which justifies the use of heuristic methods for its solution.To date, a large number of improvements to the algorithm have been proposed, of which the most relevant were selected using systematic review methodology.As a result, 1125 documents on improvements were retrieved, and 79 were left after applying inclusion and exclusion criteria.The improvements selected were classified and summarized according to the algorithm steps: initialization, classification, centroid calculation, and convergence.It is remarkable that some of the most successful algorithm variants were found.Some articles on trends in recent years were included, concerning K-means improvements and its use in other areas.Finally, it is considered that the main improvements may inspire the development of new heuristics for K-means or other clustering algorithms.