Concepts / The General k-NN Rule

The General k-NN Rule

k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.

  • Programming
Interactive lab

Try it: k-Nearest Neighbours

How a k-nearest-neighbours classifier labels a new point: measure its distance to every known point, take the K closest, and let them vote.

How it works

  1. Measure the straight-line (Euclidean) distance from the new point to every labelled point.
  2. Rank the points from nearest to farthest.
  3. Keep the K nearest.
  4. Count how many of them belong to each class; the class with the most votes is the prediction (a tie goes to the class of the nearest tied neighbour).

Default run (15 steps): 10 labelled points and a new query point at (5, 3.5). K = 3. … Prediction: class A — A has the most votes.

Simplified: Small 2-D educational dataset (at most 30 points, three classes). Real KNN uses many features and usually scales them first.

Educational simulation

Loading the simulation…

From Neighbors to a Number

Suppose an input x needs a prediction in a regression problem. Its target belongs to the real numbers, written as Y = R, so the prediction must also be a number. k-NN regression produces that number by finding the k nearest neighbors of x and combining the target values attached to those neighbors.

Input xNeighbor orderingnearest to farthestk neighborsNeighbor targetsPrediction h_S(x)consider neighborschoose first kretrieve targetscombine
How does a new input move through neighbor selection and target aggregation to become a real-valued prediction?
Key point

The prediction does not choose only one neighbor's target. It uses all k selected targets.

The Ordinary Average Rule

The standard k-NN regression rule gives every selected neighbor equal participation. Add the k neighbor targets and divide the total by k. If the selected targets are represented by the neighbor positions π_1(x) through π_k(x), then h_S(x) denotes the prediction for x, and the summation combines the target values associated with those positions.

Target 1Add targetsDivide by kArithmetic averageTarget 2Target 3equal participationequal participationequal participationsumby k
How do the selected neighbor targets become their arithmetic average?
Worked example

A Three-Neighbor Prediction

A new input has three selected neighbors with target values 6, 9, and 12. Using the ordinary k-NN regression rule, what prediction is produced?

  1. 1
    Select the targets

    The three selected neighbors contribute the targets 6, 9, and 12.

  2. 2
    Add the targets

    The total is 6 + 9 + 12 = 27.

  3. 3
    Divide by k

    There are three selected neighbors, so divide 27 by 3.

Result

The prediction is 9.

Reading the Generalized Rule

Definition

The function φ provides a generalized way to map the selected neighbor input-target pairs to an output target. In this view, the ordinary average is one particular rule for combining the selected neighbors, rather than the only possible rule.

φcombining ruleOutput targetNeighbor pair 1input and targetNeighbor pair 2input and targetNeighbor pair kinput and targetselected pairselected pairselected pairmap
What does the function φ do to the selected neighbor input-target pairs?

The generalized perspective separates two jobs. First, k-NN identifies the selected neighbors using their ordering for x. Second, φ decides how the selected input-target pairs are mapped to the output target. Choosing the ordinary average means that φ combines the selected targets by adding them and dividing by their count.

The Effect of Changing k

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 prediction is calculated from the selected targets, changing k can change the result.

69611.2599121218k = 3k = 3k = 3k = 4k = 4k = 4k = 4
Which targets are included, and how can the prediction change when k increases?
Worked example

Increasing k

Using the generated target sequence 6, 9, 12, and 18, compare the ordinary average when k is 3 with the ordinary average when k is 4.

  1. 1
    Use k = 3

    The first three selected targets contribute: (6 + 9 + 12) divided by 3 equals 9.

  2. 2
    Use k = 4

    The first four selected targets contribute: (6 + 9 + 12 + 18) divided by 4 equals 11.25.

  3. 3
    Compare

    Increasing k adds another target to the ordinary average, so the prediction changes from 9 to 11.25.

Result

Changing k changes the set of contributing targets and can change the prediction.

Equal and Distance-Based Influence

RuleHow selected neighbors contributeResulting idea
Ordinary averageEach of the k selected targets has equal participation.Add the selected targets and divide by k.
Distance-based weighted averageThe selected targets can receive influence based on distance, with closer neighbors given more influence.The prediction need not equal the ordinary average.

Both rules combine selected neighbor information, but they do not assign influence in the same way.

Selected targetsEqual participationOrdinary averageSelected targetsDistance-basedinfluenceWeighted averagesame influencecombinecloser may influence morecombine
How does giving closer neighbors more influence differ from treating all selected neighbors equally?

The ordinary average is therefore a specific choice of φ. A different φ can represent another combining rule, such as a distance-based weighted average. The key distinction is participation: the ordinary rule gives each selected target equal participation, while a distance-based rule can give closer neighbors more influence.

Common Reasoning Mistakes

  • Common mistake

    Choosing only the nearest neighbor's target for a regression prediction.

    What it looks like

    With k = 3, using only the first neighbor's target.

    Why it fails

    The ordinary k-NN regression rule uses all three selected targets and gives each equal participation.

    Do this instead

    Combine the targets of all k selected neighbors.

  • Common mistake

    Forgetting to divide by k after adding the targets.

    What it looks like

    Adding 6, 9, and 12 to obtain 27 and stopping there.

    Why it fails

    The standard rule computes an average, not just a sum.

    Do this instead

    Divide the sum by the number of selected neighbors.

  • Common mistake

    Treating k as irrelevant to the prediction.

    What it looks like

    Assuming the prediction stays the same after increasing k.

    Why it fails

    Changing k changes how many target values contribute.

    Do this instead

    Reidentify the selected set and recompute the combination.

  • Common mistake

    Confusing an ordinary average with a distance-based weighted average.

    What it looks like

    Assuming every combining rule gives every selected neighbor equal influence.

    Why it fails

    Distance-based weighted averages can give closer neighbors more influence.

    Do this instead

    Identify the function φ or combining rule before interpreting the prediction.

Practice Check

EASY

A new input has selected neighbor targets 4, 10, and 16. Using the ordinary average rule with k = 3, compute the regression prediction. Then explain what must be reconsidered if k changes to 2.

Hints
  • Add the three target values.
  • Divide the total by 3.
  • For k = 2, use only the two targets occupying the first two positions in the neighbor ordering.

What do you think happens?

For targets 4, 10, and 16 with k = 3, what does the ordinary average rule predict?

  • 10

  • 16

  • 30

  • 3

Reveal answer
Answer:

10

The ordinary rule adds the three targets to get 30 and divides by k = 3.

Key Takeaways

  1. 1
    k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
  2. 2
    The standard rule is the ordinary average: add the k selected targets and divide by k.
  3. 3
    All selected targets participate in the ordinary average; the rule does not choose only one neighbor.
  4. 4
    Changing k changes how many targets contribute and can change the prediction.
  5. 5
    The function φ describes a generalized way to map selected neighbor input-target pairs to an output target, including rules other than the ordinary average.

At a glance

  • k-NN regression turns the target values of the k nearest neighbors into a real-valued prediction.
  • The ordinary rule gives every selected neighbor equal participation through an arithmetic average.
  • The value of k determines how many targets enter the calculation, so changing k can change the result.
  • The generalized function φ represents the rule used to map selected neighbor pairs to an output target.
  • Distance-based weighted averages differ from ordinary averages because they can give closer neighbors more influence.

Related Topics

Related concepts

More concepts starting with T