Choosing the Number of Clusters

K-means demands you specify k before running; hierarchical clustering produces every k from 1 to n. Either way, the modeler must defend the choice.

Define the total within-cluster sum of squares.

$$W(k) = \sum_{c=1}^{k} \frac{1}{2|C_c|} \sum_{i, j \in C_c} \|x_i - x_j\|^2$$

The inner sum runs over every ordered pair in $C_c$, so each unordered pair is counted twice, and the 2 in the denominator cancels that double count. The pairwise form is slow to evaluate, so compute the same number from the centroids instead:

$$W(k) = \sum_{c=1}^{k} \sum_{i \in C_c} \|x_i - \bar{x}_c\|^2$$

Check both routes on the cluster $\{2, 4, 9\}$, whose centroid is 5. Centroid route: $9 + 1 + 16 = 26$. Pairwise route: the three unordered pairs contribute $4 + 49 + 25 = 78$, which doubles to 156 over ordered pairs, and $156/(2 \times 3) = 26$.

TRAP: Two names, two scales. An Introduction to Statistical Learning (ISLR) calls $\frac{1}{|C_c|} \sum_{i, j \in C_c} \|x_i - x_j\|^2$ the within-cluster variation of cluster c, with no 2 in the denominator, and equation 12.18 shows that...

Common mistakes

• Picking the k that minimizes W(k). W is non-increasing in k, so this always returns k = n. Useless.
• Choosing the largest absolute drop. The k=1 to k=2 step typically dominates regardless of structure. The elbow is about marginal flattening, not raw drop size.
• Maximizing mean silhouette while ignoring negative $s(i)$ values. A high average can hide a cluster full of misassigned points. Inspect the silhouette plot per cluster, not just $\bar{s}$.

Bottom line

• W(k) is non-increasing in k, so minimizing it alone always returns k = n and cannot select a cluster count by itself.
• Elbow method: plot within-cluster sum of squares W(k) against k; pick the kink where marginal gain flattens, not the largest raw drop.
• Silhouette: average a per-point score in [-1, 1] measuring fit to own cluster vs nearest neighbor; choose k with highest mean silhouette.
• Mean silhouette above 0.7 signals strong structure; below 0.25 signals essentially none.

Exam shortcut

If a prompt gives W(k) values, compute successive drops and locate where the ratio of consecutive drops collapses; that is the elbow. If it gives silhouette averages, pick the maximum unless a higher-k value is within rounding distance of the leader. If it mentions an expected log W or a reference distribution, you are in gap-statistic territory and the answer rule is "smallest k with Gap(k) ≥ Gap(k+1) − $s_{k+1}$."

The full lesson (about 1,797 words, 12 min read) adds 2 worked examples, all 6 common mistakes, a self-check, free in the app.

Learning objectives

• 5d

Browse all free Exam SRM lessons or jump into free Exam SRM practice questions.