Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|improve this question
up vote 3 down vote accepted

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:

enter image description here

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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