Why is Nearest Neighbor a Lazy Algorithm?
Classic MLLevel: IntermediateML concepts — Sebastian Raschka FAQ
Why is Nearest Neighbor a Lazy Algorithm?
Hints
- State the task, inputs and prediction target.
- Compare with a simple baseline: assumptions, objective and independent validation.
Answer
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.
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! (Note that there are certain tricks such as BallTrees and KDtrees to speed this up a bit.)
To summarize: An eager learner has a model fitting or training step. A lazy learner does not have a training phase.
Source and licence: Sebastian Raschka — Python Machine Learning FAQ · MIT