k-NN Classification

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.

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

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.

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.

Common Reasoning Mistakes

• Choosing one neighbor's target as the prediction

  The ordinary regression rule uses all three selected targets with equal participation.

  Fix: Add 8, 10, and 13, then divide by 3.

• Using every available training target

  The prediction is based on the k selected nearest neighbors.

  Fix: First identify the selected neighbors, then use only their targets.

• Assuming k has no effect

  Changing k changes how many targets participate and can change the average.

  Fix: Recompute the combination using the new number of selected targets.

• Treating every combination rule as the ordinary average

  A weighted rule can assign different influence according to distance.

  Fix: Identify the rule represented by φ before combining the targets.

Practice Check

Key Takeaways

1. k-NN regression predicts a real-valued target by combining the targets of the k nearest neighbors.
2. The ordinary rule averages the selected targets, giving each one equal participation.
3. Changing k changes how many targets contribute and can change the prediction.
4. The function φ represents a generalized rule for mapping selected neighbor input-target pairs to an output target.
5. Distance-based weighted averages differ from the ordinary average because the selected targets need not have equal participation.