Scipy.sparse.csr_matrix: как получить первые десять значений и индексов?
У меня большой csr_matrix и меня интересуют первые десять значений и их индексы в каждой строке. Но я не нашел достойного способа манипулировать матрицей.
Вот мое текущее решение, и основная идея состоит в том, чтобы обрабатывать их построчно:
row = csr_matrix.getrow(row_number).toarray()[0].ravel()
top_ten_indicies = row.argsort()[-10:]
top_ten_values = row[row.argsort()[-10:]]
Делая это, преимущества csr_matrix не используется полностью Это больше похоже на решение грубой силы.
2 ответа
Я не вижу, в чем преимущества csr Формат в этом случае. Конечно, все ненулевые значения собраны в одном .data массив, с соответствующими индексами столбцов в .indices, Но они в блоках разной длины. А это значит, что они не могут быть обработаны параллельно или с numpy шаг массива.
Одним из решений является объединение этих блоков в блоки общей длины. Это то что .toarray() делает. Тогда вы можете найти максимальные значения с argsort(axis=1) or with argpartition`.
Другой - разбить их на блоки размером с строку и обработать каждый из них. Это то, что вы делаете с .getrow, Другой способ разбить их - конвертировать в lil форматировать и обрабатывать списки .data а также .rows массивы.
Возможным третьим вариантом является использование ufuncreduceat метод. Это позволяет вам применять ufuncreduction методы последовательных блоков массива. Там установлены ufunc лайк np.add что воспользоваться этим. argsort это не такая функция. Но есть способ построения ufunc из функции Python, и получить некоторую скромную скорость по сравнению с обычной итерацией Python. [Мне нужно посмотреть недавний вопрос SO, который иллюстрирует это.]
Я проиллюстрирую это с помощью более простой функции - сумма по строкам.
Если A2 матрица csr
A2.sum(axis=1) # the fastest compile csr method
A2.A.sum(axis=1) # same, but with a dense intermediary
[np.sum(l.data) for l in A2] # iterate over the rows of A2
[np.sum(A2.getrow(i).data) for i in range(A2.shape[0])] # iterate with index
[np.sum(l) for l in A2.tolil().data] # sum the sublists of lil format
np.add.reduceat(A2.data, A2.indptr[:-1]) # with reduceat
A2.sum(axis=1) реализован в виде матричного умножения. Это не относится к проблеме сортировки, но все же интересный способ взглянуть на проблему суммирования. Помните csr Формат был разработан для эффективного умножения.
Для моей текущей выборки матрицы (созданной для другого ТАК разреженного вопроса)
<8x47752 sparse matrix of type '<class 'numpy.float32'>'
with 32 stored elements in Compressed Sparse Row format>
некоторые сравнительные времена
In [694]: timeit np.add.reduceat(A2.data, A2.indptr[:-1])
100000 loops, best of 3: 7.41 µs per loop
In [695]: timeit A2.sum(axis=1)
10000 loops, best of 3: 71.6 µs per loop
In [696]: timeit [np.sum(l) for l in A2.tolil().data]
1000 loops, best of 3: 280 µs per loop
Все остальное составляет 1 мс или более.
Я предлагаю сосредоточиться на разработке вашей однорядной функции, что-то вроде:
def max_n(row_data, row_indices, n):
i = row_data.argsort()[-n:]
# i = row_data.argpartition(-n)[-n:]
top_values = row_data[i]
top_indices = row_indices[i] # do the sparse indices matter?
return top_values, top_indices, i
Тогда посмотрите, как, если вписывается в один из этих методов итерации. tolil() выглядит наиболее перспективным.
Я не обращался к вопросу о том, как собрать эти результаты. Должны ли они быть списками списков, массивом с 10 столбцами, другой разреженной матрицей с 10 значениями в строке и т. Д.?
сортировка каждой строки большого разреженного и сохранение верхних значений K и индекса столбца - аналогичный вопрос несколько лет назад, но без ответа.
Argmax каждой строки или столбца в скудной разреженной матрице - недавний поиск вопроса argmax для рядов csr, Я обсуждаю некоторые из тех же вопросов.
Как ускорить цикл в NumPy? - пример того, как использовать np.frompyfunc создать ufunc, Я не знаю, имеет ли результирующая функция .reduceat метод.
Увеличение значения верхних k элементов в разреженной матрице - получить верхние k элементов csr (не по строке). Чехол для argpartition,
Суммирование строк осуществляется с помощью np.frompyfunc:
In [741]: def foo(a,b):
return a+b
In [742]: vfoo=np.frompyfunc(foo,2,1)
In [743]: timeit vfoo.reduceat(A2.data,A2.indptr[:-1],dtype=object).astype(float)
10000 loops, best of 3: 26.2 µs per loop
Это респектабельная скорость. Но я не могу придумать, как написать двоичную функцию (принимает 2 аргумента), которая бы argsort через сокращение. Так что это, вероятно, deadend для этой проблемы.
Просто чтобы ответить на первоначальный вопрос (для таких людей, как я, которые нашли этот вопрос в поисках copy-pasta), вот решение с использованием многопроцессорной обработки, основанное на предложении @hpaulj о преобразовании в lil_matrixи итерации по строкам
from multiprocessing import Pool
def _top_k(args):
"""
Helper function to process a single row of top_k
"""
data, row = args
data, row = zip(*sorted(zip(data, row), reverse=True)[:k])
return data, row
def top_k(m, k):
"""
Keep only the top k elements of each row in a csr_matrix
"""
ml = m.tolil()
with Pool() as p:
ms = p.map(_top_k, zip(ml.data, ml.rows))
ml.data, ml.rows = zip(*ms)
return ml.tocsr()
Потребовалось бы перебрать строки и получить верхние индексы для каждой строки отдельно. Но этот цикл можно джитить (и распараллеливать) для получения чрезвычайно быстрой функции.
@nb.njit(cache=True)
def row_topk_csr(data, indices, indptr, K):
m = indptr.shape[0] - 1
max_indices = np.zeros((m, K), dtype=indices.dtype)
max_values = np.zeros((m, K), dtype=data.dtype)
for i in nb.prange(m):
top_inds = np.argsort(data[indptr[i] : indptr[i + 1]])[::-1][:K]
max_indices[i] = indices[indptr[i] : indptr[i + 1]][top_inds]
max_values[i] = data[indptr[i] : indptr[i + 1]][top_inds]
return max_indices, max_values
Назовите это так:
top_pred_indices, _ = row_topk_csr(csr_mat.data, csr_mat.indices, csr_mat.indptr, K)
Мне нужно часто выполнять эту операцию, и эта функция для меня достаточно быстрая, выполняется за <1 с на разреженной матрице размером 1 мил x 400 тыс.
HTH.