# Does k-NN with k=1 always implies overfitting?

I found somewhere such statement, but on the other hand in some sources I found, that it is ok.

What about risk of overfitting while using 1-NN in binary classification problem where explanatory variables are TF-IDF values (cosine measure)?

-

The short answer to your title question is "No". Consider an example with a binary target variable which is perfectly separated by some value of the single explanatory variable to a large degree:

Clearly 1-NN classification will work very well here and won't overfit. (The fact that there are other methods which will work equally well and may be simpler is irrelevant to the central point.)

TF-IDV values are outside my areas of expertise, but in general, writing loosely, the greater the separation between values of the target value in the space spanned by the explanatory values, the more effective 1-NN classification will be, regardless of the application area.

-

The nice answer of @jbowman is absolutely true, but I miss one point though. It would be more accurate to say that kNN with k=1 in general implies over-fitting, or in most cases leads to over-fitting.

To see why let me refer to this other answer where it is explained WHY kNN gives you an estimate of the conditional probability. When k=1 you estimate your probability based on a single sample: your closest neighbor. This is very sensitive to all sort of distortions like noise, outliers, mislabelling of data, and so on. By using a higher value for k, you tend to be more robust against those distortions.

-

At the risk of stating something obvious to many readers, the one thing you need to be particularly careful about is estimating the classification accuracy of a 1-NN classifier.

For any estimation of classifier accuracy, you need to split the data used to train the classifier (training set) and that used to measure accuracy for the classifier (test set). This is generally done using resampling techniques like cross-validation, bootstrap, etc. If you fail to do so, you will overestimate accuracy. 1-NN is the most extreme example of the problem: If you build a 1-NN classifier and test it on same data set you will get 100% accuracy since (barring ties) the "nearest neighbor" will be the point itself.

Even if you split training and test, this could be an issue if the data you are using are not truly independent (say texts from the same author that end up in both training and test sets) so that the nearest neighbor is closer than it would be if you were sampling properly.

-