时间戳

首页 > 解决方案 > 高效的稀疏矩阵列变化

python-3.x - 高效的稀疏矩阵列变化

问题描述

我正在实现一个高效的 PageRank 算法，所以我使用的是稀疏矩阵。我很接近，但有一个问题。我有一个矩阵，我希望每列的总和为一。这很容易实现，但是当我得到一个零列的矩阵时就会出现问题。

在这种情况下，我想将列中的每个元素设置为 1/(n-1) 其中 n 是矩阵的维度。我除以 n-1 而不是 n 因为我希望始终保持对角线为零。

我怎样才能有效地实现这一点？我天真的解决方案是只确定每列的总和，然后找到为零的列索引并用 1/(n-1) 值替换整个列，如下所示：

# naive approach (too slow!)
# M is my nxn sparse matrix where each column sums to one
col_sums = M.sum(axis=0)
for i in range(n):
   if col_sums[0,i] == 0:
      # set entire column to 1/(n-1)
      M[:, i] = 1/(n-1)
      # make sure diagonal is zeroed
      M[i,i] = 0

我的 M 矩阵非常非常大，这种方法根本无法扩展。我怎样才能有效地做到这一点？

标签： python-3.xalgorithmnumpyscipysparse-matrix

解决方案

如果不重新分配和复制基础数据结构，就无法添加新的非零值。如果您希望这些零列非常常见（> 25% 的数据），您应该以其他方式处理它们，或者您最好使用密集数组。

否则试试这个：

import scipy.sparse

M = scipy.sparse.rand(1000, 1000, density=0.001, format='csr')

nz_col_weights = scipy.sparse.csr_matrix(M.shape, dtype=M.dtype)
nz_col_weights[:, M.getnnz(axis=0) == 0] = 1 / (M.shape[0] - 1)
nz_col_weights.setdiag(0)

M += nz_col_weights

这只有两个分配操作

推荐阅读