Scipy CSGraph

Scipy CSGraph

CSGraph表示压缩稀疏图，它着重于基于稀疏矩阵表示快速图算法。

图表示

首先，让我们了解一个稀疏图是什么以及它在图表示中的作用。

稀疏图是什么？

图只是节点的集合，它们之间有链接。 图几乎可以代表任何事物 - 社交网络连接，每个节点都是一个人，并且与熟人相连; 图像，其中每个节点是像素并连接到相邻像素; 指向一个高维分布，其中每个节点连接到最近的邻居; 实际上你可以想象的任何其他东西。

表示图形数据的一种非常有效的方式是在一个稀疏矩阵中: 假设名称为G。矩阵G的大小为N×N，并且G[i，j]给出节点'i'和节点之间的连接的值'J'。 稀疏图形包含大部分零 - 也就是说，大多数节点只有几个连接。

在scikit-learn中使用的几种算法激发了稀疏图子模块的创建，其中包括以下内容 -

  • Isomap - 流形学习算法，需要在图中找到最短路径。
  • 分层聚类 - 基于最小生成树的聚类算法。
  • 谱分解 - 基于稀疏图拉普拉斯算子的投影算法。

作为一个具体的例子，假设想要表示以下无向图 -

该图有三个节点，其中节点0和1通过权重2的边连接，节点0和2通过权重1的边连接。可以构造如下例所示的稠密，蒙板和稀疏表示，无向图由对称矩阵表示。

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])

G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print (G_sparse.data)

上述程序将生成以下输出 - 

array([2, 1, 2, 1])

这与前面的图相同，只是节点0和2通过零权重的边连接。 在这种情况下，上面的稠密表示会导致含糊不清 - 如果零是一个有意义的值，那么如何表示非边缘。 在这种情况下，必须使用蒙版或稀疏表示来消除歧义。

参考下面的例子 - 

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print (G2_sparse.data)

上述程序将生成以下输出 - 

array([ 2., 0., 2., 0.])

使用稀疏图的词梯子

词梯是刘易斯卡罗尔发明的游戏，其中单词通过在每一步更改单个字母而链接在一起。 例如 -

APE → APT → AIT → BIT → BIG → BAG → MAG → MAN

在这里，分七步从“APE”到“MAN”，每次更换一个字母。 问题是 - 我们能否使用相同的规则在这些词之间找到更短的路径？ 这个问题自然表示为一个稀疏图形问题。 节点将对应于单个单词，并且将创建最多不超过一个字母的单词之间的连接。

获取单词列表

首先，当然，我们必须获得有效的单词列表。如果使用Mac，并且Mac在以下代码块中给出的位置具有单词字典。 如果在其它的架构上，可能需要搜索一下才能找到你的系统字典。

wordlist = open('/usr/share/dict/words').read().split()
print (len(wordlist))

执行上面示例代码，得到以下结果 - 

205882

现在想看长度为3的单词，选择正确长度的单词。 还将消除以大写字母(专有名词)开头的单词或包含撇号和连字符等非字母数字字符的单词。 最后，确保一切都是小写的，以便稍后进行比较。

word_list = [word for word in word_list if len(word) == 3]
word_list = [word for word in word_list if word[0].islower()]
word_list = [word for word in word_list if word.isalpha()]
word_list = map(str.lower, word_list)
print (len(word_list))

执行上面示例代码，得到以下结果 - 

1185

现在，列出了1185个有效的三个字母的单词(确切的数字可能会根据所使用的特定列表而变化)。 这些单词中的每一个都将成为图中的一个节点，我们将创建连接与每对单词关联的节点的边，这些节点之间的差异只有一个字母。

import numpy as np
word_list = np.asarray(word_list)

word_list.dtype
word_list.sort()

word_bytes = np.ndarray((word_list.size, word_list.itemsize),
   dtype = 'int8',
   buffer = word_list.data)
print (word_bytes.shape)

执行上面示例代码，得到以下结果 - 

(1185,3)

我们将使用每个点之间的汉明距离来确定连接哪些单词对。 汉明距离度量两个向量之间的条目分数，它们不同:汉明距离等于1/N1/N的任何两个单词，其中NN是单词阶梯中连接的字母数。

from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
hamming_dist = pdist(word_bytes, metric = 'hamming')
graph = csr_matrix(squareform(hamming_dist < 1.5 / word_list.itemsize))

比较距离时，不使用相等性，因为这对于浮点值可能不稳定。 只要字表中没有两个条目是相同的，不平等就会产生所需的结果。 现在，图形已经建立，我们将使用最短路径搜索来查找图形中任何两个单词之间的路径。

i1 = word_list.searchsorted('ape')
i2 = word_list.searchsorted('man')
print (word_list[i1],word_list[i2])

执行上面示例代码，得到以下结果 -

ape, man

我们需要检查它们是否匹配，因为如果单词不在列表中，输出中会有错误。 现在，需要在图中找到这两个索引之间的最短路径。使用dijkstra算法，因为它能够为一个节点找到路径。

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
print (distances[i2])

执行上面示例代码，得到以下结果 -

5.0

因此，我们看到ape和man之间的最短路径只包含五个步骤。可以使用算法返回的前辈来重构这条路径。

path = []
i = i2

while i != i1:
   path.append(word_list[i])
   i = predecessors[i]

path.append(word_list[i1])
print (path[::-1]i2])

上述程序将生成以下输出 - 

['ape', 'ope', 'opt', 'oat', 'mat', 'man']

目录
Scipy CSGraph