Как можно рассчитать евклидово расстояние с помощью NumPy?

Используйте numpy.linalg.norm:

dist = numpy.linalg.norm(a-b)

Вы можете найти теорию, лежащую в основе этого, в Введение в интеллектуальный анализ данных

Это работает, потому что евклидово расстояние является нормой l2, а значение по умолчанию для параметра ord в numpy.linalg.norm равно 2.

Для этого есть функция в SciPy. Он называется евклидовым.

Пример:

from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)

Для всех, кто интересуется одновременным вычислением нескольких расстояний, я провел небольшое сравнение, используя perfplot (небольшой мой проект).

Первый совет - организовать ваши данные так, чтобы массивы имели размерность (3, n) (и, очевидно, были C-смежными). Если добавление происходит в непрерывном первом измерении, все происходит быстрее, и не имеет большого значения, используете ли вы sqrt-sum с axis=0, linalg.norm с axis=0 или

a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->j', a_min_b, a_min_b))

что с небольшим отрывом является самым быстрым вариантом. (На самом деле это справедливо и для одной строки.)

Варианты, в которых вы суммируете по второй оси, axis=1, все значительно медленнее.

Код для воспроизведения сюжета:

import numpy
import perfplot
from scipy.spatial import distance


def linalg_norm(data):
    a, b = data[0]
    return numpy.linalg.norm(a - b, axis=1)


def linalg_norm_T(data):
    a, b = data[1]
    return numpy.linalg.norm(a - b, axis=0)


def sqrt_sum(data):
    a, b = data[0]
    return numpy.sqrt(numpy.sum((a - b) ** 2, axis=1))


def sqrt_sum_T(data):
    a, b = data[1]
    return numpy.sqrt(numpy.sum((a - b) ** 2, axis=0))


def scipy_distance(data):
    a, b = data[0]
    return list(map(distance.euclidean, a, b))


def sqrt_einsum(data):
    a, b = data[0]
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum("ij,ij->i", a_min_b, a_min_b))


def sqrt_einsum_T(data):
    a, b = data[1]
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum("ij,ij->j", a_min_b, a_min_b))


def setup(n):
    a = numpy.random.rand(n, 3)
    b = numpy.random.rand(n, 3)
    out0 = numpy.array([a, b])
    out1 = numpy.array([a.T, b.T])
    return out0, out1


perfplot.save(
    "norm.png",
    setup=setup,
    n_range=[2 ** k for k in range(22)],
    kernels=[
        linalg_norm,
        linalg_norm_T,
        scipy_distance,
        sqrt_sum,
        sqrt_sum_T,
        sqrt_einsum,
        sqrt_einsum_T,
    ],
    xlabel="len(x), len(y)",
)

Я хочу изложить простой ответ с различными примечаниями к производительности. np.linalg.norm, возможно, сделает больше, чем вам нужно:

dist = numpy.linalg.norm(a-b)

Во-первых, эта функция предназначена для работы со списком и возврата всех значений, например для сравнения расстояния от pA до набора точек sP:

sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.)  # 'distances' is a list

Запомните несколько вещей:

• Вызов функций Python стоит дорого.
• [Обычный] Python не кэширует поиск по имени.

So

def distance(pointA, pointB):
    dist = np.linalg.norm(pointA - pointB)
    return dist

не так невинно, как кажется.

>>> dis.dis(distance)
  2           0 LOAD_GLOBAL              0 (np)
              2 LOAD_ATTR                1 (linalg)
              4 LOAD_ATTR                2 (norm)
              6 LOAD_FAST                0 (pointA)
              8 LOAD_FAST                1 (pointB)
             10 BINARY_SUBTRACT
             12 CALL_FUNCTION            1
             14 STORE_FAST               2 (dist)

  3          16 LOAD_FAST                2 (dist)
             18 RETURN_VALUE

Во-первых, каждый раз, когда мы вызываем его, мы должны выполнять глобальный поиск для "np", поиск в области видимости для "linalg" и поиск в области видимости для "norm", а также накладные расходы на простой вызов функция может приравниваться к десяткам инструкций Python.

Наконец, мы потратили две операции, чтобы сохранить результат и перезагрузить его для возврата ...

Первый шаг к улучшению: сделайте поиск быстрее, пропустите магазин

def distance(pointA, pointB, _norm=np.linalg.norm):
    return _norm(pointA - pointB)

Мы получаем гораздо более рациональный вариант:

>>> dis.dis(distance)
  2           0 LOAD_FAST                2 (_norm)
              2 LOAD_FAST                0 (pointA)
              4 LOAD_FAST                1 (pointB)
              6 BINARY_SUBTRACT
              8 CALL_FUNCTION            1
             10 RETURN_VALUE

Однако накладные расходы на вызов функции по-прежнему требуют некоторой работы. И вы захотите провести тесты, чтобы определить, может ли вам лучше заниматься математикой самостоятельно:

def distance(pointA, pointB):
    return (
        ((pointA.x - pointB.x) ** 2) +
        ((pointA.y - pointB.y) ** 2) +
        ((pointA.z - pointB.z) ** 2)
    ) ** 0.5  # fast sqrt

На некоторых платформах **0.5 быстрее, чем math.sqrt. Ваш пробег может отличаться.

**** Расширенные примечания к производительности.

Зачем вы рассчитываете расстояние? Если единственная цель - показать его,

 print("The target is %.2fm away" % (distance(a, b)))

двигаться дальше. Но если вы сравниваете расстояния, выполняете проверки диапазонов и т. Д., Я хотел бы добавить несколько полезных наблюдений за производительностью.

Возьмем два случая: сортировка по расстоянию или отбраковка списка до элементов, которые соответствуют ограничению диапазона.

# Ultra naive implementations. Hold onto your hat.

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance(origin, thing))

def in_range(origin, range, things):
    things_in_range = []
    for thing in things:
        if distance(origin, thing) <= range:
            things_in_range.append(thing)

Первое, что нам нужно помнить, это то, что мы используем Pythagoras для вычисления расстояния (dist = sqrt(x^2 + y^2 + z^2) ) поэтому мы делаем много sqrt звонков. Математика 101:

dist = root ( x^2 + y^2 + z^2 )
:.
dist^2 = x^2 + y^2 + z^2
and
sq(N) < sq(M) iff M > N
and
sq(N) > sq(M) iff N > M
and
sq(N) = sq(M) iff N == M

Вкратце: до тех пор, пока нам не потребуется расстояние в единицах X, а не X ^ 2, мы можем исключить самую сложную часть вычислений.

# Still naive, but much faster.

def distance_sq(left, right):
    """ Returns the square of the distance between left and right. """
    return (
        ((left.x - right.x) ** 2) +
        ((left.y - right.y) ** 2) +
        ((left.z - right.z) ** 2)
    )

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance_sq(origin, thing))

def in_range(origin, range, things):
    things_in_range = []

    # Remember that sqrt(N)**2 == N, so if we square
    # range, we don't need to root the distances.
    range_sq = range**2

    for thing in things:
        if distance_sq(origin, thing) <= range_sq:
            things_in_range.append(thing)

Отлично, обе функции больше не используют дорогостоящие извлечения квадратного корня. Это будет намного быстрее. Мы также можем улучшить in_range, преобразовав его в генератор:

def in_range(origin, range, things):
    range_sq = range**2
    yield from (thing for thing in things
                if distance_sq(origin, thing) <= range_sq)

Это особенно полезно, если вы делаете что-то вроде:

if any(in_range(origin, max_dist, things)):
    ...

Но если следующее, что вы собираетесь сделать, требует расстояния,

for nearby in in_range(origin, walking_distance, hotdog_stands):
    print("%s %.2fm" % (nearby.name, distance(origin, nearby)))

рассмотрите возможность получения кортежей:

def in_range_with_dist_sq(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = distance_sq(origin, thing)
        if dist_sq <= range_sq: yield (thing, dist_sq)

Это может быть особенно полезно, если вы можете связать проверки диапазона («найти объекты, которые находятся рядом с X и в пределах Нм от Y», поскольку вам не нужно снова рассчитывать расстояние).

Но что делать, если мы ищем действительно большой список things и ожидаем, что многие из них не заслуживают рассмотрения?

На самом деле есть очень простая оптимизация:

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = (origin.x - thing.x) ** 2
        if dist_sq <= range_sq:
            dist_sq += (origin.y - thing.y) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing

Будет ли это полезно, будет зависеть от размера «вещей».

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    if len(things) >= 4096:
        for thing in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2
                if dist_sq <= range_sq:
                    dist_sq += (origin.z - thing.z) ** 2
                    if dist_sq <= range_sq:
                        yield thing
    elif len(things) > 32:
        for things in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2 + (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing
    else:
        ... just calculate distance and range-check it ...

И снова рассмотрите возможность выдачи dist_sq. Наш пример хот-дога становится таким:

# Chaining generators
info = in_range_with_dist_sq(origin, walking_distance, hotdog_stands)
info = (stand, dist_sq**0.5 for stand, dist_sq in info)
for stand, dist in info:
    print("%s %.2fm" % (stand, dist))

Другой пример решения этой проблемы метод:

def dist(x,y):   
    return numpy.sqrt(numpy.sum((x-y)**2))

a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
dist_a_b = dist(a,b)

Начиная с Python 3.8, модуль math напрямую предоставляет _ 3_, которая возвращает евклидово расстояние между двумя точками (заданное в виде кортежей или списков координат):

from math import dist

dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845

А если вы работаете со списками:

dist([1, 2, 6], [-2, 3, 2]) # 5.0990195135927845

Это можно сделать следующим образом. Я не знаю, насколько это быстро, но он не использует NumPy.

from math import sqrt
a = (1, 2, 3) # Data point 1
b = (4, 5, 6) # Data point 2
print sqrt(sum( (a - b)**2 for a, b in zip(a, b)))

Хороший однострочный:

dist = numpy.linalg.norm(a-b)

Однако, если вас беспокоит скорость, я бы порекомендовал поэкспериментировать на вашей машине. Я обнаружил, что использование sqrt библиотеки math с оператором ** для квадрата на моей машине намного быстрее, чем однострочное решение NumPy.

Я провел свои тесты с помощью этой простой программы:

#!/usr/bin/python
import math
import numpy
from random import uniform

def fastest_calc_dist(p1,p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 +
                     (p2[1] - p1[1]) ** 2 +
                     (p2[2] - p1[2]) ** 2)

def math_calc_dist(p1,p2):
    return math.sqrt(math.pow((p2[0] - p1[0]), 2) +
                     math.pow((p2[1] - p1[1]), 2) +
                     math.pow((p2[2] - p1[2]), 2))

def numpy_calc_dist(p1,p2):
    return numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))

TOTAL_LOCATIONS = 1000

p1 = dict()
p2 = dict()
for i in range(0, TOTAL_LOCATIONS):
    p1[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))
    p2[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))

total_dist = 0
for i in range(0, TOTAL_LOCATIONS):
    for j in range(0, TOTAL_LOCATIONS):
        dist = fastest_calc_dist(p1[i], p2[j]) #change this line for testing
        total_dist += dist

print total_dist

На моей машине math_calc_dist работает намного быстрее, чем numpy_calc_dist: 1,5 секунды против 23,5 секунды.

Чтобы получить измеримую разницу между fastest_calc_dist и math_calc_dist, мне пришлось увеличить TOTAL_LOCATIONS до 6000. Тогда fastest_calc_dist занимает ~ 50 секунд, а math_calc_dist - ~ 60 секунд.

Вы также можете поэкспериментировать с numpy.sqrt и numpy.square, хотя оба они были медленнее, чем math альтернативы на моей машине.

Мои тесты проводились с Python 2.6.6.

Я нашел функцию dist в matplotlib.mlab, но не думаю, что она достаточно удобна.

Выкладываю сюда только для справки.

import numpy as np
import matplotlib as plt

a = np.array([1, 2, 3])
b = np.array([2, 3, 4])

# Distance between a and b
dis = plt.mlab.dist(a, b)

Вы можете просто вычесть векторы, а затем внутреннее произведение.

Следуя вашему примеру,

a = numpy.array((xa, ya, za))
b = numpy.array((xb, yb, zb))

tmp = a - b
sum_squared = numpy.dot(tmp.T, tmp)
result = numpy.sqrt(sum_squared)

Мне нравится np.dot (точечный продукт):

a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))

distance = (np.dot(a-b,a-b))**.5

Имея a и b, как вы их определили, вы также можете использовать:

distance = np.sqrt(np.sum((a-b)**2))

С Python 3.8 это очень просто.

https://docs.python.org/3/library/math.html#math.dist

math.dist(p, q)

Возвращает евклидово расстояние между двумя точками p и q, каждая из которых задана как последовательность (или итерация) координат. Две точки должны иметь одинаковый размер.

Примерно эквивалентно:

sqrt(sum((px - qx) ** 2.0 for px, qx in zip(p, q)))

Вот краткий код для евклидова расстояния в Python с учетом двух точек, представленных в виде списков в Python.

def distance(v1,v2): 
    return sum([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)

Начиная с Python 3.8

Начиная с Python 3.8 модуль math включает функцию math.dist().
См. Здесь https://docs.python.org/3.8/library/math.html#math.dist.

math.dist (p1, p2)
Возвращает евклидово расстояние между двумя точками p1 и p2, каждая из которых задана как последовательность (или итерация) координат.

import math
print( math.dist( (0,0),   (1,1)   )) # sqrt(2) -> 1.4142
print( math.dist( (0,0,0), (1,1,1) )) # sqrt(3) -> 1.7321

Вычислите евклидово расстояние для многомерного пространства:

 import math

 x = [1, 2, 6] 
 y = [-2, 3, 2]

 dist = math.sqrt(sum([(xi-yi)**2 for xi,yi in zip(x, y)]))
 5.0990195135927845

Вы можете легко использовать формулу

distance = np.sqrt(np.sum(np.square(a-b)))

который на самом деле делает не что иное, как использование теоремы Пифагора для вычисления расстояния путем сложения квадратов Δx, Δy и Δz и укоренения результата.

Сначала найдите разность двух матриц. Затем примените поэлементное умножение с помощью команды умножения numpy. После этого найдите сумму поэлементно перемноженной новой матрицы. Наконец, найдите квадратный корень из суммы.

def findEuclideanDistance(a, b):
    euclidean_distance = a - b
    euclidean_distance = np.sum(np.multiply(euclidean_distance, euclidean_distance))
    euclidean_distance = np.sqrt(euclidean_distance)
    return euclidean_distance

import numpy as np
# any two python array as two points
a = [0, 0]
b = [3, 4]

Сначала вы меняете список на массив numpy и делаете следующее: print(np.linalg.norm(np.array(a) - np.array(b))). Второй метод прямо из списка Python как: print(np.linalg.norm(np.subtract(a,b)))

Другие ответы работают для чисел с плавающей запятой, но неправильно вычисляют расстояние для целочисленных dtypes, которые подвержены переполнению и потере значимости. Обратите внимание, что даже scipy.distance.euclidean имеет эту проблему:

>>> a1 = np.array([1], dtype='uint8')
>>> a2 = np.array([2], dtype='uint8')
>>> a1 - a2
array([255], dtype=uint8)
>>> np.linalg.norm(a1 - a2)
255.0
>>> from scipy.spatial import distance
>>> distance.euclidean(a1, a2)
255.0

Это обычное дело, поскольку многие библиотеки изображений представляют изображение как ndarray с dtype = uint8. Это означает, что если у вас есть изображение в оттенках серого, которое состоит из очень темно-серых пикселей (скажем, все пиксели имеют цвет #000001), и вы сравниваете его с черным изображением (#000000), вы можете получить x-y, состоящий из 255 во всех ячейках , который регистрируется как два изображения, находящиеся очень далеко друг от друга. Для целочисленных типов без знака (например, uint8) вы можете безопасно вычислить расстояние в numpy как:

np.linalg.norm(np.maximum(x, y) - np.minimum(x, y))

Для целочисленных типов со знаком вы можете сначала привести к типу с плавающей запятой:

np.linalg.norm(x.astype("float") - y.astype("float"))

В частности, для данных изображения вы можете использовать метод нормы opencv:

import cv2
cv2.norm(x, y, cv2.NORM_L2)