dm.cs.tu-dortmund.de/mlbits/foundations-curse/
Curse of Dimensionality – Lecture Notes
in \(d\) dimensions \([0;1]^d\) .
How much of the volume is \(\lt{}0.1\) from any side of the box?
core volume = \(0.8^d\) margin volume = \(1 - 0.8^d\)
dimensionality
\(d\)
1
2
3
10
20
100
core volume [...] margin volume
\(1\! -\! 0.8^d\)
0.2
0.36
0.488
0.8926
0.9885
$$1
➜ almost all the data is in the margin
\(3\) -sigma outliers: outermost 0.26% of a normal distribution
dimensionality
\(d\)
1
2
3
10
20
100 [...] Combinatorial Explosion
Assume a grid with 10 partitions on each axis, and \(|N|=10.000.000\) .
in \(d=1\)
dimension,
the grid has \(10\)
cells
in \(d=2\)
dimensions,
the grid has \(100\)
cells
in \(d=10\) …