k-nearest neighbours (KNN)

Prerequisites

• Euclidean distance: $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$.
• Feature scaling.
• Bias–variance, to understand the role of $k$.

The analogy

How it works

Requirement: features must be on comparable scales, because KNN compares raw distances. Standardize first.

Start with one classification by hand

Training: A(1, 1) red, B(2, 2) red, C(3, 3) blue, D(4, 2) blue. New point P(2.5, 2), $k = 3$, Euclidean distance. Predict, then open "Check".

Finish the picture: the effect of k

Same data, other values of $k$.

• $k = 1$. Predict the behaviour on noisy data.
  Check

  Very flexible: each prediction copies the single nearest point, noise included. Low bias, high variance.

• $k = 4$ (all points). Predict P's label and the general behaviour.
  Check

  A 2–2 tie here; in general, $k = n$ always predicts the majority class. Very smooth: high bias, low variance. Odd $k$ avoids ties with two classes.

Full worked calculation

Every distance for the new point $P = (2.5, 2)$, the ranking, two different votes, and why they disagree. Training points: A(1, 1) red, B(2, 2) red, C(3, 3) blue, D(4, 2) blue.

1. 1Differences per coordinate

   $$\Delta x = x_i - 2.5, \qquad \Delta y = y_i - 2$$

   For each training point we measure how far it is from $P$ along each axis. Signs don't matter yet, because the next step squares them.

2. 2Squared Euclidean distance

   $$d_B^2 = (-0.5)^2 + 0^2 = 0.25, \qquad d_C^2 = 0.5^2 + 1^2 = 1.25$$

   Squaring removes the signs and makes larger gaps count more. To rank neighbours you can stop here: the square root never changes the order.

3. 3Actual distances

   $$d_A = \sqrt{3.25} \approx 1.803,\; d_B = 0.5,\; d_C = \sqrt{1.25} \approx 1.118,\; d_D = 1.5$$

   Taking square roots gives distances in the original units. They are needed for distance-weighted voting (step 6).

4. 4Rank and keep the k nearest

   $$B\,(0.5) < C\,(1.118) < D\,(1.5) < A\,(1.803) \quad\Rightarrow\quad k = 3: \{B, C, D\}$$

   Sorting by distance and keeping the first $k$ gives the neighbourhood that will vote. A, the farthest, is ignored with $k = 3$.

5. 5Majority vote

   $$\text{red}: 1 \;(B), \qquad \text{blue}: 2 \;(C, D) \quad\Rightarrow\quad \hat y = \text{blue}$$

   Each neighbour has one vote. Two of the three are blue, so P is classified blue, with an estimated probability of 2/3.

6. 6Distance-weighted vote

   $$\text{red}: \tfrac{1}{0.5} = 2.0, \qquad \text{blue}: \tfrac{1}{1.118} + \tfrac{1}{1.5} = 0.894 + 0.667 = 1.561 \quad\Rightarrow\quad \hat y = \text{red}$$

   A common variant gives closer neighbours bigger votes, weight $1/d$. B is so close (0.5) that its vote outweighs C and D together, and the answer flips to red.

The rule in plain words

To classify a point, compute its distance to every training point, take the $k$ nearest, and return their majority label (or mean value, for regression).

Choose $k$ by cross-validation: small $k$ overfits, large $k$ underfits. Always scale the features first.

The code

Read this code after you have classified P by hand. It will make more sense.

int knn_predict(double px[], double py[], int label[], int n, double qx, double qy, int k) {
    double d[100]; int idx[100];                   /* labels are 0 (red) or 1 (blue) */
    for (int i = 0; i < n; i++) { d[i] = (px[i]-qx)*(px[i]-qx) + (py[i]-qy)*(py[i]-qy); idx[i] = i; }
    int votes = 0;
    for (int j = 0; j < k; j++) {                  /* select the j-th nearest */
        int best = j;
        for (int i = j + 1; i < n; i++) if (d[idx[i]] < d[idx[best]]) best = i;
        int t = idx[j]; idx[j] = idx[best]; idx[best] = t;
        votes += label[idx[j]];
    }
    return 2 * votes > k ? 1 : 0;                  /* majority vote */
}

flowchart TD
  A["new point P"] --> B["distance from P to every training point"]
  B --> C["keep the k smallest distances"]
  C --> D{"classification or regression?"}
  D -->|classification| E["majority vote of their labels"]
  D -->|regression| F["average of their values"]
          

How costly is it?

Distances are Euclidean; one prediction compares the query with all $n$ training points in $d$ dimensions:

Best for: small to medium datasets with few, well-scaled features and irregular class boundaries.

• Pro: No training; adapts to any boundary shape.
• Pro: Simple to understand and easy to update with new data.
• Con: Slow predictions and high memory on large datasets.
• Con: Suffers in high dimensions (distances become similar) and needs scaling.

Common mistakes

• Forgetting to scale features before computing distances.
• Using an even $k$ with two classes, which allows ties.
• Evaluating with the training points themselves, where $k = 1$ is always 100% correct.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• KNN needs no training because it stores the data and decides at prediction time.
• Predictions are slow because each one computes distances to all $n$ training points.
• Scaling is essential because distances are dominated by the largest-valued feature.
• Small $k$ overfits because a single noisy neighbour decides the label.
• Large $k$ underfits because far-away points dilute the local pattern.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is KNN like asking your nearest neighbours about a new town?
   Sample answer

   You guess what a place is like from the few people closest to you; KNN labels a point from its $k$ closest training points.

2. Classify P(2.5, 2) with $k = 3$ given A, B red and C, D blue.
   Sample answer

   Distances: B 0.5, C 1.12, D 1.5, A 1.80. Nearest three B, C, D vote blue two to one.

3. Why does the code compare squared distances instead of taking the square root?

   A good answer mentions order.

   Sample answer

   The square root doesn't change which distances are smallest, so skipping it gives the same neighbours with less work.

4. So what is KNN, in one sentence?
   Sample answer

   A method that predicts from the majority label, or average value, of the $k$ nearest training points.

5. Why does the choice of $k$ change P's label?

   A good answer relates $k$ to bias and variance.

   Sample answer

   With $k = 1$, only B (red) votes; with $k = 3$, C and D join and outvote it. Small $k$ follows local details (high variance); larger $k$ smooths them out (higher bias).

6. What do training and one prediction cost?
   Sample answer

   Training is just storing the data; a brute-force prediction is $O(nd)$.

7. Give two pros and two cons of KNN.
   Sample answer

   Pros: no training, any boundary shape. Cons: slow, memory-hungry predictions, and poor in high dimensions or without scaling.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out KD-trees and the curse of dimensionality. I'd keep the neighbour analogy, the P example with $k = 3$ versus $k = 1$, and "scale features, choose $k$ by CV".

External resources

• scikit-learn: Nearest neighbors: classification, regression and fast search structures.
• Wikipedia: k-nearest neighbors algorithm: theory and variants.
• GeeksforGeeks: KNN: worked examples with code.

Videos

• YouTube search: StatQuest KNN: StatQuest's short video on KNN.