生活随笔
收集整理的這篇文章主要介紹了
node2vec算法
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
圖嵌入算法
- 一、背景
- 二、DeepWalk
- 三、node2vec
- 引言
- node2walk
- skip-gram(用中心詞預測周圍詞)
一、背景
1.提出
①使用鄰接矩陣表示網絡時,由于矩陣中大多數元素是0,難以體現節點間關系,同時數據的稀疏性使得計算效率很低
②為此提出圖嵌入算法:將圖節點或子圖以低維向量形式表達,供現有模型直接使用。
2.應用
①節點分類任務,預測網絡中某節點最可能的標簽。如社交網絡:用戶感興趣對象;蛋白質網絡:蛋白質功能
②邊預測任務,預測網絡中兩節點是否應該相連。如社交網絡:兩用戶是否朋友
3.特點
①節點的向量表達僅考慮節點間關系,沒考慮節點本身特征
二、DeepWalk
RandomWalk
DeepWalk使用隨機游走(RandomWalk)的方式在圖中進行節點采樣。
RandomWalk:給定當前訪問起始節點,從其鄰居中隨機采樣節點作為下一個訪問節點,重復此過程,直到訪問序列長度滿足預設條件。原則是可重復訪問已訪問節點的深度優先遍歷算法。
RandomWalk采樣的過程:
①打亂頂點集合V
②自頂點vi開始在圖G中進行步數為t的隨機游走,得到游走序列Wvi=(vi,…,vj)
③窗口大小w,將序列Wvi輸入SkipGram中用于訓練隱藏層參數Φ
④重復上述過程,直到每一個vi都做過起始點
如下圖:
選擇如打亂集合中各個頂點后,先選擇了頂點1,然后隨機游走(即隨機選擇下一個定點),依次走到了3,1,5,…窗口大小就是游走序列的長度。頂點1游走完之后再從頂點2開始隨機游走,依次走到了1,3,4,…。頂點2游走完之后再從頂點6開始游走,依次走到了1,5,1,…一直到所有頂點都作為起點游走過后,這時我們會得到頂點個數個長度為窗口大小的游走序列,然后用這些序列去訓練。deepwalk和node2vec的不同之后在于游走的方法不同,而二者的序列訓練方法基本相同,下面介紹node2vec
三、node2vec
引言
前文所介紹的DeepWalk獲得游走序列是基于DFS鄰域,基于BFS獲得游走序列的是LINE。node2vec種綜合考慮DFS鄰域和BFS鄰域的graph embedding方法。簡單來說,node2walk可以看作是deepwalk的一種擴展,即結合了DFS和BFS隨機游走的deepwalk。
注意:node2vec是利用node2walk獲取的序列。deepwalk是利用randomwalk獲取的序列。
node2walk
node2walk的游走策略(已經由節點t游走到節點v,下一步如何抉擇),根據下面公式,計算出每個每個鄰近節點的“值”,然后折算成概率,最后別名采樣(alias sample)算法最終游走到的目標節點(p越小,embedding越傾向于表達同質性;q越小,embedding越傾向于表達結構性)
下圖的含義是上一步在頂點t,當前在頂點v,下一步走到頂點x的“權重”。dtx=0,1,2分別表示下一步走回t,走到x1,走到x2或x3的權重。(對應距離上一步位置t與下一步位置x的距離分別是0,1,2)
skip-gram(用中心詞預測周圍詞)
經過node2vec后,我們得到了若干序列,我們認為在同一個序列中出現的詞之間是有關聯的,所以我們希望用同一個序列中按照某個規則,兩兩取頂點,將一個頂點作為輸入值,另一個頂點作為標簽,經過神經網絡訓練后,取出網絡中的某個矩陣,那個這個矩陣就是這些頂點的嵌入詞向量,即能表示某個詞,有了向量就能通過計算向量間距離來判斷某兩個頂點之間的距離(關系度)了。
假設網絡中一共有1194個結點,算法的步驟為:
①對每個結點進行維數1194的獨熱編碼
②初始化embedding矩陣,形狀(1194,128)
③用一個batch的train_inputs(128,1194)點乘embedding矩陣,得到這些輸入樣本的嵌入詞向量組成的矩陣embed(128,128)。
注意:embedding矩陣(嵌入圖矩陣)是由所有詞的嵌入詞向量組成的。
如下圖,左邊是一個batch的train_inputs矩陣的一個行向量(1x1194),代表編號為3的頂點的獨熱編碼。右邊是embedding矩陣(1194x128),每一列對應一個頂點的嵌入詞向量,那么運算結果為該頂點對應的嵌入詞向量。那么用一個batch(設batch_size=128)的train_inputs矩陣點乘embedding矩陣,得到這些輸入樣本的嵌入詞向量組成的矩陣embed(128,128)。
④初始化weights矩陣,形狀(1194,128)以及biases(biases初始值0)
⑤用embed(128,128)點乘轉置的weights(128,1194)并加上biases,得到隱藏層輸出hidden_out(128,1194)
hidden_out的含義是這128個輸入樣本中每個樣本對每個其他樣本的相似度。
⑥128個標簽組成了一個(128,1194)的矩陣labels
⑦用訓練值hidden_out和標簽值labels求損失,然后生成優化器
⑧經過迭代后,得到訓練完成后的embedding(1194,128),用每個結點的獨熱編碼乘以該矩陣,得到的表示這個結點的嵌入詞向量(128維)。
附上一段在某處看到的代碼(我添加了注釋):
這段代碼的作用是給一篇文章,然后輸出與每個單詞關聯度最高的單詞。
import time
import collections
import math
import os
import random
import zipfile
import numpy
as np
import urllib
import pprint
import tensorflow
as tf
import matplotlib
.pyplot
as plt
os
.environ
["TF_CPP_MIN_LOG_LEVEL"] = "2"url
= "http://mattmahoney.net/dc/"def maybe_download(filename
, expected_bytes
):"""判斷文件是否已經下載,如果沒有,則下載數據集"""if not os
.path
.exists
(filename
):filename
, _
= urllib
.request
.urlretrieve
(url
+ filename
, filename
)stateinfo
= os
.stat
(filename
)if stateinfo
.st_size
== expected_bytes
:print("數據集已存在,且文件尺寸合格!", filename
)else :print(stateinfo
.st_size
)raise Exception
("文件尺寸不對 !請重新下載,下載地址為:"+url
)return filename
"""
測試文件是否存在
"""
filename
= maybe_download
("text8.zip", 31344016)def read_data(filename
):with zipfile
.ZipFile
(filename
) as f
: data
= tf
.compat
.as_str
(f
.read
(f
.namelist
()[0])).split
() '''使用 zipfile.ZipFile()來提取壓縮文件,然后我們可以使用zipfile 模塊中的讀取器功能。首先,namelist()函數檢索該檔案中的所有成員——在本例中只有一個成員,所以我們可以使用 0 索引對其進行訪問。然后,我們使用 read()函數讀取文件中的所有文本,并傳遞給 TensorFlow 的 as_str 函數,以確保文本保存為字符串數據類型。最后,我們使用 split()函數創建一個列表,該列表包含文本文件中所有的單詞,并用空格字符分隔'''return datafilename
= "text8.zip"
words
= read_data
(filename
)
print("總的單詞個數:", len(words
))
vocabulary_size
= 50000def build_dataset(words
): count
= [["UNK", -1]] count
.extend
(collections
.Counter
(words
).most_common
(vocabulary_size
- 1))dictionary
= {}for word
, _
in count
:dictionary
[word
] = len(dictionary
)data
= []unk_count
= 0 for word
in words
:if word
in dictionary
:index
= dictionary
[word
]else:index
= 0unk_count
+= 1data
.append
(index
) """print(data[:10])[5234, 3081, 12, 6, 195, 2, 3134, 46, 59, 156]"""count
[0][1] = unk_count reverse_dictionary
= dict(zip(dictionary
.values
(), dictionary
.keys
()))return data
, count
, dictionary
, reverse_dictionary
data
,count
,dictionary
,reverse_dictionary
= build_dataset
(words
)
del words
data_index
= 0def generate_batch(batch_size
, num_skips
, skip_window
):""":param batch_size: 每個訓練批次的數據量,8:param num_skips: 每個單詞生成的樣本數量,不能超過skip_window的兩倍,并且必須是batch_size的整數倍,2:param skip_window: 單詞最遠可以聯系的距離,設置為1則表示當前單詞只考慮前后兩個單詞之間的關系,也稱為滑窗的大小,1:return:返回每個批次的樣本以及對應的標簽"""global data_index
assert batch_size
% num_skips
== 0assert num_skips
<= skip_window
* 2batch
= np
.ndarray
(shape
=(batch_size
), dtype
=np
.int32
) labels
= np
.ndarray
(shape
=(batch_size
, 1), dtype
=np
.int32
) span
= 2 * skip_window
+ 1 buffer = collections
.deque
(maxlen
=span
) """print(batch,"\n",labels)batch :[0 ,-805306368 ,405222565 ,1610614781 ,-2106392574 ,2721-,2106373584 ,163793]labels: [[ 0][-805306368][ 407791039][ 536872957][ 2][ 0][ 0][ 131072]]"""for _
in range(span
):buffer.append
(data
[data_index
])data_index
= (data_index
+1) % len(data
)"""print(buffer,"\n",data_index) 輸出:deque([5234, 3081, 12], maxlen=3)3"""for i
in range(batch_size
// num_skips
): target
= skip_window targets_avoid
= [skip_window
] for j
in range(num_skips
): """第二層循環,每次循環對一個語境單詞生成樣本,先產生隨機數,直到不在需要避免的單詞中,也即需要找到可以使用的語境詞語"""while target
in targets_avoid
:target
= random
.randint
(0, span
-1)targets_avoid
.append
(target
) batch
[i
* num_skips
+ j
] = buffer[skip_window
] labels
[i
* num_skips
+ j
, 0] = buffer[target
] buffer.append
(data
[data_index
])data_index
= (data_index
+ 1) % len(data
)return batch
, labels
batch
, labels
= generate_batch
(8, 2, 1)
"""
for i in range(8):print("目標單詞:"+reverse_dictionary[batch[i]]+"對應編號為:".center(20)+str(batch[i])+" 對應的語境單詞為: ".ljust(20)+reverse_dictionary[labels[i,0]]+" 編號為",labels[i,0])
測試結果:
目標單詞:originated 對應編號為: 3080 對應的語境單詞為: as 編號為 12
目標單詞:originated 對應編號為: 3080 對應的語境單詞為: anarchism 編號為 5233
目標單詞:as 對應編號為: 12 對應的語境單詞為: originated 編號為 3080
目標單詞:as 對應編號為: 12 對應的語境單詞為: a 編號為 6
目標單詞:a 對應編號為: 6 對應的語境單詞為: as 編號為 12
目標單詞:a 對應編號為: 6 對應的語境單詞為: term 編號為 195
目標單詞:term 對應編號為: 195 對應的語境單詞為: of 編號為 2
目標單詞:term 對應編號為: 95 對應的語境單詞為: a 編號為 6
"""
batch_size
= 128
embedding_size
= 128
skip_window
= 1
num_skips
= 1
valid_size
= 16
valid_window
= 100
valid_examples
= np
.random
.choice
(valid_window
, valid_size
, replace
=False)
num_sampled
= 64
graph
= tf
.Graph
()
with graph
.as_default
():train_inputs
= tf
.compat
.v1
.placeholder
(tf
.int32
, [batch_size
]) train_labels
= tf
.compat
.v1
.placeholder
(tf
.int32
, [batch_size
, 1]) valid_dataset
= tf
.constant
(valid_examples
, tf
.int32
) with tf
.device
("/cpu:0"):embeddings
= tf
.Variable
(tf
.compat
.v1
.random_uniform
([vocabulary_size
, embedding_size
], -1.0, 1.0)) embed
= tf
.nn
.embedding_lookup
(embeddings
, train_inputs
) weights
= tf
.Variable
(tf
.compat
.v1
.truncated_normal
([vocabulary_size
, embedding_size
], stddev
=1.0 /math
.sqrt
(embedding_size
))) biases
= tf
.Variable
(tf
.zeros
([vocabulary_size
]))hidden_out
= tf
.matmul
(embed
, tf
.transpose
(weights
)) + biases train_one_hot
= tf
.one_hot
(train_labels
, vocabulary_size
) cross_entropy
= tf
.reduce_mean
(tf
.nn
.softmax_cross_entropy_with_logits
(logits
=hidden_out
, labels
=train_one_hot
)) optimizer
= tf
.compat
.v1
.train
.GradientDescentOptimizer
(1.0).minimize
(cross_entropy
)norm
= tf
.compat
.v1
.sqrt
(tf
.compat
.v1
.reduce_sum
(tf
.square
(weights
), 1, keepdims
=True))normalized_embeddings
= weights
/ norm valid_embeddings
= tf
.nn
.embedding_lookup
(normalized_embeddings
, valid_dataset
) similarity
= tf
.matmul
(valid_embeddings
, normalized_embeddings
, transpose_b
=True )init
= tf
.compat
.v1
.global_variables_initializer
()
num_steps
= 150001
t0
= time
.time
()
with tf
.compat
.v1
.Session
(graph
=graph
) as session
:init
.run
() print("初始化完成!")average_loss
= 0 for step
in range(num_steps
):batch_inputs
, batch_labels
= generate_batch
(batch_size
, num_skips
, skip_window
) feed_dict
= {train_inputs
: batch_inputs
, train_labels
: batch_labels
} optimizer_trained
, loss_val
= session
.run
([optimizer
, cross_entropy
], feed_dict
=feed_dict
) average_loss
+= loss_val
if step
% 2000 == 0:if step
> 0:average_loss
/= 2000print('第%d輪迭代用時:%s' % (step
, time
.time
() - t0
))t0
= time
.time
()print("第{}輪迭代后的損失為:{}".format(step
, average_loss
))average_loss
= 0if step
% 10000 == 0:sim
= similarity
.eval() for i
in range(valid_size
):valid_word
= reverse_dictionary
[valid_examples
[i
]] top_k
= 8nearest
= (-sim
[i
, :]).argsort
()[1:top_k
+1] log_str
= "與單詞 {} 最相似的: ".format(str(valid_word
))for k
in range(top_k
):close_word
= reverse_dictionary
[nearest
[k
]] log_str
= "%s %s, " % (log_str
, close_word
)print(log_str
)final_embeddings
= normalized_embeddings
.eval()
def plot_with_labels(low_dim_embs
, labels
, filename
= "tsne.png"):assert low_dim_embs
.shape
[0] >= len(labels
), "標簽數超過了嵌入向量的個數!!"plt
.figure
(figsize
=(20, 20))for i
, label
in enumerate(labels
):x
, y
= low_dim_embs
[i
, :]plt
.scatter
(x
, y
)plt
.annotate
(label
,xy
= (x
, y
),xytext
=(5, 2),textcoords
="offset points",ha
="right",va
="bottom")plt
.savefig
(filename
)
from sklearn
.manifold
import TSNE
tsne
= TSNE
(perplexity
=30, n_components
=2, init
="pca", n_iter
=5000)
plot_only
= 100
low_dim_embs
= tsne
.fit_transform
(final_embeddings
[:plot_only
, :])
Labels
= [reverse_dictionary
[i
] for i
in range(plot_only
)]
plot_with_labels
(low_dim_embs
, Labels
)
plt
.show
()
"""
第142000輪迭代后的損失為:4.46674475479126
第144000輪迭代后的損失為:4.460033647537231
第146000輪迭代后的損失為:4.479593712329865
第148000輪迭代后的損失為:4.463101862192154
第150000輪迭代后的損失為:4.3655951328277585
與單詞 can 最相似的: may, will, would, could, should, must, might, cannot,
與單詞 were 最相似的: are, was, have, had, been, be, those, including,
與單詞 is 最相似的: was, has, are, callithrix, landesverband, cegep, contains, became,
與單詞 been 最相似的: be, become, were, was, acuity, already, banded, had,
與單詞 new 最相似的: repertory, rium, real, ursus, proclaiming, cegep, mesoplodon, bolster,
與單詞 their 最相似的: its, his, her, the, our, some, these, landesverband,
與單詞 when 最相似的: while, if, where, before, after, although, was, during,
與單詞 of 最相似的: vah, in, neutronic, widehat, abet, including, nine, cegep,
與單詞 first 最相似的: second, last, biggest, cardiomyopathy, next, cegep, third, burnt,
與單詞 other 最相似的: different, some, various, many, thames, including, several, bearings,
與單詞 its 最相似的: their, his, her, the, simplistic, dativus, landesverband, any,
與單詞 from 最相似的: into, through, within, in, akita, bde, during, lawless,
與單詞 would 最相似的: will, can, could, may, should, might, must, shall,
與單詞 people 最相似的: those, men, pisa, lep, arctocephalus, protectors, saguinus, builders,
與單詞 had 最相似的: has, have, was, were, having, ascribed, wrote, nitrile,
與單詞 all 最相似的: auditum, some, scratch, both, several, many, katydids, two,
"""
總結
以上是生活随笔為你收集整理的node2vec算法的全部內容,希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯,歡迎將生活随笔推薦給好友。