欧式距离的高效精确计算

Question

经过一些在线研究（ 1 、 2 、 numpy 、 scipy 、 scikit 、 math ），我发现了几种 在 Python 中计算欧氏距离的 方法：

 # 1
numpy.linalg.norm(a-b)

# 2
distance.euclidean(vector1, vector2)

# 3
sklearn.metrics.pairwise.euclidean_distances

# 4
sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)

# 5
dist = [(a - b)**2 for a, b in zip(vector1, vector2)]
dist = math.sqrt(sum(dist))

# 6
math.hypot(x, y)

我想知道是否有人可以提供关于以上哪一项（ _或我没有发现的任何其他项_）在 效率 和 精度 方面被认为是最好的见解。如果有人知道讨论该主题的任何 _资源_，那也很好。

我感兴趣的 上下文 是计算数字元组对之间的欧几里得距离，例如 (52, 106, 35, 12) 和 (33, 153, 75, 10) 之间的距离。

原文由 user6167676 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

先说结论：

从使用 timeit 进行效率测试的测试结果，我们可以得出 关于效率的 结论：

Method5 (zip, math.sqrt) > Method1 (numpy.linalg.norm) > Method2 (scipy.spatial.distance) > Method3 (sklearn.metrics.pairwise.euclidean_distances )

虽然我没有真正测试你的 Method4 因为它不适合一般情况，它通常等同于 Method5 。

对于其余部分，令人惊讶的是， Method5 是最快的。而对于使用 Method1 的 numpy ，正如我们预期的那样，它在 C 中进行了大量优化，是第二快的。

对于 scipy.spatial.distance ，如果你直接进入函数定义，你会看到它实际上使用了 numpy.linalg.norm ，除了它会在实际之前对两个输入向量执行验证 numpy.linalg.norm 。这就是为什么它比 numpy.linalg.norm 稍慢。

最后对于 sklearn ，根据文档：

与其他计算距离的方法相比，该公式有两个优点。首先，它在处理稀疏数据时计算效率高。其次，如果一个参数发生变化而另一个参数保持不变，则可以预先计算 dot(x, x) 和/或 dot(y, y)。但是，这不是进行此计算的最精确方法，并且此函数返回的距离矩阵可能不会按要求完全对称

由于在你的问题中你想使用一组固定的数据，所以这种实现的优势没有体现出来。并且由于性能和精度之间的权衡，它也给出了所有方法中最差的精度。

关于精确度， Method5 = Metho1 = --- = Method2 = --- = --- = ----------------- = Method3

效率测试脚本：

 import numpy as np
from scipy.spatial import distance
from sklearn.metrics.pairwise import euclidean_distances
import math

# 1
def eudis1(v1, v2):
    return np.linalg.norm(v1-v2)

# 2
def eudis2(v1, v2):
    return distance.euclidean(v1, v2)

# 3
def eudis3(v1, v2):
    return euclidean_distances(v1, v2)

# 5
def eudis5(v1, v2):
    dist = [(a - b)**2 for a, b in zip(v1, v2)]
    dist = math.sqrt(sum(dist))
    return dist

dis1 = (52, 106, 35, 12)
dis2 = (33, 153, 75, 10)
v1, v2 = np.array(dis1), np.array(dis2)

import timeit

def wrapper(func, *args, **kwargs):
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

wrappered1 = wrapper(eudis1, v1, v2)
wrappered2 = wrapper(eudis2, v1, v2)
wrappered3 = wrapper(eudis3, v1, v2)
wrappered5 = wrapper(eudis5, v1, v2)
t1 = timeit.repeat(wrappered1, repeat=3, number=100000)
t2 = timeit.repeat(wrappered2, repeat=3, number=100000)
t3 = timeit.repeat(wrappered3, repeat=3, number=100000)
t5 = timeit.repeat(wrappered5, repeat=3, number=100000)

print('\n')
print('t1: ', sum(t1)/len(t1))
print('t2: ', sum(t2)/len(t2))
print('t3: ', sum(t3)/len(t3))
print('t5: ', sum(t5)/len(t5))

效率测试输出：

 t1:  0.654838958307
t2:  1.53977598714
t3:  6.7898791732
t5:  0.422228400305

精度测试脚本和结果：

 In [8]: eudis1(v1,v2)
Out[8]: 64.60650122085238

In [9]: eudis2(v1,v2)
Out[9]: 64.60650122085238

In [10]: eudis3(v1,v2)
Out[10]: array([[ 64.60650122]])

In [11]: eudis5(v1,v2)
Out[11]: 64.60650122085238

原文由 MaThMaX 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这并不能完全回答问题，但可能值得一提的是，如果您对实际的欧氏距离不感兴趣，而只是想比较欧氏距离，平方根是单调函数，即 x**(1 /2) < y**(¹⁄₂) 当且仅当 x < y 时。

因此，如果您不想要显式距离，但例如只想知道 vector1 的欧氏距离是否更接近一个向量列表，称为 vectorlist，您可以避免昂贵的（在精度和时间方面）平方root，但可以用类似的东西凑合

min(vectorlist, key = lambda compare: sum([(a - b)**2 for a, b in zip(vector1, compare)])

原文由 Tarje Bargheer 发布，翻译遵循 CC BY-SA 4.0 许可协议