Beta k-Means: Accelerating k-Means Using Probabilistic Cluster Filtering

Lloyd k-means is a widely used clustering algorithm. The Hamerly and Annulus algorithms are faster versions of the Lloyd k-means, employing the triangle inequality to skip unnecessary distance computations. In this paper, we propose new probabilistic k-means clustering algorithms - Beta k-means and Beta Hamerly k-means, which converge faster than the Lloyd, Hamerly, and Annulus algorithms for a high number of clusters and dimensions. We compute the probability of a center being closest to the point, and if the probability is lower than the threshold, the distance calculation can be skipped. To the best of our knowledge, this is the first algorithm that uses Beta distribution to accelerate k-means. Experiments were conducted to demonstrate the advantages of the proposed algorithm in practice.