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

Question

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

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

我想找出所有点之间的平均欧几里得距离。

请注意，我有超过20,000个点，因此我希望尽可能高效地完成这项任务。

谢谢。

- Mel Kaye

---

我建议您将此标记为算法问题。您真的在尝试找到一种比朴素的O(dn^2)更好的算法，其中d是维度，n是这些点的数量。这可以轻松地并行化为n个操作，每个操作的运行时间为O(nd)，可以在O(n)时间内合并，但考虑到您不会拥有20,000个处理器，似乎您正在寻找一种更有效的算法...所以也许有人可以给出一个好的对手论证，说明它为什么是Omega(dn^2)，或者有人可以想出一个聪明的方法来更快地完成它... - Michael Aaron Safyan

你需要所有的距离，还是只需要满足某些要求的距离？ - Seamus Connor

如果你只需要找到离群值，为什么不找到分布的平均点（平均 x、平均 y、平均 z），并使用距离该点的标准偏差来确定离群值。 这将是一个O(N)算法，而不是您目前使用的O(N^2)算法。 - Justin Peel

@Justin，你抢先发了我的帖子。 - Michael Aaron Safyan

如果你的数据在R空间中有一定的正态分布，Grubbs'测试可能是一个不错的选择。它只需要计算平均点和标准差即可。http://en.wikipedia.org/wiki/Grubbs'_test_for_outliers - Philippe Beaudoin

Answer 1

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

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

（注：cdist函数可计算数据之间的距离）

- Nick

---

我认为 OP 实际上想要使用 scipy.spatial.distance.pdist。 - Keith

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

- Justin Peel

---

这在1.86 GHz Win32机器上运行大约需要35秒。如果对您的应用程序来说可以接受，我建议使用它。@Justin - 几个小错误：你应该有 tot += (...).mean()，和 avg = tot/(data.shape[0]-1)。 - mtrw

@mtrw 我同意之前有个bug - 我把总数除以了错误的数字，但现在我已经修复了它。 - Justin Peel

Answer 3

有没有一个有效的解决方案，优化是否值得进行？另外，整个数据集的距离矩阵计算很少需要快速完成，因为您只需要在需要知道两点之间的距离时查找即可，它已经被计算出来了。

所以，如果您没有起点，这里有一个。如果您想在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")

- doug

Answer 4

无论如何，评估的数量都是不可避免的：

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

但如果您能够使用近似结果，则可以节省所有这些平方根的费用。这取决于您的需求。

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

由于 和 ，我不知道这是否意味着您必须在某个地方乘以二。

- duffymo

Answer 5

现在您已经表明了找到异常值的目标，最好计算样本均值和样本方差，因为这两个操作都将给您一个O(nd)操作。有了这个，您应该能够找到异常值（例如，排除比某个标准差的一些倍数更远离平均值的点），并且该过滤过程应该可以在O(nd)时间内执行，总共是O(nd)。

您可能对切比雪夫不等式需要进行复习。

- Michael Aaron Safyan

Answer 6

如果您想要一个快速但不太准确的解决方案，您可能可以改编快速多极子方法算法。

距离较近的点对最终平均距离的贡献较小，因此将点分组并比较群集之间的距离是有意义的。

- Luper Rouch