How to solve this problem on Curse of Dimensionality problem - Nearest Neighbours

Question

I have started learning classification techniques and trying to solve the problems from the book Introduction to Statistical Learning.

While currently working on the which is based on Curse of dimensionality and how Nearest neighbours averaging tends to perform poorly when the dimensions become large. The first part of the problem is below and similarly I have to find for p = 2, p= 100:

(a) Suppose that we have a set of observations, each with measurements on p = 1 feature, X. We assume that X is uniformly (evenly) distributed on [0, 1]. Associated with each observation is a response value. Suppose that we wish to predict a test observation’s response using only observations that are within 10% of the range of X closest to that test observation. For instance, in order to predict the response for a test observation with X = 0.6, we will use observations in the range [0.55, 0.65]. On average, what fraction of the available observations will we use to make the prediction?

After reading scikit The way I have approached this problem is : Assume that 100 observations are given and p = 1 , d = 10% , we require 1/d^p points. So for p = 1 , its 10/100 For p = 2, its 1/(0.1)^2

But I am not sure if that is correct.Can someone guide me ?

Answer 1

Your approach is to look at the hypercube of side $0.1$ and as you say the hypervolume is $0.1^n$, which for $n=1$ is $0.1$, for $n=2$ is $0.01$ and for $n=3$ is $0.001$. This is enough to make the point that the "near" data is an increasingly smaller proportion as the dimension increases.

Strictly speaking the position is even worse than that. You might instead look at the hypersphere of radius $0.05$: its hypervolume is a little more complicated, but for $n=1$ it is $2r=0.1$; for $n=2$ is is $\pi r^2 \approx 0.007854$; for $n=3$ it is $\frac43 \pi r^3 \approx 0.0005236$ and you can see that the hypersphere is a decreasing proportion even of the diminishing hypercube.

For $n=100$ the hypervolume of the hypercube is $10^{-100}$. The hypervolume of the hypersphere is $\frac{\pi^{50}}{50!}r^{100} \approx 1.8 \times 10^{-170}$ which really is a ridiculously small proportion: it is extremely unlikely that there will be any points within the hypersphere.

There is an argument which could make the hypersphere bigger: the longest diagonal of the unit hypercube is $\sqrt{n}$ so perhaps we should multiply the radius of the hypersphere by this. So for $n=100$ we would have $r=0.5$ which might suggest having a hypervolume about $1.8 \times 10^{-70}$, though the proportion inside the original unit hypercube would in fact be less as part of the small hypersphere would extend outside the original unit hypercube.

So whichever way you look at it, very high dimensions reduce the amount which is "near" to be an extremely small proportion of the data.