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

241

Я читал, что «евклидово расстояние не является хорошим расстоянием в больших измерениях». Я думаю, что это утверждение как-то связано с проклятием размерности, но что именно? Кроме того, что такое «большие размеры»? Я применял иерархическую кластеризацию, используя евклидово расстояние со 100 объектами. До скольких функций «безопасно» использовать этот показатель?

teaLeef
источник
5
Это, вероятно, слишком для вас; Я написал серию постов в блоге на тему евклидовой метрики в более высоких измерениях и о том, как это влияет на поиск векторных пространств для ближайших совпадений. blogs.msdn.com/b/ericlippert/archive/tags/…
Эрик Липперт
1
@ HorstGrünbusch см. Ответы ниже для некоторых ссылок. Дисперсия расстояний становится небольшой по сравнению со средней. Так что в какой-то момент вы столкнетесь с проблемами при выборе порогов, веса, порядка; и вы можете даже получить проблемы с числовой точностью. Но если ваши данные редки, они, вероятно, имеют гораздо меньшую внутреннюю размерность.
Anony-Mousse
3
«большие размеры», кажется, вводит в заблуждение термин - некоторые ответы трактуют 9-12 как «большие размеры», но в других областях высокая размерность означала бы тысячи или миллион измерений (скажем, измерение углов между векторами мешков слова, где каждое измерение - это частота некоторого слова в словаре), и 100 измерений будут называться низкими, а не высокими.
Петерис
2
Этот вопрос действительно может быть связан с некоторым контекстом. Не хорошо для чего?
Сабольч

Ответы:

244

Большое резюме неинтуитивных результатов в более высоких измерениях взято из « Несколько полезных вещей, которые нужно знать о машинном обучении » Педро Домингоса из Университета Вашингтона:

[O] Ваши интуиции, которые происходят из трехмерного мира, часто не применяются в многомерных. В больших измерениях большая часть массы многомерного гауссовского распределения находится не рядом со средним, а во все более удаленной «оболочке» вокруг него; и большая часть объема большого апельсина находится в коже, а не в мякоти. Если постоянное число примеров равномерно распределено в многомерном гиперкубе, то за пределами некоторой размерности большинство примеров ближе к грани гиперкуба, чем к ближайшему соседу. И если мы приближаем гиперсферу, вписывая ее в гиперкуб, то в больших измерениях почти весь объем гиперкуба находится за пределами гиперсферы. Это плохая новость для машинного обучения, где формы одного типа часто аппроксимируются формами другого.

Статья также полна многих дополнительных жемчужин мудрости для машинного обучения.

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

От Чару С. Аггарвал, Александра Хиннебурга, Даниеля А. Кейма, « Об удивительном поведении метрик расстояния в многомерном пространстве »:

В [Кевин Бейер, Джонатан Голдштейн, Рагху Рамакришнан, Ури Шафт, « Когда важен« Ближайший сосед »? »] Утверждается, что при определенных разумных предположениях о распределении данных отношение расстояний ближайших и самых дальних соседей » для данной цели в многомерном пространстве почти 1 для широкого спектра распределений данных и функций расстояния. В таком случае проблема ближайшего соседа становится плохо определенной, поскольку контраст между расстояниями до разных точек данных не существует. В таких случаях даже концепция близости может не иметь смысла с качественной точки зрения: проблема, которая является даже более фундаментальной, чем снижение производительности алгоритмов высокой размерности.

... Многие многомерные структуры и алгоритмы индексации используют метрику [E] uclidean в качестве естественного расширения ее традиционного использования в двух- или трехмерных пространственных приложениях. ... В этой статье мы приводим некоторые удивительные теоретические и экспериментальные результаты при анализе зависимости нормы от значения . Более конкретно, мы показываем, что относительные контрасты расстояний до точки запроса сильно зависят от метрики . Это является убедительным доказательством того, что значимость нормы ухудшается быстрее при увеличении размерности для более высоких значений . Таким образом, для данной задачи с фиксированным (высоким) значением для размерностиLkkLkLkkdможет быть предпочтительным использовать более низкие значения . Это означает, что метрика расстояния (манхэттенская метрика расстояния) является наиболее предпочтительной для крупномасштабных приложений, за которой следует евклидова метрика ( ). ...kL1L2

Авторы статьи «Удивительное поведение» затем предлагают использовать нормы с . Они дают некоторые результаты, которые демонстрируют, что эти «дробные нормы» демонстрируют свойство увеличивать контраст между самыми дальними и ближайшими точками. Это может быть полезно в некоторых контекстах, однако есть предостережение: эти «дробные нормы» не являются правильными метриками расстояния, потому что они нарушают неравенство треугольника. Если неравенство треугольника является важным качеством в ваших исследованиях, то дробные метрики не будут чрезвычайно полезны.Lkk<1

Sycorax
источник
7
эта ссылка потрясающая
Антуан
1
Читая еще раз ... Прекрасно ...
Ричард Харди
113

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

Рассмотрим квадрат с вершинами в . Нарисуйте четыре круга единичного радиуса с центром в . Они «заполняют» квадрат, причем каждый круг касается сторон квадрата в двух точках, а каждый круг касается двух своих соседей. Например, окружность с центром в касается сторон квадрата в и и соседних окружностей в и . Затем нарисуйте маленький круг с центром в начале координат4×4(±2,±2)(±1,±1)(1,1)(2,1)(1,2)(1,0)(0,1)это касается всех четырех кругов. Поскольку отрезок, конечными точками которого являются центры двух колеблющихся окружностей, проходит через точку осцилляции, легко проверить, что маленький кружок имеет радиус и что он касается четырех больших окружностей в . Обратите внимание, что маленький круг «полностью окружен» четырьмя большими кругами и, таким образом, также полностью внутри квадрата. Отметим также, что точка лежит на малом круге. Обратите также внимание на то, что из начала координат нельзя «увидеть» точку на краю квадрата, поскольку линия визирования проходит через точку осцилляции двух окружностей с центром. вr2=21(±r2/2,±r2/2)(r2,0)(2,0,0)(1,0,0)(1,1) и . То же самое для линий визирования в другие точки, где оси проходят через края квадрата.(1,1)

Далее рассмотрим куб × × с вершинами в . Мы заполняем его осциллирующими сферами единичного радиуса с центром в , а затем помещаем меньшую осциллирующую сферу с центром в начале координат. Обратите внимание, что малая сфера имеет радиус а точка лежит на поверхности малой сферы. Но заметьте также, что в трех измерениях можно «увидеть» точку 4×4×4(±2,±2,±2)8(±1,±1,±1)r3=31<1(r3,0,0)(2,0,0)от происхождения; нет больших больших сфер, блокирующих обзор, как это происходит в двух измерениях. Эти четкие линии обзора от начала координат до точек, где оси проходят через поверхность куба, встречаются и во всех больших измерениях.

Обобщая, мы можем рассмотреть мерный гиперкуб со стороны и заполнить его осциллирующими гиперсферами единичного радиуса с центром в а затем поместить «меньший» осциллирующая сфера радиуса в начале координат. Точка лежит на этой "меньшей" сфере. Но обратите внимание на что когда , и, следовательно, «меньшая» сфера имеет единичный радиус и, таким образом, действительно не заслуживает субрикета «меньшего» дляn42n(±1,±1,,±1)

(1)rn=n1
(rn,0,0,,0)(1)n=4rn=1n4, Действительно, было бы лучше, если бы мы назвали это «большей сферой» или просто «центральной сферой». Как отмечено в последнем абзаце, существует четкая линия видимости от начала координат до точек, где оси проходят через поверхность гиперкуба. Хуже того, когда , мы имеем из что , и, таким образом, точка на центральной сфере лежит вне гиперкуба стороны даже если она «полностью окруженный» гиперсферами единичного радиуса, которые «заполняют» гиперкуб (в смысле его упаковки).n>9(1)rn>2(rn,0,0,,0)4 Центральная сфера «выпирает» вне гиперкуба в многомерном пространстве. Я нахожу это очень нелогичным, потому что мои умственные переводы понятия евклидова расстояния в более высокие измерения с использованием геометрической интуиции, которую я развил из знакомого мне 2-мерного и 3-мерного пространств, не описывают реальность многомерное пространство.

Мой ответ на вопрос ОП "Кроме того, что такое" большие размеры "?" это .n9

Дилип Сарватэ
источник
9
@ stackoverflowuser2010: Если этот ответ совершенно непонятен, как вы можете определить, отвечает ли он или пытается ответить на исходный вопрос? Более конструктивный подход может заключаться в том, чтобы просить разъяснить любые моменты, которые вы находите неясными, а не отбрасывать все это из-под контроля.
Scortchi
8
@ stackoverflowuser2010 Поскольку в этом ответе много десятков голосов, кажется, что многие люди считают, что он достаточно понятен и отвечает приемлемым образом на вопрос. Возможно, вы могли бы попытаться сделать более конструктивную критику - как конкретно вы думаете, этот ответ будет улучшен? Что это должно включать, что это не так?
Glen_b
1
@ Scortchi: Может быть, я ожидаю слишком многого, но однозначным ответом на этот вопрос, который мог бы помочь сообществу, было бы что-то вроде «Евклидово расстояние не является хорошим показателем, потому что <X>».
stackoverflowuser2010
7
@ stackoverflow2010 Вы никогда не увидите такого «хорошего» ответа, потому что <все гораздо сложнее, чем утверждения if-then>. Если вы хотите простой ответ, скорее всего, он ложный. Как чертовски лжецы-брекситы, они умели предлагать простые ответы (ложные, но простые).
Anony-Mousse
42

Это вопрос сигнал-шум . Евклидово расстояние, благодаря квадратным слагаемым, особенно чувствительно к шуму; но даже Манхэттенское расстояние и «дробные» (неметрические) расстояния страдают.

Я нашел исследования в этой статье очень поучительными:

Зимек А., Шуберт Э. и Кригель Х.-П. (2012),
Обследование по обнаружению неконтролируемых выбросов в многомерных числовых данных.
Статистический анализ данных Mining, 5: 363–387. doi: 10.1002 / sam.11161

В нем также рассматриваются наблюдения, сделанные, например, «Об удивительном поведении метрик расстояния в высокомерном пространстве» Аггарвала, Хиннебурга и Кейма, упомянутые @Pat. Но это также показывает, насколько синтетические эксперименты вводят в заблуждение и что на самом деле многомерные данные могут стать проще . Если у вас много (избыточного) сигнала, а новые размеры добавляют мало шума.

Последнее утверждение, вероятно, наиболее очевидно при рассмотрении дублирующих размеров. Отображение вашего набора данных увеличивает репрезентативную размерность, но вовсе не приводит к сбою евклидова расстояния. (Смотрите также: внутренняя размерность )x,yx,y,x,y,x,y,x,y,...,x,y

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

Некоторые люди считают, что косинусное расстояние лучше, чем евклидово, по многомерным данным. Я так не думаю: косинусное расстояние и евклидово расстояние тесно связаны; поэтому мы должны ожидать, что они будут страдать от тех же проблем. Тем не менее, текстовые данные, где косинус популярен, обычно редки , и косинус быстрее в разреженных данных, поэтому для разреженных данных есть веские причины использовать косинус; и поскольку данные редки, внутренняя размерность намного меньше, чем размерность векторного пространства.

См. Также ответ, который я дал на предыдущий вопрос: https://stats.stackexchange.com/a/29647/7828.

Anony-Мус
источник
Средний угол случайно расположенных точек в всегда близок к 90 ° для больших (см. Графики здесь )[1,1]nn
Мартин Тома
И каков будет вывод из этого? На [-1; 1] ^ d нельзя использовать косинус, потому что он не определен в 0, среднее ничего не говорит нам о проклятии, и единообразные данные нереальны.
Anony-Mousse
Я не пробовал это сейчас, но я предполагаю, что углы выглядят одинаково для реальных данных. Факт, что это не определено в 0, не должен действительно иметь значение, поскольку это - только одна точка. Мой вывод похож на ваш: расстояние до косинуса не подходит для пространств с большими размерами (хотя, возможно, существуют области, в которых оно все еще работает)
Мартин Тома,
Более реалистичным сценарием были бы точки на сфере неотрицательных единиц. И мерой интереса, скорее всего, будет дисперсия, а не среднее.
Anony-Mousse
Чтобы попасть в неотрицательную единичную сферу, нужно всего лишь добавить +1 и поделить на 2 ...
Мартин Тома,
34

Лучше всего начать с чтения «Удивительного поведения дистанционных метрик в многомерном пространстве » Аггарвала, Хиннебурга и Кейма. Здесь есть действующая ссылка (pdf) , но она должна быть очень удобной для Google, если она сломается. Короче говоря, с ростом числа измерений относительное евклидово расстояние между точкой в ​​наборе и ее ближайшим соседом, а также между этой точкой и ее самым дальним соседом изменяется некоторыми неочевидными способами. Будет ли это плохо влиять на ваши результаты, во многом зависит от того, чего вы пытаетесь достичь и каковы ваши данные.

похлопывание
источник
6

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

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

samthebest
источник
2
Это может быть проблематично, так как KL Divergence не является метрикой. :-)
Агари
2
Если вам нужна симметрия, вы можете использовать Взаимную информацию, которая, как намекнул, может быть определена в терминах KL.
Самбест
3

В качестве аналогии представьте круг с центром в начале координат. Очки распределяются равномерно. Предположим, что случайно выбранная точка находится в точке (x1, x2). Евклидово расстояние от начала координат ((x1) ^ 2 + (x2) ^ 2) ^ 0.5

Теперь представьте точки, равномерно распределенные по сфере. Та же самая точка (x1, x2) теперь вероятно будет (x1, x2, x3). Поскольку в четном распределении только в нескольких точках одна из координат равна нулю, мы будем считать, что [x3! = 0] для нашей случайно выбранной равномерно распределенной точки. Таким образом, наша случайная точка наиболее вероятна (x1, x2, x3), а не (x1, x2, 0).

Эффект этого таков: любая случайная точка теперь находится на расстоянии ((x1) ^ 2 + (x2) ^ 2 + (x3) ^ 2) ^ 0.5 от начала трехмерной сферы. Это расстояние больше, чем для случайной точки около начала двумерного круга. Эта проблема усугубляется в более высоких измерениях, поэтому мы выбираем показатели, отличные от евклидовых измерений, для работы с более высокими измерениями.

РЕДАКТИРОВАТЬ: есть поговорка, которую я сейчас вспоминаю: «Большая часть массы многомерного апельсина находится в коже, а не в мякоти», означая, что в более высоких измерениях равномерно распределенные точки находятся более «близко» (евклидово расстояние) к границе чем происхождение.

Примечание: Евклидово расстояние не слишком плохо для реальных проблем из-за «благословения неоднородности», которое в основном утверждает, что для реальных данных ваши данные, вероятно, НЕ будут распределяться равномерно в пространстве более высокого измерения, но будет занимать небольшое кластерное подмножество пространства. Это имеет смысл интуитивно: если вы измеряете 100 величин о людях, таких как рост, вес и т. Д., Равномерное распределение по пространству измерений просто не имеет смысла, например, человек с (рост = 65 дюймов, вес = 150 фунтов, avg_calorie_intake = 4000), что просто невозможно в реальном мире.

Абхишек Дивекар
источник
Если кого-то из будущих читателей заинтересует цитата «апельсин / мякоть» или замечание «благословение неоднородности», они оба появятся в «Несколько полезных вещей для изучения машинного обучения», с которыми связан мой ответ на этот вопрос. нить.
Sycorax
1

Другой аспект этого вопроса заключается в следующем:

Очень часто большие проблемы в (машинном обучении / статистике) являются результатом чрезмерно ограниченных возможностей.

Это означает, что измерения НЕ являются независимыми (или некоррелированными), но евклидовы метрики предполагают (как минимум) некорреляцию и, следовательно, могут не дать наилучших результатов.

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

Кроме того: Csiszar (et al.) Утверждает, что евклидовы метрики являются «естественными» кандидатами на умозаключения, когда характеристики имеют определенные формы.

Никос М.
источник
3
Евклидовы метрики не "предполагают ... некорреляцию". Евклидовы расстояния хуже всего работают в больших измерениях с некоррелированными переменными. Рассмотрим крайний случай: у вас очень много измерений, которые все идеально коррелируют, r = 1, теперь ваши данные фактически являются одномерными, а евклидово расстояние отлично работает с одномерными данными.
gung
Нет, я так не думаю, евклидово расстояние по определению предполагает некоррелированные данные (кроме случаев использования обобщенного евклидова расстояния с матрицей корреляции)
Никос М.
Характеристики с полной корреляцией (r = 1) - тривиальный пример, эквивалентный «тривиальной матрице корреляции», но, возможно, я ошибаюсь
Никос М.
@gung Вы можете интерпретировать евклидову потерю как перекрестную энтропийную потерю гауссианов с фиксированной единицей изотропной матрицы дисперсии. Я думаю, что это хороший момент, но это может быть лучше объяснено.
Нил Дж
1
@NeilG, я понятия не имею, что это вообще значит. Рассмотрим 2 точки на плоскости: и . Евклидово расстояние между ними определяется как: ; здесь, . Теперь представьте, что на этой плоскости существует больше точек, но все они лежат вдоль линии , что делает корреляцию между двумя переменными . Каково евклидово расстояние между этими двумя точками? Это все еще . Теперь представьте, что дополнительные точки расположены равномерно st . Каково евклидово расстояние между этими двумя точками? Это все еще . (0,0)(1,1)dE=j(x2jx1j)22X1=X212cor(X1,X2)=02
gung
0

Эта статья также может вам помочь. «Улучшенное измерение подобия по косинусу». Посетите страницу https://journalofbigdata.springeropen.com/articles/10.1186/s40537-017-0083-6. В этой статье объясняется, почему евклидово расстояние не является хорошим показателем в высоком измерении. данные и что является лучшей заменой евклидова расстояния в многомерных данных. Евклидово расстояние является нормой L2, и, уменьшая значение k в норме Lk, мы можем облегчить проблему расстояния в многомерных данных. Вы также можете найти ссылки в этой статье.

Саар
источник
2
Добро пожаловать на сайт. Мы пытаемся создать постоянное хранилище высококачественной статистической информации в форме вопросов и ответов. Таким образом, мы опасаемся ответов, содержащих только ссылки, из-за linkrot. Можете ли вы опубликовать полную ссылку и краткое изложение информации по ссылке, если она не работает?
gung