从字典创建一个稀疏矩阵

Question

我正在做一个学校项目，在那里我得到了一个无向图 G，并且应该在 G 中找到最小生成树。我想我会使用 Scipy 的 minimum_spanning_tree (https://docs.scipy.org/doc/scipy- 0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html)。但要做到这一点，我必须为它提供一个 array_like 或稀疏矩阵，二维。像这样：

x_right=
    ([[0, 2, 0],
    [2, 0, 5],
    [0, 5, 0]])

在项目中，我应该接受一个结构如下的邻接表：

x_input=
    {'A': [('B', 2)],
     'B': [('A', 2), ('C', 5)], 
     'C': [('B', 5)]}

试一试......有，看看 minimum_spanning_tree 是否给出了我想要的结果，我通过手动将 x_input 更改为 x_right 来运行它，我得到的输出为：

(0, 1)    2.0
(1, 2)    5.0

这是我想要的，但我应该以与 x_input 相同的格式返回输出。

我一直在尝试各种方法（其中一种 DictVectorizer - ValueError: could not convert string to float: 'B'... 就像在其他情况下一样）很长时间，我认为是时候寻求帮助了。

因此，归根结底，您是否有关于如何从 x_input 创建适合于 minimum_spanning_tree 的矩阵的建议（以及如何将结果再次转换为 x_input 格式）。

谢谢

Answer 1

不确定我是否完全理解这个问题。从我得到的是你想转换x_input为稀疏矩阵x_right

import scipy.sparse as sp

x_input= {'A': [('B', 2)],
          'B': [('A', 2), ('C', 5)], 
          'C': [('B', 5)]}

keys = x_input.keys()
map_dict = dict(zip(list(keys), range(len(keys))))

我创建字典键以将值映射到上面的索引，例如 from Ato1和Bto 2。然后，您可以遍历给定的字典以获得行/列位置。之后，您可以将具有相应值的矩阵的行/列对转换为稀疏矩阵。

rows, cols, vals = [], [], []
for key, values in x_input.items():
    for value in values:
        rows.append(map_dict[key])
        cols.append(map_dict[value[0]])
        vals.append(value[1])
X = sp.csr_matrix((vals, (rows, cols)))

输出如下：

print(X.toarray())
array([[0, 2, 0],
       [2, 0, 5],
       [0, 5, 0]], dtype=int64)

要将稀疏矩阵转换回，简单的方法是将稀疏 CSR 矩阵转换为 COO 矩阵。COO 矩阵让您轻松获取行、列和数据。获得行/列位置后，我有字典map_dict_reverse将它们转换回给定的键。

from collections import defaultdict
map_dict_reverse = dict(zip(range(len(keys)), list(keys)))

Xcoo = X.tocoo() # convert csr matrix to coo sparse matrix
x_convert = defaultdict(list)
for (r, c, d) in zip(Xcoo.row, Xcoo.col, Xcoo.data):
    x_convert[map_dict_reverse[r]].append((map_dict_reverse[c] , d))
x_convert = dict(x_convert)

你会x_input在最后回来。

{'A': [('B', 2)], 'B': [('A', 2), ('C', 5)], 'C': [('B', 5)]}