The k-means-u* algorithm: non-local jumps and greedy retries improve
  k-means++ clustering
  We present a new clustering algorithm called k-means-u* which in many cases
is able to significantly improve the clusterings found by k-means++, the
current de-facto standard for clustering in Euclidean spaces. First we
introduce the k-means-u algorithm which starts from a result of k-means++ and
attempts to improve it with a sequence of non-local "jumps" alternated by runs
of standard k-means. Each jump transfers the "least useful" center towards the
center with the largest local error, offset by a small random vector. This is
continued as long as the error decreases and often leads to an improved
solution. Occasionally k-means-u terminates despite obvious remaining
optimization possibilities. By allowing a limited number of retries for the
last jump it is frequently possible to reach better local minima. The resulting
algorithm is called k-means-u* and dominates k-means++ wrt. solution quality
which is demonstrated empirically using various data sets. By construction the
logarithmic quality bound established for k-means++ holds for k-means-u* as
well.
