Tutorials › Statistical Learning (Graduate) › Population Quantization Risk for Fixed-K Clustering

Home  /  Tutorials  /  Clustering Risk and Consistency

Clustering Risk and Consistency · Tutorial 641 of 989

Population Quantization Risk for Fixed-K Clustering

Learn to define and compare fixed-\(K\) codebooks through their population distortion, without confusing an optimal set of centers with its induced clustering.

Advanced 9 min read

What You'll Learn

  • Define a \(K\)-center codebook and its squared-distance population risk.
  • State the moment condition that makes the risk finite.
  • Distinguish the codebook optimization problem from a partition of the feature space.
  • Explain how ties, relabeling, and repeated centers affect induced clusters.
  • Verify risk minimization and codebook comparisons with explicit distributions.
  • Prove a continuity bound for the population risk on bounded codebooks.

Population Risk as the Clustering Objective

A clustering algorithm returns centers, but the statistical question is not only where those centers lie. We also need a criterion for comparing them under the distribution of future observations. For squared-distance clustering, that criterion is the expected squared distance from a random observation to its closest center. It is a population quantity: it depends on the distribution, not on a particular observed sample.

Fix a dimension \(d\) and a positive integer \(K\). Let \(X\) be a random vector in \(\mathbb{R}^d\) with distribution \(F\). Throughout, assume \(E\|X\|^2<\infty\), unless a statement explicitly requires less. This second-moment condition ensures that the population risk defined below is finite for every fixed finite codebook.

Definition: A \(K\)-center codebook is an ordered tuple \(c=(c_1,\ldots,c_K)\) with each \(c_j\in\mathbb{R}^d\). Repeated centers are allowed, so the tuple has \(K\) entries but may have fewer than \(K\) distinct points. Its squared-distance distortion at \(x\in\mathbb{R}^d\) is $$ \delta_c(x)=\min_{1\leq j\leq K}\|x-c_j\|^2. $$ The population quantization risk of \(c\) under \(F\) is $$ R_F(c)=E[\delta_c(X)]=\int_{\mathbb{R}^d}\min_{1\leq j\leq K}\|x-c_j\|^2\,dF(x). $$ The fixed-\(K\) population optimization problem is to find a codebook minimizing \(R_F(c)\), or, without assuming a minimizer exists, to determine its infimum \(R^*_{K,F}=\inf_{c\in(\mathbb{R}^d)^K}R_F(c)\).

The minimum in the definition means that an observation is charged the squared distance to its closest available center. This objective uses the distribution of \(X\) and the locations of the centers; it does not require that a sample has already been drawn. The moment assumption guarantees finiteness because, for any fixed center \(c_1\), \(\delta_c(X)\leq\|X-c_1\|^2\), and \(\|X-c_1\|^2\leq 2\|X\|^2+2\|c_1\|^2\).

Codebooks, Minimizers, and Partitions

A codebook is a tuple of points. A partition, by contrast, divides the feature space into groups. A codebook can be used to assign each observation to a center that achieves the minimum distance, thereby inducing groups. To make this precise, assign \(x\) to the smallest index among the indices attaining \(\min_j\|x-c_j\|\). The set assigned to index \(j\) is the \(j\)th cell. These cells are measurable: each is specified by finitely many weak or strict comparisons between continuous distance functions.

This tie rule is a convenient convention, not part of the risk definition. If two or more centers are equally close, another tie rule can assign the tied point differently without changing its distortion. In particular, assignments that differ only on a set of \(F\)-probability zero give the same population risk. A cell may also have probability zero or be empty; the definition of a \(K\)-center codebook does not require every center to receive observations.

A risk minimizer is a codebook \(c\) satisfying \(R_F(c)=R^*_{K,F}\). The optimization is over center tuples, not directly over partitions. A partition alone does not specify center locations and therefore does not determine the squared distances in the risk. Conversely, different codebooks can induce the same partition of the probability-bearing part of the space while having different risks. The next results and examples make these distinctions explicit.

Worked Example: A One-Center Risk With Two Possible Values

Let \(X\) equal \(0\) with probability \(1/4\) and \(2\) with probability \(3/4\). For \(K=1\), a codebook consists of one real number \(c\), and its risk is

$$ R_F(c)=\frac14c^2+\frac34(2-c)^2 =\frac14c^2+\frac34(4-4c+c^2) =c^2-3c+3 =\left(c-\frac32\right)^2+\frac34. $$

The squared term is nonnegative and equals zero at \(c=3/2\). Thus \(c=3/2\) is the unique minimizer and the minimum risk is \(3/4\). The calculation illustrates the population objective directly: each possible observation contributes its squared distance, weighted by its probability. It does not rely on a sample-based criterion.

Worked Example: The Same Partition Can Have Different Risks

Let \(X\) be uniform on \(\{0,1,2\}\), and consider the two codebooks \(c=(0,1)\) and \(c'=(0,1.2)\). Under \(c\), the point \(0\) is assigned to the first center, while \(1\) and \(2\) are assigned to the second. Under \(c'\), the point \(0\) is assigned to \(0\), since its distances to the centers are \(0\) and \(1.2\); the point \(1\) is assigned to \(1.2\), since its distances are \(1\) and \(0.2\); and \(2\) is assigned to \(1.2\), since its distances are \(2\) and \(0.8\). The induced partition of the support is \(\{0\}\) and \(\{1,2\}\) for both codebooks.

For \(c\), the three squared distances to the closest center are \(0,0,1\), so \(R_F(c)=(0+0+1)/3=1/3\). For \(c'\), they are \(0,(0.2)^2,(0.8)^2\), so

$$ R_F(c')=\frac{0+0.04+0.64}{3} =\frac{0.68}{3} =\frac{17}{75}. $$

Since \(17/75<1/3\), the risks differ even though the partition of the support is the same. This is why a partition cannot stand in for a codebook in the population optimization problem.

Basic Properties of the Risk

Proposition: For a fixed distribution \(F\), permuting the entries of a codebook does not change its population risk. Moreover, under the finite-second-moment assumption, a codebook has risk zero if and only if \(P(X\in\{c_1,\ldots,c_K\})=1\).

Proof. A permutation only changes the order in which the same \(K\) squared distances appear. Their minimum is unchanged at every \(x\), so the distortion function and its expectation are unchanged. For the second claim, \(\delta_c(X)\) is nonnegative. A nonnegative random variable has expectation zero exactly when it is zero almost surely. At any \(x\), \(\delta_c(x)=0\) exactly when \(x=c_j\) for at least one \(j\). Therefore \(R_F(c)=0\) exactly when \(X\) belongs to the set of codebook points with probability one. \(\square\)

The permutation property means that ordered tuples can represent the same unordered set of centers. Thus a minimizer need not be unique as an ordered tuple even when its set of center locations is fixed. The zero-risk characterization is also useful: if the distribution places all its probability on at most \(K\) distinct points, choosing those points as centers gives zero risk. The converse says that zero risk is impossible unless the distribution is concentrated on the codebook points.

Worked Example: Relabeling a Zero-Risk Codebook

Suppose \(X\) is equally likely to be \(-1\) or \(1\), and let \(K=2\). For \(c=(-1,1)\), each possible observation is itself a center, so both squared distances to the closest center are zero and \(R_F(c)=0\). For the permuted tuple \(c'=(1,-1)\), the two possible observations are again centers, so \(R_F(c')=0\) as well.

With the smallest-index tie convention, the labeled groups for \(c\) are \(\{-1\}\) and \(\{1\}\); for \(c'\), those labels are reversed. The unordered partition and the risk are unchanged. This is a concrete instance of label symmetry, not a different clustering quality.

The risk is also stable to small changes in the center locations, provided the codebooks remain bounded. This matters because it makes the population objective a continuous function of the codebook on bounded regions. The bound below gives a direct quantitative statement.

Theorem: Suppose \(E\|X\|^2<\infty\). Let \(c=(c_1,\ldots,c_K)\) and \(c'=(c'_1,\ldots,c'_K)\) satisfy \(\max_j\|c_j\|\leq B\) and \(\max_j\|c'_j\|\leq B\), and define \(\Delta=\max_j\|c_j-c'_j\|\). Then $$ |R_F(c)-R_F(c')|\leq 2\Delta\big(E\|X\|+B\big). $$ In particular, the risk is continuous as a function of the codebook on every bounded set.

Proof. For a fixed \(x\), write \(d_c(x)=\min_j\|x-c_j\|\). For each \(j\), the triangle inequality gives \(\|x-c_j\|\leq\|x-c'_j\|+\Delta\). Taking minima yields \(d_c(x)\leq d_{c'}(x)+\Delta\). Reversing the roles of \(c\) and \(c'\) gives \(|d_c(x)-d_{c'}(x)|\leq\Delta\). Also, the center norm bounds imply \(d_c(x)\leq\|x\|+B\) and \(d_{c'}(x)\leq\|x\|+B\). Consequently,

$$ |\delta_c(x)-\delta_{c'}(x)| =|d_c(x)^2-d_{c'}(x)^2| =|d_c(x)-d_{c'}(x)|\{d_c(x)+d_{c'}(x)\} \leq 2\Delta(\|x\|+B). $$

Taking expectations and using \(|E[U]-E[V]|\leq E|U-V|\) for integrable \(U,V\) gives \(|R_F(c)-R_F(c')|\leq2\Delta(E\|X\|+B)\). The expectation on the right is finite because \(E\|X\|^2<\infty\) implies \(E\|X\|<\infty\). As \(\Delta\) tends to zero within a bounded set, the upper bound tends to zero, proving continuity. \(\square\)

Comparing Different Values of \(K\)

Although this tutorial fixes \(K\) when defining the optimization problem, it is helpful to see how the optimum changes when one more center is allowed. Let \(R^*_{K,F}\) denote the infimum over all \(K\)-entry tuples. Given any \(K\)-center tuple, append a copy of one of its centers to form a \((K+1)\)-entry tuple. The minimum distance at every \(x\) is unchanged, so the risk is unchanged. Taking infima therefore gives \(R^*_{K+1,F}\leq R^*_{K,F}\). This comparison does not claim that the decrease is strict: an extra center may provide no improvement for a particular distribution.

More centers can reduce the best achievable distortion, but the population risk alone does not specify how to select \(K\). That decision requires a separate criterion or modeling goal. Likewise, the definition of \(R^*_{K,F}\) as an infimum does not itself assert that some codebook attains it. Existence of optimal codebooks requires additional analysis.

Common Mistake: Treating a Partition as the Optimizer

A tempting argument is: “The clusters are the groups of observations, so if two codebooks produce the same groups, they must have the same objective.” This is false. Squared-distance risk depends on the actual center coordinates, not only on which group each point joins; the calculation for \(c=(0,1)\) and \(c'=(0,1.2)\) gave different risks for the same partition of the support.

The correction is to keep three objects distinct: the distribution \(F\), the codebook \(c\), and the assignment or partition induced by \(c\). The risk compares codebooks under \(F\). A partition records assignments, and ties or relabeling can change its representation without changing risk. In particular, a risk minimizer is defined by minimizing \(R_F(c)\), not by being a uniquely defined partition.

Key takeaway: Fixed-\(K\) population quantization minimizes expected squared distance to a codebook of \(K\) centers. Risk is a property of the distribution and the center locations; the induced partition is a related representation, not a substitute for the optimizing codebook.

Check Your Understanding

Work through these questions using the definitions and calculations above.

  1. For \(K=1\), write the population risk when \(X\) takes values \(0\) and \(3\) with probabilities \(1/2\) each. What value of the center minimizes that risk?
  2. Why does \(E\|X\|^2<\infty\) ensure that a fixed codebook has finite population risk?
  3. Give a reason that permuting the entries of a codebook leaves its risk unchanged.
  4. Can a codebook have \(K\) entries but fewer than \(K\) nonempty induced groups? Explain.
  5. What does the zero-risk characterization imply about the distribution of \(X\) when a codebook has risk zero?

Previous

Next

Back to Tutorials
Clinical Biostats