k-NN Classification
k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
From Neighbors to a Number
Suppose a new input x needs a prediction, but its target value is unknown. k-NN regression looks at the k training examples nearest to x and combines their target values. The standard rule gives every selected neighbor equal participation: add their targets and divide by k. The result is a real-valued prediction rather than a choice of one neighbor's target.
The central idea is: select neighbors first, then combine all of their target values.
Selecting the Neighbors
The value of k determines how many training targets are used. For a generated example, suppose the three nearest neighbors of a new input q have target values 8, 10, and 13. With k equal to 3, all three targets participate in the prediction. Their spatial position matters because only the selected nearest neighbors contribute; other training points are not part of this particular average.
Averaging the Target Values
A three-neighbor prediction
A new input has three selected neighbors with target values 8, 10, and 13. What prediction does the ordinary k-NN regression rule produce?
- 1Select
Use the target values attached to the three nearest neighbors: 8, 10, and 13.
- 2Add
Combine all selected targets: 8 + 10 + 13 = 31.
- 3Divide
Because three targets participate, divide the total by 3.
The prediction is 31 divided by 3, or approximately 10.33.
The important point is that the prediction is not 8, 10, or 13. It is formed from all three selected targets. In the source notation, h_S(x) denotes the prediction for x, while the neighbor index π_i(x) identifies the neighbor in position i of the ordering for x. The summation combines the targets associated with the selected neighbor positions.
Changing the Value of k
Changing k changes how many neighbor targets participate. A smaller k uses fewer targets, while a larger k uses more targets. Because the selected set can change when k changes, the resulting average can also change.
Comparing k equal to 2 and k equal to 3
A new input has nearby target values 8, 10, and 13 in neighbor order. Compare the ordinary predictions when k is 2 and when k is 3.
- 1Use k equal to 2
The first two selected targets participate: 8 and 10. Their average is 9.
- 2Use k equal to 3
The first three selected targets participate: 8, 10, and 13. Their average is approximately 10.33.
- 3Compare
Adding the third target changes the prediction from 9 to approximately 10.33.
The prediction depends on k because k controls how many neighbor targets are included.
The Generalized Function φ
The ordinary average is one particular k-NN rule. A generalized rule uses a function φ to map the selected neighbor input-target pairs to an output target. In other words, the neighbor-selection step identifies the relevant pairs, and φ specifies how those pairs are transformed and combined into the prediction.
Equal and Distance-Based Combination
Under the ordinary average rule, each of the k selected targets has equal participation. A different rule can use a distance-based weighted average, in which the contributions depend on distance. These are different combination rules: the ordinary average treats the selected targets equally, while the distance-based version gives different influence according to distance. The generalized function φ provides a way to describe either kind of rule.
| Rule | How selected targets participate | Prediction |
|---|---|---|
| Ordinary average | Each of the k targets participates equally | Sum the targets and divide by k |
| Distance-based weighted average | Participation depends on distance | Use a distance-based combination rule |
Both rules use selected neighbors, but they combine their targets differently.
Common Reasoning Mistakes
Common mistake Choosing one neighbor's target as the prediction
What it looks likeThe selected targets are 8, 10, and 13, but the prediction is reported as 10 because it belongs to the middle neighbor.
Why it failsThe ordinary regression rule uses all three selected targets with equal participation.
Do this insteadAdd 8, 10, and 13, then divide by 3.
Common mistake Using every available training target
What it looks likeA learner averages targets from points that are not among the k nearest neighbors.
Why it failsThe prediction is based on the k selected nearest neighbors.
Do this insteadFirst identify the selected neighbors, then use only their targets.
Common mistake Assuming k has no effect
What it looks likeThe prediction is kept at 9 after k changes from 2 to 3, even though the third target is 13.
Why it failsChanging k changes how many targets participate and can change the average.
Do this insteadRecompute the combination using the new number of selected targets.
Common mistake Treating every combination rule as the ordinary average
What it looks likeA distance-based weighted average is described as if every target had equal participation.
Why it failsA weighted rule can assign different influence according to distance.
Do this insteadIdentify the rule represented by φ before combining the targets.
Practice Check
A query point has target values 4, 7, and 12 attached to its three nearest neighbors. What is the ordinary k-NN regression prediction when k is 3? Then explain what changes conceptually if k is reduced to 2.
Hints
- Use all three targets when k is 3.
- For the ordinary rule, add the selected targets and divide by the number of selected targets.
- When k is reduced to 2, only two neighbor targets participate.
What do you think happens?
For target values 4, 7, and 12 with k equal to 3, what is the ordinary k-NN regression prediction?
Reveal answer
23 divided by 3, approximately 7.67
The ordinary rule combines all three selected targets and divides their sum by 3.
Key Takeaways
- 1k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
- 2The ordinary rule averages the selected targets, giving each one equal participation.
- 3Changing k changes how many targets contribute and can change the prediction.
- 4The function φ represents a generalized rule for mapping selected neighbor input-target pairs to an output target.
- 5Distance-based weighted averages differ from the ordinary average because the selected targets need not have equal participation.
At a glance
- k-NN regression uses the target values of the k nearest neighbors to predict a real-valued target.
- With the ordinary rule, add the selected targets and divide by k.
- Increasing or decreasing k changes which and how many targets contribute.
- The generalized function φ describes how selected neighbor pairs are transformed into a prediction.
- An ordinary average gives equal participation, whereas a distance-based weighted average uses a different combination rule.