Unequal Cluster Sizes And Densities

Why Unequal Sizes and Densities Matter

K-means assigns observations to a fixed number of clusters, then places each centroid at the mean of its assigned observations. Its objective is the within-cluster sum of squares (WCSS): the sum of squared distances from each observation to its assigned centroid. Because every observation contributes one squared distance, a large cluster can contribute more to WCSS than a small cluster, even when its typical distance from its centroid is similar.

This objective does not require clusters to have equal sizes or equal densities. But it does not explicitly reward a clustering for recovering groups of unequal size, either. A cluster’s count, spread, and distance from other centroids jointly affect the objective. As a result, k-means may allocate a centroid to part of a large, diffuse group while combining a small, compact group with another one.

Definition: For observations $x_1,\ldots,x_n$ assigned to $K$ nonempty clusters $C_1,\ldots,C_K$, the centroid of cluster $C_j$ is $\bar{x}_j=(1/n_j)\sum_{i\in C_j}x_i$, where $n_j$ is its number of observations. The WCSS of the partition is $$ \operatorname{WCSS}=\sum_{j=1}^{K}\sum_{i\in C_j}\lVert x_i-\bar{x}_j\rVert^2. $$ The squared distance is Euclidean squared distance when the observations have multiple numerical features.

For a fixed partition, the centroid minimizes the sum of squared distances within that cluster. In one dimension, the squared distance is simply $(x_i-\bar{x}_j)^2$. In more dimensions, the squared Euclidean distance adds the squared differences across features. These calculations compare partitions under the specified feature scaling; changing the scale of a feature can change the distances and the resulting WCSS.

Cluster Size Multiplies Within-Cluster Spread

The effect of cluster size can be stated precisely. Define the within-cluster mean squared distance as the cluster’s WCSS divided by its number of observations. Then $$ \operatorname{WCSS}(C_j)=n_j\left(\frac{1}{n_j}\sum_{i\in C_j}\lVert x_i-\bar{x}_j\rVert^2\right). $$ Thus, if two clusters have the same within-cluster mean squared distance, the one with more observations contributes more to total WCSS. This is a statement about the objective’s weighting, not a guarantee that every large cluster will be divided: the cost of other possible assignments matters too.

Density is not an explicit term in the WCSS formula. A tight, compact group tends to have small within-cluster distances, while a diffuse group tends to have larger distances. But k-means does not estimate density or impose a minimum separation between groups. It chooses assignments and centroids to minimize total squared distance.

Worked Example: Comparing Two Partitions With Unequal Spread

Six hypothetical observations lie on a line at $0,0,3,3,8,8$. Compare two possible partitions into $K=2$ clusters: $P=\{0,0,3,3\}\mid\{8,8\}$ and $Q=\{0,0\}\mid\{3,3,8,8\}$. Recalculate each centroid and WCSS before comparing the partitions.

Method. For each cluster, find its arithmetic mean, square each observation’s deviation from that mean, and add the squared deviations. The centroids are the WCSS-minimizing representatives for the stated assignments.

For partition $P$, the first cluster has centroid $(0+0+3+3)/4=1.5$. Its WCSS is $2(0-1.5)^2+2(3-1.5)^2=2(2.25)+2(2.25)=9$. The second cluster has centroid $(8+8)/2=8$, and its WCSS is $0$. Therefore, partition $P$ has total WCSS $9+0=9$.

For partition $Q$, the first cluster has centroid $0$ and WCSS $0$. The second cluster has centroid $(3+3+8+8)/4=5.5$. Its WCSS is $2(3-5.5)^2+2(8-5.5)^2=2(6.25)+2(6.25)=25$. Therefore, partition $Q$ has total WCSS $0+25=25$.

Check. Since $9<25$, partition $P$ has the lower WCSS of these two candidates. The common arithmetic mistake is to report the first cluster’s WCSS in $P$ as $18$. There are four observations, each with squared deviation $2.25$, so the correct total is $4(2.25)=9$, not $18$.

The Cost of Merging Two Clusters

Centroid distance alone does not determine how costly it is to merge two clusters. A separation of a given size matters more when it is supported by more observations. The following identity gives the exact increase in WCSS when two clusters are merged and their centroid is recomputed.

Theorem: Suppose clusters $A$ and $B$ have sizes $n_A$ and $n_B$, centroids $\bar{x}_A$ and $\bar{x}_B$, and within-cluster WCSS values $W_A$ and $W_B$. The WCSS after merging them is $$ W_{A\cup B}=W_A+W_B+\frac{n_A n_B}{n_A+n_B}\lVert\bar{x}_A-\bar{x}_B\rVert^2. $$ The final term is the increase in WCSS due to merging.

To justify the identity, write $n=n_A+n_B$ and let the merged centroid be $\bar{x}=(n_A\bar{x}_A+n_B\bar{x}_B)/n$. For an observation $x$ in $A$, decompose its deviation as $x-\bar{x}=(x-\bar{x}_A)+(\bar{x}_A-\bar{x})$. When the squared norms are summed over $A$, the cross-products sum to zero because $\sum_{x\in A}(x-\bar{x}_A)=0$. The resulting contribution is $W_A+n_A\lVert\bar{x}_A-\bar{x}\rVert^2$. The same argument for $B$ gives $W_B+n_B\lVert\bar{x}_B-\bar{x}\rVert^2$. Finally, $\bar{x}_A-\bar{x}=[n_B/n](\bar{x}_A-\bar{x}_B)$ and $\bar{x}_B-\bar{x}=-[n_A/n](\bar{x}_A-\bar{x}_B)$. Adding the two extra terms yields \[ n_A\left(\frac{n_B}{n}\right)^2\lVert\bar{x}_A-\bar{x}_B\rVert^2+ n_B\left(\frac{n_A}{n}\right)^2\lVert\bar{x}_A-\bar{x}_B\rVert^2 =\frac{n_A n_B}{n}\lVert\bar{x}_A-\bar{x}_B\rVert^2, \] which proves the formula.

The increase depends on both cluster sizes and the squared centroid distance. If one cluster is small, the multiplier can be relatively small, so merging it with another cluster may be less costly than separating part of a large, diffuse group. This is a comparison of objective values; it does not establish that a particular resulting cluster has a meaningful interpretation.

Worked Example: A Small Compact Group Is Merged

Six hypothetical observations lie at $0,0,4,4,12,12$, and $K=2$. Suppose the scientific interpretation suggests a compact group at $0$ and a larger, more diffuse group containing the observations at $4$ and $12$. Compare the partition that preserves those two groups with one that merges the observations at $0$ and $4$.

Method. Compute both WCSS values directly. This avoids assuming that an intuitively named group must receive its own centroid.

For the interpretation-based partition, $\{0,0\}\mid\{4,4,12,12\}$, the first centroid is $0$ and its WCSS is $0$. The second centroid is $(4+4+12+12)/4=8$, and its WCSS is $2(4-8)^2+2(12-8)^2=2(16)+2(16)=64$. The total is $64$.

For the alternative partition, $\{0,0,4,4\}\mid\{12,12\}$, the first centroid is $(0+0+4+4)/4=2$, and its WCSS is $2(0-2)^2+2(4-2)^2=2(4)+2(4)=16$. The second centroid is $12$, with WCSS $0$. The total is $16$.

Check. The alternative has lower WCSS, $16<64$, even though it combines the compact observations at $0$ with those at $4$. The remaining observations at $12$ receive the other centroid. This comparison illustrates how a broad group can be split when doing so reduces total squared error substantially.

Worked Example: Quantifying a Merge Penalty

Two hypothetical clusters of policy records have sizes $n_A=3$ and $n_B=2$, centroids $2$ and $5$, and within-cluster WCSS values $W_A=2$ and $W_B=1$, respectively. Calculate the WCSS if they are merged.

Method. Apply the merging identity. The centroid separation is $|5-2|=3$, so its square is $9$. The size multiplier is $(3\cdot2)/(3+2)=6/5=1.2$.

The increase caused by merging is $1.2(9)=10.8$. The merged WCSS is the original within-cluster total plus that increase: $W_{A\cup B}=2+1+10.8=13.8$.

Check. The merged WCSS exceeds $W_A+W_B=3$ by exactly $10.8$, as the formula requires. A common mistake is to use only the squared centroid distance, $9$, as the increase. That omits the size multiplier $6/5$; the correct increase is $10.8$.

Interpreting Unequal Cluster Sizes and Densities

A small compact group can be merged when the reduction in error from using another centroid elsewhere is larger than the WCSS penalty of absorbing that group. Conversely, a large diffuse group can be divided if one centroid cannot represent its spread efficiently. These outcomes are not contradictions: k-means minimizes the total squared error across observations, not a separate score for each group.

The cluster-merging formula is useful for comparing a proposed merge with alternatives. A small centroid distance does not automatically make a merge inexpensive if both clusters are large; the multiplier may be substantial. A larger distance can have a modest merge penalty when one cluster is tiny. Always include the squared distance and both cluster sizes.

K-means also does not enforce balance. It can produce clusters with very different counts, and it can allocate multiple centroids to a broad population while leaving a compact group combined with another. If equal-size groups or density-based groups are the actual goal, WCSS alone may not express that goal. The analyst should distinguish an optimization result from a substantive claim about the population.

Common Exam Traps

Counting clusters equally. WCSS sums contributions over observations. It is not the average of one score per cluster unless an explicitly different objective is defined.
Forgetting to recalculate the centroid. After a merge, the centroid is the mean of all observations in the merged cluster, not either original centroid.
Using distance instead of squared distance. The merging penalty uses $\lVert\bar{x}_A-\bar{x}_B\rVert^2$, multiplied by $n_A n_B/(n_A+n_B)$.
Assuming the smallest or densest group must remain separate. K-means has no rule requiring each apparent population to receive a centroid.
Calling a lower-WCSS partition more meaningful without evidence. It is better under the specified objective and features; that alone does not validate its interpretation.

Key takeaway: Unequal sizes and densities affect k-means through observation-level squared distances. Compare full WCSS values, or use the merge penalty $\frac{n_A n_B}{n_A+n_B}\lVert\bar{x}_A-\bar{x}_B\rVert^2$; centroid separation by itself is not enough.

Check Your Understanding

For each problem, calculate the requested WCSS or merge penalty before reading the answer.

Six observations are $-1,-1,1,1,7,7$, with $K=2$. Compare the WCSS of $\{-1,-1,1,1\}\mid\{7,7\}$ with that of $\{-1,-1\}\mid\{1,1,7,7\}$. (Answer: The WCSS values are $4$ and $36$, respectively.)
Clusters $A$ and $B$ have sizes $4$ and $3$, centroids $1$ and $5$, and within-cluster WCSS values $6$ and $2$. What is the merged WCSS? (Answer: $248/7$, or approximately $35.4286$.)
For observations $0,0,4,4,10,10$ and $K=2$, compare $\{0,0,4,4\}\mid\{10,10\}$ with $\{0,0\}\mid\{4,4,10,10\}$. (Answer: The WCSS values are $16$ and $36$, respectively; the first partition is lower.)
Seven observations are $0,0,2,2,6,6,6$, with $K=2$. Compare the partitions $\{0,0,2,2\}\mid\{6,6,6\}$ and $\{0,0\}\mid\{2,2,6,6,6\}$. (Answer: The WCSS values are $4$ and $19.2$, respectively.)
Cluster $A$ has size $2$. Compare the increase in WCSS from merging it with $B$, of size $8$ and centroid distance $3$, against merging it with $C$, of size $2$ and centroid distance $5$. (Answer: The penalties are $14.4$ for $A$ with $B$ and $25$ for $A$ with $C$; the first merge has the smaller penalty by $10.6$.)

What You'll Learn