Classify with Nearby Examples
k-nearest neighbors finds k training examples close to a new point and uses their answers. Classification commonly selects the majority label. The method is intuitive, but the distance definition matters.
Ask three neighbors
This example uses one numeric feature and finds the three training points closest to 2.5.
from collections import Counter
training = [(1, "small"), (2, "small"), (8, "large"), (9, "large")]
query, k = 2.5, 3
neighbors = sorted(training, key=lambda row: abs(row[0] - query))[:k]
votes = Counter(label for _, label in neighbors)
prediction = min(votes, key=lambda label: (-votes[label], label))
print(prediction)
The result is small: among nearby values 2, 1, and 8, two have that label. This example breaks ties alphabetically. Real applications should define tie handling and whether closer neighbors receive more weight.
Changing k changes the decision
- Small k: Captures fine local differences but can react strongly to noise.
- Large k: Smooths decisions but can miss smaller groups.
- Different units: Raw price and weight may let the larger numeric range dominate distance. Scale using parameters learned from training data.
Comparing all distances for n examples with d features requires O(nd) distance work. Neighbor selection adds a cost depending on the method; this example sorts.
Check your understanding
Why is it a problem to choose k by repeatedly checking test-set answers?
Show explanation
The setting becomes adapted to the test set, making its score an optimistic estimate of performance on new data. Choose k with validation data or cross-validation, and reserve the final test set for evaluation.