我在二维空间中有一组点,需要计算每个点到其他点的距离。
我的点数量相对较少,可能最多 100 个。但是因为我需要经常快速地执行此操作,以确定这些移动点之间的关系,并且因为我知道迭代这些点可能会像由于 O(n^2) 复杂度很糟糕,我正在寻找利用 numpy 的矩阵魔法(或 scipy)的方法。
在我的代码中,每个对象的坐标都存储在其类中。但是,当我更新类坐标时,我也可以在 numpy 数组中更新它们。
class Cell(object):
"""Represents one object in the field."""
def __init__(self,id,x=0,y=0):
self.m_id = id
self.m_x = x
self.m_y = y
我想到创建一个欧几里德距离矩阵来防止重复,但也许你有一个更聪明的数据结构。
我也愿意接受漂亮算法的指导。
此外,我注意到有类似的问题涉及欧几里德距离和 numpy,但没有找到任何直接解决有效填充全距离矩阵的问题。
您可以利用
complex
类型:
# build a complex array of your cells
z = np.array([complex(c.m_x, c.m_y) for c in cells])
# mesh this array so that you will have all combinations
m, n = np.meshgrid(z, z)
# get the distance via the norm
out = abs(m-n)
网格划分是主要思想。但是
numpy
很聪明,所以你不必生成 m
& n
。只需使用 z
的转置版本来计算差异即可。网格是自动完成的:
out = abs(z[..., np.newaxis] - z)
而如果直接将
z
设置为二维数组,则可以使用z.T
来代替奇怪的z[..., np.newaxis]
。最后,你的代码将如下所示:
z = np.array([[complex(c.m_x, c.m_y) for c in cells]]) # notice the [[ ... ]]
out = abs(z.T-z)
>>> z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])
>>> abs(z.T-z)
array([[ 0. , 2.23606798, 4.12310563],
[ 2.23606798, 0. , 4.24264069],
[ 4.12310563, 4.24264069, 0. ]])
作为补充,您可能想在之后删除重复项,取上三角形:
>>> np.triu(out)
array([[ 0. , 2.23606798, 4.12310563],
[ 0. , 0. , 4.24264069],
[ 0. , 0. , 0. ]])
>>> timeit.timeit('abs(z.T-z)', setup='import numpy as np;z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])')
4.645645342274779
>>> timeit.timeit('abs(z[..., np.newaxis] - z)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
5.049334864854522
>>> timeit.timeit('m, n = np.meshgrid(z, z); abs(m-n)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
22.489568296184686
如果不需要全距离矩阵,最好使用kd-tree。考虑
scipy.spatial.cKDTree
或 sklearn.neighbors.KDTree
。这是因为 kd 树可以在 O(n log n) 时间内找到 k 个近邻,因此可以避免计算所有 n 乘 n 距离的 O(n**2) 复杂性。
Jake Vanderplas 在 Python Data Science Handbook 中使用广播给出了这个示例,这与 @shx2 提出的非常相似。
import numpy as np
rand = random.RandomState(42)
X = rand.rand(3, 2)
dist_sq = np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis = -1)
dist_sq
array([[0. , 0.18543317, 0.81602495],
[0.18543317, 0. , 0.22819282],
[0.81602495, 0.22819282, 0. ]])
以下是使用 numpy 的方法:
import numpy as np
x = np.array([0,1,2])
y = np.array([2,4,6])
# take advantage of broadcasting, to make a 2dim array of diffs
dx = x[..., np.newaxis] - x[np.newaxis, ...]
dy = y[..., np.newaxis] - y[np.newaxis, ...]
dx
=> array([[ 0, -1, -2],
[ 1, 0, -1],
[ 2, 1, 0]])
# stack in one array, to speed up calculations
d = np.array([dx,dy])
d.shape
=> (2, 3, 3)
现在剩下的就是计算沿 0 轴的 L2 范数(如此处所述):
(d**2).sum(axis=0)**0.5
=> array([[ 0. , 2.23606798, 4.47213595],
[ 2.23606798, 0. , 2.23606798],
[ 4.47213595, 2.23606798, 0. ]])
如果您正在寻找最有效的计算方式 - 请使用 SciPy 的
cdist()
(或者 pdist()
,如果您只需要成对距离向量而不是全距离矩阵),如 Tweakimp 的评论中所建议的。正如他所说,它比 RichPauloo 和 shx2 提出基于矢量化和广播的方法快得多。原因是 SciPy 的 cdist()
和 pdist()
在底层使用 for
循环和 C 实现 进行度量计算,这甚至比矢量化更快。
顺便说一句,如果您可以使用 SciPy 并且仍然更喜欢使用广播的方法,则不必自己实现它,因为
distance_matrix()
函数是纯 Python 实现,它利用了广播和矢量化(源代码,文档)。
值得一提的是,
cdist()
/pdist()
也比广播内存方式更有效,因为它逐个计算距离并避免创建n*n*d
元素数组,其中n
是点数,d
是点的维数。
我进行了一些简单的实验来比较 SciPy 的
cdist()
、distance_matrix()
和 NumPy 中的广播实现的性能。我使用 Python 时间模块中的 perf_counter_ns()
来测量时间,所有结果都是使用 np.float64
数据类型在 2D 空间中 10000 个点上运行 10 次的平均值(在 Python 3.8.10、配备 Ryzen 2700 和 16 GB RAM 的 Windows 10 上测试) :
cdist()
- 0.6724sdistance_matrix()
- 3.0128s如果有人想重现实验,请编写代码:
from scipy.spatial import *
import numpy as np
from time import perf_counter_ns
def dist_mat_custom(a, b):
return np.sqrt(np.sum(np.square(a[:, np.newaxis, :] - b[np.newaxis, :, :]), axis=-1))
results = []
size = 10000
it_num = 10
for i in range(it_num):
a = np.random.normal(size=(size, 2))
b = np.random.normal(size=(size, 2))
start = perf_counter_ns()
c = distance_matrix(a, b)
#c = dist_mat_custom(a, b)
#c = distance.cdist(a, b)
results.append(perf_counter_ns() - start)
print(np.mean(results) / 1e9)
如果你有归一化的向量,你通常可以使用余弦相似度,它的计算速度要快得多(按数量级):
dist_matrix = 1 - np.matmul(vectors, vectors.T)
请注意,它与欧几里德距离不同,但在比较距离时给出相同的结果。
它对于巨大的距离矩阵可能很有用。