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

以上程序将生成e以下输出.

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


使用对称矩阵的无向图

这除了节点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.])

使用稀疏图的字梯

Word Ladders是由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是字梯数,它们连接在单词梯中.

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