Termination conditions for K-means and their interconnection

Question

As far as I know, there are two termination criteria for K-means clustering algorithm:

1. assignments of data points do not change
2. centroids do not change

I wonder if there is any kind of relation between these criteria. Do they imply each other?

Answer 1

Near convergence, the means can change ever so slightly; however, the small change in means may not be enough to warrant an object being closer to another cluster than the one it's currently assigned to. K-means stops when objects are no longer swapped between clusters. Some algorithms may monitor the means, but the "vanilla-flavored" K-means monitors object swapping. So the answer could likely be: "it depends on the K-means algorithm (software)." Software houses can do anything they want during algorithm development - obviously.

If an algorithm monitored change in means, it would need to establish some sort of convergence criterion like the norm of all of the delta vectors for each centroid vector at iteration $t$ and iteration $t-1$.

Perhaps something like the following for $K$ clusters (centroids) each having $p$ dimensions:

$||\Delta||$<1E-4,

where

$\Delta=\begin{bmatrix} \delta_{11} & \delta_{12} &\cdots& \delta_{1k} &\cdots &\delta_{1K} \\ \delta_{21} & \delta_{22} &\cdots & \delta_{2k} &\cdots & \delta_{2K} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \delta_{j1} & \delta_{j2} &\cdots &\delta_{jk} &\cdots & \delta_{jK} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \delta_{p1} & \delta_{p2}& \cdots & \delta_{pk} &\cdots & \delta_{pK} \\ \end{bmatrix}$,

where $\delta_{jk}$ is equal to the difference between $\mu_{jk}^{(t)}$ and $\mu_{jk}^{(t-1)}$, the mean difference of the $j$th feature within the $k$th centroid at iterations $t$ and $t-1$.

Convergence criteria like the one above is similar to what's employed for a lot of unsupervised clustering and manifold learning algorithms. However, for the simple cartoon example of K-means clustering, there's no need to wait for a low value of the norm for the above $\Delta$ matrix, since object swapping between clusters will stop changing before the above convergence criteria is met. In addition, you would have to toy around with what the optimal convergence criteria is: 1E-4, 1E-8, 1E-12, etc. Whereas, stopping when object swapping terminates is more "adaptive" to the dataset and centroids used, occurs much earlier, and is therefore much less computationally expensive.

Answer 2

Note that there is more than one algorithm for obtaining a K-means clustering. The literature is to some extent confusing as some literature uses the term "K-means" for a specific algorithm (mostly Lloyd's algorithm as explained below, sometimes attributed to MacQueen), whereas other literature (which I like more) uses the term "K-means" for the general optimisation problem, for which you then can have several algorithms (which only deliver a local optimum that depends on initialisation unless the dataset is very small or initialisation is fixed and deterministic).

One of the most popular and maybe the most simple K-means algorithm is Lloyd's algorithm, which alternates (i) assigning all observation to the closest mean and (ii) compute the mean from the new cluster assignments.

Normally for Lloyd, if the observations don't change anymore, the means remain the same as well, and if the means remain the same, the observations are all again assigned to the same clusters. The only potential exception is if there are observations that are exactly equally close to two means, in which case their assignment is ambiguous. What happens then depends on how the assignment is exactly implemented. In any case I believe that it is hard to construct examples for any assignment rule in which after equality of the means occurred once many further steps are needed for convergence of the assignments, and I think this happens very rarely. I can conceive situations in which the means don't change at some point but they start changing again for a few steps afterwards due to assignment changes of ambiguous observations (if assignment is random in case of ambiguity, convergence may not be guaranteed).

There may be other algorithms which play out differently. The Hartigan-Wong algorithm as used as default in R-function kmeans will stop if no assignment change can be found anymore that improves the objective function, in which case also centroids are no longer changed, and on the other hand if only one observation changes clusters (as is the case for a single Hartigan-Wong step), centroids will always change unless an observation is changed that is exactly the centroid for both the cluster where it originally comes from and where it goes, which once more is extremely rare and can only happen in the beginning due to weird initialisation. I won't comment on further algorithms.