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


336

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

Przykład:

np.find_nearest( array, value )

Odpowiedzi:


516
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

52
@EOL: return np.abs(array-value).min()daje złą odpowiedź. To daje ci minimalną odległość wartości bezwzględnej i jakoś musimy zwrócić rzeczywistą wartość tablicy. Możemy dodać valuei zbliżyć się, ale wartość bezwzględna wrzuca klucz do rzeczy ...
unutbu

9
@ ~ unutbu Masz rację, mój zły. Nie mogę wymyślić nic lepszego niż twoje rozwiązanie!
Eric O Lebigot,

24
wydaje się szalony, nie ma wbudowanego numpy, który to robi.
dbliss,

3
@jsmedmar Metodą podziału (patrz moja poniższa odpowiedź) jest O (log (n)).
Josh Albert

4
FutureWarning: 'argmin' is deprecated. Use 'idxmin' instead. The behavior of 'argmin' will be corrected to return the positional minimum in the future. Use 'series.values.argmin' to get the position of the minimum now.Używanie idxminzamiast argmindziała dla mnie z powyższym rozwiązaniem. (v3.6.4)
jorijnsmit

78

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.


To brzmi jak najbardziej rozsądne rozwiązanie. Zastanawiam się, dlaczego i tak jest tak wolny. Zwykły np.searchsortedzajmuje około 2 µs dla mojego zestawu testowego, cała funkcja około 10 µs. Korzystanie np.absstaje się jeszcze gorsze. Nie ma pojęcia, co tam robi python.
Michael

2
@Michael W przypadku pojedynczych wartości procedury matematyczne Numpy będą wolniejsze niż mathprocedury, zobacz tę odpowiedź .
Demitri

3
Jest to najlepsze rozwiązanie, jeśli masz wiele wartości, które chcesz sprawdzić jednocześnie (z kilkoma zmianami). Całość if/elsenależy zastąpićidx = idx - (np.abs(value - array[idx-1]) < np.abs(value - array[idx])); return array[idx]
coderforlife

3
To jest świetne, ale nie działa, jeśli valuejest większy niż arraynajwiększy element. Zmieniłem ifoświadczenie, if idx == len(array) or math.fabs(value - array[idx - 1]) < math.fabs(value - array[idx])aby działało dla mnie!
nicoco

3
To nie działa, gdy idx wynosi 0. The if powinien przeczytać:if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])):
JPaget

52

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

6
„Płaski” bit nie jest konieczny. a[np.abs(a-a0).argmin)]działa w porządku.
Max Shron,

2
W rzeczywistości działa to tylko dla jednego wymiaru, ponieważ argmin () daje wiele wyników na kolumnę / wymiar. Też miałem literówkę. To działa, przynajmniej przez 2 wymiarach a[np.sum(np.square(np.abs(a-a0)),1).argmin()].
Max Shron,

3
Nie działa więc w przypadku wyższych wymiarów, a odpowiedź powinna zostać usunięta (lub zmodyfikowana w celu odzwierciedlenia tego)
Hugues Fontenelle

11
Podaj przykład, w którym proponowana odpowiedź nie działa. Jeśli znajdziesz taki, zmodyfikuję moją odpowiedź. Jeśli nie możesz go znaleźć, czy możesz usunąć swoje komentarze?
kwgoodman

18

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.


2
Zakładasz, że tablica jest posortowana. Istnieje wiele powodów, dla których ktoś nie chce sortować tablicy: na przykład, jeśli tablica reprezentuje punkty danych na wykresie liniowym.
user1917407

7
Standardowa biblioteka Pythona zawiera już implementację algorytmu bisekcji: docs.python.org/3.6/library/bisect.html
Felix

Kiedy powiedziałeś: „jeśli arrayjest mały, to metoda 2 wydaje się najszybsza”. jak mały miałeś na myśli @JoshAlbert?
Mr.Zeus

2
Nie znajduje najbliższej wartości, znajduje następną najniższą wartość.
endolith

@endolith dotyczy to tylko bisect.
Homero Esmeraldo

17

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

Myślę, że norm(..., axis=-1)powinno być szybsze niż wyodrębnianie x,ywartości za pomocą iteracji Pythona. Ponadto, x,ysą skalary tutaj? Potem norm(x+y)jest błąd, ponieważ np. Dystans (+1, -1)będzie traktowany jako 0.
cfh

To zadziałało dla mnieidx = np.array([np.linalg.norm(x+y) for (x,y) in abs(array-value)]).argmin()
ezchx

9

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]

9

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]

Dobra odpowiedź, nigdy wcześniej nie korzystałem z outermetody ufunc, myślę, że będę jej częściej używać w przyszłości. Nawiasem array[indices]mówiąc, pierwsza funkcja powinna wrócić .
Widjet,

1
To rozwiązanie nie jest skalowane. np.subtract.outerwygeneruje całą macierz produktu zewnętrznego, która jest naprawdę wolna i intensywnie zapamiętuje, jeśli arrayi / lub valuesjest bardzo duża.
anthonybell

8

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

Zbudowanie KDTree jest dość dużym obciążeniem dla takiego problemu. Nie poleciłbym takiego rozwiązania, chyba że będziesz musiał wykonać wiele zapytań na dużej tablicy ... A wtedy lepiej byłoby zbudować je raz i użyć ponownie, niż tworzyć na bieżąco dla każdego zapytania.
Ben

8

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

jeśli masz ciągłe próbkowanie w tablicy, staje się to jeszcze prostsze: idx = np.searchsorted(array, values)wtedy: idx[array[idx] - values>np.diff(array).mean()*0.5]-=1i wreszciereturn array[idx]
Siergiej Antopolskiy

7

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

1
Warto zauważyć, że jest to świetny przykład tego, jak optymalizacja kodu sprawia, że ​​jest brzydszy i trudniejszy do odczytania. Odpowiedź udzielona przez @unutbu powinna być (zdecydowanie) preferowana w przypadkach, w których szybkość nie jest głównym problemem, ponieważ jest znacznie bardziej przejrzysta.
aph

Nie widzę odpowiedzi udzielonej przez @Michael. Czy to błąd, czy jestem ślepy?
Fookatchu,

Nie, nie jesteś ślepy, jestem po prostu analfabetą ;-) To był @Demitri, na którego odpowiedź się zastanawiałem. Mój błąd. Właśnie naprawiłem swój post. Dzięki!
aph

Dostaję różne odpowiedzi u Demitri i u ciebie. Jakieś pomysły? x = np.array([2038, 1758, 1721, 1637, 2097, 2047, 2205, 1787, 2287, 1940, 2311, 2054, 2406, 1471, 1460]). Z find_nearest(x, 1739.5)(najbliższa wartość do pierwszego kwantyla) dostaję 1637(rozsądne) i 1(błąd?).
PatrickT

3

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)

2

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


2

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.


1

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

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

1
Cześć, witamy w Stack Overflow. Sprawdź, jak napisać dobrą odpowiedź . Spróbuj podać krótki opis tego, co zrobiłeś w kontekście pytania!
Tristo,

0

Może pomocne w ndarrays:

def find_nearest(X, value):
    return X[np.unravel_index(np.argmin(np.abs(X - value)), X.shape)]
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.