Ties, Null Boundaries, and Partition Representations

Centers and Their Representations

A collection of centers does not, by itself, always specify which cluster should contain every observation. The issue arises when an observation is equally close to two or more centers. Such a tie leaves the nearest-center distortion unchanged, but a rule for resolving it can change the represented partition. It is therefore useful to distinguish the codebook from the assignment rule and the partition that the rule produces.

Let \(X\) be a random vector in \(\mathbb{R}^d\), with distribution \(P\) and \(E[\|X\|^2]<\infty\). Fix \(K\) distinct centers \(C=(c_1,\ldots,c_K)\). The codebook can be viewed as an ordered tuple or, when labels do not matter, as the set \(\{c_1,\ldots,c_K\}\). Its nearest-center risk is

R(C)=E\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right].

The finite second-moment assumption ensures this risk is finite: for any fixed center \(c_j\), \(\|X-c_j\|^2\leq 2\|X\|^2+2\|c_j\|^2\), and the minimum is no larger than this bound.

Definition: For a fixed codebook \(C\), a nearest-center assignment is a measurable map \(a:\mathbb{R}^d\to\{1,\ldots,K\}\) such that \(a(x)\) is an index attaining \(\min_j\|x-c_j\|\) for every \(x\). Its partition is the collection \(A_j=\{x:a(x)=j\}\). These sets are measurable, disjoint, and cover \(\mathbb{R}^d\); some may be empty. Two partitions are considered equivalent up to labels if a permutation of their parts makes corresponding parts equal except on sets of \(P\)-probability zero.

Measurability is not an obstacle here. There are finitely many continuous distance functions, so their comparisons define Borel sets. For example, assigning a point to the smallest index attaining the minimum gives a measurable rule. Other measurable rules may choose different indices at ties.

Voronoi Boundaries and Null Boundary Probability

The ordinary Voronoi cell of a center consists of points for which it is nearest. The cells can overlap where distances tie. Only ties for the nearest distance matter for assignments; equal distances to two centers that are both farther away than a third do not create an assignment choice.

Definition: The nearest-center tie set, or Voronoi boundary set, is \(B_C=\{x:\text{at least two distinct indices attain }\min_j\|x-c_j\|\}\). A codebook has null boundary probability when \(P(X\in B_C)=0\). A partition representation of \(C\) is the partition produced by a specified measurable nearest-center assignment.

The distinction between geometric boundaries and the tie set is worth keeping precise. The perpendicular bisector of a pair of centers contains points equally distant from that pair, but a point on that bisector belongs to \(B_C\) only if that common distance is the smallest distance to the codebook.

Theorem: If \(P(X\in B_C)=0\), then any two measurable nearest-center assignments for \(C\) agree with probability one. Consequently, they produce the same partition up to \(P\)-null sets (and hence the same partition up to labels).

Proof. Let \(a\) and \(a'\) be two nearest-center assignments. At any \(x\notin B_C\), exactly one center attains the minimum distance. Both assignments must select that center, so \(a(x)=a'(x)\). Thus the event \(\{a(X)\ne a'(X)\}\) is contained in \(\{X\in B_C\}\), and

P(a(X)\ne a'(X))\leq P(X\in B_C)=0.

For each index \(j\), the events \(\{a(X)=j\}\) and \(\{a'(X)=j\}\) therefore differ only on a null set. This is precisely equality of the corresponding labeled partition parts up to \(P\)-null sets. \(\square\)

The converse needs care. Positive probability on \(B_C\) means there is positive mass at points where an assignment choice is available. It allows different assignments to disagree on positive probability, but it does not guarantee that every pair of tie-breaking rules yields different partitions up to labels. The distribution and the choices of rules matter.

Worked Examples

Worked Example: A Tie Changes the Partition but Not the Risk

Let \(X\) take the values \(-1,0,1\), each with probability \(1/3\), and fix the codebook \(C=(-1,1)\). Compare the rules that assign a tied point to the left center and to the right center.

At \(x=-1\), the squared distances to \(-1\) and \(1\) are \(0\) and \(4\), so the nearest center is \(-1\). At \(x=1\), they are \(4\) and \(0\), so the nearest center is \(1\). At \(x=0\), both squared distances are \(1\), so there is a tie.

If the tie goes left, the two partition parts, restricted to the support of \(X\), are \(\{-1,0\}\) and \(\{1\}\). If it goes right, they are \(\{-1\}\) and \(\{0,1\}\). These are different even as unlabeled partitions: neither is obtained from the other by simply swapping the two parts.

In either case, the nearest-center squared loss at \(-1\), \(0\), and \(1\) is respectively \(0\), \(1\), and \(0\). Therefore

R(C)=\frac{1}{3}(0)+\frac{1}{3}(1)+\frac{1}{3}(0)=\frac{1}{3}.

The boundary set contains \(0\), so \(P(X\in B_C)=1/3\). The example shows directly that the codebook and its risk can stay fixed while its represented partition changes. It makes no claim that this codebook minimizes risk for this distribution.

Worked Example: A Boundary With Zero Probability

Let \(X\) be uniform on \([-2,2]\), and again take \(C=(-1,1)\). The only nearest-center tie is at \(x=0\). Since a uniform distribution assigns probability zero to a single point, \(P(X\in B_C)=0\). Assigning \(0\) to either center changes the set-theoretic partition at that point, but not the partition up to \(P\)-null sets.

The risk can also be checked explicitly. For \(x\geq 0\), the nearest center is \(1\); for \(x<0\), it is \(-1\). Thus the squared loss is \((|x|-1)^2\), and the uniform density on \([-2,2]\) is \(1/4\). By symmetry,

R(C)=\frac{1}{4}\,2\int_0^2(x-1)^2\,dx =\frac{1}{2}\left[\frac{(x-1)^3}{3}\right]_0^2 =\frac{1}{2}\left(\frac{1}{3}-\left(-\frac{1}{3}\right)\right) =\frac{1}{3}.

No matter which center receives the single boundary point, the integral and the resulting probability-equivalence class of the partition are unchanged.

Worked Example: One Partition From Different Codebooks

Let \(X\) take values \(-2\) and \(2\), each with probability \(1/2\). Compare \(C_1=\{-2,2\}\) and \(C_2=\{-3,3\}\). For either codebook, \(-2\) is assigned to the left center and \(2\) to the right center. Both codebooks therefore induce the same partition on the support: \(\{-2\}\) and \(\{2\}\).

The codebooks are nevertheless different. Their risks are different too. Under \(C_1\), both observations have zero loss, so \(R(C_1)=0\). Under \(C_2\), the squared distance is \(1\) for each observation, giving

R(C_2)=\frac{1}{2}(1)+\frac{1}{2}(1)=1.

Thus a partition does not, by itself, determine the centers. This is a representational example, not a statement that both codebooks are optimal.

Why Tie-Breaking Does Not Change Nearest-Center Risk

Theorem: For a fixed codebook \(C\), every measurable nearest-center assignment \(a\) has the same assignment-based squared risk, and that risk equals \(R(C)\): \(E[\|X-c_{a(X)}\|^2]=R(C)\).

Proof. By the definition of a nearest-center assignment, for every \(x\),

\|x-c_{a(x)}\|^2=\min_{1\leq j\leq K}\|x-c_j\|^2.

This equality holds even when there is a tie: every selected index attains the same minimum. The two sides are measurable, nonnegative functions. They are integrable because the right side is bounded above by \(2\|X\|^2+2\|c_1\|^2\), which has finite expectation. Taking expectations gives

E[\|X-c_{a(X)}\|^2] =E\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right] =R(C).

The equality is pointwise before integration, so no exchange of a limit and an integral is involved. \(\square\)

This result separates two questions that are sometimes conflated. The risk asks how close observations are to their nearest centers; the partition asks which center label is assigned to each observation. A tie can change the second answer without changing the first.

Three Notions of Uniqueness

When discussing clustering uniqueness, specify which object is meant. A codebook is unique if there is only one center set of interest, with permutations of labels ignored. A partition is unique if all relevant representations have the same partition up to labels and probability-zero differences. A representation pairs a codebook with an assignment rule. Uniqueness of one of these objects does not automatically imply uniqueness of the others.

For a fixed codebook with null boundary probability, the theorem above gives a unique partition representation in the probability-equivalence sense. If boundary probability is positive, different choices can assign positive mass differently, as in the discrete example. The geometric set on which the choices are possible is not itself enough to decide whether the resulting unlabeled partitions differ; the example verifies that they can.

Conversely, even identical partitions need not identify a unique codebook, as the two-point example shows. A partition records which observations are grouped together, not the precise locations of the centers. If an analysis needs both labels and centers, it should report the codebook and the tie convention rather than treating a partition as a complete description.

Common Mistakes

Assuming ties change the distortion. They do not: every tied center gives the same minimum squared distance at that observation. Recompute the nearest distance, not just the selected label.
Calling every pairwise bisector a relevant boundary. A tie matters for assignment only when the tied centers attain the nearest distance.
Treating a null boundary as an empty boundary. A boundary may contain points, while still having probability zero. In the uniform example, the point \(0\) is a tie but has no probability mass.
Inferring partition uniqueness from a fixed codebook without checking ties. A fixed codebook can have multiple partition representations if positive probability lies on its nearest-center tie set.
Inferring centers from a partition. The grouping alone does not specify the center locations; different codebooks can induce the same partition.

Key takeaway: Codebook, assignment, partition, and risk are related but distinct. Null boundary probability guarantees that nearest-center tie-breaking is irrelevant to the partition almost surely. Positive boundary probability can make tie-breaking alter the represented clustering, while leaving nearest-center risk exactly unchanged.

Check Your Understanding

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

For a fixed codebook, why does assigning a tied observation to either tied center leave its squared loss unchanged?
What does null boundary probability imply about two measurable nearest-center assignments? State the conclusion using probability.
In the distribution on \(\{-1,0,1\}\) with codebook \(\{-1,1\}\), calculate the squared loss at each support point and the resulting risk.
Can a boundary contain points but have probability zero? Give the feature of the uniform example that makes this possible.
Why does the partition induced by a codebook not generally determine the codebook?