Jak uzyskać indeksy N maksymalnych wartości w tablicy NumPy?

482

NumPy proponuje sposób uzyskania indeksu maksymalnej wartości tablicy przez np.argmax.

Chciałbym podobną rzecz, ale zwracanie indeksów Nwartości maksymalnych.

Na przykład, jeśli mam tablicę [1, 3, 2, 4, 5], function(array, n=3)zwróciłby indeksy [4, 3, 1]odpowiadające elementom [5, 4, 3].

Alexis Métaireau
źródło
4
Twoje pytanie nie jest naprawdę dobrze zdefiniowane. Na przykład, jakie byłyby (oczekiwane) wskaźniki array([5, 1, 5, 5, 2, 3, 2, 4, 1, 5]), odrobina n= 3? Który z wszystkich alternatyw, jak [0, 2, 3], [0, 2, 9], ...byłaby prawidłowa? Proszę opracować więcej na temat konkretnych wymagań. Dzięki
zjedz
@eat, tak naprawdę nie dbam o to, który z nich ma zostać zwrócony w tym konkretnym przypadku. Nawet jeśli zwrócenie pierwszego napotkanego wydaje się logiczne, nie jest to dla mnie wymogiem.
Alexis Métaireau
argsortmoże być realną alternatywą, jeśli nie przejmujesz się kolejnością zwracanych nieczystości. Zobacz moją odpowiedź poniżej.
niebieski

Odpowiedzi:

347

Najprostszy, jaki udało mi się wymyślić, to:

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])

Wymaga to pełnego rodzaju tablicy. Zastanawiam się, czy numpyzapewnia wbudowany sposób na częściowe sortowanie; jak dotąd nie udało mi się go znaleźć.

Jeśli to rozwiązanie okaże się zbyt wolne (szczególnie w przypadku małych n), warto zastanowić się nad kodowaniem czegoś w Cython .

NPE
źródło
1
Czy wiersz 3 może być napisany równorzędnie jak arr.argsort()[-1:-4:-1]? Próbowałem tego w tłumaczu i daje ten sam wynik, ale zastanawiam się, czy nie jest to zepsute przez jakiś przykład.
abroekhof
44
@abroekhof Tak, to powinno być równoważne dla dowolnej listy lub tablicy. Alternatywnie można to zrobić bez odwrócenia za pomocą np.argsort(-arr)[:3], co uważam za bardziej czytelne i do rzeczy.
askewchan
6
co oznacza [:: - 1]? @NPE
1a1a11a 17.10.16
@ 1a1a11a oznacza odwrócenie tablicy (dosłownie, bierze kopię tablicy z nieograniczonej wartości minimalnej do nieograniczonej wartości maksymalnej w odwrotnej kolejności)
FizBack
15
arr.argsort()[::-1][:n]jest lepszy, ponieważ zwraca pustą n=0zamiast pełnej tablicy
abora
599

Nowsze wersje NumPy (1.8 i nowsze) mają funkcję argpartitiondo tego wywołaną . Aby uzyskać indeksy czterech największych elementów, wykonaj

>>> 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])

W przeciwieństwie do argsorttej funkcji, w najgorszym przypadku, działa ona w czasie liniowym, ale zwrócone wskaźniki nie są sortowane, jak widać z wyniku oceny a[ind]. Jeśli też tego potrzebujesz, posortuj je później:

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

Uzyskanie w ten sposób elementów top- k w uporządkowanej kolejności zajmuje czas O ( n + k log k ).

Fred Foo
źródło
27
@varela argpartitiondziała w czasie liniowym, O (n), przy użyciu algorytmu introselect . Kolejne sortowanie obsługuje tylko k elementów, więc działa w O (k log k).
Fred Foo
2
Jeśli ktoś zastanawia się, jak dokładnie działa np.argpartitionjego algorytm siostrzany, np.partitionbardziej szczegółowe wyjaśnienie znajduje się w powiązanym pytaniu: stackoverflow.com/questions/10337533/…
Ramon Martinez
7
@FredFoo: dlaczego użyłeś -4? zrobiłeś to, żeby zacząć od tyłu? (skoro k bycie dodatnim lub ujemnym działa dla mnie tak samo! najpierw drukuje tylko najmniejsze liczby!
Rika,
2
Użyj @LKT, a=np.array([9, 4, 4, 3, 3, 9, 0, 4, 6, 0])ponieważ normalne listy python nie obsługują indeksowania według list, w przeciwieństwie donp.array
Marawan Okasha
2
@Umangsinghal np.argpartitionprzyjmuje opcjonalny axisargument. Aby znaleźć indeksy najwyższych n wartości dla każdego wiersza:np.argpartition(a, -n, axis=1)[-n:]
Ralph
48

Jeszcze prostsze:

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

gdzie n jest liczbą maksymalnych wartości.

Ketan
źródło
7
Czy można to zrobić dla tablicy 2d? Jeśli nie, to może wiesz jak?
Andrew Hundt,
2
@AndrewHundt: po prostu użyj (-arr) .argsort (oś = -1) [:,: n]
MiniQuark
2
podobnie byłoby arr[arr.argsort()[-n:]]zamiast negować tablicę, po prostu weź kawałek ostatnich n elementów
loganjones16
35

Posługiwać się:

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

W przypadku zwykłych list w języku Python:

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

Jeśli używasz Python 2, użyj xrangezamiast range.

Źródło: heapq - algorytm kolejki sterty

anishpatel
źródło
2
Nie ma potrzeby pętli w ogóle tutaj: heapq.nlargest(3, xrange(len(a)), a.take). Do list w języku Python możemy użyć .__getitem__zamiast .take.
Ashwini Chaudhary
Dla n-wymiarowej macierzy A, ogólnie: heapq.nlargest(3, range(len(A.ravel())), A.ravel().take). (Mam nadzieję, że działa to tylko w widokach, zobacz także ( ravel vs flatten] ( stackoverflow.com/a/28930580/603003 )).
ComFreek
31

Jeśli akurat pracujesz z tablicą wielowymiarową, musisz spłaszczyć i rozwikłać indeksy:

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)

Na przykład:

>>> 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])
Danvk
źródło
9

Jeśli nie zależy ci na kolejności K-tych największych elementów, których możesz użyć argpartition, które powinny działać lepiej niż pełne sortowanie 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])

Kredyty trafiają na to pytanie .

Przeprowadziłem kilka testów i wygląda to na argpartitionlepsze niż argsortrozmiar tablicy i wartość K wzrostu.

niebieski
źródło
7

W przypadku tablic wielowymiarowych można użyć axissłowa kluczowego, aby zastosować partycjonowanie wzdłuż oczekiwanej osi.

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

I do chwytania przedmiotów:

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

Pamiętaj jednak, że nie zwróci to posortowanego wyniku. W takim przypadku możesz użyć np.argsort()wzdłuż zamierzonej osi:

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

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

Oto przykład:

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]])
Kasramvd
źródło
Myślę, że możesz uprościć indeksowanie tutaj, używając np.take_along_axis(co prawdopodobnie nie istniało, kiedy odpowiedziałeś na to pytanie)
Eric
4

Będzie to szybsze niż pełne sortowanie, w zależności od rozmiaru oryginalnej tablicy i rozmiaru zaznaczenia:

>>> 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])

Polega to oczywiście na manipulowaniu oryginalną tablicą. Które można naprawić (w razie potrzeby), wykonując kopię lub zastępując oryginalne wartości. ... w zależności od tego, który wariant jest tańszy w twoim przypadku użycia.

Paweł
źródło
FWIW, twoje rozwiązanie nie zapewni jednoznacznego rozwiązania we wszystkich sytuacjach. OP powinien opisać sposób postępowania w tych jednoznacznych przypadkach. Dzięki
zjedz
@eat Pytanie OP jest trochę niejednoznaczne. Wdrożenie nie jest jednak tak naprawdę otwarte na interpretację. :) OP powinien po prostu odwoływać się do definicji np.argmax docs.scipy.org/doc/numpy/reference/generated/numpy.argmax.html, aby upewnić się, że to konkretne rozwiązanie spełnia wymagania. Możliwe jest, że każde rozwiązanie spełniające podane wymaganie PO jest dopuszczalne.
Paul
Cóż, można również uznać wdrożenie argmax(.)za jednoznaczne. (IMHO stara się zastosować pewną logikę zwarć, ale niestety nie zapewnia ogólnie akceptowalnego zachowania). Dzięki
zjedz
3

Metoda np.argpartitionzwraca tylko k największych indeksów, wykonuje sortowanie lokalne i jest szybsza niż np.argsort(przeprowadzanie pełnego sortowania), gdy tablica jest dość duża. Ale zwrócone indeksy NIEw porządku rosnącym / malejącym . Powiedzmy na przykład:

Wpisz opis zdjęcia tutaj

Widzimy, że jeśli chcesz ścisłego porządku rosnących indeksów k, np.argpartitionnie zwróci tego, co chcesz.

Oprócz ręcznego sortowania po np.argpartition, moim rozwiązaniem jest użycie PyTorch, torch.topknarzędzia do budowy sieci neuronowych, zapewniającego interfejsy API NumPy z obsługą zarówno CPU, jak i GPU. Jest tak szybki jak NumPy z MKL i oferuje przyspieszenie GPU, jeśli potrzebujesz dużych obliczeń macierzy / wektorów.

Kod ścisłych indeksów k wzlotów / wzlotów będzie:

Wpisz opis zdjęcia tutaj

Zauważ, że torch.topkakceptuje tensor palnika i zwraca zarówno górne wartości k, jak i górne wskaźniki k typu torch.Tensor. Podobnie z np. Torch.topk akceptuje również argument osi, dzięki czemu można obsługiwać tablice / tensory wielowymiarowe.

przyszły
źródło
2

Posługiwać się:

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

Teraz resultlista będzie zawierać N krotek ( index, value), gdzie valuejest zmaksymalizowane.

off99555
źródło
2

Posługiwać się:

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

Działa również z tablicami 2D. Na przykład,

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])
X Æ A-12
źródło
Działa dobrze, ale daje więcej wyników, jeśli masz zduplikowane (maksymalne) wartości w tablicy A. Spodziewałbym się dokładnie k wyników, ale w przypadku zduplikowanych wartości otrzymasz więcej niż k wyników.
Guido
Lekko zmodyfikowałem kod. Lista zwracanych wskaźników ma długość równą dokładnie k. Jeśli masz duplikaty, są one zgrupowane w jedną krotkę.
X Æ A-12
1

bottleneck ma funkcję częściowego sortowania, jeśli koszt sortowania całej tablicy tylko w celu uzyskania N największych wartości jest zbyt duży.

Nic nie wiem o tym module; Właśnie googlowałem numpy partial sort.

Katriel
źródło
Nie mam funkcji częściowego sortowania w wąskim gardle, jest funkcja partycji, ale to nie sortuje
nbecker
1

Poniżej przedstawiono bardzo łatwy sposób na sprawdzenie maksymalnej liczby elementów i ich pozycji. Oto axisdomena; axis= 0 oznacza maksymalną liczbę w kolumnie, a axis= 1 oznacza maksymalną liczbę w rzędzie dla przypadku 2D. A dla wyższych wymiarów to zależy od ciebie.

M = np.random.random((3, 4))
print(M)
print(M.max(axis=1), M.argmax(axis=1))
liberał
źródło
Użyłem tego linku jakevdp.github.io/PythonDataScienceHandbook/...
liberalny
0

Uznałem, że jest najbardziej intuicyjny w użyciu np.unique.

Chodzi o to, że unikalna metoda zwraca wskaźniki wartości wejściowych. Następnie z maksymalnej unikalnej wartości i wskazań można odtworzyć pozycję oryginalnych wartości.

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]
phi
źródło
0

Myślę, że najbardziej efektywnym sposobem na oszczędność czasu jest ręczne iterowanie tablicy i utrzymywanie stosu min wielkości K, jak wspomnieli inni ludzie.

Wymyślam też podejście brutalnej siły:

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')

Ustaw największy element na dużą wartość ujemną po użyciu argmax do uzyskania jego indeksu. A następnie następne wywołanie argmax zwróci drugi co do wielkości element. I możesz zapisać oryginalną wartość tych elementów i odzyskać je, jeśli chcesz.

Zhenghao Zhao
źródło
0

Ten kod działa dla tablicy macierzy numpy:

mat = np.array([[1, 3], [2, 5]]) # numpy matrix

n = 2  # n
n_largest_mat = np.sort(mat, axis=None)[-n:] # n_largest 
tf_n_largest = np.zeros((2,2), dtype=bool) # all false matrix
for x in n_largest_mat: 
  tf_n_largest = (tf_n_largest) | (mat == x) # true-false  

n_largest_elems = mat[tf_n_largest] # true-false indexing 

Powoduje to wygenerowanie prawdziwie fałszywego największego indeksowania macierzy, które działa również w celu wyodrębnienia najliczniejszych elementów z macierzy macierzy

Yi Xiang Chong
źródło