Solved – Is it pointless to use Bagging with nearest neighbor classifiers

baggingk nearest neighbour

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.

Best Answer

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, classication 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.

Related Solutions

Solved – k nearest neighbor with decision tree

1) Why will the performance of k-nn change if I change the representation of attribute X to cm instead of m ?

k nearest neighbor classifiers use a distance measure , usually Euclid distance, to decide classification. Suppose you have this data set.

10m 10kg
11m 11kg

 >> sqrt((11-10)^2 + (11-10)^2) 
 ans =
 1.4142

if you change m to cm. you have following data set.

1000cm 10kg
1100cm 11kg

Here your distances changed.

 >> sqrt((1100-1000)^2 + (11-10)^2)
 ans =
 100.0050

If you do not want this behavior, you need to normalize your data.

2) Why will the performance of k-nn and decision tree not change if I multiply all the attributes with 20?

here you scale your data but you scale ALL of them. Since both k-nn and decision trees use distance measures to classify your data, classifications does not change.

Solved – KNN: 1-nearest neighbor

The bias is low, because you fit your model only to the 1-nearest point. This means your model will be really close to your training data.

The variance is high, because optimizing on only 1-nearest point means that the probability that you model the noise in your data is really high. Following your definition above, your model will depend highly on the subset of data points that you choose as training data. If you randomly reshuffle the data points you choose, the model will be dramatically different in each iteration. So

expected divergence of the estimated prediction function from its average value (i.e. how dependent the classifier is on the random sampling made in the training set)

will be high, because each time your model will be different.

Example In general, a k-NN model fits a specific point in the data with the N nearest data points in your training set. For 1-NN this point depends only of 1 single other point. E.g. you want to split your samples into two groups (classification) - red and blue. If you train your model for a certain point p for which the nearest 4 neighbors would be red, blue, blue, blue (ascending by distance to p). Then a 4-NN would classify your point to blue (3 times blue and 1 time red), but your 1-NN model classifies it to red, because red is the nearest point. This means, that your model is really close to your training data and therefore the bias is low. If you compute the RSS between your model and your training data it is close to 0. In contrast to this the variance in your model is high, because your model is extremely sensitive and wiggly. As pointed out above, a random shuffling of your training set would be likely to change your model dramatically. In contrast, 10-NN would be more robust in such cases, but could be to stiff. Which k to choose depends on your data set. This highly depends on the Bias-Variance-Tradeoff, which exactly relates to this problem.

Best Answer

Related Solutions

Solved – k nearest neighbor with decision tree

Solved – KNN: 1-nearest neighbor

Related Question