Более быстрый способ сравнить два набора точек в N-мерном пространстве?

Question

List1 содержит большое количество (~ 7 ^ 10) N-мерных точек (N <= 10), <strong>List2 содержит такое же или меньшее количество N-мерных точек (N <= 10). </p>

Моя задача заключается в следующем: я хочу проверить, какая точка в List2 является ближайшей ( евклидово расстояние ) к точке в List1 для каждой точки в List1, и затем выполнить некоторую операцию над ней. Я делал это простым способом с вложенными циклами, когда у меня не было более 50 баллов в List1, но с 7 ^ 10 баллами это, очевидно, отнимает много времени.

Какой самый быстрый способ сделать это? Какие-нибудь концепции из вычислительной геометрии могут помочь?

РЕДАКТИРОВАТЬ: У меня есть следующее на месте, я построил kd-дерево из List2 , а затем сейчас я делаю поиск ближайших окрестностей для каждой точки в List1 . Теперь, как я изначально указывал, List1 имеет 7 ^ 10 баллов, и, следовательно, хотя я экономлю на грубой силе, метод евклидова расстояния для каждой пары, огромное количество точек в List1 вызывает много времени. Можно ли как-нибудь улучшить это?

Answer 1

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

http://www.cs.umd.edu/~mount/ANN/

Answer 2

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

Первый алгоритм не работает & mdash; по двум причинам: (1) неверное предположение - я предполагаю, что ограничивающие оболочки не пересекаются, и (2) неправильное прочтение вопроса - он не находит кратчайшего края для каждой пары точек.

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

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

Второй алгоритм: частичный

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

Perfomance

Когда List2 является чем-то вроде равномерно распределенного или нормально распределенного по некоторой довольно наклонной форме, это поможет сократить количество рассматриваемых точек и должно быть совместимо с предложением kd-дерева.

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

Моя оценка

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

Answer 3

(Год спустя) деревья kd, которые рано уходят, после просмотра, скажем, 1M из всех 200M точек может быть намного быстрее в больших размерах.
Результаты только статистически близки к абсолютному ближайшему, в зависимости от данных и метрики; нет бесплатного обеда.
(Обратите внимание, что выборка из 1M точек, а из дерева kd только из 1M, совсем другая, хуже.)

FLANN делает это для данных изображения с dim = 128, и я верю в opencv. Локальный мод быстрого и солидного SciPy cKDTree также имеет обрезание =.

Answer 4

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

Я уверен, что вокруг есть библиотеки, но иногда приятно знать, что происходит - Бентли хорошо это объясняет.

По сути, существует несколько способов поиска дерева: Ближайшие N соседей, Все соседи в пределах данного радиуса, Ближайшие N соседей в пределах радиуса. Иногда вы хотите искать ограниченные объекты.

Идея состоит в том, что kdTree рекурсивно разделяет пространство. Каждый узел делится на 2 по оси в одном из измерений пространства, в котором вы находитесь. В идеале он разделяется перпендикулярно самому длинному измерению узла. Вы должны продолжать делить пространство, пока у вас не будет около 4 точек в каждом ведре.

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

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

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