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

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

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 .

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

Jeszcze prostsze:

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

gdzie n jest liczbą maksymalnych wartości.

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

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

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.

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

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.

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 NIE są w porządku rosnącym / malejącym . Powiedzmy na przykład:

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:

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.

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.

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

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.}

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

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]

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.

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