使用 Numpy 求一组点的平均距离

Question

我有一个未知维度空间中的点数组，例如：

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

我想找到所有点之间的平均欧氏距离。

请注意，我有超过 20,000 积分，所以我想尽可能高效地完成此操作。

谢谢。

Answer 1

如果您可以访问 scipy，您可以尝试以下操作：

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

Answer 2

嗯，我不认为有一种超级快速的方法可以做到这一点，但这应该可以做到：

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

Answer 3

既然您已经说明了查找异常值的目标，那么您最好计算样本均值以及样本方差，因为这两个操作都会为您提供 O(nd) 操作。这样，您应该能够找到异常值（例如，排除比标准偏差的某些分数更远离平均值的点），并且该过滤过程应该可以在 O(nd) 时间内执行，总共 O( nd）。

您可能有兴趣回顾一下切比雪夫不等式。

Answer 4

在没有可行的解决方案的情况下是否值得进行优化？ 此外，在整个数据集上计算距离矩阵很少需要很快，因为您只需执行一次 - 当您需要知道两点之间的距离时，您只需查找它，它已经计算出来了。

因此，如果您没有地方开始，这里就是一个。 如果你想在 Numpy 中执行此操作，而不需要编写任何内联 fortran 或 C，那应该没问题，尽管你可能想要包含这个名为“numexpr”的小型基于向量的虚拟机（在 PyPI 上可用，微不足道）安装），在这种情况下，与单独使用 Numpy 相比，性能提升了 5 倍。

下面我计算了 2D 空间中 10,000 个点的 距离矩阵（一个 10K x 10k 矩阵给出了所有 10k 点之间的距离）。在我的 MBP 上这花了 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 5

无法回避评估的数量：

Sum[n-i, {i, 0, n}] = http://www.equationsheet.com/latexrender/pictures/27744c0bd81116aa31c138ab38a2aa87.gif

但是，如果你能得到近似结果，你就可以节省所有这些平方根的费用。 这取决于您的需求。

如果您要计算平均值，我建议您在计算之前不要尝试将所有值放入数组中。 只需计算总和（如果还需要标准差，则计算平方和）并在计算时丢弃每个值。

自从 和 ，我不知道这是否意味着你必须在某个地方乘以二。

Answer 6

如果您想要快速且不精确的解决方案，您可以采用 Fast Multipole Method 算法。

相距较小距离的点对最终平均距离的贡献较小，因此将点分组为簇并比较簇距离是有意义的。

Answer 7

在一组点（1D）中，“欧氏距离”只是点之间的差异，您可以使用

np.diff

非常轻松地计算它们的平均值：

import numpy as np

arr = np.array([10,80,50,5,25,4])
avg = np.mean (    abs ( np.diff(arr)  )     )
print(avg)

打印：

37.2

如果您想考虑结果平均值中的负差异，则可以排除

abs

。祝你好运。