Introducing the k-nearest neighbors algorithm
This section deals with a classification algorithm that is very easy to understand intuitively through an example. Consider the cloud in Figure 3.11 that contains three types of smiley faces – happy, sad, and neutral. There is also a hidden face depicted by a question mark. If you had to guess what its actual type was, what would that be?
Figure 3.11 – A cloud with happy, sad, and neutral smiley faces
Most probably, it’s a happy face. Right? The implicit assumption is that one needs to examine the neighborhood to identify the hidden type. As more happy faces are nearby, we can reasonably argue that the face shows a happy one.
This line of thought is precisely the intuition behind the k-nearest neighbors (KNN) algorithm. KNN is a non-parametric and lazy learning method that stores the position of all data samples and classifies new cases based on some similarity measure. Lazy learning means...