python - 点集之间的成对位移向量

我在N维度d中有一个(N, d)点数组，我想为每个对(N choose 2, d)的所有位移矢量制作一个新数组。如果我只想要这些向量的大小，则可以使用 pdist 中的 scipy.spatial.distance 。

如果我能做的话那太好了

pdist(points, lambda u, v: u - v)

但metric函数必须返回标量(ValueError: setting an array element with a sequence.)

我的解决方案是使用np.triu_indices:

i, j = np.triu_indices(len(points), 1)
displacements = points[i] - points[j]

这比使用pdist慢大约20-30倍(我比较displacements的大小，尽管这不是耗时的部分，我认为这实际上是在制作上三角形并运行花式索引)。

最佳答案

直截了当

dis_vectors = [l - r for l, r in itertools.combinations(points, 2)]

但我怀疑它很快。实际上%timeit说:

3分:

list : 13 us
pdist: 24 us

但已经有27分:

list : 798 us
pdist: 35.2 us

我们在这里谈几点？

另一种可能性像

import numpy
from operator import mul
from fractions import Fraction

def binomial_coefficient(n,k):
    # credit to http://stackoverflow.com/users/226086/nas-banov
    return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

def pairwise_displacements(a):
    n = a.shape[0]
    d = a.shape[1]
    c = binomial_coefficient(n, 2)

    out = numpy.zeros( (c, d) )

    l = 0
    r = l + n - 1
    for sl in range(1, n): # no point1 - point1!
        out[l:r] = a[:n-sl] - a[sl:]
        l = r
        r += n - (sl + 1)
    return out

这简单地使数组在所有维度上相对于其自身“滑动”，并在每个步骤中执行(可广播的)减法。请注意，不考虑重复，也没有相等的对(例如point1-point1)。

使用31.3ms时，此功能在1000分范围内仍然表现良好，而使用pdist时，20.7 ms仍然更快，而使用1.23 s时，列表理解排名第三。