Nearest-Center Risk and Voronoi Partitions

From Nearest Centers to a Risk Decomposition

A squared-distance clustering rule assigns each observation to a closest center. The population risk of a fixed collection of centers is the expected squared distance from an observation to its closest center. To express this risk using regions of the feature space, we need to define those regions carefully: points can be equally close to more than one center, and the resulting assignment should be unambiguous.

Let \(X\) be a random vector taking values in \(\mathbb{R}^d\), with Borel probability distribution \(P\). Fix an ordered list of \(K\geq 1\) centers \(c_1,\ldots,c_K\in\mathbb{R}^d\). Write \(\|\cdot\|\) for the Euclidean norm. The squared-distance risk of this list is

This expectation is well-defined as a nonnegative extended real number. In particular, it is finite if \(E[\|X\|^2]<\infty\): for any fixed center \(c_1\), the minimum is at most \(\|X-c_1\|^2\), and \(\|X-c_1\|^2\leq 2\|X\|^2+2\|c_1\|^2\). No density is required; \(P\) may be discrete, continuous, or a mixture.

The order of the centers matters for this assignment rule when ties occur. The geometric comparisons are determined by the center locations, but the rule determines which cell receives a point on a tie. In particular, a tie-breaking rule is needed even if ties have probability zero: a partition of the whole space must assign every point.

Half-Space Comparisons and Cell Geometry

Comparing two squared distances gives a linear inequality in \(x\). For any indices \(i\) and \(j\),

The equivalence follows by expanding both squared norms and cancelling \(x\mathbin{\cdot}x\). Reversing the first comparison to a strict inequality reverses the resulting inequality to a strict one as well. The equality set, when the centers differ, is the perpendicular bisector of the segment joining them.

The coincident-center case follows directly: if \(c_i=c_j\), their distances are equal for every \(x\), so \(\|x-c_j\|^2\leq\|x-c_i\|^2\) always holds and the strict comparison never holds. This distinction matters when describing cells by intersections of comparisons; it cannot be inferred by treating the comparison as a nontrivial half-space.

For the smallest-index tie rule, a point belongs to \(V_j\) precisely when it is no farther from \(c_j\) than any center with a larger index, and strictly closer than every center with a smaller index. Thus

An intersection over no indices imposes no constraint. The strict comparisons exclude points tied with an earlier center, while the weak comparisons allow ties with later centers. The resulting cells need not all be closed: strict comparisons can make some parts of a cell open.

Measurability, Partition, and Risk Identity

The cell definitions give both a partition and a convenient expression for risk. The partition claim is pointwise: for every \(x\), the finite collection of distances has at least one minimum, and the smallest index attaining it is unique. The measurability claim follows from the comparison sets, which are open or closed half-spaces when centers differ and are either the whole space or empty when centers coincide.

Proof. Each squared-distance function \(x\mapsto\|x-c_i\|^2\) is continuous. For each pair \(i,j\), the weak and strict comparison sets in the definition of \(V_j\) are Borel sets: by the distance expansion, they are half-spaces when \(c_i\ne c_j\); when \(c_i=c_j\), they are respectively \(\mathbb{R}^d\) and the empty set. Each \(V_j\) is a finite intersection of such sets, so it is Borel measurable.

For any fixed \(x\), let \(j(x)\) be the smallest index attaining the minimum of the \(K\) distances. By definition, \(x\in V_{j(x)}\). If \(x\) belonged to two distinct cells \(V_j\) and \(V_\ell\), both indices would be the smallest minimizer, which is impossible. Hence the cells cover \(\mathbb{R}^d\) and are pairwise disjoint.

At each \(x\), exactly one cell indicator is 1, and its center is a nearest center. Consequently,

Both sides are nonnegative measurable functions. Integrating this pointwise identity with respect to \(P\), and using additivity of the integral for a finite sum of nonnegative functions, gives the stated risk decomposition. The identity is valid even if the risk is infinite; if \(E[\|X\|^2]<\infty\), the bound given earlier makes it finite. \(\square\)

This theorem is a representation of the risk for a fixed list of centers and a fixed assignment rule. It does not assert that any such list minimizes risk, nor that a minimizing list exists.

Higher-Dimensional Cells and Duplicate Centers

In dimensions greater than one, the pairwise comparisons have the same form. They describe which side of a perpendicular-bisector hyperplane is closer to a given center. A cell is an intersection of the relevant comparison regions. If all centers in a comparison are distinct, these regions are half-spaces. The intersection can be empty, for example if the constraints for one index are incompatible; the partition theorem still applies.

Why the Partition Representation Matters

The nearest-center representation separates two ingredients of squared-distance clustering risk: the regions to which observations are assigned and the squared distance incurred within each region. It lets us integrate with respect to an arbitrary population distribution, including distributions with atoms on boundaries. It also makes clear that a tie rule is part of a pointwise assignment definition, not a claim about how often ties occur.

A common mistake is to describe a cell only by weak inequalities and then say that ties do not matter. Weak inequalities alone can put a tied point in several cells, so the claimed sets are not a partition of the space. The correction is to state an explicit rule and use strict comparisons against earlier centers and weak comparisons against later centers. Another related error is to treat every pairwise comparison as a nontrivial half-space: if the two centers coincide, the weak comparison is all of \(\mathbb{R}^d\) and the strict one is empty. These details ensure the cell sets are measurable and the risk decomposition is valid pointwise.