Минимальное евклидово расстояние между точками в двух разных массивах Numpy, не находящееся в пределах
-
18-09-2019 - |
Вопрос
У меня есть два массива x-y координаты, и я хотел бы найти минимальное евклидово расстояние между каждый укажите в одном массиве с ВСЕ точки в другом массиве.Массивы не обязательно должны быть одинакового размера.Например:
xy1=numpy.array(
[[ 243, 3173],
[ 525, 2997]])
xy2=numpy.array(
[[ 682, 2644],
[ 277, 2651],
[ 396, 2640]])
Мой текущий метод перебирает каждую координату xy
в xy1
и вычисляет расстояния между этой координатой и другими координатами.
mindist=numpy.zeros(len(xy1))
minid=numpy.zeros(len(xy1))
for i,xy in enumerate(xy1):
dists=numpy.sqrt(numpy.sum((xy-xy2)**2,axis=1))
mindist[i],minid[i]=dists.min(),dists.argmin()
Есть ли способ исключить цикл for и каким-то образом выполнять поэлементные вычисления между двумя массивами?Я предполагаю создать матрицу расстояний, для которой я мог бы найти минимальный элемент в каждой строке или столбце.
Можно по-другому взглянуть на проблему.Скажем, я объединяю xy1
(длина m) и xy2
(длина p) в xy
(длина n), и я сохраняю длины исходных массивов.Теоретически, тогда я должен быть в состоянии сгенерировать n x n матрица расстояний от тех координат, из которых я могу получить m x p подматрица.Есть ли способ эффективно сгенерировать эту подматрицу?
Решение
(Месяцы спустя)
scipy.spatial.distance.cdist( X, Y )
задает все пары расстояний,
для X и Y 2 dim, 3 dim...
Он также содержит 22 различных нормы, детализированных
здесь .
# cdist example: (nx,dim) (ny,dim) -> (nx,ny)
from __future__ import division
import sys
import numpy as np
from scipy.spatial.distance import cdist
#...............................................................................
dim = 10
nx = 1000
ny = 100
metric = "euclidean"
seed = 1
# change these params in sh or ipython: run this.py dim=3 ...
for arg in sys.argv[1:]:
exec( arg )
np.random.seed(seed)
np.set_printoptions( 2, threshold=100, edgeitems=10, suppress=True )
title = "%s dim %d nx %d ny %d metric %s" % (
__file__, dim, nx, ny, metric )
print "\n", title
#...............................................................................
X = np.random.uniform( 0, 1, size=(nx,dim) )
Y = np.random.uniform( 0, 1, size=(ny,dim) )
dist = cdist( X, Y, metric=metric ) # -> (nx, ny) distances
#...............................................................................
print "scipy.spatial.distance.cdist: X %s Y %s -> %s" % (
X.shape, Y.shape, dist.shape )
print "dist average %.3g +- %.2g" % (dist.mean(), dist.std())
print "check: dist[0,3] %.3g == cdist( [X[0]], [Y[3]] ) %.3g" % (
dist[0,3], cdist( [X[0]], [Y[3]] ))
# (trivia: how do pairwise distances between uniform-random points in the unit cube
# depend on the metric ? With the right scaling, not much at all:
# L1 / dim ~ .33 +- .2/sqrt dim
# L2 / sqrt dim ~ .4 +- .2/sqrt dim
# Lmax / 2 ~ .4 +- .2/sqrt dim
Другие советы
Чтобы вычислить матрицу расстояний m на p, это должно работать:
>>> def distances(xy1, xy2):
... d0 = numpy.subtract.outer(xy1[:,0], xy2[:,0])
... d1 = numpy.subtract.outer(xy1[:,1], xy2[:,1])
... return numpy.hypot(d0, d1)
тот .outer
вызовы создают две такие матрицы (скалярных разностей по двум осям), .hypot
вызовы превращают их в матрицу одинаковой формы (скалярных евклидовых расстояний).
Для того, что вы пытаетесь сделать:
dists = numpy.sqrt((xy1[:, 0, numpy.newaxis] - xy2[:, 0])**2 + (xy1[:, 1, numpy.newaxis - xy2[:, 1])**2)
mindist = numpy.min(dists, axis=1)
minid = numpy.argmin(dists, axis=1)
Редактировать:Вместо того, чтобы звонить sqrt
, делая квадраты и т. д., вы можете использовать numpy.hypot
:
dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1])
Принятый ответ не полностью отвечает на вопрос, который требует найти минимум расстояние между двумя наборами точек, а не расстояние между каждый очко в двух сетах.
Хотя простое решение исходного вопроса действительно состоит в вычислении расстояния между каждый пары и последующего нахождения минимальной, в этом нет необходимости, если нас интересует только минимум расстояния.Для последней проблемы существует гораздо более быстрое решение.
Все предложенные решения имеют время работы, которое масштабируется как m*p = len(xy1)*len(xy2)
.Это нормально для небольших наборов данных, но можно написать оптимальное решение, масштабируемое как m*log(p)
, что дает огромную экономию для крупных xy2
наборы данных.
Это оптимальное масштабирование времени выполнения может быть достигнуто с помощью scipy.spatial.cKDTree следующее
import numpy as np
from scipy import spatial
xy1 = np.array(
[[243, 3173],
[525, 2997]])
xy2 = np.array(
[[682, 2644],
[277, 2651],
[396, 2640]])
# This solution is optimal when xy2 is very large
tree = spatial.cKDTree(xy2)
mindist, minid = tree.query(xy1)
print(mindist)
# This solution by @denis is OK for small xy2
mindist = np.min(spatial.distance.cdist(xy1, xy2), axis=1)
print(mindist)
где mindist
минимальное расстояние между каждой точкой в xy1
и набор точек в xy2
import numpy as np
P = np.add.outer(np.sum(xy1**2, axis=1), np.sum(xy2**2, axis=1))
N = np.dot(xy1, xy2.T)
dists = np.sqrt(P - 2*N)