select scipy 中稀疏矩阵每一行的随机非零列

Question

我正在尝试为大型稀疏 SciPy 矩阵的每一行有效地 select 随机非零列索引。我似乎无法找出一种矢量化的方法，所以我求助于一个非常慢的 Python 循环：

random_columns = np.zeros((sparse_matrix.shape[0]))
for i,row in enumerate(sparse_matrix):
    random_columns[i] = (np.random.choice(row.nonzero()[1]))

我的矩阵大约是 (4000000, 800) csr_matrix，几乎每一行都只有一个非零值，因此 Python 循环会降低性能。必须有更好的方法！

EDIT 通过直接访问 csr_matrix:

的基础数据，我可以使速度提高约 2 倍

random_columns[i] = row.indices[np.random.choice(len(row.data))]

Answer 1

您是否查看过此格式和其他稀疏格式的基础数据表示？

例如，对于小矩阵

In [257]: M = sparse.rand(10,10,.1,format='csr')

In [258]: M
Out[258]: 
<10x10 sparse matrix of type '<class 'numpy.float64'>'
    with 10 stored elements in Compressed Sparse Row format>

In [259]: M.data
Out[259]: 
array([ 0.86390256,  0.85244302,  0.88549326,  0.78737361,  0.99918561,
        0.89862529,  0.86842524,  0.25714778,  0.4174032 ,  0.33137501])

In [260]: M.indices
Out[260]: array([1, 5, 8, 8, 9, 0, 3, 9, 4, 5], dtype=int32)

In [261]: M.indptr
Out[261]: array([ 0,  1,  1,  3,  4,  4,  5,  5,  7,  8, 10], dtype=int32)

对于csr，索引有点模糊。或者更确切地说，每个非零值的列索引都存在于 M.indices 中，但需要一些计算来确定哪些属于哪一行。

对于其他格式，这种联系更为明显。

对于lil，我们有 2 个列表列表

In [262]: Ml=M.tolil()

In [263]: Ml.data
Out[263]: 
array([[0.863902562935336], [], [0.8524430195076207, 0.8854932609233054],
       [0.7873736126927198], [], [0.9991856090158101], [],
       [0.8986252926235274, 0.8684252408594123], [0.2571477751356357],
       [0.4174032029993796, 0.3313750148434619]], dtype=object)

In [264]: Ml.rows
Out[264]: array([[1], [], [5, 8], [8], [], [9], [], [0, 3], [9], [4, 5]], dtype=object)

In [265]: [np.random.choice(x) for x in Ml.rows if x]
# some rows might not have any nonzero
Out[265]: [1, 5, 8, 9, 3, 9, 5]

In [268]: [np.random.choice(x.nonzero()[1]) for x in M if len(x.nonzero()[1])]
Out[268]: [1, 5, 8, 9, 0, 9, 4]

你也可以对整个矩阵取nonzero

 In [274]: M.nonzero()
 Out[274]: 
 (array([0, 2, 2, 3, 5, 7, 7, 8, 9, 9], dtype=int32),
 array([1, 5, 8, 8, 9, 0, 3, 9, 4, 5], dtype=int32))

这些数组与使用 M.tocoo() 并查看 row 和 col 属性时得到的相同。理论上，您可以使用 groupby 获取列的子列表，并从中进行选择。但是你又一次有了列表或生成器和迭代。

我不知道这些表示中的任何一个是否更快。

矢量化问题可能存在一些限制。非零的数量（choices 的输入）将因行而异。有些行没有，其他行有 1 个或更多。任何时候遇到不同长度的数组或列表，都很难将操作向量化。如果你不能将这些值排列成一个普通的二维数组，你就不能用数组操作将它们作为一个整体来操作。

lil格式值得一看：

In [276]: timeit [np.random.choice(x.nonzero()[1]) for x in M if len(x.nonzero()[1])]
100 loops, best of 3: 4.24 ms per loop

In [289]: timeit [np.random.choice(row.indices) for row in M if len(row.indices)]
1000 loops, best of 3: 1.52 ms per loop
# 3x speedup using row.indices

In [277]: %%timeit
   .....: Ml=M.tolil()
   .....: [np.random.choice(x) for x in Ml.rows if x]
   .....: 
10000 loops, best of 3: 181 µs per loop

select scipy 中稀疏矩阵每一行的随机非零列

Efficiently select random non-zero column from each row of sparse matrix in scipy

python

numpy

scipy