Breathing K-Means
  The k-means++ algorithm is the de-facto standard for finding approximate
solutions to the k-means problem. A widely used implementation is provided by
the scikit-learn Python package for machine learning. We propose the breathing
k-means algorithm, which on average significantly outperforms scikit-learn's
k-means++ w.r.t. both solution quality and execution speed. The initialization
step in the new method is done by k-means++ but without the usual (and costly)
repetitions (ten in scikit-learn). The core of the new method is a sequence of
"breathing cycles," each consisting of a "breathe in" step where the number of
centroids is increased by m and a "breathe out" step where m centroids are
removed. Each step is ended by a run of Lloyd's algorithm. The parameter m is
decreased until zero, at which point the algorithm terminates. With the default
(m = 5), breathing k-means dominates scikit-learn's k-means++. This is
demonstrated via experiments on various data sets, including all those from the
original k-means++ publication. By setting m to smaller or larger values, one
can optionally produce faster or better solutions, respectively. For larger
values of m, e.g., m = 20, breathing k-means likely is the new SOTA for the
k-means problem.
