7
$\begingroup$

In page 485 of the book [1], it is noted that "it is pointless to bag nearest-neighbor classifiers because their output changes very little if the training data is perturbed by sampling". This is strange to me because I think the KNN method has high variance when $K$ is small (such as for nearest neighbor method where $K$ is equal to one), and that makes it perfect for bagging. What is wrong with this intuition?

[1] Witten, Ian H., et al. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 2016.

$\endgroup$
  • 1
    $\begingroup$ Good question. Have you tried a few simulations? $\endgroup$ – Stephan Kolassa Nov 19 '17 at 14:46
  • 2
    $\begingroup$ @StephanKolassa Not yet. But I think it is typical to use bagging with KNN since there are some papers for it such as jmlr.org/papers/volume11/biau10a/biau10a.pdf $\endgroup$ – Hossein Nov 19 '17 at 14:57
6
$\begingroup$

In the original paper about bagging, Breiman refers to this point. He explains that unstable learners are likely to give different prediction for modified datasets and likely to benefit from bagging. On the other hand, stable learners (take to the extreme a constant), will give quite similar predictions anyway so bagging won't help.

He also refer to specific algorithms stability:

Unstability was studied in Breiman [1994] where it was pointed out that neural nets, classi cation and regression trees, and subset selection in linear regression were unstable,while k-nearest neighbor methods were stable.

Breiman [1994] is "Breiman,L.(1994)Heuristics of instability in model selection,Technical Report, Statistics Department, University of California at Berkeley."

I think the Breiman extended the technical report into Heuristics of Instability and Stabilization in Model Selection but he hardly refers to knn there.

I your intuition is correct. The lower k the more unstable the model will be. The more we modify the dataset, the higher probability the use a different set of neighbors. If you take k=1 and modify the dataset enough so the probability of getting the same neighbor is less then 80%, bagging should help. I think the the use case Breiman had in mind is a higher k and more delicate modifications. If you have k of 10 and probability of having the same neighbour of 99%, the results will be quite stable.

$\endgroup$
  • $\begingroup$ Thanks for your answer and references. In the Witten's book, the "nearest-neighbor" classifiers are mentioned, which as I know, are the KNN classifiers with K=1. So, it is still not obvious to me why they think 1NN is a stable classifier. $\endgroup$ – Hossein Nov 22 '17 at 3:37
  • $\begingroup$ Being stable is a function of the classifier and the data set. If all items in the same area behave the same 1-nn will be as stable as 10-nn. In the family of k-nn, 1-nn is indeed the least stable. $\endgroup$ – DaL Nov 22 '17 at 7:08
  • $\begingroup$ Yes, and this is exactly my question that why Witten et. al think 1NN is a stable classifier, while in general it is the least stable KNN classifier. $\endgroup$ – Hossein Nov 22 '17 at 17:11
  • $\begingroup$ I guess that they are used to stable data sets but this is a shot in the dark. $\endgroup$ – DaL Nov 23 '17 at 6:59

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.