Эффективный расчет расстояния между N точками и ссылкой в ​​numpy/scipy

Ответ 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

См. этот для более глубокого изучения этого вопроса в моем сообщении в блоге.