Concepts / Nearest-Neighbor Selection

Nearest-Neighbor Selection

The prediction does not come from choosing one neighbor's target. It combines the targets of all k selected neighbors.

  • Programming

From Neighbors to a Prediction

Suppose a new input x does not yet have a known target. The k-nearest-neighbors method looks at the training examples closest to x. In a regression problem, the target space is the set of real numbers, written as Y = R. The method uses the target values attached to the k nearest neighbors to produce one real-valued prediction.

Key point

The prediction does not come from choosing one neighbor's target. It combines the targets of all k selected neighbors.

The central question is therefore not only which point is closest. It is also how the selected target values are combined after the neighbors have been identified.

Selecting the Nearest Neighbors

For a new input x, the training examples are ordered by their distance from x. The position of a neighbor in this ordering is represented by π_i(x), where i identifies its position. The first k positions identify the k selected neighbors. Their input locations determine selection, while their attached target values are used later to calculate the prediction.

new input xqueryneighbor π₁(x)closestneighbor π₂(x)second closestneighbor π₃(x)third closestother training pointsoutside selected kdistance order 1distance order 2distance order 3later in ordering
Which training points are selected for a new input, and how does their ordered distance determine the selected set?
Worked example

Choosing Three Neighbors

A new input is compared with training points ordered from closest to farthest. If k = 3, which points contribute to the prediction?

  1. 1
    Order the points

    Use the distance ordering around the new input. The first point is π₁(x), the second is π₂(x), and the third is π₃(x).

  2. 2
    Apply k

    Because k = 3, select the first three positions in the ordering.

  3. 3
    Exclude the rest

    Points appearing after the first three do not contribute to this particular k-nearest-neighbors prediction.

Result

The selected neighbors are π₁(x), π₂(x), and π₃(x).

Averaging the Selected Targets

The standard regression rule computes an ordinary average. Add the target values of the k selected neighbors and divide by k. If h_S(x) denotes the prediction for x, then the prediction uses the target associated with each selected neighbor π_i(x). Every selected target has equal participation in this ordinary average.

selected neighborsk targetsneighbor targetsy₁, y₂, ..., yₖadd targetstotaldivide by kordinary averageh_S(x)real-valued predictionread attached valuescombineuse kproduce
How do the target values of the selected neighbors combine to produce one real-valued prediction?
Worked example

Computing an Ordinary k-NN Average

The three selected neighbors have target values 10, 20, and 30. What prediction does the ordinary k-NN regression rule produce?

  1. 1
    Identify k

    There are three selected targets, so k = 3.

  2. 2
    Add the targets

    The total is 10 + 20 + 30 = 60.

  3. 3
    Divide by k

    Divide the total by 3: 60 divided by 3 equals 20.

Result

The regression prediction is 20.

Key point

With the ordinary average rule, changing the order of the selected targets does not change the result, because each selected target contributes equally.

Changing k Changes the Result

The value of k controls how many neighbor targets participate in the prediction. A smaller k uses fewer targets, while a larger k uses more targets. Because the selected targets are the values being averaged, changing k can change both the selected set and the resulting prediction.

new input xnew input x3 selected targets10, 20, 304 selected targets10, 20, 30, 50prediction 20k = 3prediction 27.5k = 4select k = 3averageselect k = 4average
What changes in the selected neighbors and final prediction when k increases?
Worked example

Comparing Two Values of k

The ordered neighbor targets are 10, 20, 30, and 50. Compare the ordinary-average predictions for k = 3 and k = 4.

  1. 1
    Use k = 3

    Average the first three targets: 10 + 20 + 30 = 60, and 60 divided by 3 equals 20.

  2. 2
    Use k = 4

    Include the fourth target as well: 10 + 20 + 30 + 50 = 110, and 110 divided by 4 equals 27.5.

  3. 3
    Compare

    The fourth target participates when k increases from 3 to 4, so the average changes.

Result

The prediction is 20 for k = 3 and 27.5 for k = 4.

The Generalized Function φ

The ordinary average is one rule for combining the selected neighbor information. A generalized k-NN rule uses a function φ to map the selected neighbor input-target pairs to an output target. In this view, neighbor selection happens first, and φ specifies what to do with the selected pairs afterward.

input xselect k neighborsordered by distanceselected input-targetpairsφcombining ruleoutput targetcompare distancesretain selected pairsprovide inputsmap to
Where does the function φ act, and how does it transform or combine the selected neighbor pairs?

When φ is the ordinary average rule, it adds the selected target values and divides by k. Other choices of φ can define different combination rules. For example, a distance-based weighted average gives closer neighbors more influence instead of giving every selected neighbor equal influence.

RuleWhat is combinedInfluence of selected neighbors
Ordinary averageThe k selected target valuesEqual participation
Distance-based weighted averageThe k selected target values using a distance-based ruleCloser neighbors receive more influence

Both rules use selected neighbors, but they differ in how φ combines their target information.

Common Selection Mistakes

  • Common mistake

    Using only the single closest target when k is greater than 1.

    What it looks like

    For k = 3, using only the closest target instead of all three selected targets.

    Why it fails

    The standard regression rule uses all k selected targets in the average.

    Do this instead

    Identify the first k neighbors in the distance ordering, then combine all k target values.

  • Common mistake

    Selecting neighbors by their target values rather than by their distance from the new input.

    What it looks like

    Choosing the three largest target values because they seem important.

    Why it fails

    Nearest-neighbor selection is based on which training inputs are closest to x. The target values are used after selection.

    Do this instead

    Order the training inputs by distance from x before reading the attached targets.

  • Common mistake

    Changing k but keeping the old prediction.

    What it looks like

    Reporting the k = 3 average after changing the setting to k = 4.

    Why it fails

    Changing k changes how many target values participate, so the average may change.

    Do this instead

    Rebuild the selected set and recompute the combination rule whenever k changes.

  • Common mistake

    Assuming every k-NN rule must be an ordinary average.

    What it looks like

    Treating a distance-based weighted average as if every neighbor had equal influence.

    Why it fails

    The generalized function φ can specify other ways to map selected neighbor pairs to an output target.

    Do this instead

    Identify the rule represented by φ before deciding how the selected targets contribute.

Practice the Prediction

EASY

A new input has four nearest neighbors with target values ordered by distance as 6, 12, 18, and 30. Using the ordinary average rule, calculate the prediction for k = 2 and for k = 4. Then explain why the two predictions differ.

Hints
  • For k = 2, use only the first two target values in the distance ordering.
  • For k = 4, use all four target values.
  • For each value of k, add the selected targets and divide by k.
Worked example

Practice Solution

Use the ordered target values 6, 12, 18, and 30 to calculate the ordinary-average predictions for k = 2 and k = 4.

  1. 1
    Calculate k = 2

    Use 6 and 12. Their sum is 18, and 18 divided by 2 equals 9.

  2. 2
    Calculate k = 4

    Use 6, 12, 18, and 30. Their sum is 66, and 66 divided by 4 equals 16.5.

  3. 3
    Explain the difference

    The k = 4 calculation includes two additional target values, so it produces a different average.

Result

The prediction is 9 for k = 2 and 16.5 for k = 4.

Key Takeaways

  1. 1
    k-NN regression predicts a real-valued target from the targets attached to the k nearest neighbors.
  2. 2
    The standard rule adds the k selected targets and divides by k, giving every selected target equal participation.
  3. 3
    The value of k determines how many neighbor targets contribute, so changing k can change the prediction.
  4. 4
    The function φ describes a generalized rule for mapping selected neighbor input-target pairs to an output target.
  5. 5
    A distance-based weighted average is different from an ordinary average because closer neighbors receive more influence.

At a glance

  • Select neighbors according to their distance from the new input.
  • For ordinary k-NN regression, average the target values of the k selected neighbors.
  • Increasing or decreasing k changes the set of targets that participates in the prediction.
  • The generalized function φ represents the rule used to combine selected neighbor input-target pairs.
  • Equal participation describes the ordinary average, while distance-based weighting gives closer neighbors more influence.

Related Topics

Related concepts

More concepts starting with N