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

Question

Я только начал использовать scipy / numpy.У меня есть массив 100000 * 3, каждая строка - это координата и центральная точка 1 * 3.Я хочу рассчитать расстояние для каждой строки в массиве до центра и сохранить их в другом массиве.Какой самый эффективный способ сделать это?

Answer 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 быстрее в ~ 35 раз).

Answer 2

Я бы использовал реализацию sklearn евклидова расстояния. Преимущество заключается в использовании более эффективного выражения с использованием умножения матриц:

dist(x, y) = sqrt(dot(x, x) - 2 * dot(x, y) + dot(y, y)

Простой скрипт будет выглядеть так:

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 / стабильный / модули / полученные / sklearn.metrics.pairwise.euclidean_distances.html # sklearn.metrics.pairwise.euclidean_distances

Я использую этот подход для обработки больших массивов данных (10000, 10000) с некоторыми незначительными изменениями, такими как использование функции np.einsum.

Answer 3

Это может не дать прямого ответа на ваш вопрос, но если вы после всех перестановок пар частиц, я обнаружил, что следующее решение в некоторых случаях быстрее, чем функция 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

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

Answer 4

Вы также можете использовать разработку нормы (аналогично замечательным тождествам). Это, вероятно, самый эффективный способ вычисления расстояния матрицы точек.

Вот фрагмент кода, который я первоначально использовал для реализации k-Nearest-Neighbours в Octave, но вы можете легко адаптировать его к numpy, поскольку он использует только умножения матриц (эквивалент numpy.dot ()): 1003 *

% 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;

Answer 5

#is it true, to find the biggest distance between the points in surface?

from math import sqrt

n = int(input( "enter the range : "))
x = list(map(float,input("type x coordinates: ").split()))
y = list(map(float,input("type y coordinates: ").split()))
maxdis = 0  
for i in range(n):
    for j in range(n):
        print(i, j, x[i], x[j], y[i], y[j])
        dist = sqrt((x[j]-x[i])**2+(y[j]-y[i])**2)
        if maxdis < dist:

            maxdis = dist
print(" maximum distance is : {:5g}".format(maxdis))

Answer 6

Возможно, вам потребуется более детально указать интересующую вас функцию расстояния, но вот очень простая (и эффективная) реализация квадратного евклидова расстояния на основе 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 - центр.