K-Nearest Neighbours (kNN)

Blinkit wants each dark store to have the right number of delivery partners. It sorts stores into three classes by how much they deliver: Class 1, High traffic (many partners), Class 2, Moderate and Class 3, Low (very few). Each store is described by its Region (Tier-1, 2 or 3 city) and its delivery counts for Fresh, Milk, Grocery, Frozen, Detergents_Paper and Delicassen. When a new store opens, which class does it belong in?

Three facts about this data decide which model can work. It is multi-class (three answers, not two). It is imbalanced (far fewer High-traffic stores than the others). And when you plot it, the classes curl around each other, so it is non-linear — no straight line separates them. Keep these three in mind; the rest of the module is about a model that handles all three.

Logistic regression draws a straight boundary between two classes. To bend the boundary you add polynomial features (f1², f1·f2, …) and search for the right degree. To handle three classes it trains one model per class (one-vs-rest). So on Blinkit's data you would be searching polynomial degrees for three separate models.

Now imagine a million stores and 50 store types instead of 3: fifty models, each with its own search for the right polynomial features. That is slow, expensive and fragile. What we want is a model with no assumed shape for the boundary and one model for any number of classes — which is exactly what kNN is.

Plot the stores as points. If a new store lands in the middle of a cluster of High-traffic stores, you would call it High traffic without doing any maths — its neighbours tell you. kNN turns that instinct into a rule: find the k stored points nearest the new one, and let them vote.

There is no equation to fit and no shape to assume, so the boundary can be as curved as the data needs, and three classes are no harder than two. This is why kNN handles exactly the problems logistic regression struggled with: non-linear, multi-class data.

To classify a query point: 1. Distance — measure how far it is from every training point (usually the Euclidean distance, the straight-line distance). 2. Sort — order the training points from nearest to farthest. 3. Pick k — keep the first k. 4. Vote — the class that appears most among those k is the prediction.

That is the whole model. Nothing is learned in advance — the training data *is* the model, and all the work happens when a question arrives. Working it by hand once makes every later idea (the effect of k, scaling, speed) obvious.

With k = 4 in the example, the four nearest are x1 (class 1), x5 (class 2), x6 (class 2), x2 (class 1): two votes for class 1 and two for class 2 — a tie, and no clear answer. With two classes, an odd k can never tie. With three or more classes it still can (k = 5 might give 2, 2 and 1 votes).

A tie has to be broken somehow, and silently. scikit-learn picks whichever tied class comes first in sorted order; other implementations pick at random. Either way the prediction for that point is arbitrary, so it is better to choose k to avoid ties, or to weight votes by distance so the nearer neighbours win.

The four steps are a few lines of NumPy: compute all distances at once, sort, take the first k labels, count them. Writing it yourself once is the fastest way to be sure you understand what scikit-learn does for you.

It shows there is no hidden training: the function takes the stored data and the query every time. It also shows where the time goes — the distance line touches every stored row for every query.

In practice: split the data into train, validation and test; balance the classes in the training set only (the lecture uses SMOTE); fit a StandardScaler on the training data; then KNeighborsClassifier. fit just stores the scaled training rows; predict does the search.

On Blinkit's stores this reaches about 0.90 accuracy on the validation set with k = 5, and the confusion matrix shows most mistakes are on Class 1 — the smallest class. It confirms kNN handles multi-class, non-linear data with no feature engineering at all.

kNN assumes that points close together share the same class — that each neighbourhood is homogeneous. The prediction for a new point is simply whatever its neighbours are.

When that holds, kNN is excellent. When the data is noisy — mislabelled stores, outliers scattered inside other classes — the neighbourhoods are mixed and the votes become unreliable, so kNN makes mistakes exactly where the data is messy.

With k = 1, each prediction copies the single nearest point — even when that point is an outlier. The model follows every quirk of the training data: low bias, high variance, it overfits. With k = all the data (say 72 of 72 points), every query gets the overall majority class, whatever its neighbourhood: high bias, low variance, it underfits.

k is one number that slides kNN from overfitting to underfitting, so it is the clearest picture of the bias-variance trade-off in the course. Training accuracy falls as k grows; validation accuracy rises, peaks, then falls. The best k sits at that peak.

k is a hyperparameter — you choose it; the model does not learn it. Try a range of values, score each on the validation set (never the test set), and keep the best. On Blinkit's stores the lecture tries k = 1 to 50; validation accuracy is highest at small k (about 0.915 at k = 3) and falls steadily after about k = 17.

Choosing k on the training set would always pick k = 1, and choosing it on the test set would leave you no honest final check. The validation set exists for exactly this decision. Cross-validation (GridSearchCV) does the same job more reliably on small data.

Colour every spot on the plane by the class kNN would predict there, and you see its decision boundary. It bends wherever the data bends — it is non-linear, with no formula behind it — and a small k makes it jagged, a large k makes it smooth.

It shows directly why kNN succeeded where a straight-line model struggled: the boundary between Blinkit's store classes follows the curved shape of the data, and three classes each get their own region.

Training: O(1) — it only stores the data. Space: O(n × d) — it keeps all n rows of d columns. Prediction: O(n × d + n log n) per query — a distance to every row, then a sort (O(n × d + n log k) with a partial sort). Picking and voting over k rows is tiny next to that.

This is kNN's biggest practical cost, and the reverse of most models: instant to train, slow to answer. With a million stores and thousands of queries a second, searching every row for every query is too slow — which is why real systems use fast approximate search (see LSH below).

Distance adds up the differences in every column. If Fresh deliveries run into the tens of thousands and Region is 1, 2 or 3, a difference of 5,000 in Fresh drowns out everything else — the "nearest" stores are just the ones with similar Fresh counts. StandardScaler puts every column on the same scale so each one counts.

Without scaling, kNN quietly becomes a model of your largest column. Scaling is not an optional tidy-up for kNN; it changes which points are neighbours, and so every prediction.

Distance needs numbers, so text categories must be converted. Take a diabetes dataset with Gender (M, F), Age, Blood group (8 groups), Glucose and Blood pressure. One-hot encoding gives each category its own 0/1 column: Gender becomes 2 columns and Blood group 8, so 5 features become 13 columns. Target encoding replaces each category with a single number learned from the target (such as the diabetes rate for that blood group), keeping one column per feature.

One-hot is simple but multiplies the columns, and kNN gets worse as columns multiply (see the next concept). For categories with many values, target encoding keeps the data compact — as long as it is learned on training data only.

As the number of columns grows, the distances between points bunch together: the nearest point and the farthest point end up almost the same distance away. In the lecture's picture, two points far apart in 2 columns look nearly as close as any other pair once there are 1,000 columns.

kNN depends entirely on ranking points by distance. When all distances are nearly equal, "nearest" means almost nothing and predictions become close to random — which is why one-hot encoding a lot of categories can quietly ruin a kNN model.

Euclidean (L2) is the straight-line distance: √(Σ(aⱼ − bⱼ)²). Manhattan (L1) is the distance walking along the grid: Σ|aⱼ − bⱼ| — for A = (1, 1, 3) and B = (1, 3, 5) it is 0 + 2 + 2 = 4. Minkowski generalises both: (Σ|aⱼ − bⱼ|ᵖ)^(1/p), with p = 1 giving Manhattan and p = 2 Euclidean. Cosine similarity, a·b ÷ (‖a‖‖b‖), compares directions and ranges from −1 (opposite) to 1 (same direction).

The metric decides who counts as a neighbour, so it is a hyperparameter like k. Use Euclidean for a few dense numeric columns, Manhattan for grid-like or city-block data, and cosine for high-dimensional sparse data such as text, where it ignores the many columns that are zero in both rows.

Instead of comparing a query with every stored point, Locality Sensitive Hashing (LSH) first puts points into buckets so that similar points tend to land in the same bucket. A simple version: pick a few random directions and record, for each point, which side of each direction it falls on — e.g. [0, 1, 0]. Points with the same code share a bucket. At query time, compute the query's code and run kNN only on that bucket.

It turns an impossible search over billions of items into a quick search over a few thousand. This family of approximate nearest-neighbour methods is what makes image search, product recommendations and semantic search fast (Google's ScaNN, Facebook's FAISS).

When a row is missing a value, you can fill it with the column's mean or median — or with kNN: find the k rows most similar to it on the columns it *does* have, and use the average of their values for the missing one.

A store's missing Frozen count is better guessed from stores with similar Fresh, Milk and Grocery counts than from the average of all stores. kNN imputation keeps the relationships between columns that a plain mean ignores.