k-nearest neighbour classification
k-nearest neighbour (k-NN) classification is a simple, non-parametric method that labels a query by majority vote of its k closest training examples using a chosen distance measure, widely used for prototype-based classification and baseline models in engineering tasks.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
k-NN classification is used by engineers as a simple, interpretable baseline for classification problems, for prototype matching, and in systems where training is cheap but queries must use stored examples (e.g., image retrieval, anomaly detection, recommendation). It is also taught because it shows important ideas: distance measures, the need for normalization, curse of dimensionality, and model selection (choosing k).
Key ideas
Decision rule (exact statement): Let training set be {(x_i, y_i)} for i = 1..n. For a query x, let N_k(x) be indices of k points with smallest distances to x. Then the k-NN prediction ŷ is any label maximizing sum_{i in N_k(x)} I(y_i = c) over classes c (I is indicator). If weighted k-NN is used, maximize sum_{i in N_k(x)} w_i·I(y_i = c) where weights w_i depend on distance (larger weight for closer neighbour). Tie-breaking: If multiple classes have equal votes, state a deterministic rule (e.g., choose the class with the smallest total distance to the query, or use a fixed class order) and apply it.
Weighted k-NN: weighting schemes include inverse-distance weight w_i = 1/(d(x, x_i)+ε) and Gaussian kernel w_i = exp(-d(x,x_i)^2 / (2σ^2)). Choose ε>0 to avoid division by zero.
Choice of k: small k (e.g., 1) gives low bias but high variance and very flexible decision boundary; large k smooths predictions (higher bias, lower variance). Use cross-validation (commonly k-fold or leave-one-out) to select k. In binary classification, using an odd k reduces the chance of ties.
Normalization: If features have different units or scales, distance will be dominated by large-scale features. Apply feature scaling such as min-max normalization or z-score (standardization) before distance computations. Fit the scaling parameters (min, max, or mean and standard deviation) on the training set only, and apply the same transformation to queries/test data.
Complexity: Brute-force k-NN requires O(n·d) time per query (n = number of training examples, d = number of features), and O(n·d) memory to store training data. Query time can be improved in low dimensions using indexing structures like kd-tree or ball-tree (often near O(log n) average), at the cost of extra space; performance degrades in high dimensions (curse of dimensionality).
Curse of dimensionality: As d grows, distances concentrate and nearest neighbours become less informative. Effective dimensionality reduction (PCA) or feature selection is often needed when d is large.
Theoretical fact (advanced): For 1-NN, under mild regularity conditions and as n → ∞, the asymptotic error rate of the nearest-neighbour rule is at most twice the Bayes error rate (Cover and Hart, 1967). However, 1-NN is not Bayes-consistent in general; k-NN becomes universally consistent when k → ∞ and k/n → 0.
Decision boundary drawing (what to draw for an exam): For 1-NN in 2D with two classes, draw a scatter plot of training points (use different markers for each class). For each training point, draw perpendicular bisectors between that point and its neighbours to form the Voronoi diagram: regions in the plane where a given training point is the nearest neighbour. Label axes x1, x2 and show a new query point and which cell it falls into.
Formulas
d_E(x, y) = sqrt( sum_{j=1..d} (x_j - y_j)^2 ) — Euclidean distance. x_j, y_j are feature j; unit: same as features (no SI unit); applies when features are numeric and scaled comparably.
d_M1(x, y) = sum_{j=1..d} |x_j - y_j| — Manhattan (L1) distance. Units: same as features; applies when differences add linearly or robust to outliers.
d_p(x, y) = ( sum_{j=1..d} |x_j - y_j|^p )^(1/p) — Minkowski distance with order p ≥ 1. p=1 → Manhattan, p=2 → Euclidean.
d_Cheb(x, y) = max_{j=1..d} |x_j - y_j| — Chebyshev distance (L∞). Units: same as features.
d_Mah(x, y) = sqrt( (x - y)^T Σ^{-1} (x - y) ) — Mahalanobis distance. Σ is covariance matrix of features; units: dimensionless after appropriate covariance units; applies when features have different scales and are correlated.
z_j = (x_j - μ_j) / σ_j — z-score standardization. μ_j is mean of feature j, σ_j is standard deviation. Unit: dimensionless; apply before Euclidean distance when features have different variances.
x'_j = (x_j - min_j) / (max_j - min_j) — min-max normalization to [0,1]. Unit: dimensionless.
prediction ŷ = argmax_c sum_{i in N_k(x)} w_i·I(y_i = c) — weighted vote. w_i ≥ 0 are weights; apply in weighted k-NN.
time_per_query_bruteforce = O(n · d) — time complexity for naïve search. n is count of stored examples, d is number of features.
Worked examples
Example 1 — 2D numeric dataset, Euclidean, k = 3 Training set (units: no physical units, just numeric features x1,x2):
- (1.0, 1.0) class A
- (2.0, 1.0) class A
- (2.0, 2.0) class B
- (3.0, 4.0) class B Query: x = (2.2, 1.5). Use Euclidean distance and k = 3. Steps:
- Formula:
d_E(x, x_i) = sqrt((x1 - x1_i)^2 + (x2 - x2_i)^2). - Distances:
- d to #1: sqrt((2.2-1.0)^2 + (1.5-1.0)^2) = sqrt(1.44 + 0.25) = sqrt(1.69) = 1.3
- d to #2: sqrt((2.2-2.0)^2 + (1.5-1.0)^2) = sqrt(0.04 + 0.25) = sqrt(0.29) ≈ 0.5385
- d to #3: sqrt((2.2-2.0)^2 + (1.5-2.0)^2) = sqrt(0.04 + 0.25) = sqrt(0.29) ≈ 0.5385
- d to #4: sqrt((2.2-3.0)^2 + (1.5-4.0)^2) = sqrt(0.64 + 6.25) = sqrt(6.89) = 2.6249
- Sort distances: indices 2 (0.5385, A), 3 (0.5385, B), 1 (1.3, A) are the nearest three. (If exact tie between 2 and 3, both included — tie in distance is fine.)
- Majority vote among classes {A, B, A} → A wins (2 votes vs 1). Final answer: predicted class = A.
Example 2 — effect of normalization (min-max) on classification Training set:
- (age = 20, income = 20,000) class Low
- (age = 22, income = 25,000) class Low
- (age = 40, income = 90,000) class High Query: (age = 30, income = 50,000). If we use Euclidean without normalization, income dominates because income values are large. Steps without normalization:
- distances are dominated by income differences; Euclidean distances are approximately: to #1 ≈ 30000.002, to #2 ≈ 25000.001, to #3 ≈ 40000.001; the nearest is #2 (class Low). With min-max normalization to [0,1] per feature:
- age' = (30 - 20) / (40 - 20) = 10/20 = 0.5
- income' = (50000 - 20000) / (90000 - 20000) = 30000/70000 ≈ 0.4286 Repeat distances on normalized features: to #1 ≈ 0.6586, to #2 ≈ 0.5362, to #3 ≈ 0.7593; the nearest is still #2 (Low). Normalization ensures both features contribute comparably; in other datasets it can change the predicted class. This shows you must standardize features before k-NN when scales differ. Final point: Always show normalization steps in exam answers and state why it was necessary.
Common mistakes
- Not stating how ties are broken when multiple classes have equal votes.
- Applying kd-trees or ball-trees without noting they degrade in high dimension (d large) — claim of O(log n) query time is only for low d.
- Confusing Minkowski p parameter: p must be ≥ 1. p < 1 is not a metric and shouldn't be used as a distance in proofs requiring triangle inequality.
- Computing Mahalanobis distance but forgetting to invert the covariance matrix or using a singular covariance (must regularize or remove collinear features).
For your exam
Typical question types:
- Definitions and short notes: define k-NN, distance measures, curse of dimensionality, kd-tree.
- Derivation/algorithm trace: trace k-NN on a small dataset (you must compute distances and votes step-by-step).
- Numerical: show normalization and recompute distances; calculate weighted k-NN with specific weights.
- Program/design: pseudo-code for brute-force k-NN and brief discussion of time and space complexity and indexing options.
- Diagram: draw 2D scatter and Voronoi cells for 1-NN; label axes and classes. What a full-marks answer includes:
- Precise definitions (bold if asked), assumptions, and chosen distance.
- Step-by-step distance calculations with formulas shown before plugging numbers.
- Clear statement of k, tie-breaking rule, and whether features were normalized (show normalization math).
- Complexity analysis and brief discussion of alternatives (kd-tree, ball-tree, approx. nearest neighbours) and limits (curse of dimensionality).
Quick check
- What is the time complexity per query for brute-force k-NN in terms of n and d?
- Give the formula for z-score standardization of a feature x_j.
- For k = 3 with neighbour classes {A, B, B}, what is the predicted class? (Assume simple majority vote.) Answers: 1) O(n · d). 2) z_j = (x_j - μ_j) / σ_j. 3) B.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?