时间戳

首页 > 解决方案 > Numpy在二维数组中查找公共点的索引

python - Numpy在二维数组中查找公共点的索引

问题描述

系统

操作系统： Windows 10 (x64)，Build 1909
Python 版本： 3.8.10
Numpy 版本： 1.21.2

问题

给定两个浮点数据点的 2D (N, 3)Numpy 数组，(x, y, z)在一个数组中查找点与另一个数组中的点相等的索引的 Pythonic（矢量化）方法是什么？

（注意： 我的问题不同之处在于我需要它来处理实际数据集，其中两个数据集可能因浮点错误而有所不同。请阅读下面的详细信息。）

历史

类似的问题已经被问过很多次了：

  1. 如何找到另一个二维数组中出现的二维numpy数组的索引
  2. 测试二维 numpy 数组中的成员资格
  3. 获取 Numpy 2d 数组相交行的索引
  4. 在另一个二维数组中查找 numpy 二维数组行的索引
  5. Numpy 2d Array 相交行的索引
  6. 在另一个二维数组中查找 numpy 二维数组行的索引

以前的尝试

SO Post 1提供了一个工作列表理解解决方案，但我正在寻找一种能够很好地扩展到大型数据集（即数百万点）的解决方案：

代码1：

import numpy as np

if __name__ == "__main__":
    big_array = np.array(
        [
            [1.0, 2.0, 1.2],
            [5.0, 3.0, 0.12],
            [-1.0, 14.0, 0.0],
            [-9.0, 0.0, 13.0],
        ]
    )

    small_array = np.array(
        [
            [5.0, 3.0, 0.12],
            [-9.0, 0.0, 13.0],
        ]
    )

    inds = [
        ndx
        for ndx, barr in enumerate(big_array)
        for sarr in small_array
        if all(sarr == barr)
    ]

    print(inds)

输出1：

[1, 2]

尝试SO Post 3的解决方案（类似于SO Post 2），但使用浮点数不起作用（我怀疑np.isclose需要使用一些东西）：

代码3：

import numpy as np

if __name__ == "__main__":
    big_array = np.array(
        [
            [1.0, 2.0, 1.2],
            [5.0, 3.0, 0.12],
            [-1.0, 14.0, 0.0],
            [-9.0, 0.0, 13.0],
        ],
        dtype=float,
    )

    small_array = np.array(
        [
            [5.0, 3.0, 0.12],
            [-9.0, 0.0, 13.0],
        ],
        dtype=float,
    )

    inds = np.nonzero(
        np.in1d(big_array.view("f,f").reshape(-1), small_array.view("f,f").reshape(-1))
    )[0]

    print(inds)

输出3：

[ 3  4  5  8  9 10 11]

我的尝试

我试过numpy.isin和np.allnp.argwhere

inds = np.argwhere(np.all(np.isin(big_array, small_array), axis=1)).reshape(-1)

哪个有效（并且，我认为，更具可读性和可理解性；即pythonic），但不适用于包含浮点错误的真实数据集：

import numpy as np

if __name__ == "__main__":
    big_array = np.array(
        [
            [1.0, 2.0, 1.2],
            [5.0, 3.0, 0.12],
            [-1.0, 14.0, 0.0],
            [-9.0, 0.0, 13.0],
        ],
        dtype=float,
    )

    small_array = np.array(
        [
            [5.0, 3.0, 0.12],
            [-9.0, 0.0, 13.0],
        ],
        dtype=float,
    )

    small_array_fpe = np.array(
        [
            [5.0 + 1e-9, 3.0 + 1e-9, 0.12 + 1e-9],
            [-9.0 + 1e-9, 0.0 + 1e-9, 13.0 + 1e-9],
        ],
        dtype=float,
    )

    inds_no_fpe = np.argwhere(np.all(np.isin(big_array, small_array), axis=1)).reshape(-1)

    inds_with_fpe = np.argwhere(
        np.all(np.isin(big_array, small_array_fpe), axis=1)
    ).reshape(-1)

    print(f"No Floating Point Error: {inds_no_fpe}")
    print(f"With Floating Point Error: {inds_with_fpe}")

    print(f"Are 5.0 and 5.0+1e-9 close?: {np.isclose(5.0, 5.0 + 1e-9)}")

输出：

No Floating Point Error: [1 3]
With Floating Point Error: []
Are 5.0 and 5.0+1e-9 close?: True

如何通过合并使我的上述解决方案工作（在具有浮点错误的数据集上）np.isclose？欢迎替代解决方案。

注意： 由于small_array是 的子集big_array，因此无法直接使用，np.isclose因为形状不会广播：

np.isclose(big_array, small_array_fpe)

产量

ValueError: operands could not be broadcast together with shapes (4,3) (2,3)

更新

目前，我唯一可行的解​​决方案是

inds_with_fpe = [
    ndx
    for ndx, barr in enumerate(big_array)
    for sarr in small_array_fpe
    if np.all(np.isclose(sarr, barr))
]

标签： pythonnumpyfloating-pointclosestisin

解决方案

我不会给出任何代码，但我已经大规模处理过类似的问题。我怀疑要使用这些方法中的任何一种获得不错的性能，您需要在 C 中实现核心（您可能会使用 numba）。

如果您的两个阵列都很大，那么有几种方法可以工作。这些主要归结为构建一个结构，该结构可用于从其中一个数组中找到一个点的最近邻居，然后查询另一个数据集中的每个点。

为此，我之前使用了 Kd Tree 方法和基于网格的方法。

基于网格的方法的基础是

  • 找到你的第一个数组的 3D 范围。
  • 将该区域分成 L N M 个 bin。
  • 对于第二个数组中的每个输入点，找到它的 bin。任何与它匹配的点都将在该 bin 中。

您需要处理的边缘情况是

  • 如果该点落在一个 bin 的边缘，或者足够接近被认为等于它的 bin 的边界，则可能落在另一个 bin 中 - 那么您需要搜索多个 bin 来寻找它的“相等”。
  • 如果该点落在所有 bin 之外，但靠近边缘，则“等于”它的点可能落在附近的 bin 中。

缺点是这对非均匀分布的数据不利。

好处是它相对简单。统一数据的预期运行时间为n1 * n2 / (L*N*M)（与 n1*n2 相比）。通常，您选择 L,N,M 以使其变为O(n log(n))。您还可以从对第二个数组进行排序以提高 bin 的重用性获得进一步的提升。并行化也相对容易（分箱和搜索）

Kd 树方法是类似的。IIRC 它提供了O(n log(n))行为，但实现起来比较棘手，并且数据结构的构建很难并行化）。它往往对缓存不友好，这可能意味着尽管它的渐近运行时间比基于网格的方法更好，但它在实践中可能运行得更慢。然而，它确实为非均匀分布的数据提供了更好的保证。

推荐阅读