Section 1.4.8 of "Machine Learning: A Probabilistic Perspective by Kevin Patrick Murphy" gives this figure (Figure 1.21(a)) to illustrate the error rate of a KNN classifier for different values of k:
And gives the following explanation:
We see that increasing K increases our error rate on the training set, because we are over-smoothing. As we said above, we can get minimal error on the training set by using K = 1, since this model is just memorizing the data.
However, what we care about is generalization error, which is the expected value of the misclassification rate when averaged over future data (see Section 6.3 for details). This can be approximated by computing the misclassification rate on a large independent test set, not used during model training. We plot the test error vs K in Figure 1.21(a) in solid red (upper curve). Now we see a U-shaped curve: for complex models (small K), the method overfits, and for simple models (big K), the method underfits.
Why small K generates more complex models?