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

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 ?

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.

• But if I have to numerically find the fraction of observations that were used for prediction, when number of features = 1 or 2 or 100 , should I use the hypervolume of hypersphere? – Deeksha Sharma Nov 2 '14 at 0:09
• If you are using a Euclidean metric then it would be the hypersphere. – Henry Nov 2 '14 at 8:56
• Not arguing on the technical content of your answer, but like dude, what's with all the hyper business? You're like hyper to the hypermax, like you know? Even in infinite dimensions, a sphere is a sphere, etc. And God, volume is volume not HYPERvolume. Why radius and not hyperradius? Why not hyperdiagonal? Isn't an argument about a hypershere really a hyperargument? – Mark L. Stone Jul 13 '15 at 23:55
• @MarkL.Stone: Call a hypersphere an $n$-sphere if you prefer. For me volume is 3-dimensional while hypervolume is the measure at the highest dimension being considered. – Henry Jul 14 '15 at 9:18