Поиск ближайшего соседа: Python

У меня есть двумерный массив:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

Первые два элемента MyArray[0] и MyArray[1] представляют собой координаты точек X и Y.

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

скажем для этого примера X = 6.

Я решил проблему, сравнивая каждый элемент с каждым другим элементом, но это занимает 15 минут или около того, когда ваш список имеет длину 22 000 пунктов. Мы надеемся в конечном итоге запустить это в списках примерно из 30 миллионов точек.

Я читал о деревьях K-d и понимаю основную концепцию, но у меня возникли проблемы с пониманием того, как их писать.


python numpy nearest-neighbor kdtree closest-points
person Dlinet    schedule 16.10.2012    source источник
comment
Что такое Kt-дерево? Вы имеете в виду k-d дерево? Для двухмерных точек вам понадобится только quadtree. Ранее был задан вопрос о реализации quadtree в Python: вопросы/6060302/   -  person Mark Reed    schedule 17.10.2012
comment
Спасибо! Я имел в виду k-d дерево. Я поищу четырехъядерное дерево.   -  person Dlinet    schedule 17.10.2012
comment
В модуле scipy.spatial есть реализация дерева k-d.   -  person John Vinyard    schedule 17.10.2012
comment
Обратите внимание на cKDTree, он намного быстрее.   -  person seberg    schedule 17.10.2012
comment
Я просмотрел оба из них, но не могу понять, как их использовать. Соответствующий пример кода был бы очень признателен!   -  person Dlinet    schedule 17.10.2012
comment
@Dlinet: ваше решение даст не самый близкий результат, а само себя, поскольку расстояние до самого себя равно 0! Вместо этого вы должны использовать k=2 и взять второй ближайший результат.   -  person jkflying    schedule 15.12.2012

Ответы (1)


arrow_upward
35
arrow_downward

Спасибо Джону Виньярду за предложение scipy. После некоторых хороших исследований и испытаний, вот решение этого вопроса:

Предварительные требования: установите Numpy и SciPy.

  1. Импорт модулей SciPy и Numpy

  2. Сделайте копию 5-мерного массива, включая только значения X и Y.

  3. Создайте экземпляр cKDTree как таковой:

    YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
#Play with the leafsize to get the fastest result for your dataset

  4. Запросите cKDTree для ближайшего соседа в пределах 6 единиц как таковых:

    for item in YourArray:
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

    для каждого элемента в YourArray, TheResult будет кортеж расстояния между двумя точками и индекс местоположения точки в YourArray.

person Dlinet    schedule 26.10.2012
comment
Как насчет ближайшего к одной конкретной точке, а не коллекции? - person Steve Yeago; 11.11.2015
comment
@SteveYeago query_ball_point кажется доступным для этого. - person ldavid; 25.01.2016