使用Numpy计算一组点的平均距离

Question

我有一个包含很多点的数组，这些点在一个不知道维度的空间里，比如：

data=numpy.array(
[[ 115, 241, 314],
[ 153, 413, 144],
[ 535, 2986, 41445]])

我想要计算这些点之间的平均欧几里得距离。

请注意，我有超过20,000个点，所以我希望能尽可能高效地完成这个计算。

谢谢。

Answer 1

在没有一个可用的解决方案的情况下，优化代码真的有必要吗？而且，计算整个数据集的距离矩阵通常不需要很快，因为你只会做一次这个计算——当你想知道两个点之间的距离时，你只需要查一下，那个距离已经算好了。

所以，如果你不知道从哪里开始，这里有个建议。如果你想用Numpy来做这个，而不想写任何内联的Fortran或C代码，那完全没问题。不过，你可能想要使用一个叫做“numexpr”的小型向量虚拟机（可以在PyPI上找到，安装也很简单），在这种情况下，它的性能比单独使用Numpy快了5倍。

下面我计算了一个距离矩阵，包含了10,000个二维空间的点（这是一个10K x 10K的矩阵，显示所有10K点之间的距离）。在我的MacBook Pro上，这个计算花了59秒。

import numpy as NP
import numexpr as NE

# data are points in 2D space (x, y)--obviously, this code can accept data of any dimension
x = NP.random.randint(0, 10, 10000)
y = NP.random.randint(0, 10, 10000)
fnx = lambda q : q - NP.reshape(q, (len(q), 1))
delX = fnx(x)
delY = fnx(y)
dist_mat = NE.evaluate("(delX**2 + delY**2)**0.5")

Answer 2

如果你能使用scipy这个库，可以试试下面的方法：

scipy.spatial.distance.cdist(data,data)

Answer 3

嗯，我觉得没有特别快的方法来做到这一点，不过这个方法应该可以解决问题：

tot = 0.

for i in xrange(data.shape[0]-1):
    tot += ((((data[i+1:]-data[i])**2).sum(1))**.5).sum()

avg = tot/((data.shape[0]-1)*(data.shape[0])/2.)