NumPyは、を介して配列の最大値のインデックスを取得する方法を提案しますnp.argmax
。
同様のことをしたいのですが、N
最大値のインデックスを返します。
たとえば、配列がある場合[1, 3, 2, 4, 5]
、、は要素に対応するfunction(array, n=3)
インデックスを返します。[4, 3, 1]
[5, 4, 3]
NumPyは、を介して配列の最大値のインデックスを取得する方法を提案しますnp.argmax
。
同様のことをしたいのですが、N
最大値のインデックスを返します。
たとえば、配列がある場合[1, 3, 2, 4, 5]
、、は要素に対応するfunction(array, n=3)
インデックスを返します。[4, 3, 1]
[5, 4, 3]
新しいNumPyバージョン(1.8以降)には、これを呼び出す関数がありますargpartition
。最大の4つの要素のインデックスを取得するには、次のようにします。
>>> 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])
>>> top4 = a[ind]
>>> top4
array([4, 9, 6, 9])
とは異なりargsort
、この関数は最悪の場合線形時間で実行されますが、評価の結果からわかるように、返されるインデックスは並べ替えられませんa[ind]
。それも必要な場合は、後で並べ替えます。
>>> ind[np.argsort(a[ind])]
array([1, 8, 5, 0])
この方法で上位k個の要素をソートされた順序で取得するには、O(n + k log k)時間がかかります。
私が思いついた最も簡単なものは次のとおりです。
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で何かをコーディングすることを検討する価値があるかもしれません。
さらにシンプル:
idx = (-arr).argsort()[:n]
ここで、nは最大値の数です。
使用する:
>>> 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
。
多次元配列を使用している場合は、インデックスをフラット化して解明する必要があります。
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 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])
クレジットはこの質問に行きます。
いくつかのテストを実行しましたが、配列のサイズとKの値が大きくなると、argpartition
パフォーマンスが向上するように見えます。argsort
多次元配列の場合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]])
スピードは私のニーズにとって重要だったので、私はこの質問に対する3つの答えをテストしました。
これらの3つの回答のコードは、私の特定のケースに応じて必要に応じて変更されました。
次に、各メソッドの速度を比較しました。
賢明なコーディング:
import numpy as np
import time
import random
import sys
from operator import itemgetter
from heapq import nlargest
''' Fake Data Setup '''
a1 = list(range(1000000))
random.shuffle(a1)
a1 = np.array(a1)
''' ################################################ '''
''' NPE's Answer Modified A Bit For My Case '''
t0 = time.time()
indices = np.flip(np.argsort(a1))[:5]
results = []
for index in indices:
results.append((index, a1[index]))
t1 = time.time()
print("NPE's Answer:")
print(results)
print(t1 - t0)
print()
''' Fred Foos Answer Modified A Bit For My Case'''
t0 = time.time()
indices = np.argpartition(a1, -6)[-5:]
results = []
for index in indices:
results.append((a1[index], index))
results.sort(reverse=True)
results = [(b, a) for a, b in results]
t1 = time.time()
print("Fred Foo's Answer:")
print(results)
print(t1 - t0)
print()
''' off99555's Answer - No Modification Needed For My Needs '''
t0 = time.time()
result = nlargest(5, enumerate(a1), itemgetter(1))
t1 = time.time()
print("off99555's Answer:")
print(result)
print(t1 - t0)
NPE's Answer:
[(631934, 999999), (788104, 999998), (413003, 999997), (536514, 999996), (81029, 999995)]
0.1349949836730957
Fred Foo's Answer:
[(631934, 999999), (788104, 999998), (413003, 999997), (536514, 999996), (81029, 999995)]
0.011161565780639648
off99555's Answer:
[(631934, 999999), (788104, 999998), (413003, 999997), (536514, 999996), (81029, 999995)]
0.439760684967041
メソッドnp.argpartition
は、k個の最大のインデックスのみを返し、ローカルソートを実行しnp.argsort
、配列が非常に大きい場合よりも高速です(完全ソートを実行します)。ただし、返されるインデックスは昇順/降順ではありません。例を挙げてみましょう:
厳密な昇順の上位kインデックスが必要な場合、必要なnp.argpartition
ものが返されないことがわかります。
np.argpartitionの後に手動で並べ替えを行う以外に、私の解決策は、torch.topk
ニューラルネットワーク構築用のツールであるPyTorchを使用して、CPUとGPUの両方をサポートするNumPyのようなAPIを提供することです。MKLを使用したNumPyと同じくらい高速で、大規模な行列/ベクトル計算が必要な場合はGPUブーストを提供します。
厳密な昇順/降順の上位kインデックスコードは次のようになります。
torch.topk
はトーチテンソルを受け入れ、タイプの上位k値と上位kインデックスの両方を返すことに注意してくださいtorch.Tensor
。npと同様に、torch.topkも軸引数を受け入れるため、多次元配列/テンソルを処理できます。
これは、元の配列のサイズと選択した配列のサイズによっては、完全な並べ替えよりも高速になります。
>>> 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])
もちろん、元のアレイを改ざんする必要があります。コピーを作成するか、元の値に戻すことで、(必要に応じて)修正できます。...ユースケースにとって安い方。
使用する:
from operator import itemgetter
from heapq import nlargest
result = nlargest(N, enumerate(your_list), itemgetter(1))
これで、リストには最大化されたN個のタプル(、)result
が含まれます。index
value
value
使用する:
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])
以下は、最大要素とその位置を確認するための非常に簡単な方法です。これaxis
がドメインです。axis
= 0は列ごとの最大数をaxis
意味し、=1は2Dの場合の行ごとの最大数を意味します。そして、より高い次元の場合、それはあなた次第です。
M = np.random.random((3, 4))
print(M)
print(M.max(axis=1), M.argmax(axis=1))
n番目の値が同点の場合にnを増やす、より複雑な方法を次に示します。
>>>> def get_top_n_plus_ties(arr,n):
>>>> sorted_args = np.argsort(-arr)
>>>> thresh = arr[sorted_args[n]]
>>>> n_ = np.sum(arr >= thresh)
>>>> return sorted_args[:n_]
>>>> get_top_n_plus_ties(np.array([2,9,8,3,0,2,8,3,1,9,5]),3)
array([1, 9, 2, 6])
を使用するのが最も直感的であることがわかりました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]
他の人が言っているように、最も時間効率の良い方法は、配列を手動で反復し、kサイズの最小ヒープを維持することだと思います。
また、ブルートフォースアプローチも考え出します。
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')
argmaxを使用してインデックスを取得した後、最大の要素を大きな負の値に設定します。そして、次にargmaxを呼び出すと、2番目に大きい要素が返されます。また、これらの要素の元の値をログに記録し、必要に応じて回復することができます。
このコードは、numpyの2D行列配列に対して機能します。
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
これにより、真偽のn_largest行列インデックスが生成され、行列配列からn_largest要素を抽出することもできます。
top_k << axis_lengthの場合、argsortよりも優れています。
import numpy as np
def get_sorted_top_k(array, top_k=1, axis=-1, reverse=False):
if reverse:
axis_length = array.shape[axis]
partition_index = np.take(np.argpartition(array, kth=-top_k, axis=axis),
range(axis_length - top_k, axis_length), axis)
else:
partition_index = np.take(np.argpartition(array, kth=top_k, axis=axis), range(0, top_k), axis)
top_scores = np.take_along_axis(array, partition_index, axis)
# resort partition
sorted_index = np.argsort(top_scores, axis=axis)
if reverse:
sorted_index = np.flip(sorted_index, axis=axis)
top_sorted_scores = np.take_along_axis(top_scores, sorted_index, axis)
top_sorted_indexes = np.take_along_axis(partition_index, sorted_index, axis)
return top_sorted_scores, top_sorted_indexes
if __name__ == "__main__":
import time
from sklearn.metrics.pairwise import cosine_similarity
x = np.random.rand(10, 128)
y = np.random.rand(1000000, 128)
z = cosine_similarity(x, y)
start_time = time.time()
sorted_index_1 = get_sorted_top_k(z, top_k=3, axis=1, reverse=True)[1]
print(time.time() - start_time)
辞書を使用するだけで、numpy配列の上位k個の値とインデックスを見つけることができます。たとえば、上位2つの最大値とインデックスを検索する場合
import numpy as np
nums = np.array([0.2, 0.3, 0.25, 0.15, 0.1])
def TopK(x, k):
a = dict([(i, j) for i, j in enumerate(x)])
sorted_a = dict(sorted(a.items(), key = lambda kv:kv[1], reverse=True))
indices = list(sorted_a.keys())[:k]
values = list(sorted_a.values())[:k]
return (indices, values)
print(f"Indices: {TopK(nums, k = 2)[0]}")
print(f"Values: {TopK(nums, k = 2)[1]}")
Indices: [1, 2]
Values: [0.3, 0.25]
argpartitionを使用したベクトル化された2D実装:
k = 3
probas = np.array([
[.6, .1, .15, .15],
[.1, .6, .15, .15],
[.3, .1, .6, 0],
])
k_indices = np.argpartition(-probas, k-1, axis=-1)[:, :k]
# adjust indices to apply in flat array
adjuster = np.arange(probas.shape[0]) * probas.shape[1]
adjuster = np.broadcast_to(adjuster[:, None], k_indices.shape)
k_indices_flat = k_indices + adjuster
k_values = probas.flatten()[k_indices_flat]
# k_indices:
# array([[0, 2, 3],
# [1, 2, 3],
# [2, 0, 1]])
# k_values:
# array([[0.6 , 0.15, 0.15],
# [0.6 , 0.15, 0.15],
# [0.6 , 0.3 , 0.1 ]])