稀疏矩阵行中的连续元素

Question

我正在处理以 COO 格式存储的稀疏矩阵。获取每行连续元素数的最快方法是什么。

例如考虑以下矩阵：

a = [[0,1,2,0],[1,0,0,2],[0,0,0,0],[1,0,1,0]]

它的 COO 代表将是

  (0, 1)    1
  (0, 2)    2
  (1, 0)    1
  (1, 3)    2
  (3, 0)    1
  (3, 2)    1

我需要的结果是 [1,2,0,2]。第一行包含两个位于附近的非零元素。因此它是一组或一组。在第二行我们有两个非零元素，但它们不在附近，因此我们可以说它形成了两个群。第三行没有非零，因此没有组。第四行再次有两个非零但被零隔开，因此我们认为是两组。这就像每行的簇数。遍历行是一种选择，但前提是没有更快的解决方案。在这方面的任何帮助表示赞赏。

另一个简单示例：考虑以下行：

[1,2,3,0,0,0,2,0,0,8,7,6,0,0]

上面的行应该 return [3] 因为有三组非零被零分隔。

Answer 1

将其转换为密集数组，并逐行应用您的逻辑。

你想要每行的组数
定义组时零计数
数组的行迭代速度更快

在 coo 格式中，您的矩阵如下所示：

In [623]: M=sparse.coo_matrix(a)
In [624]: M.data
Out[624]: array([1, 2, 1, 2, 1, 1])
In [625]: M.row
Out[625]: array([0, 0, 1, 1, 3, 3], dtype=int32)
In [626]: M.col
Out[626]: array([1, 2, 0, 3, 0, 2], dtype=int32)

这种格式没有实现行索引； csr 和 lil 做

In [627]: M.tolil().data
Out[627]: array([[1, 2], [1, 2], [], [1, 1]], dtype=object)
In [628]: M.tolil().rows
Out[628]: array([[1, 2], [0, 3], [], [0, 2]], dtype=object)

因此，第一行的稀疏信息是一个非零数据值列表 [1,2]，以及它们的列号列表 [1,2]。将其与密集数组的行进行比较，[0, 1, 2, 0]。哪个更容易分析？

您的第一个任务是编写一个分析一行的函数。我还没有充分研究你的逻辑来说明密集形式是否比稀疏形式更好。使用 M.A[0,:].nonzero().

很容易从密集形式中获取列信息

在你的最后一个例子中，我可以获得非零索引：

In [631]: np.nonzero([1,2,3,0,0,0,2,0,0,8,7,6,0,0])
Out[631]: (array([ 0,  1,  2,  6,  9, 10, 11], dtype=int32),)
In [632]: idx=np.nonzero([1,2,3,0,0,0,2,0,0,8,7,6,0,0])[0]
In [633]: idx
Out[633]: array([ 0,  1,  2,  6,  9, 10, 11], dtype=int32)
In [634]: np.diff(idx)
Out[634]: array([1, 1, 4, 3, 1, 1], dtype=int32)

我们或许能够从 diff 个值 >1 的数量中得到所需的计数，但我必须查看更多示例来定义详细信息。

将分析扩展到多行取决于首先彻底理解单行情况。

Answer 2

在 @hpaulj 的评论的帮助下，我想出了以下代码片段：

    M = m.tolil()
r = []  
for i in range(M.shape[0]):
   sumx=0
   idx= M.rows[i]
   if (len(idx) > 2):
       tempidx = np.diff(idx)
       if (1 in tempidx):
           temp = filter(lambda a: a != 1, tempidx)
           sumx=1
       counts = len(temp)
       r.append(counts+sumx)
   elif (len(idx) == 2):
       tempidx = np.diff(idx)
       if(tempidx[0]==1):
           counts = 1
           r.append(counts)
       else:
           counts = 2
           r.append(counts)
   elif (len(idx) == 1):
       counts = 1
       r.append(counts) 
   else:
       counts = 0
       r.append(counts)
tempcluster = np.sum(r)/float(M.shape[0])
cluster.append(tempcluster)

稀疏矩阵行中的连续元素

Consecutive elements in a Sparse matrix row

python

matrix

scipy

sparse-matrix

python-2.7