Визуализация стомерного пространства невероятно сложна для человека. Вдобавок к тому, что это трудно визуализировать, существуют как минимум две дополнительные проблемы с большими размерностями, обе из которых называются проклятием размерности. Один расчетный, другой математический.

С вычислительной точки зрения рассмотрим следующую задачу. Для K ближайших соседей скорость прогнозирования низкая для очень большого набора данных. По крайней мере, вы должны смотреть на каждый обучающий пример каждый раз, когда хотите сделать прогноз. Чтобы ускорить процесс, вы можете создать индексирующую структуру данных. Вы можете разбить плоскость на сетку, как показано на рисунке выше. Теперь, когда приходит контрольная точка, можно быстро определить ячейку сетки, в которой она лежит. Теперь, вместо рассмотрения всехтренировочных точек, вы можете ограничиться тренировочными точками в этой ячейке сетки (и, возможно, в соседних ячейках). Это потенциально может привести к огромной экономии вычислительных ресурсов.

В двух измерениях эта процедура эффективна. Если мы хотим разбить пространство на сетку с ячейками 0,2 × 0,2, мы можем сделать это с 25 ячейками сетки в двух измерениях (предполагая, что диапазон признаков составляет от 0 до 1 для простоты). В трех измерениях нам понадобится 125 = 5×5×5 ячеек сетки. В четырех измерениях нам потребуется 625. К тому времени, когда мы получим «низкомерные» данные в 20 измерениях, нам потребуется 95, 367, 431, 640, 625 ячеек сетки (это 95 триллионов, что примерно равно в 7 раз больше государственного долга США по состоянию на январь 2011 г.). Таким образом, если вы находитесь в 20 измерениях, этот метод построения сетки будет полезен только в том случае, если у вас есть не менее 95 триллионов обучающих примеров. Достаточно сказать, что даже для умеренно высоких размерностей объем вычислений, связанных с этими задачами, огромен.

Рассмотрите возможность применения классификатора/регрессора KNN к данным, где входные данные равномерно распределены в D-мерном единичном кубе. Предположим, мы оцениваем плотность меток классов вокруг контрольной точки x, «выращивая» гиперкуб вокруг x, пока он не будет содержать желаемую долю f точек данных.

Ожидаемая длина ребра этого куба будет e( f) = f **1/D. Если D = 10, и мы хотим основывать нашу оценку на 10% данных, у нас есть e 10(0,1) = 0,8, поэтому нам нужно расширить куб 80 % по каждому измерению в районе x. Даже если мы используем только 1% данных, мы находим e10(0,01) = 0,63. — уже не очень локально.

Способы избежать проклятия размерности

  • Уменьшение размерности: уменьшите размерность данных, чтобы исчезло проклятие размерности.
  • Регуляризация: проблема возникает из-за того, что оценки параметров нестабильны, поэтому регуляризируйте эти оценки, чтобы параметр оценивался правильно.
  • Экономные модели: проблема возникает из-за того, что количество оцениваемых параметров слишком велико, поэтому сделайте ограничительные предположения о модели, чтобы количество оцениваемых параметров стало более «приличным».

Рекомендации

[1] В основном адаптировано из https://web.cs.hacettepe.edu.tr/~erkut/ain311.f22/slides/l3-kernel_regression.pdf

[2] В основном адаптировано из http://ciml.info/dl/v0_99/ciml-v0_99-ch03.pdf