Electronics & Telecommunication (University) is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

K-nearest neighbours

K-nearest neighbours (KNN) is a simple, instance-based supervised learning algorithm used for classification and regression that predicts a query point's label from the labels of its nearest training examples.

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-nearest neighbours (KNN) is used when you need a simple, interpretable method to classify items or predict values using similar past examples. Engineers use KNN in prototyping, anomaly detection, recommendation baselines and when model training time must be minimal while query time is acceptable.

Key ideas

  • Classification — predicting a discrete label; regression — predicting a continuous value. KNN can do both: classification by majority vote, regression by averaging neighbour values.
  • Feature vector — a vector x = (x1, x2, ..., xd) of d measured features for one example. We assume numeric features unless noted.
  • Distance metric — a function that gives a non-negative number measuring closeness between two feature vectors. Common metrics: Euclidean distance, Manhattan distance, Minkowski distance (general family). Define precisely: for two points x and y in R^d, Euclidean distance is sqrt(sum_i (xi - yi)^2).

KNN algorithm (classification) — exact description universities expect:

  1. Given training set T = {(x1, y1), (x2, y2), ..., (xn, yn)} where xi in R^d and yi in label set Y.
  2. Choose k, a positive integer (1 <= k <= n), and a distance metric D(., .).
  3. To classify query point x_q: a. Compute distances D(x_q, xi) for all i = 1..n. b. Select the k training points with smallest distances; call this set N_k(x_q). c. Predict label y_hat by majority vote among {yi | (xi, yi) in N_k(x_q)}. If there is a tie, break ties by choosing the label of the nearest neighbour among tied classes (deterministic tie-break) or by preferring lower index / class order.

Variants and important points:

  • Weighted KNN — weight neighbour votes by a function w(d) of distance (e.g., w(d) = 1/(d + epsilon), Gaussian kernel w(d) = exp(-d^2/(2σ^2))). This reduces influence of distant neighbours. For regression, use the weighted average y_hat(x_q) = (sum_{i in N_k(x_q)} w(D(x_q, x_i)) y_i) / (sum_{i in N_k(x_q)} w(D(x_q, x_i))).
  • Scaling / Normalisation — because distances combine feature dimensions, scale features to comparable ranges (standard score z = (x - mean)/std or min–max in [0,1]). Without scaling, features with larger numeric range dominate distance.
  • Categorical features — convert to numeric (one-hot encoding) or use Hamming distance (count mismatches) for categorical dimensions.
  • Curse of dimensionality — as d grows, relative differences in distances shrink, nearest neighbour becomes less informative. Dimensionality reduction (PCA, feature selection) is often needed first.
  • Choice of k — small k (e.g., 1) gives low bias but high variance; large k smooths decision boundary (higher bias, lower variance). A common rule: use cross-validation to choose k. For binary problems, odd k avoids ties.
  • Asymptotic property (sketch) — classical Cover & Hart (1967): with i.i.d. samples and mild regularity (e.g., feature distributions where exact ties have probability 0), the asymptotic error of 1-NN satisfies R_1NN ≤ R* (2 − R*), where R* is the Bayes error; in particular R_1NN ≤ 2 R*.
  • Complexity — training time is O(n·d) to read/store the data (no model fitting beyond storage); prediction for one query does O(n·d) distance computations plus either O(n log n) to sort, O(n) to select top-k, or O(n log k) with a heap. Data structures (kd-tree, ball-tree) can reduce average query time toward O(log n) for low d but degrade in high d. Memory requirement is O(n·d).

Diagram to draw for an exam (exact instructions):

  • Draw a 2D scatterplot with x-axis label "feature 1", y-axis label "feature 2". Plot two classes with different colours/shapes (e.g., blue circles for Class A, red crosses for Class B). Mark a query point with a black star.
  • Draw circles around the query showing the radius to its 1st, 3rd and 5th nearest neighbours. Also sketch the Voronoi region boundaries for 1-NN (straight perpendicular bisectors between neighbours) and label the predicted class for K=1 and K=5.

Assumptions to state in answers: data are i.i.d., features numeric or properly encoded, distance metric appropriate for features, ties broken deterministically.

Formulas

Euclidean distance: D(x,y) = sqrt(sum_{i=1..d} (x_i - y_i)^2) — x_i, y_i are the i-th feature values (Units: well-defined only if all features share the same units or after scaling/standardising features; otherwise treat distance as unitless.). Applies for real-valued feature vectors in R^d.

Minkowski distance (order p): D_p(x,y) = (sum_{i=1..d} |x_i - y_i|^p)^(1/p) — p >= 1; p=2 gives Euclidean, p=1 gives Manhattan. Units: well-defined only when all features share the same units or after scaling; otherwise treat as unitless.

Manhattan distance: D_1(x,y) = sum_{i=1..d} |x_i - y_i| — units are well-defined only when features share units or after scaling; otherwise treat as unitless.

Weighted vote (classification): score_c(x_q) = sum_{i in N_k(x_q), y_i = c} w(D(x_q, x_i)) — w(d) is a non-negative weight function (e.g., w(d)=1/(d+epsilon)). Predict class c with largest score_c.

KNN regression prediction: y_hat(x_q) = (1/k) * sum_{i in N_k(x_q)} y_i — y_i are numeric target values; units are units of target. Weighted regression: y_hat(x_q) = (sum_{i in N_k(x_q)} w(D(x_q, x_i)) y_i) / (sum_{i in N_k(x_q)} w(D(x_q, x_i))).

Brute-force query time: O(n * d + S(n,k)) — n training examples, d features; S(n,k) is the cost to select the k nearest (e.g., O(n log n) to sort, O(n) with selection, or O(n log k) with a heap).

Space: O(n * d) — storing all training feature values.

Worked examples

Example 1 — manual numerical classification (step-by-step) Given training set (height in cm, weight in kg, label):

  1. (170 cm, 65 kg) — Fit
  2. (160 cm, 55 kg) — NotFit
  3. (180 cm, 80 kg) — Fit
  4. (155 cm, 50 kg) — NotFit
  5. (175 cm, 70 kg) — Fit
  6. (165 cm, 60 kg) — NotFit Query: (168 cm, 66 kg). Use Euclidean distance and k=3. Step 1 — compute distances D = sqrt((h_q - h_i)^2 + (w_q - w_i)^2):
  • D1 = sqrt((168-170)^2 + (66-65)^2) = sqrt((-2)^2 + 1^2) = sqrt(4+1) = sqrt(5) = 2.23607 (numeric distance; mixing cm and kg requires prior scaling—treat distance as unitless after scaling)
  • D2 = sqrt((168-160)^2 + (66-55)^2) = sqrt(8^2 + 11^2) = sqrt(64+121) = sqrt(185) = 13.60147
  • D3 = sqrt((168-180)^2 + (66-80)^2) = sqrt((-12)^2 + (-14)^2) = sqrt(144+196) = sqrt(340) = 18.43909
  • D4 = sqrt((168-155)^2 + (66-50)^2) = sqrt(13^2 + 16^2) = sqrt(169+256) = sqrt(425) = 20.61553
  • D5 = sqrt((168-175)^2 + (66-70)^2) = sqrt((-7)^2 + (-4)^2) = sqrt(49+16) = sqrt(65) = 8.06226
  • D6 = sqrt((168-165)^2 + (66-60)^2) = sqrt(3^2 + 6^2) = sqrt(9+36) = sqrt(45) = 6.70820 Step 2 — sort distances: D1 (Fit)=2.236, D6 (NotFit)=6.708, D5 (Fit)=8.062, ... Nearest 3 labels: Fit, NotFit, Fit => majority = Fit. Final answer: Predicted label = Fit.

Example 2 — weighted KNN numeric calculation Use same data, k=3, weight w(d) = 1/d (avoid divide by zero). Compute weights for k=3 neighbors (distances D1, D6, D5):

  • w1 = 1 / 2.23607 = 0.44721
  • w2 = 1 / 6.70820 = 0.14907
  • w3 = 1 / 8.06226 = 0.12403 Sum weights: Fit = w1 + w3 = 0.44721 + 0.12403 = 0.57124; NotFit = w2 = 0.14907. Weighted vote -> Fit wins. Predicted label = Fit.

Example 3 — Python implementation (complete, runs with the dataset above)

# Simple KNN classifier from scratch (Euclidean, deterministic tie-break using nearest neighbour)
import math

def euclidean(a, b):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

def knn_predict(train_X, train_y, query, k=3):
    # compute distances
    dists = []
    for x, y in zip(train_X, train_y):
        d = euclidean(x, query)
        dists.append((d, y))
    # sort by distance
    dists.sort(key=lambda t: t[0])
    # take k nearest
    k_nearest = dists[:k]
    print('Nearest neighbors (distance, label):')
    for d, y in k_nearest:
        print(f'{d:.5f}', y)
    # majority vote
    counts = {}
    for d, y in k_nearest:
        counts[y] = counts.get(y, 0) + 1
    # find winner(s)
    max_count = max(counts.values())
    winners = [label for label, cnt in counts.items() if cnt == max_count]
    if len(winners) == 1:
        return winners[0]
    # tie-break: pick label of the nearest neighbour among tied labels
    for d, y in k_nearest:
        if y in winners:
            return y

if __name__ == '__main__':
    train_X = [ (170,65), (160,55), (180,80), (155,50), (175,70), (165,60) ]
    train_y = ['Fit', 'NotFit', 'Fit', 'NotFit', 'Fit', 'NotFit']
    query = (168,66)
    pred = knn_predict(train_X, train_y, query, k=3)
    print('Predicted label:', pred)

Sample exact output when run (each numeric distance rounded to 5 decimals): Nearest neighbors (distance, label): 2.23607 Fit 6.70820 NotFit 8.06226 Fit Predicted label: Fit

(You can change k and weight functions; this code is educational, not optimized.)

Common mistakes

  • Not handling ties deterministically — exam answers should state a tie-break rule.
  • Applying kd-tree or similar accelerated search without stating dimensionality limits (these degrade in high d).
  • Mixing units in features (e.g., seconds and metres) without normalising.
  • Forgetting the zero-distance case (query identical to training point) — should return that training label.
  • Using Euclidean distance for categorical data without encoding or using an appropriate metric.

For your exam

Types of questions you will get:

  • Definitions: define KNN, instance-based learning, distance metric, weighted KNN.
  • Short notes: explain scaling, curse of dimensionality, tie-breaking.
  • Derivations: derive Euclidean distance from Minkowski p=2, show majority vote rule, show weighted vote formula.
  • Numericals: compute distances for a small dataset and classify a query (show steps and units where applicable).
  • Programs: write a simple KNN from scratch (prefer Python); include deterministic tie-breaking and distance printing.
  • Diagrams: draw 2-D scatter with Voronoi regions for 1-NN and indicate k-neighbour circles.

What a full-marks answer includes:

  • Precise definitions with bold terms, stated assumptions (i.i.d., numeric features or encoding), the algorithm steps, and complexity.
  • For numericals: show every distance calculation, sorting, and final majority or weighted vote, carry units, and give final answer clearly.
  • For programs: correct, runnable code with sample input and sample output; state any tie-break policy.

Quick check

  1. What is the time complexity to answer one query with brute-force KNN in terms of n (examples) and d (features)?
  2. Why must we scale features before using Euclidean distance? Give one method to scale.
  3. For binary classification with k=5, neighbour labels are [A, B, A, B, A]. What is the predicted label under (a) normal KNN majority vote and (b) weighted with weight = 1/d if the distances corresponding to these labels are [2, 3, 4, 5, 6] respectively? (Compute weighted sums.) Answers: 1) O(n·d). 2) Because features with larger numeric ranges dominate distance; one method is standardisation z = (x - mean)/std. 3a) A (3 votes vs 2). 3b) weights: 1/2=0.5 (A), 1/3≈0.333 (B), 1/4=0.25 (A), 1/5=0.2 (B), 1/6≈0.1667 (A). Sum A = 0.5+0.25+0.1667=0.9167, Sum B = 0.333+0.2=0.5333; weighted winner = A.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?