Lazy Learners and K-Nearest Neighbour Classification

Definition. A lazy learner (instance-based learner) performs no, or almost no, generalisation during training: training only stores the labelled instances, and all computation is deferred until a prediction is requested. KNN is the standard example.

1. Lazy vs eager learners

Aspect	Lazy learner (KNN)	Eager learner (decision tree, neural net)
Training phase	Stores the data only; very fast	Builds an explicit model; slower
Prediction phase	Expensive: queries the whole training set	Cheap: one traversal of the model
Model built	None, the data is the model	Explicit rules, nodes or weights
Incremental data	Added instantly, no retraining	Usually requires rebuilding
Interpretability	Low unless $K$ is tiny	Generally higher
Main weakness	Irrelevant features and feature scale	Rigid model assumptions

Lazy learners adapt naturally to the local shape of the decision boundary but pay for it at query time; eager learners summarise the data, which is faster to use but may miss local detail.

2. KNN algorithm for classification

1. Choose the number of neighbours $K$ (an odd value avoids ties in two-class problems) and a distance metric, Euclidean by default.
2. Standardise or normalise the features so that one attribute does not dominate the distance.
3. For a new instance $x$, compute the distance $d(x, x_i)$ to every training instance.
4. Select the $K$ instances with the smallest distances.
5. Vote: assign the majority class; in weighted voting each neighbour contributes $1/d$ or $1/d^2$.

$$\hat{y} = \arg\max_c \sum_{i \in N_K(x)} w_i \, \mathbb{1}[y_i = c], \qquad w_i = \frac{1}{d(x, x_i)}$$

3. Worked mini-example

Training point	$x_1$	$x_2$	Class
A	1	2	+
B	2	3	+
C	3	1	-
D	6	5	-
E	7	6	-

Classify $T = (5, 4)$ with $K = 3$:

Point	Distance to T
D	$\sqrt{1^2+1^2} = 1.41$
E	$\sqrt{2^2+2^2} = 2.83$
B	$\sqrt{3^2+1^2} = 3.16$
C	$\sqrt{2^2+3^2} = 3.61$
A	$\sqrt{4^2+2^2} = 4.47$

The nearest three are D (-), E (-) and B (+); the majority class is -, so $T$ is classified as -.

4. Practical remarks

• Small $K$ gives a jagged, high-variance boundary (with $K = 1$ there is zero training error but overfitting); large $K$ smooths the boundary and can wash out small clusters.
• KNN is non-parametric, handles multiple classes naturally and needs essentially no training time.
• Its weaknesses: prediction costs $O(nd)$, the whole data set must be kept in memory, and accuracy degrades as dimensionality grows (curse of dimensionality).
• Acceleration structures include KD-trees, ball trees and approximate nearest-neighbour search; distance-weighted voting limits the damage done by distant neighbours.