轉(zhuǎn)載https://blog.csdn.net/u012151283/article/details/86806922?spm=1001.2014.3001.5501
圖表示學(xué)習(xí)
我們都知道在數(shù)據(jù)結(jié)構(gòu)中宙帝，圖是一種基礎(chǔ)且常用的結(jié)構(gòu)」补現(xiàn)實(shí)世界中許多場(chǎng)景可以抽象為一種圖結(jié)構(gòu)谣膳，如社交網(wǎng)絡(luò)，交通網(wǎng)絡(luò)礁击，電商網(wǎng)站中用戶與物品的關(guān)系等。
目前提到圖算法一般指：
- 經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法層面的：最小生成樹(shù)(Prim,Kruskal,…)，最短路(Dijkstra,Floyed,…)看彼，拓?fù)渑判颍P(guān)鍵路徑等
- 概率圖模型囚聚，涉及圖的表示靖榕，推斷和學(xué)習(xí)，詳細(xì)可以參考Koller的書(shū)或者公開(kāi)課
- 圖神經(jīng)網(wǎng)絡(luò)顽铸，主要包括Graph Embedding(基于隨機(jī)游走)和Graph CNN(基于鄰居匯聚)兩部分茁计。
這里先看下Graph Embedding的相關(guān)內(nèi)容。
Graph Embedding技術(shù)將圖中的節(jié)點(diǎn)以低維稠密向量的形式進(jìn)行表達(dá)谓松，要求在原始圖中相似(不同的方法對(duì)相似的定義不同)的節(jié)點(diǎn)其在低維表達(dá)空間也接近星压。得到的表達(dá)向量可以用來(lái)進(jìn)行下游任務(wù)，如節(jié)點(diǎn)分類鬼譬，鏈接預(yù)測(cè)娜膘，可視化或重構(gòu)原始圖等。
DeepWalk 原理
我們都知道在數(shù)據(jù)結(jié)構(gòu)中优质，圖是一種基礎(chǔ)且常用的結(jié)構(gòu)】⑻埃現(xiàn)實(shí)世界中許多場(chǎng)景可以抽象為一種圖結(jié)構(gòu)，如社交網(wǎng)絡(luò)巩螃，交通網(wǎng)絡(luò)演怎，電商網(wǎng)站中用戶與物品的關(guān)系等。
目前提到圖算法一般指：
經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法層面的：最小生成樹(shù)(Prim,Kruskal,…)避乏，最短路(Dijkstra,Floyed,…)爷耀，拓?fù)渑判颍P(guān)鍵路徑等
概率圖模型淑际，涉及圖的表示畏纲，推斷和學(xué)習(xí)扇住，詳細(xì)可以參考Koller的書(shū)或者公開(kāi)課
圖神經(jīng)網(wǎng)絡(luò)，主要包括Graph Embedding(基于隨機(jī)游走)和Graph CNN(基于鄰居匯聚)兩部分盗胀。
這里先看下Graph Embedding的相關(guān)內(nèi)容艘蹋。
Graph Embedding技術(shù)將圖中的節(jié)點(diǎn)以低維稠密向量的形式進(jìn)行表達(dá)，要求在原始圖中相似(不同的方法對(duì)相似的定義不同)的節(jié)點(diǎn)其在低維表達(dá)空間也接近票灰。得到的表達(dá)向量可以用來(lái)進(jìn)行下游任務(wù)女阀，如節(jié)點(diǎn)分類，鏈接預(yù)測(cè)屑迂，可視化或重構(gòu)原始圖等浸策。
DeepWalk
DeepWalk 算法主要包括兩個(gè)步驟，第一步為隨機(jī)游走采樣節(jié)點(diǎn)序列惹盼，第二部為使用word2vec學(xué)習(xí)表達(dá)向量
Random Walk
我們可以通過(guò)并行的方式加速采樣庸汗，在采用多進(jìn)程進(jìn)行加速時(shí)，相比于開(kāi)一個(gè)進(jìn)程池讓每次外層循環(huán)啟動(dòng)一個(gè)進(jìn)程手报，我們采用固定為每個(gè)進(jìn)程分配指定數(shù)量的num_walks的方式蚯舱，這樣可以最大限度減少進(jìn)程頻繁創(chuàng)建與銷毀的時(shí)間開(kāi)銷。
deepwalk_walk方法對(duì)應(yīng)上一節(jié)偽代碼中第6行掩蛤，_simulate_walks對(duì)應(yīng)偽代碼中第3行開(kāi)始的外層循環(huán)枉昏。最后的Parallel為多進(jìn)程并行時(shí)的任務(wù)分配操作。
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, nodes, num_walks, walk_length,):
walks = []
for _ in range(num_walks):
random.shuffle(nodes)
for v in nodes:
walks.append(self.deepwalk_walk(alk_length=walk_length, start_node=v))
return walks
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))
Word2vec
這里就偷個(gè)懶直接用gensim里的Word2Vec了揍鸟。
from gensim.models import Word2Vec
w2v_model = Word2Vec(walks,sg=1,hs=1)
DeepWalk應(yīng)用
這里簡(jiǎn)單的用DeepWalk算法在wiki數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類任務(wù)和可視化任務(wù)兄裂。
wiki數(shù)據(jù)集包含 2,405 個(gè)網(wǎng)頁(yè)和17,981條網(wǎng)頁(yè)之間的鏈接關(guān)系，以及每個(gè)網(wǎng)頁(yè)的所屬類別阳藻。
本例中的訓(xùn)練晰奖，評(píng)測(cè)和可視化的完整代碼在下面的git倉(cāng)庫(kù)中，后面還會(huì)陸續(xù)更新line,node2vec,sdne,struc2vec等graph embedding算法以及一些GCN算法
https://github.com/shenweichen/GraphEmbedding/blob/master/examples/deepwalk_wiki.py
G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])
model = DeepWalk(G,walk_length=10,num_walks=80,workers=1)
model.train(window_size=5,iter=3)
embeddings = model.get_embeddings()
evaluate_embeddings(embeddings)
plot_embeddings(embeddings)
分類任務(wù)結(jié)果
| micro-F1 -|- macro-F1 |
| 0.6674 -|- 0.5768 |
可視化結(jié)果
