logo标签列表

在二维数组/矩阵中查找前k个最大值的索引

pythonnumpy
3
我可以帮您翻译关于IT技术的内容。"Original Answer"可以翻译成"原始答案"。以下是您需要翻译的内容：

我有一个包含数值的二维矩阵，我想找到其中前五个最大数值的索引。例如：

matrix([[0.17542851, 0.13199346, 0.01579704, 0.01429822, 0.01302919],
        [0.13279703, 0.12444886, 0.04742024, 0.03114371, 0.02623729],
        [0.13502306, 0.07815065, 0.07291175, 0.03690815, 0.02163695],
        [0.19032505, 0.15853737, 0.05889324, 0.02791679, 0.02699252],
        [0.1695696 , 0.14538635, 0.07127667, 0.04997876, 0.02580234]])

我希望获得(0,3), (0,1), (0,4), (3,1), (4,1)

我尝试了许多解决方法，包括np.argmax(), np.argsort(), np.argpartition()，但都没有好的结果。

例如： 

>>np.dstack(np.unravel_index(np.argsort(a.ravel(),axis=None), a.shape))

array([[[0, 4],
        [0, 3],
        [0, 2],
        [2, 4],
        [4, 4],
        [1, 4],
        [3, 4],
        [3, 3],
        [1, 3],
        [2, 3],
        [1, 2],
        [4, 3],
        [3, 2],
        [4, 2],
        [2, 2],
        [2, 1],
        [1, 1],
        [0, 1],
        [1, 0],
        [2, 0],
        [4, 1],
        [3, 1],
        [4, 0],
        [0, 0],
        [3, 0]]], dtype=int64)

这个结果毫无意义。请注意，我需要原始索引，不在乎顺序（只想要前5个，任何顺序都可以，但升序会更好）

翻译后：

这个结果没有意义。请注意，我需要原始的索引，不关心它们的顺序（只需要前五个，无论什么顺序，升序会更好）。

以下发布的解决方案对您有用吗？ - Divakar
@Divakar 是的，所有的都能完成这个任务，但有点复杂，所以我在尝试弄清楚哪种对长期使用来说更容易一些。 - M.F
4个回答
2

您的示例：

n = np.array([[0.17542851, 0.13199346, 0.01579704, 0.01429822, 0.01302919],
        [0.13279703, 0.12444886, 0.04742024, 0.03114371, 0.02623729],
        [0.13502306, 0.07815065, 0.07291175, 0.03690815, 0.02163695],
        [0.19032505, 0.15853737, 0.05889324, 0.02791679, 0.02699252],
        [0.1695696 , 0.14538635, 0.07127667, 0.04997876, 0.02580234]])

你的输出不是前五个值的索引。前五个值为：

最初的回答

array([0.14538635, 0.15853737, 0.1695696 , 0.17542851, 0.19032505])

为了获得它们的索引：使用sort函数并使用isin函数标记它们的位置为True。最后，使用argwhere函数获取它们的位置。"最初的回答"
np.argwhere(np.isin(n, np.sort(n, axis=None)[-5:]))

Out[324]:
array([[0, 0],
       [3, 0],
       [3, 1],
       [4, 0],
       [4, 1]], dtype=int32)
2

np.argpartition 是一个高效的工具，可以获取前 k 个索引而无需维护顺序。因此，对于数组数据 a，使用该函数即可 -

最初的回答：使用 np.argpartition 函数可以高效地获取前 k 个索引，而无需维护顺序。对于数组数据 a，只需调用该函数即可。
In [43]: np.c_[np.unravel_index(np.argpartition(a.ravel(),-5)[-5:],a.shape)]
Out[43]: 
array([[4, 1],
       [3, 1],
       [4, 0],
       [0, 0],
       [3, 0]])

为了解释清楚，让我们将其分解为单个流程步骤 -
# Get partitioned indices such that the last 5 indices refer to the top 5
# values taken globally from the input array. Refer to docs for more info
# Note that it's global because we will flatten it. 
In [9]: np.argpartition(a.ravel(),-5)
Out[9]: 
array([14, 24,  2,  3,  4, 23, 22,  7,  8,  9, 19, 18, 17, 13, 12, 11,  6,
        1,  5, 10, 21, 16, 20,  0, 15])

# Get last 5 indices, which are the top 5 valued indices
In [10]: np.argpartition(a.ravel(),-5)[-5:]
Out[10]: array([21, 16, 20,  0, 15])

# Convert the global indices back to row-col format
In [11]: np.unravel_index(np.argpartition(a.ravel(),-5)[-5:],a.shape)
Out[11]: (array([4, 3, 4, 0, 3]), array([1, 1, 0, 0, 0]))

# Stack into two-columnar array
In [12]: np.c_[np.unravel_index(np.argpartition(a.ravel(),-5)[-5:],a.shape)]
Out[12]: 
array([[4, 1],
       [3, 1],
       [4, 0],
       [0, 0],
       [3, 0]])

对于矩阵数据a，最初的回答是 -
In [48]: np.dstack(np.unravel_index(np.argpartition(a.ravel(),-5)[:,-5:],a.shape))
Out[48]: 
array([[[4, 1],
        [3, 1],
        [4, 0],
        [0, 0],
        [3, 0]]])

因此，与数组相比，唯一的区别在于使用了np.dstack，因为对于矩阵数据而言，数据始终保持为二维。

请注意，这些是您从最后5行获得的结果。

注：Original Answer 翻译成“最初的回答”

1
谢谢，请问你能解释一下那里发生了什么吗？ - M.F
@M.F 添加了解释。 - Divakar
1
假设您有一个列表嵌套的列表：
In [112]: M                                                                                                                                                                                                                                                                                                                   
Out[112]: 
[[0, 1, 2, 3, 4],
 [5, 6, 7, 8, 9],
 [10, 11, 12, 13, 14],
 [15, 16, 17, 18, 19],
 [20, 21, 22, 23, 24]]

In [113]: heapq.nlargest(5, ((r,c) for r in range(len(M)) for c in range(len(M[r]))), key=lambda t: M[t[0]][t[1]])                                                                                                                                                                                                            
Out[113]: [(4, 4), (4, 3), (4, 2), (4, 1), (4, 0)]

不要忘记导入堆模块：import heapq
0

我从一个引用了@Divakar（非常优雅和快速）答案的问题中来到这里。

排名中常见的问题是如何处理重复项（并列）。

在某些情况下，使用“密集排名”是可取的，其中[4, 7, 7, 9]将按升序排名：[0, 1, 1, 2]。

相比之下，@Divakar的答案基本上反映了“序数排名”，其中[4, 7, 7, 9]将按升序排名[0, 1, 2, 3]。这在“前k”问题中可能会稍微有些不直观。例如，在：

b = np.array(
    [[8, 6, 3],
    [6, 7, 2],
    [0, 8, 9]])

假设按降序排列，带有等级k=2的结果如下：

k = 2
>>> np.c_[np.unravel_index(np.argpartition(b.ravel(),-k)[-k:], b.shape)]
array([[2, 1],
       [2, 2]])

这对应于9和仅有的8个值之一，省略了另外的8个值。

如果有人对“密集排名”感兴趣，我建议采用以下方法（它以“任何顺序”返回前k个值的所有索引--实际上是按索引顺序）：

def topk_indices(a, k):
    _, rix = np.unique(-a, return_inverse=True)
    return np.c_[np.unravel_index(np.where(rix < k)[0], a.shape)]

关于OP的数组：
>>> topk_indices(a, 5)
array([[0, 0],
       [3, 0],
       [3, 1],
       [4, 0],
       [4, 1]])

在上面的 int 数组中：

>>> topk_indices(b, 2)
array([[0, 0],
       [2, 1],
       [2, 2]])

性能

就性能而言，@Divakar的答案比这个快5倍到10倍，对于各种维度和参数的广泛测试。因此，如果您认为没有关联或者您不在意，那么请使用它代替这个。

例如：

a = np.random.randint(0, 10, (1_000_000, 2))
t0 = %timeit -o topk_indices(a, 5)
# 157 ms ± 1.61 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

t1 = %timeit -o divakar_topk_indices(a, 5)
# 25.1 ms ± 49.5 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> t0.average / t1.average
6.24

顺便提一下，整个数组排序（O(n log n)）只为找到前k个元素让我感到不舒服...更合理的heapq方法更具可扩展性（O(n log k)），但有更大的常数乘数（仅heapq.nlargest(5, a.ravel())就需要211毫秒，而这只是返回值，没有索引。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接