Как эффективно найти k-ближайших соседей в высокоразмерных данных?

Question

Так у меня есть около 16 000 75-мерных точек данных, и для каждой точки я хочу найти его K ближайших соседей (используя евклидово расстояние, в настоящее время к = 2, если это делает его easiser)

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

Моя следующая идея будет использовать PCA (основной компонентный анализ), чтобы уменьшить количество измерений, но мне было интересно: есть ли какой-нибудь умный алгоритм или структура данных, чтобы решить это именно в разумные сроки?

Answer 1

Статья Википедии для KD-деревьев имеет ссылку на ANN library:

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

Основываясь на собственном опыте, ANN выполняет достаточно эффективен для точечных множеств в размере от тысячи до сотни тысяч, а в размеров достигают 20. (Для применения в значительно более высоких размерах, результаты довольно пятнистые, но вы можете попробовать его в любом случае.)

Насколько обеспокоены структуры алгоритма/данные:

Библиотека реализует ряд различных структур данных на основе kd-деревьев и box-decomposition trees, и использует несколько различных стратегий поиска .

Я бы попробовал это сначала напрямую, и если это не принесет удовлетворительных результатов, я бы использовал его с набором данных после применения PCA/ICA (так как маловероятно, что вы закончите с небольшим количеством измерений для обработки kd-дерева).

Answer 2

Возможно, вы можете использовать Morton Codes, но с 75 размерами они будут огромными. И если у вас всего 16 000 точек данных, исчерпывающий поиск не должен занять слишком много времени.

Answer 3

Нет причин полагать, что это NP-комплект. Вы ничего не оптимизируете, и мне сложно определить, как преобразовать это в другую проблему с NP-полным (у меня есть Garey and Johnson на моей полке и не могу найти ничего подобного). На самом деле, я бы просто начал более эффективные методы поиска и сортировки. Если у вас есть n наблюдений, вам нужно рассчитать n x n расстояний прямо вверх. Затем для каждого наблюдения вам нужно выбрать лучших k ближайших соседей. Это n в квадрате для вычисления расстояния, n log (n) для сортировки, но вы должны делать sort n раз (разные для КАЖДОГО значения n). Беспорядочное, но все же полиномиальное время, чтобы получить ответы.

Answer 4

BK-Tree - не такая уж плохая мысль. Взгляните на Nick's Blog on Levenshtein Automata. В то время как его фокус - это струны, он должен дать вам весеннюю доску для других подходов. Другая вещь, о которой я могу думать, - R-Trees, однако я не знаю, были ли они обобщены для больших размеров. Я не могу сказать больше, потому что я не использовал их напрямую и не реализовал их сам.

Answer 5

Очень часто реализация будет рода ближайших соседей массива, что вы рассчитали для каждой точки данных. Поскольку сортировка всего массива может быть очень дорогостоящей, вы можете использовать такие методы, как косвенная сортировка, например, Numpy.argpartition в библиотеке Python Numpy для сортировки только ближайших значений K, которые вам интересны. Не нужно сортировать весь массив.

@ Ответ Grembo выше должен быть значительно сокращен. так как вам нужны только K близкие значения. и нет необходимости сортировать все расстояния от каждой точки.

Если вам просто нужны соседи K, этот метод будет очень хорошо уменьшать ваши вычислительные затраты и сложность по времени.

если вам нужно отсортированные соседей K, сортировать выход снова

см

Documentation for argpartition

Answer 6

использовать KD-дерево

К сожалению, в больших размерах этой структуры данных сильно страдает от curse of dimensionality, что заставляет его время поиска быть сопоставимым с грубой силой se архипелаг

уменьшить количество измерений

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

По точности я имею в виду поиск точного ближайшего соседства (NN).

Анализ основных компонентов (PCA) - это хорошая идея, когда вы хотите уменьшить размерное пространство, в котором живут ваши данные.

Есть ли какой-нибудь умный алгоритм или структура данных, чтобы решить это именно в разумные сроки?

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

Этот подход требует вашей точности, но значительно повышает производительность. Более того, вероятность нахождения хорошего NN (достаточно близкого к запросу) относительно высока.

Вы можете узнать больше об ANNS во введении нашего kd-GeRaF paper.

Хорошая идея - объединить ANNS с уменьшением размерности.

Чувствительность на месте (LSH) - это современный подход к решению проблемы Nearest Neighbor в высоких измерениях. Основная идея заключается в том, что точки, которые лежат близко друг к другу, хэшируются в одно и то же ведро. Поэтому, когда запрос приходит, он будет хэширован в ведро, где это ведро (и обычно его соседние) содержит хорошие кандидаты NN).

FALCONN - хорошая реализация на С ++, которая фокусируется на схожих косинусах. Еще одна хорошая реализация - наш DOLPHINN, который является более общей библиотекой.