ESLII states that

effective number of parameters in K nearest neighbor is inversely proportional to K. To get an idea why, note that if the neighborhood were not overlapping, there would be N/K neighborhoods and we would fit one parameter ( a mean) in each neighborhood.

My question :- what does it really mean when it states that we would fit one parameter in each neighborhood? How does it( fitting one parameter per neighborhood) really work?

Any intuitive example will be appreciated, thank you!


1 Answer 1


At first glance, k-nearest neighbors has a single parameter, that is k, the number of neighbours to be included in deciding on the majority-vote predicted classification.

However, the effective number of parameters to be fit is not really k but more like n/k. This is because the approach effectively divides the region spanned by the training set into approximately n/k parts and where each part is governed by the majority vote classifier.

To form an analogy with a parameterised model (e.g. GLM) if you have a dataset of size n 50, a choice of k=25 for kNN results in an effec­tive number of parameters of about 2 and is comparable in the extent of smoothing / degree of freedom to a linear regression fit with two coefficients.

P.S. For kNN, the effective number of parameters / the degree of complexity is known as Vapnik–Chervonenkis (VC) dimension.

  • 1
    $\begingroup$ This it not really an answer, you are basically repeating what is already said in ESLII a little bit more verbose. $\endgroup$
    – newandlost
    Commented Aug 9, 2022 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.