6.2.1. Simple Nearest Neighbor Classifier

The classifier is defined as:

\[\text{classify}(\v x) = y\ls i,\quad\text{where}\quad i = \arg\min_j \|\v x - \v x\ls j\|\]

i.e. we first look for the example \(\v x\ls i\) in the learning set that is closest to the given \(\v x\) and then assign its label \(y\ls i\) to the unknown feature vector \(\v x\).

This very simple classifier is:

• only accurate in case a lot of learning data is available, essentially we need enough data to be able to estimate the class conditional probability density functions.

• only efficient in case the learning set is not too large and the dimensionality of the feature space is not too large either. The first demand is of course contradictory to the requirement for an accurate classifier.

• very prone to overfitting in the case of ‘outliers’ of a class in the feature space region that is more probable for another class.

In the next section we define the k-nearest neighbor classifier as a way to deal with the overfitting problem.