Znajdź najbliższą wartość w tablicy numpy

Czy istnieje sposób numps-toniczny, np. Funkcja, aby znaleźć najbliższą wartość w tablicy?

Przykład:

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

JEŻELI twoja tablica jest posortowana i jest bardzo duża, jest to znacznie szybsze rozwiązanie:

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]

Skaluje się to do bardzo dużych tablic. Możesz łatwo zmodyfikować powyższe, aby posortować w metodzie, jeśli nie możesz założyć, że tablica jest już posortowana. Jest to nadmiar w przypadku małych tablic, ale gdy stają się duże, jest to znacznie szybsze.

Po niewielkiej modyfikacji powyższa odpowiedź działa z tablicami o dowolnym wymiarze (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]

Lub zapisany jako pojedynczy wiersz:

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

Podsumowanie odpowiedzi : jeśli ktoś ma posortowane, arraykod bisekcji (podany poniżej) działa najszybciej. ~ 100-1000 razy szybciej dla dużych tablic i ~ 2-100 razy szybciej dla małych tablic. Nie wymaga też numpy. Jeśli masz nieposortowane, arrayto jeśli arrayjest duże, należy najpierw rozważyć użycie sortowania O (n logn), a następnie bisekcji, a jeśli arrayjest małe, metoda 2 wydaje się najszybsza.

Najpierw wyjaśnij, co rozumiesz przez najbliższą wartość . Często chce się odstępu w odciętej, np. Tablica = [0,0.7,2.1], wartość = 1,95, odpowiedź brzmiałaby idx = 1. Podejrzewam, że jest to przypadek (w przeciwnym razie można bardzo łatwo zmodyfikować następujące instrukcje warunkowe po znalezieniu interwału). Zwrócę uwagę, że optymalnym sposobem na wykonanie tego jest bisekcja (którą przedstawię jako pierwszą - zauważ, że w ogóle nie wymaga numpy i jest szybsza niż używanie funkcji numpy, ponieważ wykonują one operacje redundantne). Następnie przedstawię porównanie czasowe z innymi przedstawionymi tutaj przez innych użytkowników.

Przepołowienie:

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

Teraz zdefiniuję kod na podstawie innych odpowiedzi, każda zwróci indeks:

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

Teraz zmierzę kody: Zwróć uwagę, że metody 1,2,4,5 nie podają poprawnie interwału. Metody 1,2,4 zaokrąglają do najbliższego punktu w tablicy (np.> = 1,5 -> 2), a metoda 5 zawsze zaokrągla w górę (np. 1,45 -> 2). Tylko metody 3 i 6, i oczywiście bisekcja dają odpowiedni odstęp.

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

Dla bisekcji z dużą tablicą daje 4us w porównaniu do następnego najlepszego 180us i najdłuższego 1,21ms (~ 100-1000 razy szybciej). Dla mniejszych tablic jest ~ 2-100 razy szybszy.

Oto rozszerzenie umożliwiające znalezienie najbliższego wektora w szeregu wektorów.

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

Jeśli nie chcesz używać Numpy, zrobi to:

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

Oto wersja, która obsłuży nieskalarną tablicę „wartości”:

import numpy as np

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

Lub wersja, która zwraca typ liczbowy (np. Int, float), jeśli dane wejściowe są skalarne:

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]

Oto wersja z scipy dla @Ari Onasafari, odpowiedz „ aby znaleźć najbliższy wektor w szeregu wektorów ”

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

Oto szybka wektoryzowana wersja rozwiązania @ Dimitri, jeśli masz wiele valuesdo wyszukiwania ( valuesmoże to być tablica wielowymiarowa):

#`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]

Benchmarki

> 100 razy szybszy niż użycie forpętli z rozwiązaniem @ 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

W przypadku dużych tablic odpowiedź (doskonała) podana przez @Demitri jest znacznie szybsza niż odpowiedź oznaczona obecnie jako najlepsza. Dostosowałem jego dokładny algorytm na dwa sposoby:

1. Poniższa funkcja działa niezależnie od tego, czy tablica wejściowa jest posortowana.

2. Poniższa funkcja zwraca indeks tablicy wejściowej odpowiadający najbliższej wartości, która jest nieco bardziej ogólna.

Zauważ, że poniższa funkcja obsługuje również określony przypadek krawędzi, który prowadziłby do błędu w oryginalnej funkcji napisanej przez @Demitri. W przeciwnym razie mój algorytm jest identyczny z jego.

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

To jest wektoryzowana wersja odpowiedzi 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)

Myślę, że najbardziej pythonicznym sposobem byłoby:

 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)

To jest podstawowy kod. Możesz użyć go jako funkcji, jeśli chcesz

Wszystkie odpowiedzi są przydatne do zebrania informacji i napisania wydajnego kodu. Napisałem jednak mały skrypt w języku Python, aby zoptymalizować go pod kątem różnych przypadków. Najlepszym rozwiązaniem będzie posortowanie dostarczonej tablicy. Jeśli ktoś przeszukuje indeks najbliższego punktu o określonej wartości, bisectmoduł jest najbardziej wydajny czasowo. Kiedy jedno wyszukiwanie indeksów odpowiada tablicy, numpy searchsortedjest najbardziej wydajne.

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)

W [63]:% czasu bisect.bisect_left (xlist, 0.3) Czasy procesora: użytkownik 0 ns, sys: 0 ns, łącznie: 0 ns Czas ściany: 22,2 µs

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

W [64]:% czasu np. Wyszukiwanie posortowane (xar, 0.3, side = "left") Czasy procesora: użytkownik 0 ns, sys: 0 ns, ogółem: 0 ns Czas ściany: 98,9 µs

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

% czasu np.searchsorted (xar, randpts, side = "left") Czasy procesora: użytkownik 4 ms, sys: 0 ns, łącznie: 4 ms Czas ściany: 1,2 ms

Jeśli zastosujemy regułę multiplikatywną, to numpy powinno zająć ~ 100 ms, co oznacza ~ 83X szybciej.

Dla tablicy 2d, aby określić pozycję i, j najbliższego elementu:

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

Może pomocne w ndarrays:

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