在numpy数组中找到最接近的值

Question

如何在numpy数组中找到最接近的值？例如：

np.find_nearest(array, value)

- Fookatchu

Answer 1

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]

print(find_nearest(array, value=0.5))
# 0.568743859261

- unutbu

---

@EOL: return np.abs(array-value).min()这个函数的结果是错误的。它仅返回了每个元素与给定值的差的绝对值的最小值，我们需要返回最接近给定值的实际数组元素。虽然我们可以添加给定值 value 来实现更接近的结果，但是绝对值的存在使问题变得复杂... - unutbu

你说得对，我的错。我想不出比你的解决方案更好的东西！ - Eric O. Lebigot

似乎很疯狂，竟然没有一个内置的NumPy函数可以做到这一点。 - abcd

重要警告：如果您的数据包含np.nan，则这些点将始终被认为是最近的。 - johanvdw

哇，那几乎可以算作一个bug。要修复它，将 np.argmin() 替换为 np.nanargmin() 就可以了。 - eric

Answer 2

如果您的数组已经排序并且非常大，这是一个更快的解决方案:

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甚至更糟。不知道Python在那里做了什么。 - Michael

@Michael 对于单个值，Numpy数学函数的速度比math函数慢，参见这个答案。 - Demitri

如果您想一次查找多个值（需要进行一些调整），那么这是最佳解决方案。整个 if/else 需要替换为 idx = idx - (np.abs(value - array[idx-1]) < np.abs(value - array[idx])); return array[idx]。 - coderforlife

这很棒，但如果“value”大于“array”的最大元素，则无法使用。我将“if”语句更改为“if idx == len(array) or math.fabs(value - array[idx - 1]) < math.fabs(value - array[idx])”，以使其适用于我的情况！ - nicoco

当idx为0时，这个方法不起作用。if语句应该改为：if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])): - JPaget

Answer 3

稍加修改后，上面的答案可用于任意维度的数组（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

---

“flat”一词并非必要。a[np.abs(a-a0).argmin)]即可。 - Max Shron

在Max Shron之前的评论中，它不适用于二维或多维情况。 - relent95

Answer 4

答案摘要: 如果数组已排序，则下面给出的二分代码运行速度最快，对于大数组，速度约为100-1000倍，对于小数组，速度约为2-100倍。它不需要numpy。 如果数组未排序，则如果数组很大，则应首先使用O(n logn)排序，然后再使用二分法，如果数组很小，则方法2似乎是最快的。 首先，您应该澄清什么是最接近的值。通常，人们希望在横坐标上获得间隔，例如array=[0,0.7,2.1]，value=1.95，则答案将是idx=1。我怀疑这就是您需要的情况（否则，一旦找到间隔，以下内容可以轻松修改为跟进条件语句）。我将注意到，执行此操作的最佳方法是使用二分法（我将首先提供它 - 请注意，它根本不需要numpy，并且比使用numpy函数更快，因为它们会执行冗余操作）。然后，我将提供其他用户提供的其他方法的定时比较。

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

对于大型数组，二分法的时间为4微秒，而下一个最好的方法需要180微秒，最长需要1.21毫秒（比其他方法快100-1000倍）。对于较小的数组，速度会更快，大约快2-100倍。

- Josh Albert

---

你假设数组已经排序了。有很多原因为什么有人不想对数组进行排序：例如，如果数组代表线图上的数据点。 - adamcircle

Python标准库已经包含了二分法算法的实现：https://docs.python.org/3.6/library/bisect.html - Felix

当你说：“如果array很小，那么方法2似乎是最快的。”时，@JoshAlbert，你指的是多小？ - Mr.Zeus

这并不是找到最接近的值，而是找到下一个最低的值。 - endolith

@endolith 这只适用于二分查找。 - Homero Esmeraldo

Answer 5

如果您有许多要搜索的values（values可以是多维数组），这里是@Dimitri方案的快速向量化版本：

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

基准测试

> 使用 @Demitri 的解决方案，比使用 for 循环快100倍。

>>> %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] - Sergey Antopolskiy

首先回答“只需运行即可”的问题：get_closest([1,5,10,20], [1,4,16]) -> [1, 5, 20]，这个应该会得到更多的赞。 - David Parks

正是我所需要的，而且速度非常快！非常感谢你，安东尼！ - egor.ananyev

有没有简单的方法来区分给定值是应该在左边（比如低于）还是右边（比如高于）最近？ - Flash Thunder

请注意，根据np.searchsorted要求，输入变量 array 需要按升序排序。 - nwly

即使数组因传入 array[3：] 而移动索引，它仍然可以正常工作。完美！ - YPOC

Answer 6

这是一个可以在向量数组中找到最近向量的扩展。

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)比通过Python迭代提取x,y值更快。此外，这里的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

Answer 7

如果您不想使用numpy，可以使用以下代码：

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

- Nick Crawford

Answer 8

这是一个可以处理非标量“values”数组的版本：

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

---

好的答案，我以前从未使用过ufunc的outer方法，我想我将来会更多地使用它。顺便说一下，第一个函数应该返回array[indices]。 - Widjet

这个解决方案不具备可扩展性。如果array和/或values非常大，np.subtract.outer将生成整个外积矩阵，这会非常缓慢且占用大量内存。 - anthonybell

Answer 9

这是一个包含scipy的版本，用于在矢量数组中找到最近的矢量。

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

---

构建KD树对于这样的问题来说是相当繁琐的。除非你需要在一个大数组上进行多次查询，否则我不建议使用这种解决方案...然后，最好只构建一次并重复使用它，而不是为每个查询即时创建它。 - Ben

Answer 10

对于大数组，@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

---

值得指出的是，这是一个很好的例子，说明优化代码会使其变得更加丑陋和难以阅读。在速度不是主要关注点的情况下，应该（更）偏爱@unutbu所给出的答案，因为它更加透明易懂。 - aph

我没有看到@Michael给出的答案。这是一个错误还是我眼瞎了？ - Fookatchu

不好意思，你没有看错，我只是文盲；-) 我的回答是基于@Demitri的答案。我的错误。我刚刚修正了我的帖子。谢谢！ - aph

我用Demitri和你的方法得到了不同的答案。有什么想法吗？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

同意PatrickT的观点，这个版本有漏洞。推荐@anthonybell的解决方案，比Demitri的更快。 - nwly