Ближайшие соседи по многомерным данным?

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

• Является ли евклидово расстояние хорошей метрикой для поиска ближайших соседей? Если нет, каковы мои варианты?
• Кроме того, как можно определить правильный порог для определения k-соседей? Можно ли провести анализ, чтобы выяснить это значение?
• Ранее мне предлагалось использовать kd-Trees, но на странице Википедии четко сказано, что для больших размеров kd-Tree почти эквивалентно поиску методом грубой силы. В таком случае, как лучше всего найти ближайших соседей в наборе данных на миллион точек?

Может кто-нибудь уточнить некоторые (или все) из вышеперечисленных вопросов?

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

Вы можете быть заинтересованы в алгоритмах Приблизительный ближайший сосед ( ANN ). Идея состоит в том, что вы позволяете алгоритму возвращать достаточно близко к соседям (возможно, не к ближайшему соседу); тем самым вы уменьшаете сложность. Вы упомянули дерево кд ; это один из примеров. Но, как вы сказали, kd-tree плохо работает в больших размерах. Фактически, все современные методы индексации (основанные на разделении пространства) ухудшаются до линейного поиска для достаточно больших измерений [1] [2] [3].

Среди алгоритмов ANN , предложенных в последнее время, возможно, наиболее популярным является локально-чувствительное хеширование ( LSH ), которое отображает набор точек в многомерном пространстве в набор бинов, то есть хеш-таблицу [1] [3]. Но в отличие от традиционных хешей, чувствительный к локальному хешу размещает соседние точки в одну и ту же корзину.

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

Во-вторых, существует строгая теория, которая поддерживает его эффективность. Можно показать, что время запроса является сублинейным по размеру базы данных, т.е. быстрее, чем линейный поиск. Насколько быстрее зависит от того, сколько приближений мы можем терпеть.

Наконец, LSH совместим с любой нормой Lp для 0 < p <= 2. Поэтому, чтобы ответить на ваш первый вопрос, вы можете использовать LSH с евклидовой метрикой расстояния или с манхэттенской (L1) метрикой расстояния. Существуют также варианты расстояния Хэмминга и косинуса.

Достойный обзор был написан Malcolm Slaney и Michael Casey для IEEE Signal Processing Magazine в 2008 году [4].

LSH был применен, казалось бы, везде. Вы можете попробовать.

[1] Datar, Indyk, Immorlica, Mirrokni, "Схема хеширования с учетом локальных особенностей, основанная на p-стабильных распределениях", 2004.

[2] Вебер, Шек, Блотт, «Количественный анализ и исследование производительности для методов поиска сходства в многомерных пространствах», 1998.

[3] Gionis, Indyk, Motwani, «Поиск сходства в больших измерениях с помощью хеширования», 1999.

[4] Слэни, Кейси, «Хеширование с учетом локальных условий для поиска ближайших соседей», 2008.

I. Метрика расстояния

Во-первых, количество признаков (столбцов) в наборе данных не является фактором при выборе метрики расстояния для использования в kNN. Есть довольно много опубликованных исследований, направленных именно на этот вопрос, и обычные основы для сравнения:

• основное статистическое распределение ваших данных;

• связь между функциями, составляющими ваши данные (являются ли они независимыми - то есть как выглядит ковариационная матрица); и

• координатное пространство, из которого были получены ваши данные.

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

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

Он провалился только несколько раз, в каждом из этих случаев евклидово расстояние не удавалось, потому что базовая (декартова) система координат была плохим выбором. И вы обычно признаете это, потому что, например, длины пути (расстояния) больше не являются аддитивными - например, когда метрическое пространство является шахматной доской, манхэттенское расстояние лучше, чем евклидово, аналогично, когда метрическое пространство является Землей, а ваши расстояния транс -континентальные рейсы, метрика расстояния, подходящая для полярной системы координат, является хорошей идеей (например, от Лондона до Вены - 2,5 часа, от Вены до Санкт-Петербурга - еще 3 часа, более или менее в том же направлении, но от Лондона до Санкт-Петербурга Петербург не 5,5 часов, а чуть более 3 часов.)

Но кроме тех случаев, когда ваши данные принадлежат не декартовой системе координат, выбор метрики расстояния обычно не является существенным. (См. Это сообщение в блоге от студента CS, сравнивая несколько метрик расстояния, изучая их влияние на классификатор kNN - квадраты хи дают лучшие результаты, но различия не велики; более подробное исследование содержится в академической статье, Сравнительное исследование Функции расстояния для ближайших соседей - Махаланобис (по существу евклидово, нормализованное для учета ковариации измерений) был лучшим в этом исследовании.

Одно важное условие: чтобы расчеты расстояния были значимыми, необходимо изменить масштабваши данные - редко можно построить модель kNN для генерации точных прогнозов без этого. Например, если вы строите модель kNN для прогнозирования спортивных результатов, а вашими переменными ожидания являются рост (см), вес (кг), жировые отложения (%) и пульс покоя (ударов в минуту), тогда типичная точка данных может выглядеть примерно так: [180.4, 66.1, 11.3, 71]. Очевидно, что при расчете расстояния будет доминировать рост, а вклад% жира в организме будет практически незначительным. Иными словами, если вместо этого данные были представлены по-другому, так что вес тела был в граммах, а не в килограммах, тогда исходное значение 86,1 было бы 86,100, что сильно повлияло бы на ваши результаты, а это именно то, что вы делаете. не хочу

X_new = (X_old - mu) / sigma

II. Структура данных

Если вас беспокоит производительность структуры дерева kd, то тесселяция Вороного - это концептуально простой контейнер, но он значительно улучшит производительность и масштабируется лучше, чем kd-Trees.

Это не самый распространенный способ сохранения данных обучения kNN, хотя применение VT для этой цели, а также вытекающие из этого преимущества производительности хорошо документированы (см., Например, этот отчет Microsoft Research ). Практическое значение этого заключается в том, что, если вы используете основной язык (например, в индексе TIOBE ), вам следует найти библиотеку для выполнения VT. Я знаю, что в Python и R есть несколько вариантов для каждого языка (например, пакет voronoi для R доступен на CRAN )

Использование VT для kNN работает так:

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

Как выбрать центры Вороного? Я использую два ортогональных руководства. После случайного выбора точек w, рассчитайте VT для ваших тренировочных данных. Затем проверьте количество точек данных, назначенных каждому центру Вороного - эти значения должны быть примерно одинаковыми (с учетом равномерной плотности точек по всему пространству данных). В двух измерениях это приведет к VT с тайлами одинакового размера. Это первое правило, вот второе. Выберите w с помощью итерации - запустите алгоритм kNN с w в качестве параметра переменной и измерьте производительность (время, необходимое для возврата прогноза путем запроса VT).

Итак, представьте, что у вас есть миллион точек данных ..... Если бы точки были сохранены в обычной двухмерной структуре данных или в дереве kd, вы бы выполнили в среднем пару миллионов вычислений расстояния для каждойновые точки данных, ответная переменная которых вы хотите предсказать. Конечно, эти расчеты выполняются на одном наборе данных. С помощью V / T поиск ближайшего соседа выполняется в два этапа один за другим по двум различным группам данных - сначала по центрам Вороного, затем, как только ближайший центр найден, точки внутри ячейки соответствуют этот центр ищется, чтобы найти фактического ближайшего соседа (путем последовательных вычислений расстояния). В совокупности эти два поиска выполняются намного быстрее, чем один поиск методом "грубой силы". Это легко увидеть: предположим, что для 1М точек данных вы выбираете 250 центров Вороного, чтобы тесселяровать пространство данных. В среднем каждая ячейка Вороного будет иметь 4000 точек данных. Таким образом, вместо выполнения в среднем 500 000 вычислений расстояния (грубой силы), вы выполняете намного меньше, в среднем всего 125 + 2000.

III. Расчет результата (прогнозируемая переменная ответа)

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

W / r / t первый компонент, вы можете определить наилучшее значение n, решив задачу оптимизации (очень похоже на оптимизацию по методу наименьших квадратов). Это теория; на практике большинство людей просто используют n = 3. В любом случае, просто запустить алгоритм kNN для набора тестовых экземпляров (для расчета прогнозируемых значений) для n = 1, n = 2, n = 3 и т. Д. И отобразить ошибку как функцию от n. Если вы просто хотите получить правдоподобное значение для n, опять же, просто используйте n = 3.

Второй компонент - как взвешивать вклад каждого из соседей (предполагая, что n> 1).

Самым простым методом взвешивания является просто умножение каждого соседа на весовой коэффициент, который равен 1 / (dist * K), или обратное расстояние от этого соседа до тестового экземпляра, часто умноженное на некоторую эмпирически выведенную константу, K. I я не фанат этой техники, потому что она часто перевешивает ближайших соседей (и одновременно перевешивает более отдаленных); Значение этого в том, что данный прогноз может почти полностью зависеть от одного соседа, что, в свою очередь, увеличивает чувствительность алгоритма к шуму.

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

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Чтобы вычислить прогнозируемое значение, используя ваш код kNN, вы должны определить n ближайших соседей к точке данных, чью переменную ответа вы хотите предсказать («тестовый экземпляр»), а затем вызвать функцию weight_gauss, один раз для каждого из n соседей, передав на расстоянии между каждым соседом контрольной точки. Эта функция возвращает вес для каждого соседа, который затем используется в качестве коэффициента этого соседа в средневзвешенном расчете.

То, с чем вы сталкиваетесь, известно как проклятие размерности . Иногда полезно запустить алгоритм, такой как PCA или ICA, чтобы убедиться, что вам действительно нужны все 21 измерение и, возможно, найти линейное преобразование, которое позволит вам использовать менее 21 с примерно таким же качеством результата.

Обновление: я столкнулся с ними в книге Rangayyan под названием «Биомедицинская обработка сигналов» (надеюсь, я правильно ее помню). ICA - не тривиальная методика, но она была разработана исследователями в Финляндии, и я думаю, что код Matlab для нее доступен для скачивания. PCA - более широко используемый метод, и я полагаю, что вы сможете найти его R или другую программную реализацию. PCA выполняется путем итерационного решения линейных уравнений. Я сделал это слишком давно, чтобы вспомнить как. знак равно

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

Лучшие ответы хорошие, но старые, поэтому я хотел бы добавить ответ 2016 года .

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

Горячие темы, которые могут быть достойны:

1. Современные подходы ЛШ , такие как Разенштейн .
2. Лес RKD : Лес (ы) рандомизированных деревьев kd (RKD), как описано в FLANN , или в более позднем подходе, частью которого я был, kd-GeRaF .
3. LOPQ, что означает локально оптимизированное квантование продукта, как описано здесь . Это очень похоже на новый подход Бабенко + Лемптицкий .

Вы также можете проверить мои соответствующие ответы:

1. Два набора точек с высокой размерностью: найдите ближайшего соседа в другом наборе
2. Сравнение времени выполнения запросов Nearest Neighbor для разных структур данных
3. PCL KD-дерево реализации очень медленно

Чтобы ответить на ваши вопросы один за другим:

• Нет, евклидово расстояние - плохая метрика в многомерном пространстве. В основном в больших измерениях точки данных имеют большие различия между собой. Это уменьшает относительную разницу в расстоянии между данной точкой данных и ее ближайшим и самым дальним соседом.
• Есть много работ / исследований в данных высокого измерения, но большинство вещей требует большой математической сложности.
• KD-дерево плохо подходит для многомерных данных ... избегайте его всеми средствами

Вот хорошая статья, чтобы вы начали в правильном направлении. " Когда в ближайшем соседе значимо ?" Бейер и все.

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

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

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

Известно, что метод k Nearest Neighbor является вычислительно дорогим. Это одна из основных причин, по которой люди обращаются к другим алгоритмам, таким как машины опорных векторов.

KD-деревья действительно не очень хорошо работают с многомерными данными. Поскольку шаг сокращения больше не помогает, поскольку самый близкий край - 1-мерное отклонение - почти всегда будет меньше, чем полноразмерное отклонение от известных ближайших соседей.

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

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

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

Многое зависит от того, почему вы хотите знать ближайших соседей. Вы можете заглянуть в алгоритм среднего смещения http://en.wikipedia.org/wiki/Mean-shift, если вы действительно хотите найти режимы своего набора данных.

Я думаю, что косинус на tf-idf логических функций будет хорошо работать для большинства проблем. Это потому, что его проверенная временем эвристика используется во многих поисковых системах, таких как Lucene. Евклидово расстояние в моем опыте показывает плохие результаты для любых текстовых данных. Выбор различных весовых коэффициентов и k-примеров можно выполнить с помощью обучающих данных и выбора параметров грубой силы.

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

Я испытал ту же проблему и могу сказать следующее.

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

2. Значение k можно найти опытным путем. Вы можете попробовать разные значения и проверить полученные кривые ROC или какую-то другую меру точности / отзыва, чтобы найти приемлемое значение.

3. Как евклидовы, так и манхэттенские расстояния учитывают неравенство треугольника , поэтому вы можете использовать их в метрических деревьях. Действительно, производительность KD-деревьев сильно ухудшается, когда данные имеют более 10 измерений (я сам сталкивался с этой проблемой). Я считаю VP-деревья лучшим вариантом.

Деревья KD отлично работают для 21 измерения, если вы уйдете рано, посмотрев, скажем, 5% всех точек. FLANN делает это (и другие ускорения), чтобы соответствовать 128-мерным векторам SIFT. (К сожалению, FLANN использует только евклидову метрику, а быстрый и надежный scipy.spatial.cKDTree - только метрики Lp; они могут или не могут быть адекватны вашим данным.) Конечно, здесь есть компромисс между скоростью и точностью.

(Если бы вы могли описать свои Ndata, Nquery, распределение данных, это могло бы помочь людям попробовать похожие данные.)

Добавлено 26 апреля, время выполнения cKDTree с отсечкой на моем старом компьютере Mac, чтобы дать очень грубое представление о возможности:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

Вы можете попробовать кривая z порядка. Это легко для 3 измерения.

Является ли евклидово расстояние хорошей метрикой для поиска ближайших соседей? Если нет, каковы мои варианты?

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

Алгоритм кластеризации типа k-средних для подпространственной кластеризации смешанных числовых и категориальных наборов данных