最小歐幾里德距離，而不是內

Question

我有X兩個數組 - ÿ座標，並且我想找到在一個陣列與每個點之間的最小歐幾里得距離全部其他陣列中的點。數組不一定是相同的大小。例如：

xy1=numpy.array(
[[ 243, 3173], 
[ 525, 2997]]) 

xy2=numpy.array(
[[ 682, 2644], 
[ 277, 2651], 
[ 396, 2640]]) 

我的當前方法遍歷每個座標在xy1xy並且計算的距離之間的座標和其他座標。

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（長度米）和xy2（長度p）插入xy（長度Ñ）和I存儲原始陣列的長度。從理論上講，我應該能夠從這些座標中產生一個距離矩陣，我可以從這些座標中獲取一個子矩陣。有沒有辦法有效地生成這個子矩陣？

Answer 1

（個月以後） scipy.spatial.distance.cdist(X, Y) 給出了所有對距離的， X和Y 2暗淡，3 ...暗淡
它還執行22個不同的規範，詳細 here。

# 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 

Answer 2

對於你想做什麼：

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]) 

Answer 3

要計算米由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調用將這些矩陣變成相同形狀的矩陣（標量歐式距離）。

Answer 4

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) 

Answer 5

接受的答案不能完全解決問題，它要求以發現兩套點之間的最小的距離，不是兩套每點之間的距離。

Altough一個直接的解決方案，以原來的問題確實由計算距離之間的每一個對和susequently找到最小的一個的，這如果是隻在最小距離感興趣的是沒有必要的。後一個問題存在更快的解決方案。

所有建議的解決方案的運行時間的比例爲m*p = len(xy1)*len(xy2)。對於小數據集，這是可以的，但可以編寫一個最佳解決方案，其規模爲m*log(p)，爲大數據集生成大量節省。

該最佳執行時間縮放可以使用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