Balls: 0 spawns, 0 merges, 0 prunes, 0 splits. Ellipses: 0 spawns, 0 merges, 0 prunes, 0 splits. Sketch:
0 spawns, 0 merges, 0 prunes, 0 splits.
Balls. Each cluster is a ball: a center and a radius, the root mean square distance of its points.
A point joins the nearest ball if it lies within that ball’s reach, a few radii out, and otherwise spawns a ball of
its own. A ball merges into a neighbor when that leaves the neighbor about as tight as it was, and splits when a tiny
two-means over its own points finds two halves well apart, which is how it notices a cluster pulling slowly in two.
Forgetting lets old points fade; a ball that no longer gets points stops counting and is eventually pruned. A
cluster counts once it holds a small share of the recent points, 2 % by default, which also caps how many can
count at once: lower it for many small clusters.
Finding the nearest ball is where the balls earn their name. After Xia et al.’s ball k-means (2020): if a point lies
within ball b’s reach, any nearer center is less than twice that reach from b, so only b’s neighbors need checking.
Each ball also links to its nearest few, so a greedy walk from the last point’s ball can cross to the right one; the
readout counts the distances that takes against the number of balls. Points arrive in no particular order, so the walk
starts anywhere, which is what a hierarchy would fix.
Ellipses. The same rules with a covariance per cluster: a point’s distance to a cluster is its
Mahalanobis distance, so the reach is a number of standard deviations along the cluster’s own axes and a long thin
cluster is one long thin ellipse instead of a chain of balls. Among the ellipses that reach a point it joins the one
it fits best by Gaussian likelihood, so a big loose ellipse doesn’t outbid a tight one. Two merge when the merged
ellipse is no bigger than the two together, and one splits when its halves are four of their own standard
deviations apart; one Gaussian’s halves sit about 2.7 apart however stretched, so a long cluster stays whole. The
search bounds each ellipse by its longest semi-axis and so stays exact, at the price of checking more neighbors
around thin ones.
Sketch + ball k-means. Online facility location keeps a few dozen weighted centers in one pass: a point
opens a new facility with probability d²/f, its squared distance to the nearest over the cost of opening one, and
otherwise joins the nearest. When there are too many, f grows and the facilities are run through the same rule again.
Every 200 points, a ball k-means with a price λ on every cluster refines the facilities into clusters, so their
number is whatever balances error against that price. Pause and step to see the probability and the draw.
Balls and the sketch struggle where clusters aren’t ball-shaped: long thin ones come apart. Ellipses hold those, but
rings and moons, which aren’t ellipses either, are still cut into arcs by all three.
Batch k-means, told the true number and given the recent points all at once, is the line to beat; on the rings it
fails too. The adjusted Rand index is 1 when a method groups the newest 600 points exactly as their true clusters do,
and about 0 when it does no better than chance.