python - 如何读取边缘列表以制作 scipy 稀疏矩阵

Question

我有一个大文件，其中每一行都有一对 8 个字符的字符串。像这样的东西:

ab1234gh iu9240gh

在每一行。

这个文件实际上代表了一个图，每个字符串都是一个节点 ID。我想读入文件并直接制作一个 scipy 稀疏邻接矩阵。然后，我将使用 python 中可用的众多工具之一在此矩阵上运行 PCA

有没有一种巧妙的方法可以做到这一点，还是我需要先在 RAM 中制作图形，然后将其转换为稀疏矩阵？由于文件很大，我想尽可能避免中间步骤。

最终我会将稀疏邻接矩阵输入 http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html#sklearn.decomposition.TruncatedSVD .

Answer 1

我认为这是 sklearn 中的常规任务，因此包中必须有一些工具可以执行此操作，或者其他 SO 问题中的答案。我们需要添加正确的标签。

但仅根据我对 numpy 和 sparse 的了解，我会做什么:

制作一个示例二维数组 - N 行，2 列字符值:

In [638]: A=np.array([('a','b'),('b','d'),('a','d'),('b','c'),('d','e')])
In [639]: A
Out[639]: 
array([['a', 'b'],
       ['b', 'd'],
       ['a', 'd'],
       ['b', 'c'],
       ['d', 'e']], 
      dtype='<U1')

使用 np.unique 来识别唯一的字符串，并作为奖励将这些字符串映射到原始数组。这是任务的主力。

In [640]: k1,k2,k3=np.unique(A,return_inverse=True,return_index=True)
In [641]: k1
Out[641]: 
array(['a', 'b', 'c', 'd', 'e'], 
      dtype='<U1')
In [642]: k2
Out[642]: array([0, 1, 7, 3, 9], dtype=int32)
In [643]: k3
Out[643]: array([0, 1, 1, 3, 0, 3, 1, 2, 3, 4], dtype=int32)

我可以 reshape inverse 数组以识别 A 中每个条目的行和列。

In [644]: rows,cols=k3.reshape(A.shape).T
In [645]: rows
Out[645]: array([0, 1, 0, 1, 3], dtype=int32)
In [646]: cols
Out[646]: array([1, 3, 3, 2, 4], dtype=int32)

有了这些，构造一个在每个“交点”处都有 1 的稀疏矩阵就很简单了。

In [648]: M=sparse.coo_matrix((np.ones(rows.shape,int),(rows,cols)))
In [649]: M
Out[649]: 
<4x5 sparse matrix of type '<class 'numpy.int32'>'
    with 5 stored elements in COOrdinate format>
In [650]: M.A
Out[650]: 
array([[0, 1, 0, 1, 0],
       [0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1]])

第一行，a 在第 2 列和第 4 列，b 和 d 中有值。等等。

============================

最初我有:

In [648]: M=sparse.coo_matrix((np.ones(k1.shape,int),(rows,cols)))

这是错误的。 data 数组的形状应与 rows 和 cols 匹配。在这里它没有引发错误，因为 k1 恰好具有相同的大小。但是使用不同的组合，唯一值可能会引发错误。

====================

这种方法假定整个数据库A 都可以加载到内存中。 unique 可能需要类似的内存使用。最初，coo 矩阵可能不会增加内存使用量，因为它将使用提供的数组作为参数。但是任何计算和/或转换为 csr 或其他格式都会产生更多副本。

我可以想象通过分块加载数据库并使用其他一些结构来获取唯一值和映射来解决内存问题。您甚至可以从 block 中构造一个 coo 矩阵。但迟早你会遇到内存问题。 scikit 代码将制作该稀疏矩阵的一个或多个副本。