Breathing K-Means

We introduce the breathing k-means algorithm, which significantly improves upon the widely-known greedy k-means++ algorithm, the default method for k-means clustering in the scikit-learn package. Our approach is able to improve solutions obtained by greedy k-means++ through a novel 'breathing' technique cyclically increasing and decreasing the number of centroids based on local error and utility measures. We conducted experiments using greedy k-means++ as a baseline, comparing it with breathing k-means and five other k-means algorithms. Among the methods investigated, only breathing k-means and better k-means++ consistently outperformed the baseline, with breathing k-means demonstrating a substantial lead. This superior performance was maintained even when comparing the best result of ten runs for all other algorithms to a single run of breathing k-means, demonstrating its effectiveness and speed. Our findings indicate that the breathing k-means algorithm outperforms the other k-means techniques, especially greedy k-means++ with ten repetitions, which it dominates in both solution quality and speed. This positions breathing k-means as a full replacement for greedy k-means++.