Encuentra el valor más cercano en una matriz numpy

¿Existe una forma numpy-thonic, por ejemplo, función, para encontrar el valor más cercano en una matriz?

Ejemplo:

np.find_nearest( array, value )

import numpy as np
def find_nearest(array, value):
    array = np.asarray(array)
    idx = (np.abs(array - value)).argmin()
    return array[idx]

array = np.random.random(10)
print(array)
# [ 0.21069679  0.61290182  0.63425412  0.84635244  0.91599191  0.00213826
#   0.17104965  0.56874386  0.57319379  0.28719469]

value = 0.5

print(find_nearest(array, value))
# 0.568743859261

SI su matriz está ordenada y es muy grande, esta es una solución mucho más rápida:

def find_nearest(array,value):
    idx = np.searchsorted(array, value, side="left")
    if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])):
        return array[idx-1]
    else:
        return array[idx]

Esto se escala a matrices muy grandes. Puede modificar fácilmente lo anterior para ordenar en el método si no puede asumir que la matriz ya está ordenada. Es excesivo para arreglos pequeños, pero una vez que se hacen grandes, esto es mucho más rápido.

Con una ligera modificación, la respuesta anterior funciona con matrices de dimensión arbitraria (1d, 2d, 3d, ...):

def find_nearest(a, a0):
    "Element in nd array `a` closest to the scalar value `a0`"
    idx = np.abs(a - a0).argmin()
    return a.flat[idx]

O, escrito como una sola línea:

a.flat[np.abs(a - a0).argmin()]

Resumen de la respuesta : si uno tiene un orden array, el código de bisección (que se muestra a continuación) se realiza más rápido. ~ 100-1000 veces más rápido para matrices grandes y ~ 2-100 veces más rápido para matrices pequeñas. No requiere numpy tampoco. Si tiene un no ordenado, arrayentonces si arrayes grande, primero debe considerar usar una clasificación O (n logn) y luego una bisección, y si arrayes pequeño, entonces el método 2 parece el más rápido.

Primero debes aclarar lo que quieres decir con el valor más cercano . A menudo se quiere el intervalo en una abscisa, por ejemplo, matriz = [0,0.7,2.1], valor = 1.95, la respuesta sería idx = 1. Este es el caso que sospecho que necesita (de lo contrario, lo siguiente se puede modificar muy fácilmente con una declaración condicional de seguimiento una vez que encuentre el intervalo). Notaré que la forma óptima de realizar esto es con la bisección (que proporcionaré primero; tenga en cuenta que no requiere numpy en absoluto y es más rápido que usar funciones numpy porque realizan operaciones redundantes). Luego proporcionaré una comparación de tiempos con los otros presentados aquí por otros usuarios.

Bisección:

def bisection(array,value):
    '''Given an ``array`` , and given a ``value`` , returns an index j such that ``value`` is between array[j]
    and array[j+1]. ``array`` must be monotonic increasing. j=-1 or j=len(array) is returned
    to indicate that ``value`` is out of range below and above respectively.'''
    n = len(array)
    if (value < array[0]):
        return -1
    elif (value > array[n-1]):
        return n
    jl = 0# Initialize lower
    ju = n-1# and upper limits.
    while (ju-jl > 1):# If we are not yet done,
        jm=(ju+jl) >> 1# compute a midpoint with a bitshift
        if (value >= array[jm]):
            jl=jm# and replace either the lower limit
        else:
            ju=jm# or the upper limit, as appropriate.
        # Repeat until the test condition is satisfied.
    if (value == array[0]):# edge cases at bottom
        return 0
    elif (value == array[n-1]):# and top
        return n-1
    else:
        return jl

Ahora definiré el código de las otras respuestas, cada una devuelve un índice:

import math
import numpy as np

def find_nearest1(array,value):
    idx,val = min(enumerate(array), key=lambda x: abs(x[1]-value))
    return idx

def find_nearest2(array, values):
    indices = np.abs(np.subtract.outer(array, values)).argmin(0)
    return indices

def find_nearest3(array, values):
    values = np.atleast_1d(values)
    indices = np.abs(np.int64(np.subtract.outer(array, values))).argmin(0)
    out = array[indices]
    return indices

def find_nearest4(array,value):
    idx = (np.abs(array-value)).argmin()
    return idx


def find_nearest5(array, value):
    idx_sorted = np.argsort(array)
    sorted_array = np.array(array[idx_sorted])
    idx = np.searchsorted(sorted_array, value, side="left")
    if idx >= len(array):
        idx_nearest = idx_sorted[len(array)-1]
    elif idx == 0:
        idx_nearest = idx_sorted[0]
    else:
        if abs(value - sorted_array[idx-1]) < abs(value - sorted_array[idx]):
            idx_nearest = idx_sorted[idx-1]
        else:
            idx_nearest = idx_sorted[idx]
    return idx_nearest

def find_nearest6(array,value):
    xi = np.argmin(np.abs(np.ceil(array[None].T - value)),axis=0)
    return xi

Ahora cronometraré los códigos: los métodos de nota 1,2,4,5 no dan correctamente el intervalo. Los métodos 1, 2, 4 redondean al punto más cercano en la matriz (por ejemplo,> = 1.5 -> 2), y el método 5 siempre redondea hacia arriba (por ejemplo, 1.45 -> 2). Solo los métodos 3 y 6 y, por supuesto, la bisección dan el intervalo correctamente.

array = np.arange(100000)
val = array[50000]+0.55
print( bisection(array,val))
%timeit bisection(array,val)
print( find_nearest1(array,val))
%timeit find_nearest1(array,val)
print( find_nearest2(array,val))
%timeit find_nearest2(array,val)
print( find_nearest3(array,val))
%timeit find_nearest3(array,val)
print( find_nearest4(array,val))
%timeit find_nearest4(array,val)
print( find_nearest5(array,val))
%timeit find_nearest5(array,val)
print( find_nearest6(array,val))
%timeit find_nearest6(array,val)

(50000, 50000)
100000 loops, best of 3: 4.4 µs per loop
50001
1 loop, best of 3: 180 ms per loop
50001
1000 loops, best of 3: 267 µs per loop
[50000]
1000 loops, best of 3: 390 µs per loop
50001
1000 loops, best of 3: 259 µs per loop
50001
1000 loops, best of 3: 1.21 ms per loop
[50000]
1000 loops, best of 3: 746 µs per loop

Para una gran matriz, la bisección da 4us en comparación con el siguiente mejor 180us y el más largo 1.21ms (~ 100 - 1000 veces más rápido). Para arreglos más pequeños es ~ 2-100 veces más rápido.

Aquí hay una extensión para encontrar el vector más cercano en una matriz de vectores.

import numpy as np

def find_nearest_vector(array, value):
  idx = np.array([np.linalg.norm(x+y) for (x,y) in array-value]).argmin()
  return array[idx]

A = np.random.random((10,2))*100
""" A = array([[ 34.19762933,  43.14534123],
   [ 48.79558706,  47.79243283],
   [ 38.42774411,  84.87155478],
   [ 63.64371943,  50.7722317 ],
   [ 73.56362857,  27.87895698],
   [ 96.67790593,  77.76150486],
   [ 68.86202147,  21.38735169],
   [  5.21796467,  59.17051276],
   [ 82.92389467,  99.90387851],
   [  6.76626539,  30.50661753]])"""
pt = [6, 30]  
print find_nearest_vector(A,pt)
# array([  6.76626539,  30.50661753])

Si no quieres usar numpy, esto lo hará:

def find_nearest(array, value):
    n = [abs(i-value) for i in array]
    idx = n.index(min(n))
    return array[idx]

Aquí hay una versión que manejará una matriz de "valores" no escalares:

import numpy as np

def find_nearest(array, values):
    indices = np.abs(np.subtract.outer(array, values)).argmin(0)
    return array[indices]

O una versión que devuelve un tipo numérico (por ejemplo, int, float) si la entrada es escalar:

def find_nearest(array, values):
    values = np.atleast_1d(values)
    indices = np.abs(np.subtract.outer(array, values)).argmin(0)
    out = array[indices]
    return out if len(out) > 1 else out[0]

Aquí hay una versión con scipy para @Ari Onasafari, responda " para encontrar el vector más cercano en una matriz de vectores "

In [1]: from scipy import spatial

In [2]: import numpy as np

In [3]: A = np.random.random((10,2))*100

In [4]: A
Out[4]:
array([[ 68.83402637,  38.07632221],
       [ 76.84704074,  24.9395109 ],
       [ 16.26715795,  98.52763827],
       [ 70.99411985,  67.31740151],
       [ 71.72452181,  24.13516764],
       [ 17.22707611,  20.65425362],
       [ 43.85122458,  21.50624882],
       [ 76.71987125,  44.95031274],
       [ 63.77341073,  78.87417774],
       [  8.45828909,  30.18426696]])

In [5]: pt = [6, 30]  # <-- the point to find

In [6]: A[spatial.KDTree(A).query(pt)[1]] # <-- the nearest point 
Out[6]: array([  8.45828909,  30.18426696])

#how it works!
In [7]: distance,index = spatial.KDTree(A).query(pt)

In [8]: distance # <-- The distances to the nearest neighbors
Out[8]: 2.4651855048258393

In [9]: index # <-- The locations of the neighbors
Out[9]: 9

#then 
In [10]: A[index]
Out[10]: array([  8.45828909,  30.18426696])

Aquí hay una versión rápida y vectorizada de la solución de @ Dimitri si tiene muchas valuespara buscar ( valuespuede ser una matriz multidimensional):

#`values` should be sorted
def get_closest(array, values):
    #make sure array is a numpy array
    array = np.array(array)

    # get insert positions
    idxs = np.searchsorted(array, values, side="left")

    # find indexes where previous index is closer
    prev_idx_is_less = ((idxs == len(array))|(np.fabs(values - array[np.maximum(idxs-1, 0)]) < np.fabs(values - array[np.minimum(idxs, len(array)-1)])))
    idxs[prev_idx_is_less] -= 1

    return array[idxs]

Puntos de referencia

> 100 veces más rápido que usar un forbucle con la solución de @ Demitri`

>>> %timeit ar=get_closest(np.linspace(1, 1000, 100), np.random.randint(0, 1050, (1000, 1000)))
139 ms ± 4.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit ar=[find_nearest(np.linspace(1, 1000, 100), value) for value in np.random.randint(0, 1050, 1000*1000)]
took 21.4 seconds

Para matrices grandes, la respuesta (excelente) dada por @Demitri es mucho más rápida que la respuesta actualmente marcada como la mejor. He adaptado su algoritmo exacto de las siguientes dos maneras:

1. La siguiente función funciona independientemente de si la matriz de entrada está ordenada o no.

2. La siguiente función devuelve el índice de la matriz de entrada correspondiente al valor más cercano, que es algo más general.

Tenga en cuenta que la función a continuación también maneja un caso de borde específico que conduciría a un error en la función original escrita por @Demitri. De lo contrario, mi algoritmo es idéntico al suyo.

def find_idx_nearest_val(array, value):
    idx_sorted = np.argsort(array)
    sorted_array = np.array(array[idx_sorted])
    idx = np.searchsorted(sorted_array, value, side="left")
    if idx >= len(array):
        idx_nearest = idx_sorted[len(array)-1]
    elif idx == 0:
        idx_nearest = idx_sorted[0]
    else:
        if abs(value - sorted_array[idx-1]) < abs(value - sorted_array[idx]):
            idx_nearest = idx_sorted[idx-1]
        else:
            idx_nearest = idx_sorted[idx]
    return idx_nearest

Esta es una versión vectorizada de la respuesta de unutbu :

def find_nearest(array, values):
    array = np.asarray(array)

    # the last dim must be 1 to broadcast in (array - values) below.
    values = np.expand_dims(values, axis=-1) 

    indices = np.abs(array - values).argmin(axis=-1)

    return array[indices]


image = plt.imread('example_3_band_image.jpg')

print(image.shape) # should be (nrows, ncols, 3)

quantiles = np.linspace(0, 255, num=2 ** 2, dtype=np.uint8)

quantiled_image = find_nearest(quantiles, image)

print(quantiled_image.shape) # should be (nrows, ncols, 3)

Creo que la forma más pitónica sería:

 num = 65 # Input number
 array = n.random.random((10))*100 # Given array 
 nearest_idx = n.where(abs(array-num)==abs(array-num).min())[0] # If you want the index of the element of array (array) nearest to the the given number (num)
 nearest_val = array[abs(array-num)==abs(array-num).min()] # If you directly want the element of array (array) nearest to the given number (num)

Este es el código básico. Puedes usarlo como una función si quieres

Todas las respuestas son beneficiosas para recopilar la información para escribir código eficiente. Sin embargo, he escrito un pequeño script de Python para optimizarlo en varios casos. Será el mejor caso si se ordena la matriz proporcionada. Si uno busca el índice del punto más cercano de un valor especificado, entonces el bisectmódulo es el más eficiente en el tiempo. Cuando uno busca los índices corresponden a una matriz, el numpy searchsortedes más eficiente.

import numpy as np
import bisect
xarr = np.random.rand(int(1e7))

srt_ind = xarr.argsort()
xar = xarr.copy()[srt_ind]
xlist = xar.tolist()
bisect.bisect_left(xlist, 0.3)

En [63]:% de tiempo bisect.bisect_left (xlist, 0.3) tiempos de CPU: usuario 0 ns, sys: 0 ns, total: 0 ns Tiempo de pared: 22.2 µs

np.searchsorted(xar, 0.3, side="left")

En [64]:% de tiempo np.searchsorted (xar, 0.3, side = "left") Tiempo de CPU: usuario 0 ns, sys: 0 ns, total: 0 ns Tiempo de pared: 98.9 µs

randpts = np.random.rand(1000)
np.searchsorted(xar, randpts, side="left")

% de tiempo np.searchsorted (xar, randpts, side = "left") Tiempo de CPU: usuario 4 ms, sys: 0 ns, total: 4 ms Tiempo de muro: 1,2 ms

Si seguimos la regla multiplicativa, entonces numpy debería tomar ~ 100 ms, lo que implica ~ 83X más rápido.

Para la matriz 2d, para determinar la posición i, j del elemento más cercano:

import numpy as np
def find_nearest(a, a0):
    idx = (np.abs(a - a0)).argmin()
    w = a.shape[1]
    i = idx // w
    j = idx - i * w
    return a[i,j], i, j

import numpy as np
def find_nearest(array, value):
    array = np.array(array)
    z=np.abs(array-value)
    y= np.where(z == z.min())
    m=np.array(y)
    x=m[0,0]
    y=m[1,0]
    near_value=array[x,y]

    return near_value

array =np.array([[60,200,30],[3,30,50],[20,1,-50],[20,-500,11]])
print(array)
value = 0
print(find_nearest(array, value))

Quizás útil para ndarrays:

def find_nearest(X, value):
    return X[np.unravel_index(np.argmin(np.abs(X - value)), X.shape)]