Найти ближайшее значение в массиве NumPy

336

Есть ли простой способ, например, функция, чтобы найти ближайшее значение в массиве?

Пример:

np.find_nearest( array, value )
Fookatchu
источник

Ответы:

517
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
unutbu
источник
52
@EOL: return np.abs(array-value).min()дает неправильный ответ. Это дает вам минимум абсолютного значения расстояния, и каким-то образом нам нужно вернуть фактическое значение массива. Мы могли бы добавить valueи приблизиться, но абсолютное значение бросает
рывок
9
@ ~ unutbu Ты прав, мой плохой. Я не могу придумать ничего лучше твоего решения!
Эрик О Лебигот
24
кажется сумасшедшим, нет встроенной функции, которая делает это.
ДБЛИС
3
@jsmedmar Метод деления пополам (см. мой ответ ниже) - O (log (n)).
Джош Альберт
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.Использование idxminвместо argminменя работает с решением выше. (v3.6.4)
jorijnsmit
78

Если ваш массив отсортирован и он очень большой, это гораздо более быстрое решение:

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]

Это масштабируется до очень больших массивов. Вы можете легко изменить вышеупомянутое для сортировки в методе, если вы не можете предположить, что массив уже отсортирован. Для маленьких массивов это излишне, но как только они становятся большими, это намного быстрее.

Demitri
источник
Это звучит как самое разумное решение. Интересно, почему так медленно? Обычный np.searchsortedзанимает около 2 мкс для моего тестового набора, вся функция около 10 мкс. Использование np.absстановится еще хуже. Понятия не имею, что там делает питон.
Майкл
2
@Michael Для отдельных значений математические процедуры Numpy будут медленнее, чем mathпроцедуры, см. Этот ответ .
Демитри
3
Это лучшее решение, если у вас есть несколько значений, которые вы хотите просмотреть одновременно (с некоторыми изменениями). Целое if/elseдолжно быть заменено наidx = idx - (np.abs(value - array[idx-1]) < np.abs(value - array[idx])); return array[idx]
coderforlife
3
Это здорово, но не работает, если valueбольше, чем arrayсамый большой элемент. Я изменил ifзаявление, чтобы if idx == len(array) or math.fabs(value - array[idx - 1]) < math.fabs(value - array[idx])оно работало на меня!
Никоко
3
Это не работает, когда idx равен 0. Если должно читаться:if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])):
JPaget
52

С небольшой модификацией ответ выше работает с массивами произвольной размерности (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]

Или написано в одну строку:

a.flat[np.abs(a - a0).argmin()]
kwgoodman
источник
6
«Плоский» бит не нужен. a[np.abs(a-a0).argmin)]работает отлично.
Макс Шрон
2
На самом деле, это все еще работает только для одного измерения, так как argmin () дает несколько результатов на столбец / измерение. Также у меня была опечатка. Это работает, по крайней мере , для 2 -х измерениях: a[np.sum(np.square(np.abs(a-a0)),1).argmin()].
Макс Шрон
3
Таким образом, это не работает для более высоких измерений, и ответ должен быть удален (или изменен, чтобы отразить это)
Hugues Fontenelle
11
Пожалуйста, приведите пример, когда предлагаемый ответ не работает. Если вы найдете один, я изменю свой ответ. Если вы не можете найти его, то можете ли вы удалить свои комментарии?
kwgoodman
18

Краткое изложение ответа : если у вас есть сортировка, arrayто код деления пополам (приведенный ниже) работает быстрее всего. ~ 100-1000 раз быстрее для больших массивов и ~ 2-100 раз быстрее для маленьких массивов. Это также не требует NumPy. Если у вас есть несортированный, arrayто, если arrayон большой, следует сначала рассмотреть использование сортировки O (n logn), а затем разделить пополам, а если arrayон мал, то метод 2 кажется самым быстрым.

Сначала вы должны уточнить, что вы подразумеваете под ближайшим значением . Часто нужно, чтобы интервал в абсциссе, например, массив = [0,0.7,2.1], значение = 1,95, ответом будет idx = 1. Я подозреваю, что это именно тот случай (в противном случае следующее очень легко можно изменить с помощью условного оператора последующего действия, когда вы найдете интервал). Я отмечу, что оптимальный способ сделать это - разделить пополам (что я предоставлю первым - заметьте, что он вообще не требует numpy и работает быстрее, чем использование numpy функций, поскольку они выполняют избыточные операции). Затем я приведу сравнение времени с другими, представленными здесь другими пользователями.

Bisection:

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

Теперь я определю код из других ответов, каждый из которых возвращает индекс:

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

Теперь я определю время кодов: обратите внимание, методы 1,2,4,5 не дают правильный интервал. Методы 1,2,4 округляют до ближайшей точки в массиве (например,> = 1,5 -> 2), а метод 5 всегда округляет (например, 1,45 -> 2). Только методы 3, 6 и, конечно, деление пополам дают правильный интервал.

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

Для большого массива бисекция дает 4us по сравнению со следующими лучшими 180us и самой длинной 1,21 мс (~ 100 - 1000 раз быстрее). Для меньших массивов это в 2-100 раз быстрее.

Джош Альберт
источник
2
Вы предполагаете, что массив отсортирован. Есть много причин, по которым кто-то не хочет сортировать массив: например, если массив представляет точки данных на линейном графике.
user1917407
7
Стандартная библиотека Python уже содержится в реализации алгоритма деления пополам: docs.python.org/3.6/library/bisect.html
Феликс,
Когда вы сказали: «Если arrayмало, то метод 2 кажется самым быстрым». как мало ты имел в виду @JoshAlbert?
Зевс
2
Это не находит ближайшее значение, оно находит следующее наименьшее значение.
Эндолит
@endolith это только для пополам.
Гомер Эсмеральдо
17

Вот расширение, чтобы найти ближайший вектор в массиве векторов.

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])
Onasafari
источник
Я думаю, что norm(..., axis=-1)должно быть быстрее, чем извлекать x,yзначения через итерацию Python. Кроме того, x,yздесь скаляры? Тогда norm(x+y)это ошибка, так как, например, расстояние (+1, -1)будет рассматриваться как 0.
CFH
Это сработало для меняidx = np.array([np.linalg.norm(x+y) for (x,y) in abs(array-value)]).argmin()
ezchx
9

Если вы не хотите использовать numpy, это сделает это:

def find_nearest(array, value):
    n = [abs(i-value) for i in array]
    idx = n.index(min(n))
    return array[idx]
Ник Кроуфорд
источник
9

Вот версия, которая будет обрабатывать нескалярный массив «значений»:

import numpy as np

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

Или версия, которая возвращает числовой тип (например, int, float), если ввод скалярный:

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]
ryggyr
источник
Хороший ответ, я никогда не использовал outerметод ufunc прежде, я думаю, что буду использовать его больше в будущем. array[indices]Кстати, первая функция должна вернуться .
Виджет
1
Это решение не масштабируется. np.subtract.outerбудет генерировать всю матрицу внешнего продукта, которая действительно медленная и требует много памяти, если arrayи / или valuesочень велика.
Энтонибелл
8

Вот версия со scipy для @Ari Onasafari, ответьте « найти ближайший вектор в массиве векторов »

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])
efirvida
источник
Построение KDTree - непростая задача для такой проблемы. Я бы не рекомендовал такое решение, если вам не нужно делать несколько запросов к большому массиву ... И тогда было бы лучше создать его один раз и использовать повторно, а не создавать его на лету для каждого запроса.
Бен
8

Вот быстрая векторизованная версия решения @ Dimitri, если у вас есть много valuesдля поиска ( valuesможет быть многомерный массив):

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

Ориентиры

> В 100 раз быстрее, чем использование forцикла с решением @ 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
anthonybell
источник
если у вас есть постоянная выборка в массиве, это становится еще проще: idx = np.searchsorted(array, values)затем: idx[array[idx] - values>np.diff(array).mean()*0.5]-=1и наконецreturn array[idx]
Сергей Антопольский
7

Для больших массивов (превосходный) ответ, данный @Demitri, намного быстрее, чем ответ, который в настоящее время помечен как лучший. Я адаптировал его точный алгоритм следующими двумя способами:

  1. Функция ниже работает независимо от того, отсортирован ли входной массив.

  2. Функция ниже возвращает индекс входного массива, соответствующий ближайшему значению, которое является несколько более общим.

Обратите внимание, что нижеприведенная функция также обрабатывает определенный край, который может привести к ошибке в исходной функции, написанной @Demitri В остальном мой алгоритм идентичен его.

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
APH
источник
1
Стоит отметить, что это отличный пример того, как оптимизация кода делает его более уродливым и трудным для чтения. Ответ, данный @unutbu, должен быть (очень) предпочтительным в тех случаях, когда скорость не является серьезной проблемой, поскольку она гораздо более прозрачна.
APH
Я не вижу ответа от @Michael. Это ошибка или я слепой?
Фукачу
Нет, ты не слепой, я просто неграмотный ;-) Это был ответ @Demitri, на который я намекал. Виноват. Я только исправил свой пост. Спасибо!
APH
Я получаю разные ответы с Демитри и твоими. Любые идеи? x = np.array([2038, 1758, 1721, 1637, 2097, 2047, 2205, 1787, 2287, 1940, 2311, 2054, 2406, 1471, 1460]), С find_nearest(x, 1739.5)(ближайшее значение к первому квантилю), я получаю 1637(разумно) и 1(ошибка?).
PatrickT
3

Это векторизованная версия ответа 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

Я думаю, что самый питонический способ будет:

 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)

Это основной код. Вы можете использовать его как функцию, если хотите

Ишан Томар
источник
2

Все ответы полезны для сбора информации для написания эффективного кода. Тем не менее, я написал небольшой скрипт на Python для оптимизации под различные случаи. Это будет лучший случай, если предоставленный массив отсортирован. При поиске по индексу ближайшей точки заданного значения bisectмодуль наиболее эффективен по времени. Когда один поиск индексов соответствует массиву, numpy searchsortedэто наиболее эффективно.

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)

В [63]:% time bisect.bisect_left (xlist, 0.3) Время ЦП: пользователь 0 нс, sys: 0 нс, всего: 0 нс Время стены: 22,2 мкс

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

В [64]:% time np.searchsorted (xar, 0.3, side = "left") Время ЦП: пользователь 0 нс, sys: 0 нс, всего: 0 нс Время стены: 98,9 мкс

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

% time np.searchsorted (xar, randpts, side = "left") Время ЦП: пользователь 4 мс, sys: 0 нс, всего: 4 мс Время ожидания: 1,2 мс

Если мы следуем мультипликативному правилу, тогда numpy должен занять ~ 100 мс, что означает ~ 83X быстрее.

Soumen
источник
1

Для двумерного массива определить позицию i, j ближайшего элемента:

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
Привет, добро пожаловать в Stack Overflow. Проверьте, как написать хороший ответ . Попробуйте дать краткое описание того, что вы сделали в контексте вопроса!
Tristo
0

Может быть полезно для ndarrays:

def find_nearest(X, value):
    return X[np.unravel_index(np.argmin(np.abs(X - value)), X.shape)]
Гусев Слава
источник