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

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

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

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

Домены

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

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

Выборка

Существует экспоненциальное увеличение объема, связанное с добавлением дополнительных измерений в математическое пространство . Например, 10 ²  = 100 равномерно расположенных точек выборки достаточно для выборки единичного интервала (попытайтесь визуализировать «одномерный» куб) с расстоянием между точками не более 10 ^-2 = 0,01; эквивалентная выборка 10-мерного единичного гиперкуба с решеткой, расстояние между соседними точками которой составляет 10 ^-2 = 0,01, потребует 10 ²⁰ = [(10 ² ) ¹⁰ ] точек выборки. В общем, при расстоянии 10 ^{− n} 10-мерный гиперкуб оказывается в 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ /(10 ⁿ )] «большем», чем одномерный гиперкуб. гиперкуб, который является единичным интервалом. В приведенном выше примере 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 -ближайших соседей ( k -NN) , построенных на основе набора данных с использованием функции расстояния. По мере увеличения размерности распределение по степени орграфа k -NN становится искаженным с пиком справа из-за появления непропорционального количества узлов , то есть точек данных, которые появляются во многих других списках k -NN других точек данных, чем в среднем. Это явление может оказать значительное влияние на различные методы классификации ( включая классификатор k -NN ), полуконтролируемое обучение и кластеризацию ^[21] , а также влияет на поиск информации . ^[22]

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

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

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

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

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

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

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

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

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

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

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

1. Беллман, Ричард Эрнест; Рэнд Корпорейшн (1957). Динамическое программирование. Издательство Принстонского университета. п. ix. ISBN 978-0-691-07951-6.,
   Переиздано: Беллман, Ричард Эрнест (2003). Динамическое программирование. Публикации Курьера Дувра. ISBN 978-0-486-42809-3.
2. Беллман, Ричард Эрнест (1961). Процессы адаптивного управления: экскурсия. Издательство Принстонского университета. ISBN 9780691079011.
3. Тейлор, К. Роберт (1993). «Динамическое программирование и проклятия размерности». Применение динамического программирования к задачам принятия решений в сельском хозяйстве . Вествью Пресс. стр. 1–10. ISBN 0-8133-8641-1.
4. Udacity (23 февраля 2015 г.). «Проклятие размерности – Технологический институт Джорджии – Машинное обучение» . Проверено 29 июня 2022 г.
5. Кутрумбас, Константинос; Теодоридис, Сергиос (2008). Распознавание образов (4-е изд.). Берлингтон. ISBN 978-1-59749-272-0. Проверено 8 января 2018 г.{{cite book}}: CS1 maint: location missing publisher (link)
6. Хьюз, Г.Ф. (январь 1968 г.). «О средней точности статистических распознавателей образов». Транзакции IEEE по теории информации . 14 (1): 55–63. дои : 10.1109/TIT.1968.1054102. S2CID  206729491.
7. Транк, Г.В. (июль 1979 г.). «Проблема размерности: простой пример». Транзакции IEEE по анализу шаблонов и машинному интеллекту . ПАМИ-1 (3): 306–307. дои : 10.1109/TPAMI.1979.4766926. PMID  21868861. S2CID  13086902.
8. Б. Чандрасекаран; А. К. Джайн (1974). «Сложность квантования и независимые измерения». Транзакции IEEE на компьютерах . 23 (8): 102–106. дои : 10.1109/TC.1974.223789. S2CID  35360973.
9. Маклахлан, GJ (2004). Дискриминантный анализ и статистическое распознавание образов . Уайли Интерсайенс. ISBN 978-0-471-69115-0. МР  1190469.
10. Золланвари, А.; Джеймс, AP; Самени, Р. (2020). «Теоретический анализ феномена пика в классификации». Журнал классификации . 37 (2): 421–434. дои : 10.1007/s00357-019-09327-3. S2CID  253851666.
11. Шрофф, Флориан; Калениченко Дмитрий; Филбин, Джеймс (июнь 2015 г.). «FaceNet: унифицированное внедрение для распознавания лиц и кластеризации» (PDF) . Конференция IEEE 2015 по компьютерному зрению и распознаванию образов (CVPR) . стр. 815–823. arXiv : 1503.03832 . дои : 10.1109/CVPR.2015.7298682. ISBN 978-1-4673-6964-0. S2CID  206592766.
12. Инь, Цзы; Шен, Юаньюань (2018). «О размерности встраивания слов» (PDF) . Достижения в области нейронных систем обработки информации . Карран Ассошиэйтс, Инк. 31 .
13. Бейли, Д.Х.; Борвейн, Дж. М.; Крэндалл, Р.Э. (2006), «Боксовые интегралы», Журнал вычислительной и прикладной математики , 206 : 196–208, doi : 10.1016/j.cam.2006.06.010 , S2CID  2763194
14. Бейер, К.; Гольдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда имеет смысл слово «ближайший сосед»?». Теория баз данных — ICDT'99. ЛНКС. Том. 1540. стр. 217–235. дои : 10.1007/3-540-49257-7_15. ISBN 978-3-540-65452-0. S2CID  206634099.
15. Зимек, А.; Шуберт, Э.; Кригель, Х.-П. (2012). «Опрос по неконтролируемому обнаружению выбросов в многомерных числовых данных». Статистический анализ и интеллектуальный анализ данных . 5 (5): 363–387. дои : 10.1002/sam.11161. S2CID  6724536.
16. Линь, Вэнь-Янь; Лю, Сыин; Рен, Чанхао; Чунг, Нгай-Ман; Ли, Гонконг; Мацусита, Ясуюки (2021). «Теория оболочек: статистическая модель реальности». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 44 (10): 6438–6453. дои : 10.1109/TPAMI.2021.3084598. ISSN  1939-3539. PMID  34048335. S2CID  235242104.
17. Маримонт, РБ; Шапиро, МБ (1979). «Поиски ближайших соседей и проклятие размерности». IMA J Appl Math . 24 (1): 59–70. дои : 10.1093/имамат/24.1.59.
18. Чавес, Эдгар; Наварро, Гонсало; Баеза-Йейтс, Рикардо; Маррокин, Хосе Луис (2001). «Поиск в метрических пространствах». Обзоры вычислительной техники ACM . 33 (3): 273–321. CiteSeerX 10.1.1.100.7845 . дои : 10.1145/502807.502808. S2CID  3201604. 
19. Хоул, Мэн; Кригель, HP ; Крегер, П.; Шуберт, Э.; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспекты лекций по информатике. Том. 6187. с. 482. дои : 10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
20. Бернекер, Т.; Хоул, Мэн; Кригель, HP ; Крегер, П.; Ренц, М.; Шуберт, Э.; Зимек, А. (2011). Качество ранжирования сходства во временных рядах . Симпозиум по пространственным и временным базам данных. Конспекты лекций по информатике. Том. 6849. с. 422. дои : 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. дои : 10.1145/1835449.1835482. ISBN 9781450301534.
23. Кайнен, Пол К. (1997), «Использование геометрических аномалий большой размерности: когда сложность упрощает вычисления», в Карни, М.; Уорвик, К. (ред.), Интенсивные компьютерные методы управления и обработки сигналов , стр. 283–294, номер документа : 10.1007/978-1-4612-1996-5_18.
24. Донохо, Дэвид Л. (2000), «Анализ многомерных данных: проклятия и благословения размерности», приглашенная лекция на тему «Математические проблемы 21 века», Национальное собрание AMS, Лос-Анджелес, Калифорния, США, 6–12 августа. , 2000 , CiteSeerX 10.1.1.329.3392 
25. Горбань, Александр Н .; Макаров Валерий А.; Тюкин, Иван Юрьевич (2020). «Многомерный мозг в многомерном мире: благословение размерности». Энтропия . 22 (1): 82. arXiv : 2001.04959 . Бибкод : 2020Entrp..22...82G. дои : 10.3390/e22010082 . ПМЦ 7516518 . ПМИД  33285855. 
26. Горбань, Александр Н.; Тюкин, Иван Юрьевич (2018). «Благословение размерности: математические основы статистической физики данных». Фил. Пер. Р. Сок. А. _ 376 (2118): 20170237.arXiv : 1801.03421 . Бибкод : 2018RSPTA.37670237G. дои : 10.1098/rsta.2017.0237 . ПМК 5869543 . ПМИД  29555807. 
27. Хехт-Нильсен, Роберт (1994), «Векторы контекста: универсальные приблизительные представления значения, самоорганизующиеся на основе необработанных данных», в Зураде, Дж. М.; Маркс, Р.Дж.; Робинсон, CJ (ред.), Вычислительный интеллект: имитация жизни; Труды Всемирного конгресса по вычислительному интеллекту, нейронным сетям; 1994 год; Орландо; Флорида , Пискатауэй, Нью-Джерси: IEEE Press, стр. 43–56, ISBN. 0780311043
28. Пестов, Владимир (2013). «Подвержено ли проклятию размерности классификатор k-NN в больших измерениях?». Вычислить. Математика. Приложение . 65 (10): 43–56. дои : 10.1016/j.camwa.2012.09.011 .