Более быстрый способ сравнить два набора точек в N-мерном пространстве?
List1 содержит большое количество (~7^10) N-мерных точек (N <= 10), List2 содержит такое же или меньшее количество N-мерных точек (N <=10).
Моя задача заключается в следующем: я хочу проверить, какая точка в List2 является ближайшей (евклидово расстояние) к точке в List1 для каждой точки в List1, и впоследствии выполнить некоторую операцию над ней. Я делал это простым способом с вложенными циклами, когда у меня не было более 50 баллов в List1, но с 7 ^ 10 баллами это, очевидно, отнимает много времени.
Какой самый быстрый способ сделать это? Какие-нибудь концепции из вычислительной геометрии могут помочь?
РЕДАКТИРОВАТЬ: У меня есть следующее на месте, я построил kd-дерево из List2, а затем я делаю поиск ближайших окрестностей для каждой точки в List1. Теперь, как я первоначально указал, List1 имеет 7 ^ 10 баллов, и, следовательно, хотя я экономлю на грубой силе, методе евклидова расстояния для каждой пары, огромное количество точек в List1 вызывает много времени. Есть ли способ, которым я могу улучшить это?
4 ответа
Хорошо, хороший способ - использовать что-то вроде kd-дерева и выполнить поиск ближайшего соседа. К счастью, вам не нужно реализовывать эту структуру данных самостоятельно, это было сделано раньше. Я рекомендую этот, но есть и другие:
Невозможно сказать вам, какой алгоритм является наиболее эффективным, не зная ничего о распределении точек в двух решениях. Впрочем, на первый взгляд...
Первый алгоритм не работает - по двум причинам: (1) неверное предположение - я предполагаю, что ограничивающие оболочки не пересекаются, и (2) неправильное прочтение вопроса - он не находит кратчайшего ребра для каждой пары точек.
... вычислить выпуклую оболочку из двух наборов: ближайшие точки должны быть на гиперповерхности на двух корпусах, через которые проходит линия между двумя центрами тяжести.
Вы можете вычислить выпуклую оболочку, вычислив центральные точки, центр тяжести, предполагая, что все точки имеют одинаковую массу, и упорядочив списки от самого дальнего от центра до наименее дальнего. Затем возьмите самую дальнюю точку в списке, добавьте ее к выпуклой оболочке, а затем удалите все точки, которые находятся в вычисленной до сих пор выпуклой оболочке (для этого вам потребуется вычислить много 10d гипертреугольников). Повторите, пока в списке не осталось ничего, кроме выпуклой оболочки.
Второй алгоритм: частичный
Вычислить выпуклую оболочку для List2. Для каждой точки List1, если точка находится за пределами выпуклой оболочки, найдите гиперграницу, как для первого алгоритма: ближайшая точка должна быть на этой грани. Если это на лице, аналогично. Если он внутри, вы все равно можете найти гиперграницу, продолжив линию после точки из List1: ближайшая точка должна быть внутри шара, которая включает гиперграницу до центра тяжести List2: здесь, однако, вам нужен новый алгоритм, чтобы получить ближайшая точка, возможно, подход KD-дерева.
Perfomance
Когда List2 представляет собой что-то вроде равномерно распределенного или нормально распределенного по некоторой довольно наклонной форме, это поможет сократить количество рассматриваемых точек и должно быть совместимо с предложением kd-дерева.
Однако есть некоторые ужасные случаи сусла: если List2 содержит только точки на поверхности тора, геометрический центр которого является центром тяжести списка, то выпуклая оболочка будет очень дорогой для вычисления и не сильно поможет в уменьшении количество рассматриваемых баллов.
Моя оценка
Эти виды геометрических методов могут быть полезным дополнением к подходу kd-деревьев других плакатов, но вам нужно немного узнать о распределении точек, прежде чем вы сможете определить, стоит ли их применять.
KD-дерево довольно быстро. Я использовал алгоритм в этой статье, и он хорошо работает Bentley - деревья Kd для полудинамических множеств точек
Я уверен, что вокруг есть библиотеки, но иногда приятно знать, что происходит - Бентли хорошо это объясняет.
В основном, существует несколько способов поиска дерева: Ближайшие N соседей, Все соседи в пределах данного радиуса, Ближайшие N соседей в пределах радиуса. Иногда вы хотите искать ограниченные объекты.
Идея состоит в том, что kdTree рекурсивно разделяет пространство. Каждый узел делится на 2 по оси в одном из измерений пространства, в котором вы находитесь. В идеале он разделяется перпендикулярно самому длинному измерению узла. Вы должны продолжать делить пространство, пока у вас не будет около 4 точек в каждом ведре.
Затем для каждой точки запроса, когда вы рекурсивно посещаете узлы, вы проверяете расстояние от до разделительной стены для конкретного узла, в котором вы находитесь. Вы опускаетесь на оба узла (тот, в котором вы находитесь и его брат), если расстояние до разделительной стены ближе, чем радиус поиска. Если стена находится за пределами радиуса, просто найдите дочерние элементы узла, в котором вы находитесь.
Когда вы попадаете в ведро (листовой узел), вы проверяете точки там, чтобы увидеть, находятся ли они в радиусе.
Если вы хотите самую близкую точку, вы можете начать с массивного радиуса и передать указатель или ссылку на нее, когда вы повторяете - и таким образом вы можете уменьшить радиус поиска, когда вы находите близкие точки - и расположиться в самой близкой точке достаточно быстро.
(Год спустя) Деревья kd, которые уходят рано, после просмотра, скажем, 1M из всех 200M точек, могут быть намного быстрее в больших измерениях.
Результаты только статистически близки к абсолютному ближайшему, в зависимости от данных и метрики; Там нет бесплатного обеда.
(Обратите внимание, что выборка 1M точек, а kd tree только тех 1M, совсем другая, хуже.)
FLANN делает это для данных изображений с dim=128, и я верю в opencv. Локальный мод быстрого и надежного SciPy cKDTree также имеет обрезку = .