A-means: improving the cluster assignment phase of k-means for Big Data

Abstract

This paper proposes a new criterion for reducing the processing time of the assignment of data points to clusters for algorithms of the k-means family, when they are applied to instances where the number n of points is large. Our criterion allows a point to be classified in an early stage, excluding it from distance calculations to cluster centroids in subsequent iterations. The proposed criterion uses knowledge of the distance of a point to its two closest centroids and their shifts in the last two iterations. By computer experimentation using synthetic and real instances, we found that this criterion reduces execution time to approximately 2/100 of the time by k-means and generates solutions whose quality is approximately reduced by less than 3%. These findings suggest the usefulness of our criterion for problems like those found in Big Data. The NP-hardness of k-means motivates the use of this heuristics.