Two Ways to Define a Neighborhood
A nearest-neighbor prediction uses observations near a query point, but “near” can be defined in two different ways. One method fixes the number of observations and lets the distance vary. The other fixes the distance and lets the number of observations vary. This distinction matters when training observations are concentrated in some regions of predictor space and sparse in others.
The earlier material on KNN establishes that predictions can be based on nearby observations and that distance depends on the chosen metric and predictor scaling. Here, assume that the metric has already been selected and that all distances are measured consistently. The focus is how a neighborhood is defined and what its size implies.
Thus, fixed-k methods adapt the radius to the local data, while fixed-radius methods adapt the count. With no tie at the kth distance, a fixed-k neighborhood contains exactly \(k\) observations. A closed fixed-radius neighborhood uses the condition distance \(\leq r\), so observations exactly on its boundary are included. When distances tie at a fixed-k boundary, a rule for selecting among tied observations may be needed; the examples below avoid such ties.
Counting Neighbors Carefully
For a one-dimensional predictor, distance is the absolute difference between the observation and the query. For a Euclidean distance in several dimensions, the distance is the square root of the sum of squared coordinate differences. In either case, the reliable procedure is to calculate every distance, sort them for fixed k, and compare each distance with the stated radius for a fixed-radius count.
Worked Example: Correcting the kth-Distance Calculation
A hypothetical training set has one-dimensional predictor values \(2,5,8,13,19\), and the query is \(10\). Find the radius of its \(k=2\) neighborhood. Separately, count the observations in a fixed-radius neighborhood with radius \(4\), and compare the two neighborhoods.
Method. Calculate the absolute distance from every training value to \(10\):
Sort these distances in increasing order: \(2,3,5,8,9\). The second-smallest distance is \(3\), so the fixed-k neighborhood has radius \(3\). Its two observations are \(8\) and \(13\), at distances \(2\) and \(3\).
For radius \(4\), include every observation with distance at most \(4\). The distances satisfying this condition are \(2\) and \(3\), corresponding to values \(8\) and \(13\). The fixed-radius count is therefore \(2\).
The two neighborhoods happen to contain the same observations in this case, but that is not guaranteed. The check is that the kth radius is the kth-smallest distance, not the distance to whichever observation appears second in the original data order. A common mistake is to report \(2\) as the \(k=2\) radius because it is the smallest distance; the correction is to use the second-smallest distance, \(3\).
Worked Example: Same Query, Different Counts
A hypothetical two-dimensional classification data set has query point \((0,0)\) and five training observations: \(A=(1,0)\), class L; \(B=(0,2)\), class R; \(C=(3,0)\), class R; \(D=(0,4)\), class L; and \(E=(5,0)\), class R. Use Euclidean distance. Find the neighborhood for \(k=3\), then find the count and class fractions for radius \(4\).
Method. Because the query is the origin, the Euclidean distance of \((a,b)\) is \(\sqrt{a^2+b^2}\). The distances are \(1\) for \(A\), \(2\) for \(B\), \(3\) for \(C\), \(4\) for \(D\), and \(5\) for \(E\).
The three nearest observations are \(A,B,C\). The \(k=3\) neighborhood has radius \(3\) and count \(3\). Within it, two of the three labels are R, so the local class fraction for R is \(2/3\); one label is L, so its fraction is \(1/3\).
For a fixed radius of \(4\), the condition is distance \(\leq 4\). It includes \(A,B,C,D\), giving a count of \(4\). There are two L labels and two R labels, so each class fraction is \(2/4=1/2\).
The fixed-radius neighborhood contains one more observation than the fixed-k neighborhood and has different class fractions. The count difference is not an error: the radius was held fixed, not the number of observations. The common mistake is to stop after finding the three nearest observations and assume that a radius-\(4\) neighborhood must also contain three. Counting all distances up to and including \(4\) gives the correct result.
Why Local Density Changes the Comparison
Suppose predictor observations are densely packed near a query. A small radius may include many observations there. In a sparse region, the same radius may include only a few—or none. A fixed-k rule avoids that changing count by reaching farther in sparse regions and staying closer in dense regions. A fixed-radius rule does the reverse: it preserves a common distance scale but allows the amount of available local data to vary.
A simple approximation makes this relationship explicit. Suppose the \(n\) training predictors are independent draws from a smooth density \(f\) in \(d\) dimensions, and consider a query point \(x\) away from the edge of the predictor space. Let \(B(x,r)\) be the ball of radius \(r\) centered at \(x\), under the chosen distance metric. The probability that one training predictor falls in this ball is the integral of its density over the ball. If \(r\) is small enough that the density changes little across the ball, this probability is approximately \(f(x)V_d r^d\), where \(V_d\) is the volume of the unit ball in \(d\) dimensions.
The number of training observations in the ball is a sum of \(n\) indicator variables, one for each observation. By linearity of expectation, its expected value is \(n\) times the probability that one observation falls in the ball. Therefore, the expected fixed-radius count is approximately \(n f(x)V_d r^d\). For a fixed-k neighborhood, solving this approximation for the radius gives the approximate kth-neighbor distance.
The approximation is most useful as an explanation of the direction of the effect, not as an exact prediction for a small sample. It assumes a locally smooth density, a sufficiently small neighborhood, and a query away from boundaries. At a high-density point, a fixed radius has a larger expected count, and the radius needed to reach \(k\) observations is smaller. At a low-density point, the fixed-radius count is smaller, and the kth-neighbor radius is larger.
Worked Example: Comparing Dense and Sparse Regions
A hypothetical one-dimensional training set is \(\{-1,-0.4,0.2,0.6,2,8,11,15\}\). Compare neighborhoods at query points \(0\) and \(10\). At each query, find the \(k=3\) radius and the count within fixed radius \(1\). Use absolute distance.
At query \(0\). The distances, in the order of the listed observations, are \(1,0.4,0.2,0.6,2,8,11,15\). Sorted, they are \(0.2,0.4,0.6,1,2,8,11,15\). The third-neighbor radius is \(0.6\), and the three nearest observations are \(0.2,-0.4,0.6\). For fixed radius \(1\), the observations \(-1,-0.4,0.2,0.6\) are all within the boundary, so the count is \(4\).
At query \(10\). The distances to the listed observations are \(11,10.4,9.8,9.4,8,2,1,5\). Sorted, they are \(1,2,5,8,9.4,9.8,10.4,11\). The third-neighbor radius is \(5\), and the three nearest observations are \(11,8,15\). For fixed radius \(1\), only observation \(11\) is within the boundary, so the count is \(1\).
At the dense query \(0\), the third-neighbor radius is small and radius \(1\) contains four observations. At the sparse query \(10\), reaching three observations requires a much larger radius, while radius \(1\) contains only one. These results illustrate the density effect directly. The common mistake is to confuse a fixed-k radius with a fixed radius: the values \(0.6\) and \(5\) are the radii needed to reach three observations, not the fixed radius used to count observations.
Choosing Between the Two Rules
Neither neighborhood rule is universally preferable. The choice depends on what a stable neighborhood is meant to preserve and on how predictor density varies in the region where predictions are needed.
| Feature | Fixed-k neighborhood | Fixed-radius neighborhood |
|---|---|---|
| Held constant | Number of selected observations | Maximum distance from the query |
| Adapts to local density | Radius: smaller in dense regions, larger in sparse regions | Count: larger in dense regions, smaller in sparse regions |
| Useful when | A prediction needs a chosen amount of local data | A common distance scale defines what counts as locally relevant |
| Potential concern | In sparse regions, selected observations may be far from the query | In sparse regions, few observations may be available for a prediction |
A fixed-k rule can be attractive when a prediction needs a minimum, controlled number of nearby observations. Its radius can nevertheless become large in sparse regions, so some selected observations may be only relatively close. A fixed-radius rule is useful when observations beyond a particular distance should not contribute merely to fill a quota. Its count can then vary substantially, and an extremely sparse neighborhood may not provide enough information for a stable prediction.
These interpretations rely on a meaningful distance scale. If one predictor is measured in large numerical units and another in small units, the raw distance can be dominated by the first unless the features have been appropriately handled. This issue does not change the definitions of fixed k and fixed radius, but it can make either neighborhood rule misleading. In multiple dimensions, the volume term \(V_d r^d\) also helps explain why neighborhood counts can behave differently from the one-dimensional examples.
Check Your Understanding
For each problem, distinguish the kth-neighbor radius from the count in a fixed-radius neighborhood. Use the stated metric and include observations exactly on a fixed-radius boundary.
- A one-dimensional training set is \(1,4,9,12,20\), with query \(10\). Find the \(k=3\) radius and the count within fixed radius \(5\). (Answer: \(k=3\) radius \(6\); fixed-radius count \(2\).)
- Using Euclidean distance from query \((1,1)\), consider observations \((2,1),(1,3),(5,1),(1,6)\). Find the \(k=2\) radius and the count within fixed radius \(4\). (Answer: \(k=2\) radius \(2\); fixed-radius count \(3\).)
- A one-dimensional training set is \(0,2,5,9,14\), with query \(6\). Find the \(k=3\) radius and the count within fixed radius \(3\). (Answer: \(k=3\) radius \(4\); fixed-radius count \(2\).)
- A one-dimensional training set is \(-0.5,0.2,0.8,6,9,12,16\). Compare the \(k=2\) radius at query \(0\) and query \(10\). Also give the fixed-radius-\(1\) count at each query. (Answer: kth radii are \(0.5\) at \(0\) and \(2\) at \(10\); fixed-radius counts are \(3\) at \(0\) and \(1\) at \(10\).)
- In a region where predictor density is higher, explain what happens to the expected count for a fixed radius and to the approximate radius required for fixed k, compared with a lower-density region. (Answer: The fixed-radius expected count is higher, while the fixed-k radius is smaller.)