I'm having trouble understanding the curse of dimensionality. Specifically, I came across it while doing the
scikit-learn tutorial in python. Can someone please explain the below in a simpler manner? Sorry I have been trying to understand for the longest time and can't understand how they came up with the calculation for number of training examples to achieve an efficient KNN estimator?
Here is the explanation:
For an estimator to be effective, you need the distance between neighboring points to be less than some value d, which depends on the problem. In one dimension, this requires on average n ~ 1/d points. In the context of the above KNN example, if the data is described by just one feature with values ranging from 0 to 1 and with n training observations, then new data will be no further away than 1/n. Therefore, the nearest neighbor decision rule will be efficient as soon as 1/n is small compared to the scale of between-class feature variations.
If the number of features is p, you now require n ~ 1/d^p points. Let’s say that we require 10 points in one dimension: Now 10^p points are required in p dimensions to pave the [0, 1] space. As p becomes large, the number of training points required for a good estimator grows exponentially.
EDIT: also is the tilde (
~) supposed to represent approximate in that example? or the python tilde operator?