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}\Vert x_i-x_j{\Vert }^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}\Vert x_i-{\bar{x}}_c{\Vert }^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}\Vert x_i-x_j{\Vert }^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.