SciPy CSGraph

CSGraph是 Compressed Sparse Graph 的缩写，它专注于基于稀疏矩阵表示的快速图形算法。

图形表示法

首先，让我们了解一下什么是稀疏图，以及它是如何帮助进行图形表示的。

究竟什么是稀疏图？

图只是一个节点的集合，这些节点之间有链接。图几乎可以代表任何东西–社交网络连接，其中每个节点是一个人，并与熟人相连；图像，其中每个节点是一个像素，并与邻近的像素相连；高维分布中的点，其中每个节点与其最近的邻居相连；以及几乎任何你能想象的东西。

表示图数据的一种非常有效的方法是用稀疏矩阵：我们称它为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)

上述程序将产生以下输出。

235886

我们现在要看的是长度为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)

上述程序将产生以下输出。

1135

现在，我们有一个包含1135个有效的三个字母单词的列表（确切的数字可能会根据所使用的特定列表而改变）。这些词中的每一个都将成为我们图中的一个节点，我们将创建连接与每一对词相关的节点的边，这些节点只相差一个字母。

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

上述程序将产生以下输出。

(1135, 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

因此，我们看到，”猿 “和 “人 “之间的最短路径只包含五个步骤。我们可以使用该算法返回的前辈来重建这个路径。

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']