K-means: Deriving Lloyd’s Algorithm, Choosing Centres and Diagnosing Failure

Start with the representation

Suppose each customer has two features: monthly spending and number of visits. A centre represents a typical feature vector, and each customer is assigned to the nearest representative. This is a compression problem before it is a discovery problem: replace many vectors with a small codebook while keeping squared error small.

Spending measured in cents rather than pounds changes the geometry unless the features are scaled. Standardisation is one possible modelling choice, not a universal correction. If monetary differences genuinely matter more than visit counts, equalising their variances may remove that preference. Decide what distance means before selecting k.

The objective and the two updates

For vectors \(x_i\in\mathbb R^d\), assignments \(z_i\in\{1,\ldots,k\}\) and centres \(\mu_j\), minimise

With centres fixed, each observation contributes independently. Choose the centre with the smallest squared distance. With assignments fixed, differentiate the cost of one nonempty cluster:

The arithmetic mean is therefore the exact minimiser for that assignment. It is not an interchangeable choice of representative: changing to an absolute-distance objective leads toward medians or medoids, not the same update.

Lloyd’s algorithm repeats these two conditional minimisations. Under a consistent tie rule and appropriate handling of empty clusters it terminates at a stable partition, or an implementation stops at a tolerance. Monotonic improvement does not imply the globally best partition. A centre can never reach another arrangement if doing so requires an initially worse assignment.

Work through a full iteration

Take the one-dimensional data \(0,2,3,9,10\) and initialise centres at 0 and 3. The initial assignments are \(\{0\}\) and \(\{2,3,9,10\}\). Their centres update to 0 and 6, reducing the objective from 86 to 50.

Reassigning with a tie sent to the first centre gives \(\{0,2,3\}\) and \(\{9,10\}\). The updated centres are \(5/3\) and \(9.5\). Their squared-error contributions are \(14/3\) and \(1/2\), for a total of \(31/6\approx5.167\). Another assignment step changes nothing.

points = [0.0, 2.0, 3.0, 9.0, 10.0]
centres = [0.0, 3.0]
objectives = []
for _ in range(10):
    labels = [min(range(2), key=lambda j: (x-centres[j])**2)
              for x in points]
    groups = [[x for x, z in zip(points, labels) if z == j]
              for j in range(2)]
    assert all(groups)  # This example never creates an empty cluster.
    updated = [sum(g)/len(g) for g in groups]
    objectives.append(sum((x-updated[z])**2
                          for x, z in zip(points, labels)))
    if updated == centres:
        break
    centres = updated
assert all(b <= a + 1e-12 for a, b in zip(objectives, objectives[1:]))
assert abs(objectives[-1] - 31/6) < 1e-10

This deliberately small implementation exposes the mechanism. A production implementation also needs an empty-cluster policy, iteration limits, efficient distance computation and reproducible initialisation.

Why k-means++ helps

Choose the first centre from the observations. For each later centre, let \(D_i\) be the distance to the closest already selected centre, and sample observation i with probability proportional to \(D_i^2\). If candidate squared distances are 1, 4 and 25, their probabilities are \(1/30,4/30,25/30\).

This spreads initial representatives across regions that are currently badly represented. The original k-means++ analysis bounds expected seeded objective relative to the optimum; it does not promise that every run discovers a scientifically meaningful grouping. Multiple initialisations remain useful. Report the restart count explicitly rather than relying on a library default.

What the geometry permits

Nearest-centre boundaries are hyperplanes, giving convex Voronoi cells. K-means can quantise an elongated cloud, but it may divide it across its long axis rather than preserve a domain-defined group. Two concentric rings cannot be represented as two ordinary nearest-centroid regions. More restarts cannot repair that mismatch.

Squared distance also gives faraway points large influence. Adding a single extreme customer can move a mean substantially or consume a centre. K-medoids changes the representative and loss; DBSCAN changes the definition of a cluster and can leave observations unassigned.

Choosing k and validating the result

The globally optimal training objective cannot increase as k grows. Therefore choosing the smallest training error selects as many centres as allowed. An elbow is a heuristic, and separate local optimisation runs may even produce small violations of the expected decreasing pattern.

Use clustering evaluation to examine stability, silhouettes, representative observations and domain utility. If the goal is compression, held-out quantisation error is relevant. If the goal is customer segmentation, verify that the segments support a useful decision and persist under plausible data changes.

A full assignment pass costs roughly \(O(nkd)\); T passes cost \(O(Tnkd)\) before acceleration. Mini-batch k-means trades exact full-data updates for cheaper stochastic ones. Record feature transformations, centres, random seed, objective and cluster sizes so another person can reproduce the partition.

References

1. Arthur and Vassilvitskii. k-means++: The Advantages of Careful Seeding. SODA, 2007.
2. scikit-learn. Clustering user guide.