您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

了解携程个性化推荐算法原理,让旅行更实惠

时间:2019-11-14 10:35:57  来源:  作者:

携程作为国内领先的OTA,每天向上千万用户提供全方位的旅行服务,如何为如此众多的用户发现适合自己的旅游产品与服务,挖掘潜在的兴趣,缓解信息过载,个性化推荐系统与算法在其中发挥着不可或缺的作用。而OTA的个性化推荐一直也是个难点,没有太多成功经验可以借鉴,本文分享了携程在个性化推荐实践中的一些尝试与摸索。

推荐流程大体上可以分为3个部分,召回、排序、推荐结果生成,整体的架构如下图所示。

了解携程个性化推荐算法原理,让旅行更实惠

 

召回阶段,主要是利用数据工程和算法的方式,从千万级的产品中锁定特定的候选集合,完成对产品的初步筛选,其在一定程度上决定了排序阶段的效率和推荐结果的优劣。

业内比较传统的算法,主要是CF[1][2]、基于统计的Contextual推荐和LBS,但近期来深度学习被广泛引入,算法性取得较大的提升,如:2015年Netflix和Gravity R&D Inc提出的利用RNN的Session-based推荐[5],2016年Recsys上提出的结合CNN和PMF应用于Context-aware推荐[10],2016年google提出的将DNN作为MF的推广,可以很容易地将任意连续和分类特征添加到模型中[9],2017年IJCAI会议中提出的利用LSTM进行序列推荐[6]。2017年携程个性化团队在AAAI会议上提出的深度模型aSDAE,通过将附加的side information集成到输入中,可以改善数据稀疏和冷启动问题[4]。

对于召回阶段得到的候选集,会对其进行更加复杂和精确的打分与重排序,进而得到一个更小的用户可能感兴趣的产品列表。携程的推荐排序并不单纯追求点击率或者转化率,还需要考虑距离控制,产品质量控制等因素。相比适用于搜索排序,文本相关性检索等领域的pairwise和listwise方法,pointwise方法可以通过叠加其他控制项进行干预,适用于多目标优化问题。

工业界的推荐方法经历从线性模型+大量人工特征工程[11] -> 复杂非线性模型-> 深度学习的发展。Microsoft首先于2007年提出采用Logistic Regression来预估搜索广告的点击率[12],并于同年提出OWLQN优化算法用于求解带L1正则的LR问题[13],之后于2010年提出基于L2正则的在线学习版本Ad Predictor[14]。

Google在2013年提出基于L1正则化的LR优化算法FTRL-Proximal[15]。2010年提出的Factorization machine算法[17]和进一步2014年提出的Filed-aware Factorization Machine[18]旨在解决稀疏数据下的特征组合问题,从而避免采用LR时需要的大量人工特征组合工作。

阿里于2011年提出Mixture of Logistic Regression直接在原始空间学习特征之间的非线性关系[19]。Facebook于2014年提出采用GBDT做自动特征组合,同时融合Logistic Regression[20]。

近年来,深度学习也被成功应用于推荐排序领域。Google在2016年提出wide and deep learning方法[21],综合模型的记忆和泛化能力。进一步华为提出DeepFM[15]模型用于替换wdl中的人工特征组合部分。阿里在2017年将attention机制引入,提出Deep Interest Network[23]。

携程在实践相应的模型中积累了一定的经验,无论是最常用的逻辑回归模型(Logistic Regression),树模型(GBDT,Random Forest)[16],因子分解机(FactorizationMachine),以及近期提出的wdl模型。同时,我们认为即使在深度学习大行其道的今下,精细化的特征工程仍然是不可或缺的。

基于排序后的列表,在综合考虑多样性、新颖性、Exploit & Explore等因素后,生成最终的推荐结果。本文之后将着重介绍召回与排序相关的工作与实践。

一、数据
 

机器学习=数据+特征+模型

在介绍召回和排序之前,先简单的了解一下所用到的数据。携程作为大型OTA企业,每天都有海量用户来访问,积累了大量的产品数据以及用户行为相关的数据。实际在召回和排序的过程中大致使用到了以下这些数据:

  • 产品属性:产品的一些固有属性,如酒店的位置,星级,房型等。
  • 产品统计:比如产品一段时间内的订单量,浏览量,搜索量,点击率等。
  • 用户画像:用户基础属性,比如年纪,性别,偏好等等。
  • 用户行为:用户的评论,评分,浏览,搜索,下单等行为。

值得注意的是,针对统计类信息,可能需要进行一些平滑。例如针对历史CTR反馈,利用贝叶斯平滑来预处理。

二、召回

召回阶段是推荐流程基础的一步,从成千上万的Item中生成数量有限的候选集,在一定程度上决定了排序阶段的效率和推荐结果的优劣。而由OTA的属性决定,用户的访问行为大多是低频的。这就使得user-item的交互数据是极其稀疏的,这对召回提出了很大的挑战。在业务实践中,我们结合现有的通用推荐方法和业务场景,筛选和摸索出了几种行之有效的方法:

  • Real-timeIntention

我们的实时意图系统可以根据用户最近浏览下单等行为,基于马尔科夫预测模型推荐或者交叉推荐出的产品。这些候选产品可以比较精准的反应出用户最近最新的意愿。

  • BusinessRules

业务规则是认为设定的规则,用来限定推荐的内容范围等。例如机票推酒店的场景,需要通过业务规则来限定推荐的产品只能是酒店,而不会推荐其他旅游产品。

  • Context-Based

基于Context的推荐场景和Context本身密切相关,例如与季候相关的旅游产品(冬季滑雪、元旦跨年等)。

了解携程个性化推荐算法原理,让旅行更实惠

 

  • LBS

基于用户的当前位置信息,筛选出的周边酒店,景点,美食等等,比较适用于行中场景的推荐。地理位置距离通过GeoHash算法计算,将区域递归划分为规则矩形,并对每个矩形进行编码,筛选GeoHash编码相似的POI,然后进行实际距离计算。

  • CollaborativeFiltering

协同过滤算法是推荐系统广泛使用的一种解决实际问题的方法。携程个性化团队在深度学习与推荐系统结合的领域进行了相关的研究与应用,通过改进现有的深度模型,提出了一种深度模型aSDAE。该混合协同过滤模型是SDAE的一种变体,通过将附加的side information集成到输入中,可以改善数据稀疏和冷启动问题,详情可以参见文献[4]。

  • SequentialModel

现有的矩阵分解(Matrix Factorization)方法基于历史的user-item交互学习用户的长期兴趣偏好,Markov chain通过学习item间的transition graph对用户的序列行为建模[3]。事实上,在旅游场景下,加入用户行为的先后顺序,从而能更好的反映用户的决策过程。我们结合Matrix Factorization和Markov chain为每个用户构建个性化转移矩阵,从而基于用户的历史行为来预测用户的下一行为。在旅游场景中,可以用来预测用户下一个目的地或者POI。

除此之外,也可以使用RNN来进行序列推荐,比如基于Session的推荐[5],使用考虑时间间隔信息的LSTM来做下一个item的推荐等[6]。

此外,一些常见的深度模型(DNN, AE,CNN等)[7][8][9][10]都可以应用于推荐系统中,但是针对不同领域的推荐,需要更多的高效的模型。随着深度学习技术的发展,相信深度学习将会成为推荐系统领域中一项非常重要的技术手段。以上几种类型的召回方法各有优势,在实践中,针对不同场景,结合使用多种方法,提供给用户最佳的推荐,以此提升用户体验,增加用户粘性。

三、排序

以工业界在广告、搜索、推荐等领域的实践经验,在数据给定的条件下,经历了从简单线性模型+大量人工特征工程到复杂非线性模型+自动特征学习的演变。在构建携程个性化推荐系统的实践过程中,对于推荐排序这个特定问题有一些自己的思考和总结,并将从特征和模型这两方面展开。

  • Model

个性化排序模型旨在利用每个用户的历史行为数据集建立其各自的排序模型,本质上可以看作多任务学习(multi-task learning)。事实上,通过加入conjunctionfeatures,也就是加入user和product的交叉特征,可以将特定的multi-task任务简化为单任务模型。

梳理工业界应用的排序模型,大致经历三个阶段,如下图所示:

了解携程个性化推荐算法原理,让旅行更实惠

 

本文并不准备详细介绍上图中的算法细节,感兴趣的读者可以查看相关论文,以下几点是我们的一些实践经验和体会。

  • 在实践中选用以LR为主的模型,通过对数据离散化、分布转换等非线性处理后使用LR。一般的,采用L1正则保证模型权重的稀疏性。在优化算法的选择上,使用OWL-QN做batch learning,FTRL做online learning。
  • 实践中利用因子分解机(FactorizationMachine)得到的特征交叉系数来选择喂入LR模型的交叉特征组合,从而避免了繁杂的特征选择工作。一般的受限于模型复杂度只进行二阶展开。对于三阶以上的特征组合可以利用基于mutual information等方法处理。已有针对高阶因子分解机(HighOrder FM)的研究,参见文献[24]。
  • 对于Wide and Deep Learning,将wide部分替换gbdt组合特征,在实验中取得了较好的效果,并将在近期上线。后续的工作将针对如何进行wide部分和deep部分的alternatingtraining展开。
  • Feature Engineering

事实上,虽然深度学习等方法一定程度上减少了繁杂的特征工程工作,但我们认为精心设计的特征工程仍旧是不可或缺的, 其中如何进行特征组合是我们在实践中着重考虑的问题。一般的,可以分为显式特征组合和半显式特征组合。
 

显式特征组合

对特征进行离散化后然后进行叉乘,采用笛卡尔积(cartesian product)、内积(inner product)等方式。

在构造交叉特征的过程中,需要进行特征离散化;针对不同的特征类型,有不同的处理方式。

1、numerical feature

  • 无监督离散化:根据简单统计量进行等频、等宽、分位点等划分区间
  • 有监督离散化:1R方法,Entropy-BasedDiscretization (e.g. D2,MDLP)

2、ordinal feature(有序特征)

编码表示值之间的顺序关系。比如对于卫生条件这一特征,分别有差,中,好三档,那么可以分别编码为(1,0,0),(1,1,0),(1,1,1)。

3、categorical feature (无序特征)

离散化方法

具体做法

OHE(one hot encoding)

用h个变量代表h个level

Dummy Encoding

将一个有h个level的变量变成h-1个变量

Hash Trick

转化为固定长度的hash variable

  • 离散化为哑变量,将一维信息嵌入模型的bias中,起到简化逻辑回归模型的作用,降低了模型过拟合的风险。
  • 离散特征经过OHE后,每个分类型变量的各个值在模型中都可以看作独立变量,增强拟合能力。一般的,当模型加正则化的情况下约束模型自由度,我们认为OHE更好。
  • 利用feature hash技术将高维稀疏特征映射到固定维度空间

半显式特征组合

区别于显式特征组合具有明确的组合解释信息,半显式特征组合通常的做法是基于树方法形成特征划分并给出相应组合路径。

一般做法是将样本的连续值特征输入ensemble tree,分别在每颗决策树沿着特定分支路径最终落入某个叶子结点得到其编号,本质上是这些特征在特定取值区间内的组合。ensemble tree可以采用Gbdt 或者 random forest实现。每一轮迭代,产生一棵新树,最终通过one-hotencoding转化为binary vector,如下图所示。

了解携程个性化推荐算法原理,让旅行更实惠

 

以下几点是我们在实践中的一些总结和思考。

  • 在实验中发现如果将连续值特征进行离散化后喂入gbdt,gbdt的效果不佳,AUC比较低。这是因为gbdt本身能很好的处理非线性特征,使用离散化后的特征反而没什么效果。xgboost等树模型无法有效处理高维稀疏特征比如user id类特征,可以采用的替代方式是:将这类id利用一种方式转换为一个或多个新的连续型特征,然后用于模型训练。
  • 需要注意的是当采用叶子结点的index作为特征输出需要考虑每棵树的叶子结点并不完全同处于相同深度。
  • 实践中采用了Monte Carlo Search对xgboost的众多参数进行超参数选择。
  • 在离线训练阶段采用基于Spark集群的xgboost分布式训练,而在线预测时则对模型文件直接进行解析,能够满足线上实时响应的需求。

此外,在实践发现单纯采用Xgboost自动学到的高阶组合特征后续输入LR模型并不能完全替代人工特征工程的作用;可以将原始特征以及一些人工组合的高阶交叉特征同xgboost学习到的特征组合一起放入后续的模型,获得更好的效果。

四、总结

完整的推荐系统是一个庞大的系统,涉及多个方面,除了召回、排序、列表生产等步骤外,还有数据准备与处理,工程架构与实现,前端展现等等。在实际中,通过把这些模块集成在一起,构成了一个集团通用推荐系统,对外提供推服务,应用在10多个栏位,60多个场景,取得了很好的效果。本文侧重介绍了召回与排序算法相关的目前已有的一些工作与实践,下一步,计划引入更多地深度模型来处理召回与排序问题,并结合在线学习、强化学习、迁移学习等方面的进展,优化推荐的整体质量。



Tags:推荐算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
导读:本文的主题为阿里飞猪推荐算法探索实践,首先会介绍电商背景下主流推荐技术的发展,例如基于全空间的CVR预估技术的发展历程等 ( ESMM / ESM^2 / HM^3 );接着会重点结合旅行...【详细内容】
2021-10-21  Tags: 推荐算法  点击:(56)  评论:(0)  加入收藏
商品详情页是手淘内流量最大的模块之一,它加载了数十亿级商品的详细信息,是用户整个决策过程必不可少的一环。这个区块不仅要承接用户对当前商品充分感知的诉求,同时也要能肩负起其他来源导流流量的留存,最终尽可能地激活...【详细内容】
2021-08-04  Tags: 推荐算法  点击:(89)  评论:(0)  加入收藏
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  Tags: 推荐算法  点击:(121)  评论:(0)  加入收藏
导读:近年来,电商呈现内容化的趋势,以直播和短视频为首,内容化提升了用户体验,增加了平台收益。作为电商的重要流量入口,推荐算法除了应用于商品,现在也被应用于直播场景。我们将以阿里的B类电商网站1688为例,分享直播推荐相...【详细内容】
2021-04-21  Tags: 推荐算法  点击:(287)  评论:(0)  加入收藏
【写在前面】淘宝搜索引擎至今已经迭代了多轮,搜索排序也已经从最开始的统计模型升级到机器学习模型;2010年前是没有标签概念的就是基础标签这些都没有,随着算力的增强,2010年后...【详细内容】
2020-12-29  Tags: 推荐算法  点击:(222)  评论:(0)  加入收藏
指尖在抖音上划过,满屏幕的颜值少女,满屏幕的乡村野趣,满屏幕的都市传奇,满屏幕的生活乐趣。在碎片化的时间里,我们拿着手机,看着屏上的视频,充满了视觉的欢乐与笑语。手指迅速地划...【详细内容】
2020-09-28  Tags: 推荐算法  点击:(200)  评论:(0)  加入收藏
本次分享的主要内容包括以下三个方面:首先是介绍推荐业务背景,包括推荐产品形态及算法优化目标;然后是算法的演进路线;最后重点介绍在线学习是如何在饿了么推荐领域实践的。...【详细内容】
2020-09-21  Tags: 推荐算法  点击:(88)  评论:(0)  加入收藏
读者读完本文后,你会知道每类范式常用的算法有哪些、实现的思路是什么、以及常用的应用场景。本文也可以作为读者落地推荐算法到真实推荐场景的参考指南。一、推荐算法与产品...【详细内容】
2020-08-31  Tags: 推荐算法  点击:(147)  评论:(0)  加入收藏
近些年,随着深度学习理论,GPU 和 CPU 等计算机硬件,TensorFlow、Caffe、PyTorch 等算法平台的发展,深度学习算法在个性化推荐、计算机视觉、自然语言处理、语音识别等领域大放光...【详细内容】
2020-08-04  Tags: 推荐算法  点击:(53)  评论:(0)  加入收藏
今天,算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。今日头条的推荐算法,从2012年9月第一版开发运行至今,...【详细内容】
2020-06-22  Tags: 推荐算法  点击:(66)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条