Neighborhood Size and Geometric Coverage

Why Neighborhood Size Is a Geometric Question

A nearest-neighbor method finds training observations close to a query point. The number of observations requested, \(k\), does not by itself say how close those observations will be. If training data are dense near the query, the kth neighbor may be very close; if observations are sparse, the same \(k\) can require a much larger radius. Predictor dimension matters too: a ball's volume grows at a different rate with radius in one dimension than in several dimensions.

This tutorial describes that relationship using geometry and probability mass. The calculations concern the distance needed to cover a neighborhood, not how the responses of its observations are combined. Unless stated otherwise, distances are Euclidean distances after any required feature scaling, and \(p\) denotes the number of continuous predictor dimensions being considered.

The training predictor vectors are assumed to be independent draws from a distribution with density \(f\), unless an example says otherwise. A density describes probability per unit volume; probability is obtained by integrating it over a region. When the distribution has support \(\mathcal{D}\), observations can occur only in \(\mathcal{D}\).

From Probability Mass to a Neighborhood Radius

Write \(q_x(r)=P(X\in B(x,r))\). For a fixed radius \(r\), the number \(N_r\) of training observations in the ball has a binomial distribution:

The event \(R_k(x)\le r\) occurs exactly when at least \(k\) observations fall inside the ball. Thus, when the predictor distribution is continuous so that ties in distance have probability zero,

This is the exact distributional statement. A useful characteristic-radius approximation sets the expected count \(nq_x(r)\) equal to \(k\). It locates a radius at which the ball contains about the requested number of observations on average. It is not, in general, an exact formula for \(E[R_k(x)]\); randomness in the count and the nonlinear conversion from probability mass to distance matter.

For an interior point \(x\) where \(f\) is continuous and positive, the density is approximately \(f(x)\) throughout a sufficiently small ball. In \(p\) dimensions, the volume of a Euclidean ball of radius \(r\) is \(c_p r^p\), where \(c_p\) is the volume of the unit ball. Consequently, for a small interior ball,

Substitute this expression into \(nq_x(r_k)\approx k\), then solve for the radius:

Why the Dimension Changes the Radius

The formula follows from matching the expected count in a local ball to \(k\). With density held fixed, the ball must have volume about \(k/\{nf(x)\}\). Since its volume is \(c_p r^p\), taking the \(p\)th root converts that required volume to a radius. This is the reason for the exponent \(1/p\): the radius is not proportional to the required volume when \(p>1\).

The unit-ball constants for the first three dimensions are \(c_1=2\), \(c_2=\pi\), and \(c_3=4\pi/3\). In one dimension, a ball is an interval of length \(2r\). In two dimensions it is a disk, and in three dimensions it is a sphere. More generally, if the density and sample size are fixed, increasing \(k\) increases the characteristic radius by the factor \(k^{1/p}\). The radius grows with \(k\), but the rate depends on dimension.

In higher dimensions, the radius can be much larger even when the required probability mass is unchanged. A fixed volume is spread across more directions; the radius has to expand enough for the \(p\)-dimensional ball to enclose that volume.

Boundaries and Uneven Density

The interior approximation \(f(x)c_p r^p\) requires care near the edge of the predictor domain. In general, the probability mass is the integral over the part of the ball where observations can occur:

If the density is approximately constant near \(x\), this integral is approximately \(f(x)\) times the volume of \(B(x,r)\cap\mathcal{D}\). A boundary can make that intersection smaller than the full ball. But when density varies within the region, it is not generally valid to claim that the mass is less than \(f(x)c_p r^p\): higher density elsewhere in the ball can change the comparison. In that setting, use the integral rather than a full-ball calculation.

Interpreting Coverage and Avoiding Traps

A neighborhood radius summarizes how far one must search to gather a specified number of observations. A large radius at a given \(k\) signals that those observations cover a wider predictor region; it does not mean the data are uniformly distributed within that region. Local density, domain shape, and distance scaling all affect what the radius represents.

• Do not confuse a count with a mass. The expected count is \(nq_x(r)\); \(q_x(r)\) is a probability. Set \(nq_x(r)\approx k\), not \(q_x(r)\approx k\).
• Do not call the approximation an exact expected distance. The binomial count is random, and converting probability mass to radius is nonlinear. The exact distribution is given by \(P(R_k(x)\le r)=P(N_r\ge k)\).
• Do not assume a full ball fits near an edge. Integrate over the intersection of the ball with the support. Under approximately constant density, the boundary-adjusted volume is appropriate; under varying density, use the density integral.
• Do not use the same radius formula blindly across dimensions. The exponent and unit-ball volume depend on \(p\), and the assumptions of local constancy and an interior point must be checked.

These calculations are useful for judging whether a nominal neighborhood is genuinely local or instead spans a broad region of predictor space. They also explain why the same \(k\) need not provide comparable local coverage across datasets with different dimensions or predictor densities. This geometric perspective is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.