logo标签列表

从元组列表的列表中构建稀疏矩阵

pythonconstructorscipysparse-matrix
13

我有一个Python列表，其中包含稀疏矩阵的行信息。每一行表示为(column, value)元组的列表。把它叫做alist：

alist = [[(1,10), (3,-3)],
         [(2,12)]]

我该如何高效地从这个列表的列表中构建一个scipy稀疏矩阵，生成类似于以下矩阵的结果：

0  10   0  -3
0   0  12   0
明显的方法是创建一个 scipy.sparse.lil_matrix，它在内部具有这种“列表的列表”结构。但是从scipy.sparse.lil_matrix — SciPy v0.19.0 Reference Guide中我只看到了三种构造方法：
  • 从密集数组开始
  • 从另一个稀疏数组开始
  • 仅构造一个空数组
因此，唯一的方法是用其他稀疏矩阵表示解决这个问题，或者从密集数组开始，两者都不解决最初的问题，并且两者似乎比对于这些数据本身来说效率更低。
我想我可以创建一个空的稀疏矩阵，并使用循环添加值，但肯定会有更好的方法。
当涉及稀疏矩阵时，scipy文档真的很令人沮丧。
另请参阅 https://github.com/pandas-dev/pandas/issues/21909 - matanster
5个回答
9
如果在创建稀疏矩阵之前已经有了整个“alist”，则无需使用“lil_matrix”，因为它是针对增量更新稀疏矩阵进行优化的。
如果您想在之后对矩阵进行任何算术运算，那么“csr_matrix”可能是最好的选择。您可以直接使用“（data，（row，column））”格式构建“csr_matrix”，如下所示：
In [40]: alist = [[(1,10), (3,-3)],
    ...:          [(2,12)]]

In [41]: i, j, data = zip(*((i, t[0], t[1]) for i, row in enumerate(alist) for t in row))

In [42]: (i, j, data)
Out[42]: ((0, 0, 1), (1, 3, 2), (10, -3, 12))

In [43]: csr_matrix((data, (i, j)), shape=(2, 4)).todense()
Out[43]: 
matrix([[ 0, 10,  0, -3],
        [ 0,  0, 12,  0]], dtype=int64)

如果效率是一个真正的问题，你可以直接使用indptr创建csr_matrix内部格式：
In [57]: indptr = np.cumsum([0] + [len(row) for row in alist])

In [58]: j, data = zip(*(t for row in alist for t in row))

In [59]: csr_matrix((data, j, indptr), shape=(2, 4)).todense()
Out[59]: 
matrix([[ 0, 10,  0, -3],
        [ 0,  0, 12,  0]])

如果你在之后转换为pandas，使用coo_matrix是最好的选择，因为pandas会自动转换为coo_matrix：
In [41]: i, j, data = zip(*((i, t[0], t[1]) for i, row in enumerate(alist) for t in row))

In [43]: coo_matrix((data, (i, j)), shape=(2, 4))
感谢您的考虑！实际上，在我的特定情况下，我只需要将其作为稀疏特征矩阵与其他数据框列一起使用，可以轻松地使用pandas进行处理和查看，然后在其上拟合sklearn模型（.fit）。 - matanster
2
在这种情况下，coo_matrix是最好的选择，因为pandas无论如何都会转换为该格式。 - kuppern87
提供 coo_matrix 的形状在性能上有帮助/必要吗？即使没有它，它也可以工作！ - matanster
2
如果您不提供形状，则coo_matrix将从shape =（max（i），max（j））中推导出它。如果例如最后一列或最后一行全为零，这可能会导致问题，因为您将从矩阵中丢失该行/列。 - kuppern87
8

您的数据布局非常不寻常。以下是我尝试使用它的第一步。

In [565]: M = sparse.lil_matrix((2,4), dtype=int)
In [566]: M
Out[566]: 
<2x4 sparse matrix of type '<class 'numpy.int32'>'
    with 0 stored elements in LInked List format>
In [567]: for i,row in enumerate(alist):
     ...:     for col in row:
     ...:         M[i, col[0]] = col[1]
     ...:         
In [568]: M
Out[568]: 
<2x4 sparse matrix of type '<class 'numpy.int32'>'
    with 3 stored elements in LInked List format>
In [569]: M.A
Out[569]: 
array([[ 0, 10,  0, -3],
       [ 0,  0, 12,  0]])

是的，这是迭代的；lil是最好的格式。

或者使用常见的输入样式coo：

In [580]: data,col,row = [],[],[]
In [581]: for i, rr in enumerate(alist):
     ...:     for cc in rr:
     ...:         row.append(i)
     ...:         col.append(cc[0])
     ...:         data.append(cc[1])
     ...:         
In [582]: data,col,row
Out[582]: ([10, -3, 12], [1, 3, 2], [0, 0, 1])
In [583]: M1=sparse.coo_matrix((data,(row,col)),shape=(2,4))
In [584]: M1
Out[584]: 
<2x4 sparse matrix of type '<class 'numpy.int32'>'
    with 3 stored elements in COOrdinate format>
In [585]: M1.A
Out[585]: 
array([[ 0, 10,  0, -3],
       [ 0,  0, 12,  0]])

另一种选择是创建空的lil矩阵，并直接填写其属性:
换句话说，从以下内容开始:
In [591]: m.data
Out[591]: array([[], []], dtype=object)
In [592]: m.rows
Out[592]: array([[], []], dtype=object)

并将它们改为：

In [587]: M.data
Out[587]: array([[10, -3], [12]], dtype=object)
In [588]: M.rows
Out[588]: array([[1, 3], [2]], dtype=object)

这仍然需要在您的alist结构上进行2层迭代。

In [593]: for i, rr in enumerate(alist):
     ...:     for cc in rr:
     ...:         m.rows[i].append(cc[0])
     ...:         m.data[i].append(cc[1])       
In [594]: m
Out[594]: 
<2x4 sparse matrix of type '<class 'numpy.int32'>'
    with 3 stored elements in LInked List format>
In [595]: m.A
Out[595]: 
array([[ 0, 10,  0, -3],
       [ 0,  0, 12,  0]])

在另一条评论中，你提到理解 csr indptr 的难度。最简单的方法是将这些格式之一转换为另一种格式：

In [597]: Mr=M.tocsr()
In [598]: Mr.indptr
Out[598]: array([0, 2, 3], dtype=int32)
In [599]: Mr.data
Out[599]: array([10, -3, 12])
In [600]: Mr.indices
Out[600]: array([1, 3, 2], dtype=int32)
3
非常清晰、有用和详细的回答 — 谢谢！基于COO格式的构造器似乎是最自然的，我可以想出一些生成器来产生它，并实现一个内存和时间高效的输入管道。我希望Scipy开发人员能够添加一些类似这样的示例，以便人们能够找到它们。这是我的数据所采用的格式，鉴于支持所有这些不同的稀疏格式的系统的数量，如稀疏数组 - 维基百科所讨论的那样，我认为更多的人会使用它们交换数据。 - nealmcb
1
我最初在MATLAB中为有限元问题使用了稀疏矩阵。在那里，“coo”输入格式是唯一的选择，尽管它在内部将数据存储为“csc”（至少是它保存到“.mat”文件的格式）。大多数稀疏数学是为线性代数问题开发的。“scipy”添加了许多格式（请注意Wiki文章中的链接）。现在，许多稀疏矩阵的兴趣来自于大数据问题、稀疏特征矩阵、机器学习、语言学等领域。例如，“scikit learn”添加了一些自己编译的稀疏矩阵实用程序。 - hpaulj
我觉得令人惊讶的是，原始的OP数据结构会被认为是不寻常的（与上面的评论相反）。 - matanster
4
你可以从 (列，值) 元组列表 `alist` 中创建一个位置和值的 `dict`，然后使用 `dok_matrix` 构建稀疏矩阵。
>>> d = {(i,j):v for i,l in enumerate(alist) for j,v in l}
>>> d
{(0, 1): 10, (0, 3): -3, (1, 2): 12}
>>> 
>>> from operator import itemgetter
>>> m = max(d.keys(), key=itemgetter(0))[0] + 1
>>> n = max(d.keys(), key=itemgetter(1))[1] + 1
>>> m,n
(2, 4)
>>>
>>> from scipy.sparse import dok_matrix
>>> S = dok_matrix((m,n), dtype=int)
>>> for pos,v in d.items():
...     S[pos] = v
... 
>>> S.todense()
matrix([[ 0, 10,  0, -3],
        [ 0,  0, 12,  0]])
>>>
什么时候需要加上.todense()？ - matanster
这里绝对需要使用itemgetter吗？ - matanster
@matanster。.todense()只是为了展示矩阵的样子。 - Sunitha
1
@matanster。itemgetter 不是必须的。我们只需要自动获取维度。您可以将其替换为 lambda t: t[0]。这样看起来就像 m = max(d.keys(), key=lambda t: t[0])[0] + 1 和 n = max(d.keys(), key=lambda t: t[1])[1] + 1。 - Sunitha
3

我想再发布一个使用coo_matrix的答案，这是一种用于构建稀疏矩阵的快速格式。

>>> alist = [[(1, 10), (3, -3)], [(2, 12)]]
>>> row, col, data = zip(*((i,j,v) for i,l in enumerate(alist) for j,v in l))
>>>
>>> from scipy.sparse import coo_matrix
>>> S = coo_matrix((data, (row, col)), (max(row)+1,max(col)+1), dtype=np.int8)
>>> S.todense()
matrix([[ 0, 10,  0, -3],
        [ 0,  0, 12,  0]], dtype=int8)
>>>
0
发布的解决方案可以总结为三个步骤：添加行号，展开行数据，提取坐标和数据。这里是一个更详细的迭代实现方式：
alist = [[(1,10), (3,-3)],[(2,12)]]

import itertools
from scipy import sparse

# add row ids

it = enumerate(alist)
# explode row data by id
it = map(lambda t: itertools.product([t[0]],*t[1:]), it)
it = itertools.chain(*it)
# flatten tupples
it = map(lambda t: (t[0],*t[1]), it)
# extract coordinates and data 
i,j,data=zip(*it)
# use coo format
sparse.coo_matrix((data,(i,j)))
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接