Если у меня два массива:
X = np.random.rand(10000,2)
Y = np.random.rand(10000,2)
Как я могу определить для каждой точки в X, какая точка в Y ближе всего к ней? Итак, в итоге у меня есть массив, показывающий:
x1_index y_index_of_closest
1 7
2 54
3 3
... ...
Я хочу сделать это для обоих столбцов в X и сравнить каждый с каждым столбцом и значением в Y
Этот вопрос довольно популярен. Поскольку подобные вопросы здесь закрываются и связываются, я думаю, стоит отметить, что, хотя существующие ответы довольно быстрые для тысяч точек данных, после этого они начинают разрушаться. Моя картофельная ошибка составляет 10 тыс. Элементов в каждом массиве.
Потенциальная проблема с другими ответами - алгоритмическая сложность. Они сравнивают все в X со всем в Y. Чтобы обойти это, по крайней мере в среднем, нам нужна лучшая стратегия для исключения некоторых вещей в Y.
В одном измерении это легко - просто отсортируйте все и начните выявлять ближайших соседей. В двух измерениях существует множество стратегий, но KD-деревья довольно популярны и уже реализованы в стеке scipy. На моей машине есть кроссовер между различными методами примерно в той точке, где каждый из X и Y содержит по 6 тыс. Элементов.
from scipy.spatial import KDTree
tree = KDTree(X)
neighbor_dists, neighbor_indices = tree.query(Y)
Чрезвычайно низкая производительность реализации KDTree scipy какое-то время была для меня болезненным местом, особенно когда на ее основе было построено столько всего. Вероятно, есть наборы данных, в которых он работает хорошо, но я еще не видел ни одного.
Если вы не возражаете против дополнительной зависимости, вы можете получить увеличение скорости в 1000 раз, просто переключив библиотеку KDTree. Пакет pykdtree можно установить с помощью pip, и я в значительной степени гарантирую, что пакеты conda тоже работают нормально. При таком подходе мой бюджетный Chromebook может обрабатывать X и Y с 10 миллионами точек каждый всего за 30 секунд. Это превосходит segfaulting в 10 тысяч баллов со временем стены;)
from pykdtree.kdtree import KDTree
tree = KDTree(X)
neighbor_dists, neighbor_indices = tree.query(Y)
pykdtree потрясающе, ты спас мне день! Для всех, кто заинтересован, у меня есть два 2D-массива по 32 м (A) и 200 тыс. (B) каждый, мне нужно найти ближайшую точку данных в A для всех элементов в B, я пробовал подход KDTree scipy и scikit-learn в @ Ответ Даниэля, они оказываются неприемлемо медленными, но расчет выполняется менее чем за одну секунду с pykdtree. Я не эксперт в KDTree, но это волшебство! Вот что я обнаружил: pykdtree ›scikit-learn KDtree (Зависает при размерах массива (32 м, 200 КБ))› scipy.spatial.distance.cdist (Ошибка памяти при размерах массива (300 КБ, 200 КБ)).
- person zyxue; 19.09.2018
Это, наверное, самый частый вопрос (я сам дважды отвечал на него за последнюю неделю), но, поскольку его можно сформулировать миллионами способов:
import numpy as np
import scipy.spatial.distance.cdist as cdist
def withScipy(X,Y): # faster
return np.argmin(cdist(X,Y,'sqeuclidean'),axis=0)
def withoutScipy(X,Y): #slower, using broadcasting
return np.argmin(np.sum((X[None,:,:]-Y[:,None,:])**2,axis=-1), axis=0)
Также существует метод только с numpy, использующий einsum, который быстрее, чем моя функция (но не cdist), но я не понимаю ее достаточно хорошо, чтобы это объяснить.
EDIT + = 21 месяц:
Однако лучший способ сделать это алгоритмически - использовать KDTree.
from sklearn.neighbors import KDTree
# since the sklearn implementation allows return_distance = False, saving memory
y_tree = KDTree(Y)
y_index_of_closest = y_tree.query(X, k = 1, return_distance = False)
@HansMusgrave имеет довольно хорошее ускорение для KDTree ниже.
И для завершения, ответ np.einsum, который я теперь понимаю:
np.argmin( # (X - Y) ** 2
np.einsum('ij, ij ->i', X, X)[:, None] + # = X ** 2 \
np.einsum('ij, ij ->i', Y, Y) - # + Y ** 2 \
2 * X.dot(Y.T), # - 2 * X * Y
axis = 1)
@Divakar хорошо объясняет этот метод на странице вики своего пакет eucl_dist
