Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

kNN in high dimensional spaces

English · فارسی

kNN in high dimensional spaces

The curse of dimensionality

Computer Science Dept, Ferdowsi University of Mashhad

No artists with labels found to put in legend.  Note that artists whose label start with an underscore are ignored when legend() is called with no argument.
<Figure size 640x480 with 1 Axes>
<Figure size 640x480 with 1 Axes>

Exercises

  1. For n=1000n=1000 points uniform in [0,1]d[0,1]^d, measure the ratio between the distance to the 10th neighbour and to the 1st, for d=2,…,200d=2,\dots,200. Plot it and explain why the curve flattens.

  2. Show that the fraction of the volume of a unit ball lying outside radius 1−ε1-\varepsilon is 1−(1−ε)d1-(1-\varepsilon)^d, and evaluate it for d=100d=100 and ε=0.1\varepsilon=0.1.

  3. Why does a fixed fraction of the ball require nn to grow exponentially in the dimension? Relate the answer to the kNN error curves of the notebook.