首页 文章

高效精确地计算欧氏距离

提问于
浏览 次
4

在一些在线研究（1，2，numpy，scipy，scikit，math）之后，我找到了几种计算 Euclidean Distance in 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)

我想知道是否有人可以提供关于 efficiency 和 precision 中哪一个（或我没有找到的任何其他）被认为是最佳的洞察力 . 如果有人知道讨论该主题的任何资源也会很棒 .

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

python python-3.x euclidean-distance

3 回答

  • 0

    结论第一：

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

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

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

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

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

    最后为 sklearn ，根据文档：

    与其他计算距离的方法相比，此公式有两个优点 . 首先，它在处理稀疏数据时具有计算效率 . 其次，如果一个参数变化但另一个参数保持不变，则可以预先计算点（x，x）和/或点（y，y） . 但是，这不是进行此计算的最精确方式，并且此函数返回的距离矩阵可能不是所需的完全对称

    由于在您的问题中您希望使用一组固定的数据，因此不会反映此实现的优势 . 由于性能和精度之间的权衡，它在所有方法中也提供了最差的精度 .

    Regarding the precision ， 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
    回复于
  • 1

    我不知道精度和速度如何与您提到的其他库相比，但您可以使用内置的 math.hypot() 函数为2D矢量执行此操作：

    from math import hypot

def pairwise(iterable):
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = iter(iterable), iter(iterable)
    next(b, None)
    return zip(a, b)

a = (52, 106, 35, 12)
b = (33, 153, 75, 10)

dist = [hypot(p2[0]-p1[0], p2[1]-p1[1]) for p1, p2 in pairwise(tuple(zip(a, b)))]
print(dist)  # -> [131.59027319676787, 105.47511554864494, 68.94925670375281]
    回复于
  • 8

    作为一般的经验法则，尽可能坚持 scipy 和 numpy 实现，因为它们被矢量化并且比本机Python代码快得多 . （主要原因是：在C中实现，向量化消除了循环所做的类型检查开销 . ）

    （旁白：我的答案不包括这里的精度，但我认为同样的原则适用于效率的精确度 . ）

    作为一个奖励，我重新使用IPython解释器，秘诀是使用 %prun 线魔术 .

    In [1]: import numpy

In [2]: from scipy.spatial import distance

In [3]: c1 = numpy.array((52, 106, 35, 12))

In [4]: c2 = numpy.array((33, 153, 75, 10))

In [5]: %prun distance.euclidean(c1, c2)
         35 function calls in 0.000 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 linalg.py:1976(norm)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.dot}
        6    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.array}
        4    0.000    0.000    0.000    0.000 numeric.py:406(asarray)
        1    0.000    0.000    0.000    0.000 distance.py:232(euclidean)
        2    0.000    0.000    0.000    0.000 distance.py:152(_validate_vector)
        2    0.000    0.000    0.000    0.000 shape_base.py:9(atleast_1d)
        1    0.000    0.000    0.000    0.000 misc.py:11(norm)
        1    0.000    0.000    0.000    0.000 function_base.py:605(asarray_chkfinite)
        2    0.000    0.000    0.000    0.000 numeric.py:476(asanyarray)
        1    0.000    0.000    0.000    0.000 {method 'ravel' of 'numpy.ndarray' objects}
        1    0.000    0.000    0.000    0.000 linalg.py:111(isComplexType)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'squeeze' of 'numpy.ndarray' objects}


In [6]: %prun numpy.linalg.norm(c1 - c2)
         10 function calls in 0.000 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 linalg.py:1976(norm)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.dot}
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 numeric.py:406(asarray)
        1    0.000    0.000    0.000    0.000 {method 'ravel' of 'numpy.ndarray' objects}
        1    0.000    0.000    0.000    0.000 linalg.py:111(isComplexType)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.array}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

    %prun 的作用是告诉你函数调用需要多长时间才能运行，包括一些跟踪以找出瓶颈所在的位置 . 在这种情况下， scipy.spatial.distance.euclidean 和 numpy.linalg.norm 实现都非常快 . 假设您定义了一个函数 dist(vect1, vect2) ，您可以使用相同的IPython魔术调用进行概要分析 . 作为另一个额外的好处， %prun 也可以在Jupyter笔记本内部工作，你可以做 %%prun 分析整个代码单元，而不仅仅是一个函数，只需将 %%prun 作为该单元格的第一行 .

    回复于

相关问题