在scipy中更新稀疏连接矩阵-Java 学习之路

我正在使用连接矩阵，它是图数据结构的表示 . NxM矩阵对应于具有M个顶点的N个边缘（它可能具有比顶点更多的边缘，这就是我使用scipy的csr_matrix的原因） . 边缘的“起始”点由“-1”表示，终点在连接矩阵中由“1”表示 . 所有其他值均为0，因此每行只有2个非零值 .

我需要集成一个“细分”方法，它将有效地更新连接矩阵 . 目前我正在将连接矩阵转换为密集矩阵，因此我可以添加新的行/列并更新旧的行/列 . 我正在转换为密集矩阵，因为我找不到找到用于更新旧边连接的列索引的解决方案（没有等效的scipy.where），并且csr表示不允许我通过索引更新值 .

from numpy import where, array, zeros, hstack, vstack
from scipy.sparse import coo_matrix, csr_matrix

def connectivity_matrix(edges):
    m    = len(edges)
    data = array([-1] * m + [1] * m)
    rows = array(list(range(m)) + list(range(m)))
    cols = array([edge[0] for edge in edges] + [edge[1] for edge in edges])
    C    = coo_matrix((data, (rows, cols))).asfptype()
    return C.tocsr()

def subdivide_edges(C, edge_indices):
    C = C.todense()
    num_e = C.shape[0] # number of edges
    num_v = C.shape[1] # number of vertices

    for edge in edge_indices:
        num_e += 1 # increment row (edge count)
        num_v += 1 # increment column (vertex count)
        _, start = where(C[edge] == -1.0)
        _, end   = where(C[edge] == 1.0)
        si    = start[0]
        ei    = end[0]
        # add row
        r, c = C.shape
        new_r = zeros((1, c))
        C = vstack([C, new_r])
        # add column
        r, c = C.shape
        new_c = zeros((r, 1))
        C = hstack([C, new_c])
        # edit edge start/end points
        C[edge, ei] = 0.0
        C[edge, num_v - 1] = 1.0
        # add new edge start/end points
        C[num_e - 1, ei] = 1.0
        C[num_e - 1, num_v - 1] = -1.0

    return csr_matrix(C)

edges = [(0, 1), (1, 2)] # edge connectivity
C = connectivity_matrix(edges)
C = subdivide_edges(C, [0, 1])
# new edge connectivity: [(0, 3), (1, 4), (3, 1), (4, 2)]

1 回答

稀疏矩阵确实有 nonzero 方法（ np.where 使用 np.nonzero ） . 但看看它的代码 - 它返回 coo row / cols数据 .

使用另一个问题留下的稀疏矩阵：

In [468]: M
Out[468]: 
<5x5 sparse matrix of type '<class 'numpy.float64'>'
    with 5 stored elements in COOrdinate format>
In [469]: Mc = M.tocsr()
In [470]: Mc.nonzero()
Out[470]: (array([0, 1, 2, 3, 4], dtype=int32), array([2, 0, 4, 3, 1], dtype=int32))
In [471]: Mc[1,:].nonzero()
Out[471]: (array([0]), array([0]))
In [472]: Mc[3,:].nonzero()
Out[472]: (array([0]), array([3]))

我转换为 csr 来做行索引 .

还有一个稀疏 vstack .

但是，与密集阵列相比，稀疏矩阵的迭代工作很慢 .

警惕像 C[edge] == -1.0 这样的浮动比较 . == 测试使用整数更好 .

将值从零更改为非零确实会引发警告，但确实有效：

In [473]: Mc[1,1] = 23
/usr/local/lib/python3.5/dist-packages/scipy/sparse/compressed.py:774: SparseEfficiencyWarning: Changing the sparsity structure of a csr_matrix is expensive. lil_matrix is more efficient.
  SparseEfficiencyWarning)
In [474]: (Mc[1,:]==23).nonzero()
Out[474]: (array([0]), array([1]))

将非零值更改为零并不会更改基础稀疏性（直到清除矩阵） . lil 格式更适合逐个元素更改 .

In [478]: Ml = M.tolil()
In [479]: Ml.nonzero()
Out[479]: (array([0, 1, 2, 3, 4], dtype=int32), array([2, 0, 4, 3, 1], dtype=int32))
In [480]: Ml[1,:].nonzero()
Out[480]: (array([0], dtype=int32), array([0], dtype=int32))
In [481]: Ml[1,2]=.5
In [482]: Ml[1,:].nonzero()
Out[482]: (array([0, 0], dtype=int32), array([0, 2], dtype=int32))
In [483]: (Ml[1,:]==.5).nonzero()
Out[483]: (array([0], dtype=int32), array([2], dtype=int32))

In [486]: sparse.vstack((Ml,Ml),format='lil')
Out[486]: 
<10x5 sparse matrix of type '<class 'numpy.float64'>'
    with 12 stored elements in LInked List format>

sparse.vstack 的工作原理是将输入转换为 coo ，并加入它们的属性（行，列，数据），并创建一个新矩阵 .

我怀疑你的代码将使用 lil 矩阵而不需要太多更改 . 但它可能会慢一些 . 稀疏在低密度矩阵上进行矩阵乘法等时获得最佳速度 . 当密集的等价物太大而不适合存储器时，它也有帮助 . 但是对于迭代工作和不断增长的矩阵来说，它很慢 .

回复于 2024-05-16T08:02:33+08:00

在scipy中更新稀疏连接矩阵

1 回答

相关问题