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

Question

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

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 единиц. Мы предполагаем, что это в 2D-пространстве.

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

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

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

Answer 1

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

Предварительные условия: Установите 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,

Answer 2

Использовать sklearn.neighbors

      from sklearn.neighbors import NearestNeighbors

#----- Creating example data start -------
number_of_points = 10
x_vect = np.sin(range(number_of_points))
y_vect = np.cos(range(number_of_points))
coords_vect = np.vstack([x_vect, y_vect]).T 
#----- Creating example data end -------

knn = NearestNeighbors(n_neighbors=3)
knn.fit(coords_vect)
distance_mat, neighbours_mat = knn.kneighbors(coords_vect)

Полученные результаты:

      neighbours_mat = array([[0, 6, 7],
                        [1, 7, 8],
                        [2, 8, 9],
                        [3, 9, 4],
                        [4, 3, 5],
                        [5, 6, 4],
                        [6, 0, 5],
                        [7, 1, 0],
                        [8, 2, 1],
                        [9, 3, 2]], dtype=int64)

Обратите внимание, что первый столбец — это сам узел, второй столбец — ближайший сосед, третий столбец — второй ближайший сосед. Вы можете получить больше соседей, увеличив n_neighbors@ NearestNeighbors(n_neighbors=3)инициализация. distance_matявляются расстояниями каждого узла от его соседей, обратите внимание, что каждый узел имеет расстояние 0 до себя, поэтому первый столбец всегда равен нулю:

      distance_mat = array([[0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.95885108],
                      [0.        , 0.95885108, 0.95885108],
                      [0.        , 0.95885108, 0.95885108],
                      [0.        , 0.28224002, 0.95885108],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646]])

Нанесение точек:

      plt.figure()
plt.scatter(x_vect, y_vect)
for x,y, label in zip (x_vect, y_vect, range(number_of_points)):
    plt.text(x,y,label)