Rote-learner and K-nearest neighbor

Rote learner

A rote learner memorises the entire training data and classifies a test record only if its attributes exactly match a training record, using that record's class. It cannot classify a record without an exact match, so it is very restrictive. K-nearest neighbour relaxes this to "similar enough".

K-Nearest Neighbour (KNN) classifier

KNN is a lazy, instance-based classifier: it stores the training data and builds no model. A record is classified by its K closest training records (the neighbours).

Steps:

1. Choose K and a distance measure (Euclidean: d(x, y) = √Σ(xᵢ − yᵢ)²). Normalise attributes.
2. Compute the distance from the unknown record to all training records.
3. Select the K nearest neighbours.
4. Assign the majority class among them (or weighted vote with weight 1/d²).

Example

Training: A(1, 1) Red, B(1, 2) Red, C(5, 5) Blue, D(6, 5) Blue, E(5, 6) Blue. New record X = (2, 2), K = 3.

The 3 nearest are B, A, C = Red, Red, Blue. X is classified as Red.

Issues in choosing K

• K too small (e.g. 1): sensitive to noise and outliers; overfitting.
• K too large: includes points from other classes; the neighbourhood is no longer local; underfitting. If K = n, the majority class is always predicted.
• Use an odd K for two classes to avoid ties. A common rule is K ≈ √n.
• Choose K by cross-validation on a validation set.
• Use distance-weighted voting to reduce the effect of K.
• Attributes must be scaled, and irrelevant attributes and high dimension should be removed.