Non-Parametric Methods Like K-Nearest-Neighbours in High Dimensional Feature Space

The main idea of k-Nearest-Neighbour takes into account the $k$ nearest points and decides the classification of the data by majority vote. If so, then it should not have problems in higher dimensional data because methods like locality sensitive hashing can efficiently find nearest neighbours.

In addition, feature selection with Bayesian networks can reduce the dimension of data and make learning easier.

However, this review paper by John Lafferty in statistical learning points out that non-parametric learning in high dimensional feature spaces is still a challenge and unsolved.

What is going wrong?

• Please give a full reference for the paper; the authors do not seem to appear (prominently) in the it. – Raphael Apr 4 '12 at 5:46

This problem is known as the curse of dimensionality. Basically, as you increase the number of dimensions, $d$, points in the space generally tend to become far from all other points. This makes partitioning the space (such as is necessary for classification or clustering) very difficult.

You can see this for yourself very easily. I generated $50$ random $d$-dimensional points in the unit hypercube at 20 evenly selected values of $d$ from $1..1000$. For each value of $d$ I computed the distance from the first point to all others and took the average of these distances. Plotting this, we can see that average distance is increasing with dimensionality even though the space in which we are generating the points in each dimension remains the same.

Average distance vs. dimensionality

• Of course. You increase the number of points in a hypersphere of fixed radius exponentially in the dimensionalty, so if you choose 50 points uniformly at random this has to happen. Therefore, if your reasoning is correct, partitioning should become easy if I have many samples; is that so? – Raphael Apr 4 '12 at 20:48
• I believe you have it reversed. By increasing dimensionality, I REDUCE the number of points within a hypersphere. Partitioning becomes more difficult because the measure of distance essentially loses its meaning (e.g. everything is far away). – Nick Apr 4 '12 at 20:50
• I meant: The total number of points in a hypersphere of radius $k$ in say $\mathbb{N}^n$, i.e. $|\mathbb{N}^n \cap S_n(k)|$ increases with $n$. – Raphael Apr 4 '12 at 20:52
• Also note that what people mean when they refer to high-dimensional feature space is that the number of samples, $n$, is much less than the dimensionality of each point, $d$, ($n << d$). So in these problems you assume that you do NOT have 'many samples'. – Nick Apr 4 '12 at 20:54
• I don't see that this holds by definition; it seems to be a convention based on experience, though. – Raphael Apr 4 '12 at 20:55