ML0060 K Selection in K-Means

Written by

How to select K in K-Means?

Answer

To select the optimal number of clusters $K$ in K-means, combine visual tools (the elbow method), quantitative metrics (the silhouette score), and statistical methods (the gap statistic), balancing model fit against generalization without overfitting. Domain knowledge and interpretability should have the final word.

(1) Elbow Method: Plot within-cluster sum of squares (WCSS) against $K$ and pick the “elbow” where the rate of improvement sharply slows.
(2) Silhouette Score: Compute the average silhouette coefficient for each candidate $K$ and pick the highest: it rewards tight, well-separated clusters.
(3) Gap Statistic: Compare the observed WCSS against that of a random reference distribution; pick the $K$ maximizing the gap.

WCSS curve dropping steeply from K equals 1 and flattening after the marked elbow at K equals 3

Figure 1: The elbow method: WCSS always decreases as K grows, but the marginal gain collapses after the true cluster count (the marked elbow at K = 3). Beyond the elbow you pay model complexity for noise.

Mathematical Formulation:
$\text{WCSS}(K) = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$
$s(i) = \frac{b(i) - a(i)}{\max\big(a(i),\, b(i)\big)}$

Where:

$C_k$ is cluster $k$ and $\mu_k$ its centroid; WCSS is the total within-cluster squared distance that the elbow method plots against $K$ .
$a(i)$ is point $i$ ‘s mean distance to its own cluster (intra-cluster); $b(i)$ its mean distance to the nearest other cluster.
$s(i) \in [-1, 1]$ : near 1 means well clustered, near 0 means on a boundary, negative means likely misassigned; average it over all points for each $K$ .