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

Difficulties arising when analyzing data with many aspects ("dimensions")

Проклятие размерности относится к различным явлениям, которые возникают при анализе и организации данных в многомерных пространствах , которые не встречаются в низкомерных условиях, таких как трехмерное физическое пространство повседневного опыта. Выражение было придумано Ричардом Э. Беллманом при рассмотрении проблем динамического программирования . ^{[1] [2]} Проклятие обычно относится к проблемам, которые возникают, когда количество точек данных мало (в подходящем определенном смысле) относительно внутренней размерности данных.

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

Домены

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

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

Отбор проб

Существует экспоненциальное увеличение объема, связанное с добавлением дополнительных измерений в математическое пространство . Например, 10 ²  = 100 равномерно распределенных точек выборки достаточно для выборки единичного интервала (попробуйте визуализировать «одномерный» куб) с расстоянием между точками не более 10 ⁻² = 0,01; эквивалентная выборка 10-мерного единичного гиперкуба с решеткой, которая имеет расстояние 10 ⁻² = 0,01 между соседними точками, потребовала бы 10 ²⁰ = [(10 ² ) ¹⁰ ] точек выборки. В общем случае, с расстоянием между соседними точками 10 ^{− n} 10-мерный гиперкуб оказывается в 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ /(10 ⁿ )] «больше», чем 1-мерный гиперкуб, который является единичным интервалом. В приведенном выше примере n = 2: при использовании расстояния выборки 0,01 10-мерный гиперкуб кажется на 10 ¹⁸ "больше" единичного интервала. Этот эффект является комбинацией вышеприведенных проблем комбинаторики и проблем функции расстояния, объясненных ниже.

Оптимизация

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

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

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

Типичное практическое правило заключается в том, что для каждого измерения в представлении должно быть не менее 5 обучающих примеров. ^[5] В машинном обучении и в том, что касается предсказательной эффективности, проклятие размерности используется взаимозаменяемо с явлением пика , ^[5] которое также известно как явление Хьюза . ^[6] Это явление заключается в том, что при фиксированном количестве обучающих образцов средняя (ожидаемая) предсказательная способность классификатора или регрессора сначала увеличивается по мере увеличения количества используемых измерений или признаков, но после определенной размерности она начинает ухудшаться вместо того, чтобы неуклонно улучшаться. ^{[7] [8] [9]}

Тем не менее, в контексте простого классификатора (например, линейный дискриминантный анализ в многомерной гауссовой модели в предположении общей известной ковариационной матрицы), Золланвари и др. показали как аналитически, так и эмпирически, что до тех пор, пока относительная кумулятивная эффективность дополнительного набора признаков (по отношению к признакам, которые уже являются частью классификатора) больше (или меньше), чем размер этого дополнительного набора признаков, ожидаемая ошибка классификатора, построенного с использованием этих дополнительных признаков, будет меньше (или больше), чем ожидаемая ошибка классификатора, построенного без них. Другими словами, как размер дополнительных признаков, так и их (относительный) кумулятивный дискриминационный эффект важны для наблюдения за уменьшением или увеличением средней предсказательной силы. ^[10]

В метрическом обучении более высокие измерения иногда могут позволить модели достичь лучшей производительности. После нормализации вложений на поверхность гиперсферы FaceNet достигает наилучшей производительности, используя 128 измерений, а не 64, 256 или 512 измерений в одном исследовании абляции. ^[11] Было обнаружено, что функция потерь для унитарно-инвариантного различия между вложениями слов минимизируется в высоких измерениях. ^[12]

Сбор данных

В интеллектуальном анализе данных проклятие размерности относится к набору данных со слишком большим количеством признаков.

Рассмотрим первую таблицу, в которой изображены 200 человек и 2000 генов (признаков), где 1 или 0 обозначают наличие или отсутствие генетической мутации в этом гене. Приложением для интеллектуального анализа данных к этому набору данных может быть поиск корреляции между определенными генетическими мутациями и создание алгоритма классификации, например, дерева решений, для определения того, есть ли у человека рак или нет.

Распространенной практикой интеллектуального анализа данных в этой области было бы создание правил ассоциации между генетическими мутациями, которые приводят к развитию рака. Для этого нужно было бы пройтись по каждой генетической мутации каждого человека и найти другие генетические мутации, которые происходят выше желаемого порога, и создать пары. Они бы начинали с пар из двух, затем трех, затем четырех, пока не получили бы пустой набор пар. Сложность этого алгоритма может привести к вычислению всех перестановок пар генов для каждого человека или строки. Учитывая формулу для вычисления перестановок n элементов с размером группы r , вычисление количества трех парных перестановок любого данного человека будет составлять 7988004000 различных пар генов для оценки для каждого человека. Количество созданных пар будет расти на порядок факториала по мере увеличения размера пар. Рост отображен в таблице перестановок (см. справа). ${\displaystyle {\frac {n!}{(n-r)!}}}$

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

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

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

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

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

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

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

${\displaystyle {\frac {V_{\mathrm {hypersphere} }}{V_{\mathrm {hypercube} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0}$как . ${\displaystyle d\rightarrow \infty }$

При этом расстояние между центром и углами равно , которое неограниченно увеличивается при фиксированном r. ${\displaystyle r{\sqrt {d}}}$

В этом смысле, когда точки равномерно генерируются в гиперкубе высокой размерности, почти все точки находятся намного дальше, чем единицы от центра. В высоких размерностях объем d -мерного единичного гиперкуба (с координатами вершин ) сосредоточен вблизи сферы с радиусом для большой размерности d . Действительно, для каждой координаты среднее значение в кубе равно ^[13] ${\displaystyle r}$ ${\displaystyle \pm 1}$ ${\displaystyle {\sqrt {d}}/{\sqrt {3}}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}^{2}}$

${\displaystyle \left\langle x_{i}^{2}\right\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}}$.

Дисперсия для равномерного распределения в кубе равна ${\displaystyle x_{i}^{2}}$

${\displaystyle {\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\left\langle x_{i}^{2}\right\rangle ^{2}={\frac {4}{45}}}$

Поэтому квадрат расстояния от начала координат имеет среднее значение d /3 и дисперсию 4 d /45. При больших d распределение близко к нормальному распределению со средним значением 1/3 и стандартным отклонением согласно центральной предельной теореме . Таким образом, при равномерной генерации точек в больших размерностях как «середина» гиперкуба, так и углы оказываются пустыми, а весь объем сосредоточен вблизи поверхности сферы «промежуточного» радиуса . ${\textstyle r^{2}=\sum _{i}x_{i}^{2}}$ ${\displaystyle r^{2}/d}$ ${\displaystyle 2/{\sqrt {45d}}}$ ${\textstyle {\sqrt {d/3}}}$

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

Дальнейшее развитие этого явления заключается в следующем. Любое фиксированное распределение действительных чисел индуцирует распределение произведения точек в . Для любого фиксированного n оказывается, что разница между минимальным и максимальным расстоянием между случайной опорной точкой Q и списком из n случайных точек данных P ₁ ,..., P _n становится неразличимой по сравнению с минимальным расстоянием: ^[14] ${\displaystyle \mathbb {R} ^{d}}$

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

Это часто упоминается как функция расстояния, теряющая свою полезность (например, для критерия ближайшего соседа в алгоритмах сравнения признаков) в больших размерностях. Однако недавние исследования показали, что это справедливо только в искусственном сценарии, когда одномерные распределения независимы и распределены одинаково . ^[15] Когда атрибуты коррелируют, данные могут стать проще и обеспечить более высокий контраст расстояний, а соотношение сигнал/шум, как было обнаружено, играет важную роль, поэтому следует использовать выбор признаков . ^[15] ${\displaystyle \mathbb {R} }$

Совсем недавно было высказано предположение, что в аргументе о том, что потеря контраста создает проклятие в больших измерениях, может быть концептуальный изъян. Машинное обучение можно понимать как проблему назначения экземпляров их соответствующему генеративному процессу происхождения, при этом метки классов действуют как символические представления отдельных генеративных процессов. Вывод проклятия предполагает, что все экземпляры являются независимыми, идентичными результатами одного генеративного процесса большой размерности. Если бы существовал только один генеративный процесс, существовал бы только один (естественный) класс, и машинное обучение было бы концептуально плохо определено как в больших, так и в малых измерениях. Таким образом, традиционный аргумент о том, что потеря контраста создает проклятие, может быть принципиально неуместным. Кроме того, было показано, что когда генеративная модель модифицируется для учета нескольких генеративных процессов, потеря контраста может трансформироваться из проклятия в благословение, поскольку она гарантирует, что ближайший сосед экземпляра почти наверняка является его наиболее тесно связанным экземпляром. С этой точки зрения потеря контраста делает большие размерные расстояния особенно значимыми, а не особенно бессмысленными, как это часто утверждается. ^[16]

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

Эффект усложняет поиск ближайшего соседа в пространстве с высокой размерностью. Невозможно быстро отклонить кандидатов, используя разницу в одной координате как нижнюю границу для расстояния, основанного на всех измерениях. ^{[17] [18]}

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

к-классификация по методу ближайшего соседа

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

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

В исследовании 2012 года Зимек и др. выявили следующие проблемы при поиске аномалий в многомерных данных: ^[15]

1. Концентрация оценок и расстояний: производные значения, такие как расстояния, становятся численно схожими
2. Нерелевантные атрибуты: в многомерных данных значительное количество атрибутов может быть нерелевантным.
3. Определение наборов ссылок: для локальных методов наборы ссылок часто основаны на методе ближайших соседей.
4. Несравнимые оценки для разных размерностей: разные подпространства дают несравнимые оценки
5. Интерпретируемость оценок: оценки часто больше не несут семантического значения.
6. Экспоненциальное пространство поиска: пространство поиска больше не может систематически сканироваться
7. Ошибка слежки за данными : учитывая большое пространство поиска, для каждого желаемого значения можно найти гипотезу
8. Хабнес: некоторые объекты встречаются в списках соседей чаще, чем другие.

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

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

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

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

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

Смотрите также

• Уравнение Беллмана
• Кластеризация многомерных данных
• Концентрация меры
• Уменьшение размерности
• Динамическое программирование
• Преобразования, связанные с Фурье
• Гранд Тур
• Линейный метод наименьших квадратов
• Сокращение порядка модели
• Многолинейный PCA
• Мультилинейное подпространственное обучение
• Анализ главных компонент
• Разложение по сингулярным значениям

Ссылки

1. Беллман, Ричард Эрнест; Rand Corporation (1957). Динамическое программирование. Princeton University Press. стр. ix. ISBN 978-0-691-07951-6.,
   Переиздано: Беллман, Ричард Эрнест (2003). Динамическое программирование. Courier Dover Publications. ISBN 978-0-486-42809-3.
2. Беллман, Ричард Эрнест (1961). Адаптивные процессы управления: путеводитель. Princeton University Press. ISBN 9780691079011.
3. Тейлор, К. Роберт (1993). «Динамическое программирование и проклятия размерности». Приложения динамического программирования к проблемам принятия решений в сельском хозяйстве . Westview Press. стр. 1–10. ISBN 0-8133-8641-1.
4. Udacity (23.02.2015). "Проклятие размерности - Georgia Tech - Машинное обучение". YouTube . Получено 29.06.2022 .
5. Koutroumbas, Konstantinos; Theodoridis, Sergios (2008). Распознавание образов (4-е изд.). Burlington. ISBN 978-1-59749-272-0. Получено 2018-01-08 .{{cite book}}: CS1 maint: location missing publisher (link)
6. Хьюз, ГФ (январь 1968). «О средней точности статистических распознавателей образов». Труды IEEE по теории информации . 14 (1): 55–63. doi :10.1109/TIT.1968.1054102. S2CID  206729491.
7. Транк, Г. В. (июль 1979 г.). «Проблема размерности: простой пример». Труды IEEE по анализу шаблонов и машинному интеллекту . PAMI-1 (3): 306–307. doi :10.1109/TPAMI.1979.4766926. PMID  21868861. S2CID  13086902.
8. B. Chandrasekaran; AK Jain (1974). «Сложность квантования и независимые измерения». IEEE Transactions on Computers . 23 (8): 102–106. doi :10.1109/TC.1974.223789. S2CID  35360973.
9. Маклахлан, Г. Дж. (2004). Дискриминантный анализ и статистическое распознавание образов . Wiley Interscience. ISBN 978-0-471-69115-0. МР  1190469.
10. Золланвари, А.; Джеймс, А.П.; Самени, Р. (2020). «Теоретический анализ явления пика в классификации». Журнал классификации . 37 (2): 421–434. doi :10.1007/s00357-019-09327-3. S2CID  253851666.
11. Шрофф, Флориан; Калениченко, Дмитрий; Филбин, Джеймс (июнь 2015 г.). «FaceNet: унифицированное встраивание для распознавания лиц и кластеризации» (PDF) . Конференция IEEE 2015 г. по компьютерному зрению и распознаванию образов (CVPR) . стр. 815–823. arXiv : 1503.03832 . doi : 10.1109/CVPR.2015.7298682. ISBN 978-1-4673-6964-0. S2CID  206592766.
12. Инь, Цзы; Шэнь, Юаньюань (2018). «О размерности встраивания слов» (PDF) . Достижения в области нейронных систем обработки информации . 31. Curran Associates, Inc.
13. Бейли, Д. Х.; Борвейн, Дж. М.; Крэндалл, Р. Э. (2006), «Ящичные интегралы», Журнал вычислительной и прикладной математики , 206 : 196–208, doi : 10.1016/j.cam.2006.06.010 , S2CID  2763194
14. Бейер, К.; Голдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда „ближайший сосед“ имеет смысл?». Теория баз данных — ICDT'99. LNCS. Том 1540. С. 217–235. doi :10.1007/3-540-49257-7_15. ISBN 978-3-540-65452-0. S2CID  206634099.
15. Zimek, A.; Schubert, E.; Kriegel, H.-P. (2012). «Обзор неконтролируемого обнаружения выбросов в многомерных числовых данных». Статистический анализ и интеллектуальный анализ данных . 5 (5): 363–387. doi :10.1002/sam.11161. S2CID  6724536.
16. Линь, Вэнь-Янь; Лю, Сыин; Жэнь, Чанхао; Чунг, Нгай-Ман; Ли, Хундун; Мацусита, Ясуюки (2021). «Теория оболочек: статистическая модель реальности». Труды IEEE по анализу шаблонов и машинному интеллекту . 44 (10): 6438–6453. doi :10.1109/TPAMI.2021.3084598. ISSN  1939-3539. PMID  34048335. S2CID  235242104.
17. Маримонт, Р. Б.; Шапиро, М. Б. (1979). «Поиск ближайшего соседа и проклятие размерности». IMA J Appl Math . 24 (1): 59–70. doi :10.1093/imamat/24.1.59.
18. Чавес, Эдгар; Наварро, Гонсало; Баеза-Йейтс, Рикардо; Маррокин, Хосе Луис (2001). «Поиск в метрических пространствах». Обзоры вычислительной техники ACM . 33 (3): 273–321. CiteSeerX 10.1.1.100.7845 . дои : 10.1145/502807.502808. S2CID  3201604. 
19. Хоул, ME; Кригель, HP ; Крёгер, P.; Шуберт, E.; Зимек, A. (2010). Могут ли расстояния между соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспект лекций по информатике. Том 6187. стр. 482. doi :10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
20. Бернекер, Т.; Хоул, М.Э.; Кригель, Х.П .; Крёгер, П.; Ренц, М.; Шуберт, Э.; Зимек, А. (2011). Качество ранжирования сходства во временных рядах . Симпозиум по пространственным и временным базам данных. Конспект лекций по информатике. Том 6849. стр. 422. doi :10.1007/978-3-642-22922-0_25. ISBN 978-3-642-22921-3.
21. Радованович, Милош; Нанопулос, Александрос; Иванович, Мирьяна (2010). «Хабы в космосе: популярные ближайшие соседи в многомерных данных» (PDF) . Журнал исследований машинного обучения . 11 : 2487–2531.
22. Радованович, М.; Нанопулос, А.; Иванович, М. (2010). О существовании упрямых результатов в моделях векторного пространства . 33-я международная конференция ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '10. стр. 186. doi :10.1145/1835449.1835482. ISBN 9781450301534.
23. Kainen, Paul C. (1997), «Использование геометрических аномалий высокой размерности: когда сложность упрощает вычисления», в Kárný, M.; Warwick, K. (ред.), Computer Intensive Methods in Control and Signal Processing , стр. 283–294, doi :10.1007/978-1-4612-1996-5_18, ISBN 978-1-4612-7373-8
24. Донохо, Дэвид Л. (2000), «Анализ многомерных данных: проклятия и благословения размерности», приглашенная лекция на конференции «Математические проблемы XXI века», Национальное собрание AMS, Лос-Анджелес, Калифорния, США, 6–12 августа 2000 г. , CiteSeerX 10.1.1.329.3392 
25. Горбань, Александр Н .; Макаров, Валерий А.; Тюкин, Иван Ю. (2020). «Мозг высокой размерности в мире высокой размерности: благословение размерности». Entropy . 22 (1): 82. arXiv : 2001.04959 . Bibcode : 2020Entrp..22 ...82G. doi : 10.3390/e22010082 . PMC 7516518. PMID  33285855. 
26. Горбань, Александр Н.; Тюкин, Иван Ю. (2018). «Благословение размерности: математические основы статистической физики данных». Phil. Trans. R. Soc. A. 376 ( 2118): 20170237. arXiv : 1801.03421 . Bibcode : 2018RSPTA.37670237G. doi : 10.1098/rsta.2017.0237 . PMC 5869543. PMID  29555807 . 
27. Хехт-Нильсен, Роберт (1994), «Контекстные векторы: универсальные приближенные смысловые представления, самоорганизованные из необработанных данных», в Zurada, JM; Marks, RJ; Robinson, CJ (ред.), Вычислительный интеллект: имитация жизни; Труды Всемирного конгресса по вычислительному интеллекту, нейронные сети; 1994; Орландо; Флорида , Пискатауэй, Нью-Джерси: IEEE Press, стр. 43–56, ISBN 0780311043
28. Пестов, Владимир (2013). «Подвержен ли классификатор k-NN в больших размерностях проклятию размерности?». Comput. Math. Appl . 65 (10): 43–56. doi : 10.1016/j.camwa.2012.09.011 .