Numpy предлагает способ получить индекс максимального значения массива через np.argmax.
Мне нужна аналогичная вещь, но возвращающая индексы максимальных значений N.
Например, если у меня есть массив [1, 3, 2, 4, 5], он function(array, n=3) вернет [4, 3, 1].
Спасибо:)
Самое простое, с чем я смог придумать:
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])
Это включает в себя полный вид массива. Интересно, если numpy предоставляет встроенный способ сделать частичную сортировку; пока я не смог его найти.
Если это решение оказывается слишком медленным (особенно для небольших n), может быть стоит посмотреть на что-то кодировать в Cython.
Новые версии NumPy (1,8 и выше) имеют функцию argpartition. Чтобы получить индексы четырех наибольших элементов, do
>>> 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])
В отличие от argsort, эта функция выполняется в линейном времени в худшем случае, но возвращаемые индексы не сортируются, как видно из результата оценки a[ind]. Если вам это нужно, сортируйте их позже:
>>> ind[np.argsort(a[ind])]
array([1, 8, 5, 0])
Чтобы получить элементы top-k в отсортированном порядке таким образом, берется время O (n + k log k).
EDIT: Изменено, чтобы включить улучшение Ashwini Chaudhary.
>>> import heapq
>>> import numpy
>>> a = numpy.array([1, 3, 2, 4, 5])
>>> heapq.nlargest(3, range(len(a)), a.take)
[4, 3, 1]
Для регулярных списков Python:
>>> a = [1, 3, 2, 4, 5]
>>> heapq.nlargest(3, range(len(a)), a.__getitem__)
[4, 3, 1]
Если вы используете Python 2, используйте xrange вместо range.
Еще проще:
idx = (-arr).argsort()[:n]
где n - число максимальных значений.
Если вы работаете с многомерным массивом, вам нужно сгладить и разгадать индексы:
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)
Например:
>>> 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])
Если вы не заботитесь о порядке K-ых крупнейших элементов, вы можете использовать argpartition, который должен выполнять лучше, чем полный сорт через argsort.
K = 4 # we want the indeces 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])
Кредиты на этот вопрос.
Я провел несколько тестов, и он выглядит loke argpartition превосходит argsort по мере увеличения размера массива и увеличения значения K.
Это будет быстрее, чем полный сортировка в зависимости от размера исходного массива и размера вашего выбора:
>>> 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])
Это, конечно, связано с изменением исходного массива. Который вы могли бы исправить (если необходимо), сделав копию или заменив исходные значения.... в зависимости от того, что дешевле для вашего случая использования.
bottleneck имеет функцию частичной сортировки, если расход сортировки всего массива только для получения наибольших значений N слишком велик.
Я ничего не знаю об этом модуле; Я просто googled numpy partial sort.
Для многомерных массивов вы можете использовать ключевое слово axis, чтобы применить разбиение вдоль ожидаемой оси.
# For a 2D array
indices = np.argpartition(arr, -N, axis=1)[:, -N:]
И для захвата элементов:
x = arr.shape[0]
arr[np.repeat(np.arange(x), N), indices.ravel()].reshape(x, N)
Но обратите внимание, что это не вернет отсортированный результат. В этом случае вы можете использовать np.argsort() вдоль предполагаемой оси:
indices = np.argsort(arr, axis=1)[:, -N:]
# result
x = arr.shape[0]
arr[np.repeat(np.arange(x), N), indices.ravel()].reshape(x, N)
Вот пример:
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]])
from operator import itemgetter
from heapq import nlargest
result = nlargest(N, enumerate(your_list), itemgetter(1))
Теперь список result будет содержать кортежи N (индекс, значение), где значение максимизировано
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
Работает также с 2D-массивами. Например.
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])
Я нашел наиболее интуитивно понятным использование np.unique.
Идея заключается в том, что уникальный метод возвращает индексы входных значений. Затем из максимального уникального значения и указателей можно восстановить восходящие позиции исходных значений.
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]
метод np.argpartition возвращает только k самых больших индексов, выполняет локальную сортировку, быстрее, чем np.argsort (выполняя полный сортировку), когда массив довольно велик. но возвращаемые индексы НЕ в порядке возрастания/убывания. Скажем, например:
мы можем видеть, что если вы хотите строгие индексы верхнего k верхнего индекса, np.argpartition не вернет то, что вы хотите.
Помимо выполнения сортировки вручную после np.argpartition, моим решением является использование PyTorch, torch.topk, инструмент для нейронной сети построение, предоставляющее многоподобные API с поддержкой как CPU, так и GPU. Это так же быстро, как numpy с MKL, и предлагает ускорение GPU, если вам нужен большой расчет матрицы/вектора.
Строгий код перехода с возрастанием/спуска вверх k будет:
Обратите внимание, что torch.topk принимает тензор факела и возвращает как верхние k значения, так и верхние k-индексы в типе torch.Tensor. Подобно np, torch.topk также принимает аргумент оси, так что вы можете обрабатывать многомерный массив/тензор.