Empirical evaluation of five algorithms for the initialization phase of the k-Means algorithm

Abstract

A recurring problem in a wide variety of research areas such as pattern recognition, machine learning, data mining and statistics, among others, is characterized as a clustering problem. Such a problem can be described in a simplistic way as: given a set of data (observations, objects, points, etc.), group similar data into clusters (groups). A clustering of a given data set is then characterized as a set of clusters, in which elements belonging to a cluster are similar to each other and elements belonging to distinct clusters are not similar. Clustering algorithms are non-supervised algorithms and, among the many available in the literature, the k-Means, that uses a random initizalization process, can be considered one of the most popular and successful. The performance of the k-Means, however, is highly dependent on a ‘good’ initialization of the $k$ cluster centers (centroids), as well as on the value assigned to the number ( $k$ ) of clusters the final clustering should have. This paper addresses experiments using five initialization algorithms available in the literature namely, the Method1, the k-Means++, the CCIA, the Maedeh and Suresh and the SPSS algorithms, to empirically evaluate their contribution for improving the k-Means performance.