凑单算法——基于Graph Embedding的bundle mining

本文涉及的产品
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
OpenSearch LLM智能问答版免费试用套餐,存储1GB首月+计算资源100CU
智能开放搜索 OpenSearch向量检索版,4核32GB 1个月
简介: 本文描述如何在凑单场景突破找相似、发现惊喜的同时做到成交翻倍,实现体验和数据上的双赢。

一、背景

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

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

image.pngimage.png
    购物车的凑单入口        凑单页

二、核心算法

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)训练。下图是算法框架图。
image.png
                算法框架图

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。
image.png
                商品graph

b)Sampling

  传统的方法,比如deep walk,它的Sampling本质上是有两部分,首先,通过random walk的方式进行游走截断,其次,在仍给word2vec中Skip-Gram模型进行embedding之前,用negative sampling的方式去构造样本;这种随机采样的方法会大概率的将热门节点采集为负样本,这种方式适用于语言模型,因为在自然语言中,热门的单词均为无用单词(比如he、she、it、is、the)。对于我们的商品网络,刚好相反,热门商品往往是最重要的样本,如果采用negative sampling的方式去构造样本,模型肯定是学不出来。因此,我们基于边的权重去采样(weighted walk),使采样尽量往热门节点方向游走,以下图为例:
      image.png
             带权重的商品graph

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

Algorithm 1 Weigted Walk($G,n,Walks$)
Input: Graph $G(V,E,W)$
   Step $n$
Output: $walk$
Initialization: $walk$ to empty
  For each $v_i$ $\in$ $V$ do
   Append $v_i$ to $walk$
   For $j=1...n$ do
     $v_j=GetNeighbor(G,v_i)$
     Append $v_j$ to $walk$
   Return $walk$

Algorithm 2 $GetNeighbor(G,v_i)$
Input: Graph $G(V,E,W)$
   Node $v_i$
Output: next node $v_j$
$v_j=WeightedSample(v_i,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),规避无监督模型无法离线评估模型效果的问题。模型结构如下图。
image.png
              有监督的embedding模型(DNN)

有监督的embedding环节做了许多迭代优化,详见另一篇ata:基于DNN的多目标、多通道的bundle算法

三、实现

1、离线

  a)训练:离线模型在PAI平台上用tensorflow框架实现,抽取了历史50天的全网成交数据,大概抽取3000万节点,构建的graph,在odps graph平台做完weighted walk,产出2亿条样本,也就是item-item的pair对,训练至收敛需要2小时的时间
  b)预测:从全网所有行为中,随机抽取几十亿条pair对,去做预测,给每对item pair预测一个score
  c)上线:对每个种子商品取topN的bundle商品,打到搜索引擎的倒排和正排字段,从qp中取出每个用户的种子商品,基于倒排字段召回bundle商品,基于正排字段做bundle排序

2、实时

  用户购买行为,日常和大促差异很大,为了能够实时的捕获用户实时行为,我们在porsche上建了一套实时计算bundle mining的流程:
  a)数据预处理:在porsche上对用户实时日志进行收集,按离线的数据格式处理成实时的数据流
  b)Sampling:发送给odps graph实时计算平台,构建graph,做weighted walk,生成序,再通过swift消息发出
  c)Embedding:在porsche上做DNN模型训练和实时预测
  d)数据后处理:计算item的topN的bundle item list,实时写到dump和引擎

四、实验和结果

双十一预热期间,我们将bundle算法上线对比基准桶,提升很明显

1、点击:离线版bundle算法对比基准桶,ipv提升13%,实时版bundle算法在此基础上又提升4%,如下图:

image.png

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

image.png

五、总结

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

六、未来和展望

  凑单在未来还要继续努力,我们还有不完善的地方,在产品形态上,第一,价格preview没有做出来,用户不知道自己已经加购了多少,还差多少,能用多少优惠券,我们希望下次能在凑单页帮用户实时的算出凑单进度,第二,我们这次没有实时捕捉到入口种子商品,下次我们期望能做到,不同入口点进去,凑单的商品能和入口种子商品强相关;在算法优化上,把新颖性做强,尝试用graph bandit的方法,给用户投放一些没看过的但又相关的品类,根据投放的收益,设计一个合理的机制去explore。

相关文章
|
5月前
|
机器学习/深度学习 自然语言处理 搜索推荐
神经网络算法 —— Embedding(嵌入)!!
神经网络算法 —— Embedding(嵌入)!!
166 1
|
2月前
|
机器学习/深度学习 算法 数据挖掘
【博士每天一篇文-算法】Graph Structure of Neural Networks
本文介绍了尤家轩在2020年发表于国际机器学习会议上的研究,该研究探讨了神经网络的图结构与预测性能之间的关系,并提出了一种新的关系图表示方法,揭示了神经网络性能与图聚类系数和平均路径长度的函数关系,同时发现最优神经网络图结构与生物神经网络相似。
14 2
【博士每天一篇文-算法】Graph Structure of Neural Networks
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
算法金 | 没有思考过 Embedding,不足以谈 AI
**摘要:** 本文深入探讨了人工智能中的Embedding技术,解释了它是如何将高维数据映射到低维向量空间以简化处理和捕获内在关系的。文章介绍了词向量、图像嵌入和用户嵌入等常见类型的Embedding,并强调了其在自然语言处理、计算机视觉和推荐系统中的应用。此外,还讨论了Embedding的数学基础,如向量空间和线性代数,并提到了Word2Vec、GloVe和BERT等经典模型。最后,文章涵盖了如何选择合适的Embedding技术,以及在资源有限时的考虑因素。通过理解Embedding,读者能够更好地掌握AI的精髓。
47 0
算法金 | 没有思考过 Embedding,不足以谈 AI
|
5月前
|
算法 搜索推荐 Python
Python高级数据结构——图论算法(Graph Algorithms)
Python高级数据结构——图论算法(Graph Algorithms)
146 0
|
机器学习/深度学习 分布式计算 算法
阿里凑单算法首次公开!基于Graph Embedding的打包购商品挖掘系统解析
你是否也曾遇到类似的情况——差5块钱就能包邮,跨店满400减50就少20怎么办?凑单作为购物券导购链路的一个重要环节,旨在帮助你找到合适的商品。如何在凑单场景突破找相似、发现惊喜的同时做到成交翻倍,实现体验和数据上的双赢?今天我们一起来破解。
7800 0
|
机器学习/深度学习 算法 搜索推荐
|
1天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
1天前
|
编解码 算法 数据挖掘
基于MUSIC算法的六阵元圆阵DOA估计matlab仿真
该程序使用MATLAB 2022a版本实现基于MUSIC算法的六阵元圆阵DOA估计仿真。MUSIC算法通过区分信号和噪声子空间,利用协方差矩阵的特征向量估计信号到达方向。程序计算了不同角度下的MUSIC谱,并绘制了三维谱图及对数谱图,展示了高分辨率的DOA估计结果。适用于各种形状的麦克风阵列,尤其在声源定位中表现出色。
|
7天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
1天前
|
数据采集 算法 5G
基于稀疏CoSaMP算法的大规模MIMO信道估计matlab性能仿真,对比LS,OMP,MOMP,CoSaMP
该研究采用MATLAB 2022a仿真大规模MIMO系统中的信道估计,利用压缩感知技术克服传统方法的高开销问题。在稀疏信号恢复理论基础上,通过CoSaMP等算法实现高效信道估计。核心程序对比了LS、OMP、NOMP及CoSaMP等多种算法的均方误差(MSE),验证其在不同信噪比下的性能。仿真结果显示,稀疏CoSaMP表现优异。
8 2