Temukan nilai terdekat dalam array numpy

Apakah ada cara numpy-thonic, misalnya fungsi, untuk menemukan nilai terdekat dalam array?

Contoh:

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

JIKA array Anda diurutkan dan sangat besar, ini adalah solusi yang jauh lebih cepat:

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]

Ini skala untuk array yang sangat besar. Anda dapat dengan mudah memodifikasi di atas untuk mengurutkan dalam metode jika Anda tidak dapat mengasumsikan bahwa array sudah diurutkan. Dibutuhkan terlalu banyak untuk array kecil, tetapi begitu mereka menjadi besar ini jauh lebih cepat.

Dengan sedikit modifikasi, jawaban di atas berfungsi dengan array dimensi sewenang-wenang (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]

Atau, ditulis sebagai satu baris:

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

Ringkasan jawaban : Jika ada yang diurutkan arraymaka kode pembagian dua (diberikan di bawah) melakukan yang tercepat. ~ 100-1000 kali lebih cepat untuk array besar, dan ~ 2-100 kali lebih cepat untuk array kecil. Tidak perlu numpy juga. Jika Anda memiliki yang tidak disortir arraymaka jika arraybesar, orang harus mempertimbangkan terlebih dahulu menggunakan jenis O (n logn) dan kemudian membagi dua, dan jika arraykecil maka metode 2 tampaknya yang tercepat.

Pertama, Anda harus mengklarifikasi apa yang Anda maksud dengan nilai terdekat . Seringkali orang menginginkan interval dalam absis, mis. Array = [0,0.7,2.1], nilai = 1,95, jawabannya adalah idx = 1. Ini adalah kasus yang saya duga Anda butuhkan (jika tidak, berikut ini dapat dimodifikasi dengan sangat mudah dengan pernyataan bersyarat tindak lanjut setelah Anda menemukan interval). Saya akan mencatat bahwa cara optimal untuk melakukan ini adalah dengan membagi dua (yang akan saya berikan pertama - perhatikan itu tidak memerlukan numpy sama sekali dan lebih cepat daripada menggunakan fungsi numpy karena mereka melakukan operasi yang berlebihan). Lalu saya akan memberikan perbandingan waktu terhadap yang lain yang disajikan di sini oleh pengguna lain.

Pembagian atas dua bagian:

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

Sekarang saya akan mendefinisikan kode dari jawaban lain, mereka masing-masing mengembalikan 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

Sekarang saya akan mengatur waktu kode: Catatan metode 1,2,4,5 tidak memberikan interval dengan benar. Metode 1,2,4 putaran ke titik terdekat dalam array (misalnya> = 1,5 -> 2), dan metode 5 selalu dibulatkan ke atas (misalnya 1,45 -> 2). Hanya metode 3, dan 6, dan tentu saja pembelahan dua memberikan interval dengan benar.

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

Untuk pembagian dua array besar memberikan 4us dibandingkan 180us terbaik berikutnya dan 1.21 ms terpanjang (~ 100 - 1000 kali lebih cepat). Untuk array yang lebih kecil ~ 2-100 kali lebih cepat.

Berikut ini ekstensi untuk menemukan vektor terdekat dalam array vektor.

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

Jika Anda tidak ingin menggunakan numpy ini akan melakukannya:

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

Berikut adalah versi yang akan menangani larik "nilai" non-skalar:

import numpy as np

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

Atau versi yang mengembalikan tipe numerik (mis. Int, float) jika input skalar:

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]

Ini adalah versi dengan scipy untuk @Ari Onasafari, jawab " untuk menemukan vektor terdekat dalam array vektor "

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

Ini adalah versi cepat dari solusi @ Dimitri jika Anda memiliki banyak hal valuesuntuk dicari ( valuesbisa berupa array multi-dimensi):

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

Tolak ukur

> 100 kali lebih cepat daripada menggunakan forloop dengan solusi @ 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

Untuk array besar, jawaban (luar biasa) yang diberikan oleh @ Demitri jauh lebih cepat daripada jawaban yang saat ini ditandai sebagai yang terbaik. Saya telah menyesuaikan algoritme persisnya dengan dua cara berikut:

1. Fungsi di bawah ini berfungsi apakah array input diurutkan atau tidak.

2. Fungsi di bawah ini mengembalikan indeks array input yang sesuai dengan nilai terdekat, yang agak lebih umum.

Perhatikan bahwa fungsi di bawah ini juga menangani kasus tepi tertentu yang akan mengarah ke bug dalam fungsi asli yang ditulis oleh @ Demitri. Kalau tidak, algoritma saya identik dengan miliknya.

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

Ini adalah versi vektor dari jawaban 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)

Saya pikir cara yang paling pythonic adalah:

 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)

Ini adalah kode dasar. Anda dapat menggunakannya sebagai fungsi jika Anda mau

Semua jawaban bermanfaat untuk mengumpulkan informasi untuk menulis kode yang efisien. Namun, saya telah menulis skrip Python kecil untuk mengoptimalkan berbagai kasus. Ini akan menjadi kasus terbaik jika array yang disediakan diurutkan. Jika seseorang mencari indeks dari titik terdekat dari nilai yang ditentukan, maka bisectmodul adalah yang paling efisien waktu. Ketika satu pencarian indeks sesuai dengan array, yang numpy searchsortedpaling efisien.

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)

Dalam [63]:% time bisect.bisect_left (xlist, 0.3) Waktu CPU: pengguna 0 ns, sistem: 0 ns, total: 0 ns Waktu dinding: 22.2 µs

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

Dalam [64]:% waktu np.searchsorted (xar, 0.3, side = "left") Waktu CPU: pengguna 0 ns, sys: 0 ns, total: 0 ns Waktu dinding: 98,9 µs

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

% waktu np.searchsorted (xar, randpts, side = "left") Waktu CPU: pengguna 4 ms, sistem: 0 ns, total: 4 ms Waktu dinding: 1,2 ms

Jika kita mengikuti aturan multiplikasi, maka numpy harus mengambil ~ 100 ms yang menyiratkan ~ 83X lebih cepat.

Untuk array 2d, untuk menentukan posisi i, j dari elemen terdekat:

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

Mungkin bermanfaat untuk ndarrays:

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