更快地计算每个点与剩余 n-1 点之间的距离

Question

我有 n 点，我必须计算每个点与其余 n-1 点之间的欧氏距离。我在 python 中使用了以下方法：

for eachRow in range(0, numberOfPoints):
        distanceProximityMatrix.append([])

    print('Initialisation Completed')
    for i in range(0, numberOfPoints):
        if(i%100 == 0) : print('.', end = '')
        for j in range(i, numberOfPoints):
            if(i != j):
                tempDist = distanceForMultivariate(recordsList[i], recordsList[j], attributesToBeUsed, isFirstColumnID = isFirstColumnID)
                distanceProximityMatrix[i].append(tempDist) 
                distanceProximityMatrix[j].append(tempDist)
            else :
                distanceProximityMatrix[i].append(0)

有没有更快的方法来做到这一点，因为我拥有的点数相当大，并且这个策略需要大量时间。

注意：distanceForMultivariate 函数计算欧氏距离。

Answer 1

我在这里假设 2D 点。那么欧氏距离就是：

sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

我们这里有以下操作：

• 2 减法
• 2 次乘法
• 添加1个
• 1 平方根

如果您只需要比较距离（例如，找到最近的邻居），您可以完全删除 sqrt，因为它保留了顺序。但请注意，它们不要变得很大，如果您想稍后对这些值求和，它们可能会变得很大。

三角形方程不成立，所以不要在必要的地方使用它（所以没有寻路或基本上在任何需要计算距离的地方！）：

if sqrt(a) + sqrt(b) >= sqrt(c), then
a + b <= a + 2sqrt(a*b) + b = (sqrt(a) + sqrt(b)) ^2 >= sqrt(c)^2 = c

sqrt(100) + sqrt(1) >= sqrt(121)

但是

100 + 1 < 121

话虽如此，如果您确实需要所有距离，我认为您无法降低复杂性，因为无论如何，您都在计算 O(n^2) 值。

[由于申请现已明确而更新]

虽然我认为我的解决方案适用于找到最近的邻居，但实际上有更好的算法可以解决该问题，然后计算所有点对的距离。例如，kd-trees。

这个问题的答案可能会有所帮助：如何在高维数据中高效地找到k近邻？

Answer 2

如果只是想找到最近的

k

点，你觉得这个怎么样？
首先将第一个

k

点放入某个排序数组中（基于到源点的距离），然后计算最大距离，称之为

d_max

。
对于每个新点

p

，请执行以下检查：

if (x_p - x_start > d_max) or (y_p - y_start > d_max)
then disregard(x)
else:
  d = distance (x, start);
  if d < d_max 
  then:
    insert_into_array(x) // obviously the array must stay sorted
    d_max = distance(array[k],start)

背后的想法是：如果X坐标或Y坐标之间的差值大于最大距离，那么距离也会更大。

例如
假设你的起点是 (2,2)，并且你已经添加了 (2,6)、(2,3) 和 (3,2)，那么 d_max 将为 4。 你的其他点是（10,0）、（0,20）和（5,6），那么会发生以下情况：

Add (10,0)? No, because 10 - 2 > 4 (x_p - x_start > d_max)
Add (0,20)? No, because 20 - 2 > 4 (y_p - y_start > d_max)
Add (5,6) ? Maybe: 5 - 2 <= d_max (X-coordinates) => ok
                   6 - 2 <= d_max (Y-coordinates) => ok
                   distance((5,6),(2,2)) = 5, which is larger than 4 => don't add (5,6)

显然，您需要创建某种“数组”：

• 您可以在中间的某个位置添加一个点，以便其他点相应地移动（链接列表）。
• 如果您添加一个点并且已经有

  k

  条目，则应删除最后一个条目。

由于只需比较距离，无需计算平方根。

Answer 3

计算点 point 和 pointlist 之间的距离的一种极其快速的方法是 numpy 中的 einsum 函数：

    deltas = pointlist - point
    dist_2 = np.einsum('ij,ij->i', deltas, deltas) #squared distance.

对于 n=1e8 点，这在我的机器上只需要 1 秒。

import numpy as np
import time

n = int( 1e8 )
x_test = np.random.uniform(0,1000, n )
y_test = np.random.uniform(0,1000, n )
xy = np.vstack(( x_test, y_test )).T


t0 = time.perf_counter()     
dist_x0 = argmin_dist( [ x_test[0], y_test[0] ] , xy[1:])
print('Argmin dist took', np.round( time.perf_counter() - t0, 4) , 's')