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

редактировать

трудности, возникающие при анализе данных со многими аспектами («измерениями»)

Проклятие размерности относится к различным явлениям, которые возникают при анализе и организации данных в многомерных пространствах, которые не возникают в низкоразмерных средах, таких как трехмерное физическое пространство повседневного опыта. Выражение было придумано Ричардом Э. Беллманом при рассмотрении проблем в динамическом программировании.

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

Содержание

1 Домены
- 1.1 Комбинаторика
- 1.2 Выборка
- 1.3 Оптимизация
- 1.4 Машинное обучение
- 1.5 Функции расстояния
- 1.6 Поиск ближайшего соседа
  - 1.6.1 k -классификация ближайшего соседа
- 1.7 Обнаружение аномалий
- 1.8 Благословение размерности
2 См. также
3 Ссылки

Домены

Комбинаторика

В некоторых задачах каждый переменная может принимать одно из нескольких дискретных значений, либо диапазон возможных значений делится, чтобы дать конечное число возможностей. Взяв переменные вместе, необходимо рассмотреть огромное количество комбинаций значений. Этот эффект также известен как комбинаторный взрыв. Даже в простейшем случае $d {\ displaystyle d}$ $d$ двоичных переменных количество возможных комбинаций уже составляет $2 d {\ displaystyle 2 ^ {d}}$ $2 ^ {d}$ , экспоненциальный по размерности. Наивно, что каждое дополнительное измерение удваивает усилия, необходимые для опробования всех комбинаций.

Выборка

Имеется экспоненциальное увеличение объема, связанное с добавлением дополнительных измерений в математическое пространство. Например, 10 = 100 равномерно разнесенных точек выборки достаточно для выборки единичного интервала («одномерный куб») с не более чем 10 = 0,01 расстоянием между точками; для эквивалентной выборки 10-мерного единичного гиперкуба с решеткой, имеющей интервал 10 = 0,01 между соседними точками, потребуется 10 = [(10)] точек выборки. В общем, с интервалом 10 10-мерный гиперкуб оказывается в 10 = [(10) / (10)] раз больше, чем 1-мерный гиперкуб, который является единичным интервалом. В приведенном выше примере n = 2: при использовании расстояния выборки 0,01 10-мерный гиперкуб оказывается на 10 «больше», чем единичный интервал. Этот эффект представляет собой комбинацию задач комбинаторики, описанных выше, и задач функции расстояния, описанных ниже.

Оптимизация

При решении задач динамической оптимизации числовым методом обратной индукции, целевая функция должна вычисляться для каждой комбинации значений. Это серьезное препятствие, когда размер «переменной состояния» велик.

Машинное обучение

В машинном обучении задачи, которые включают изучение «состояния- природа "из конечного числа выборок данных в многомерном пространстве признаков с каждой характеристикой, имеющей диапазон возможных значений, обычно требуется огромное количество обучающих данных, чтобы гарантировать наличие нескольких выборок с каждым сочетание ценностей. Типичное практическое правило состоит в том, что для каждого измерения в представлении должно быть не менее 5 обучающих примеров. При фиксированном количестве обучающих выборок прогностическая сила классификатора или регрессора сначала увеличивается по мере увеличения числа используемых измерений или функций, но затем уменьшается, что известно как феномен Хьюза или феномен пика.

Функции расстояния

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

Один из способов проиллюстрировать «необъятность» многомерного евклидова пространства - это сравнить пропорцию вписанной гиперсферы с радиусом $r {\ displaystyle r}$ $r$ и размерностью $d {\ displaystyle d}$ $d$ , с размером гиперкуба с ребрами длиной $2 r. {\ displaystyle 2r.}$ ${\ displaystyle 2r.}$ Объем такой сферы равен $2 rd π d / 2 d Γ (d / 2) {\ displaystyle {\ frac {2r ^ {d} \ pi ^ {d / 2}} {d \; \ Gamma (d / 2)}}}$ ${\ frac {2r ^ {d} \ pi ^ {{d / 2} }} {d \; \ Gamma (d / 2)}}$ , где $Γ {\ displaystyle \ Gamma}$ $\ Gamma$ - гамма функция, а объем куба равен $(2 r) d {\ displaystyle (2r) ^ {d}}$ $(2r) ^ d$ . По мере того как размер $d {\ displaystyle d}$ $d$ пространства увеличивается, гиперсфера становится незначительным объемом по сравнению с объемом гиперкуба. Это ясно можно увидеть, сравнив пропорции, когда измерение $d {\ displaystyle d}$ $d$ уходит в бесконечность:

V гиперсфера V гиперкуб = π d / 2 d 2 d - 1 Γ (d / 2) → 0 {\ displaystyle {\ frac {V _ {\ mathrm {hypersphere}}} {V _ {\ mathrm {hypercube}}}} = {\ frac {\ pi ^ {d / 2}} {d2 ^ {d-1} \ Gamma (d / 2)}} \ rightarrow 0}

{\ displaystyle {\ frac {V _ {\ mathrm {hypersphere}}} {V _ {\ mathrm {hypercube}}}} = { \ frac {\ pi ^ {d / 2}} {d2 ^ {d-1} \ Gamma (d / 2)}} \ rightarrow 0}

d → ∞ {\ displaystyle d \ rightarrow \ infty}

d \ rightarrow \ infty

Кроме того, расстояние между центром и углами составляет $rd {\ displaystyle r {\ sqrt {d}}}$ $r {\ sqrt {d}}$ , которое неограниченно увеличивается при фиксированном r. В этом смысле почти все многомерное пространство «далеко» от центра. Другими словами, можно сказать, что многомерный единичный гиперкуб почти полностью состоит из «углов» гиперкуба и почти не имеет «середины».

Это также помогает понять распределение хи-квадрат. Действительно, (нецентральное) распределение хи-квадрат, связанное со случайной точкой в интервале [-1, 1], совпадает с распределением квадрата длины случайной точки в d-кубе. По закону больших чисел это распределение концентрируется в узкой полосе примерно в d, умноженной на квадрат стандартного отклонения (σ) исходного вывода. Это освещает распределение хи-квадрат, а также показывает, что большая часть объема d-куба сосредоточена около поверхности сферы радиуса $σ d {\ displaystyle \ sigma {\ sqrt {d}}}$ ${\ displaystyle \ sigma {\ sqrt {d}}}$ .

Дальнейшее развитие этого явления состоит в следующем. Любое фиксированное распределение на ℝ индуцирует распределение продукта по точкам в ℝ. Для любого фиксированного n оказывается, что минимальное и максимальное расстояние между случайной контрольной точкой Q и списком из n случайных точек данных P 1,..., P n становятся неразличимыми по сравнению с минимальным расстоянием:

lim d → ∞ E (dist max ⁡ (d) - dist min ⁡ (d) dist min ⁡ (d)) → 0 {\ displaystyle \ lim _ {d \ to \ infty} E \ left ({\ frac {\ operatorname {dist} _ {\ max} (d) - \ operatorname {dist} _ {\ min} (d)} {\ operatorname {dist} _ {\ min} ( d)}} \ right) \ to 0}

\ lim_ {d \ to \ infty} E \ left (\ frac {\ operatorname { dist} _ {\ max} (d) - \ operatorname {dist} _ {\ min} (d)} {\ operatorname {dist} _ {\ min} (d)} \ right) \ to 0

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

Поиск ближайшего соседа

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

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

Классификация k-ближайших соседей

Другой эффект высокой размерности на функции расстояния касается графиков k-ближайших соседей (k-NN) , построенных из набора данных с использованием функция расстояния. По мере увеличения размера распределение степени k-NN орграфа становится перекошенным с пиком справа из-за появления непропорционального количества концентраторы, то есть точки данных, которые появляются в гораздо большем количестве k-NN списков других точек данных, чем в среднем. Это явление может оказать значительное влияние на различные методы классификации (включая классификатор k-NN ), полу-контролируемого обучения и кластеризации, а также влияет на поиск информации.

Обнаружение аномалий

В опросе 2012 года Zimek et al. выявил следующие проблемы при поиске аномалий в данных большой размерности:

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

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

Благословение размерности

Удивительно, но несмотря на ожидаемые трудности, связанные с «проклятием размерности», эвристика здравого смысла, основанная на самых простых методах, может дать результаты, которые почти наверняка оптимальны »для больших размерные проблемы. Термин «благословение размерности» был введен в конце 1990-х. Донохо в своем «Манифесте тысячелетия» ясно объяснил, почему «благословение размерности» ляжет в основу будущего интеллектуального анализа данных. Эффекты благословения размерности были обнаружены во многих приложениях и нашли свою основу в концентрации явлений меры. Одним из примеров благословения феномена размерности является линейная отделимость случайной точки от большого конечного случайного множества с высокой вероятностью, даже если это множество экспоненциально велико: количество элементов в этом случайном множестве может экспоненциально расти вместе с размерностью. Причем этот линейный функционал можно выбрать в виде простейшего линейного дискриминанта Фишера . Эта теорема отделимости была доказана для широкого класса распределений вероятностей: общих равномерно логарифмически вогнутых распределений, распределений произведений в кубе и многих других семейств (недавно рассмотренных в).

«Благословение размерности и проклятие размерности - две стороны одной медали». Например, типичное свойство по существу многомерных распределений вероятностей в многомерном пространстве: квадрат расстояния от случайных точек до выбранной точки с высокой вероятностью близок к среднему (или медианному) квадрату расстояния. Это свойство значительно упрощает ожидаемую геометрию данных и индексацию многомерных данных (благо), но в то же время делает поиск подобия в больших измерениях трудным и даже бесполезным (проклятие).

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

См. Также

Ссылки