Definition of local minimum in k-means algorithm

Question

I know what a local minimum for a function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is. The error function in a k-means algorithm gets a vector of assignments and a vector of centers. How does the term local minimum make sense for the error function?

Answer 1

Given a set of observations $X_1, X_2, \ldots, X_N$, where each observation $X_j \in \mathcal R^n$, the $k$-means clustering algorithm's goal is to partition the $N$ observations into $k (\leq N)$ clusters $C = \{C_1, C_2, \ldots, C_k\}$ in order to minimize the within-cluster sum of squares.

The objective function for k-means clustering is

$\underset{\mu}{\mathrm{min}}\;\underset{C}{\mathrm{min}}\sum\limits_{i=1}^{k}\sum\limits_{X_j \in C_i}\|X_j-\mu_i\|^2$

where $\mu=(\mu_1, \mu_2, \ldots \mu_k)$ are cluster centroids for the clusters $C_1,C_2,\ldots,C_k$, respectively.

This function is highly non-convex and potentially prone to have multiple local minima.

The problem is NP-hard and the k-means is a coordinate descent algorithm that fixes one of $\mu$ and $C$ and optimizes the other one.

Answer 2

Here's an example of how it can happen and what's going on. Suppose there are really four clusters but you're trying for a three-cluster solution. You'll probably end up with two real clusters in one of the fitted clusters. It could be that there's an obvious best choice for which two real clusters get lumped together, but it could also be that there isn't.

If there isn't, you're still likely to get convergence to a stable solution. Given the partition into three clusters, the estimated centroids are well-defined; given the centroids, the partition into three clusters is well-defined. But if you'd initialised the algorithm at a different place you could well have converged to a different stable solution, with a different two clusters merged. These are all local minima, but only one of them can be the global minimum

The same sort of thing can happen if there aren't any real clusters, just a splodge of data. The algorithm can converge to a stable solution, but different starting points can converge to different solutions. Each possible solution is a minimum of the objective function -- you can't improve it by making small changes -- but only one of them is the global minimum.

(And the same thing can also happen without a good story as to why)