поиск ближайшего соседа для python numpy.ndarray в 3d-пространстве

У меня есть numpy.ndarray 3d-точек, т.е. его np.shape (4350,3) и такой второй numpy.ndarray 3d-точек np.shape (10510,3). Теперь я пытаюсь найти правильный python-пакет, чтобы как можно быстрее вычислить ближайших соседей во втором массиве точек в первом массиве.

Я нашел здесь очень похожий вопрос: найти k ближайших соседей точки в трехмерном пространстве с помощью python numpy, но я не понимаю, как использовать это решение для моей проблемы.

Я был бы очень, очень признателен за вашу помощь в этом!


python-3.x python numpy numpy-ndarray nearest-neighbor
person Studentu    schedule 09.01.2019    source источник
comment
Это одноразовая операция или вы собираетесь найти несколько ближайших соседей в одном и том же наборе? Я спрашиваю об этом, потому что, если это одна операция, и вы буквально каждый раз ищете только 1 точку в новых наборах, тогда простой 1 цикл времени, ищущий наименьшее квадратное расстояние, будет достаточным и будет самым быстрым.   -  person Victor 'Chris' Cabral    schedule 09.01.2019
comment
@Victor'Chris'Cabral Нет, до сих пор я реализовал поиск ближайшего соседа путем вычисления евклидова расстояния для каждой точки первого набора для каждой точки второго (4350 * 10510 = 45718500 раз) и возвращение точки для ближайших расстояний. Но все это я делаю в цикле while, который выполняется ~20 раз и для нескольких первых наборов точек, так что этот наивный классический подход занимает несколько часов.   -  person Studentu    schedule 09.01.2019
comment
Я определенно оговорился. Теперь я вижу твою проблему.   -  person Victor 'Chris' Cabral    schedule 09.01.2019
comment
Я бы предложил сделать kdtree из меньшего набора, а затем выполнить цикл. docs.scipy.org/doc/ scipy-0.14.0/ссылка/генерируется/   -  person Victor 'Chris' Cabral    schedule 09.01.2019
comment
@Victor'Chris'Cabral Спасибо за ссылку и предложение! Я читал эту документацию раньше, но я не знаю, как применить ее к моей проблеме (извините, если это должно быть ясно из документации, я не очень хорошо разбираюсь в программировании). Не могли бы вы привести пример того, как это может выглядеть для моей задачи (я имею в виду вообще для двух 3D-наборов точек)?   -  person Studentu    schedule 09.01.2019
comment
Недавно я сам работал над проблемой kdtree. Вот отличный учебник.   -  person Ic3fr0g    schedule 09.01.2019
comment
@ lc3fr0g Спасибо за ссылки! На мой вопрос дан ответ, но я обязательно посмотрю видео.   -  person Studentu    schedule 10.01.2019

Ответы (1)


arrow_upward
6
arrow_downward

Вот KDTree способ:

from scipy.spatial import KDTree

data= np.random.rand(10510,3)
sample= np.random.rand(4350,3)
kdtree=KDTree(data)

Затем dist,points=kdtree.query(sample,2) даст вам 2 лучших соседей для 4350 кандидатов примерно за одну секунду.

person B. M.    schedule 09.01.2019
comment
Большое спасибо, я попробую этот способ, а затем дам вам знать, если это сработало! - person Studentu; 10.01.2019
comment
Извините, я не понимаю, что означают результаты kdtree.query(sample,2). Я ожидал, что в dist есть евклидовы (поскольку параметр 2 обозначает евклидово расстояние) расстояния до ближайших соседей, а точки - это точки из данных набора точек, которые находятся ближе всего к выборке. Но dist выглядит следующим образом: print(dist) [[0.02731417 0.03267154] [0.02175954 0.04624616] ... [0.03183459 0.03818426] [0.01794547 0.03079906]] и точки примерно так: print(points) [[ 262 567] .. [696 9467][9617 1987]] так что я явно не прав. - person Studentu; 10.01.2019
comment
О, я думаю, что kdtree.query(sample,2) интерпретируется как kdtree.query(sample, k=2) вместо kdtree.query(sample, p=2), но мне нужно последнее, верно? - person Studentu; 10.01.2019
comment
нет p=2 по умолчанию. k для k-ближайших точек. если вам нужен только ближайший kdtree.query(sample,1) или kdtree.query(sample) достаточно, так как k=1 по умолчанию. - person B. M.; 10.01.2019
comment
Да, это то, что я имел в виду. Спасибо за ответ, очень приятно, что вы помогли! - person Studentu; 10.01.2019