How do I mathematically prove that k-means clustering converges to minimum squared error?

Question

I am using k-means clustering to analyze and obtain patterns in traffic data. This well-known algorithm performs 2 steps per iteration.

1. Assign each object to a cluster closest to it, based on the euclidean distance between the object and a cluster's center (obtained at a previous iteration).
2. Update the centers of the clusters based on the new members of clusters.

I understand that k-means clustering overall aims to minimize the sum of the square errors. However, how can we mathematically prove that the 2 steps eventually converges to this goal? It sounds like a complicated optimization problem involving Lagrange multipliers, but maybe there is a more straightforward way to prove it?

Answer 1

1. There is no k-means algorithm. K-means is the problem. Algorithms for it include MacQueen, Lloyd/Forgy, Hartigan/Wong and many more.

2. Most of these algorithms (all but exhaustive search I guess) will only find a local optimum, not the global optimum. They are heuristics. Fast heuristics...

3. It turns out the usual nearest-center heuristic sometimes even misses the local optimum, if cluster sizes vary much. Not by much. But rarely, points should not be assigned the nearest center.

4. Global optimium search is IIRC NP-hard, so you do not want to use a perfect algorithm, unless you assume that P=NP.

Answer 2

K-means clustering does not guarantee you global optimum (although I'd not call K-means a "heuristic" technique). However you can do this: run K-means a number of times, each time with different random initial centres seed, and obtain a set of final cluster centres each time. If these sets appear similar enough - in the sense that you can easily identify the "same" final centres across the runs - then you are surely close to the global optimum. Then just average those corresponding final centres across the runs and input the obtained averaged centers as initial ones for one final run. That run is almost sure to give you the global optimum solution.

Another, similar to this, trick to obtain "good" initial centres is to randomly split the total sample into subsamples and to perform K-means on each, then again averaging the final centres and running clustering of the total sample. Yet one more way to get "good" initial centres is to run Ward hierarchical clustering first and get K clusters with it, and use their centres as the input to K-means. Read about some variants of K-means initializing.

Under the following conditions (or "assumptions") you are more likely to get at the global optimal solution in K-means clustering:

• there is cluster structure in the data, i.e. the data is not single-cluster;
• your K, the-number-of-clusters specification, is correct;
• the number of variables is not very great: K-means is sensitive to the "curse of dimensionality", with many variables, a preliminary PCA would be a good idea;
• clusters in the data are more or less spherical, and compact in their middle (such as normally distributed); variances in clusters are about equal.

K-means assignes, at each iteration, each object to the closest cluster centre. After all objects were thus assigned, the K centres are updated. It thus appears that a centre moves further towards the set of objects that were already "its" objects. That's why each iteration is an improvement, and the optimum - local or global, dependent on the initial centres choice - is reached. The optimized function is the pooled within-cluster sum-of-squares (because mean is the locus of minimal SS deviations from it), which is equivalent to minimizing the pooled within-cluster sum of pairwise squared euclidean distances normalized by the respective number-of-objects in a cluster.

Answer 3

You can actually prove that it converges to a local minimum and that, actually, you are performing Newton minimization on the quantization error functional. All the details are in the Léon Bottou and Yoshua Bengio's paper "Convergence Properties of the K-Means Algorithms"

Answer 4

The objective function in this type of clustering is to assign points to clusters in a way that the sum of squared distances to the centroids are minimized. However, with K-Means we (approximately) solve a different problem which has the same optimal solution as our original problem: \begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - y_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ &y_j \in \mathbb{R}^d \quad \forall j \end{align}

Instead of minimizing the distance to centroids, we minimize the distance to just any set of points that will give a better solution. It turns out that these points are exactly the centroids.

In this post, I have explained in detail that how the two steps of K-Means solve this optimization problem approximately.