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