05_k_Nearest_Neighbour

Module 4 — k-Nearest-Neighbour Decision Rules

Source: Lec 9 — k-Nearest Neighbor Decision Rule.

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).

---

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.

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

• Problem: Training: $(1,1)A,(2,1)A,(5,5)B,(6,5)B,(5,6)B$. Classify $(2,2)$ with $k=3$ (Euclidean).
• Asked: Class.
• Concept: kNN.
• Approach: Distances, sort, vote.
• Solution: $d(1,1)=\sqrt{1+1}=1.414$; $d(2,1)=1$; $d(5,5)=\sqrt{9+9}=4.243$; $d(6,5)=\sqrt{16+9}=5$; $d(5,6)=\sqrt{9+16}=5$. Sorted: $(2,1)A(1),(1,1)A(1.414),(5,5)B(4.243)$. Votes: A=2, B=1.
• Final answer: A.
• Key lesson: Only the $k$ closest matter.

Example 2 — Easy

• Problem: The sorted neighbour labels of ${\vec{X}}_0$ are (nearest first): $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=5$: $y_1$: positions 1,3 ⇒ 2; $y_2$: 2,4,5 ⇒ 3 ⇒ $y_2$. $k=6$: $y_1$: 1,3,6 ⇒ 3; $y_2$ 3 ⇒ tie. $k=7$: $y_1$: 1,3,6,7 ⇒ 4; $y_2$ 3 ⇒ $y_1$. $k=9$: $y_1$: 1,3,6,7,9 ⇒ 5; $y_2$ 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

• 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

• 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}=\sqrt{25+250000}=500.02$; $d_B=\sqrt{0+2000^2}=2000$ ⇒ A. Scaled: ${\Delta }_A=(\frac{5}{5},\frac{-500}{10000})=(1,-0.05)$, $d_A=\sqrt{1+0.0025}=1.0012$; ${\Delta }_B=(0,\frac{-2000}{10000})=(0,-0.2)$, $d_B=0.2$ ⇒ B.
• Final answer: Raw → A; scaled → B.
• Key lesson: Without normalisation the large-unit feature is the only feature.

Example 5 — Very Hard

• 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$.
• 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.

Properties

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

Worked examples

Example 1 — Very Easy

• 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=\frac{4-4}{3}=0$.
• Final answer: $(1,0.667,0)$.
• Key lesson: The farthest neighbour always gets 0.

Example 2 — Easy

• 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 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.
• Key lesson: One very close point can outweigh two distant ones.

Example 3 — Moderate

• Problem: $d=(2,2,2,2,2)$ (all equal) 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

• 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=(\frac{2.0}{2.0},\frac{1.9}{2.0},\frac{1.5}{2.0},\frac{0.5}{2.0},0)=(1,0.95,0.75,0.25,0)$. Class A: $w_1+w_4+w_5=1+0.25+0=1.25$. Class B: $w_2+w_3=0.95+0.75=1.70$. Plain majority: A $=3$, B $=2$ ⇒ A. Weighted ⇒ B.
• Final answer: Plain → A; weighted → B.
• Key lesson: Close neighbours (B,B) outweigh far ones (A,A).

Example 5 — Very Hard

• 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.
• Key lesson: The weighting depends on relative distances; outliers 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.
• 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$.

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. Does not consider the quality of the voting neighbours (open problem noted in the lecture).

Worked examples

Example 1 — Very Easy

• Problem: Show TkNN with $\beta =1$ equals 1-NN.
• Asked: Proof.
• Concept: Margin definition.
• Approach: Start at $L=1$.
• Solution: At $L=\beta =1$: 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

• 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 margin.
• Solution: $\beta =1$: $L=1$: counts $(1,0)$ margin $1=\beta$ ⇒ $y_1$. $\beta =2$: $L=2$: $(1,1)$ margin $0$; $L=3$: $(2,1)$ margin $1$; $L=4$: $(2,2)$ margin $0$; $L=5$: $(2,3)$ margin $1$; $L=6$: $(3,3)$ margin $0$; $L=7$: $(4,3)$ margin $1$; $L=8$: $(4,4)$ margin $0$; $L=9$: $(5,4)$ margin $1$. Never reaches $2$; $L=10>n$ ⇒ unclassified.
• Final answer: $\beta =1\to y_1$; $\beta =2\to$ unclassified.
• Key lesson: The lecture’s remark “for $\beta \ge 2$ cannot classify” is verified; an alternating sequence never builds a margin.

Example 3 — Moderate

• 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$: $y_2:2,y_1:1$ margin 1. $L=4$: $y_2:3,y_1:1$ margin $2=\beta$ ⇒ stop.
• Final answer: $y_2$ with $L=4$.
• Key lesson: Effective $k$ depends on the query.

Example 4 — Hard

• 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)$, $L_{max1}=1,L_{max2}=1$, 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$.
• Key lesson: The margin is against the second best class, not the average of the others.

Example 5 — Very Hard

• 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, so $L_{max1}$ and $L_{max2}$ each change by at most $1$ and $M$ changes by at most $1$ in absolute value. Hence $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.