Instance-Based Classifiers

How an instance-based classifier works

Instance-based (lazy) classifiers do not build an explicit global model (such as a decision tree or a weight vector) during a separate training phase. Instead they store the training tuples and, at classification time, compare a new tuple with those stored tuples by a similarity/distance measure, then assign it a class based on the local neighbourhood of the most similar stored instances.

k-Nearest Neighbour (k-NN) is the classic algorithm:

1. Given a new, unseen query tuple $x_q$, compute its distance (usually Euclidean) to every stored training tuple.
2. Select the $k$ closest tuples; $k$ is typically an odd number (to avoid ties) chosen empirically by cross-validation.
3. Assign $x_q$ to the class held by the majority of these $k$ nearest neighbours.

      Training set (stored)          New tuple
      (features, class)                │
              │  distance
              ▼
          select k nearest neighbours
              │  majority vote
              ▼
           predicted class

Nearest-neighbour classifiers may also use weighted voting (nearer neighbours vote more heavily).

Two instance-based classifiers:

1. k-Nearest Neighbours (k-NN) — lazy, non-parametric, the workhorse of instance-based classification.
2. Case-based reasoning (CBR) — stores previously solved cases (problem–solution pairs); a new problem is solved by retrieving the most similar stored case(s) and adapting their solutions.
3. Rote classifier — pure lookup: a new tuple is classified only if there is an exactly matching stored tuple (no generalisation at all; fragile when no exact match exists).

(For the exam, k-NN and case-based reasoning are the two commonly named.)