高效精确地计算欧氏距离

Question

继一些在线调查(1,2,numpy的,SciPy的,scikit,数学),我已经找到了计算的几种方法在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).

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,根据文档:

与其他计算距离的方法相比,这种公式有两个优点.首先,它在处理稀疏数据时具有计算效率.其次,如果一个参数变化但另一个参数保持不变,则可以预先计算点(x,x)和/或点(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

Answer 2

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

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

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