CSGraph表示壓縮稀疏圖,它著重于基于稀疏矩陣表示快速圖算法。
首先,讓我們了解一個稀疏圖是什么以及它在圖表示中的作用。
稀疏圖是什么?
圖只是節(jié)點的集合,它們之間有鏈接。 圖幾乎可以代表任何事物 - 社交網(wǎng)絡(luò)連接,每個節(jié)點都是一個人,并且與熟人相連; 圖像,其中每個節(jié)點是像素并連接到相鄰像素; 指向一個高維分布,其中每個節(jié)點連接到最近的鄰居; 實際上你可以想象的任何其他東西。
表示圖形數(shù)據(jù)的一種非常有效的方式是在一個稀疏矩陣中: 假設(shè)名稱為G
。矩陣G
的大小為N×N
,并且G[i,j]
給出節(jié)點'i'
和節(jié)點之間的連接的值'J'
。 稀疏圖形包含大部分零 - 也就是說,大多數(shù)節(jié)點只有幾個連接。
在scikit-learn
中使用的幾種算法激發(fā)了稀疏圖子模塊的創(chuàng)建,其中包括以下內(nèi)容 -
作為一個具體的例子,假設(shè)想要表示以下無向圖 -
該圖有三個節(jié)點,其中節(jié)點0
和1
通過權(quán)重2
的邊連接,節(jié)點0
和2
通過權(quán)重1
的邊連接??梢詷?gòu)造如下例所示的稠密,蒙板和稀疏表示,無向圖由對稱矩陣表示。
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)
上述程序?qū)⑸梢韵螺敵?-
array([2, 1, 2, 1])
這與前面的圖相同,只是節(jié)點0
和2
通過零權(quán)重的邊連接。 在這種情況下,上面的稠密表示會導(dǎo)致含糊不清 - 如果零是一個有意義的值,那么如何表示非邊緣。 在這種情況下,必須使用蒙版或稀疏表示來消除歧義。
參考下面的例子 -
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)
上述程序?qū)⑸梢韵螺敵?-
array([ 2., 0., 2., 0.])
使用稀疏圖的詞梯子
詞梯是劉易斯卡羅爾發(fā)明的游戲,其中單詞通過在每一步更改單個字母而鏈接在一起。 例如 -
APE → APT → AIT → BIT → BIG → BAG → MAG → MAN
在這里,分七步從“APE”
到“MAN”
,每次更換一個字母。 問題是 - 我們能否使用相同的規(guī)則在這些詞之間找到更短的路徑? 這個問題自然表示為一個稀疏圖形問題。 節(jié)點將對應(yīng)于單個單詞,并且將創(chuàng)建最多不超過一個字母的單詞之間的連接。
首先,當(dāng)然,我們必須獲得有效的單詞列表。如果使用Mac,并且Mac在以下代碼塊中給出的位置具有單詞字典。 如果在其它的架構(gòu)上,可能需要搜索一下才能找到你的系統(tǒng)字典。
wordlist = open('/usr/share/dict/words').read().split()
print (len(wordlist))
執(zhí)行上面示例代碼,得到以下結(jié)果 -
205882
現(xiàn)在想看長度為3
的單詞,選擇正確長度的單詞。 還將消除以大寫字母(專有名詞)開頭的單詞或包含撇號和連字符等非字母數(shù)字字符的單詞。 最后,確保一切都是小寫的,以便稍后進(jìn)行比較。
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))
執(zhí)行上面示例代碼,得到以下結(jié)果 -
1185
現(xiàn)在,列出了1185
個有效的三個字母的單詞(確切的數(shù)字可能會根據(jù)所使用的特定列表而變化)。 這些單詞中的每一個都將成為圖中的一個節(jié)點,我們將創(chuàng)建連接與每對單詞關(guān)聯(lián)的節(jié)點的邊,這些節(jié)點之間的差異只有一個字母。
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)
執(zhí)行上面示例代碼,得到以下結(jié)果 -
(1185,3)
我們將使用每個點之間的漢明距離來確定連接哪些單詞對。 漢明距離度量兩個向量之間的條目分?jǐn)?shù),它們不同:漢明距離等于1/N1/N
的任何兩個單詞,其中NN
是單詞階梯中連接的字母數(shù)。
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))
比較距離時,不使用相等性,因為這對于浮點值可能不穩(wěn)定。 只要字表中沒有兩個條目是相同的,不平等就會產(chǎn)生所需的結(jié)果。 現(xiàn)在,圖形已經(jīng)建立,我們將使用最短路徑搜索來查找圖形中任何兩個單詞之間的路徑。
i1 = word_list.searchsorted('ape')
i2 = word_list.searchsorted('man')
print (word_list[i1],word_list[i2])
執(zhí)行上面示例代碼,得到以下結(jié)果 -
ape, man
我們需要檢查它們是否匹配,因為如果單詞不在列表中,輸出中會有錯誤。 現(xiàn)在,需要在圖中找到這兩個索引之間的最短路徑。使用dijkstra
算法,因為它能夠為一個節(jié)點找到路徑。
from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
print (distances[i2])
執(zhí)行上面示例代碼,得到以下結(jié)果 -
5.0
因此,我們看到ape
和man
之間的最短路徑只包含五個步驟。可以使用算法返回的前輩來重構(gòu)這條路徑。
path = []
i = i2
while i != i1:
path.append(word_list[i])
i = predecessors[i]
path.append(word_list[i1])
print (path[::-1]i2])
上述程序?qū)⑸梢韵螺敵?-
['ape', 'ope', 'opt', 'oat', 'mat', 'man']