From Center Error to Partition Error

Why Small Center Error Does Not Automatically Mean Small Partition Error

A clustering codebook assigns each observation to its nearest center. Even if every estimated center is close to its population counterpart, the assignments need not all agree: observations close to a cell boundary can switch labels under a small perturbation. The useful question is therefore not only how far the centers moved, but also how many observations lie near an assignment boundary.

This tutorial makes that distinction precise. It gives a pointwise condition under which an assignment can change, converts the condition into a probability bound, and explains why center labels must be matched before the bound is applied.

Matched Codebooks and Partition Disagreement

Let $K\geq 2$, and let $c=(c_1,\ldots,c_K)$ and $\hat c=(\hat c_1,\ldots,\hat c_K)$ be two codebooks in Euclidean space. The index $j$ identifies a matched pair of centers: $\hat c_j$ is compared with $c_j$. Define the largest matched center error by

\delta(c,\hat c)=\max_{1\leq j\leq K}\|\hat c_j-c_j\|.

For a point $x$, write $d_j(x)=\|x-c_j\|$ and $\hat d_j(x)=\|x-\hat c_j\|$. Its Voronoi label is an index minimizing the distance to a center. To make the label a function even when distances tie, fix a deterministic tie-breaking rule, such as choosing the smallest minimizing index. Write $g_c(x)$ for the label under $c$, and $g_{\hat c}(x)$ for the label under $\hat c$.

Definition: The partition disagreement probability under a random observation $X$ is $P\{g_c(X)\ne g_{\hat c}(X)\}$. Define the distance gap $\Delta_c(x)$ as the second-smallest of the $K$ numbers $d_1(x),\ldots,d_K(x)$, counting ties, minus the smallest. Thus $\Delta_c(x)\geq 0$, and it is zero exactly when the nearest center is tied.

A small distance gap means that the observation has nearly competing nearest centers. In particular, ties occur on Voronoi boundaries. The gap is a convenient way to quantify assignment ambiguity without first describing the shape of every cell.

The Pointwise Stability Bound

Theorem: For every $x$, if $g_c(x)\ne g_{\hat c}(x)$, then $\Delta_c(x)\leq 2\delta(c,\hat c)$. Consequently, for fixed codebooks, $$ P\{g_c(X)\ne g_{\hat c}(X)\} \leq P\{\Delta_c(X)\leq 2\delta(c,\hat c)\}. $$

The key fact is that moving a center by at most $\delta$ changes its distance from any fixed point by at most $\delta$. This follows directly from the triangle inequality:

\big|\hat d_j(x)-d_j(x)\big| =\big|\|x-\hat c_j\|-\|x-c_j\|\big| \leq \|\hat c_j-c_j\| \leq \delta.

Here is the full pointwise argument. Let $i=g_c(x)$ and $j=g_{\hat c}(x)$, and suppose $i\ne j$. Since $i$ is a true nearest center, $d_i(x)$ is the smallest true distance and $d_j(x)-d_i(x)\geq\Delta_c(x)$. Since $j$ is an estimated nearest center, $\hat d_j(x)\leq\hat d_i(x)$. Therefore,

\begin{aligned} \Delta_c(x) &\leq d_j(x)-d_i(x)\\ &\leq \big(\hat d_j(x)+\delta\big)-\big(\hat d_i(x)-\delta\big)\\ &\leq 2\delta. \end{aligned}

This proves the pointwise claim. The probability bound follows because the disagreement event is contained in the event $\{\Delta_c(X)\leq 2\delta\}$. The argument also covers ties: a true tie has gap zero, so it is not ruled out as a possible source of disagreement.

Worked Example: A Shifted Boundary in One Dimension

Take two true centers $c_1=-2$ and $c_2=2$, and estimated centers $\hat c_1=-1.8$ and $\hat c_2=2.2$. Each estimated center is shifted right by $0.2$, so $\delta=0.2$. Let $X$ be uniform on $[-1,1]$.

The true boundary is the midpoint of $-2$ and $2$, namely $0$. The estimated boundary is the midpoint of $-1.8$ and $2.2$, namely $0.2$. Thus the labels differ for $0<X<0.2$; endpoints do not affect the probability. The interval has length $0.2$, while the support has length $2$, giving

P\{g_c(X)\ne g_{\hat c}(X)\}=\frac{0.2}{2}=0.1.

For $x\in[-1,1]$, the two true distances differ by $2|x|$, so $\Delta_c(x)=2|x|$. The theorem’s boundary region is $\Delta_c(x)\leq 2\delta=0.4$, or $|x|\leq 0.2$. Its probability is $0.4/2=0.2$, which indeed bounds the actual disagreement probability $0.1$. The bound allows for possible disagreement anywhere in the ambiguity region; it need not be exact.

From a Pointwise Bound to a Random-Error Bound

In applications the estimated codebook is random, so $\delta$ can be random too. The pointwise result still applies for every realized pair of codebooks. For any threshold $t>0$, disagreement implies either the true gap is at most $t$, or the center error is at least $t/2$. Indeed, if $\Delta_c(X)>t$ and $2\delta<t$, the pointwise condition for disagreement cannot hold. Taking probabilities gives the following result.

Theorem: For any $t>0$, with random $\hat c$ and $\delta=\max_j\|\hat c_j-c_j\|$, $$ P\{g_c(X)\ne g_{\hat c}(X)\} \leq P\{\Delta_c(X)\leq t\}+P\{\delta\geq t/2\}. $$

No independence assumption between $X$ and $\hat c$ is needed for this inequality: it follows from containment of events and the union bound. If $X$ is a fresh test observation independent of the training data, that is a common setting for interpreting the probability, but independence is not needed for the argument itself.

The two terms have different meanings. The first counts observations in a boundary-ambiguity region for the true codebook. The second counts cases where the fitted codebook moved far enough that the chosen threshold cannot protect the assignment. Choosing $t$ balances these two contributions.

Worked Example: A Two-Dimensional Boundary Strip

Let the true centers be $c_1=(-1,0)$ and $c_2=(1,0)$, and the estimated centers be $\hat c_1=(-0.9,0)$ and $\hat c_2=(1.1,0)$. Both move $0.1$ to the right, so $\delta=0.1$. Suppose $X$ is uniform on the square $[-1,1]\times[-1,1]$.

For a point $(x_1,x_2)$, the squared distances to the two true centers are $(x_1+1)^2+x_2^2$ and $(x_1-1)^2+x_2^2$. They are equal when $x_1=0$. For the estimated centers, equality of squared distances gives

(x_1+0.9)^2+x_2^2=(x_1-1.1)^2+x_2^2, \qquad 4x_1=0.4, \qquad x_1=0.1.

Consequently, assignments differ in the strip $0<x_1<0.1$. Its area is $0.1\cdot 2=0.2$, and the square has area $4$. The disagreement probability is therefore $0.2/4=0.05$. The example shows the geometric effect directly: the boundary moves, and only observations in the swept strip change labels.

Distance Gaps and Geometric Boundary Distance

A distance gap describes competition between the nearest centers; it is not itself a Euclidean distance from the observation to a cell boundary. The connection can be made explicit. For distinct centers $c_i$ and $c_j$, the boundary between their two distance regions is the perpendicular bisector

H_{ij}=\{x:\|x-c_i\|=\|x-c_j\|\}.

If $x$ is on the $i$-side of this bisector, the signed distance to $H_{ij}$, positive on that side, is

\frac{\|x-c_j\|^2-\|x-c_i\|^2}{2\|c_j-c_i\|}.

To verify the formula, let $u=(c_j-c_i)/\|c_j-c_i\|$. Expanding the squared norms gives $\|x-c_j\|^2-\|x-c_i\|^2=2\|c_j-c_i\|\{(c_i+c_j)/2-x\}\cdot u$, which is $2\|c_j-c_i\|$ times the signed distance with the stated orientation. The formula helps explain the relationship: when $i$ is nearest and $j$ is nearly as close, $x$ is close to their bisector in this signed-distance sense.

The gap bound is often preferable because it does not require a lower bound on center separation or an upper bound on the observation range. A claim that disagreement is confined to a Euclidean tube of width proportional to $\delta$ generally needs additional geometric control. The distance-gap statement requires neither such a conversion nor a bounded-support assumption.

Worked Example: Separating Boundary Mass from Center-Error Probability

Let the true one-dimensional centers be $c_1=-1$ and $c_2=1$. Give $X$ the following distribution: probability $0.1$ at $0$; probability $0.15$ at each of $-0.1$ and $0.1$; probability $0.2$ at each of $-0.5$ and $0.5$; and probability $0.1$ at each of $-0.9$ and $0.9$. These probabilities sum to $1$. For $|x|\leq 1$, the true gap is $\Delta_c(x)=2|x|$.

Suppose an estimated codebook is obtained by shifting both centers right by the same random amount $\delta$, where $\delta=0.05$ with probability $0.8$ and $\delta=0.3$ with probability $0.2$, independently of $X$. The maximum matched center error is exactly this shift. Choose $t=0.4$. The event $\Delta_c(X)\leq t$ is $|X|\leq 0.2$, which includes $0$, $-0.1$, and $0.1$, and has probability $0.1+0.15+0.15=0.4$. Also, $P(\delta\geq t/2)=P(\delta\geq 0.2)=0.2$. Hence the theorem gives

P\{g_c(X)\ne g_{\hat c}(X)\}\leq 0.4+0.2=0.6.

The actual disagreement probability can also be checked. A common rightward shift $\delta$ moves the boundary from $0$ to $\delta$. For $\delta=0.05$, none of the support points changes label. For $\delta=0.3$, only $X=0.1$ changes label, with probability $0.15$. Thus the actual disagreement probability is $0.8(0)+0.2(0.15)=0.03$, below the valid but deliberately conservative bound $0.6$.

What the Bound Implies—and What It Does Not

The two-term inequality gives a useful qualitative implication. Suppose a sequence of fitted codebooks has matched center error $\delta_n\xrightarrow{p}0$, and the test observation is drawn from a fixed distribution for which $P\{\Delta_c(X)=0\}=0$. For fixed $t>0$, the bound gives

P\{g_c(X)\ne g_{\hat c_n}(X)\} \leq P\{\Delta_c(X)\leq t\}+P\{\delta_n\geq t/2\}.

First take $n$ large: the second term tends to zero because $\delta_n\xrightarrow{p}0$. Then let $t$ decrease to zero. The events $\{\Delta_c(X)\leq t\}$ decrease to $\{\Delta_c(X)=0\}$, so continuity of probability for decreasing events makes the first term tend to zero. Thus the disagreement probability tends to zero. The no-tie condition is important: if the distribution places mass on a true boundary, arbitrarily small perturbations can change labels for that mass.

This argument does not say that every observation’s assignment is eventually stable uniformly over the support. It controls probability under the distribution of $X$. Nor does center convergence by itself supply a numerical rate for partition error: a rate also depends on how much probability lies in the small-gap region.

Common Pitfalls

Comparing centers without matching their labels. A codebook can represent the same centers in a different order. The maximum coordinatewise error may then be large even though the geometric codebook is unchanged. Match centers first; the bound compares $\hat c_j$ with its corresponding $c_j$.
Assuming that small center error prevents all label changes. This ignores points arbitrarily close to a boundary. The correct conclusion is conditional: a changed label requires $\Delta_c(x)\leq 2\delta$.
Calling the gap a Euclidean distance to the boundary. The gap is a difference of distances. Converting it into a geometric tube width requires additional geometric conditions; the pointwise theorem itself does not.
Dropping the boundary-mass term in the probability bound. Center error can be tiny while many observations lie near a boundary. The two-term bound keeps boundary ambiguity and center estimation error separate.

Key takeaway: Matched centers with maximum displacement $\delta$ can change an observation’s Voronoi label only when its nearest and second-nearest true-center distances differ by at most $2\delta$. Partition error is controlled by combining the probability of this ambiguous region with the probability of a large center error.

Check Your Understanding

Use the distance-gap bound to reason about each situation.

Why does the triangle inequality imply $\big|\hat d_j(x)-d_j(x)\big|\leq\delta$ for every center index $j$?
If the matched center error is $0.03$, what upper bound on $\Delta_c(x)$ is necessary for a label change to be possible?
In the random-error bound, explain the roles of $P\{\Delta_c(X)\leq t\}$ and $P\{\delta\geq t/2\}$.
Why does the bound not require independence between the test observation and the estimated codebook?
What can go wrong with a claim that small center error guarantees small partition error when the distribution assigns positive probability to a Voronoi boundary?