Using Annealing to Accelerate Triangle Inequality k-means

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.