时间戳

首页 > 解决方案 > 如何有效地将稀疏矩阵列添加到另一个稀疏矩阵中的每一列？

python - 如何有效地将稀疏矩阵列添加到另一个稀疏矩阵中的每一列？

问题描述

感谢您花时间看我的问题。

我正在尝试创建一个程序，该程序可以将值数组添加到稀疏矩阵中的每个“列”，如下所示：

A = [[1,1,0],
     [0,0,1],
     [1,0,1]]

B = [[1],
     [0],
     [1]]

A + B = [[2,2,1],
         [0,0,1],
         [2,1,2]]

以稀疏矩阵的坐标格式表示，如下所示：

A = [[0,0,1],
     [2,0,1],
     [0,1,1],
     [1,2,1],
     [2,2,1]]

B = [[0,0,1],
     [2,0,1]]

A + B = [[0,0,2],
         [2,0,2],
         [0,1,2],
         [2,1,1],
         [0,2,1],
         [1,2,1],
         [2,2,2]]

我正在处理由于其大小而必须以稀疏方式表示的大型矩阵。我需要能够将一列值添加到矩阵中的每一列，但使用专门处理稀疏三元组的算法。

我花了一整天的时间来解决这个问题，实际上是连续 10 个小时，我真的很震惊，我无法在任何地方找到一个好的答案。用乘法执行这个操作既简单又高效，但是 scipy 或 numpy 中似乎没有任何时间和空间有效的解决方案可以做到这一点，或者如果有，当我发现它会杀了我。我试图实施一个解决方案，但它最终效率低下。

从本质上讲，我的解决方案在技术上确实有效，但时间效率却很差，它遵循以下步骤：

  1. 检查 A 和 B 之间的行上的共享值，将相关的三元组值加在一起
  2. 添加来自 A 的唯一值
  3. 在矩阵的列中为 i 添加 B_row_i、x_i、B_value_i，检查我们没有从 A 三元组中添加逐字记录值。

至少，我认为这就是它的作用......我现在完全筋疲力尽了，我开始在编码时逐步退出。如果有人能提出快速解决方案，将不胜感激！

from scipy.sparse import coo_matrix 
from tqdm import tqdm

class SparseCoordinates:
    def __init__(self,coo_a,coo_b):

        self.shape = coo_a.shape

        self.coo_a_rows = coo_a.row
        self.coo_a_cols = coo_a.col
        self.coo_a_data = coo_a.data

        self.coo_b_rows = coo_b.row
        self.coo_b_cols = coo_b.col
        self.coo_b_data = coo_b.data

        self.coo_c_rows = []
        self.coo_c_cols = []
        self.coo_c_data = []

    def __check(self,a,b,c,lr,lc,lv):
        for i in range(len(lr)):
            if lr[i] == a and lc[i] == b and lv[i] == c:
                return True
        return False

    def __check_shared_rows(self):
        for i in tqdm(range(len(self.coo_a_rows))):
            for j in range(len(self.coo_b_rows)):
                if self.coo_a_rows[i] == self.coo_b_rows[j]:
                    self.coo_c_rows.append(self.coo_a_rows[i])
                    self.coo_c_cols.append(self.coo_a_cols[i])
                    self.coo_c_data.append(self.coo_a_data[i] + self.coo_b_data[j])
        
    def __add_unique_from_a(self):
        a_unique = set(self.coo_a_rows) - set(self.coo_b_rows)
        for i in tqdm(range(len(self.coo_a_rows))):
            if self.coo_a_rows[i] in a_unique:
                self.coo_c_rows.append(self.coo_a_rows[i])
                self.coo_c_cols.append(self.coo_a_cols[i])
                self.coo_c_data.append(self.coo_a_data[i])
    
    def __add_all_remaining_from_b(self):
        for i in tqdm(range(len(self.coo_b_rows))):
            for j in range(self.shape[1]):
                if not self.__check(self.coo_b_rows[i],j,self.coo_b_data[i],
                                    self.coo_a_rows,self.coo_a_cols,self.coo_a_data):
                    self.coo_c_rows.append(self.coo_b_rows[i])
                    self.coo_c_cols.append(j)
                    self.coo_c_data.append(self.coo_b_data[i])
    
    def add(self):
        self.__check_shared_rows()
        self.__add_unique_from_a()
        self.__add_all_remaining_from_b()
        return coo_matrix((self.coo_c_data,(self.coo_c_rows,self.coo_c_cols)),shape=self.shape)

标签： pythonnumpyscipylinear-algebrasparse-matrix

解决方案

对于numpy数组，A+B由于broadcasting. broadcasting在核心迭代级别实现，利用strides. scipy.sparse不执行broadcasting。如果B扩展为 (3,3) 矩阵以匹配A加法确实有效

In [76]: A = np.array([[1,1,0],
    ...:      [0,0,1],
    ...:      [1,0,1]])
    ...: 
    ...: B = np.array([[1],
    ...:      [0],
    ...:      [1]])
In [77]: B.shape
Out[77]: (3, 1)
In [78]: A+B
Out[78]: 
array([[2, 2, 1],
       [0, 0, 1],
       [2, 1, 2]])

疏：

In [79]: from scipy import sparse
In [81]: M=sparse.csr_matrix(A);N=sparse.csr_matrix(B)

矩阵乘法非常适合稀疏矩阵：

In [82]: M@N
Out[82]: 
<3x1 sparse matrix of type '<class 'numpy.int64'>'
    with 3 stored elements in Compressed Sparse Row format>

In [84]: N.T@M
Out[84]: 
<1x3 sparse matrix of type '<class 'numpy.int64'>'
    with 3 stored elements in Compressed Sparse Column format>

矩阵乘法用于行或列索引以及求和。

定义一个助手：

In [86]: O=sparse.csr_matrix([1,1,1])
In [87]: O
Out[87]: 
<1x3 sparse matrix of type '<class 'numpy.int64'>'
    with 3 stored elements in Compressed Sparse Row format>
In [88]: N@O
Out[88]: 
<3x3 sparse matrix of type '<class 'numpy.int64'>'
    with 6 stored elements in Compressed Sparse Row format>

在总和中使用它：

In [89]: M+N@O
Out[89]: 
<3x3 sparse matrix of type '<class 'numpy.int64'>'
    with 7 stored elements in Compressed Sparse Row format>
In [90]: _.A
Out[90]: 
array([[2, 2, 1],
       [0, 0, 1],
       [2, 1, 2]])

这个矩阵比M- 更少的 0 更稀疏。这减少了使用稀疏矩阵的好处。

coo_matrix格式用于创建矩阵和构建新矩阵，如sparse.bmat,sparse.hstack和sparse.vstack，但csr_matrix用于大多数数学。有时可以通过intptr数组迭代“行”来进行自定义数学运算。有各种各样的答案可以做到这一点。使用属性的数学coo通常不是一个好主意。

但是，由于coo在转换为 时会对重复项求和csr，因此我可能可以对M和的 coo 格式进行合理的求和N。

In [91]: Mo=M.tocoo(); No=N.tocoo()
In [95]: Oo=O.tocoo()
In [98]: rows = np.concatenate((Mo.row, Oo.row))
In [99]: cols = np.concatenate((Mo.col, Oo.col))
In [100]: data = np.concatenate((Mo.data, Oo.data))
In [101]: sparse.coo_matrix((data,(rows,cols)),M.shape)
Out[101]: 
<3x3 sparse matrix of type '<class 'numpy.int64'>'
    with 8 stored elements in COOrdinate format>
In [102]: _.A
Out[102]: 
array([[2, 2, 1],
       [0, 0, 1],
       [1, 0, 1]])

这里我加入了Mo和的属性Oo。我可以对 的属性做同样的事情No，但是因为我已经有了Oo，所以我认为这是值得的。我会把它留给你。

In [103]: Oo.row,Oo.col,Oo.data
Out[103]: 
(array([0, 0, 0], dtype=int32),
 array([0, 1, 2], dtype=int32),
 array([1, 1, 1]))
In [104]: No.row,No.col,No.data
Out[104]: (array([0, 2], dtype=int32), array([0, 0], dtype=int32), array([1, 1]))

我不知道这种coo方法是否值得努力。

推荐阅读