Angle K-Means
Shenfei Pei, Ruiyu Huang, Yiqing Hu, Zhongqi Lin, Xudong Jiang, Zengwei Zheng
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.
BibTeX
@inproceedings{
pei2026angle,
title={Angle K-Means},
author={Shenfei Pei and Ruiyu Huang and Yiqing Hu and Zhongqi Lin and Xudong Jiang and Zengwei Zheng},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=BdhQWT0y9s}
}