基于Graph Embedding的凑单算法是什么

这篇文章主要讲解了"基于Graph Embedding的凑单算法是什么"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"基于Graph Embedding的凑单算法是什么"吧！

一、背景

  凑单作为购物券导购链路的一个重要环节，旨在帮助用户找到商品，达成某个满减门槛（比如满400减50），完成跨店凑单，完善购物券整个链路的体验。满减购物券作为大促中使用最广泛的一种营销手段，优势远大于红包、商品打折等优惠活动，它不仅能给用户带来切实的优惠，而且能让用户买的更多，提升客单价。凑单作为用券的重要链路，旨在帮助消费者找到能使用同门槛优惠券的商品。

  今年凑单相比往年，有两个重大突破，首先是产品形态上的改变，往年，凑单只是一个商品推荐页，今年，凑单能够支持搜索、价格筛选、类目筛选、销量排序、价格排序等搜索功能。其次，算法上做了重大突破，基于Graph Embedding的bundle mining，bundle是打包购的意思，我们认为凑单的重要场景是当用户已经加购了商品A，还想找一个能一起打包买的商品B，而不是想找跟A相似的商品C，传统的u2i、相似i2i并不能满足凑单场景的需求，为了突破找相似等经常被人诟病的体验，我们甚至不能有u2i、相似i2i等逻辑，所以bundle mining变成凑单算法优化的重点，不仅能提升丰富性的体验，还能提升转化效率。

二、核心算法

1、基本思路

  图是一种抽象程度高、表达能力强的数据结构，它通过对节点和边的定义来描述实体和实体之间的关联关系。常用的图有社交关系网络、商品网络、知识图谱等等。

  用户行为是一个天然的网络图，边和节点往往有着各种丰富的信息，graph embedding是学习节点隐表示向量，在一个连续向量空间中对节点的关联关系进行编码，便于计算节点之间的关联关系，同时，graph具有传播能力，通过random walk可以挖掘多度关系，能有效的提升覆盖度，扩大召回。

  Graph Embedding是学术界一个重要研究方向，比如deep walk，是语言模型和无监督学习从单词序列扩展到图结构上的一个典型方法，该方法将截断游走的序列当成句子进行学习，之后采用word2vec中Skip-Gram模型进行训练，得到每个节点的embedding向量。Line只针对边进行采样，Node2vec可以调节参数来进行BFS或者DFS的抽样。

  所以Graph Embedding的基本思路是，对graph进行采样（Sampling），采出来的序构建模型（Embedding）。

2、主要技术

  结合我们的场景，要挖掘共同购买的关系，直接通过item-item的关系挖掘也可以做到，传统的协同过滤，也可以做到，为什么我们还需要构建graph？因为graph具有传播能力，它不仅能有效的提取出来直接关联，而且可以通过游走策略，挖掘出来二度、三度的关系。我们认为，朋友的朋友，也是朋友，也存在一定的弱关联，有效的利用这种传播能力，能解决购买数据的稀疏性，大大的提升覆盖。

  我们主要有三方面的工作，一是，基于用户购买行为构建graph，节点：商品，边：商品间同时购买的行为，权重：同时购买的比重，可以是购买次数、购买时间、金额等feature；二是，基于权重Sampling（weighted walk）作为正样本的候选，负样本从用户非购买行为中随机抽样；三是，embedding部分将无监督模型升级成有监督模型，将基于weighted walk采出来的序，构造成item-item的pair对，送给有监督模型（DNN）训练。下图是算法框架图。

                算法框架图

a) 构建Graph

  上文提到，我们要挖掘商品间共同购买的关系（bundle mining），类似买了又买的问题，所以，我们构建的graph是带权重的商品网络，节点：商品，边：商品间共同购买的关系，权重：共同购买次数、购买时间。

  为什么需要带权重的Graph？因为random walk等传统方法不适用商品网络，商品节点动辄上千万，其中大部分节点的关联性是很弱的，也就是冷门商品居多，只有少部分商品构建的graph是热点，如果采用random walk去采样，会采出很多冷门节点的序列，所以我们基于边的权重去采样（weighted walk），使采样尽量往热门节点方向游走，这样采样出来的样本置信度才更高。

  因此，我们的输入是一个带weight的graph ，Graph定义：G = （V，E，W），V = vertex （顶点或者节点，在bundle的问题中，特指商品），E = edge（边，在bundle的问题中，特指共同购买） ，W = weight（边的权重，共同购买的次数、时间），如下图，接下来就要进行sampling。

             带权重的商品graph

  举个例子来说，假设游走2步，从节点A出发，随机取下一个邻居节点时，如果是random walk算法，它会等概率的游走到B或C节点，但是我们的算法会以7/8的概率取节点C，再会以8/12的概率游走到节点D，最终很大概率上会采出来一条序walk=（A，C，D）walk=（A，C，D），对于原始graph，A和D是没有关联的，但是通过weighted walk，能够有效的挖掘出A和D的关系，算法详见：

Algorithm 1 Weigted Walk(G,n,WalksG,n,Walks)
Input: Graph G(V,E,W)G(V,E,W)
   Step nn
Output: walkwalk
Initialization: walkwalk to empty
  For each vivi ∈∈ VV do
   Append vivi to walkwalk
   For j=1...nj=1...n do
     vj=GetNeighbor(G,vi)vj=GetNeighbor(G,vi)
     Append vjvj to walkwalk
   Return walkwalk

Algorithm 2 GetNeighbor(G,vi)GetNeighbor(G,vi)
Input: Graph G(V,E,W)G(V,E,W)
   Node vivi
Output: next node vjvj
vj=WeightedSample(vi,w)vj=WeightedSample(vi,w)

  算法实现是在odps graph平台实现的，一个分布式的图计算平台，离线graph有2亿条边，3千万节点，10分钟跑完所有的数据，实时部分，我们实现了每分钟最高可更新10w的Graph边的结构，如何在分布式odps graph平台实现这套算法详见另一篇ata，尽请期待

c）Embedding

  上一部分介绍了如何构建了带权重的概率图，基于带权重的采样（weighted walk）作为正样本的候选，负样本从用户非购买行为中随机抽样；这一部分主要介绍embedding的部分，将基于weighted walk采出来的序，构造成item-item的pair对，送给embedding模型，我们构造了一个有监督embedding模型（DNN），规避无监督模型无法离线评估模型效果的问题。模型结构如下图。

2、丰富性：bundle算法对比基准桶，人均曝光叶子类目提升88%，人均曝光一级类目提升43%，如下图。

graph的核心优势，具有传播能力，朋友的朋友，也是朋友，传统i2i（统计版i2i）,只统计直接关系，而我们构建的共同购买的graph，可以通过游走挖掘多度关系，弥补购买行为稀疏的问题，有效的提升了覆盖率，我们离线实验发现，对比统计版本auc提升非常明显。我们实现了实时大规模graph更新，每分钟最高可更新10万条边，双11这么大的qps能够平稳运行。

感谢各位的阅读，以上就是"基于Graph Embedding的凑单算法是什么"的内容了，经过本文的学习后，相信大家对基于Graph Embedding的凑单算法是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！