A complete, hand-worked walkthrough of a single KNN prediction — computing every distance, sorting them, and taking the majority vote — so the algorithm is fully transparent, not just a library call.
The Algorithm, As Explicit Steps
| Step | What Happens |
|---|---|
| 1 | Store the entire labeled training dataset (no other "training" happens) |
| 2 | For a new query point, compute its distance to every training point |
| 3 | Sort all training points by distance, ascending |
| 4 | Take the \(k\) closest points |
| 5 | Classification: majority vote among their labels. Regression: average their target values |
Worked Example — Every Step by Hand
Training data (hours studied, practice tests) → passed (1) or failed (0):
| Point | (hours, tests) | Label |
|---|---|---|
| A | (1, 0) | 0 |
| B | (2, 0) | 0 |
| C | (2, 1) | 0 |
| D | (3, 1) | 0 |
| E | (4, 1) | 1 |
| F | (5, 2) | 1 |
| G | (6, 2) | 1 |
| H | (7, 3) | 1 |
Query point: (4, 2) — 4 hours studied, 2 practice tests. Using \(d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\):
| Point | Distance Calculation | Distance |
|---|---|---|
| E (4,1) | \(\sqrt{(4-4)^2+(2-1)^2}=\sqrt{1}\) | 1.000 |
| F (5,2) | \(\sqrt{(4-5)^2+(2-2)^2}=\sqrt{1}\) | 1.000 |
| D (3,1) | \(\sqrt{(4-3)^2+(2-1)^2}=\sqrt{2}\) | 1.414 |
| G (6,2) | \(\sqrt{(4-6)^2+(2-2)^2}=\sqrt{4}\) | 2.000 |
| C (2,1) | \(\sqrt{(4-2)^2+(2-1)^2}=\sqrt{5}\) | 2.236 |
| B (2,0) | \(\sqrt{(4-2)^2+(2-0)^2}=\sqrt{8}\) | 2.828 |
| H (7,3) | \(\sqrt{(4-7)^2+(2-3)^2}=\sqrt{10}\) | 3.162 |
| A (1,0) | \(\sqrt{(4-1)^2+(2-0)^2}=\sqrt{13}\) | 3.606 |
Sorted ascending, the 3 nearest neighbors (\(k=3\)) are: E (d=1.0, label 1), F (d=1.0, label 1), D (d=1.414, label 0). Vote: two 1s, one 0 → predicted label = 1 (pass).
Python Implementation — Matching the Hand Calculation
import numpy as np
from collections import Counter
X_train = np.array([[1,0],[2,0],[2,1],[3,1],[4,1],[5,2],[6,2],[7,3]])
y_train = np.array([0,0,0,0,1,1,1,1])
query = np.array([4, 2])
k = 3
distances = np.sqrt(np.sum((X_train - query) ** 2, axis=1))
nearest_indices = np.argsort(distances)[:k]
nearest_labels = y_train[nearest_indices]
print(distances) # matches the table above
print(nearest_labels) # [1 1 0]
print(Counter(nearest_labels).most_common(1)[0][0]) # 1 -- majority vote
# scikit-learn -- same result
from sklearn.neighbors import KNeighborsClassifier
model = KNeighborsClassifier(n_neighbors=3).fit(X_train, y_train)
print(model.predict([[4, 2]])) # [1]Handling Ties
With an even \(k\), a vote can tie exactly (e.g. 2 vs 2 with k=4) — scikit-learn breaks ties by falling back to whichever class appears first among the neighbors sorted by distance. This is exactly why odd values of \(k\) are preferred for binary classification: see Choosing k in KNN.
Practical Use Cases
- Any scenario where "find similar past cases and go with what happened then" is a natural, defensible prediction strategy
Common Mistakes
- Computing distance using unscaled features — in this example, "hours" (1-7) and "tests" (0-3) happen to be on comparable scales, but real features rarely are; always scale first in practice.
- Forgetting that KNN recomputes distances to every training point for every single prediction — this is the direct cause of its slow prediction-time cost on large datasets.
Interview Relevance
Q: "Walk me through exactly what KNN does for a single prediction." Compute distance to every training point, sort by distance, take the k closest, then vote (classification) or average (regression) — the worked example above is exactly this answer, concretely.
Practice Question
Using the table above, what would the prediction be for k=5 instead of k=3? (Hint: add the next two nearest points to the vote.)
