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

Шаг 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 тысяч раз!

Настолько необычно работает объём в многомерных пространствах

Шаг 2

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

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

И с увеличением размерности этот эффект только усиливается

Это приводит к немалой части проблем

Например, расстояния почти всех точек друг от друга становятся практически одинаковыми

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

Поэтому, алгоритмы строящиеся на сравнении расстояний могут сломаться

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

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

Шаг 3

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

Будем рассматривать их со сторонами равной 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$

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

Шаг 4

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

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

$2.46 * 10^{-8}$ от объёма всего куба

Это примерно вообще нисколько и, скорее всего, ни одна точка из данных в этот шар не попадёт

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

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

Об этом следующий урок