推荐系统中的常用算法——DeepWalk算法

我会带着你远行 2022-05-28 05:38 442阅读 0赞

# 1. 概述 #

DeepWalk算法是在KDD2014中提出的算法，最初应用在图表示（Graph Embedding）方向，由于在推荐系统中，用户的行为数据固然的可以表示成图的形式，如下图所示：

![在这里插入图片描述][2020091712041581.png_pic_center]  
通过Graph Embedding得到图中每个item的Embedding表示，DeepWalk算法常被用于推荐系统。Graph Embedding使用低维稠密向量的形式表示图中的节点，使得在原始图中相似（不同的方法对相似的定义不同）的节点其在低维表达空间也接近。

# 2. 算法思想 #

DeepWalk算法借鉴了word2vec算法的思想，word2vec是NLP中一种常用的word embedding方法，word2vec通过语料库中的句子序列来描述词与词的共现关系，进而学习到词语的向量表示。DeepWalk算法与word2vec类似，使用图中节点与节点的共现关系来学习节点的向量表示。在DeepWalk中通过使用随机游走(RandomWalk)的方式在图中进行节点采样来模拟语料库中的预料，进而使用word2vec的方式学习出节点的共现关系，其具体过程如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center]  
具体过程为：

1.  抽取用户的行为序列，如图中(a)所示；
2.  将用户的行为序列转换成图的表示方法，如图中(b)所示；
3.  使用RandomWalk对图中节点采样，得到节点序列的表示，如图中©所示；
4.  使用Skip-Gram学习出节点的Embedding表示，如图中(d)所示。

DeepWalk算法思想具体过程如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 1]

## 2.1. RandomWalk ##

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。假设图为 G = ( V , E ) G=\\left ( V,E \\right ) G=(V,E)，其中， V V V表示图中点的集合， E E E表示图中边的集合，在RandomWalk中关键的问题是如何计算从节点 v i v\_i vi跳转到节点 v j v\_j vj的概率 P ( v j ∣ v i ) P\\left ( v\_j\\mid v\_i \\right ) P(vj∣vi)：

P ( v j ∣ v i ) = \{ M i j ∑ j ∈ N + ( v i ) M i j if v i ∈ N + ( v i ) 0 if e i j ∉ E P\\left ( v\_j\\mid v\_i \\right )=\\begin\{cases\} \\frac\{M\_\{ij\}\}\{\\sum \_\{j\\in N\_+\\left ( v\_i \\right )\}M\_\{ij\}\} & \\text\{ if \} v\_i\\in N\_+\\left ( v\_i \\right ) \\\\ 0 & \\text\{ if \} e\_\{ij\}\\notin E \\end\{cases\} P(vj∣vi)=\{ ∑j∈N\+(vi)MijMij0 if vi∈N\+(vi) if eij∈/E

其中， E E E是图中所有边的集合， N + ( v i ) N\_+\\left ( v\_i \\right ) N\+(vi)是节点 v i v\_i vi所有的出边的集合， M i j M\_\{ij\} Mij是节点 v i v\_i vi到节点 v j v\_j vj的边的权重，对于无向无权图 M i j = 1 M\_\{ij\}=1 Mij=1。RandomWalk的代码大致如下：

def deep_worker(self):
        for _ in range(self.nums):
        	for node in self.G.nodes():
            	self.node_series.append(self.random_walker(node))
     
    def random_walker(self, first_node):
    	series = [first_node]
        for _ in range(1, self.walk_length):
    		nodes_list = list(self.G.adj[first_node])
            first_node = random.choice(nodes_list)
            series.append(first_node)
        return series

## 2.2. word2vec ##

word2vec的基本原理不再在本文中详细给出，可以参阅其他的一些材料，Python下可以通过gensim里的Word2Vec实践：

from gensim.models import Word2Vec
    w2v_model = Word2Vec(walks,sg=1,hs=1)

# 参考文献 #

*  Perozzi B, Alrfou R, Skiena S. DeepWalk: online learning of social representations\[J\]. 2014:701-710.
 *  Wang J , Huang P , Zhao H , et al. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba\[J\]. 2018.
 *  [DeepWalk源码][DeepWalk]
 *  [《DeepWalk: Online Learning of Social Representations》笔记][DeepWalk_ Online Learning of Social Representations]
 *  [C实现的DeepWalk][C_DeepWalk]

[2020091712041581.png_pic_center]: /images/20220528/a352d4a4879942389ca7ae3be6b9bcfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center]: /images/20220528/3c0c4da1da824af0b20aaf7ea4470fcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220528/c8e1bf2fe8164aaea09ffbb728f7d754.png
[DeepWalk]: https://github.com/phanein/deepwalk
[DeepWalk_ Online Learning of Social Representations]: https://blog.csdn.net/Dinosoft/article/details/53557919
[C_DeepWalk]: https://github.com/xgfs/deepwalk-c