携程个性化推荐算法实践

2018 年 1 月 18 日 架构文摘 基础业务研发部

携程作为国内领先的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多个场景，取得了很好的效果。本文侧重介绍了召回与排序算法相关的目前已有的一些工作与实践，下一步，计划引入更多地深度模型来处理召回与排序问题，并结合在线学习、强化学习、迁移学习等方面的进展，优化推荐的整体质量。

References

[1] Koren, Yehuda,Robert Bell, and Chris Volinsky. "Matrix factorization techniques forrecommender systems." Computer 42.8 (2009).

[2] Sedhain, Suvash,et al. "Autorec: Autoencoders meet collaborative filtering." Proceedingsof the 24th International Conference on World Wide Web. ACM, 2015.

[3] Rendle, Steffen,Christoph Freudenthaler, and Lars Schmidt-Thieme. "Factorizingpersonalized markov chains for next-basket recommendation." Proceedings ofthe 19th international conference on World wide web. ACM, 2010.

[4] Dong, Xin, etal. "A Hybrid Collaborative Filtering Model with Deep Structure forRecommender Systems." AAAI. 2017.

[5] Hidasi, Balázs,et al. "Session-based recommendations with recurrent neuralnetworks." arXiv preprint arXiv:1511.06939 (2015).

[6] Zhu, Yu, et al."What to Do Next: Modeling User Behaviors by Time-LSTM." Proceedingsof the Twenty-Sixth International Joint Conference on Artificial Intelligence,IJCAI-17. 2017.

[7] Barkan, Oren,and Noam Koenigstein. "Item2vec: neural item embedding for collaborativefiltering." Machine Learning for Signal Processing (MLSP), 2016 IEEE 26thInternational Workshop on. IEEE, 2016.

[8] Wang, Hao,Naiyan Wang, and Dit-Yan Yeung. "Collaborative deep learning forrecommender systems." Proceedings of the 21th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining. ACM, 2015.

[9] Covington, Paul,Jay Adams, and Emre Sargin. "Deep neural networks for youtuberecommendations." Proceedings of the 10th ACM Conference on RecommenderSystems. ACM, 2016.

[10] Kim, Donghyun, et al. "Convolutional matrix factorization fordocument context-aware recommendation." Proceedings of the 10th ACMConference on Recommender Systems. ACM, 2016.[11] https://mli.github.io/2013/03/24/the-end-of-feature-engineering-and-linear-model/[12] Richardson, Matthew, Ewa Dominowska, and Robert Ragno."Predicting clicks: estimating the click-through rate for new ads."Proceedings of the 16th international conference on World Wide Web. ACM, 2007[13] Andrew, Galen, and Jianfeng Gao. "Scalable training of L1-regularized log-linear models." Proceedings of the 24th internationalconference on Machine learning. ACM, 2007.[14] Graepel, Thore, et al. "Web-scale bayesian click-through rateprediction for sponsored search advertising in microsoft's bing searchengine." Omnipress, 2010.

[15] McMahan, H. Brendan, et al. "Ad click prediction: a view fromthe trenches." Proceedings of the 19th ACM SIGKDD international conferenceon Knowledge discovery and data mining. ACM, 2013.

[16] Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable treeboosting system." Proceedings of the 22nd acm sigkdd internationalconference on knowledge discovery and data mining. ACM, 2016.

[17] Rendle, Steffen. "Factorization machines." Data Mining(ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

[18] Juan, Yuchin, et al. "Field-aware factorization machines forCTR prediction." Proceedings of the 10th ACM Conference on RecommenderSystems. ACM, 2016.

[19] Gai, Kun, et al. "Learning Piece-wise Linear Models fromLarge Scale Data for Ad Click Prediction." arXiv preprint arXiv:1704.05194(2017).

[20] He, Xinran, et al. "Practical lessons from predicting clickson ads at facebook." Proceedings of the Eighth International Workshop onData Mining for Online Advertising. ACM, 2014.

[21] Cheng, Heng-Tze, et al. "Wide & deep learning forrecommender systems." Proceedings of the 1st Workshop on Deep Learning forRecommender Systems. ACM, 2016.

[22] Guo, Huifeng, et al. "DeepFM: A Factorization-Machine basedNeural Network for CTR Prediction." arXiv preprint arXiv:1703.04247(2017).

[23] Zhou, Guorui, et al. "Deep Interest Network for Click-ThroughRate Prediction." arXiv preprint arXiv:1706.06978 (2017).

[24] Blondel, Mathieu, et al. "Higher-orderfactorization machines." Advances in Neural Information ProcessingSystems. 2016.

[25] http://breezedeus.github.io/2014/11/20/breezedeus-feature-hashing.html

[26] https://en.wikipedia.org/wiki/Categorical_variable

[27] https://www.zhihu.com/question/48674426

[28] 多高的AUC才算高？https://zhuanlan.zhihu.com/p/24217322