# k-Nearest neighbors

> Predict by vote or average of the k closest training points — there is no training step.

Source: https://www.mlfoundry.in/learn/k-nearest-neighbors  
Section: ML Algorithms › Supervised · Classification  
Level: core · 17 min read · updated 2026-10-07

**k-nearest neighbors (k-NN):** classifies a new point $q$ by finding the $k$ training points closest to it under a distance metric and letting them **vote**: the predicted class is the one most common among those neighbours, and the vote shares are its class probabilities. Nothing is fitted. The stored training set *is* the model.

- **Task:** Classification (this article); the same recipe with an average instead of a vote gives **KNN regression**
- **Input → output:** query $q\in\mathbb{R}^d$ → class probabilities $\hat p(c\mid q)$ = (weighted) share of the $k$ neighbours in class $c$, and $\hat y=\arg\max_c \hat p(c\mid q)$
- **Learns:** nothing: it memorises all $n$ labelled pairs $(x_i,y_i)$ (a *lazy*, *instance-based* learner)
- **Training cost:** $O(1)$ to store; $O(dn\log n)$ if you build a KD-tree or ball tree for faster search
- **Prediction cost:** $O(nd)$ per query by brute force (plus $O(n)$ to select the $k$ smallest); roughly $O(\log n)$ with a tree index in low dimension
- **Hyperparameters:** `n_neighbors` k, `weights` (uniform or distance), the metric (`p` for Minkowski, or any custom distance), the search `algorithm`
- **Assumes:** points that are close under your metric tend to share a label; all features are on comparable scales and actually relevant

## The problem

Most classifiers commit to a *shape* for the decision boundary before they see data. **Logistic regression** draws a straight line (a hyperplane); a **decision tree** draws axis-aligned boxes; **Naive Bayes** assumes features are independent within each class. When the true boundary is curved, wiggly, or made of several disconnected islands, these shapes fit it badly unless you hand-engineer features.

There is a much weaker assumption that holds for an enormous range of problems: **similar inputs have similar labels**. Two emails with almost the same words are probably both spam or both not; two tumours with nearly identical measurements probably share a diagnosis. k-NN turns that single assumption into a classifier with no parameters to fit and no boundary shape to choose. The price is paid at prediction time, and in the need for a distance that genuinely captures "similar".

## The idea

To label a new point, look at the training points around it and copy the local majority. Picture the data as coloured dots on a map. Drop the query on the map, draw the smallest circle around it that contains $k$ dots, and count colours. The circle's radius adapts automatically: in dense regions it is small and the prediction is very local; in sparse regions it grows until it has gathered enough evidence.

$k$ controls how much evidence you demand. With $k=1$ you copy the single nearest point, so every training point owns a little territory around it (its **Voronoi cell**) and the boundary bends around every outlier. With large $k$ the vote averages over a wide neighbourhood: the boundary becomes smooth, but small or minority regions get out-voted. At the extreme $k=n$, every query sees the whole dataset and k-NN predicts the majority class everywhere.

**Vocabulary**

- **Query point q:** the unlabelled input you want a prediction for
- **Neighbourhood N_k(q):** the indices of the $k$ training points with the smallest distance to $q$
- **k-th neighbour distance:** $r_k(q)$, the distance to the farthest member of $N_k(q)$: the radius of the smallest ball around $q$ holding $k$ points
- **Metric:** the distance function $d(\cdot,\cdot)$; Euclidean ($L_2$), Manhattan ($L_1$) and cosine are the usual choices
- **Uniform vs distance weighting:** each neighbour casts one vote, or a vote of weight $1/d(q,x_i)$ so that closer neighbours count more
- **Voronoi cell:** the region of space closer to one training point than to any other; the 1-NN decision regions are unions of these cells
- **Lazy learner:** a method that defers all work to prediction time; the opposite (eager) learners compress data into parameters during training
- **Leave-one-out (LOO):** predict each training point from all the others; for k-NN it is cheap and the standard way to pick k on small data

## The math

Everything depends on the distance. The **Minkowski** family covers the common cases:

$$
d_p(q,x)=\Big(\sum_{j=1}^{d}\lvert q_j-x_j\rvert^{p}\Big)^{1/p}
$$

- $q,\;x$: the query and a training point, both in $\mathbb{R}^d$
- $q_j,\;x_j$: their $j$-th features
- $p$: $p=2$ Euclidean (straight-line), $p=1$ Manhattan (sum of absolute differences), $p\to\infty$ the largest single difference

The unit "ball" of $d_p$ changes shape with $p$: a circle for $p=2$, a diamond for $p=1$, a square for $p=\infty$. $L_1$ is less dominated by one large coordinate difference than $L_2$, which squares it. Given a metric, the classifier is a vote over the neighbourhood:

$$
\hat p(c\mid q)=\frac{\sum_{i\in N_k(q)} w_i\,[\,y_i=c\,]}{\sum_{i\in N_k(q)} w_i},\qquad \hat y(q)=\arg\max_c\,\hat p(c\mid q)
$$

- $N_k(q)$: the $k$ training indices nearest to $q$
- $[\,y_i=c\,]$: 1 if neighbour $i$ has class $c$, else 0
- $w_i$: vote weight: $w_i=1$ (uniform) or $w_i=1/d(q,x_i)$ (distance weighting)
- $\hat p(c\mid q)$: estimated probability of class $c$ at $q$: the (weighted) fraction of neighbours in class $c$

With uniform weights, $\hat p(c\mid q)=k_c/k$, where $k_c$ is the number of neighbours in class $c$. With $k=5$ these probabilities can only be $0, 0.2, 0.4,\dots,1$: k-NN probabilities are coarse, and you need a larger $k$ for smoother ones.

## Why voting is the right thing: k-NN as density estimation

The vote is not an ad-hoc rule; it falls out of Bayes' rule with a local density estimate. Grow a ball of volume $V$ around $q$ until it contains $k$ points, $k_c$ of them from class $c$. If class $c$ has $n_c$ training points in total, the fraction of them inside the ball estimates its probability mass there, so the class-conditional density is about

$$
\hat p(q\mid c)=\frac{k_c}{n_c V},\qquad \hat p(c)=\frac{n_c}{n},\qquad \hat p(q)=\frac{k}{nV}
$$

- $V$: volume of the smallest ball around $q$ holding $k$ training points (radius $r_k(q)$)
- $n_c,\;n$: training points in class $c$, and in total
- $k_c$: neighbours of $q$ that belong to class $c$

Plug these into Bayes' rule $p(c\mid q)=p(q\mid c)\,p(c)/p(q)$. The volume $V$ and the counts $n$, $n_c$ all cancel:

$$
\hat p(c\mid q)=\frac{\dfrac{k_c}{n_cV}\cdot\dfrac{n_c}{n}}{\dfrac{k}{nV}}=\frac{k_c}{k}
$$

So majority voting is the **Bayes classifier applied to a nearest-neighbour density estimate**, and the vote shares are genuine (if noisy) posterior estimates. It also explains the bias–variance trade-off of $k$. The estimate $k_c/k$ is a proportion over $k$ samples, so its variance is about $p(1-p)/k$: small $k$ gives noisy probabilities. But the ball must grow to hold $k$ points, and the larger it is, the more it averages over regions where $p(c\mid x)$ differs from $p(c\mid q)$: large $k$ gives biased, over-smoothed probabilities. Consistency theory makes this precise: k-NN converges to the Bayes-optimal classifier as $n\to\infty$ provided $k\to\infty$ and $k/n\to 0$.

> **Even 1-NN is at most twice as bad as perfect:** Cover and Hart (1967) proved that, as $n\to\infty$, the error rate $R_{1}$ of the *one*-nearest-neighbour rule on two classes satisfies $R^*\le R_1\le 2R^*(1-R^*)\le 2R^*$, where $R^*$ is the Bayes error, the lowest error any classifier can achieve. Half of all the classification information in an infinite sample is contained in the single nearest neighbour.

**Distance weighting** replaces $w_i=1$ with $w_i=1/d(q,x_i)$. It makes the prediction depend continuously on how close each neighbour is, reduces the sensitivity to the exact choice of $k$ (far neighbours barely count), and breaks ties. If $q$ coincides with a training point, $d=0$ and that point takes all the weight (scikit-learn's convention), so distance-weighted k-NN, like 1-NN, always reproduces its training labels.

**Scale.** Every metric above adds up raw feature differences, so a feature measured in large units dominates. The standard fix is to standardise each feature, $x_j\mapsto (x_j-\mu_j)/\sigma_j$, which is the same as using a diagonal Mahalanobis distance:

$$
d_M(q,x)=\sqrt{(q-x)^\top M\,(q-x)},\qquad M=\operatorname{diag}(1/\sigma_1^2,\dots,1/\sigma_d^2)
$$

- $M$: a positive-definite matrix; $M=I$ is Euclidean, $M=\Sigma^{-1}$ (inverse covariance) is the full Mahalanobis distance
- $\sigma_j$: standard deviation of feature $j$ on the training set

Learning $M$ from labels (so that same-class points end up close) is called **metric learning**; NCA and LMNN are the classical methods. In deep learning the same idea appears as training an embedding network and running k-NN on its outputs.

## Worked example: is a tomato a fruit?

Fourteen foods, scored 0–10 for **sweetness** and **crunchiness** (both features already on the same scale, so no standardisation is needed), and labelled fruit or vegetable. The query is a tomato: sweetness 6, crunchiness 4. Botanists and cooks disagree about tomatoes, and so, it turns out, do different values of $k$.

Training data: 6 fruits and 8 vegetables. Highlighted: the 5 foods nearest the tomato at (6, 4).

| # | Food | Sweetness | Crunchiness | Class |
| --- | --- | --- | --- | --- |
| 1 | peach | 7 | 4.5 | fruit |
| 2 | orange | 8 | 3 | fruit |
| 3 | pear | 7.5 | 6 | fruit |
| 4 | apple | 9 | 8 | fruit |
| 5 | banana | 10 | 1.5 | fruit |
| 6 | grape | 8.5 | 5 | fruit |
| 7 | bell pepper | 5 | 5 | vegetable |
| 8 | sweet potato | 6.5 | 2.5 | vegetable |
| 9 | carrot | 3 | 9 | vegetable |
| 10 | celery | 2 | 8 | vegetable |
| 11 | lettuce | 1 | 6 | vegetable |
| 12 | cucumber | 2 | 4 | vegetable |
| 13 | onion | 3 | 2 | vegetable |
| 14 | green bean | 3.5 | 6.5 | vegetable |

**Classifying the tomato q = (6, 4) by hand**

1. **Distances.** For every food compute $d=\sqrt{(x_1-6)^2+(x_2-4)^2}$. Peach: $\sqrt{1^2+0.5^2}=\sqrt{1.25}=1.118$. Bell pepper: $\sqrt{(-1)^2+1^2}=\sqrt{2}=1.414$. Sweet potato: $\sqrt{0.5^2+(-1.5)^2}=\sqrt{2.5}=1.581$. Orange: $\sqrt{2^2+(-1)^2}=\sqrt5=2.236$. Pear: $\sqrt{1.5^2+2^2}=\sqrt{6.25}=2.500$. The other nine are all farther (next: grape 2.693, green bean 3.536; the farthest is the carrot at 5.831).
2. **Sort** the 14 distances ascending (table below). There is no "training": this ranking is computed fresh for this query.
3. **k = 1.** The single nearest food is the peach, a fruit. $\hat p(\text{fruit})=1/1=1.0$ → **fruit**.
4. **k = 3.** Peach (fruit), bell pepper (veg), sweet potato (veg). Votes 1 to 2, $\hat p(\text{fruit})=1/3=0.333$ → **vegetable**.
5. **k = 5.** Add orange and pear, both fruit. Votes 3 to 2, $\hat p(\text{fruit})=3/5=0.600$ → **fruit**.
6. **k = 3 with 1/d weights.** Fruit: $1/1.118=0.894$. Vegetable: $1/1.414+1/1.581=0.707+0.632=1.340$. $\hat p(\text{fruit})=0.894/(0.894+1.340)=0.400$ → still **vegetable**: two moderately close vegetables outweigh one closer fruit.
7. **k = 5 with 1/d weights.** Fruit gains $1/2.236+1/2.5=0.447+0.400$, reaching $1.742$; vegetable stays $1.340$. $\hat p(\text{fruit})=0.565$ → **fruit**, slightly less confident than the uniform 0.600 because the two added fruits are the farthest neighbours.

The seven nearest foods to the tomato, with the running vote. The prediction flips fruit → vegetable → fruit as k goes 1 → 3 → 5.

| Rank | Food | Δ sweet | Δ crunch | d² | d | Class | Votes so far (fruit : veg) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | peach | 1 | 0.5 | 1.25 | 1.118 | fruit | 1 : 0 |
| 2 | bell pepper | −1 | 1 | 2.00 | 1.414 | vegetable | 1 : 1 |
| 3 | sweet potato | 0.5 | −1.5 | 2.50 | 1.581 | vegetable | **1 : 2** |
| 4 | orange | 2 | −1 | 5.00 | 2.236 | fruit | 2 : 2 |
| 5 | pear | 1.5 | 2 | 6.25 | 2.500 | fruit | **3 : 2** |
| 6 | grape | 2.5 | 1 | 7.25 | 2.693 | fruit | 4 : 2 |
| 7 | green bean | −2.5 | 2.5 | 12.50 | 3.536 | vegetable | 4 : 3 |

Three values of $k$, two different answers. Which should we trust? Use the data itself: **leave-one-out** predicts each of the 14 foods from the other 13 and counts the hits.

Leave-one-out accuracy on the 14 foods (Euclidean). k = 5 is the smallest k with the best score, so it is the one we choose, and the tomato is a fruit.

| k | 1 | 3 | 5 | 7 | 9 | 11 | 13 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Uniform vote | 11/14 = 0.786 | 12/14 = 0.857 | **13/14 = 0.929** | 12/14 = 0.857 | 13/14 = 0.929 | 7/14 = 0.500 | 8/14 = 0.571 |
| 1/d weights | 0.786 | 0.857 | **0.929** | 0.857 | 0.929 | 0.929 | 0.929 |

The table tells the whole bias–variance story. At $k=1$ three foods are misclassified: orange (its nearest other food is the sweet potato), bell pepper and sweet potato (each sits next to fruit). At $k=5$ only the sweet potato, a genuinely fruit-like vegetable, is still wrong. At $k=11$ the uniform vote collapses to 7/14: leaving out a fruit leaves only 5 fruits among the 13 remaining foods, so an 11-point neighbourhood is always mostly vegetable, and **every fruit is misclassified**. Distance weighting rescues large $k$ because the far-away vegetables barely count.

## Explore it

> Figure: The 14 foods from the worked example. Drag the tomato (✚); the dashed ball passes through the k-th neighbour, the lines show who votes, and the background shading is the prediction everywhere. At (6, 4) with Euclidean distance: k = 1 → fruit, k = 3 → vegetable (P(fruit) = 0.333, 0.400 with 1/d weights), k = 5 → fruit (0.600). Toggle Manhattan to see the ball become a diamond. The bars on the right are leave-one-out hits for every odd k: 11, 12, 13, 12, 13, 7, 8 with a uniform vote. Switch to 1/d weights and the k = 11 and 13 bars jump to 13. At k = 1 the boundary is made of Voronoi-cell edges and bends around the sweet potato; at k = 13 with a uniform vote the tomato becomes a vegetable (P(fruit) = 0.462).

> **What to try in the figure:** Set $k=13$ with a uniform vote: the vegetable region swallows nearly everything, because 8 of the 14 foods are vegetables. Then click 1/d weights and watch the fruit region come back. Drag the tomato slowly along the line between peach and bell pepper at $k=1$; the prediction flips exactly at the perpendicular bisector of the two points.

## The algorithm, step by step

**fit(X, y) and predict(q)**

1. **Fit.** Standardise the features (store each $\mu_j,\sigma_j$), then store the $n$ scaled rows and their labels. Optionally build a KD-tree or ball tree over them.
2. **Distances.** For a query $q$ (scaled with the *training* $\mu,\sigma$), compute $d(q,x_i)$ for every stored point, or let the tree prune whole regions that cannot contain a nearer point.
3. **Select** the $k$ smallest. A partial selection (quickselect / "argpartition") does this in $O(n)$; a full sort costs $O(n\log n)$.
4. **Weight** each neighbour: $w_i=1$, or $w_i=1/d_i$ (an exact match takes all the weight).
5. **Vote.** Sum the weights per class, divide by the total to get $\hat p(c\mid q)$, and return the arg-max. Break remaining ties consistently (scikit-learn picks the class that comes first in its sorted class list), or avoid them with an odd $k$ on two classes.

> Figure: The same procedure on three classes: store, measure every distance, sort, take the k = 5 nearest, vote. The circle grows to the k-th neighbour; two queries give two different answers.

**Complexity**

- **Fit:** $O(1)$ (brute force) or $O(dn\log n)$ (KD-tree / ball tree build); memory $O(nd)$ either way: you keep every training point
- **Predict, brute force:** $O(nd)$ distances + $O(n)$ selection per query; vectorises perfectly on GPUs, so it is often the fastest exact choice for moderate n
- **Predict, KD-tree:** about $O(\log n)$ per query when $d$ is small, degrading towards $O(n)$ as $d$ grows, because the pruning test rarely succeeds
- **Predict, approximate (HNSW, IVF-PQ):** sub-linear search over millions to billions of vectors, trading a small loss in recall for orders-of-magnitude speed; this is what vector databases do

## Choosing k and the other knobs

> Figure: A larger noisy two-class dataset. Slide k and click to move the query: k = 1 scores perfectly on the training points it memorised but worse on fresh test points; moderate k trades a little training accuracy for better test accuracy.

Hyperparameters and their effect.

| Knob | Small / off | Large / on | Practical default |
| --- | --- | --- | --- |
| `n_neighbors` k | jagged boundary, Voronoi islands around outliers, high variance, coarse probabilities | smooth boundary, minority classes out-voted, high bias; k = n predicts the majority | tune by cross-validation over odd k; √n is a common starting point |
| `weights` | uniform: every neighbour counts the same, sensitive to k | distance: close neighbours dominate, robust to large k, ties vanish | try both in the grid search |
| metric | L2: rotation-invariant, dominated by the largest difference | L1: more robust to one extreme coordinate; cosine: compares direction only (text, embeddings) | L2 on standardised numeric features; cosine on embeddings |
| feature scaling | unscaled: the feature with the biggest units decides | standardised or min-max scaled: features contribute comparably | always scale, inside a Pipeline |
| `algorithm` | brute: exact, simple, GPU-friendly | kd_tree / ball_tree: fast in low d; ANN libraries for huge n | `auto` lets scikit-learn choose |

> **Unscaled features decide the neighbours:** Suppose crunchiness had been measured on a 0–100 scale instead of 0–10. Multiply that column by 10 and rerun the worked example: the tomato's single nearest neighbour becomes the **cucumber**, a vegetable 4 sweetness units away, because a 0.5-unit crunchiness gap now counts as 5. The 1-NN answer flips from fruit to vegetable for a reason that has nothing to do with food. Standardising the columns gives the same 5 neighbours whichever units were used.

## The curse of dimensionality

k-NN's one assumption, that near means similar, quietly breaks in high dimensions, for two reasons. First, **neighbourhoods stop being local**. To capture 1% of points spread uniformly in a unit hypercube, a sub-cube needs edge length $0.01^{1/d}$: 0.1 of each axis in 2-D, but 0.631 in 10-D and 0.955 in 100-D. Your "nearest" neighbours then span almost the whole range of every feature.

Second, **distances concentrate**. With 1,000 uniform random points and 100 random queries, the average ratio of nearest to farthest distance is 0.017 in 2-D, 0.275 in 10-D, 0.694 in 100-D and 0.894 in 1000-D. When every point is about equally far away, "nearest" carries little information. Real data usually lives near a much lower-dimensional surface, which is why k-NN still works on images and embeddings, but irrelevant features hurt: each one adds noise to every distance. Select features, or reduce dimension with **PCA** or a learned embedding first.

> **Where the siblings fit:** Using a different similarity than a plain distance leads to kernel methods: a **support vector machine** also predicts from a weighted vote over training points, but it learns which few points matter (the support vectors) and how much each counts, instead of using the $k$ nearest with fixed weights. See **support vector machines** and **support vector regression** for that theory. For numeric targets, the neighbourhood-average version is covered in **KNN regression**.

## In code

```python
import numpy as np

def knn_predict_proba(X_train, y_train, Q, k=5, weights="uniform", p=2, n_classes=None):
    """Class probabilities for each query row: (weighted) share of the k nearest neighbours."""
    n_classes = n_classes or y_train.max() + 1
    D = (np.abs(Q[:, None, :] - X_train[None, :, :]) ** p).sum(-1) ** (1 / p)  # (m, n) Minkowski
    idx = np.argsort(D, axis=1, kind="stable")[:, :k]                         # k nearest, ties by index
    d = np.take_along_axis(D, idx, axis=1)
    if weights == "distance":
        w = np.where(d == 0, 1e12, 1 / np.maximum(d, 1e-12))                  # exact match dominates
    else:
        w = np.ones_like(d)
    P = np.zeros((len(Q), n_classes))
    for c in range(n_classes):
        P[:, c] = (w * (y_train[idx] == c)).sum(1)
    return P / P.sum(1, keepdims=True), idx, d

def loo_accuracy(X, y, k, **kw):
    hits = 0
    for i in range(len(X)):
        keep = np.arange(len(X)) != i
        P, _, _ = knn_predict_proba(X[keep], y[keep], X[i:i + 1], k, n_classes=2, **kw)
        hits += P.argmax() == y[i]
    return hits / len(X)

names = ["peach", "orange", "pear", "apple", "banana", "grape", "bell pepper",
         "sweet potato", "carrot", "celery", "lettuce", "cucumber", "onion", "green bean"]
X = np.array([[7, 4.5], [8, 3], [7.5, 6], [9, 8], [10, 1.5], [8.5, 5], [5, 5],
              [6.5, 2.5], [3, 9], [2, 8], [1, 6], [2, 4], [3, 2], [3.5, 6.5]])
y = np.array([0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1])        # 0 = fruit, 1 = vegetable
tomato = np.array([[6, 4]])

for k in (1, 3, 5):
    P, idx, d = knn_predict_proba(X, y, tomato, k)
    print(f"k={k}: P(fruit)={P[0, 0]:.3f} ->", ["fruit", "vegetable"][P.argmax()],
          "| neighbours:", [f"{names[i]} {dist:.3f}" for i, dist in zip(idx[0], d[0])])
P, _, _ = knn_predict_proba(X, y, tomato, 3, weights="distance")
print(f"k=3, 1/d weights: P(fruit)={P[0, 0]:.3f}")
for k in (1, 3, 5, 7, 9, 11, 13):
    print(f"LOO k={k:2d}: uniform {loo_accuracy(X, y, k):.3f}  distance {loo_accuracy(X, y, k, weights='distance'):.3f}")

# k=1: P(fruit)=1.000 -> fruit | neighbours: ['peach 1.118']
# k=3: P(fruit)=0.333 -> vegetable | neighbours: ['peach 1.118', 'bell pepper 1.414', 'sweet potato 1.581']
# k=5: P(fruit)=0.600 -> fruit | neighbours: [... 'orange 2.236', 'pear 2.500']
# k=3, 1/d weights: P(fruit)=0.400
# LOO k= 1: uniform 0.786 ... k= 5: uniform 0.929 ... k=11: uniform 0.500  distance 0.929
```

From scratch in NumPy: Minkowski distance, uniform or 1/d weights, probabilities, and leave-one-out. Runs as-is.

```python
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV, LeaveOneOut

X = np.array([[7, 4.5], [8, 3], [7.5, 6], [9, 8], [10, 1.5], [8.5, 5], [5, 5],
              [6.5, 2.5], [3, 9], [2, 8], [1, 6], [2, 4], [3, 2], [3.5, 6.5]])
y = np.array(["fruit"] * 6 + ["vegetable"] * 8)
tomato = [[6, 4]]

for k in (1, 3, 5):
    knn = KNeighborsClassifier(n_neighbors=k).fit(X, y)
    dist, idx = knn.kneighbors(tomato)
    print(k, knn.predict(tomato)[0], knn.predict_proba(tomato).round(3)[0], dist.round(3)[0], idx[0])

search = GridSearchCV(KNeighborsClassifier(),
                      {"n_neighbors": [1, 3, 5, 7, 9, 11, 13], "weights": ["uniform", "distance"]},
                      cv=LeaveOneOut()).fit(X, y)
print("best:", search.best_params_, round(search.best_score_, 3))

# 1 fruit [1. 0.] [1.118] [0]
# 3 vegetable [0.333 0.667] [1.118 1.414 1.581] [0 6 7]
# 5 fruit [0.6 0.4] [1.118 1.414 1.581 2.236 2.5  ] [0 6 7 1 2]
# best: {'n_neighbors': 5, 'weights': 'uniform'} 0.929
```

scikit-learn on the same data, with k and the weighting chosen by leave-one-out grid search.

> **In a real project:** Wrap the scaler and the classifier together, `make_pipeline(StandardScaler(), KNeighborsClassifier())`, and tune `kneighborsclassifier__n_neighbors` with cross-validation, so that each fold's scaling statistics come only from its own training part.

**Strengths**

- You want a strong, assumption-light baseline in minutes: no training, any boundary shape, any number of classes.
- Data is low-dimensional or lives in a good embedding space where distance means similarity.
- Data arrives continuously: learning a new example is appending a row, and forgetting one is deleting it.
- You want explanations by example: "classified as fraud because these 5 past transactions were most similar".

**Limitations**

- Many raw, irrelevant or differently-scaled features: distances concentrate and noise drowns the signal.
- Large n with tight latency or memory budgets, unless you can use an approximate-NN index.
- Classes are heavily imbalanced: the majority class wins most neighbourhoods unless you weight votes or rebalance.
- You need calibrated probabilities or extrapolation far from the training data: k-NN only knows what is near.

- **Retrieval and RAG:** Vector databases return the k nearest document embeddings to a query embedding; k-NN classification on top gives zero-training text and image classifiers.
- **Recommendation:** Neighbourhood collaborative filtering: recommend what the k most similar users liked, or items similar to ones you bought.
- **Handwriting and face recognition:** k-NN on raw pixels is a classic strong baseline for MNIST digits; on face embeddings from a deep network it identifies people from a handful of examples.
- **Imputation and anomaly detection:** Fill a missing value from the k most similar rows (`KNNImputer`); flag a point whose k-th neighbour distance is unusually large (the idea behind LOF).

> **Evaluating on the training set:** With $k=1$ (or any $k$ with 1/d weights) each training point is its own nearest neighbour at distance 0, so training accuracy is 100% by construction and tells you nothing. Always measure k-NN with held-out data or leave-one-out, as in the table above.

> **Ties and even k:** With two classes and even $k$, a 2-to-2 vote is a tie that scikit-learn resolves by class order, not by evidence: at $k=4$ the tomato's votes are 2 fruit to 2 vegetable, and it is called "fruit" only because "fruit" sorts first. Use odd $k$ for binary problems, or distance weights.

**Question:** A query's three nearest neighbours are at distances 1 (class A), 2 (class B) and 4 (class B). What do a uniform vote and a 1/d-weighted vote predict?

- A. A and A
- B. B and B
- C. B (uniform) and A (weighted)
- D. A (uniform) and B (weighted)

**Answer:** C. B (uniform) and A (weighted) — Uniform: B wins 2 to 1. Weighted: A gets $1/1=1.0$, B gets $1/2+1/4=0.75$, so A wins, with $\hat p(A)=1/1.75\approx 0.571$.

**Question:** In the worked example, why does leave-one-out accuracy with a uniform vote drop to 7/14 at k = 11?

- A. Distances become meaningless at k = 11
- B. Leaving out a fruit leaves only 5 fruits among 13 foods, so any 11 neighbours are mostly vegetables
- C. k = 11 is even
- D. The sweet potato is an outlier

**Answer:** B. Leaving out a fruit leaves only 5 fruits among 13 foods, so any 11 neighbours are mostly vegetables — An 11-point neighbourhood drawn from 5 fruits and 8 vegetables contains at most 5 fruits, so it always votes vegetable: all 6 fruits are misclassified (the sweet potato is wrong too). This is large-k bias: the majority class swallows the minority.

**Question:** Points are uniform in a 10-dimensional unit cube. A sub-cube that holds 1% of them must have an edge length of about…

- A. 0.01
- B. 0.1
- C. 0.63
- D. 0.99

**Answer:** C. 0.63 — Edge $=0.01^{1/10}=0.631$: to collect just 1% of the data you must span 63% of every axis, so the "local" neighbourhood is not local at all.

**Question:** Features are [annual salary in dollars, years of experience], unscaled. Euclidean neighbours are chosen almost entirely by…

- A. experience
- B. salary
- C. both equally
- D. neither

**Answer:** B. salary — Salary differences are in the thousands and experience differences are single digits; squared, salary dominates the sum. Standardise both first.

**Key points**

- k-NN stores the data and predicts by a (weighted) vote of the $k$ nearest points; the vote shares $k_c/k$ are Bayes-rule posteriors from a local density estimate.
- $k$ is the bias–variance dial: $k=1$ gives Voronoi islands and 100% training accuracy; large $k$ smooths and lets the majority class win. Pick it by cross-validation or leave-one-out.
- Distance weighting (1/d) makes predictions robust to large k and removes most ties.
- Everything depends on the metric: standardise features, drop irrelevant ones, and use cosine or learned embeddings for text and images.
- Prediction costs O(nd) per query by brute force; KD-trees help in low dimension, approximate-NN indexes at scale. High dimensions make all distances look alike.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
