Skip to main content
9 of 9
added 3 characters in body
wjktrs
  • 870
  • 1
  • 10

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.

wjktrs
  • 870
  • 1
  • 10