SciPy - CSGraph
CSGraph 代表压缩稀疏图,专注于基于稀疏矩阵表示的快速图算法。
图表示
首先,让我们了解什么是稀疏图以及它如何帮助图表示。
稀疏图到底是什么?
图只是节点的集合,节点之间有链接。图几乎可以表示任何东西 &min; 社交网络连接,其中每个节点都是一个人并与熟人相连;图像,其中每个节点都是一个像素并与相邻像素相连;高维分布中的点,其中每个节点都与其最近的邻居相连;以及您能想象到的任何其他东西。
表示图形数据的一种非常有效的方法是使用稀疏矩阵:我们称之为 G。矩阵 G 的大小为 N x 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.])
使用稀疏图的单词阶梯
单词阶梯是 Lewis Carroll 发明的一种游戏,其中单词通过每一步改变一个字母来连接。例如 −
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 是单词阶梯中相连的字母数。
来自 scipy.spatial.distance 导入 pdist, squareform 来自 scipy.sparse 导入 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']