计算python中numpy的欧几里德距离

Question

我是Python的新手,所以这个问题可能看起来很琐碎.但是,我没有找到类似的情况.我有一个20个节点的坐标矩阵.我想计算此集合中所有节点对之间的欧氏距离,并将它们存储在成对矩阵中.例如,如果我有20个节点,我希望最终结果是(20,20)的矩阵,每个节点对之间的欧几里德距离值.我尝试使用for循环遍历坐标集的每个元素并计算欧氏距离,如下所示:

ncoord=numpy.matrix('3225   318;2387    989;1228    2335;57      1569;2288  8138;3514   2350;7936   314;9888    4683;6901   1834;7515   8231;709   3701;1321    8881;2290   2350;5687   5034;760    9868;2378   7521;9025   5385;4819   5943;2917   9418;3928   9770')
n=20 
c=numpy.zeros((n,n))
for i in range(0,n):
    for j in range(i+1,n):
        c[i][j]=math.sqrt((ncoord[i][0]-ncoord[j][0])**2+(ncoord[i][1]-ncoord[j][1])**2)

但是,我收到的错误是"输入必须是方阵".我想知道是否有人知道这里发生了什么.谢谢

Answer 1

为此使用嵌套for循环有很多,更快的替代方法.我将向您展示两种不同的方法 - 第一种将是一种更为通用的方法,它将向您介绍广播和矢量化,第二种方法将使用更方便的scipy库函数.

1.一般方式,使用广播和矢量化

我建议做的第一件事就是转而使用np.array而不是np.matrix.出于多种原因,阵列是优选的,最重要的是因为它们可以具有> 2维度,并且它们使得元素乘法更加笨拙.

import numpy as np

ncoord = np.array(ncoord)

使用数组,我们可以for通过插入新的单例维度并在其上广播减法来消除嵌套循环:

# indexing with None (or np.newaxis) inserts a new dimension of size 1
print(ncoord[:, :, None].shape)
# (20, 2, 1)

# by making the 'inner' dimensions equal to 1, i.e. (20, 2, 1) - (1, 2, 20),
# the subtraction is 'broadcast' over every pair of rows in ncoord
xydiff = ncoord[:, :, None] - ncoord[:, :, None].T

print(xydiff.shape)
# (20, 2, 20)

这相当于使用嵌套for循环遍历每对行,但更快,更快!

xydiff2 = np.zeros((20, 2, 20), dtype=xydiff.dtype)
for ii in range(20):
    for jj in range(20):
        for kk in range(2):
            xydiff[ii, kk, jj] = ncoords[ii, kk] - ncoords[jj, kk]

# check that these give the same result
print(np.all(xydiff == xydiff2))
# True

其余的我们也可以使用矢量化操作:

# we square the differences and sum over the 'middle' axis, equivalent to
# computing (x_i - x_j) ** 2 + (y_i - y_j) ** 2
ssdiff = (xydiff * xydiff).sum(1)

# finally we take the square root
D = np.sqrt(ssdiff)

整个过程可以像这样在一行中完成:

D = np.sqrt(((ncoord[:, :, None] - ncoord[:, :, None].T) ** 2).sum(1))

2.懒惰的方式,使用 pdist

事实证明,已经有一个快速方便的功能来计算所有成对距离:scipy.spatial.distance.pdist.

from scipy.spatial.distance import pdist, squareform

d = pdist(ncoord)

# pdist just returns the upper triangle of the pairwise distance matrix. to get
# the whole (20, 20) array we can use squareform:

print(d.shape)
# (190,)

D2 = squareform(d)
print(D2.shape)
# (20, 20)

# check that the two methods are equivalent
print np.all(D == D2)
# True

Answer 2

for i in range(0, n):
    for j in range(i+1, n):
        c[i, j] = math.sqrt((ncoord[i, 0] - ncoord[j, 0])**2 
        + (ncoord[i, 1] - ncoord[j, 1])**2)

注意：ncoord[i, j]与ncoord[i][j]Numpy矩阵不同。这似乎是混淆的根源。如果ncoord是 Numpy数组，则它们将给出相同的结果。

对于numpy的矩阵，ncoord[i]返回第i行的ncoord，这本身就是一个numpy的矩阵与你的情况形状1×2对象。因此，ncoord[i][j]实际上意味着：取第i行的ncoord 和取第j行一个1×2的矩阵。这就是当j> 0时出现索引问题的地方。

关于您对分配给c[i][j]“工作”的评论，它不应该。至少在我构建的 Numpy 1.9.1 中，如果您的索引i和j迭代到n.

顺便说一句，请记住将矩阵的转置添加c到自身。

建议使用 Numpy 数组而不是矩阵。看到这个帖子。

如果您的坐标存储为 Numpy 数组，则成对距离可以计算为：

from scipy.spatial.distance import pdist

pairwise_distances = pdist(ncoord, metric="euclidean", p=2)

或者干脆

pairwise_distances = pdist(ncoord)

因为默认度量是“欧几里得”，默认“p”是 2。

在下面的评论中，我错误地提到 pdist 的结果是 anxn 矩阵。要获得 anxn 矩阵，您需要执行以下操作：

from scipy.spatial.distance import pdist, squareform

pairwise_distances = squareform(pdist(ncoord))

或者

from scipy.spatial.distance import cdist

pairwise_distances = cdist(ncoord, ncoord)