Ball k-Means: Fast Adaptive Clustering With No Bounds

This paper presents a novel accelerated exact k-means called as Ball k-means by using the ball to describe each cluster, which focus on reducing the point-centroid distance computation. The Ball k-means can exactly find its neighbor clusters for each cluster, resulting distance computations only between a point and its neighbor clusters' centroids instead of all centroids. What's more, each cluster can be divided into stable area and active area, and the latter one is further divided into some exact annular area. The assignment of the points in the stable area is not changed while the points in each annular area will be adjusted within a few neighbor clusters. There are no upper or lower bounds in the whole process. Moreover, ball k-means uses ball clusters and neighbor searching along with multiple novel stratagems for reducing centroid distance computations. In comparison with the current state-of-the art accelerated exact bounded methods, the Yinyang algorithm and the Exponion algorithm, as well as other top-of-the-line tree-based and bounded methods, the ball k-means attains both higher performance and performs fewer distance calculations, especially for large-k problems. The faster speed, no extra parameters and simpler design of Ball k-means make it an all-around replacement of the naive k-means.

Automated summary

This paper presents a novel accelerated exact k-means algorithm called Ball k-means, which uses a ball to describe each cluster. The algorithm focuses on reducing the point-centroid distance computation by finding neighbor clusters for each cluster. It divides each cluster into stable and active areas, with the latter further divided into annular areas. The points in the stable area remain unchanged, while the points in each annular area are adjusted among a few neighbor clusters. The Ball k-means achieves higher performance and requires fewer distance calculations compared to other state-of-the-art accelerated exact bounded methods, making it a versatile replacement for the naive k-means algorithm.