无法理解numpy argpartition输出

Question

我试图从numpy使用arpgpartition,但似乎出现了问题,我似乎无法弄明白.这是发生了什么:

这些是排序数组的前5个元素 norms

np.sort(norms)[:5]
array([ 53.64759445,  54.91434479,  60.11617279,  64.09630585,  64.75318909], dtype=float32)

但是当我使用时 indices_sorted = np.argpartition(norms, 5)[:5]

norms[indices_sorted]
array([ 60.11617279,  64.09630585,  53.64759445,  54.91434479,  64.75318909], dtype=float32)

当我认为我应该得到与排序数组相同的结果？

当我使用3作为参数时,它工作得很好 indices_sorted = np.argpartition(norms, 3)[:3]

norms[indices_sorted]
array([ 53.64759445,  54.91434479,  60.11617279], dtype=float32)

这对我来说没有多大意义,希望有人可以提供一些见解？

编辑:将这个问题改为argpartition是否保留k个分区元素的顺序更有意义.

Answer 1

我们需要使用按排序顺序保存的索引列表,而不是将第k个参数作为标量.因此,为了保持第一个5元素的排序性质,而不是np.argpartition(a,5)[:5]简单地做 -

np.argpartition(a,range(5))[:5]

这是一个让事情变得清晰的示例 -

In [84]: a = np.random.rand(10)

In [85]: a
Out[85]: 
array([ 0.85017222,  0.19406266,  0.7879974 ,  0.40444978,  0.46057793,
        0.51428578,  0.03419694,  0.47708   ,  0.73924536,  0.14437159])

In [86]: a[np.argpartition(a,5)[:5]]
Out[86]: array([ 0.19406266,  0.14437159,  0.03419694,  0.40444978,  0.46057793])

In [87]: a[np.argpartition(a,range(5))[:5]]
Out[87]: array([ 0.03419694,  0.14437159,  0.19406266,  0.40444978,  0.46057793])

请注意,argpartition在性能方面有意义,如果我们希望得到一小部分元素的排序索引,那么就说kelems 的数量只是elems总数的一小部分.

让我们使用更大的数据集并尝试获取所有元素的排序索引,以使上述要点清晰 -

In [51]: a = np.random.rand(10000)*100

In [52]: %timeit np.argpartition(a,range(a.size-1))[:5]
10 loops, best of 3: 105 ms per loop

In [53]: %timeit a.argsort()
1000 loops, best of 3: 893 µs per loop

因此,排序所有元素,np.argpartition不是要走的路.

现在,让我们说我想要获得那个大数据集的前5个元素的排序索引,并保留那些的顺序 -

In [68]: a = np.random.rand(10000)*100

In [69]: np.argpartition(a,range(5))[:5]
Out[69]: array([1647,  942, 2167, 1371, 2571])

In [70]: a.argsort()[:5]
Out[70]: array([1647,  942, 2167, 1371, 2571])

In [71]: %timeit np.argpartition(a,range(5))[:5]
10000 loops, best of 3: 112 µs per loop

In [72]: %timeit a.argsort()[:5]
1000 loops, best of 3: 888 µs per loop

这里非常实用!

Answer 2

让我们以简化的方式描述分区方法，这有助于很多理解argpartition

按照图片中的示例，如果我们执行C=numpy.argpartition(A, 3) C 将是获取 B 中每个元素相对于 A 数组的位置的结果数组。IE：

Idx(z) = index of element z in array A

then C would be

C = [ Idx(B[0]), Idx(B[1]), Idx(B[2]), Idx(X), Idx(B[4]), ..... Idx(B[N]) ]

如前所述，这种方法非常有用，当您有一个巨大的数组并且您只对选定的一组有序元素而不是整个数组感兴趣时，它会非常方便。

Answer 3

鉴于直接对子集进行排序的任务(排名顺序中的前k,顶部意义首先)有两个内置解决方案:argsort和argpartitioncf. @Divakar的回答.

然而,如果性能是一个考虑因素,那么它可能(取决于数据的大小和感兴趣的子集)非常值得抵制"单线的诱惑",再投资一条线并应用argsort以下输出argpartition:

>>> def top_k_sort(a, k):
...     return np.argsort(a)[:k]
...
>>> def top_k_argp(a, k):
...     return np.argpartition(a, range(k))[:k]
...
>>> def top_k_hybrid(a, k):
...     b = np.argpartition(a, k)[:k]
...     return b[np.argsort(a[b])]

>>> k = 100
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_sort, 'rng': np.random.random, 'k': k})
8.348663672804832
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_argp, 'rng': np.random.random, 'k': k})
9.869098862167448
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_hybrid, 'rng': np.random.random, 'k': k})
1.2305558240041137

argsort是O(n log n),argpartition范围参数看起来是O(nk)(？),argpartition+ argsort是O(n + k log k)

因此,在一个有趣的方案n >> k >> 1中,混合方法预计是最快的