43

x - y座標の 2 つの配列があり、一方の配列の各点と他方の配列のすべての点の間の最小ユークリッド距離を見つけたいと考えています。配列は必ずしも同じサイズではありません。例えば：

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 ループをなくして、2 つの配列間で要素ごとの計算を行う方法はありますか? 各行または列の最小要素を見つけることができる距離行列を生成することを想定しています。

問題を見る別の方法。xy1(長さm ) とxy2(長さp ) をxy(長さn )に連結し、元の配列の長さを格納するとします。理論的には、 mxp サブマトリックスを取得できる座標から nxn 距離マトリックスを生成できるはずです。この部分行列を効率的に生成する方法はありますか?

4

7 に答える 7

46

（数か月後） scipy.spatial.distance.cdist( X, Y ) XとYの距離のすべてのペアを示します。2薄暗い、3薄暗い...
また、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
于 2010-06-27T16:22:18.993 に答える
30

距離の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（2つの軸に沿ったスカラー差の）2つのそのような行列を作成し、.hypot呼び出しはそれらを（スカラーユークリッド距離の）同じ形状の行列に変換します。

于 2009-12-09T04:44:54.250 に答える
5

あなたがやろうとしていることについて：

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])
于 2009-12-09T04:34:52.923 に答える
0

平方を計算するために組み込みの方法を使用することを強くお勧めします。根は、最適化された方法で計算するようにカスタマイズされており、オーバーフローに対して非常に安全です。

以下の@alexの回答は、オーバーフローに関して最も安全であり、非常に高速である必要があります。また、単一の点については、2 つ以上の次元をサポートするようになった math.hypot を使用できます。

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

安全性の懸念

i, j, k = 1e+200, 1e+200, 1e+200
math.hypot(i, j, k)
# np.hypot for 2d points
# 1.7320508075688773e+200

np.sqrt(np.sum((np.array([i, j, k])) ** 2))
# RuntimeWarning: overflow encountered in square

オーバーフロー/アンダーフロー/速度

于 2021-09-26T10:35:22.497 に答える