圖上 deepwalk 演算法理論 與 tensorflow keras 實戰，圖演算法之瑞士軍刀篇(二)
圖上 deepwalk 演算法理論 與 tensorflow keras 實戰，圖演算法之瑞士軍刀篇(二)
書接上文，在 deepwalk 演算法理論與實踐，圖演算法之瑞士軍刀篇(一) 中，我們講了 Graph Embeding 的鼻祖類演算法 deepwalk , 知道 deepwalk 演算法也遵循了 圖遊走演算法 的 基本架構 Walk + Skip-Gram Loss 架構 ， 並且 deepwalk 演算法 其中用的 walk 演算法是 隨機遊走 (random walk) 演算法 。
在 深入淺出理解word2vec模型 (理論與原始碼分析) 文章中我們 再三強調 了 輸入word2vec 的序列資料的重要性，並提供了構建序列的多種方法與技巧 。對於 圖遊走演算法 也是如此，我們採用 不同的遊走演算法久可以得到完全不同的效果 ，例如 node2vec 演算法就提出了一種 帶傾向遊走 (區域性探索與全域性探索的側重與融合) 進行 圖上節點序列取樣 的方法，而 metapath 和 metapath ++ 演算法 ，則又提供了 異構圖上可以定製路徑節點型別 的 元路徑(metapath) 的節點取樣演算法。不同的 遊走取樣 方法則 構成 了不同的 圖遊走演算法。
遊走取樣演算法、負樣本資料歸一化 以及 不同取樣演算法路徑融合的不同構成了近些年圖上游走演算法得到 graph embeding 的主要創新點和優化點 。 基於 "萬變不離其宗" 的思想，這裡 暫時 我們均 不在展開。
注意我們這裡要說明的一點是: word2vec 演算法，可以有無監督的版本，也有有監督的版本。如果單純以 外界是否顯式的輸入模型樣本標籤 的話，在 上一篇文章 中， 樣本不顯式帶有標籤，輸入模型的只有 正樣本 (center,context） pair 對， 可以把歸結為 無監督模型 。 而本文要介紹的演算法，在使用 tf.keras.preprocessing.sequence.skipgrams 取樣的時候帶有了 標籤，可以把歸結為 有監督模型。
這裡需要注意： 兩篇文章程式碼裡的方法，因為負樣本取樣均是 全域性取樣，而不是排除正樣本之外的負取樣，所以均是有一定概率的可能取樣到正樣本的，也就是說有得樣本明明是正樣本，被負樣本取樣演算法採到了標記了label 0。
由於上一篇 deepwalk 演算法理論與實踐，圖演算法之瑞士軍刀篇(一) 文章中，整個演算法流程是基於 tensorflow 1.x系列開發的，而我一直很為推崇 tensorflow 2.0 系列的keras 介面，所以本文將 主要說明 deepwalk 與 tensorflow 2.0 的 keras 實戰 過程，別的沒啥不同，關注 tensorflow 2.0 介面的同學，可以繼續閱讀下去了 ～
(1)程式碼時光
老規矩，為了保持每一篇文章的 完整性和獨立性 ，這裡和上一篇文章的冗餘部分，我們也再次 贅述 一下，異同部分 我會進行文字說明哈～
老規矩， 開篇先吼一嗓子 ， talk is cheap , show me the code !!!
本文的程式碼講的是 在圖上基於 tensorflow 2.0 的 keras 介面 實現的 deepwalk 演算法，整個原始碼流程是一個小型的 工業可用 的工程，覺得有用趕緊 收藏 轉發 吧 ～
(1.1) 導包 (和上文不同)
首先導包，把程式碼跑起來，僅僅需要這些python 包就可以了。
``` @ 歡迎關注作者公眾號 演算法全棧之路
import io import itertools import numpy as np import os import re import string import tensorflow as tf import tqdm import random import pandas as pd import networkx as nx from joblib import Parallel, delayed import tensorflow as tf from tensorflow.keras.layers import * from tensorflow.keras.models import Model ```
這裡匯入的包和上一篇文章裡略有不同，注意複製這裡的程式碼～
(1.2) 資料準備 (和上文同)
注意，我們這裡的程式碼適用於同構圖，當然你用同構圖來處理異構圖問題也是可以的，也許效果更好呢 ～
``` @ 歡迎關注作者公眾號 演算法全棧之路
graph_df = pd.DataFrame([['Tom', 'pig',], ['Nancy', 'Tom'], ['Jack', 'Nancy']], columns=['src', 'dst'], index=['0', '1', '2']) graph_df['weight']=1.0 print(graph_df) ```
這裡的節點都是 同一型別 ，基於某一個關係構建的邊，這裡 pandas 的 dataframe 是儲存的邊的 src 和 dst ，以及該邊對應的權重，weight 我們都把設定為 1.0 即可。
（1.3） 同構圖節點編碼 (和上文同)
老規矩，圖節點嘛，進行編碼, 數字化 後扔到圖框架裡去。
``` @歡迎關注微信公眾號：演算法全棧之路
編碼方法
def encode_map(input_array): p_map={} length=len(input_array) for index, ele in zip(range(length),input_array): # print(ele,index) p_map[str(ele)] = index return p_map
解碼方法
def decode_map(encode_map): de_map={} for k,v in encode_map.items(): # index,ele de_map[v]=k return de_map
print(type(graph_df['src'].values))
構建 encode/ decode map
node_encode_map=encode_map(set(np.append(graph_df['src'].values, graph_df['dst'].values, axis=0))) node_decode_map=decode_map(node_encode_map)
print(len(node_encode_map))
應用編碼
graph_df['src_node_encoded'] = graph_df['src'].apply(lambda e: node_encode_map.get(str(e),-1)) graph_df['dst_node_encoded'] = graph_df['dst'].apply(lambda e: node_encode_map.get(str(e),-1))
print(graph_df) ```
這裡的程式碼非常通俗易懂，我就不再贅述了。
（1.4） networkx 構圖 (和上文同)
``` @歡迎關注微信公眾號：演算法全棧之路
G = nx.from_pandas_edgelist(graph_df, 'src_node_encoded', 'dst_node_encoded', ['weight']) print(G) ```
這裡應用 networkx 進行記憶體裡邏輯圖的構建 。 可以從 pandas 以及多種 資料來源構建，感興趣的下去自行百度哈 ～
（1.5） random walk 遊走演算法取樣 (和上文同)
這裡是演算法 非常重要 的一塊，使用 隨機遊走演算法 random walk 在圖上進行節點取樣，看程式碼 ～
``` @歡迎關注微信公眾號：演算法全棧之路
def partition_num(num, workers): if num % workers == 0: return [num//workers]workers else: return [num//workers]workers + [num % workers]
class RandomWalker: def init(self, G): """ :param G: """ self.G = G def deepwalk_walk(self, walk_length, start_node):
walk = [start_node] while len(walk) < walk_length: cur = walk[-1] cur_nbrs = list(self.G.neighbors(cur)) if len(cur_nbrs) > 0: walk.append(random.choice(cur_nbrs)) else: break return walk
def simulate_walks(self, num_walks, walk_length, workers=1, verbose=0): """ :param num_walks: random walks 的次數 (每次都要遍歷所有 node ) :param walk_length: 每次 random walk 最大長度 :param workers: 程序數 :param verbose: :return: """ G = self.G
nodes = list(G.nodes()) # 並行分割槽數， results = Parallel(n_jobs=workers, verbose=verbose, )( delayed(self._simulate_walks)(nodes, num, walk_length) for num in partition_num(num_walks, workers)) walks = list(itertools.chain(*results)) # 序列取樣路徑 # walks= self._simulate_walks(nodes,num_walks,walk_length) print("walks_len:",len(walks)) return walks def _simulate_walks(self, nodes, num_walks, walk_length,): walks = [] for index in range(num_walks): # 對每一輪 random.shuffle(nodes) for v in nodes: walks.append(self.deepwalk_walk(walk_length=walk_length, start_node=v)) return walks
隨機遊走演算法呼叫
walker = RandomWalker(G) session_reproduce = walker.simulate_walks(num_walks=6, walk_length=3, workers=2,verbose=1) ```
這裡，我們提供了 並行和串行遊走 2種方法，注意看上文的程式碼註釋。如果圖資料量比較大，建議使用 python多執行緒 進行路徑遊走節點取樣哈。
注意： 這裡的 session_reproduce 本身就是返回的結果，就是一個 二維陣列 ，數組裡每一個元素就是一次取樣返回的節點序列，也就是一個路徑。
（1.6）skip gram 樣本構造 (和上文不同)
無論在何時，樣本構造都是非常重要的～
``` @歡迎關注微信公眾號：演算法全棧之路
sample_list=[] vocab_size=len(node_encode_map) window_size=1 negative_samples=5
for sequence in sequences: positive_skip, label = tf.keras.preprocessing.sequence.skipgrams( sequence, vocabulary_size=vocab_size, window_size=window_size, negative_samples=negative_samples) # 這裡 positive_skip 和 label 長度一致 for index in range(len(positive_skip)): target_word,context_word = positive_skip[index] cur_label = label[index] sample_list.append([target_word,context_word,cur_label]) w2v_sample_df=pd.DataFrame(sample_list, columns=["target", "context","label"]) w2v_sample_df.to_csv("supervised_w2v_sample.csv",sep=',',index=False) ```
注意，這裡的 程式碼非常重要。 我們這裡的 vocab_size=len(node_encode_map) 注意這裡，後面匯出節點的embeding 的時候要用到 。
對於 sequences 二維數組裡的每一個元素也是一個取樣序列 ，對這個序列，我們採用了 tf.keras.preprocessing.sequence.skipgrams這個介面 進行負取樣, 注意這裡 負取樣是 全域性負取樣，有 可能出現正樣本。
這裡negative_samples 我選擇了2 。這裡推薦在較小的資料集中一般將 num_ns 設定為 [5， 20] 範圍內的整數，而在較大的資料集一般設定為 [2， 5] 範圍內整數。
（1.7） 資料batch處理、模型訓練與 節點 embeding 匯出
``` @歡迎關注微信公眾號：演算法全棧之路
w2v_sample_pdf=pd.read_csv("supervised_w2v_sample.csv",sep=',') labels = w2v_sample_pdf.pop('label')
batch_size=32 buffer_size=1000 embedding_dim=16
train_dataset = tf.data.Dataset.from_tensor_slices((w2v_sample_pdf.values, labels.values)) train_dataset = train_dataset.shuffle(len(w2v_sample_pdf)).batch(batch_size) train_dataset = train_dataset.cache().prefetch(buffer_size=buffer_size)
class Word2Vec(object): def init(self,train_data,inverse_map,epoch=3,embedding_file="./embeding_file.csv",vocab_size=1000): self.embedding_dim = embedding_dim self.build_model() self.train_data=train_data self.epochs=epoch self.word_embedding_file=embedding_file self.vocab_size=vocab_size self.inverse_map=inverse_map
# 構建 word2vec 模型 def build_model(self): inputs = Input(shape=(2,)) target = inputs[:, 0:1] context = inputs[:, 1:2] self.words_embedding_in = tf.keras.layers.Embedding( vocab_size, self.embedding_dim, input_length=1, name="word_embedding_in" ) self.words_embedding_out = tf.keras.layers.Embedding( vocab_size, self.embedding_dim, input_length=1, name="word_embedding_out" ) word_emb = self.words_embedding_in(target) # batch_size,1,embeing_size context_emb = self.words_embedding_out(context) dots = tf.keras.layers.Dot(axes=(2, 2))([word_emb, context_emb]) outputs = tf.keras.layers.Flatten()(dots) self.model = Model(inputs, outputs)
self.model.compile( optimizer='adam', loss=tf.keras.losses.BinaryCrossentropy(from_logits=True), metrics=['accuracy'])
# 模型訓練 def train(self): self.model.fit(self.train_data, epochs=self.epochs)
def save_word_embeddings(self): with open(self.word_embedding_file, 'w') as f: # f.write('{} {}\n'.format(self.vocab_size, self.embedding_dim)) weights = self.words_embedding_in.get_weights()[0] for i in range(self.vocab_size): emb = weights[i, :] line = '{} {}\n'.format(self.inverse_map[i],','.join([str(x) for x in emb])) f.write(line)
word2vec = Word2Vec(train_dataset,embedding_file="./embeing.csv",vocab_size=vocab_size,inverse_map=node_decode_map) word2vec.train() word2vec.save_word_embeddings() ```
這裡因為是 tensorflow 2.0 keras 版本的程式碼，資料的 batch 化 使用了 tf.data.Dataset相關的介面，算是非常簡潔了。
注意這裡的匯出 節點embeding 的方法， weights = self.words_embedding_in.get_weights()[0]這裡直接取出了 words_embedding_in 作為 embeding 。
因為 模型裡的實現 words_embedding_in 和 words_embedding_out 兩個 variable ，可以分別取出這兩個embeding 求平均效果更好哦。
剩下的就是模型的訓練了，常規程式碼，我就不在進行贅述了。
最後程式碼跑起來就是這個樣子：
匯出的embeding 長這個樣子：
到這裡，圖上deepwalk 演算法理論與tensorflow keras實戰，圖演算法之瑞士軍刀篇(二) 的全文就寫完了。這也是 短時間內圖算法系列的最後一篇文章 了，接下來再有一篇文章 總結下圖演算法就完事了。
上面的程式碼demo 在環境沒問題的情況下，全部 複製到一個python檔案 裡，就可以完美執行起來。本文的程式碼是一個 小型的商業可以用的演算法工程專案 ，希望可以對你有參考作用 ～
碼字不易，覺得有收穫就動動小手轉載一下吧，你的支援是我寫下去的最大動力 ～
更多更全更新內容，歡迎關注作者的公眾號： 演算法全棧之路
- END -