K-Means: Objective and Lloyd’s Algorithm

A retailer clusters its stores on location, sales, and floor area. K-Means converges quickly. Yet one extreme flagship store drags a centroid and absorbs several unrelated locations. The algorithm did its job. It minimized its chosen objective from its starting point. The failure came from treating that objective as a neutral definition of groups.

That much is an illustration. The rest of this lesson is not. How long the loop can run, how hard its objective is to solve exactly, how much the starting points change the answer, why a falling inertia cannot choose K — all four are published results. They are quoted below rather than paraphrased, so every claim about the loop can be checked at its source.

Each step improves or preserves the squared-distance objective until the assignments stop changing.

The loop and the label it travels under have different parents, and both are dated. The name came from a paper J. MacQueen gave at the Fifth Berkeley Symposium in 1967. It opens: “The main purpose of this paper is to describe a process for partitioning an N-dimensional population into k sets on the basis of a sample.” It is in that paper that the process “is called 'k-means'”.

The alternating assign-and-update procedure drawn here is a decade older than the name it was given. A survey of the algorithm records the descent: “It was proposed in 1957 by Lloyd [58] (and independently in 1956 by Steinhaus [71])”. Stuart Lloyd's 1957 work reached print only in 1982, in IEEE Transactions on Information Theory. Hugo Steinhaus had arrived at the same procedure independently in 1956. The five steps below have a publication history. They are not folklore that has always simply been there.

Look beyond the final labels and objective value.

Step 4 is the one with a measured price attached. Nothing inside the Lloyd loop changed — same objective, same assignment rule, same mean update. Only the seeding changed. David Arthur and Sergei Vassilvitskii ran that experiment in 2007 and called the result k-means++. Their abstract states the guarantee: “By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(log k)-competitive with the optimal clustering.” Their Theorem 3.1 bounds the seeding on its own, before a single Lloyd iteration has run: E[phi] <= 8(ln k + 2) phi_OPT. That factor of 8(ln k + 2) is the only quality guarantee the method carries.

The experiment says what the guarantee is worth in practice. On the KDD Intrusion dataset — n = 494,019 points, d = 35, with 20 trials per case and k in {10, 25, 50} — D^2 seeding cut the average final potential of plain k-means by 93.37% at k = 10 and by 99.84% at k = 50. It cut average running time by 44.49% and 66.70% as well. Faster and better, from the choice of starting points alone. When restarts of the same fit disagree, that spread is the quantity step 4 measures. It is large enough to dominate any conclusion drawn from a single run.

A small numeric example makes the optimization mechanics visible.

K-Means works best when its geometry resembles how the data is actually organized. The favorable case is compact groups well represented by their arithmetic means. The unfavorable case is groups whose identity depends on shape, density, sequence, or category. Between them sits the ambiguous case, where several compact partitions reach similar inertia and the multiple local optima are real rather than an artifact of a bad run. That third column is where the seeding evidence from the workflow bites. When partitions of nearly equal objective value exist, the starting points decide which one is returned. The objective value alone will not tell you that a different answer was available.

What K-Means offers is a fast, interpretable compression into K means under squared Euclidean geometry. That narrow contract explains both its usefulness and its failures. When the contract fits, K-Means is a strong baseline. When it does not, more restarts only optimize the wrong notion of structure more carefully.

The narrow contract is also hard to satisfy exactly, and the hardness is bounded from two directions at once. Take the low-dimensional side first. Mahajan, Nimbhorkar and Varadarajan closed it: “We show that this well-known problem is NP-hard even for instances in the plane, answering an open question posed by Dasgupta [7].” Andrea Vattani reached the same place independently, by reduction from Exact Cover by 3-Sets, in a theorem that reads “The k-means clustering problem is NP-complete even for d = 2.”

The other side is the number of clusters. In 2008 four authors reduced from densest cut and made Euclidean sum-of-squares clustering NP-hard already at k = 2. Their abstract also records something worth noticing about how such results are established: “A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al., Machine Learning 56, 9--33, 2004, is not valid. An alternate short proof is provided.” A published proof failed. A short correct one replaced it.

Two dimensions is enough, and two clusters is enough. Lloyd's loop is a heuristic for a problem with no known efficient exact solution. Its output is a partition worth auditing, not an answer worth trusting.