Lloyd's method terminates when the data partition agrees with the Voronoi
partition defined by the centers; as such, Voronoi diagrams are typically
associated with k-means clustering.
In
"Hartigan's Method: k-means without Voronoi"
(Telgarsky and Vattani, to appear in AISTATS 2010), it is shown
that there is another
family of sets, lovingly termed the
circlonoi partition, which the
points must agree with for the k-means optimum to be reached. This is found
by analyzing Hartigan's method, which proceeds point by point, but allows
points to move to centers which are slightly farther away than their
current centers; the method halts only if the data agrees with its
circlonoi partition.
The interactive figure below is meant demonstrates these notions.
Apologies in advance:
google chrome is required.
Points are represented by circles, cluster centers by x's. Cliques are
formed out of clusters.
To move a point, drag it.
To delete a point, drag it out of the canvas.
The "radii" indicate points which will change cluster assignment after
an iteration of Lloyd or Hartigan. If a point can be reassigned by
Lloyd, then a black and white line segment will extend from the point and reach
the center. If only the white extension (which has a black bar at the end) can
reach the center, then only Hartigan's method can iterate. Please see section 2.2. (Points which
will inhabit an empty cluster are not marked.)
The "inner Voronoi" shows the fringe of the Voronoi cells which is
lower bounded in theorem 3.1.
When the number of points becomes large, the circlonoi boundary becomes somewhat
inaccurate. This is because the circlonoi cell radius is huge, but the allowed error at the
boundary becomes tiny; this leads to floating point problems.