Angle K-Means

Abstract

We propose an accelerated exact $k$-means algorithm, Angle $k$-means. As its name suggests, the algorithm mainly leverages angular relationships between data points and cluster centers to reduce computational overhead. Although grounded in straightforward geometric principles, it delivers substantial performance improvements in empirical evaluations. In contrast to existing acceleration techniques, our model introduces no new hyperparameters, preserving full compatibility with standard $k$-means. Theoretical analysis shows that Angle $k$-means maintains linear time complexity with respect to both sample size and dimensionality, while empirical evaluations on diverse real-world datasets demonstrate significant speedup over state-of-the-art algorithms such as ball $k$-means and Exp-ns.