Skip to content
DSML.KZ
Publications

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

Using Annealing to Accelerate Triangle Inequality k-means

Alibek Zhakubayev, Greg Hamerly

Alibek Zhakubayev
Read on dx.doi.orgDOI 10.1109/dsaa61799.2024.10722770

Abstract

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.

Advanced Clustering Algorithms ResearchData Mining and Machine Learning ApplicationsMachine Learning and Data ClassificationK-means clusteringtriangle inequalityannealing

More by Alibek Zhakubayev