Why is Nearest Neighbor a Lazy Algorithm?

Classification algorithms based on nearest neigbhours methods are considered lazy learning algorithms because technically speaking no abstraction occurs.

Although, Nearest neighbor algorithms, for instance, the K-Nearest Neighbors (K-NN) for classification, are very “simple” algorithms, that’s not why they are called lazy. K-NN is a lazy learner because it doesn’t learn a discriminative function from the training data but “memorizes” the training dataset instead.

Under the strict definition of learning, a lazy learner is not really learning anything.Instead, it merely stores the training data verbatim. This allows the training phase,which is not actually training anything, to occur very rapidly. Of course, the downside is that the process of making predictions tends to be relatively slow in comparison to training. Due to the heavy reliance on the training instances rather than an abstracted model, lazy learning is also known as instance-based learning or rote learning.

For example, the logistic regression algorithm learns its model weights (parameters) during training time. In contrast, there is no training time in K-NN. Although this may sound very convenient, this property doesn’t come without a cost: The “prediction” step in K-NN is relatively expensive! Each time we want to make a prediction, K-NN is searching for the nearest neighbor(s) in the entire training set! 

To summarize: An eager learner has a model fitting or training step. A lazy learner does not have a training phase.