K-Nearest Neighbors: Learning by Similarity

The Forecaster Who Never Wrote an Equation

Long before "machine learning" was a phrase anyone used, weather forecasters had a trick called the analog method. Suppose you want to know whether it will rain in Chennai tomorrow. You don't build a physics model of the atmosphere. Instead, you dig through decades of historical weather records and pull out the handful of past days whose temperature, humidity, wind direction, and pressure looked almost exactly like today's. Then you check what happened the day after each of those "twin" days. If eight out of ten similar days were followed by rain, you forecast rain. No equations for atmospheric dynamics, no simulation — just "find what's similar, and copy what usually followed."

That is, almost exactly, the algorithm this chapter is about. K-Nearest Neighbors (KNN) formalizes "find what's similar" into precise mathematics: a numeric notion of distance between data points, and a rule for turning nearby examples into a prediction. It was first described in a 1951 U.S. Air Force technical report by Evelyn Fix and Joseph Hodges, and in 1967 Thomas Cover and Peter Hart proved something remarkable about it: as the amount of training data grows without bound, the error rate of the simplest version of this method (1 neighbor) never exceeds twice the error rate of the theoretically best possible classifier for that problem — the so-called Bayes error rate. A method with no training phase, no parameters to fit, and no equations to derive turns out to have a hard mathematical guarantee. That combination of simplicity and rigor is why KNN is still taught first among classification algorithms, and why it still appears, embedded inside more complex systems, in real forecasting and recommendation pipelines today.

Formalizing "Similar": Distance

To turn "similar" into arithmetic, every example needs to become a point in space. A fruit described by (weight in grams, sweetness score out of 10) is a point in a 2-dimensional space. A student described by (attendance %, average quiz score, hours studied per week) is a point in a 3-dimensional space. A photograph reduced to pixel brightness values might be a point in a space with tens of thousands of dimensions. In every case, "how similar are two examples" becomes "how far apart are their two points" — and distance is something we can compute exactly.

The most common choice is the Euclidean distance — the same straight-line distance formula from Class 10 coordinate geometry, generalized beyond two dimensions. For two points x = (x₁, x₂, …, x_d) and y = (y₁, y₂, …, y_d) in d dimensions:

distance(x, y) = sqrt( (x1-y1)^2 + (x2-y2)^2 + ... + (xd-yd)^2 )

This is one member of a family called Minkowski distances, parameterized by a power p:

d_p(x, y) = ( |x1-y1|^p + |x2-y2|^p + ... + |xd-yd|^p )^(1/p)

Setting p = 2 gives Euclidean distance. Setting p = 1 gives Manhattan distance (sum of absolute differences — named for how you'd travel city blocks on a grid, since you can't cut diagonally through buildings). Manhattan distance is often preferred when features are counts or when the data is high-dimensional and sparse, because it doesn't let one large squared difference dominate the sum the way Euclidean distance does. As p grows very large, the Minkowski distance converges to the single largest coordinate difference — called Chebyshev distance. For most Grade 10-level problems, Euclidean distance is the right default, and it's the one this chapter will use throughout.

The Algorithm, Step by Step

Given a labeled dataset and a new, unlabeled query point, KNN predicts a label in four steps:

1. Compute the distance from the query point to every point in the training data.
2. Sort the training points by distance, ascending.
3. Take the k closest points — the "k nearest neighbors."
4. For classification, output the class that appears most often among those k neighbors (majority vote). For regression, output the average of their values instead.

Notice what's missing: there is no training step that builds a model, fits weights, or learns parameters. KNN simply memorizes the entire dataset and does all its "thinking" at prediction time. This is why it's called a lazy learner (or instance-based learner) — in contrast to an eager learner like a decision tree or linear regression, which does the hard work upfront during training and then predicts quickly using the compact model it built. KNN is also non-parametric: it doesn't assume the data follows any particular mathematical shape (like a straight line or a Gaussian curve) — the data itself is the model.

A Worked Example: Classifying an Unknown Fruit

Suppose a vendor's dataset records six fruits by (weight in grams, sweetness score from 1–10) and their label:

Point   Weight  Sweetness  Class
A1      150     7          Apple
A2      170     6          Apple
A3      130     8          Apple
O1      200     4          Orange
O2      220     3          Orange
O3      190     5          Orange

A new fruit arrives: weight 160 g, sweetness 7. Is it an apple or an orange? Compute the Euclidean distance from the query (160, 7) to each stored point:

to A1 (150,7): sqrt((160-150)^2 + (7-7)^2)  = sqrt(100 + 0)   = 10.00
to A2 (170,6): sqrt((160-170)^2 + (7-6)^2)  = sqrt(100 + 1)   = 10.05
to A3 (130,8): sqrt((160-130)^2 + (7-8)^2)  = sqrt(900 + 1)   = 30.02
to O3 (190,5): sqrt((160-190)^2 + (7-5)^2)  = sqrt(900 + 4)   = 30.07
to O1 (200,4): sqrt((160-200)^2 + (7-4)^2)  = sqrt(1600 + 9)  = 40.11
to O2 (220,3): sqrt((160-220)^2 + (7-3)^2)  = sqrt(3600 + 16) = 60.13

Sorted by distance: A1 (10.00), A2 (10.05), A3 (30.02), O3 (30.07), O1 (40.11), O2 (60.13). With k = 3, the three nearest neighbors are A1, A2, A3 — all Apples. The vote is unanimous, so the new fruit is classified as Apple. Notice how close A3 (30.02) and O3 (30.07) are — a difference of just 0.05 units decided which class made it into the neighborhood. This is a preview of why the choice of k matters: near a genuine boundary between classes, small changes in distance or in k can flip the outcome.

Here is the same logic as working code. Trace it by hand against the table above and confirm it reproduces "Apple":

def euclidean_distance(a, b):
    return sum((a[i] - b[i]) ** 2 for i in range(len(a))) ** 0.5

data = [
    ((150, 7), 'Apple'),
    ((170, 6), 'Apple'),
    ((130, 8), 'Apple'),
    ((200, 4), 'Orange'),
    ((220, 3), 'Orange'),
    ((190, 5), 'Orange'),
]

def knn_classify(query, data, k):
    distances = [(euclidean_distance(query, pt), label) for pt, label in data]
    distances.sort(key=lambda item: item[0])
    nearest = distances[:k]
    votes = {}
    for _, label in nearest:
        votes[label] = votes.get(label, 0) + 1
    return max(votes, key=votes.get)

print(knn_classify((160, 7), data, 3))   # Apple

Tracing it: distances fills with six (distance, label) pairs matching the table above. After sorting, nearest = distances[:3] is [(10.00,'Apple'), (10.05,'Apple'), (30.02,'Apple')]. The vote count becomes {'Apple': 3}, so max(votes, key=votes.get) returns 'Apple' — matching the hand computation exactly.

Misconception 1: "Raw numbers are already comparable"

A very common mistake is to feed features with wildly different scales into a distance formula and assume it still measures "similarity" fairly. It doesn't. Suppose we classify job candidates as a good fit using two features: years of experience (typically 0–20) and expected salary in rupees (typically ₹3,00,000–₹12,00,000). Consider a query candidate with 5 years of experience and an expected salary of ₹6,00,000, compared against two stored candidates who both expect ₹6,05,000 but differ enormously in experience:

Candidate T: experience = 0  years, salary = Rs 6,05,000
Candidate U: experience = 20 years, salary = Rs 6,05,000
Query:                    experience = 5  years, salary = Rs 6,00,000

distance(query, T) = sqrt((5-0)^2  + (600000-605000)^2)
                    = sqrt(25 + 25,000,000) = sqrt(25,000,025) ~ 5000.0025

distance(query, U) = sqrt((5-20)^2 + (600000-605000)^2)
                    = sqrt(225 + 25,000,000) = sqrt(25,000,225) ~ 5000.0225

T and U differ by twenty full years of experience — a fresh graduate versus a veteran — yet their distances from the query differ by about 0.02 out of roughly 5000, a difference smaller than a rounding error. The salary term, measured in raw rupees, contributes a squared value in the tens of millions, while the experience term contributes at most a few hundred. Experience has effectively been erased from the decision. This is not a flaw in the fruit example above (weight and sweetness happened to have comparable ranges) — it is a structural flaw that appears the moment feature ranges differ by orders of magnitude, and it silently produces wrong nearest-neighbor sets without any error message.

The fix is feature scaling before computing distances — most simply, min-max scaling each feature to the range [0, 1]:

scaled_value = (value - min_in_column) / (max_in_column - min_in_column)

Applying this with experience range [0, 20] and salary range [₹3,00,000, ₹12,00,000] (span ₹9,00,000):

scaled T: experience = 0/20 = 0.000,  salary = (605000-300000)/900000 = 0.339
scaled U: experience = 20/20 = 1.000, salary = (605000-300000)/900000 = 0.339
scaled query: experience = 5/20 = 0.250, salary = (600000-300000)/900000 = 0.333

distance(query, T) = sqrt((0.250-0.000)^2 + (0.333-0.339)^2) = sqrt(0.0625 + 0.00003) ~ 0.250
distance(query, U) = sqrt((0.250-1.000)^2 + (0.333-0.339)^2) = sqrt(0.5625 + 0.00003) ~ 0.750

After scaling, T (0.250) is three times closer than U (0.750) — experience now actually influences the outcome, correctly reflecting that a candidate with 0 years is much closer to a 5-year query than one with 20 years. The lesson generalizes: always scale features to comparable ranges before running KNN — either min-max scaling as above, or standardization (subtracting the mean and dividing by the standard deviation), unless every feature already shares the same natural units and range.

Misconception 2: "Smaller k is always more accurate"

A second common mistake is choosing k = 1, reasoning that the single closest point must give the "most accurate" answer. In fact k = 1 usually makes predictions worse on new data, because it makes the decision boundary follow every quirk of the training set, including mislabeled points and noise. Picture one stray Orange sitting deep inside a cluster of Apples due to a measurement error — with k = 1, every query point that happens to land near that single stray point gets misclassified as Orange, even though the surrounding neighborhood is overwhelmingly Apple. With k = 7, that one stray point is outvoted by its six correctly-labeled neighbors, and the misclassification disappears.

This is the classic bias-variance trade-off applied to KNN:

• Small k (e.g., k = 1): low bias, high variance. The model reacts to every local fluctuation, including noise — it can overfit.
• Large k (e.g., k = n, the whole dataset): high bias, low variance. The model always predicts the overall majority class regardless of the query — it underfits, ignoring local structure entirely.

The right k lies between these extremes and is normally chosen using cross-validation: train (i.e., store data) on part of the dataset, test different k values on a held-out portion, and pick the k that minimizes validation error. Two practical rules of thumb are worth knowing: for binary classification, use an odd k to avoid tie votes, and a commonly cited starting point is k close to the square root of the number of training examples, refined afterward by cross-validation.

Weighted Voting

Plain majority voting treats a neighbor at distance 10 exactly the same as one at distance 60, as long as both are inside the k nearest. Distance-weighted KNN fixes this by giving each neighbor a vote weight of 1/distance (or 1/distance²), so closer neighbors count more. Extending the fruit example to k = 5, the five nearest are A1 (10.00), A2 (10.05), A3 (30.02), O3 (30.07), O1 (40.11) — a plain vote gives Apple 3 votes to Orange's 2, a win but not an overwhelming one. Weighted by 1/distance:

Apple weight  = 1/10.00 + 1/10.05 + 1/30.02 = 0.1000 + 0.0995 + 0.0333 = 0.2328
Orange weight = 1/30.07 + 1/40.11              = 0.0333 + 0.0249 = 0.0582

The weighted score (0.2328 vs 0.0582) shows Apple winning far more decisively than the raw 3-vs-2 count suggests — because the two closest points of all are both Apple, and the Orange votes come from comparatively distant points. Weighting is especially useful when k is set a little larger than necessary as a safety margin: it lets the far-away neighbors participate without letting them override the genuinely close ones.

Why KNN Struggles as Features Multiply: The Curse of Dimensionality

KNN's entire premise is that "nearby points behave similarly." That premise quietly assumes it's possible to find points that are actually nearby. This assumption breaks down as the number of features (dimensions) grows — a phenomenon called the curse of dimensionality, and it can be derived exactly rather than just asserted.

Model the training data as spread uniformly inside a d-dimensional unit hypercube — every feature rescaled to lie in [0, 1]. To find a local neighborhood, build a smaller cube of side length s centered at the query point. Because the data is spread uniformly, the fraction of all points captured inside that smaller cube equals its volume relative to the whole cube:

fraction captured = volume of small cube / volume of whole cube = s^d / 1^d = s^d

To capture a target fraction p of the data as "neighbors," set s^d = p and solve for the required side length:

s = p^(1/d)

Now compute what "local" actually means as d grows, fixing the target at p = 0.20 (a neighborhood covering 20% of the data):

d = 1:  s = 0.20^(1/1)  = 0.2000   (20% of the axis range — genuinely local)
d = 2:  s = 0.20^(1/2)  = 0.4472   (45% of each axis)
d = 4:  s = 0.20^(1/4)  = 0.6687   (about 67% of each axis)
d = 10: s = 0.20^(1/10) = 0.8513   (about 85% of each axis)
d = 20: s = 0.20^(1/20) = 0.9227   (about 92% of each axis)

At d = 20, capturing even one-fifth of the dataset as "nearby" requires a neighborhood spanning 92% of the range along every single feature. That is not a neighborhood in any meaningful sense — it is almost the entire dataset. The points KNN calls "nearest neighbors" are barely any closer to the query than a randomly chosen point would be, because in high dimensions, distances between random points become increasingly similar to one another (a related, provable fact about high-dimensional geometry). This is why KNN, used naively, tends to perform worse as more features are added, even though more features intuitively sound like "more information." The practical fix is dimensionality reduction (dropping or combining features, e.g., using techniques like PCA) before applying KNN to high-dimensional data — a topic that builds directly on this chapter.

Computational Cost

Because KNN is a lazy learner, "training" costs essentially nothing — it's just storing the dataset, O(1) beyond the storage itself. All the work happens at prediction time: classifying one new query against n stored points, each with d features, naively costs O(n·d) — computing d subtractions and squarings per stored point, for all n points, then sorting. For large datasets, spatial index structures like kd-trees can reduce average prediction cost to roughly O(d log n) — but only in low dimensions. In high dimensions, kd-trees lose their advantage and degrade back toward O(n), which is yet another face of the curse of dimensionality: the tree can't build meaningful "nearby" partitions when nothing is truly nearby.

Where KNN Fits, and Exam Connections

KNN is usually the first classification algorithm taught precisely because it makes no hidden assumptions about the shape of the data (unlike linear regression, which assumes a straight-line relationship) and requires no complex training procedure (unlike a neural network). Its weaknesses are exactly what this chapter derived: it is sensitive to feature scaling, sensitive to the choice of k, computationally expensive at large n, and degrades in high dimensions. Algorithms like decision trees and Naive Bayes, covered elsewhere in this course, address some of these weaknesses directly.

For CBSE's Artificial Intelligence skill subject (Code 417) and board exams, KNN typically appears as a worked distance-and-vote numerical, exactly like the fruit example above — practice computing distances by hand until it's automatic. For IIT-JEE and BITSAT, the underlying mathematics is not new: the Euclidean distance formula is the Class 10 coordinate-geometry distance formula extended to more than two coordinates, and the p^(1/d) derivation above is a direct application of the laws of exponents and logarithms tested throughout Class 11–12 algebra. For GATE-foundation and Olympiad-style problems, the two results worth remembering precisely are Cover and Hart's asymptotic error bound (at most twice the Bayes error rate as n → ∞) and the O(n·d) versus O(d log n) prediction-cost trade-off — both are the kind of exact, provable claims that distinguish a rigorous answer from a hand-wavy one.

Active Recall

1. Q: In your own words, what does KNN do at "training" time, and what does it do at prediction time?
   A: At training time, KNN does nothing but store the labeled dataset — there is no model-fitting step, which is why it's called a lazy, instance-based learner. At prediction time, it computes the distance from the query point to every stored point, finds the k closest ones, and outputs their majority class (or their average, for regression).
2. Q: Using the fruit dataset from this chapter, what class would a fruit at (weight = 145, sweetness = 8) get with k = 1? Show the nearest point.
   A: Distance to A3 (130,8): sqrt(15² + 0²) = 15.00. Distance to A1 (150,7): sqrt(5² + 1²) = 5.10. A1 is actually closer than A3 here. So with k = 1 the nearest point is A1 (distance 5.10), and the prediction is Apple.
3. Q: Why must features be scaled before computing distances in KNN? Give the structural reason, not just "it's good practice."
   A: Euclidean distance sums squared differences across features. A feature with a much larger numeric range (e.g., salary in rupees, range in the hundreds of thousands) produces squared differences many orders of magnitude larger than a feature with a small range (e.g., years of experience, range 0–20). The large-range feature dominates the sum and the small-range feature is effectively ignored, regardless of how meaningful it actually is — as shown numerically in this chapter, a 20-year experience gap changed the total distance by about 0.02 out of 5000 before scaling.
4. Q: A dataset has one mislabeled point sitting inside an otherwise pure cluster of the opposite class. Would k = 1 or k = 9 be more robust to this error, and why?
   A: k = 9 is more robust. With k = 1, any query landing nearest to the single mislabeled point gets its (wrong) label directly, with no correction. With k = 9, that one bad point is outvoted by the eight correctly labeled neighbors around it, so the error is absorbed rather than propagated — this is the bias-variance trade-off: larger k trades some responsiveness to local detail for resistance to noise.
5. Q: Using the curse-of-dimensionality formula s = p^(1/d), compute the side length of the neighborhood needed to capture p = 20% of the data for (a) d = 4 features and (b) d = 20 features. What does the result imply about applying plain KNN to high-dimensional data?
   A: (a) For d = 4: s = 0.20^(1/4) ≈ 0.669 (about 67% of each axis's range). (b) For d = 20: s = 0.20^(1/20) ≈ 0.923 (about 92% of each axis's range). This means that as the number of features grows, capturing even a modest fraction of the data as "neighbors" requires spanning nearly the entire range of every feature — the neighborhood stops being local at all, so plain Euclidean-distance KNN becomes unreliable in high dimensions unless the number of features is first reduced.

Summary

K-Nearest Neighbors classifies a new point by finding the k most similar stored examples — measured by a distance formula, most commonly Euclidean distance, the same formula from coordinate geometry generalized to d dimensions — and taking their majority vote (or average, for regression). It has no training phase beyond storing data, which makes it a lazy, non-parametric learner with the surprising theoretical guarantee that its error rate is asymptotically bounded by twice the best possible error rate. Its two most common failure modes are also its two most instructive lessons: features must be scaled to comparable ranges before computing distance, or large-range features silently dominate the result; and the number of neighbors k must be tuned rather than minimized, since k = 1 overfits to noise while k too large washes out real local structure. Its cost grows with dataset size at prediction time, and its core "nearby means similar" assumption provably weakens as the number of features grows — captured exactly by the relationship s = p^(1/d), which shows a supposed neighborhood swelling to cover 92% of every axis by the time there are just twenty features. Every one of these properties reappears, in more disguised form, in the more advanced algorithms later in this course.

Think About It

Think about this: How would you explain k-nearest neighbors: learning by similarity to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.