3.1. Арбуз или почему всё ломается

Задача этого модуля - разбить трёхмерную интуицию, показав что в больших размерностях всё работает иначе
Данные часто живут в больших размерностях и понимать изменение геометрии 

Рассмотрим круг
Во сколько раз уменьшится площадь круга, если уменьшить радиус на 1%?
Ну вроде со школы мы знаем, что площадь изменяется как квадрат радиуса
У нас осталось 0.99 от радиуса
Получается, что от площади осталось: $0.99^2 = 0.9801$
То есть, площадь уменьшится примерно на 2 процента

А если тоже самое сделать с трёхмерной сферой?
Её объём уже меняется как куб радиуса
Получается, что от объёма останется: $0.99^3 \approx 0.9703$

Не сложно понять получающуюся формулу остающегося объёма:
$(R - \epsilon)^d$, где d - размерность пространства

А что будет, если у нас стомерное пространство?
Посчитаем:
$0.99^{100} \approx 0.366$
Получается, мы потеряем практически две трети объёма, уменьшив радиус всего на единицу

А если тысячемерное?
$0.99^{1000} \approx 0.00004$
Отняв всего 1% от радиуса сферы мы уменьшили объём в 25 тысяч раз!
Настолько необычно работает объём в многомерных пространствах

Что это означает для данных?

Первый вывод - в многомерных пространствах, если данные ограниченны сферой, то практически все данные будут находиться практически на границе этой сферы
И с увеличением размерности этот эффект только усиливается

Это приводит к немалой части проблем
Например, расстояния почти всех точек друг от друга становятся практически одинаковыми
Точки как бы раскиданы по условному краю многомерной сферы и разница между близкими и далёкими точками по обычной евклидовой норме ничтожна

Поэтому, алгоритмы строящиеся на сравнении расстояний могут сломаться
Тот же k-means будет скорее выдавать бред и шум путать с реальной разницей в данных

На практике в таких ситуациях используют косинусное сходство или другие более устойчивые к таким эффектам варианты измерений

Теперь рассмотрим не шары, а кубы

Будем рассматривать их со сторонами равной 1 в центре, то есть, от -0.5 до 0.5 по каждой из координат
Сначала посмотрим на квадрат
Расстояние от начала координат до ребра квадрата равно 0.5
Но при этом, расстояние от начала координат до угла квадрата равно уже
 $\sqrt{0.5^2 + 0.5^2} = \sqrt{0.5} \approx 0.7 > 0.5$

Проделаем аналогичные действия для трёхмерного куба
Расстояние до его грани всё ещё 0.5, а вот до угла уже:
$\sqrt{3 * 0.5^2} \approx 0.87$

Для четырёхмерного куба расстояние до грани будет 0.5, а до угла 1
То есть, с увеличением размерности расстояние до грани не меняется, а до угла куба растёт со скоростью $\sqrt n$

Если сложить этот факт с первым выводом про шары, то выходит, что куб в больших размерностях больше похож на ежа с кучей длинных иголок (где у него находится почти весь объём), чем на привычный куб

Проблем для данных из этого всего следует много, но главная - пустота центра
Уже в размерности 20 (что очень мало для данных) если вписать шар в куб, то он займёт только 
$2.46 * 10^{-8}$ от объёма всего куба
Это примерно вообще нисколько и, скорее всего, ни одна точка из данных в этот шар не попадёт

Главное, что нужно вынести из этого урока - при работе с большими размерностями нужно каждый раз задумываться о том, как алгоритмы в них будут работать, классическая 3d интуиция практически всегда даёт сбои

Другой вариант частичного решения проблемы - уменьшение размерности
Об этом следующий урок

Представьте, что у вас есть 100-мерный шар радиуса 1. Вы уменьшаете его радиус на 5% (новый радиус = 0.95). Во сколько раз уменьшится его объём?
(Подсказка: объём пропорционален R^d, где d — размерность.)

Какие алгоритмы ломаются в больших размерностях?