Найти ближайшего соседа более питоническим способом

Question

A - это точка, а P - список точек. Я хочу найти, какая точка P[i] является ближайшей к A, т.е. я хочу найти P[i_0] с:

i_0 = argmin_i || A - P[i]||^2

Я делаю это так:

import numpy as np

# P is a list of 4 points
P = [np.array([-1, 0, 7, 3]), np.array([5, -2, 8, 1]), np.array([0, 2, -3, 4]), np.array([-9, 11, 3, 4])]
A = np.array([1, 2, 3, 4])
distance = 1000000000     # better would be : +infinity
closest = None

for p in P:
  delta = sum((p - A)**2)
  if delta < distance:
    distance = delta
    closest = p

print closest    # the closest point to A among all the points in P

Это работает, но как сделать это более коротким / более Pythonic способом?

В более общем смысле в Python (и даже без использования Numpy), как найти k_0 такой, что D[k_0] = min D[k] ? т.е. k_0 = argmin_k D[k]

Answer 1

Более Pythonic способ реализовать тот же алгоритм, который вы используете, это заменить ваш цикл вызовом min с key функция:

closest = min(P, key=lambda p: sum((p - A)**2))

Обратите внимание, что я использую ** для возведения в степень (^ является бинарным оператором xor в Python).

Answer 2

Полностью векторизованный подход в NumPy. Похож на один из @MikeMüller, но использует трансляцию numpy, чтобы избежать лямбда-функций.

С данными примера:

>>> P = [np.array([-1, 0, 7, 3]), np.array([5, -2, 8, 1]), np.array([0, 2, -3, 4]), np.array([-9, 11, 3, 4])]
>>> A = np.array([1, 2, 3, 4])

И делая P двумерный массив:

>>> P = np.asarray(P)
>>> P
array([[-1,  0,  7,  3],
       [ 5, -2,  8,  1],
       [ 0,  2, -3,  4],
       [-9, 11,  3,  4]])

Это может быть вычислено в одной строке, используя numpy:

>>> P[np.argmin(np.sum((P - A)**2, axis=1))]

Обратите внимание, что P - A, с P.shape = (N, 4) а также A.shape = (4,) будет выводить вычитание на все строки P (Pi = Pi - A).

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

Answer 3

Версия NumPy в виде одной строки:

clostest = P[np.argmin(np.apply_along_axis(lambda p: np.sum((p - A) **2), 1, P))]

Answer 4

Использование встроенного min способ для этого:

import math
p1 = [1,2]
plst = [[1,3], [10,10], [5,5]]
res = min(plst, key=lambda x: math.sqrt(pow(p1[0]-x[0], 2) + pow(p1[1]-x[1], 2)))
print res
[1, 3]

Обратите внимание, что я просто использовал простые списки Python.