How does the K-Nearest Neighbors algorithm work?
Updated Feb 20, 2026
Short answer
KNN classifies a point by finding the K closest training examples and taking a majority vote among their labels; for regression it averages their values. It is a lazy learner — there is no training phase, the entire dataset is the model, and all the work happens at prediction time. That makes it trivial to implement and expensive to query, at O(n·d) per prediction.
Deep explanation
def knn_predict(X_train, y_train, x, k): distances = [(euclidean(x, xi), yi) for xi, yi in zip(X_train, y_train)] distances.sort(key=lambda t: t[0]) neighbours = [label for _, label in distances[:k]] return Counter(neighbours).most_common(1)[0][0]Feature scaling is not optional. Distance is dominated by whichever feature has the largest numeric range. With income in the tens of thousands and age in tens, income determines every neighbour and age is effectively ignored. Standardise or min-max scale before computing distances — this is the single most common reason a KNN implementation performs poorly.
Choosing K trades bias against variance. K = 1 fits the training data perfectly and is highly sensitive to noise — one mislabelled point creates a wrong region around itself. Large K smooths the decision boundary but blurs genuine local structure, and at K = n every prediction is the majority class. Choose by cross-validation, and use an odd K for binary classification so votes cannot tie.
Distance metric matters too. Euclidean is the default; Manhattan often behaves better in high dimensions; cosine similarity suits text and other sparse high-dimensional data where magnitude is uninformative.
The curse of dimensionality is KNN's fundamental weakness. As dimensions grow, distances between points concentrate — the ratio between the nearest and farthest neighbour approaches 1 — so "nearest" stops carrying meaning. Beyond roughly 10–20 informative dimensions, KNN degrades badly, and dimensionality reduction or a different algorithm becomes necessary.
Cost. Training is O(1) — just storing the data. Prediction is O(n·d) per query with a brute-force scan. KD-trees reduce this to about O(log n) in low dimensions but degenerate to linear beyond roughly 20 dimensions. Ball trees handle moderately higher dimensions, and approximate methods such as HNSW are what production vector search actually uses.
Class imbalance distorts voting: if 95% of training points are class A, the K nearest are likely class A regardless of the query. Distance weighting — where closer neighbours count more — helps, as does resampling.
Real-world example
Why scaling changes the answer entirely:
# unscaled: income (0–200,000) vs age (18–90)query = [50_000, 25]candidateA = [51_000, 60] # distance ≈ 1000.6 -> "nearest"candidateB = [70_000, 26] # distance ≈ 20000.0
# after standardisation, age carries equal weightquery = [-0.2, -1.1]candidateA = [-0.18, 1.4] # distance ≈ 2.5candidateB = [ 0.6, -1.0] # distance ≈ 0.8 -> "nearest" nowUnscaled, a 35-year age gap is invisible next to a £19,000 income gap, and candidate A wins. Scaled, age counts equally and candidate B wins instead. Same data, same algorithm, opposite prediction — decided entirely by preprocessing.
Common mistakes
- - Not scaling features, so the largest-range feature dominates the distance and the others are effectively ignored.
- - Choosing K = 1, which fits noise exactly and produces an unstable decision boundary.
- - Using an even K for binary classification, allowing tied votes.
- - Applying KNN to high-dimensional data without reduction, where distance concentration makes 'nearest' meaningless.
- - Ignoring class imbalance, so the majority class wins votes regardless of the query point.
- - Fitting the scaler on the full dataset before splitting, leaking test-set statistics into training.
Follow-up questions
- Why is KNN called a lazy learner?
- How does the curse of dimensionality affect KNN specifically?
- How do KD-trees speed up neighbour search, and when do they stop helping?
- What is distance-weighted KNN?