CSGraph表示壓縮稀疏圖，它著重于基于稀疏矩陣表示快速圖算法。

圖表示

首先，讓我們了解一個(gè)稀疏圖是什么以及它在圖表示中的作用。

稀疏圖是什么？

圖只是節(jié)點(diǎn)的集合，它們之間有鏈接。 圖幾乎可以代表任何事物 - 社交網(wǎng)絡(luò)連接，每個(gè)節(jié)點(diǎn)都是一個(gè)人，并且與熟人相連; 圖像，其中每個(gè)節(jié)點(diǎn)是像素并連接到相鄰像素; 指向一個(gè)高維分布，其中每個(gè)節(jié)點(diǎn)連接到最近的鄰居; 實(shí)際上你可以想象的任何其他東西。

表示圖形數(shù)據(jù)的一種非常有效的方式是在一個(gè)稀疏矩陣中: 假設(shè)名稱(chēng)為G。矩陣G的大小為N×N，并且G[i，j]給出節(jié)點(diǎn)'i'和節(jié)點(diǎn)之間的連接的值'J'。 稀疏圖形包含大部分零 - 也就是說(shuō)，大多數(shù)節(jié)點(diǎn)只有幾個(gè)連接。

在scikit-learn中使用的幾種算法激發(fā)了稀疏圖子模塊的創(chuàng)建，其中包括以下內(nèi)容 -

• Isomap - 流形學(xué)習(xí)算法，需要在圖中找到最短路徑。
• 分層聚類(lèi) - 基于最小生成樹(shù)的聚類(lèi)算法。
• 譜分解 - 基于稀疏圖拉普拉斯算子的投影算法。

作為一個(gè)具體的例子，假設(shè)想要表示以下無(wú)向圖 -

該圖有三個(gè)節(jié)點(diǎn)，其中節(jié)點(diǎn)0和1通過(guò)權(quán)重2的邊連接，節(jié)點(diǎn)0和2通過(guò)權(quán)重1的邊連接?？梢詷?gòu)造如下例所示的稠密，蒙板和稀疏表示，無(wú)向圖由對(duì)稱(chēng)矩陣表示。

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é)點(diǎn)0和2通過(guò)零權(quán)重的邊連接。 在這種情況下，上面的稠密表示會(huì)導(dǎo)致含糊不清 - 如果零是一個(gè)有意義的值，那么如何表示非邊緣。 在這種情況下，必須使用蒙版或稀疏表示來(lái)消除歧義。

參考下面的例子 -

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ā)明的游戲，其中單詞通過(guò)在每一步更改單個(gè)字母而鏈接在一起。 例如 -

APE → APT → AIT → BIT → BIG → BAG → MAG → MAN

在這里，分七步從“APE”到“MAN”，每次更換一個(gè)字母。 問(wèn)題是 - 我們能否使用相同的規(guī)則在這些詞之間找到更短的路徑？ 這個(gè)問(wèn)題自然表示為一個(gè)稀疏圖形問(wèn)題。 節(jié)點(diǎn)將對(duì)應(yīng)于單個(gè)單詞，并且將創(chuàng)建最多不超過(guò)一個(gè)字母的單詞之間的連接。

獲取單詞列表

首先，當(dāng)然，我們必須獲得有效的單詞列表。如果使用Mac，并且Mac在以下代碼塊中給出的位置具有單詞字典。 如果在其它的架構(gòu)上，可能需要搜索一下才能找到你的系統(tǒng)字典。

wordlist = open('/usr/share/dict/words').read().split()
print (len(wordlist))

執(zhí)行上面示例代碼，得到以下結(jié)果 -

205882

現(xiàn)在想看長(zhǎng)度為3的單詞，選擇正確長(zhǎng)度的單詞。 還將消除以大寫(xiě)字母(專(zhuān)有名詞)開(kāi)頭的單詞或包含撇號(hào)和連字符等非字母數(shù)字字符的單詞。 最后，確保一切都是小寫(xiě)的，以便稍后進(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個(gè)有效的三個(gè)字母的單詞(確切的數(shù)字可能會(huì)根據(jù)所使用的特定列表而變化)。 這些單詞中的每一個(gè)都將成為圖中的一個(gè)節(jié)點(diǎn)，我們將創(chuàng)建連接與每對(duì)單詞關(guān)聯(lián)的節(jié)點(diǎn)的邊，這些節(jié)點(diǎn)之間的差異只有一個(gè)字母。

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)

我們將使用每個(gè)點(diǎn)之間的漢明距離來(lái)確定連接哪些單詞對(duì)。 漢明距離度量?jī)蓚€(gè)向量之間的條目分?jǐn)?shù)，它們不同:漢明距離等于1/N1/N的任何兩個(gè)單詞，其中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))

比較距離時(shí)，不使用相等性，因?yàn)檫@對(duì)于浮點(diǎn)值可能不穩(wěn)定。 只要字表中沒(méi)有兩個(gè)條目是相同的，不平等就會(huì)產(chǎn)生所需的結(jié)果。 現(xiàn)在，圖形已經(jīng)建立，我們將使用最短路徑搜索來(lái)查找圖形中任何兩個(gè)單詞之間的路徑。

i1 = word_list.searchsorted('ape')
i2 = word_list.searchsorted('man')
print (word_list[i1],word_list[i2])

執(zhí)行上面示例代碼，得到以下結(jié)果 -

ape, man

我們需要檢查它們是否匹配，因?yàn)槿绻麊卧~不在列表中，輸出中會(huì)有錯(cuò)誤。 現(xiàn)在，需要在圖中找到這兩個(gè)索引之間的最短路徑。使用dijkstra算法，因?yàn)樗軌驗(yàn)橐粋€(gè)節(jié)點(diǎn)找到路徑。

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è)步驟?？梢允褂盟惴ǚ祷氐那拜厑?lái)重構(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']