Эффективный расчет расстояния между N точками и ссылкой в numpy/scipy
Я только начал использовать scipy/numpy. У меня есть массив 100000 * 3, каждая строка - координата и 1 * 3 центральной точки. Я хочу рассчитать расстояние для каждой строки в массиве до центра и сохранить их в другом массиве. Каков наиболее эффективный способ сделать это?
Ответы
Ответ 1
Я бы посмотрел на scipy.spatial.distance.cdist
:
http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html
import numpy as np
import scipy
a = np.random.normal(size=(10,3))
b = np.random.normal(size=(1,3))
dist = scipy.spatial.distance.cdist(a,b) # pick the appropriate distance metric
dist
для удаленной метрики по умолчанию эквивалентно:
np.sqrt(np.sum((a-b)**2,axis=1))
хотя cdist
намного эффективнее для больших массивов (на моей машине для вашей проблемы с размером, cdist
быстрее в ~ 35x).
Ответ 2
Я использовал бы реализацию sklearn евклидова расстояния. Преимуществом является использование более эффективного выражения с использованием умножения матрицы:
dist(x, y) = sqrt(dot(x, x) - 2 * dot(x, y) + dot(y, y)
Простой script будет выглядеть так:
import numpy as np
x = np.random.rand(1000, 3)
y = np.random.rand(1000, 3)
dist = np.sqrt(np.dot(x, x)) - (dot(x, y) + dot(x, y)) + dot(y, y)
Преимущество этого подхода было хорошо описано в документации sklearn:
http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.euclidean_distances.html#sklearn.metrics.pairwise.euclidean_distances
Я использую этот подход для хрустания больших datamatrices (10000, 10000) с некоторыми незначительными модификациями, например, с использованием функции np.einsum.
Ответ 3
Вы также можете использовать разработку нормы (аналогично замечательным тождествам). Это, пожалуй, самый эффективный способ вычислить расстояние от матрицы точек.
Вот фрагмент кода, который я первоначально использовал для реализации k-Nearest-Neighbors, в Octave, но вы можете легко адаптировать его к numpy, поскольку он использует только умножения матриц (эквивалент numpy.dot()):
% Computing the euclidian distance between each known point (Xapp) and unknown points (Xtest)
% Note: we use the development of the norm just like a remarkable identity:
% ||x1 - x2||^2 = ||x1||^2 + ||x2||^2 - 2*<x1,x2>
[napp, d] = size(Xapp);
[ntest, d] = size(Xtest);
A = sum(Xapp.^2, 2);
A = repmat(A, 1, ntest);
B = sum(Xtest.^2, 2);
B = repmat(B', napp, 1);
C = Xapp*Xtest';
dist = A+B-2.*C;
Ответ 4
Вам может потребоваться указать более детальный способ, который вас интересует, но здесь очень простая (и эффективная) реализация Квадратное евклидово расстояние на основе inner product
(который, очевидно, может быть обобщен, прямолинейно, для других мер дистанции):
In []: P, c= randn(5, 3), randn(1, 3)
In []: dot(((P- c)** 2), ones(3))
Out[]: array([ 8.80512, 4.61693, 2.6002, 3.3293, 12.41800])
Где P
- ваши точки, а c
- центр.
Ответ 5
Это может не ответить на ваш вопрос напрямую, но если вы после перестановки пар частиц, я нашел следующее решение быстрее, чем функция pdist в некоторых случаях.
import numpy as np
L = 100 # simulation box dimension
N = 100 # Number of particles
dim = 2 # Dimensions
# Generate random positions of particles
r = (np.random.random(size=(N,dim))-0.5)*L
# uti is a list of two (1-D) numpy arrays
# containing the indices of the upper triangular matrix
uti = np.triu_indices(100,k=1) # k=1 eliminates diagonal indices
# uti[0] is i, and uti[1] is j from the previous example
dr = r[uti[0]] - r[uti[1]] # computes differences between particle positions
D = np.sqrt(np.sum(dr*dr, axis=1)) # computes distances; D is a 4950 x 1 np array
См. этот для более глубокого изучения этого вопроса в моем сообщении в блоге.