05_k_Nearest_Neighbour

Module 4 — k-Nearest-Neighbour Decision Rules

Source: Lec 9 — k-Nearest Neighbor Decision Rule. · Prev: Module 3 · Next: Module 5 — Regression · Index: 00_INDEX_and_Coverage

Setup

Training pairs $({\vec{X}}_i,y_i)$, $i=\mathrm{1..}n$, ${\vec{X}}_i\in {\mathbb{R}}^m$, $y_i\in \{1,\dots ,c\}$, $c\ge 2$. Test point ${\vec{X}}_0$. Distance $\rho$ (default Euclidean).

Python helpers — run once, the checks below reuse them

import numpy as np
 
def knn(X, y, x0, k):
    """Plain kNN vote. Returns (label, sorted distances of the k neighbours)."""
    d = np.linalg.norm(np.asarray(X, float) - x0, axis=1)
    idx = np.argsort(d, kind="stable")[:k]
    labs, cnt = np.unique(np.asarray(y)[idx], return_counts=True)
    return labs[cnt.argmax()], d[idx]
 
def dudani(d):
    """Dudani weights for distances d sorted ascending."""
    d = np.asarray(d, float)
    return np.ones_like(d) if d[-1] == d[0] else (d[-1] - d) / (d[-1] - d[0])
 
def tknn(seq, beta):
    """Tweaked kNN on a list of neighbour labels (nearest first). Returns (label, L) or (None, None)."""
    for L in range(beta, len(seq) + 1):
        c = sorted(np.unique(seq[:L], return_counts=True)[1], reverse=True) + [0]
        if c[0] - c[1] == beta:
            return max(set(seq[:L]), key=seq[:L].count), L
    return None, None

---

C23. The kNN Decision Rule

Intuition

“Tell me who your neighbours are and I will tell you who you are.” Find the $k$ training points closest to the new point and let them vote. Like asking the 3 nearest shops whether a new product sells — you trust people who live closest.

 x2
  6 |  B       ← B cluster
  5 |  B  B
    |
  2 |   ●?     ← query (k=3): neighbours A(1.0) A(1.4) B(4.2)  →  A
  1 | A  A
    +------------→ x1

Algorithm (lecture)

1. Compute $\rho ({\vec{X}}_0,{\vec{X}}_i)$ for all $i$.
2. Sort the distances in non-decreasing order.
3. Take the first $k$ (the $k$ nearest neighbours).
4. Let $L_j$ be the number of those $k$ points in class $j$. Assign ${\vec{X}}_0$ to class $p$ if $L_p\ge L_j\forall j\ne p$. Ties are broken arbitrarily.

Geometrically, the neighbourhood is the closed disk of radius $r_k=\rho ({\vec{X}}_0,\text{its }k\text{th nearest neighbour})$.

Mathematical facts

• Choice of $k$: no universal rule; estimate by cross-validation (C13). Small $k$ ⇒ low bias, high variance (jagged boundary); large $k$ ⇒ smoother, may swamp small classes.
• 1-NN asymptotics (Cover & Hart 1967): as $n\to \infty$, the 1-NN error is at most twice the Bayes error $R^{\ast }$. More precisely, for two classes $R_{1NN}\le 2R^{\ast }(1-R^{\ast })\le 2R^{\ast }$.
• Cost: no training, $O(nm)$ per query.

Derivation of the 1-NN limit (two classes)

Let $\eta (\vec{x})=P(w_1|\vec{x})$. As $n\to \infty$ the nearest neighbour ${\vec{x}}^{\prime }$ of $\vec{x}$ converges to $\vec{x}$, so its label is an independent draw with $P(w_1)=\eta (\vec{x})$. 1-NN errs when the test label and the neighbour’s label differ: $e_{1NN}(\vec{x})=\eta (1-\eta )+(1-\eta )\eta =2\eta (1-\eta ),e_{Bayes}(\vec{x})=\min (\eta ,1-\eta ).$ Let $r=\min (\eta ,1-\eta )$; then $2\eta (1-\eta )=2r(1-r)\le 2r$. Taking expectations (with $R^{\ast }=\mathbb{E}[r]$): $R_{1NN}=2\mathbb{E}[r]-2\mathbb{E}[r^2]\le 2R^{\ast }-2(R^{\ast }{)}^2=2R^{\ast }(1-R^{\ast })$, because Jensen gives $\mathbb{E}[r^2]\ge (\mathbb{E}[r]{)}^2$. ∎

Key insights

• Distance function and feature scaling dominate the behaviour.
• Majority voting is unreliable when the top two classes are nearly tied (the lecture’s motivation for the variants C24–C25).

Worked examples

Example 1 — Very Easy · Healthy or diseased plant?

• Problem: Two leaf-sensor readings per plant. Training: $(1,1)$ A, $(2,1)$ A, $(5,5)$ B, $(6,5)$ B, $(5,6)$ B (A = healthy, B = diseased). Classify $(2,2)$ with $k=3$ (Euclidean).
• Asked: Class.
• Concept: kNN.
• Approach: Distances, sort, vote.
• Solution: $d(1,1)=1.414$; $d(2,1)=1$; $d(5,5)=4.243$; $d(6,5)=5$; $d(5,6)=5$. Sorted: $(2,1)A(1),(1,1)A(1.414),(5,5)B(4.243)$. Votes: A = 2, B = 1.
• Final answer: A.

Python check

X = [(1,1), (2,1), (5,5), (6,5), (5,6)]; y = list("AABBB")
print(knn(X, y, np.array([2, 2]), 3))        # ('A', [1.  1.414  4.243])

Key lesson

Only the $k$ closest matter; the two B points at distance 5 never vote.

Example 2 — Easy · The vote flips with $k$

• Problem: The sorted neighbour labels of ${\vec{X}}_0$ (nearest first) are $y_1,y_2,y_1,y_2,y_2,y_1,y_1,y_2,y_1$. Classify for $k=5,6,7,9$.
• Asked: Four decisions.
• Concept: Dependence on $k$.
• Approach: Count in prefixes.
• Solution:

$k$	$y_1$	$y_2$	decision
5	2	3	$y_2$
6	3	3	tie
7	4	3	$y_1$
9	5	4	$y_1$

• Final answer: $y_2$, tie, $y_1$, $y_1$.

Key lesson

The prediction flips with $k$ when the vote is nearly even.

Example 3 — Moderate · How good can 1-NN be?

• Problem: Two classes with Bayes error $R^{\ast }=0.05$. Bound the asymptotic 1-NN error. Repeat for $R^{\ast }=0.3$.
• Asked: Two bounds.
• Concept: Cover–Hart.
• Approach: $2R^{\ast }(1-R^{\ast })$ vs $2R^{\ast }$.
• Solution: $R^{\ast }=0.05$: $2(0.05)(0.95)=0.095$ (crude: $0.10$). $R^{\ast }=0.3$: $2(0.3)(0.7)=0.42$ (crude: $0.6$).
• Final answer: $\le 0.095$ and $\le 0.42$.

Key lesson

The bound is tight when $R^{\ast }$ is small, loose when large (it cannot exceed $0.5$).

Example 4 — Hard · Why you must scale features

• Problem: Features (age in years, income in ₹). Training: $A=(25,50500)$, $B=(30,52000)$. Test $(30,50000)$. Feature standard deviations: age $5$, income $10000$. Classify by 1-NN raw and after standardising (divide differences by the std).
• Asked: Two decisions.
• Concept: Feature scaling.
• Approach: Compute both distances twice.
• Solution: Raw: $d_A=\sqrt{5^2+500^2}=500.02$; $d_B=\sqrt{0+2000^2}=2000$ ⇒ A. Scaled: ${\Delta }_A=(1,-0.05)$, $d_A=1.0012$; ${\Delta }_B=(0,-0.2)$, $d_B=0.2$ ⇒ B.
• Final answer: Raw → A; scaled → B.

Python check

a = np.array([(25 - 30) / 5, (50500 - 50000) / 10000]); b = np.array([0, 2000 / 10000])
print(np.linalg.norm(a), np.linalg.norm(b))      # 1.0012  0.2   -> B

Key lesson

Without normalisation the large-unit feature (income) is the only feature that matters.

Example 5 — Very Hard · Cover–Hart on a two-region world

• Problem: Half of the input space has $\eta =P(w_1|\vec{x})=0.9$, the other half $\eta =0.5$. Compute (a) the Bayes error, (b) the asymptotic 1-NN error, (c) $2R^{\ast }(1-R^{\ast })$, and confirm (b) $\le$ (c) $\le 2R^{\ast }$.
• Asked: Three numbers and verification.
• Concept: Cover–Hart derivation.
• Approach: Local errors, then average.
• Solution: (a) Local Bayes: $\min (0.9,0.1)=0.1$ and $0.5$. $R^{\ast }=\frac{1}{2}(0.1)+\frac{1}{2}(0.5)=0.3$. (b) Local 1-NN: $2(0.9)(0.1)=0.18$ and $2(0.5)(0.5)=0.5$. $R_{1NN}=\frac{1}{2}(0.18)+\frac{1}{2}(0.5)=0.34$. (c) $2(0.3)(0.7)=0.42$; $2R^{\ast }=0.6$. Chain: $0.34\le 0.42\le 0.6$ ✓.
• Final answer: $R^{\ast }=0.30$, $R_{1NN}=0.34$, bound $0.42$.

region	$\eta$	Bayes $\min (\eta ,1-\eta )$	1-NN $2\eta (1-\eta )$
half 1	0.9	0.10	0.18
half 2	0.5	0.50	0.50
average		0.30	0.34

Key lesson

1-NN pays extra only where the posterior is neither pure nor 50/50.

Common mistakes

• Not scaling features.
• Using even $k$ in 2-class problems (ties).
• Believing 1-NN error is always twice Bayes (it is an upper bound).

Exam traps

• Ties are broken arbitrarily.
• “Optimal $k$” is found by cross-validation; there is no formula.
• The bound requires $n\to \infty$.

Connections: Bayes error (C15), cross-validation (C13), weighted / Tweaked kNN (C24, C25), k-means assignment (C36).

Mastery checklist

• Run kNN by hand.
• Explain the effect of $k$ and of scaling.
• Derive $2\eta (1-\eta )$ for 1-NN.

---

C24. Distance-Weighted kNN

Intuition

A neighbour 1 cm away should speak louder than one 10 km away. Give each of the $k$ neighbours a weight that decreases with distance.

Formal definition (Dudani 1976, as in the lecture)

Let ${\vec{X}}_1,\dots ,{\vec{X}}_k$ be the $k$ nearest neighbours sorted by distance $d_j=\rho ({\vec{X}}_j,{\vec{X}}_0)$, so $d_1\le \cdots \le d_k$. $w_j=\{\begin{array}{ll}\frac{d_k-d_j}{d_k-d_1},& d_k\ne d_1,\\ 1,& d_k=d_1.\end{array}$ Assign ${\vec{X}}_0$ to the class whose neighbours’ weights sum to the greatest value.

 weight
 1.0 |●
     |   ●
     |        ●        weights fall linearly from 1 (nearest)
 0.0 +-----------●→ d   to 0 (k-th neighbour)
       d1  d2   dk

Properties

• $w_1=1$ (nearest) and $w_k=0$ (farthest), linear in between.
• It reduces sensitivity to the arbitrary cut-off, but $k$ must still be chosen.

Worked examples

Example 1 — Very Easy · Compute the weights

• Problem: Distances $d=(1,2,4)$ for $k=3$. Weights?
• Asked: $w_1,w_2,w_3$.
• Concept: Linear weighting.
• Approach: $d_1=1,d_k=4$.
• Solution: $w_1=\frac{4-1}{3}=1$; $w_2=\frac{4-2}{3}=0.6667$; $w_3=0$.
• Final answer: $(1,0.667,0)$.

Key lesson

The farthest neighbour always gets weight 0.

Example 2 — Easy · Plain vs weighted vote

• Problem: Neighbour labels (nearest first) $A,B,B$ with the distances above. Plain vote vs weighted vote.
• Asked: Two classes.
• Concept: Weighted voting.
• Approach: Sum the weights per class.
• Solution: Plain: A = 1, B = 2 ⇒ B. Weighted: A $=1$; B $=0.6667+0=0.6667$ ⇒ A.
• Final answer: Plain → B; weighted → A.

Python check

w = dudani([1, 2, 4]); labels = np.array(list("ABB"))
print(w, {c: w[labels == c].sum() for c in "AB"})        # [1. .667 0.]  {'A': 1.0, 'B': 0.667}

Key lesson

One very close point can outweigh two distant ones.

Example 3 — Moderate · All distances equal

• Problem: $d=(2,2,2,2,2)$ with labels $A,A,B,B,B$. Weights and decision.
• Asked: Weights, class.
• Concept: Degenerate case $d_k=d_1$.
• Approach: Use the "$1$" branch.
• Solution: All $w_j=1$ ⇒ A $=2$, B $=3$ ⇒ B (ordinary kNN).
• Final answer: B.

Key lesson

The formula degrades gracefully to majority vote.

Example 4 — Hard · Five neighbours

• Problem: $k=5$ with distances $(0.5,0.6,1.0,2.0,2.5)$ and labels $A,B,B,A,A$. Compute weights and compare plain majority vs weighted.
• Asked: Weights, both decisions.
• Concept: Weighted kNN.
• Approach: $d_1=0.5$, $d_5=2.5$, denominator $2.0$.
• Solution: $w=(1,0.95,0.75,0.25,0)$. Class A: $1+0.25+0=1.25$. Class B: $0.95+0.75=1.70$. Plain majority: A $=3$, B $=2$ ⇒ A. Weighted ⇒ B.
• Final answer: Plain → A; weighted → B.

Python check

w = dudani([.5, .6, 1.0, 2.0, 2.5]); lab = np.array(list("ABBAA"))
print(w, {c: round(w[lab == c].sum(), 2) for c in "AB"})   # [1 .95 .75 .25 0]  {'A': 1.25, 'B': 1.7}

Key lesson

Close neighbours (B, B) outweigh far ones (A, A).

Example 5 — Very Hard · Weighted kNN can collapse to 1-NN

• Problem: Show (i) the weighted rule with $k$ neighbours ignores the $k$th, so it uses only the $k-1$ nearer neighbours; (ii) construct $k=3$ distances where weighted kNN is identical to 1-NN regardless of the other labels.
• Asked: Proof and construction.
• Concept: Weight structure.
• Approach: Algebra.
• Solution: (i) $w_k=0$ always, so $X_k$ never contributes. The remaining weights are $\frac{d_k-d_j}{d_k-d_1}$, $j<k$; they depend on $d_k$ — so $k$ still controls the scale of the weighting. (ii) Let $d=(1,5,5.001)$ with labels $A,B,B$. Weights: $w_1=1$; $w_2=\frac{0.001}{4.001}=0.00025$; $w_3=0$. Class A $=1$; B $=0.00025$ ⇒ A, the 1-NN label, even though a majority of 3 says B.
• Final answer: Weighted kNN can behave like 1-NN when the nearest neighbour is much closer than the rest.

Python check

print(dudani([1, 5, 5.001]))                              # [1.  0.00025  0.]

Key lesson

The weighting depends on relative distances; an outlier in distance can make the rule effectively 1-NN.

Common mistakes

• Forgetting $w_k=0$.
• Using $1/d$ weights and calling them the lecture formula.

Exam traps

• Weights use $d_k-d_j$ in the numerator, $d_k-d_1$ in the denominator.
• You still need a valid $k$.

Connections: C23, C25.

Mastery checklist

• Compute linear distance weights.
• Explain when weighted and plain kNN disagree.

---

C25. Tweaked kNN (TkNN): Bounded Majority Voting

Intuition

Instead of fixing $k$, keep widening the neighbourhood until the winner leads the runner-up by a margin $\beta$. If no margin is ever reached, refuse to classify. A single, more interpretable parameter $\beta$ replaces $k$.

flowchart TD
    S[Sort neighbours] --> I["L ← β"]
    I --> C{"margin = L_max1 − L_max2 = β ?"}
    C -->|yes| O[Output majority class]
    C -->|no| G["L ← L+1"]
    G --> E{"L > n ?"}
    E -->|no| C
    E -->|yes| U[Unclassified]

Algorithm (lecture)

1. Compute and sort distances $\rho ({\vec{X}}_0,{\vec{X}}_i)$.
2. $L\leftarrow \beta$ (a positive integer).
3. Take the first $L$ neighbours; let $L_j$ be the class counts. $L_{max1}={\max }_j{L}_j$; $L_{max2}$ = second largest.
4. If $L_{max1}-L_{max2}=\beta$ ⇒ output the majority class. Else $L\leftarrow L+1$ and repeat. If $L>n$ ⇒ ${\vec{X}}_0$ is unclassified.

Properties

• $\beta =1$ ⇒ the rule equals 1-NN (at $L=1$ the margin is already $1$).
• Larger $\beta$ ⇒ more cautious, more abstentions.
• Choose $\beta$ by cross-validation. It does not consider the quality of the voting neighbours (open problem noted in the lecture).

Worked examples

Example 1 — Very Easy · β = 1 is 1-NN

• Problem: Show TkNN with $\beta =1$ equals 1-NN.
• Asked: Proof.
• Concept: Margin definition.
• Approach: Start at $L=1$.
• Solution: At $L=\beta =1$: the top class has count 1, every other has 0 ⇒ margin $=1=\beta$ ⇒ stop, output the class of the nearest neighbour.
• Final answer: Yes.

Key lesson

$\beta =1$ is the most permissive setting.

Example 2 — Easy · The alternating sequence

• Problem: The sequence (nearest first) $y_1,y_2,y_1,y_2,y_2,y_1,y_1,y_2,y_1$ (the lecture’s 9.1). Run TkNN with $\beta =1$ and $\beta =2$.
• Asked: Output.
• Concept: Algorithm.
• Approach: Track the margin.
• Solution: $\beta =1$: $L=1$: counts $(1,0)$ margin $1=\beta$ ⇒ $y_1$. $\beta =2$:

$L$	2	3	4	5	6	7	8	9
counts $(y_1,y_2)$	(1,1)	(2,1)	(2,2)	(2,3)	(3,3)	(4,3)	(4,4)	(5,4)
margin	0	1	0	1	0	1	0	1

Never reaches $2$; $L=10>n$ ⇒ unclassified.

• Final answer: $\beta =1\to y_1$; $\beta =2\to$ unclassified.

Python check

s = "1 2 1 2 2 1 1 2 1".split()
print(tknn(s, 1), tknn(s, 2))                            # ('1', 1)  (None, None)

Key lesson

The lecture’s remark “for $\beta \ge 2$ cannot classify” is verified; an alternating sequence never builds a margin.

Example 3 — Moderate · Adaptive k

• Problem: Sequence $y_2,y_1,y_2,y_2,y_1,y_1$ with $\beta =2$. Output and the effective $k$.
• Asked: Class and $L$.
• Concept: Adaptive $k$.
• Approach: Margin tracking.
• Solution: $L=2$: $(y_2:1,y_1:1)$ margin 0. $L=3$: $(2,1)$ margin 1. $L=4$: $(3,1)$ margin $2=\beta$ ⇒ stop.
• Final answer: $y_2$ with $L=4$.

Key lesson

The effective $k$ depends on the query.

Example 4 — Hard · Three classes

• Problem: Three classes $a,b,c$; sequence $a,b,c,a,b,a,a$; $\beta =2$. Find the output and $L$.
• Asked: Class and $L$.
• Concept: $L_{max2}$ with three classes.
• Approach: Counts $(a,b,c)$ at each $L$.
• Solution: $L=2$: $(1,1,0)$ margin 0. $L=3$: $(1,1,1)$ margin 0. $L=4$: $(2,1,1)$ margin 1. $L=5$: $(2,2,1)$ margin 0. $L=6$: $(3,2,1)$ margin 1. $L=7$: $(4,2,1)$ margin $4-2=2=\beta$ ⇒ stop.
• Final answer: $a$ at $L=7$.

Python check

print(tknn("2 1 2 2 1 1".split(), 2), tknn(list("abcabaa"), 2))   # ('2', 4)  ('a', 7)

Key lesson

The margin is against the second best class, not the average of the others.

Example 5 — Very Hard · Why the margin is exactly β

• Problem: Show that TkNN can only ever stop when $L\ge \beta$ and that the margin at stopping is exactly $\beta$ (not larger). Then argue why overshooting is impossible.
• Asked: Two proofs.
• Concept: Margin dynamics.
• Approach: One-step margin changes.
• Solution: The margin $M_L=L_{max1}-L_{max2}$ is at most $L$ (all neighbours in one class), so stopping requires $L\ge \beta$ — matching the initial $L=\beta$. When $L$ increases by 1, exactly one class count increases by 1: if it is the leader, $M$ rises by 1; if it is the runner-up, $M$ falls by 1; otherwise $M$ is unchanged. So $|\Delta M|\le 1$ and $M$ cannot jump over $\beta$: the first time $M\ge \beta$ it equals $\beta$. (At the start $L=\beta$ we have $M\le \beta$.)
• Final answer: The stopping margin is exactly $\beta$.

Key lesson

The test "$=\beta$" is equivalent to "$\ge \beta$", because $M$ moves in unit steps.

Common mistakes

• Starting with $L=1$ instead of $L=\beta$ (harmless, but not the lecture’s algorithm).
• Forgetting to return “unclassified”.

Exam traps

• $\beta =1$ ⇒ 1-NN.
• No $k$ is needed, but $\beta$ is.

Connections: C23, C24, cross-validation (C13).

Mastery checklist

• Run TkNN on a label sequence.
• Explain why $\beta =1$ is 1-NN.
• State when it abstains.