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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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