阿里凑单算法首次公开!基于Graph Embedding的打包购商品挖掘系统解析

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 你是否也曾遇到类似的情况——差5块钱就能包邮,跨店满400减50就少20怎么办?凑单作为购物券导购链路的一个重要环节,旨在帮助你找到合适的商品。如何在凑单场景突破找相似、发现惊喜的同时做到成交翻倍,实现体验和数据上的双赢?今天我们一起来破解。

一、背景

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

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

16ad8dd639c3b8fe2fbceb44aa65876d027e5675

二、核心算法

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

7c45f70030c8241b258eb43408bca233931355a8

算法框架图


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。

a4e08287b18421f7481d9462481b1f284dd9873d

商品graph

b)Sampling

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

98cead9feef2b413d886178137115e3873be376e

带权重的商品graph

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

5bf685bc8fdfa9c2c5a0e9d4102b797f1c1ff777

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

c)Embedding

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

adc80e67c23a11d279a2be5a559f8d99e6f94d7d

有监督的embedding模型(DNN)

三、实现

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%,如下图:

211fb168fcafa8cdbbb0dc8232f16c9e81cda128

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

35fc6388f47a17f6d320a9824113fb2154f17a7f

五、总结  

graph的核心优势,具有传播能力,朋友的朋友,也是朋友,传统i2i(统计版i2i),只统计直接关系,而我们构建的共同购买的graph,可以通过游走挖掘多度关系,弥补购买行为稀疏的问题,有效的提升了覆盖率,我们离线实验发现,对比统计版本auc提升非常明显。

我们实现了实时大规模graph更新,每分钟最高可更新10万量级边,双11这么大的qps能够平稳运行。

六、未来和展望  

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


原文发布时间为:2018-01-31

本文作者:清灵

本文来自云栖社区合作伙伴“ 阿里技术”,了解相关信息可以关注“阿里技术”微信公众号

相关文章
|
1月前
|
负载均衡 算法 Java
Spring Cloud全解析:负载均衡算法
本文介绍了负载均衡的两种方式:集中式负载均衡和进程内负载均衡,以及常见的负载均衡算法,包括轮询、随机、源地址哈希、加权轮询、加权随机和最小连接数等方法,帮助读者更好地理解和应用负载均衡技术。
|
20天前
|
机器学习/深度学习 算法 TensorFlow
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现用户上传一张动物图片,识别其名称。
49 1
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
|
19天前
|
机器学习/深度学习 人工智能 算法
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
植物病害识别系统。本系统使用Python作为主要编程语言,通过收集水稻常见的四种叶片病害图片('细菌性叶枯病', '稻瘟病', '褐斑病', '稻瘟条纹病毒病')作为后面模型训练用到的数据集。然后使用TensorFlow搭建卷积神经网络算法模型,并进行多轮迭代训练,最后得到一个识别精度较高的算法模型,然后将其保存为h5格式的本地模型文件。再使用Django搭建Web网页平台操作界面,实现用户上传一张测试图片识别其名称。
71 21
植物病害识别系统Python+卷积神经网络算法+图像识别+人工智能项目+深度学习项目+计算机课设项目+Django网页界面
|
19天前
|
机器学习/深度学习 人工智能 算法
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作界面,实现用户上传一张鸟类图像,识别其名称。
65 12
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
|
19天前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
45 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
15天前
|
机器学习/深度学习 人工智能 算法
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
文本分类识别系统。本系统使用Python作为主要开发语言,首先收集了10种中文文本数据集("体育类", "财经类", "房产类", "家居类", "教育类", "科技类", "时尚类", "时政类", "游戏类", "娱乐类"),然后基于TensorFlow搭建CNN卷积神经网络算法模型。通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型,并保存为本地的h5格式。然后使用Django开发Web网页端操作界面,实现用户上传一段文本识别其所属的类别。
28 1
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
1月前
|
前端开发 搜索推荐 算法
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
中草药管理与推荐系统。本系统使用Python作为主要开发语言,前端使用HTML,CSS,BootStrap等技术和框架搭建前端界面,后端使用Django框架处理应用请求,使用Ajax等技术实现前后端的数据通信。实现了一个综合性的中草药管理与推荐平台。具体功能如下: - 系统分为普通用户和管理员两个角色 - 普通用户可以登录,注册、查看物品信息、收藏物品、发布评论、编辑个人信息、柱状图饼状图可视化物品信息、并依据用户注册时选择的标签进行推荐 和 根据用户对物品的评分 使用协同过滤推荐算法进行推荐 - 管理员可以在后台对用户和物品信息进行管理编辑
58 12
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
|
11天前
|
算法 调度
操作系统的心脏:深入解析进程调度算法
本文旨在深入探讨现代操作系统中的核心功能之一——进程调度。进程调度算法是操作系统用于分配CPU时间片给各个进程的机制,以确保系统资源的高效利用和公平分配。本文将详细介绍几种主要的进程调度算法,包括先来先服务(FCFS)、短作业优先(SJF)、时间片轮转(RR)以及优先级调度(PS)。我们将分析每种算法的基本原理、优缺点及其适用场景。同时,本文还将讨论多级反馈队列(MFQ)调度算法,并探讨这些算法在实际应用中的表现及未来发展趋势。通过深入解析这些内容,希望能够为读者提供对操作系统进程调度机制的全面理解。
|
15天前
|
机器学习/深度学习 人工智能 算法
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台。果蔬识别系统,本系统使用Python作为主要开发语言,通过收集了12种常见的水果和蔬菜('土豆', '圣女果', '大白菜', '大葱', '梨', '胡萝卜', '芒果', '苹果', '西红柿', '韭菜', '香蕉', '黄瓜'),然后基于TensorFlow库搭建CNN卷积神经网络算法模型,然后对数据集进行训练,最后得到一个识别精度较高的算法模型,然后将其保存为h5格式的本地文件方便后期调用。再使用Django框架搭建Web网页平台操作界面,实现用户上传一张果蔬图片识别其名称。
35 0
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
20天前
|
机器学习/深度学习 存储 人工智能
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
使用Python作为开发语言,基于文本数据集(一个积极的xls文本格式和一个消极的xls文本格式文件),使用Word2vec对文本进行处理。通过支持向量机SVM算法训练情绪分类模型。实现对文本消极情感和文本积极情感的识别。并基于Django框架开发网页平台实现对用户的可视化操作和数据存储。
23 0
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计

热门文章

最新文章

推荐镜像

更多