K-Nearest Neighbours: Let Nearby Examples Vote
Sometimes nearby examples are the useful clue
K-Nearest Neighbours, or KNN, predicts a new row by looking at the training examples closest to it. For classification, the nearby labels vote. For regression, nearby target values can be averaged.
Key Points
- K is the number of neighbours considered.
- Distance defines what nearby means.
- The algorithm stores the training data rather than learning a compact coefficient formula.
- Prediction cost can grow as the training set grows.
Distance needs comparable features
A common distance is Euclidean distance: √Σ(xⱼ − zⱼ)². x and z are two rows, and j indexes the features. A feature measured in rupees can dominate a feature measured in years unless the columns are scaled.
Key Points
- Scale numeric features using training data only.
- Encode categories carefully; a fake numeric order can create misleading distances.
- Remove or handle missing values before distance calculation.
- Distance is a modelling choice, not a neutral fact.
Find the nearest rows
1training = [
2 ((1, 1), "blue"),
3 ((2, 1), "blue"),
4 ((5, 4), "red"),
5]
6query = (2, 2)
7
8def squared_distance(left, right):
9 return sum((a - b) ** 2 for a, b in zip(left, right))
10
11ranked = sorted((squared_distance(features, query), label) for features, label in training)
12print("Nearest first:", ranked)Nearest first: [(1, 'blue'), (2, 'blue'), (13, 'red')]
Both blue rows are closer than the red row, with squared distances of 1 and 2. Squared distance is enough for ranking because the square-root operation preserves order.
The majority vote gives a class
For K = 3, take the three nearest labels and choose the most common class. An odd K can reduce ties in binary classification, but it does not solve every boundary problem.
1from collections import Counter
2
3nearest_labels = ["blue", "blue", "red"]
4prediction = Counter(nearest_labels).most_common(1)[0][0]
5
6print("Neighbour labels:", nearest_labels)
7print("Prediction:", prediction)Neighbour labels: ['blue', 'blue', 'red'] Prediction: blue
K controls smoothness
A small K lets a prediction respond to a very local neighbourhood. It can capture detailed boundaries but may be sensitive to noise. A large K averages over a wider region and can produce a smoother, more biased boundary.
Key Points
- K = 1 can have very low training error and high variance.
- Large K approaches a majority-class prediction.
- Choose K with validation or cross-validation.
- The useful K depends on data density and the cost of errors.
Weighted neighbours can respect distance
Instead of giving every neighbour one equal vote, weight closer neighbours more strongly. A common choice gives weight proportional to 1 ÷ distance, with a safe rule for an exact match.
Key Points
- Equal voting is simple and robust when distances are trustworthy.
- Distance weighting can make a very close example matter more.
- A single noisy close point can also dominate.
- Validate the weighting choice rather than assuming it helps.
KNN has a lazy training phase
KNN does little parameter fitting. Most work happens when predicting: calculate distances from the new row to many stored rows, sort or search for neighbours, and vote. This is why KNN is called a lazy learner.
Key Points
- Training can be fast.
- Prediction can be slow and memory-heavy.
- Approximate neighbour indexes can help at scale.
- Changing the stored dataset changes future predictions directly.
A boundary appears from the data geometry
KNN does not learn a global line. Its decision boundary follows where the local class density changes. That can capture curved shapes, but it can also behave poorly in sparse or high-dimensional spaces.
Key Points
- High-dimensional distance becomes less useful as many points look similarly far away.
- Irrelevant features can distort neighbours.
- Feature selection and scaling are central to KNN performance.
- Inspect predictions near boundaries and in sparse regions.
Where people get confused
Key Points
- “KNN learns no model.” It stores a data-dependent prediction rule and still has hyperparameters.
- “K is the number of classes.” K is the number of neighbours.
- “Raw units are harmless.” A large-scale feature can dominate distance.
- “K = 1 is most accurate.” It can memorise noise and have high variance.
- “KNN is always simple in production.” Prediction cost and memory can be significant.
Quick check
How does KNN classify a new row?
It finds the K nearest training rows using a distance rule and predicts the class with the strongest vote, optionally weighted by distance.
Why should KNN features usually be scaled?
Distance combines feature differences. A feature with much larger numeric units can dominate the distance even if it is not more informative.
What happens when K is very small?
The model can follow local details and noise closely, reducing bias but often increasing variance.
Why can KNN be slow at prediction time?
It may need to compare a new row with many stored training rows before selecting neighbours.
Recap
Key Points
- KNN predicts from nearby labelled examples.
- Distance, scaling, feature quality, and K determine the neighbourhood.
- Small K is local and variable; large K is smoother and more biased.
- The next lesson uses probability assumptions about features with Naive Bayes.
Theia
Can you explain this concept?
Practise K-Nearest Neighbours: Let Nearby Examples Vote with realistic interview questions. Choose spoken or typed answers, get feedback on your reasoning, then return to the material that needs work.
Sign in to practise this conceptThe session stays focused on this lesson. Your selected interview level sets the bar.