🎉 75% of content is free forever — Unlock Premium from $10/mo →
CW
💼 Servicesℹ️ About✉️ ContactView Pricing Plansfrom $10
Get started free →Sign in

K-Nearest Neighbors — Complete Guide

ML FoundationsClassification🟢 Free Lesson

Advertisement

Supervised Learning

Instance-Based Learning — Your Neighbors Tell the Story

KNN classifies new points by looking at the K closest training examples. It is simple, intuitive, and requires no training phase.

  • Lazy Learner — No training phase, all computation at prediction time
  • Distance Metrics — Euclidean, Manhattan, and cosine similarity
  • Curse of Dimensionality — Why KNN struggles with too many features

"Tell me who your neighbors are, and I'll tell you who you are."

Prerequisites

Before diving in, make sure you're comfortable with:

  • Basic Python — Loops, lists, NumPy arrays
  • Distance Metrics — Euclidean distance, vector operations
  • Basic Statistics — Mean, mode (majority vote)
  • Feature Scaling — Why it matters for distance-based methods

Learning Objectives

After completing this tutorial, you will be able to:

  1. Explain how KNN classifies new data points using nearest neighbors
  2. Implement KNN from scratch and with sklearn
  3. Compare Euclidean, Manhattan, and cosine distance metrics
  4. Understand the bias-variance tradeoff in choosing K
  5. Recognize the curse of dimensionality and its impact on KNN
  6. Apply weighted KNN and know when it helps

K-Nearest Neighbors — Complete Guide

KNN is the simplest ML algorithm — it classifies a point by looking at its K closest neighbors.

How KNN Works

KNN Classification: K=5 Neighbors VoteFeature x₁?x_qC₀C₀C₁C₀C₁Class 0 (3 votes)Class 1 (2 votes)Predicted: Class 0KNN AlgorithmStep 1: Store all training data{(x⁽ⁱ⁾, y⁽ⁱ⁾)} for i = 1..NStep 2: For query point x_q:a. Compute d(x_q, x⁽ⁱ⁾) for all ib. Sort by distancec. Select K nearest: N_K(x_q)Step 3: Majority voteŷ = argmax_c Σ 𝟙[y⁽ⁱ⁾=c]Complexity:O(Nd) per prediction — no training!

Distance Metrics

Distance Metrics ComparisonManhattan (L1)d = |80−220| + |180−85| = 240Grid-aligned paths onlyEuclidean (L2)d = √(140² + 95²) = 169.3Straight-line distanceCosine Similarityθcos(θ) = x·y / (‖x‖‖y‖)Direction only, not magnitude

Choosing K

Effect of K on Decision BoundaryK=1 (Overfitting)Complex, jagged boundaryK=5 (Good Fit)Smooth, reasonable boundaryK=50 (Underfitting)Straight line, too simple

Weighted KNN

Curse of Dimensionality

# Demonstration: distances converge in high dimensions
import numpy as np
for d in [2, 5, 10, 50, 100, 500]:
    pts = np.random.rand(100, d)
    dists = np.sqrt(((pts[:,None] - pts[None,:])**2).sum(2))
    np.fill_diagonal(dists, np.inf)
    ratio = dists.max(axis=1).mean() / dists.min(axis=1).mean()
    print(f"d={d:3d}: d_max/d_min = {ratio:.2f}")
# Output: d_max/d_min → 1 as d → ∞

Real-World Applications

Recommendation Systems

Netflix and Spotify use KNN-based collaborative filtering. Users are represented as vectors of their ratings/listening history. To recommend new content, find the K most similar users and suggest what they liked. Item-based KNN finds similar items instead.

Medical Diagnosis

KNN helps diagnose diseases by comparing a patient's symptoms to K similar historical cases. If 8 out of 10 nearest patients had diabetes, the model predicts diabetes. This is particularly useful when the decision boundary is complex.

Anomaly Detection

Credit card fraud detection uses KNN: legitimate transactions cluster together, while fraudulent ones are far from any neighbors. Points with very few neighbors within a threshold distance are flagged as anomalies.

Image Recognition

Before deep learning, KNN with hand-crafted features (SIFT, HOG) was used for image classification. Given a test image, find the K most similar training images and take majority vote. Still useful as a baseline for small datasets.

Handwriting Recognition

KNN with pixel intensity features classifies handwritten digits (MNIST dataset). Each image is flattened into a vector of pixel values, and Euclidean distance measures similarity. Achieves ~97% accuracy with K=3.

Common Mistakes & How to Avoid Them

Mistake 1: Not scaling features

  • Problem: If age ranges 0-100 and income 0-1,000,000, income dominates the distance
  • Solution: Always standardize features (zero mean, unit variance) before KNN

Mistake 2: Using K=1

  • Problem: K=1 is extremely sensitive to noise and outliers — overfits badly
  • Solution: Use K=3 or higher. Cross-validate to find optimal K. Use odd K for binary classification.

Mistake 3: Ignoring the curse of dimensionality

  • Problem: With 100+ features, all points become equidistant — KNN loses its power
  • Solution: Use PCA or feature selection to reduce dimensions before KNN. Consider tree-based alternatives for high-dimensional data.

Mistake 4: Using KNN on large datasets

  • Problem: O(Nd) prediction time makes KNN slow for large N
  • Solution: Use approximate nearest neighbor (ANN) algorithms, KD-trees, or Ball trees for acceleration. Consider faster models for large datasets.

Mistake 5: Not handling categorical features

  • Problem: Euclidean distance doesn't make sense for categorical variables
  • Solution: Use Hamming distance for categorical features, or one-hot encode them before applying KNN.

Interview Questions

Q1: Why is KNN called a "lazy learner"? A: KNN doesn't build an explicit model during training — it simply stores the training data. All computation happens at prediction time when it computes distances to all training points. This contrasts with "eager learners" like logistic regression that learn a model during training.

Q2: How does K affect the bias-variance tradeoff in KNN? A: Small K (e.g., K=1): low bias, high variance — complex boundary, overfits. Large K: high bias, low variance — smooth boundary, underfits. The optimal K balances both, typically found via cross-validation.

Q3: What is the computational complexity of KNN? A: Training: O(1) — just store the data. Prediction: O(Nd) for N training points and d features — compute distances to all points. For acceleration, use KD-trees (O(d log N) average) or Ball trees.

Q4: When would you use Manhattan vs Euclidean distance? A: Manhattan (L1) is better for high-dimensional data and when features are independent. It's less affected by outliers (no squaring). Euclidean (L2) is the default for most applications and works well when features are correlated.

Q5: How do you handle ties in KNN voting? A: (1) Use odd K to avoid ties in binary classification, (2) Break ties randomly, (3) Weight votes by inverse distance (weighted KNN naturally handles ties), (4) Increase K slightly.

Q6: What improvements can be made to basic KNN? A: (1) Feature weighting (not all features equally important), (2) Distance metric learning, (3) Approximate nearest neighbors for speed, (4) Condensed nearest neighbors (prototype selection), (5) Locality-sensitive hashing for massive datasets.

Q7: How does KNN compare to logistic regression? A: KNN is non-parametric (no assumptions about data distribution), works with complex boundaries, but is slow and suffers from curse of dimensionality. Logistic regression is parametric (assumes linear boundary), fast, interpretable, but struggles with nonlinear relationships.

Practice Exercise

Challenge: KNN from Scratch

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from collections import Counter

# Load data
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Standardize
X_train = (X_train - X_train.mean(axis=0)) / X_train.std(axis=0)
X_test = (X_test - X_test.mean(axis=0)) / X_test.std(axis=0)

class KNN:
    def __init__(self, k=3):
        self.k = k
    
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
    
    def predict(self, X):
        predictions = [self._predict_one(x) for x in X]
        return np.array(predictions)
    
    def _predict_one(self, x):
        # Compute distances
        distances = np.sqrt(np.sum((self.X_train - x)**2, axis=1))
        # Get K nearest neighbors
        k_indices = np.argsort(distances)[:self.k]
        k_labels = self.y_train[k_indices]
        # Majority vote
        most_common = Counter(k_labels).most_common(1)
        return most_common[0][0]

# Test different K values
for k in [1, 3, 5, 7, 10]:
    knn = KNN(k=k)
    knn.fit(X_train, y_train)
    y_pred = knn.predict(X_test)
    acc = accuracy_score(y_test, y_pred)
    print(f"K={k:2d}: Accuracy = {acc:.3f}")

Bonus challenges:

  1. Implement weighted KNN (votes weighted by inverse distance)
  2. Use Manhattan distance instead of Euclidean
  3. Implement KD-tree for faster neighbor search

Comparison Table

KNN vs Other Algorithms

AspectKNNLogistic RegressionDecision Tree
TypeLazy / instance-basedEager / model-basedEager / model-based
Training TimeO(1) — just storeO(Nd × epochs)O(Nd log N)
Prediction TimeO(Nd) — slowO(d) — fastO(depth) — fast
Decision BoundaryArbitrary (nonlinear)LinearAxis-aligned
Interpretability★★★☆☆★★★★★★★★★★

Key Formulas Reference

FormulaExpressionContext
Euclidean DistanceDefault for KNN
Manhattan DistanceHigh-dim, robust
Minkowski DistanceGeneral (p=1 or 2)
Weighted VoteCloser = more weight
Cosine SimilarityText, direction

Key Takeaways

What to Learn Next

-> Decision Trees If-then rules that learn — the most interpretable algorithm.

-> Clustering Grouping the ungrouped — finding hidden structure in data.

-> Dimensionality Reduction Reduce features while preserving information with PCA and t-SNE.

←04 Logistic Regression06 Decision Trees→

Need Expert Machine Learning Help?

Get personalized tutoring, project support, or professional consulting.

Contact Us →View Services

Advertisement