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.

The k-means algorithm calculates the distances be-tween all points and centers at every iteration, which results in a significant amount of wasted work and slows down the algorithm. Many algorithms have been proposed to increase the convergence speed by skipping unnecessary distance computations, often using distance bounds that are cheaply adjusted with the triangle inequality. This paper proposes an annealing technique that can further accelerate these algorithms by tightening the bounds. As a result, we skip even more distance computations and only calculate the distances when the chance of changing an assignment is high. The function that tightens the bound is adaptive and depends on the number of points that change the assignment in the last iteration. The annealing technique can speed up both Hamerly's and Elkan's accelerated algorithms without lowering the output quality. Experimental results showed a time improvement of up to 15 percent, representing a significant performance boost over the Hamerly algorithm.