Scipy.sparse.csr_matrix: 如何获取前十个值和指数？
Scipy.sparse.csr_matrix: How to get top ten values and indices?
我有一个很大的 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的优点并没有得到充分发挥。它更像是一个蛮力解决方案。
在这种情况下，我看不出 csr 格式有什么优势。当然，所有非零值都收集在一个 .data 数组中，相应的列索引在 .indices 中。但它们是不同长度的块。这意味着它们不能并行处理或使用 numpy 数组步幅处理。
一种解决方案是将这些块填充到共同长度的块中。这就是 .toarray() 所做的。然后您可以使用 argsort(axis=1) or withargpartition` 找到最大值。
另一种方法是将它们分成行大小的块，然后处理每个块。这就是您使用 .getrow 所做的。另一种分解它们的方法是转换为 lil 格式，并处理 .data 和 .rows 数组的子列表。
第三种可能的选择是使用 ufunc reduceat 方法。这使您可以将 ufunc reduction 方法应用于数组的连续块。已经建立了 ufunc，例如 np.add，它们利用了这一点。 argsort 不是这样的函数。但是有一种方法可以从 Python 函数构建 ufunc，并在常规 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 格式是为高效乘法而开发的。
对于我当前的示例矩阵（为另一个 SO 稀疏问题创建）
<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
其他都是 1ms 或更多。
我建议专注于开发单行函数，例如：
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
然后看看 if 如何适合其中一种迭代方法。 tolil() 看起来最有前途。
我还没有解决如何收集这些结果的问题。它们应该是列表列表、10 列数组、另一个每行 10 个值的稀疏矩阵等？
sorting each row of a large sparse & saving top K values & column index - 几年前的类似问题，但没有得到回答。
- 最近寻求 argmax 行 csr 的问题。我讨论了一些相同的问题。
how to speed up loop in numpy? - 如何使用 np.frompyfunc 创建 ufunc 的示例。我不知道结果函数是否有.reduceat方法。
Increasing value of top k elements in sparse matrix - 获取 csr 的前 k 个元素（不是按行）。 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。所以这可能是这个问题的死胡同。
只是为了回答最初的问题（对于像我这样发现这个问题的人正在寻找 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()
需要遍历行并分别获取每一行的最高索引。但是这个循环可以被 jited（和并行化）以获得极快的功能。
@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)
我需要经常执行这个操作，这个函数对我来说足够快，在 1mil x 400k 稀疏矩阵上执行 <1s。
HTH.
我有一个很大的 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的优点并没有得到充分发挥。它更像是一个蛮力解决方案。
在这种情况下，我看不出 csr 格式有什么优势。当然，所有非零值都收集在一个 .data 数组中，相应的列索引在 .indices 中。但它们是不同长度的块。这意味着它们不能并行处理或使用 numpy 数组步幅处理。
一种解决方案是将这些块填充到共同长度的块中。这就是 .toarray() 所做的。然后您可以使用 argsort(axis=1) or withargpartition` 找到最大值。
另一种方法是将它们分成行大小的块，然后处理每个块。这就是您使用 .getrow 所做的。另一种分解它们的方法是转换为 lil 格式，并处理 .data 和 .rows 数组的子列表。
第三种可能的选择是使用 ufunc reduceat 方法。这使您可以将 ufunc reduction 方法应用于数组的连续块。已经建立了 ufunc，例如 np.add，它们利用了这一点。 argsort 不是这样的函数。但是有一种方法可以从 Python 函数构建 ufunc，并在常规 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 格式是为高效乘法而开发的。
对于我当前的示例矩阵（为另一个 SO 稀疏问题创建）
<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
其他都是 1ms 或更多。
我建议专注于开发单行函数，例如：
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
然后看看 if 如何适合其中一种迭代方法。 tolil() 看起来最有前途。
我还没有解决如何收集这些结果的问题。它们应该是列表列表、10 列数组、另一个每行 10 个值的稀疏矩阵等？
sorting each row of a large sparse & saving top K values & column index - 几年前的类似问题，但没有得到回答。
argmax 行 csr 的问题。我讨论了一些相同的问题。
how to speed up loop in numpy? - 如何使用 np.frompyfunc 创建 ufunc 的示例。我不知道结果函数是否有.reduceat方法。
Increasing value of top k elements in sparse matrix - 获取 csr 的前 k 个元素（不是按行）。 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。所以这可能是这个问题的死胡同。
只是为了回答最初的问题（对于像我这样发现这个问题的人正在寻找 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()
需要遍历行并分别获取每一行的最高索引。但是这个循环可以被 jited（和并行化）以获得极快的功能。
@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)
我需要经常执行这个操作，这个函数对我来说足够快，在 1mil x 400k 稀疏矩阵上执行 <1s。
HTH.