K-Nearest Neighbors: Your Neighborhood Decides

The New Kid in the Colony

Suppose your family just shifted to a new housing society in Pune, and you have no idea whether the area is "quiet" or "noisy" after 10 pm. You have not lived there long enough to judge for yourself, so what do you do? You do not survey all 400 flats in the society. You walk up to the five flats closest to yours, ask each one, and go with whatever most of them say. If four out of five neighbours say "quiet," you conclude your area is quiet too, even though you personally have zero experience of a Saturday night there.

That instinct — trust the people physically closest to you to tell you what a new, unknown situation is like — is almost exactly the idea behind a machine learning algorithm called K-Nearest Neighbors, or KNN. It is one of the simplest algorithms in all of machine learning, and also one of the most instructive, because it does not hide any of its reasoning behind complicated formulas. It classifies a new, unlabeled data point by looking at the labeled data points closest to it and letting them vote. This chapter builds that idea from arithmetic you already know — distance and the Pythagoras theorem — all the way up to a working algorithm you can trace by hand and in code.

From "Ask Your Neighbours" to a Number

Before KNN can "ask the neighbours," it needs a precise, numerical meaning for the word "closest." In your housing society example, "closest" meant physical distance — which flat is nearest to yours. In machine learning, our data points are usually not flats on a map; they are described by measurements, called features. But the same idea of distance still applies, as long as we can measure how different two data points' features are.

Start with the simplest possible case: one feature. Suppose you know only one number about each person — their height in centimetres — and you want to know how "close" two people are in terms of height. If Aditi is 150 cm tall and Rohan is 158 cm tall, the distance between them, along this one feature, is simply the difference: 158 minus 150, which is 8 cm. Small difference means the two points are close; large difference means they are far apart. This is the entire idea of "distance" in one dimension — just subtraction, then dropping the sign, since a distance of −8 does not make sense.

Two Features, One Distance: Bringing In Pythagoras

Real data almost never comes with just one feature. Suppose now you know two things about each person: height (cm) and weight (kg). Person A is 150 cm and 45 kg. Person B is 158 cm and 50 kg. How far apart are they now that "distance" has two directions to account for — a height-direction and a weight-direction?

Picture this on a graph, exactly the way you plot points in your Class 9 coordinate geometry chapter: height along the x-axis, weight along the y-axis. Person A is a point at (150, 45); Person B is a point at (158, 50). To go from A to B, you move 8 units along the height-direction (158 − 150 = 8) and 5 units along the weight-direction (50 − 45 = 5). These two movements are at right angles to each other, exactly like the two legs of a right triangle, and the straight-line distance between A and B is the hypotenuse of that triangle. You already know how to find a hypotenuse — the Pythagoras theorem:

distance = √(Δheight² + Δweight²)
         = √(8² + 5²)
         = √(64 + 25)
         = √89
         ≈ 9.43

This is called the Euclidean distance, and it is simply the Pythagoras theorem applied to as many features as you have. With two features you get a right triangle in a flat plane; with three features the same formula still works, just imagined in 3D space; with fifty features, you cannot draw it any more, but the arithmetic — square each difference, add them up, take the square root — is identical. This single formula is the entire engine that makes KNN work: it is how the algorithm decides who your "neighbours" are.

The Full Worked Example: Fit or Unfit?

Here is a small, complete dataset in the style CBSE's AI and Computer Science material commonly uses to introduce KNN: a school sports teacher has recorded the height and weight of six students, along with a fitness category she assigned after a simple stamina test. This is a teaching toy, not a real medical standard — real fitness assessment considers far more than two numbers — but it is perfect for learning the algorithm because you can check every calculation by hand.

Student   Height(cm)  Weight(kg)  Category
P1           163          64        Fit
P2           154          52        Fit
P3           165          72        Unfit
P4           151          72        Fit
P5           168          75        Unfit
P6           172          76        Unfit

New student Q:  160 cm, 60 kg,  Category = ?

A new student, Q, joins with height 160 cm and weight 60 kg. The teacher has no stamina-test result for Q yet, but she wants a quick estimate. KNN answers this by computing the Euclidean distance from Q to every one of the six known students, then letting the nearest ones vote. Let us do every single calculation:

P1 (163, 64): Δh = 163-160 = 3,  Δw = 64-60 = 4
              distance = √(3² + 4²) = √(9+16)  = √25  = 5

P2 (154, 52): Δh = 154-160 = -6, Δw = 52-60 = -8
              distance = √(6² + 8²) = √(36+64) = √100 = 10

P3 (165, 72): Δh = 165-160 = 5,  Δw = 72-60 = 12
              distance = √(5² + 12²)= √(25+144)= √169 = 13

P4 (151, 72): Δh = 151-160 = -9, Δw = 72-60 = 12
              distance = √(9² + 12²)= √(81+144)= √225 = 15

P5 (168, 75): Δh = 168-160 = 8,  Δw = 75-60 = 15
              distance = √(8² + 15²)= √(64+225)= √289 = 17

P6 (172, 76): Δh = 172-160 = 12, Δw = 76-60 = 16
              distance = √(12²+ 16²)= √(144+256)=√400 = 20

Notice these distances came out as clean whole numbers — 5, 10, 13, 15, 17, 20 — because each pair of differences happens to form a Pythagorean triple (3-4-5, 6-8-10, 5-12-13, and so on). Real data will rarely be this tidy; you will usually get decimals. That is fine — the algorithm does not care whether the answer is neat, only that you compare distances consistently.

Now sort the students by distance from Q, nearest first:

Rank  Student  Distance  Category
 1      P1         5      Fit
 2      P2        10      Fit
 3      P3        13      Unfit
 4      P4        15      Fit
 5      P5        17      Unfit
 6      P6        20      Unfit

Seeing the Neighbourhood

The diagram below plots all six students and the new student Q on a height–weight grid, exactly the coordinate plane we used for the Pythagoras calculation above. The three nearest neighbours to Q (when K = 3) are ringed, with a dashed line showing the exact distance computed by hand in the previous section.

With K = 3, the three ringed neighbours are P1 (Fit, distance 5), P2 (Fit, distance 10), and P3 (Unfit, distance 13). Two votes for Fit, one for Unfit — so KNN predicts Q is Fit. Notice this is a majority vote among only the K nearest points; P4, P5, and P6 are further away and are not even consulted, exactly like you would not bother asking the flat at the far end of the society about Saturday-night noise near your own door.

Choosing K: The Most Important Decision in KNN

K is simply "how many neighbours get to vote," and the value you pick can change the answer. Using the same sorted list from before, watch what happens as K grows:

K=1 -> nearest 1: P1(Fit)                                  -> 1 Fit, 0 Unfit -> Fit
K=3 -> nearest 3: P1(Fit), P2(Fit), P3(Unfit)               -> 2 Fit, 1 Unfit -> Fit
K=5 -> nearest 5: P1(Fit), P2(Fit), P3(Unfit), P4(Fit), P5(Unfit)
                                                              -> 3 Fit, 2 Unfit -> Fit
K=6 -> all 6:     P1,P2,P4 = Fit   P3,P5,P6 = Unfit          -> 3 Fit, 3 Unfit -> TIE

Two lessons sit inside this small table. First, K = 1 is extremely sensitive: the prediction rests entirely on a single neighbour, so if that one point happened to be a mislabeled or unusual case (an outlier), your prediction is wrong with no other votes to correct it. A very small K makes KNN chase noise in the data — this is called overfitting, the same danger you will meet again with other algorithms. Second, K = 6, which happens to be every student in this tiny dataset, produces an exact tie. With a very large K, KNN starts to ignore the local neighbourhood altogether and drifts toward whatever category is most common in the entire dataset, regardless of where the new point actually sits — this is underfitting, the opposite failure. A good K is usually somewhere in between, found by experimenting on real data, not by a formula. And because ties are annoying to resolve, practitioners commonly choose an odd K for a two-category problem like this one, precisely to avoid deadlocks like the K = 6 case above.

Writing KNN in Code

The algorithm translates into code almost exactly the way we did it by hand: compute every distance, sort, take the closest K, count votes.

def euclidean_distance(p, q):
    return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

training_data = [
    (163, 64, "Fit"),
    (154, 52, "Fit"),
    (165, 72, "Unfit"),
    (151, 72, "Fit"),
    (168, 75, "Unfit"),
    (172, 76, "Unfit"),
]

def knn_predict(query, data, k):
    distances = []
    for height, weight, label in data:
        d = euclidean_distance((height, weight), query)
        distances.append((d, label))
    distances.sort(key=lambda item: item[0])
    nearest = distances[:k]

    votes = {}
    for d, label in nearest:
        votes[label] = votes.get(label, 0) + 1
    return max(votes, key=votes.get)

query = (160, 60)
print(knn_predict(query, training_data, 3))   # Fit
print(knn_predict(query, training_data, 6))   # Fit  (a tie, broken by insertion order)

Trace the K=3 call the way Python actually executes it: the distances list fills up as (5.0,"Fit"), (10.0,"Fit"), (13.0,"Unfit"), (15.0,"Fit"), (17.0,"Unfit"), (20.0,"Unfit"), in whatever order the loop visits the list — then sort rearranges it into exactly that ascending order since it already matches. nearest keeps the first three: 5.0/Fit, 10.0/Fit, 13.0/Unfit. The votes dictionary is built in that order too: Fit becomes 1, then 2, then Unfit becomes 1. max(votes, key=votes.get) returns "Fit," matching our hand calculation exactly.

The K=6 call is worth tracing too, because it exposes a real bug hiding in plain sight. All six students are counted: Fit gets votes from P1, P2, and P4 (three votes); Unfit gets votes from P3, P5, and P6 (three votes). The dictionary ends up as Fit:3, Unfit:3 — a genuine tie. But max does not know how to "tie" — it walks through the dictionary's keys in the order they were first inserted (Fit was inserted before Unfit, since P1 came first) and simply keeps whichever key it saw first among the equal maximums. So the code silently returns "Fit," not because Fit truly won, but because of insertion order — an implementation detail that has nothing to do with the actual data. This is exactly why real KNN tools either forbid even values of K for two-class problems or add an explicit tie-breaking rule (such as falling back to the single nearest neighbour). A correct implementation must decide on purpose how to break ties — never let it happen by accident the way this simple version does.

The Silent Trap: Why Units Matter

Here is a mistake that even careful students make on their first KNN dataset, and it will not throw an error — it will just quietly give you the wrong answer. Suppose two candidate neighbours, A and B, are compared to a query point, with height measured in centimetres and weight in kilograms:

Point A: height differs by 20 cm, weight differs by 1 kg
         distance = √(20² + 1²) = √(400+1) = √401 ≈ 20.02

Point B: height differs by 1 cm, weight differs by 15 kg
         distance = √(1² + 15²) = √(1+225) = √226 ≈ 15.03

By this measurement, B is the closer neighbour (15.03 versus 20.02). Now suppose someone re-enters the same data, but records weight in grams instead of kilograms — a completely harmless-seeming choice, since 1 kg is still 1 kg, just written as 1000 g:

Point A: height differs by 20 cm, weight differs by 1000 g
         distance = √(20² + 1000²) = √1000400 ≈ 1000.2

Point B: height differs by 1 cm, weight differs by 15000 g
         distance = √(1² + 15000²) = √225000001 ≈ 15000.00

Nothing about which point is actually "more similar" to the query changed — yet A is now overwhelmingly the closer neighbour, and B is over ten times further away. The Euclidean distance formula has no concept of "kilograms" or "centimetres"; it just squares raw numbers. Whichever feature happens to have the largest numeric range dominates the entire distance calculation and silently drowns out every other feature. This is the single most common real-world KNN bug: mixing a feature measured in thousands (like a salary in rupees) with a feature measured in single digits (like years of experience) produces a model that is effectively only looking at salary. The fix is called feature scaling — rescaling every feature (commonly to a 0–1 range, or to have the same spread around zero) before computing any distance, so that no feature wins purely by virtue of its units. You do not need the formula for this at Grade 9 level, but you must remember the principle: KNN is only as fair as the units you feed it.

What Kind of Learner Is KNN?

Most algorithms you will later meet — including ones covered elsewhere in this course — go through a distinct "training phase" where they study the data once and build a compact model (a set of rules, weights, or a formula), which is then reused instantly for every future prediction. KNN does something unusual: it has almost no training phase at all. "Training" a KNN model means nothing more than storing the entire dataset in memory. All of the real computation — every one of those distance calculations you traced above — happens at the moment a new point needs to be classified. Because of this, KNN is called a lazy learner (or an instance-based learner): it postpones all effort until the last possible moment, then does a burst of work per query.

This has a real, practical consequence. If your training dataset has one thousand students in it instead of six, classifying a single new student now requires computing one thousand distances, sorting all of them, and only then reading off the nearest K. Double the dataset, and you roughly double the work per prediction. This makes plain KNN slow on very large datasets compared to algorithms that invest time upfront during training so they can answer instantly afterward — a tradeoff worth remembering when you are asked, in an exam or in practice, to compare KNN against other classification algorithms.

Beyond Yes/No: KNN for Regression

Everything above classified Q into a category (Fit or Unfit) — this is called classification. KNN can just as easily handle regression, where the goal is to predict a number instead of a category. Imagine, instead of a Fit/Unfit label, each of the six students had a recorded 100-metre sprint time in seconds. To estimate Q's likely sprint time, KNN would still find the same three nearest neighbours (P1, P2, P3) — the distance calculation does not change at all — but instead of taking a majority vote, it would average their sprint times. Everything you have learned about choosing K, the danger of a K that is too small or too large, and the danger of unscaled features applies identically whether the output is a category or a number; only the final step, vote versus average, changes.

Common Misconceptions, Corrected

• "KNN builds a model like other ML algorithms do." It does not. There is no formula being fitted, no equation being learned. KNN simply memorizes the training data and defers all decision-making to the moment a query arrives — this is the lazy-learning property explained above.
• "A bigger K always gives a more accurate answer." False in both directions. Too small a K (like K=1) makes predictions swing wildly based on single outlier points. Too large a K makes the algorithm ignore local structure and drift toward the overall majority class in the whole dataset, which defeats the purpose of looking at "neighbours" at all.
• "Distance is just distance — units do not matter." As shown above, switching a feature from kilograms to grams can flip which point counts as "nearest," even though nothing about the real-world similarity changed. Features must be on comparable scales before distances are computed.
• "K is a fixed, calculable property of the dataset." K is a hyperparameter — a setting you choose, typically by testing several values and seeing which works best on data you already know the correct answer for, not something derived by a formula from the dataset alone.

Check Your Understanding

• A new point Q sits at (10, 10). Two labeled points exist: R at (13, 14) labeled "A," and S at (16, 10) labeled "B." Compute the Euclidean distance from Q to R and from Q to S by hand, and state which one KNN would pick as the single nearest neighbour (K=1).
• Using the six-student Fit/Unfit dataset from this chapter, a new student arrives at height 170 cm, weight 74 kg. Compute the distance from this new student to P5 (168, 75) and to P6 (172, 76), and say which is closer.
• Explain, in your own words, why KNN is called a "lazy" learner, and describe one real cost of that laziness when the training dataset is very large.
• A dataset has two features: "annual family income in rupees" (values in the lakhs, e.g. 600000) and "number of siblings" (values like 0, 1, 2, 3). Without any rescaling, which feature will dominate the Euclidean distance, and why? What would you do before running KNN on this data?
• For a dataset with exactly two possible categories, explain why choosing an even value of K is riskier than choosing an odd value, using the K=6 tie from this chapter as your example.

Summary

K-Nearest Neighbors classifies a new data point by finding the K closest points in a labeled dataset and letting them vote by majority (or, for regression, by averaging their values). "Closeness" is measured with Euclidean distance, which is nothing more than the Pythagoras theorem extended across as many features as your data has. The choice of K trades off two failure modes: too small overreacts to individual outliers, too large drowns out local structure and can even produce outright ties. Because all the real computation happens at prediction time rather than during a separate training phase, KNN is called a lazy or instance-based learner, and its cost grows with the size of the stored dataset. Finally, because the distance formula treats every feature's raw numbers equally regardless of what unit they are measured in, features must be placed on comparable scales before distances are computed — skip this step, and one feature can silently dominate every prediction the algorithm makes.