在两个二维数组中查找所有接近的数字匹配项

Question

更新：我将解决方案制作成一个名为close-numerical-matches的库。

我正在寻找一种方法来查找两个二维数组之间的所有接近匹配项（在一定公差范围内），并获取找到的匹配项的索引数组。 SO 上的多个答案显示了如何针对精确匹配（通常使用字典）解决此问题，但这不是我要找的。让我举个例子：

>>> arr1 = [
    [19.21, 19.19],
    [13.18, 11.55],
    [21.45,  5.83]
]
>>> arr2 = [
    [13.11, 11.54],
    [19.20, 19.19],
    [51.21, 21.55],
    [19.22, 19.18],
    [11.21, 11.55]
]
>>> find_close_match_indices(arr1, arr2, tol=0.1)
[[0, 1], [0, 3], [1, 0]]

上面，返回[[0, 1], [0, 3], [1, 0]]是因为arr1、[19.21, 19.19]中的元素0在arr2中元素1和3的容差范围内。顺序对我来说并不重要，即 [[0, 3], [1, 0], [0, 1]] 也可以接受。

arr1的形状是(n, 2)而arr2的形状是(m, 2 ).您可以预期 n 和 m 会很大。现在，我可以使用嵌套的 for 循环轻松地实现这一点，但我相信一定有比将每个元素与所有其他元素进行比较更聪明的方法。

我考虑过使用 k-means 聚类将问题分成 k 个桶，从而使嵌套 for 循环方法更易于处理，但我认为两个接近的元素可能只是在它们每个集群的“边界”处，因此不会被比较。

任何外部依赖项，例如 Numpy、Scipy 等都可以，并且可以使用 O(n + m) space.

Answer 1

你不能用 NO 循环做到这一点，但你可以通过利用布尔索引用一个循环来做到这一点：

import numpy as np

xarr1 = np.array([
    [19.21, 19.19],
    [13.18, 11.55],
    [21.45,  5.83]
])
xarr2 = np.array([
    [13.11, 11.54],
    [19.20, 19.19],
    [51.21, 21.55],
    [19.22, 19.18],
    [11.21, 11.55]
])

def find_close_match_indices(arr1, arr2, tol=0.1):
    results = []
    for i,r1 in enumerate(arr1[:,0]):
        x1 = np.abs(arr2[:,0]-r1) < tol
        results.extend( [i,k] for k in np.where(x1)[0] )
    return results

print(find_close_match_indices(xarr1,xarr2,0.1))

输出：

[[0, 1], [0, 3], [1, 0]]

Answer 2

也许您会发现以下内容有用。可能比@Tim-Roberts 的解决方案更快，因为没有明确的 for 循环。但它会占用更多存储空间。

import numpy as np

xarr1 = np.array([
    [19.21, 19.19],
    [13.18, 11.55],
    [21.45,  5.83]
])
xarr2 = np.array([
    [13.11, 11.54],
    [19.20, 19.19],
    [51.21, 21.55],
    [19.22, 19.18],
    [11.21, 11.55]
])

tol=0.1
xarr1=xarr1[:,None,:]
xarr2=xarr2[None,:,:]
# broadcasting
cc = xarr2-xarr1
cc = np.apply_along_axis(np.linalg.norm,-1,cc)
# or you can use other metrics of closeness e.g. as below
#cc = np.apply_along_axis(np.abs,-1,cc) 
#cc = np.apply_along_axis(np.max,-1,cc)
id1,id2=np.where(cc<tol)

Answer 3

我想到了如何使用存储桶来解决这个问题。这个想法是根据元素的值和容差级别形成一个键。为了确保将桶“边缘”中的潜在匹配项与“边缘”处的其他元素进行比较，所有相邻桶都会进行比较。最后，我修改了@Tim Roberts 稍微执行实际匹配的方法以匹配两列。

我将其制作成一个名为 close-numerical-matches 的库。示例用法：

>>> import numpy as np
>>> from close_numerical_matches import find_matches
>>> arr0 = np.array([[25, 24], [50, 50], [25, 26]])
>>> arr1 = np.array([[25, 23], [25, 25], [50.6, 50.6], [60, 60]])
>>> find_matches(arr0, arr1, tol=1.0001)
array([[0, 0], [0, 1], [1, 2], [2, 1]])
>>> find_matches(arr0, arr1, tol=0.9999)
array([[1, 2]])
>>> find_matches(arr0, arr1, tol=0.60001)
array([], dtype=int64)
>>> find_matches(arr0, arr1, tol=0.60001, dist='max')
array([[1, 2]])
>>> manhatten_dist = lambda arr: np.sum(np.abs(arr), axis=1)
>>> matches = find_matches(arr0, arr1, tol=0.11, dist=manhatten_dist)
>>> matches
array([[0, 1], [0, 1], [2, 1]])
>>> indices0, indices1 = matches.T
>>> arr0[indices0]
array([[25, 24], [25, 24], [25, 26]])

一些分析：

from timeit import default_timer as timer
import numpy as np
from close_numerical_matches import naive_find_matches, find_matches

arr0 = np.random.rand(320_000, 2)
arr1 = np.random.rand(44_000, 2)

start = timer()
naive_find_matches(arr0, arr1, tol=0.001)
end = timer()
print(end - start)  # 255.335 s

start = timer()
find_matches(arr0, arr1, tol=0.001)
end = timer()
print(end - start)  # 5.821 s

在两个二维数组中查找所有接近的数字匹配项

Find all close numerical matches in two 2D arrays

python

numpy

match