K-Nearest Neighbors: The Simplest ML Algorithm That Actually Works

Imagine you've just moved to a new locality and want to know whether the flat you're eyeing, 8.4 km from the nearest metro station at ₹4,600 per square foot, is fairly priced or overpriced. You don't have a formula for "fair price." So you do what any sensible person does: you find the listings you actually know something about — a handful of flats whose prices you trust because you've seen them close — and you check which ones this new flat most resembles. If most of the similar ones turned out to be fairly priced, you'd guess this one is too. If most turned out to be overpriced, you'd be suspicious.

That instinct — find the most similar known examples, let them vote — is the entire idea behind K-Nearest Neighbors (KNN). It has no equations to fit, no gradient to descend, no weeks of training. It is, quite literally, "ask your neighbors." And yet it is a real, widely used machine learning algorithm, taught as one of the first classification methods in every serious ML course, because it forces you to confront a question every other algorithm also has to answer, just less visibly: what does "similar" even mean, mathematically? Get that wrong, and KNN gives you confidently wrong answers. This chapter is about building KNN correctly, from the ground up, and about the one mistake that silently breaks it for almost everyone the first time.

The Algorithm, in Plain Words

KNN classifies a new, unlabeled data point using three steps:

1. Measure the distance from the new point to every point in your labeled training data.
2. Pick the K training points with the smallest distance — the "K nearest neighbors."
3. Let those K points vote on the class. The majority label becomes the prediction.

That's the whole algorithm. There's no step where the model "learns" a set of weights or coefficients. It just remembers the training data and does all its work at prediction time. We'll come back to why that single fact has real consequences later in this chapter.

Everything hinges on step 1: distance. To measure "how similar" a new flat is to a training flat, we need to turn two flats into two points in space and compute the gap between them. That's where coordinate geometry — real math you already have — comes in.

Distance: The Only Formula KNN Needs

You already know the distance formula from your Class 10 coordinate geometry chapter: for two points P₁ = (x₁, y₁) and P₂ = (x₂, y₂) in a plane,

distance(P1, P2) = sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

This comes directly from the Pythagorean theorem: (x₁ − x₂) is the horizontal leg of a right triangle, (y₁ − y₂) is the vertical leg, and the distance is the hypotenuse. KNN uses exactly this formula, just extended to as many features (dimensions) as your data has. If a data point has d features instead of 2, the same idea generalizes to:

distance(P1, P2) = sqrt( sum over i=1..d of (P1_i - P2_i)^2 )

This is called Euclidean distance, and it's the default choice for KNN. (A related option, Manhattan distance, sums the absolute differences instead of squaring them — |x₁ − x₂| + |y₁ − y₂| — and is sometimes preferred when features represent grid-like movement, like city blocks, or when you want distance to be less sensitive to one huge outlier difference. Both are special cases of a more general family called Minkowski distance, which you'll meet if you go deeper into ML, but Euclidean is what we'll use throughout this chapter.)

Notice something important about this formula: it treats every feature identically. It has no idea that x might be "kilometres" and y might be "rupees." It just subtracts, squares, and adds. Keep that in mind — it's about to matter a lot.

A Full Worked Example: Classifying a Flat

Here is our labeled training data — six flats an analyst has already classified as Fairly Priced or Overpriced, based on real assessments we're not re-deriving from the two features below. That's the whole point of supervised learning: the label is external ground truth we're trying to predict, not something we back out of the features ourselves.

New listing to classify: Q = (8.4 km, ₹4,600). Let's use K = 3 and compute every distance by hand, applying the formula exactly as derived above.

d(Q,P1) = sqrt((8.4-1)^2   + (4600-4200)^2) = sqrt(54.76   + 160000)   = 400.07
d(Q,P2) = sqrt((8.4-2)^2   + (4600-4500)^2) = sqrt(40.96   + 10000)    = 100.20
d(Q,P3) = sqrt((8.4-1.5)^2 + (4600-4100)^2) = sqrt(47.61   + 250000)   = 500.05
d(Q,P4) = sqrt((8.4-8)^2   + (4600-9200)^2) = sqrt(0.16    + 21160000) = 4600.00
d(Q,P5) = sqrt((8.4-9)^2   + (4600-9500)^2) = sqrt(0.36    + 24010000) = 4900.00
d(Q,P6) = sqrt((8.4-7.5)^2 + (4600-8900)^2) = sqrt(0.81    + 18490000) = 4300.00

Sorted from nearest to farthest: P2 (100.20), P1 (400.07), P3 (500.05), P6 (4300.00), P4 (4600.00), P5 (4900.00). The three nearest neighbors are P2, P1, and P3 — all three labeled Fairly Priced. Unanimous vote: KNN predicts Fairly Priced, 3–0.

Before you accept that answer, look closely at the ranking. P2 < P1 < P3 < P6 < P4 < P5. Now compare that to simply ranking the six flats by how close their price alone is to ₹4,600: |4500−4600|=100, |4200−4600|=400, |4100−4600|=500, |8900−4600|=4300, |9200−4600|=4600, |9500−4600|=4900 — the exact same order: 100, 400, 500, 4300, 4600, 4900. The distance-to-metro feature had no effect whatsoever on the ranking. A flat 8.4 km from the metro was ranked as if it were essentially identical to a flat 1 km from the metro, purely because their prices happened to be close.

Misconception 1: Euclidean Distance Doesn't Know What a "Kilometre" Is

This is the single most common way KNN quietly breaks for beginners: Euclidean distance treats the numeric size of a feature as if it were the same thing as its importance. Here, distance-to-metro ranges from 1 to 9 (a span of 8), while price ranges from 4,100 to 9,500 (a span of 5,400). When you square differences in both, the price term is always going to be enormous compared to the distance term — roughly 5,400 ÷ 8 ≈ 675 times larger in scale. So no matter what the distance feature says, the formula's output is almost entirely decided by price. It isn't that price is more "important" in any real sense — it's that price happens to be measured in bigger numbers.

This is exactly the trap: an algorithm that looks like it's using two features is, numerically, using barely more than one. The fix is not a new algorithm — it's making the two features comparable before you ever compute a distance.

The Fix: Min-Max Normalization

To put every feature on equal footing, rescale each one to the same range, typically [0, 1], using the minimum and maximum observed in the training data:

x' = (x - min(x)) / (max(x) - min(x))

Check that this does what you want: when x equals the minimum, x' = 0. When x equals the maximum, x' = 1. Everything else lands proportionally in between. Both features now live on the exact same [0, 1] scale, so a difference of 0.3 in one feature carries the same weight as a difference of 0.3 in the other — which is the whole point.

Apply it to our data. For distance-to-metro: min = 1, max = 9, so the range is 8. For price: min = 4,100, max = 9,500, so the range is 5,400.

            distance'              price'
P1 (1,4200):    (1-1)/8=0.000    (4200-4100)/5400=0.0185
P2 (2,4500):    (2-1)/8=0.125    (4500-4100)/5400=0.0741
P3 (1.5,4100):  (1.5-1)/8=0.0625 (4100-4100)/5400=0.000
P4 (8,9200):    (8-1)/8=0.875    (9200-4100)/5400=0.9444
P5 (9,9500):    (9-1)/8=1.000    (9500-4100)/5400=1.000
P6 (7.5,8900):  (7.5-1)/8=0.8125 (8900-4100)/5400=0.8889
Q  (8.4,4600):  (8.4-1)/8=0.925  (4600-4100)/5400=0.0926

Now recompute Euclidean distance from Q using these normalized coordinates:

d(Q,P1) = sqrt((0.925-0.000)^2 + (0.0926-0.0185)^2) = sqrt(0.8556+0.0055) = 0.9279
d(Q,P2) = sqrt((0.925-0.125)^2 + (0.0926-0.0741)^2) = sqrt(0.6400+0.0003) = 0.8002
d(Q,P3) = sqrt((0.925-0.0625)^2+ (0.0926-0.000)^2)  = sqrt(0.7439+0.0086) = 0.8675
d(Q,P4) = sqrt((0.925-0.875)^2 + (0.0926-0.9444)^2) = sqrt(0.0025+0.7257) = 0.8533
d(Q,P5) = sqrt((0.925-1.000)^2 + (0.0926-1.000)^2)  = sqrt(0.0056+0.8234) = 0.9105
d(Q,P6) = sqrt((0.925-0.8125)^2+ (0.0926-0.8889)^2) = sqrt(0.0127+0.6341) = 0.8042

Sorted: P2 (0.8002), P6 (0.8042), P4 (0.8533), P3 (0.8675), P5 (0.9105), P1 (0.9279). The three nearest neighbors are now P2 (Fairly Priced), P6 (Overpriced), and P4 (Overpriced) — a 2–1 majority for Overpriced. The prediction has completely flipped from the raw-distance result, and P6, which raw distance ranked fourth out of six and left out of the neighborhood entirely, is now the second-closest point. Normalizing didn't just tweak the numbers — it let the distance-to-metro feature actually participate in the decision for the first time.

Which prediction should you trust — 3–0 Fairly Priced or 2–1 Overpriced? Neither is automatically "correct" in general; that depends entirely on whether price and distance-to-metro should matter equally for this problem, which is a modeling decision, not a math fact. But one thing is not a matter of opinion: the raw-distance result gave distance-to-metro effectively zero say in the outcome, and that was an accident of units, not a decision anyone made on purpose. Always normalize your features before running KNN — this is not a stylistic preference, it is a correctness requirement, in exactly the same way "use the same units on both sides of an equation" is a requirement in physics numericals.

One more note on the min–max formula above: an alternative to min–max scaling is z-score standardization, x' = (x − mean) / (standard deviation), which centers each feature at 0 with unit spread instead of squashing it into [0, 1]. Both solve the same scale-blindness problem; min–max is easier to reason about by hand (which is why we used it here), while z-scores are often preferred when a dataset has extreme outliers that would otherwise compress everything else into a tiny sliver of the [0, 1] range.

Choosing K: A Real Trade-off, Not an Arbitrary Setting

A classmate might argue: "Just use K = 1 — the model then gets every training point right, since each point's nearest neighbor is always itself, at distance 0. Zero training error means it's the best possible model." This reasoning has a real flaw, and it's worth naming precisely: zero error on data the model has already memorized tells you nothing about how it performs on data it hasn't seen. With K = 1, the predicted boundary between classes bends around every single training point individually — including mislabeled points, measurement noise, and one-off outliers. A single noisy training example can flip the prediction for every nearby query point. This is called overfitting: the model has learned the specific training data by heart rather than the underlying pattern.

Increasing K averages over more neighbors, which smooths the decision boundary and makes the prediction less sensitive to any single noisy point — but push K too high (say, K equal to the entire training set) and the model just predicts the single most common class everywhere, ignoring the query point's actual position entirely. This is underfitting. Good practice is to test several odd values of K (odd, so ties are less likely in binary classification) on data the model hasn't been trained on, and pick the one that performs best there — not the one that performs best on data it has already memorized.

Misconception 2: "Training" a KNN Model Doesn't Really Train Anything

Most ML algorithms you'll encounter later — linear regression, decision trees, neural networks — spend real computational effort during training to build a compact model: a set of weights, a set of if–then splits, something that captures a pattern in a form much smaller than the raw data. Prediction is then fast, because the model has already "boiled down" the training set. This is called eager learning.

KNN does none of this. "Training" a KNN classifier means storing the training data — that's it. All the actual work — every distance computation, every comparison — is deferred until you ask it to classify a new point. This is called lazy learning. It's the reason KNN feels so simple to understand: there's no hidden model to interpret, just the data itself and a distance rule.

The cost of laziness shows up at prediction time. To classify one new point among n training examples with d features, you must compute n distances, each taking O(d) work, giving O(nd) per prediction — and you pay this cost every single time you classify something, not once during training. For a training set of a few hundred rows, as in a textbook exercise, this is instant. For a production system searching millions of rows for every query, naive KNN is genuinely too slow, which is why real systems use spatial index structures like KD-trees or Ball trees to avoid comparing against every single point. You don't need to implement these to understand KNN, but it's worth knowing they exist precisely because "compare against everyone, every time" doesn't scale — a question you'll meet again in far more depth if you study computer science at the undergraduate level.

What the Decision Boundary Actually Looks Like

Here's a question worth sitting with: when KNN uses K = 1 and only two classes, what shape is the boundary that separates "classify as A" from "classify as B"?

Let's derive it directly, using nothing but the distance formula and algebra you already have. Take two training points from different classes: A = (1, 1) labeled Class A, and B = (5, 3) labeled Class B. A new point P = (x, y) gets classified as whichever of A or B it's closer to. The boundary between the two regions is exactly the set of points P where the two distances are equal — right at the tipping point between "closer to A" and "closer to B."

distance(P,A) = distance(P,B)
(x-1)^2 + (y-1)^2 = (x-5)^2 + (y-3)^2

Squaring both sides was already implicit in the distance formula, so we can drop the square roots entirely and expand directly:

x^2 - 2x + 1 + y^2 - 2y + 1  =  x^2 - 10x + 25 + y^2 - 6y + 9
       -2x - 2y + 2          =        -10x - 6y + 34
              8x + 4y - 32   =  0
                  2x + y - 8 =  0        i.e.  y = 8 - 2x

Every x² and y² term cancelled — that's not a coincidence, it happens whenever you set two squared-distance expressions equal, and it's exactly why this boundary comes out linear (a straight line) rather than curved. You can sanity-check the result: the midpoint of A and B is ((1+5)/2, (1+3)/2) = (3, 2) — plug it in: 2(3) + 2 − 8 = 0. It satisfies the equation, as it should, since the midpoint is equally distant from both A and B by definition.

This idea — the set of all points equidistant from two fixed points — has a name: it's called a locus, and you'll formalize it properly next year in Class 11 Straight Lines, where you'll also prove that this line is always exactly perpendicular to the segment joining the two points (here, you can check AB has slope (3−1)/(5−1) = 0.5, and our line y = 8 − 2x has slope −2, and 0.5 × (−2) = −1, the condition for perpendicularity — a preview of a fact you'll prove properly later, not something you're expected to already know). For now, the point to take away is purely algebraic and fully within what you already have: with K = 1 and two classes, the decision boundary between any two neighboring training points is always a straight line, because squaring an equality of distances always cancels the quadratic terms. String enough of these lines together across all pairs of nearby points, and you get a jagged, tiled boundary — this construction is called a Voronoi diagram, and it's the geometric shape a K = 1 KNN model is implicitly drawing across the entire feature space.

From-Scratch Implementation

Here is the entire algorithm — distance, normalization, and voting — as plain Python, using the exact flat-pricing dataset from earlier:

import math

def min_max_normalize(data, query):
    n_features = len(data[0][0])
    mins = [min(row[0][i] for row in data) for i in range(n_features)]
    maxs = [max(row[0][i] for row in data) for i in range(n_features)]

    def scale(point):
        return tuple(
            (point[i] - mins[i]) / (maxs[i] - mins[i])
            for i in range(n_features)
        )

    scaled_data = [(scale(point), label) for point, label in data]
    scaled_query = scale(query)
    return scaled_data, scaled_query

def euclidean_distance(p1, p2):
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))

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

training_data = [
    ((1, 4200), "Fairly Priced"),
    ((2, 4500), "Fairly Priced"),
    ((1.5, 4100), "Fairly Priced"),
    ((8, 9200), "Overpriced"),
    ((9, 9500), "Overpriced"),
    ((7.5, 8900), "Overpriced"),
]

new_listing = (8.4, 4600)

raw_prediction, _ = knn_classify(training_data, new_listing, k=3)
print("Without scaling:", raw_prediction)

scaled_data, scaled_query = min_max_normalize(training_data, new_listing)
scaled_prediction, _ = knn_classify(scaled_data, scaled_query, k=3)
print("After min-max scaling:", scaled_prediction)

Trace it exactly as the interpreter would. min_max_normalize reads mins = [1, 4100] and maxs = [9, 9500] straight off the training data, matching what we computed by hand. knn_classify(training_data, new_listing, k=3) runs on the raw, unscaled tuples, computes the same six distances we worked out earlier (100.20, 400.07, 500.05, 4600.00, 4900.00, 4300.00 for P2, P1, P3, P4, P5, P6 respectively), sorts them, takes the top 3 (P2, P1, P3, all "Fairly Priced"), and the vote dictionary ends up as {"Fairly Priced": 3} — so max(votes, key=votes.get) returns "Fairly Priced". The second call scales first, reproducing the normalized coordinates from the worked example, and returns a vote dictionary of {"Fairly Priced": 1, "Overpriced": 2}, so the second line prints "Overpriced". Running this program prints:

Without scaling: Fairly Priced
After min-max scaling: Overpriced

Every number your code produces should match a number you could produce by hand — that discipline is what separates understanding an algorithm from just importing it from a library.

Where This Fits

K-Nearest Neighbors is one of the classification algorithms explicitly covered in CBSE's Artificial Intelligence curriculum's machine-learning unit, and it's a natural first algorithm to implement by hand precisely because every step — distance, sorting, majority vote — is something you can compute with pen and paper on a small dataset, which makes it a favourite for short-answer numericals in school exams. The distance-formula derivation of the decision boundary above is also a legitimate way to practice coordinate geometry for JEE Main and BITSAT-style questions, where "find the locus of points satisfying a distance condition" appears often once you reach that material formally next year. If you go on to study computer science at the undergraduate level and later sit postgraduate entrance exams like GATE, you'll meet K-Nearest Neighbors again — by then as one baseline classifier among many, but the reasoning about distance, scale, and the bias–variance trade-off in choosing K carries over unchanged.

Check Yourself

1. Explain, in your own words, why KNN is called a "lazy learner." What specific computation does it defer, and until when?

2. A dataset has two features: age in years (range 10–80) and annual income in rupees (range ₹50,000–₹50,00,000). A classmate runs KNN directly on this data without any preprocessing. Predict, without doing the arithmetic, which feature will dominate the distance calculation, and explain why using the idea of "span" from this chapter.

3. Given two labeled training points, A = (2, 2) belonging to Class Red and B = (6, 4) belonging to Class Blue, find the equation of the boundary separating "classify as Red" from "classify as Blue" under 1-NN, using only the distance formula and algebra, the way we derived it in this chapter. (This is your first hands-on encounter with the locus idea you'll formalize next year in Class 11 Straight Lines — you don't need that chapter to solve this.)

4. Why does K = 1 always achieve 100% accuracy on its own training data, and why does that number tell you nothing trustworthy about how the model will perform on a new flat listing it has never seen?

Answers — 1. KNN performs no real computation during "training"; it only stores the data. All distance calculations and the majority vote happen at prediction time, for every single query. 2. Income, because its span (50,00,000 − 50,000 = 49,50,000) is vastly larger than age's span (80 − 10 = 70); squared income differences will be roughly (49,50,000/70)² ≈ 5 × 10⁹ times larger in magnitude than squared age differences, so age will have almost no effect on the ranking unless both features are normalized first. 3. (x−2)² + (y−2)² = (x−6)² + (y−4)² expands to −4x−4y+8 = −12x−8y+52, giving 8x+4y−44=0, or 2x + y − 11 = 0 (check: midpoint (4,3) satisfies 2(4)+3−11=0 ✓). 4. With K=1, every training point's single nearest neighbor is itself, at distance 0, so it always "votes" for its own correct label — this measures memorization, not generalization; the true test is accuracy on points the model never stored, and a K=1 model is typically the most overfit, most noise-sensitive choice available, not the best one.

Summary

K-Nearest Neighbors classifies a new point by finding the K closest labeled points, using Euclidean distance derived directly from the Pythagorean theorem, and letting them vote by majority. It requires no training phase beyond storing data — making it a lazy learner, in contrast to eager learners like linear regression that build a compact model upfront, at the cost of doing O(nd) work at every single prediction. Its single most dangerous failure mode is scale-blindness: because Euclidean distance has no concept of units, a feature measured in large numbers (like rupees) will silently dominate a feature measured in small numbers (like kilometres) unless you normalize every feature to a common range first, using min–max scaling or z-score standardization. The choice of K trades off overfitting (K too small, boundary hugs every noisy point) against underfitting (K too large, boundary ignores the query's actual neighborhood); the standard practice is to test candidate values of K on unseen data, not on the training set. And geometrically, for K = 1 with two classes, the boundary between any two neighboring training points is always a straight line — the perpendicular bisector of the segment joining them — a direct algebraic consequence of setting two squared distances equal, and a genuine preview of the locus concept you'll formalize fully in Class 11.