Проклятие размерности: классификатор кНН

11

Я читаю книгу Кевина Мерфи: Машинное обучение - вероятностная перспектива. В первой главе автор объясняет проклятие размерности, и есть часть, которую я не понимаю. В качестве примера автор заявляет:

Рассмотрим входы, равномерно распределенные по D-мерному единичному кубу. Предположим, что мы оцениваем плотность меток классов, выращивая гиперкуб вокруг x, пока он не будет содержать искомую дробьf точек данных. Ожидаемая длина ребра этого куба составляет .eD(f)=f1D

Это последняя формула, которую я не могу понять. кажется, что если вы хотите покрыть, скажем, 10% точек, то длина ребра должна быть 0,1 по каждому измерению? Я знаю, что мои рассуждения неверны, но я не могу понять, почему.

user42140
источник
6
Попробуйте сначала изобразить ситуацию в двух измерениях. Если у меня есть лист бумаги размером 1 м * 1 м, и я вырезал квадрат 0,1 м * 0,1 м из левого нижнего угла, я удалил не одну десятую, а только одну сотую .
Дэвид Чжан

Ответы:

13

Это именно неожиданное поведение расстояний в больших измерениях. Для 1 измерения у вас есть интервал [0, 1]. 10% точек находятся в отрезке длиной 0,1. Но что происходит, когда увеличивается размерность пространства признаков?

Это выражение говорит вам, что если вы хотите получить эти 10% точек для 5 измерений, вам нужно иметь длину для куба 0,63, в 10 измерениях 0,79 и 0,98 для 100 измерений.

Как видите, для увеличения размеров вам нужно смотреть дальше, чтобы получить одинаковое количество очков. Более того, говорит вам, что большинство точек находятся на границе куба с увеличением числа измерений. Что неожиданно.

jpmuc
источник
4

Я думаю, что главное заметить, что выражение

еD(е)знак равное1D

D

Чтобы сделать это еще более ясным, вспомним сюжет, который показывает Мерфи:

введите описание изображения здесь

D>1еD(е)

еD'(е)знак равно1Dе1D-1знак равно1Dе1-DD

D>11-D<0

еD'(е)знак равно1D(е1-D)1D

еИкс-1знак равно1Иксе<1КNDD

е1-D1D

Чарли Паркер
источник
2

Да, так что если у вас есть единичный куб или, в вашем случае, единичная строка, и данные распределены равномерно, то вам нужно увеличить длину на 0,1, чтобы собрать 10% данных. Теперь, когда вы увеличиваете размеры, D увеличивается, что уменьшает мощность, а f, составляющая менее 1, будет увеличиваться, так что если D уходит в бесконечность, вам нужно захватить весь куб, e = 1.

plumSemPy
источник
0

Я думаю, что для КНН расстояние играет большую роль. То, что происходит с (гипер) кубом, аналогично тому, что происходит с расстоянием между точками. По мере увеличения количества измерений отношение между ближайшим расстоянием и средним расстоянием увеличивается - это означает, что ближайшая точка находится почти на таком же расстоянии, что и средняя точка, тогда она обладает лишь немного большей предсказательной силой, чем средняя точка. Эта статья объясняет это красиво

Джоэл Грус хорошо описывает эту проблему в Data Science с нуля. В этой книге он вычисляет среднее и минимальное расстояния между двумя точками в пространстве измерений по мере увеличения числа измерений. Он рассчитал 10000 расстояний между точками с количеством измерений в диапазоне от 0 до 100. Затем он приступает к построению графика среднего и минимального расстояния между двумя точками, а также отношения ближайшего расстояния к среднему расстоянию (Distance_Closest / Distance_Average) ,

На этих графиках Джоэл показал, что отношение ближайшего расстояния к среднему расстоянию увеличилось с 0 в 0 измерениях до ~ 0,8 в 100 измерениях. И это показывает фундаментальную проблему размерности при использовании алгоритма k-ближайших соседей; с увеличением числа измерений и приближением отношения ближайшего к среднему расстоянию 1 предсказательная сила алгоритма уменьшается. Если ближайшая точка находится почти так же далеко, как средняя точка, то она обладает лишь немного большей предсказательной силой, чем средняя точка.

Давид Рафаэли
источник