从 scipy 稀疏矩阵中寻找 N 个随机零元素

Question

我有一个很大的稀疏矩阵，在scipy lil_matrix格式中大小是281903x281903，它是一个邻接矩阵 https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html

我需要一种可靠的方法来获取 N 个为零的索引。我不能只绘制所有零索引然后选择随机索引，因为这会使我的计算机运行内存不足。有没有一种方法可以识别 N 个随机索引而不必遍历整个数据结构？

我目前通过以下方式获得 10% 的非零索引（Y 是我的稀疏矩阵）：

percent = 0.1

oneIdx = Y.nonzero()
numberOfOnes = len(oneIdx[0])
maskLength = int(math.floor(numberOfOnes * percent))
idxOne = np.array(random.sample(range(0,numberOfOnes), maskLength))

maskOne = tuple(np.asarray(oneIdx)[:,idxOne])

我正在寻找获得与非零掩码长度相同但带有零的掩码的方法...

Answer 1

这是一种基于拒绝抽样的方法。根据您示例中的数字，随机选择的索引很可能为零，因此这将是一种相对有效的方法。

from scipy import sparse

dims = (281903, 281903)

mat = sparse.lil_matrix(dims, dtype=np.int)

for _ in range(1000):
    x, y = np.random.randint(0, dims[0], 2)
    mat[x, y] = 1


def sample_zero_forever(mat):
    nonzero_or_sampled = set(zip(*mat.nonzero()))
    while True:
        t = tuple(np.random.randint(0, mat.shape[0], 2))
        if t not in nonzero_or_sampled:
            yield t
            nonzero_or_sampled.add(t)


def sample_zero_n(mat, n=100):
    itr = sample_zero_forever(mat)
    return [next(itr) for _ in range(n)]

从 scipy 稀疏矩阵中寻找 N 个随机零元素

Finding N random zero elements from a scipy sparse matrix

python

numpy

scipy

sparse-matrix