The General k-NN Rule
k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
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.
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.
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?
Select the targets: The three selected neighbors contribute the targets 6, 9, and 12.
Add the targets: The total is 6 + 9 + 12 = 27.
Divide by k: There are three selected neighbors, so divide 27 by 3.
The prediction is 9.
Reading the Generalized Rule
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.
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.
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.
Use k = 3: The first three selected targets contribute: (6 + 9 + 12) divided by 3 equals 9.
Use k = 4: The first four selected targets contribute: (6 + 9 + 12 + 18) divided by 4 equals 11.25.
Compare: Increasing k adds another target to the ordinary average, so the prediction changes from 9 to 11.25.
Changing k changes the set of contributing targets and can change the prediction.
Equal and Distance-Based Influence
| Rule | How selected neighbors contribute | Resulting idea |
|---|---|---|
| Ordinary average | Each of the k selected targets has equal participation. | Add the selected targets and divide by k. |
| Distance-based weighted average | The selected targets can receive influence based on distance, with closer neighbors given more influence. | The prediction need not equal the ordinary average. |
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
Choosing only the nearest neighbor's target for a regression prediction.
The ordinary k-NN regression rule uses all three selected targets and gives each equal participation.
Fix:
Combine the targets of all k selected neighbors.Forgetting to divide by k after adding the targets.
The standard rule computes an average, not just a sum.
Fix:
Divide the sum by the number of selected neighbors.Treating k as irrelevant to the prediction.
Changing k changes how many target values contribute.
Fix:
Reidentify the selected set and recompute the combination.Confusing an ordinary average with a distance-based weighted average.
Distance-based weighted averages can give closer neighbors more influence.
Fix:
Identify the function φ or combining rule before interpreting the prediction.
Practice Check
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?
Reveal answer
Answer: 10
The ordinary rule adds the three targets to get 30 and divides by k = 3.
Key Takeaways
- k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
- The standard rule is the ordinary average: add the k selected targets and divide by k.
- All selected targets participate in the ordinary average; the rule does not choose only one neighbor.
- Changing k changes how many targets contribute and can change the prediction.
- The function φ describes a generalized way to map selected neighbor input-target pairs to an output target, including rules other than the ordinary average.
Key Takeaways
- 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.