11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please give a full reference for the paper; the authors do not seem to appear (prominently) in the it. $\endgroup$
    – Raphael ♦
    Apr 4, 2012 at 5:46

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Raphael ♦
    Apr 4, 2012 at 20:48
  • $\begingroup$ 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). $\endgroup$
    – Nick
    Apr 4, 2012 at 20:50
  • $\begingroup$ 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$. $\endgroup$
    – Raphael ♦
    Apr 4, 2012 at 20:52
  • $\begingroup$ 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'. $\endgroup$
    – Nick
    Apr 4, 2012 at 20:54
  • $\begingroup$ I don't see that this holds by definition; it seems to be a convention based on experience, though. $\endgroup$
    – Raphael ♦
    Apr 4, 2012 at 20:55
3
$\begingroup$

Not a complete answer, but the wikipedia page you cited states:

The accuracy of the k-NN algorithm can be severely degraded by the presence of noisy or irrelevant features, or if the feature scales are not consistent with their importance.

The likelihood of this occurring increases in the presence of high dimensional feature spaces.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But I think with PCA(principle component analysis) or any other methods to reduce dimensionality and remove irrelevant data, k-NN can still work. And what the wikipedia pages mean is the naive k-NN will fail. So this doesn't explain the review paper. $\endgroup$
    – Strin
    Apr 5, 2012 at 1:46
  • $\begingroup$ PCA can certainly work, but not in all situations. $\endgroup$
    – Dave Clarke
    Apr 5, 2012 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.