Empirical K-Means Risk and Sample Objectives

From Population Risk to a Sample Objective

For a clustering problem, a codebook is a collection of \(K\) centers in Euclidean space. Given a point, its squared quantization error is the squared distance to its nearest center. The population quantization risk averages that error over the distribution of future observations. In practice, the distribution is unknown, so the corresponding sample objective averages the errors over the observed data.

The sample objective is more than a convenient computational substitute: it has an exact representation in terms of cluster assignments and centers. That identity explains why the familiar within-cluster sum of squares is the objective associated with K-means, and why centroids arise when assignments are fixed.

Definition: Let \(X_1,\ldots,X_n\) be an iid sample from a distribution \(P\) on \(\mathbb{R}^d\). For a codebook \(a=(a_1,\ldots,a_K)\), where each \(a_j\in\mathbb{R}^d\), define its empirical quantization risk by

\hat R_n(a)=\frac{1}{n}\sum_{i=1}^n\min_{1\leq j\leq K}\|X_i-a_j\|^2.

The empirical optimal risk is \(\inf_{a\in(\mathbb{R}^d)^K}\hat R_n(a)\). The factor \(1/n\) makes this an average squared error; omitting that factor gives the total within-cluster sum of squares for the corresponding assignments.

For every realized finite sample, \(\hat R_n(a)\) is finite for every finite codebook. The iid assumption describes how the sample was generated; the assignment identity below is a deterministic statement about any fixed list of \(n\) points. If the population risk is also considered, a sufficient condition for it to be finite for every fixed codebook is \(E[\|X\|^2]<\infty\).

An assignment is a vector \(z=(z_1,\ldots,z_n)\) with \(z_i\in\{1,\ldots,K\}\), specifying which center is used for observation \(i\). Write \(C_j(z)=\{i:z_i=j\}\) for the indices assigned to cluster \(j\). A cluster may be empty. Its within-cluster sum of squares at centers \(a\) is the sum of squared distances from its assigned observations to their assigned centers; adding these sums over clusters gives the total assigned sum of squares.

Why the Assignment Formulation Is Exact

For a fixed codebook, each observation can be assigned to a center that attains its smallest squared distance. There are finitely many centers, so at least one such center exists, even when several are tied. Conversely, any assignment uses a center for each observation, and its assigned distance cannot be smaller than the nearest-center distance. These two facts give the exact equality below.

Theorem: For every finite sample \(X_1,\ldots,X_n\) in \(\mathbb{R}^d\) and every positive integer \(K\),

\inf_{a\in(\mathbb{R}^d)^K}\hat R_n(a) = \frac{1}{n} \min_{z\in\{1,\ldots,K\}^n} \inf_{a\in(\mathbb{R}^d)^K} \sum_{i=1}^n\|X_i-a_{z_i}\|^2.

Both sides attain their optimal values. Thus minimizing nearest-center empirical risk is equivalent to minimizing total within-cluster sum of squares jointly over assignments and centers.

Proof. Fix a codebook \(a\). For each \(i\), choose an index \(z_i\) attaining \(\min_j\|X_i-a_j\|^2\). Summing the \(n\) pointwise equalities shows that the nearest-center total equals the assigned total for this choice of \(z\). For every other assignment \(z'\), each assigned distance is at least the nearest-center distance. Therefore

\sum_{i=1}^n\min_j\|X_i-a_j\|^2 = \min_{z\in\{1,\ldots,K\}^n} \sum_{i=1}^n\|X_i-a_{z_i}\|^2.

Taking the infimum over \(a\) gives the equality of infima, since minimizing over codebooks and assignments jointly is the same as taking the infimum over all pairs \((a,z)\), in either order. There are finitely many assignments. For any fixed assignment, each nonempty cluster has a minimizing center at its sample mean, as proved below; an empty cluster contributes zero for every center. Hence each assignment has an attained minimum over centers. Minimizing these attained values over the finite set of assignments attains a joint minimum. The equality then also gives an attained minimum for the nearest-center objective. \(\square\)

Why the Centers Are Cluster Means

The joint objective becomes especially familiar after fixing the assignment. Each center then appears only in the sum for its own cluster. For a nonempty cluster, its sum of squared distances is minimized by the arithmetic mean of the assigned observations.

Theorem: For any nonempty index set \(C\subseteq\{1,\ldots,n\}\), define \(\bar X_C=|C|^{-1}\sum_{i\in C}X_i\). For every \(c\in\mathbb{R}^d\),

\sum_{i\in C}\|X_i-c\|^2 = \sum_{i\in C}\|X_i-\bar X_C\|^2 + |C|\|c-\bar X_C\|^2.

Consequently, the sum is minimized at \(c=\bar X_C\). If the observations in \(C\) are not all identical, this minimizing center is unique.

Proof. Write \(X_i-c=(X_i-\bar X_C)+(\bar X_C-c)\), and expand each squared norm using the Euclidean inner product. Summing yields the two sums of squared norms and the cross term

2\left\langle \sum_{i\in C}(X_i-\bar X_C),\bar X_C-c\right\rangle.

By the definition of the sample mean, \(\sum_{i\in C}(X_i-\bar X_C)=0\), so the cross term vanishes. This proves the identity. Its final term is nonnegative and equals zero exactly when \(c=\bar X_C\), establishing the minimizing claim. \(\square\)

For an empty cluster, there is no sample mean to compute, but its contribution to the assigned sum of squares is an empty sum, hence zero. Its center can be chosen arbitrarily without changing the objective. Combining the fixed-assignment result with the theorem above gives a useful second expression: the empirical optimum is the smallest, over all assignments, of the sums of squared deviations from the assigned clusters’ sample means, divided by \(n\).

\inf_a\hat R_n(a) = \frac{1}{n}\min_{z\in\{1,\ldots,K\}^n} \sum_{\substack{1\leq j\leq K\\ C_j(z)\ne\varnothing}} \sum_{i\in C_j(z)}\|X_i-\bar X_{C_j(z)}\|^2.

Worked Examples

Worked Example: A Fixed Assignment and Its Centroids

Take the one-dimensional observations \(1,2,6,10\), with \(K=2\), and fix the assignment \(C_1=\{1,2\}\), \(C_2=\{6,10\}\). Find the best centers for this assignment and its within-cluster sum of squares.

The first cluster mean is \((1+2)/2=1.5\), and its sum of squared deviations is

$$ (1-1.5)^2+(2-1.5)^2=0.25+0.25=0.5. $$

The second cluster mean is \((6+10)/2=8\), and its sum is

$$ (6-8)^2+(10-8)^2=4+4=8. $$

Thus the assigned sum of squares at the best centers is \(0.5+8=8.5\), and the corresponding average assigned squared error is \(8.5/4=2.125\). To check the role of the centroids, use centers \(0\) and \(6\) with the same assignment: the total is \((1-0)^2+(2-0)^2+(6-6)^2+(10-6)^2=1+4+0+16=21\), which is larger. The centroid identity guarantees that moving either center away from its cluster mean cannot improve its assigned sum of squares.

Worked Example: Finding the Best Two-Cluster Sample Objective

For the one-dimensional sample \(0,2,3,10\) and \(K=2\), find the global minimum. There are seven ways to divide four labelled observations into two nonempty, unlabeled groups: four singleton-versus-triple divisions and three pair-versus-pair divisions. For each division, centering each group at its mean gives its minimum assigned sum of squares.

If the singleton is \(0\), the other group has mean \(5\), so the total is \(0+(9+4+25)=38\). If the singleton is \(2\), the remaining values \(0,3,10\) have mean \(13/3\), giving

0+\left(0-\frac{13}{3}\right)^2+ \left(3-\frac{13}{3}\right)^2+ \left(10-\frac{13}{3}\right)^2 =\frac{169+16+289}{9} =\frac{474}{9}.

If the singleton is \(3\), the other group \(0,2,10\) has mean \(4\), and the total is \(0+(16+4+36)=56\). If the singleton is \(10\), the other group \(0,2,3\) has mean \(5/3\), and the total is

0+\left(0-\frac{5}{3}\right)^2+ \left(2-\frac{5}{3}\right)^2+ \left(3-\frac{5}{3}\right)^2 =\frac{25+1+16}{9} =\frac{42}{9} =\frac{14}{3}.

For the three pair divisions, the totals are \(2+24.5=26.5\) for \(\{0,2\}\) and \(\{3,10\}\); \(4.5+32=36.5\) for \(\{0,3\}\) and \(\{2,10\}\); and \(50+0.5=50.5\) for \(\{0,10\}\) and \(\{2,3\}\). Comparing all seven values shows that the minimum total is \(14/3\), attained by \(\{0,2,3\}\) and \(\{10\}\). The empirical risk is this total divided by four, \(7/6\). Centers \(5/3\) and \(10\) indeed give these assignments as nearest centers: \(0,2,3\) are nearer to \(5/3\) than to \(10\), while \(10\) is nearer to \(10\). Thus this assignment value is also attained by the nearest-center objective.

Worked Example: An Empty Cluster When \(K\) Exceeds the Sample Size

Suppose the sample is \(1,5\) and \(K=3\). Choose centers \(a_1=1\), \(a_2=5\), and \(a_3=100\). Assign \(1\) to the first center and \(5\) to the second. Both observations have zero nearest-center error, so \(\hat R_n(a)=(0+0)/2=0\), the smallest possible value because squared errors cannot be negative.

The third cluster is empty and contributes zero to the assigned sum of squares. Its center does not need to equal any sample mean. This example also shows why the unrestricted assignment formulation permits empty clusters: requiring exactly \(K\) nonempty clusters would be impossible when \(K>n\), even though the nearest-center objective is perfectly well-defined and can be zero.

Reading the Objective Correctly

The assignment identity clarifies two conventions that are easy to confuse. First, the empirical risk is an average, whereas the usual within-cluster sum of squares is a total. For a fixed sample size, both have the same minimizing codebooks and assignments, because one is the other multiplied by \(1/n\). Their numerical values differ by that factor.

Second, the assignment-and-center expression is minimized over both assignments and centers. If an assignment is chosen arbitrarily, its best centroid-based sum may be larger than the nearest-center risk for the best codebook. The identity does not say that every assignment is optimal; it says that optimizing over all assignments recovers the same global objective. Ties in nearest-center assignment cause no problem: any minimizing label may be selected for each tied observation.

The sample objective is random because the observations are random. Its exact equivalence to a within-cluster sum of squares is an algebraic fact, not a guarantee that its minimizer has small population risk or that a particular computational procedure finds the global minimum. Those are distinct questions. In particular, evaluating an objective at a sample-fitted codebook and interpreting that value as its risk on new observations requires care; the sample objective itself only records fit to the observed points.

Common Pitfalls

Dropping the normalization without saying so. The empirical risk is a sum divided by \(n\). The total within-cluster sum of squares has no such division. They have the same minimizer for a fixed \(n\), but not the same value.
Forcing every cluster to be nonempty. Standard nearest-center risk allows unused centers. Empty clusters contribute zero in the assignment sum, and their centers may be arbitrary.
Using an arbitrary assignment as if it were nearest-center assignment. Its assigned cost is at least the nearest-center cost for the same codebook. Equality holds when every observation is assigned to a closest center.
Claiming the sample mean minimizes every possible loss. The centroid conclusion depends on squared Euclidean distance. It follows from the displayed squared-error identity, not from a general property of all clustering objectives.

Key takeaway: The empirical K-means objective is the average nearest-center squared error. Minimizing it is exactly equivalent to minimizing assigned within-cluster sums of squares over all assignments and centers; for each fixed nonempty cluster, its best center is the sample mean.

Check Your Understanding

Use the definitions and derivations above to answer the following questions.

For a fixed codebook, why can a nearest-center assignment always be selected even when there are ties?
For a fixed assignment, what center minimizes the sum of squared distances in a nonempty cluster, and what identity proves the claim?
If the minimum total within-cluster sum of squares is \(18\) for a sample of size \(n=6\), what is the empirical risk?
Explain why allowing empty clusters matters when \(K>n\).
Does the assignment equivalence show that a particular algorithm finds the global minimum? Explain what the equivalence establishes instead.