Encuentra el valor más cercano en la matriz numpy

Question

¿Hay alguna forma numpy-thonic, p. función, para encontrar el valor más cercano en una matriz?

Ejemplo:

np.find_nearest(array, value) 

Answer 1

import numpy as np 
def find_nearest(array,value): 
    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 

Answer 2

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()] 

Answer 3

Aquí hay una ersion que se encargará de un no-escalar "valores" array:

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] 

Answer 4

Aquí está una extensión para encontrar el vector más cercano en un conjunto 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]) 

Answer 5

Si no desea utilizar esta numpy lo hará:

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

Answer 6

SI se ordena la matriz y es muy grande, esta es una solución mucho más rápido:

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 adapta a matrices muy grandes. Puede modificar fácilmente lo anterior para ordenar el método si no puede suponer que la matriz ya está ordenada. Es excesivo para arreglos pequeños, pero una vez que se hacen grandes, es mucho más rápido.

Answer 7

Para arreglos grandes, la (excelente) respuesta 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 formas:

1. La siguiente función funciona independientemente de que 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 de abajo también se ocupa de un caso extremo específico que daría lugar a un error en la función original escrito 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 

Answer 8

Aquí es una versión con scipy para @Ari Onasafari, respuesta "para encontrar el vector más cercano en una serie 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]) 

Answer 9

Resumen de respuesta: Si uno tiene un array ordenado, entonces el código de bisección (dado a continuación) realiza el más rápido. ~ 100-1000 veces más rápido para arreglos grandes, y ~ 2-100 veces más rápido para arreglos pequeños. No requiere numpy tampoco. Si usted tiene una desordenada array entonces si array es grande, se debe considerar en primer lugar utilizando un O (n log n) Ordenar y después de bisección, y si array es pequeño, entonces el método 2 parece el más rápido.

Primero debe aclarar lo que quiere decir con el valor más cercano. A menudo uno quiere el intervalo en una abscisa, p. array = [0,0.7,2.1], value = 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 instrucción condicional de seguimiento una vez que encuentre el intervalo). Voy a señalar que la mejor manera de realizar esto es con bisección (que voy a ofrecer primero - en cuenta que no requiere numpy en absoluto y es más rápido que el uso de funciones numpy porque realizan operaciones redundantes). Luego proporcionaré una comparación de tiempos contra 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 voy a definir el código de las otras respuestas, cada uno de ellos devuelven 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 voy a tiempo de los códigos: Nota los métodos 1,2,4,5 no dan correctamente el intervalo. Los métodos 1, 2, 4 redondean al punto más cercano en el conjunto (por ejemplo,> = 1,5 -> 2), y el método 5 siempre se redondea (por ejemplo, 1,45 -> 2). Solo los métodos 3 y 6, y por supuesto la bisección, dan el intervalo de manera apropiada.

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 variedad de bisección da 4us en comparación con el siguiente mejor 180us y 1.21ms más largas (~ 100 - 1000 veces más rápido). Para arreglos más pequeños, es ~ 2-100 veces más rápido.

Answer 10

creo que la forma más Pythonic 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. Se puede utilizar como una función si desea

Answer 11

Aquí está una versión vectorizada rápida de @ solución de Dimitri si tiene muchos values para buscar (values puede haber 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] 

Los puntos de referencia

> 100 veces más rápido que el uso de un bucle con for @ disoluciones para Demitri de

>>> %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