wake-up-neo.com

Wie erhalte ich Indizes mit N Maximalwerten in einem NumPy-Array?

NumPy schlägt eine Möglichkeit vor, den Index des Maximalwerts eines Arrays über np.argmax abzurufen.

Ich möchte eine ähnliche Sache, aber die Indizes der N Maximalwerte zurückgeben.

Wenn ich zum Beispiel ein Array habe, würde [1, 3, 2, 4, 5], function(array, n=3) die Indizes [4, 3, 1] zurückgeben, die den Elementen [5, 4, 3] entsprechen.

392

Das einfachste, was ich mir einfallen lassen konnte, ist:

In [1]: import numpy as np

In [2]: arr = np.array([1, 3, 2, 4, 5])

In [3]: arr.argsort()[-3:][::-1]
Out[3]: array([4, 3, 1])

Hierbei handelt es sich um eine vollständige Art des Arrays. Ich frage mich, ob numpy eine eingebaute Möglichkeit bietet, eine Teilsortierung durchzuführen. Bisher habe ich noch keinen gefunden.

Wenn sich herausstellt, dass diese Lösung zu langsam ist (insbesondere für kleine n), lohnt es sich möglicherweise, etwas in Cython zu codieren.

271
NPE

Neuere NumPy-Versionen (1.8 und höher) haben hierfür eine Funktion namens argpartition . Um die Indizes der vier größten Elemente zu erhalten, gehen Sie wie folgt vor

>>> a = np.array([9, 4, 4, 3, 3, 9, 0, 4, 6, 0])
>>> a
array([9, 4, 4, 3, 3, 9, 0, 4, 6, 0])
>>> ind = np.argpartition(a, -4)[-4:]
>>> ind
array([1, 5, 8, 0])
>>> a[ind]
array([4, 9, 6, 9])

Im Gegensatz zu argsort wird diese Funktion im ungünstigsten Fall in linearer Zeit ausgeführt, die zurückgegebenen Indizes werden jedoch nicht sortiert, wie aus dem Ergebnis der Auswertung von a[ind] hervorgeht. Wenn du das auch brauchst, sortiere sie danach:

>>> ind[np.argsort(a[ind])]
array([1, 8, 5, 0])

Um die oberen - k Elemente auf diese Weise in sortierter Reihenfolge zu erhalten, wird O ( n + k verwendet log k ) Zeit.

496
Fred Foo

Noch einfacher:

idx = (-arr).argsort()[:n]

dabei ist n die Anzahl der Maximalwerte.

40
Ketan

Verwenden:

>>> import heapq
>>> import numpy
>>> a = numpy.array([1, 3, 2, 4, 5])
>>> heapq.nlargest(3, range(len(a)), a.take)
[4, 3, 1]

Für reguläre Python Listen:

>>> a = [1, 3, 2, 4, 5]
>>> heapq.nlargest(3, range(len(a)), a.__getitem__)
[4, 3, 1]

Wenn Sie Python 2 verwenden, verwenden Sie xrange anstelle von range.

Quelle: Heapq - Heap-Queue-Algorithmus

29
anishpatel

Wenn Sie mit einem mehrdimensionalen Array arbeiten, müssen Sie die Indizes reduzieren und auflösen:

def largest_indices(ary, n):
    """Returns the n largest indices from a numpy array."""
    flat = ary.flatten()
    indices = np.argpartition(flat, -n)[-n:]
    indices = indices[np.argsort(-flat[indices])]
    return np.unravel_index(indices, ary.shape)

Zum Beispiel:

>>> xs = np.sin(np.arange(9)).reshape((3, 3))
>>> xs
array([[ 0.        ,  0.84147098,  0.90929743],
       [ 0.14112001, -0.7568025 , -0.95892427],
       [-0.2794155 ,  0.6569866 ,  0.98935825]])
>>> largest_indices(xs, 3)
(array([2, 0, 0]), array([2, 2, 1]))
>>> xs[largest_indices(xs, 3)]
array([ 0.98935825,  0.90929743,  0.84147098])
27
danvk

Wenn Sie sich nicht für die Reihenfolge der K-ten größten Elemente interessieren, können Sie argpartition verwenden, was eine bessere Leistung bringen sollte als eine vollständige Sortierung durch argsort.

K = 4 # We want the indices of the four largest values
a = np.array([0, 8, 0, 4, 5, 8, 8, 0, 4, 2])
np.argpartition(a,-K)[-K:]
array([4, 1, 5, 6])

Credits gehen an diese Frage .

Ich habe ein paar Tests durchgeführt und es sieht so aus, als ob argpartitionargsort übertrifft, wenn die Größe des Arrays und der Wert von K zunehmen.

9
blue

Bei mehrdimensionalen Arrays können Sie das Schlüsselwort axis verwenden, um die Partitionierung entlang der erwarteten Achse anzuwenden.

# For a 2D array
indices = np.argpartition(arr, -N, axis=1)[:, -N:]

Und um die Gegenstände zu greifen:

x = arr.shape[0]
arr[np.repeat(np.arange(x), N), indices.ravel()].reshape(x, N)

Beachten Sie jedoch, dass dies kein sortiertes Ergebnis liefert. In diesem Fall können Sie np.argsort() entlang der vorgesehenen Achse verwenden:

indices = np.argsort(arr, axis=1)[:, -N:]

# Result
x = arr.shape[0]
arr[np.repeat(np.arange(x), N), indices.ravel()].reshape(x, N)

Hier ist ein Beispiel:

In [42]: a = np.random.randint(0, 20, (10, 10))

In [44]: a
Out[44]:
array([[ 7, 11, 12,  0,  2,  3,  4, 10,  6, 10],
       [16, 16,  4,  3, 18,  5, 10,  4, 14,  9],
       [ 2,  9, 15, 12, 18,  3, 13, 11,  5, 10],
       [14,  0,  9, 11,  1,  4,  9, 19, 18, 12],
       [ 0, 10,  5, 15,  9, 18,  5,  2, 16, 19],
       [14, 19,  3, 11, 13, 11, 13, 11,  1, 14],
       [ 7, 15, 18,  6,  5, 13,  1,  7,  9, 19],
       [11, 17, 11, 16, 14,  3, 16,  1, 12, 19],
       [ 2,  4, 14,  8,  6,  9, 14,  9,  1,  5],
       [ 1, 10, 15,  0,  1,  9, 18,  2,  2, 12]])

In [45]: np.argpartition(a, np.argmin(a, axis=0))[:, 1:] # 1 is because the first item is the minimum one.
Out[45]:
array([[4, 5, 6, 8, 0, 7, 9, 1, 2],
       [2, 7, 5, 9, 6, 8, 1, 0, 4],
       [5, 8, 1, 9, 7, 3, 6, 2, 4],
       [4, 5, 2, 6, 3, 9, 0, 8, 7],
       [7, 2, 6, 4, 1, 3, 8, 5, 9],
       [2, 3, 5, 7, 6, 4, 0, 9, 1],
       [4, 3, 0, 7, 8, 5, 1, 2, 9],
       [5, 2, 0, 8, 4, 6, 3, 1, 9],
       [0, 1, 9, 4, 3, 7, 5, 2, 6],
       [0, 4, 7, 8, 5, 1, 9, 2, 6]])

In [46]: np.argpartition(a, np.argmin(a, axis=0))[:, -3:]
Out[46]:
array([[9, 1, 2],
       [1, 0, 4],
       [6, 2, 4],
       [0, 8, 7],
       [8, 5, 9],
       [0, 9, 1],
       [1, 2, 9],
       [3, 1, 9],
       [5, 2, 6],
       [9, 2, 6]])

In [89]: a[np.repeat(np.arange(x), 3), ind.ravel()].reshape(x, 3)
Out[89]:
array([[10, 11, 12],
       [16, 16, 18],
       [13, 15, 18],
       [14, 18, 19],
       [16, 18, 19],
       [14, 14, 19],
       [15, 18, 19],
       [16, 17, 19],
       [ 9, 14, 14],
       [12, 15, 18]])
7
Kasrâmvd

Dies ist schneller als eine vollständige Sortierung, abhängig von der Größe Ihres ursprünglichen Arrays und der Größe Ihrer Auswahl:

>>> A = np.random.randint(0,10,10)
>>> A
array([5, 1, 5, 5, 2, 3, 2, 4, 1, 0])
>>> B = np.zeros(3, int)
>>> for i in xrange(3):
...     idx = np.argmax(A)
...     B[i]=idx; A[idx]=0 #something smaller than A.min()
...     
>>> B
array([0, 2, 3])

Natürlich müssen Sie dabei Ihr Original-Array manipulieren. Was Sie beheben können (falls erforderlich), indem Sie eine Kopie anfertigen oder die ursprünglichen Werte zurücksetzen. ... je nachdem, was für Ihren Anwendungsfall günstiger ist.

4
Paul

Methode _np.argpartition_ gibt nur die k größten Indizes zurück, führt eine lokale Sortierung durch und ist schneller als _np.argsort_ (führt eine vollständige Sortierung durch), wenn das Array ziemlich groß ist. Die zurückgegebenen Indizes sind jedoch NICHT in aufsteigender/absteigender Reihenfolge . Sagen wir mit einem Beispiel:

Enter image description here

Wir können sehen, dass _np.argpartition_ nicht das zurückgibt, was Sie wollen, wenn Sie streng aufsteigend nach Top-k-Indizes sortieren.

Abgesehen von der manuellen Sortierung nach np.argpartition besteht meine Lösung darin, PyTorch torch.topk zu verwenden, ein Tool für den Aufbau neuronaler Netzwerke, das NumPy-ähnliche APIs mit CPU- und GPU-Unterstützung bietet. Es ist so schnell wie NumPy mit MKL und bietet einen GPU-Boost, wenn Sie umfangreiche Matrix-/Vektorberechnungen benötigen.

Der strenge Code für Auf-/Abstiegs-Top-k-Indizes lautet:

Enter image description here

Beachten Sie, dass torch.topk einen Brennertensor akzeptiert und sowohl Top-k-Werte als auch Top-k-Indizes in Typ _torch.Tensor_ zurückgibt. Ähnlich wie bei np akzeptiert torch.topk auch ein Achsenargument, damit Sie mit mehrdimensionalen Arrays/Tensoren umgehen können.

3
futureer

Verwenden:

def max_indices(arr, k):
    '''
    Returns the indices of the k first largest elements of arr
    (in descending order in values)
    '''
    assert k <= arr.size, 'k should be smaller or equal to the array size'
    arr_ = arr.astype(float)  # make a copy of arr
    max_idxs = []
    for _ in range(k):
        max_element = np.max(arr_)
        if np.isinf(max_element):
            break
        else:
            idx = np.where(arr_ == max_element)
        max_idxs.append(idx)
        arr_[idx] = -np.inf
    return max_idxs

Es funktioniert auch mit 2D-Arrays. Zum Beispiel,

In [0]: A = np.array([[ 0.51845014,  0.72528114],
                     [ 0.88421561,  0.18798661],
                     [ 0.89832036,  0.19448609],
                     [ 0.89832036,  0.19448609]])
In [1]: max_indices(A, 8)
Out[1]:
    [(array([2, 3], dtype=int64), array([0, 0], dtype=int64)),
     (array([1], dtype=int64), array([0], dtype=int64)),
     (array([0], dtype=int64), array([1], dtype=int64)),
     (array([0], dtype=int64), array([0], dtype=int64)),
     (array([2, 3], dtype=int64), array([1, 1], dtype=int64)),
     (array([1], dtype=int64), array([1], dtype=int64))]

In [2]: A[max_indices(A, 8)[0]][0]
Out[2]: array([ 0.89832036])
2
AndyK

Verwenden:

from operator import itemgetter
from heapq import nlargest
result = nlargest(N, enumerate(your_list), itemgetter(1))

Nun würde die Liste resultN Tupel (index, value) enthalten, wobei value maximiert ist.

2
off99555

bottleneck hat eine teilweise Sortierfunktion, wenn der Aufwand für das Sortieren des gesamten Arrays, nur um die N größten Werte zu erhalten, zu groß ist.

Ich weiß nichts über dieses Modul; Ich habe gerade gegoogelt numpy partial sort.

2
Katriel

Das Folgende ist ein sehr einfacher Weg, um die maximalen Elemente und ihre Positionen zu sehen. Hier ist axis die Domäne; axis = 0 bedeutet spaltenweise maximale Anzahl und axis = 1 bedeutet zeilenweise maximale Anzahl für den 2D-Fall. Und für höhere Dimensionen kommt es auf Sie an.

M = np.random.random((3, 4))
print(M)
print(M.max(axis=1), M.argmax(axis=1))
1
liberal

Ich fand es am intuitivsten, np.unique zu verwenden.

Die Idee ist, dass die eindeutige Methode die Indizes der Eingabewerte zurückgibt. Aus dem maximalen eindeutigen Wert und den Angaben kann dann die Position der ursprünglichen Werte wiederhergestellt werden.

multi_max = [1,1,2,2,4,0,0,4]
uniques, idx = np.unique(multi_max, return_inverse=True)
print np.squeeze(np.argwhere(idx == np.argmax(uniques)))
>> [4 7]
0
phi

Ich denke, der effizienteste Weg ist die manuelle Iteration durch das Array und die Beibehaltung eines Min-Heaps in der Größe von k, wie andere Leute bereits erwähnt haben.

Und ich habe auch einen Brute-Force-Ansatz entwickelt:

top_k_index_list = [ ]
for i in range(k):
    top_k_index_list.append(np.argmax(my_array))
    my_array[top_k_index_list[-1]] = -float('inf')

Setzen Sie das größte Element auf einen großen negativen Wert, nachdem Sie den Index mit argmax ermittelt haben. Und dann gibt der nächste Aufruf von argmax das zweitgrößte Element zurück. Und Sie können den ursprünglichen Wert dieser Elemente protokollieren und sie wiederherstellen, wenn Sie möchten.

0
Zhenghao Zhao