csr_matrix:如何获取前十个值和索引？

Question

我有一个很大的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的优点。这更像是一种暴力解决方案。

Answer 1

为了回答最初的问题（对于像我这样发现这个问题的人来说是为了寻找复制的意大利面），这里有一个基于@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()

Answer 2

我不明白csr格式在这种情况下有什么好处。当然，所有非零值都收集在一个.data数组中，相应的列索引位于.indices。但它们是不同长度的块。这意味着它们不能并行处理，也不能以numpy数组的方式处理。

一种解决方案是将这些块填充到公共长度块中。这就是.toarray()所做的。然后可以使用argsort(axis=1) or withargpartition`找到最大值。

另一种方法是将它们分解成行大小的块，并对每个块进行处理。这就是你用.getrow做的。另一种分解它们的方法是转换成lil格式，并处理.data和.rows数组的子列表。

第三种可能的方法是使用ufuncreduceat方法。这允许您将ufuncreduction方法应用于数组的序列块。有一些像ufunc这样的np.add已经建立起来，它们利用了这一点。argsort不是这样的函数。但是，有一种方法可以从Python函数构造一个ufunc，并且比常规Python迭代获得一定的速度。[我需要查找一个最近的SO问题来说明这一点。]

我将用一个更简单的函数sum over rows来演示其中的一些内容。

如果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个值的稀疏矩阵等吗。？

---

sorting each row of a large sparse & saving top K values & column index-几年前的类似问题，但没有答案。

Argmax of each row or column in scipy sparse matrix-为csr行查找argmax的最新问题。我讨论了一些同样的问题。

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

速度真不错。但我想不出一种编写二进制函数（带两个参数）的方法，它可以通过归约实现argsort。所以这可能是这个问题的死角。