I want to understand what exactly is curse of dimensionality and how does it effect the model performance. Does the the concept apply to all the models?. Is it equally bad for distance based models like KNN and tree based models like random forest?

Curse of Dimensionality:

"Consider applying a KNN classifier to data where the inputs are uniformly distributed in the D-dimensional unit cube. Suppose we estimate the density of class labels around a test point x by growing” a hyper-cube around x until it contains a desired fraction f of the data points. The expected edge length of this cube will be eD(f) = f1/D. If D = 10, and we want to base our estimate on 10% of the data, we have e10(0.1) = 0.8, so we need to extend the cube 80% along each dimension around x. Even if we only use 1% of the data, we find e10(0.01) = 0.63. Since the entire range of the data is only 1 along each dimension, we see that the method is no longer very local, despite the name “nearest neighbor”. The trouble with looking at neighbors that are so far away is that they may not be good predictors about the behavior of the input-output function at a given point."

This is the explanation of curse of dimensionality in the Machine learning book by Kevin P. Murphy. However, I only partially understand the concept. Can someone explain it in detail? Thanks in advance!

  • $\begingroup$ Could you tell us what the "dimensionality" of a "distance-based model" might be? The latter sounds like a model for data that are given as distances between pairs of objects and as such doesn't require any more than three columns of data (two ids and a distance). Apart from $3,$ no other dimension seems to be in evidence or possible of attaining a large value. $\endgroup$ – whuber Aug 7 '20 at 13:25