Я читаю книгу Кевина Мерфи: Машинное обучение - вероятностная перспектива. В первой главе автор объясняет проклятие размерности, и есть часть, которую я не понимаю. В качестве примера автор заявляет:
Рассмотрим входы, равномерно распределенные по D-мерному единичному кубу. Предположим, что мы оцениваем плотность меток классов, выращивая гиперкуб вокруг x, пока он не будет содержать искомую дробь точек данных. Ожидаемая длина ребра этого куба составляет .
Это последняя формула, которую я не могу понять. кажется, что если вы хотите покрыть, скажем, 10% точек, то длина ребра должна быть 0,1 по каждому измерению? Я знаю, что мои рассуждения неверны, но я не могу понять, почему.
Ответы:
Это именно неожиданное поведение расстояний в больших измерениях. Для 1 измерения у вас есть интервал [0, 1]. 10% точек находятся в отрезке длиной 0,1. Но что происходит, когда увеличивается размерность пространства признаков?
Это выражение говорит вам, что если вы хотите получить эти 10% точек для 5 измерений, вам нужно иметь длину для куба 0,63, в 10 измерениях 0,79 и 0,98 для 100 измерений.
Как видите, для увеличения размеров вам нужно смотреть дальше, чтобы получить одинаковое количество очков. Более того, говорит вам, что большинство точек находятся на границе куба с увеличением числа измерений. Что неожиданно.
источник
Я думаю, что главное заметить, что выражение
Чтобы сделать это еще более ясным, вспомним сюжет, который показывает Мерфи:
источник
Да, так что если у вас есть единичный куб или, в вашем случае, единичная строка, и данные распределены равномерно, то вам нужно увеличить длину на 0,1, чтобы собрать 10% данных. Теперь, когда вы увеличиваете размеры, D увеличивается, что уменьшает мощность, а f, составляющая менее 1, будет увеличиваться, так что если D уходит в бесконечность, вам нужно захватить весь куб, e = 1.
источник
Я думаю, что для КНН расстояние играет большую роль. То, что происходит с (гипер) кубом, аналогично тому, что происходит с расстоянием между точками. По мере увеличения количества измерений отношение между ближайшим расстоянием и средним расстоянием увеличивается - это означает, что ближайшая точка находится почти на таком же расстоянии, что и средняя точка, тогда она обладает лишь немного большей предсказательной силой, чем средняя точка. Эта статья объясняет это красиво
источник