从字典创建稀疏矩阵

Question

我正在进行一项学校项目，其中我获得了一个无向图G，并应该在其中找到最小生成树。我想使用Scipy中的minimum_spanning_tree (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html)。但是要这样做，我必须提供一个类似数组或稀疏矩阵的2维数据。

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

在这个项目中，我需要接收一个邻接列表，它的结构应该像这样：

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

为了尝试一下……我想看看最小生成树是否给出了我想要的结果，所以我手动将x_input更改为x_right运行了它，输出如下：

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

这正是我想要的，但我需要以与x_input相同的格式返回输出结果。

我已经尝试了各种方法（其中一个是DictVectorizer - ValueError：无法将字符串转换为浮点数：“B”...就像其他情况一样），但是时间太长了，我认为现在是寻求帮助的时候了。

因此，简而言之，您有关于如何从x_input创建适合最小生成树的矩阵（以及如何再次将结果转换为x_input格式）的建议吗？

谢谢

- Lara Hronn

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))))

我创建字典键来将值映射到索引上，例如从 A 到 1，从 B 到 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)]}

- titipata

---

你说得完全正确（现在看起来有点混淆）。谢谢你的回复。 - Lara Hronn

是的，有很多微小的事情正在发生！请随意花时间来消化它。 - titipata