# Why is N/k the effective number of parameters in k-NN?

For the sake of completeness, $k$-nearest neighbor method classifies a point in space by comparing the average over the labels of $k$ nearest neighbors with $0.5$.

The book Elements of Statistical Learning states [removed irrelevant text]$-$

It appears that the $k$-nearest-neighbor fits have a single parameter, the number of neighbors $k$. The effective number of parameters of $k$-nearest neighbors is $N/k$ and decreases with increasing $k$. To get an idea of why, note that if the neighborhoods were nonoverlapping, there would be $N/k$ neighborhoods and we would fit one parameter (a mean) in each neighborhood.

By fixing $k=k'$, every point in space has a fixed classification. There is no more parameter to learn. Similar argument follows that for each nonoverlapping neighborhoods, the mean is fixed.

So how are there $N/k$ parameters?

To answer that, you need to ask yourself what a model is. For example, a simple univariate linear model $$y = \beta_0 + \beta_1 x$$, where you have 2 parameters $$\beta_0, \beta_1$$ and input data $$x$$. You can predict values by introducing new data into $$x$$ and exploiting the knowledge which consists of the linear relation and 2 parameters. No other knowledge is needed to predict, so it is fine to say that the parameters of the linear model are 2. No training data values are included into parameters, they are sublimated into the regression model parameters.

Now considering k nearest neighbor. Which is the model? You have something like the class index of maximum count from neighbor of input x. Now going on, if we further assume that the regions do not overlap (which is somehow a strong assumption, but does not affect the main idea), then you can conclude that in general you will have $$n/k$$ regions, and in each region you predict with a max count of the target variable. This max count is what is used for prediction, no other information is required. Your model (considering non overlapping regions) is something like $$y = \sum_{r=1}^{n/k} argmax_k (count(y_j)) 1_{j \in region_r}$$, where $$1$$ is indicator function equals with $$1$$ if $$j \in region_r$$, $$0$$ otherwise.

From that formalization, you can see that for each region you have a parameter which is fitted as $$argmax_k$$ so you can say that you have $$n/k$$ parameters, since those only are used for prediction (other that input $$x$$ which is not a parameter).

This can go further to an extreme case, for example consider $$k=n$$. In this case, we have a single region, for that region we fit a single parameter as the argmax index of the majority category.

The assumption for non overlapping regions looks rather strong, but it is used in order to simplify the calculus a lot.

• what do you mean by a 'region' exactly? Is it it the subspace of the input space whose nearest neighbours are a particular set of k training points as opposed to a different set of k training points? Dec 3, 2022 at 22:26
• By 'regions not overlapping' do you mean that no point x in the input space has more than one possible distinct set of k nearest neighbours? Dec 3, 2022 at 22:32

Remember that 'parameter' is different in statistics; instead of merely an argument to a function, a parameter is a value that describes a population.

• It doesn't answer the question and it's hard to get what you are trying to say be this.
– Tim
Sep 8, 2022 at 19:25
• The question is misinformed. KNN produces estimates with one function argument or hyper-parameter (nothing to learn as OP states) not a parameter. Parameters are learned. To extend the concept of parameters and degrees of freedom, Jianming Ye 1998 developed an equation mentioned elsewhere, see Eq 10 in jstor.org/stable/2669609 that can be applied to kNN and reduced to N/k. The excerpted text hints at why N/k 'effective' parameters are in play. The notion offered is that with non-overlapping regions, N/k regions are overlaid on supposed N/k populations. Sep 17, 2022 at 23:50
• If it depends on full dataset then dataset is also a parameter. So it seems to me that naive KNN has practically nxd parameters. Jul 18, 2023 at 1:43

Hastie's other works (Generalized Linear Models book and Effective Degrees of Freedom paper) are more precise on the issue of "effective number parameters" aka "effective degrees of freedom."

The idea is that for linear parametric methods, the number of parameters is proportional to the expected gap between train and test error. Take the noise-scale-independent component of this quantity and call the result "effective parameters". This lets you "count parameters" even when there are no parameters to speak of. This view also explains why "effective number of parameters" of ridge regression depends on the value of $$\lambda$$

Relevant part from the Effective Degrees of Freedom (DF) paper:

I haven't seen the derivation of "DF" quantity for the nearest neighbor classifier, showing that DF is equal to $$N/k$$ for the case of nearest neighbor would answer the question.

There's a related result for "running mean smoother of $$k$$ observations" in Hastie's "Generalized Linear Models" book, section 3.3, showing that the number of effective parameters is $$O(1/k)$$