Tutorials › Exam SRM - Statistics for Risk Modeling › K-Means And Within-Cluster Sum Of Squares

Home  /  Tutorials  /  Exam SRM / K-Means Clustering

Exam SRM · K-Means Clustering · Tutorial 697 of 926

K-Means And Within-Cluster Sum Of Squares

Learn to compute and interpret k-means WCSS and compare candidate clusterings using the squared-distance objective.

Intermediate 12 min read

What You'll Learn

  • Define a cluster, its centroid, and within-cluster sum of squares
  • Calculate squared Euclidean distances in one and multiple dimensions
  • Sum point-to-centroid contributions to obtain WCSS
  • Compare candidate clusterings using the objective for a fixed number of clusters
  • Recognize why WCSS is not an ordinary sum of distances
  • Interpret the limits of WCSS when comparing different cluster counts

Why K-Means Needs an Objective

A clustering divides observations into groups, but the labels alone do not say whether the groups are compact. K-means makes compactness precise by measuring how far each observation lies from the center of the group to which it is assigned. The resulting quantity is the within-cluster sum of squares, abbreviated WCSS.

The objective is useful because it gives a numerical basis for comparing candidate clusterings when the number of clusters is fixed. A smaller WCSS means that, in total, observations are closer to their assigned centers under squared Euclidean distance. It does not by itself establish that the clusters are meaningful for a particular application.

Definition: Suppose there are \(n\) observations \(x_1,\ldots,x_n\), each represented by \(p\) numerical variables, and a clustering into \(k\) nonempty clusters \(C_1,\ldots,C_k\). Let \(\mu_j\) be the centroid of cluster \(C_j\), the vector of coordinate-wise arithmetic means of its observations. The within-cluster sum of squares is $$ \operatorname{WCSS}=\sum_{j=1}^{k}\sum_{i\in C_j}\|x_i-\mu_j\|^2 =\sum_{j=1}^{k}\sum_{i\in C_j}\sum_{r=1}^{p}(x_{ir}-\mu_{jr})^2. $$ Here \(x_{ir}\) is observation \(i\)'s value on variable \(r\), and \(\mu_{jr}\) is centroid \(j\)'s coordinate for that variable. The squared Euclidean distance is the sum of the squared coordinate differences.

The centroid and the observations must be expressed in the same coordinate system. In one dimension, the squared Euclidean distance is simply \((x_i-\mu_j)^2\). With several variables, square the difference in each coordinate and then add those squared differences. WCSS adds these point-to-center contributions over every observation, counting each observation once in the cluster to which it is assigned.

In the usual k-means definition, the centroid of a cluster is its coordinate-wise arithmetic mean. This tutorial uses that definition to calculate the objective; the reason the arithmetic mean is the appropriate center is a separate result. The objective concerns a specified clustering and its centroids, or the search for a clustering that gives the smallest objective.

From the Formula to the Clustering Problem

Write \(z_i\) for the index of the cluster assigned to observation \(i\). Then the WCSS can also be written as a single sum over observations:

$$ \operatorname{WCSS}=\sum_{i=1}^{n}\|x_i-\mu_{z_i}\|^2. $$

This equation is a regrouping of the definition, not a different measure. Each observation \(i\) appears in exactly one cluster \(C_j\), namely the one indexed by \(z_i\). Its contribution is the squared distance from \(x_i\) to that cluster's centroid. Grouping the observations by their assigned clusters gives the double sum; listing them individually gives the single sum.

For fixed \(k\), the k-means clustering problem is to find a partition into \(k\) nonempty groups whose associated centroids give the smallest WCSS. The choice of assignments affects which observations contribute to each cluster and therefore affects the centroids and the objective. The goal is not to minimize the distance of only one observation, or to minimize the largest distance; it is to minimize the sum of all squared distances.

Objective: With the number of clusters \(k\) fixed, compare admissible clusterings by their WCSS. A clustering with lower WCSS is preferred by this objective. WCSS is nonnegative, and it is zero only when every observation coincides with the centroid of its assigned cluster.

The final condition follows because each contribution is a squared distance, so every contribution is nonnegative. A sum of nonnegative terms is zero exactly when every term is zero. Thus each observation must be located at its assigned centroid. This can occur, for example, if each observation is its own cluster, but it need not be possible for a smaller fixed number of clusters.

Worked Calculations

Worked Example: Comparing Two One-Dimensional Partitions

A hypothetical portfolio team represents four account profiles by one standardized numerical score: \(0,2,7,11\). For \(k=2\), compare partition A, \(\{0,2\}\) and \(\{7,11\}\), with partition B, \(\{0,7\}\) and \(\{2,11\}\). Calculate each partition's WCSS using its cluster centroids and identify which has the smaller objective. The observations are fixed values; no probability distribution is assumed.

Method. For each cluster, calculate its arithmetic-mean centroid, square each observation's deviation from that centroid, and sum all four squared deviations.

For partition A, the centroids are \( (0+2)/2=1 \) and \( (7+11)/2=9 \). The first cluster contributes \( (0-1)^2+(2-1)^2=1+1=2 \). The second contributes \( (7-9)^2+(11-9)^2=4+4=8 \). Therefore, \( \operatorname{WCSS}_A=2+8=10 \).

For partition B, the centroids are \( (0+7)/2=3.5 \) and \( (2+11)/2=6.5 \). The first cluster contributes \( (0-3.5)^2+(7-3.5)^2=12.25+12.25=24.5 \). The second contributes \( (2-6.5)^2+(11-6.5)^2=20.25+20.25=40.5 \). Therefore, \( \operatorname{WCSS}_B=24.5+40.5=65 \). Since \(10<65\), partition A has the smaller WCSS. The check is that all four observations contribute once in each calculation.

Common mistake avoided: Summing absolute deviations would give a different objective. For partition A, those deviations total \(1+1+2+2=6\), but the WCSS is \(1^2+1^2+2^2+2^2=10\). K-means uses squared Euclidean distances, not ordinary distances.

Worked Example: Calculating WCSS in Two Dimensions

A hypothetical risk team records two numerical features for four claim profiles. The observed points are \(A=(0,0)\), \(B=(2,0)\), \(C=(5,3)\), and \(D=(5,5)\). For the proposed \(k=2\) clustering \(C_1=\{A,B\}\), \(C_2=\{C,D\}\), calculate the centroids and WCSS. The points are fixed coordinates, with no probability distribution assumed.

Method. Find the mean of each coordinate within each cluster, then calculate each point's squared Euclidean distance to its assigned centroid.

For \(C_1\), the first-coordinate mean is \((0+2)/2=1\), and the second-coordinate mean is \((0+0)/2=0\). Thus \(\mu_1=(1,0)\). The contributions are \( \|A-\mu_1\|^2=(0-1)^2+(0-0)^2=1 \) and \( \|B-\mu_1\|^2=(2-1)^2+(0-0)^2=1 \). So \(C_1\) contributes \(1+1=2\).

For \(C_2\), the coordinate means are \((5+5)/2=5\) and \((3+5)/2=4\), so \(\mu_2=(5,4)\). The contributions are \( \|C-\mu_2\|^2=(5-5)^2+(3-4)^2=1 \) and \( \|D-\mu_2\|^2=(5-5)^2+(5-4)^2=1 \). So \(C_2\) contributes \(1+1=2\), giving \( \operatorname{WCSS}=2+2=4 \).

The result is checked by counting four squared-distance contributions, one for each point. A common mistake is to use only the first coordinate: that would omit the second-coordinate differences and would not calculate the two-dimensional Euclidean objective.

Worked Example: Comparing Candidate Clusterings With the Same \(k\)

A hypothetical monitoring system summarizes four locations by a single measurement: \(1,2,6,9\). It proposes two \(k=2\) partitions: partition A is \(\{1,2\}\), \(\{6,9\}\); partition B is \(\{1,6\}\), \(\{2,9\}\). Compute both WCSS values and state which partition the objective favors. No distributional assumption is made about these fixed measurements.

Method. Compute each cluster mean and then sum squared deviations from the assigned means.

For partition A, the centroids are \((1+2)/2=1.5\) and \((6+9)/2=7.5\). The squared deviations are \( (1-1.5)^2=0.25 \), \( (2-1.5)^2=0.25 \), \( (6-7.5)^2=2.25 \), and \( (9-7.5)^2=2.25 \). Therefore, \( \operatorname{WCSS}_A=0.25+0.25+2.25+2.25=5 \).

For partition B, the centroids are \((1+6)/2=3.5\) and \((2+9)/2=5.5\). The squared deviations are \( (1-3.5)^2=6.25 \), \( (6-3.5)^2=6.25 \), \( (2-5.5)^2=12.25 \), and \( (9-5.5)^2=12.25 \). Thus, \( \operatorname{WCSS}_B=6.25+6.25+12.25+12.25=37 \). Since \(5<37\), the objective favors partition A. The calculation is checked by verifying that each partition has two clusters and that each of the four observations is included once.

Common mistake avoided: Do not compare only one cluster's contribution. WCSS is the total across all clusters; an apparently compact cluster does not determine the objective if the other cluster has large squared deviations.

Interpreting and Using WCSS

WCSS measures total within-cluster squared spread in the units induced by the variables. If a single feature is measured in units such as dollars, its squared differences are in squared dollars. With multiple features, the squared coordinate differences are added. Consequently, the numerical value depends on the represented variables and their scales; it is not a unit-free measure of fit.

Squaring makes larger deviations count disproportionately. A distance of \(4\) contributes \(16\), while a distance of \(1\) contributes \(1\). That is why a few observations far from their assigned centers can have a substantial effect on the objective. It also explains why WCSS should not be described as the average distance or as the sum of unsquared distances.

A basic boundary case helps interpret the objective. If \(k=n\) and each observation forms its own cluster, every centroid equals its sole observation and WCSS is zero. For any fixed dataset, allowing more clusters cannot increase the smallest achievable WCSS, because a previous partition can be retained and, if needed, divided into smaller groups. This fact alone does not determine an appropriate number of clusters: minimizing WCSS without constraining \(k\) would favor the trivial all-singleton solution.

Key takeaway: K-means evaluates a proposed partition by adding the squared Euclidean distance from every observation to its assigned centroid. For a fixed number of clusters, minimizing this sum defines the clustering objective. Always calculate squared coordinate differences, include every observation once, and compare totals rather than selected contributions.

Check Your Understanding

For each problem, calculate the requested WCSS or comparison using squared Euclidean distances and the stated cluster assignments.

  1. A one-dimensional dataset has observations \(2,4,10\), all in one cluster. Find its centroid and WCSS. (Answer: centroid \(16/3\); WCSS \(104/3\), approximately \(34.6667\).)
  2. Four points are \(A=(0,1)\), \(B=(2,1)\), \(C=(7,4)\), and \(D=(7,8)\). For clusters \(\{A,B\}\) and \(\{C,D\}\), find the centroids and WCSS. (Answer: centroids \((1,1)\) and \((7,6)\); WCSS \(10\).)
  3. For observations \(0,2,4\), compare the WCSS of partitions \(\{0,2\},\{4\}\) and \(\{0\},\{2,4\}\). (Answer: both have WCSS \(2\); the two candidate partitions tie under this objective.)
  4. Four points are \((1,1),(3,1),(8,5),(10,5)\). For partition A, group the first two points and the last two points. For partition B, group the first and third points together and the second and fourth points together. Calculate both WCSS values and identify the lower one. (Answer: WCSS for A is \(4\); WCSS for B is \(65\); A is lower.)
  5. A fixed dataset has \(n\) distinct observations. Explain the smallest possible WCSS when \(k=n\), and why this does not make \(k=n\) an informative choice if the aim is to summarize the data with fewer groups. (Answer: WCSS is \(0\), because every observation is its own centroid; the result gives no compression into fewer groups.)

Previous

Next

Back to Tutorials
Clinical Biostats