Skip to content
DSML.KZ
Publications

Talk · IEEE International Conference on Data Science and Advanced Analytics · October 6, 2024

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

Alibek Zhakubayev, Greg Hamerly

Alibek Zhakubayev
Open via DOI

Abstract

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.

Advanced Clustering Algorithms ResearchData Mining and Machine Learning ApplicationsBayesian Methods and Mixture ModelsK-means clusteringLloyd's algorithmbeta distribution

More by Alibek Zhakubayev