"摘要:本文介绍了美团网推荐系统的构建和优化过程中的一些做法,包括数据层、触发层、融合过滤层和排序层五个层次,采用了 HBase、Hive、storm、Spark 和机器学习等技术。两个优化亮点是将候选集进行融合与引入重排序模型。 ** 编者按:** 在用户意图明确时,我们通常用搜索引擎来解决互联网时代的信息过载问题,但 .."

美团推荐算法实践:机器学习重排序模型成亮点

本贴最后更新于 749 天前,其中的信息可能已经事过境迁

摘要:本文介绍了美团网推荐系统的构建和优化过程中的一些做法,包括数据层、触发层、融合过滤层和排序层五个层次,采用了 HBase、Hive、storm、Spark 和机器学习等技术。两个优化亮点是将候选集进行融合与引入重排序模型。

** 编者按:** 在用户意图明确时,我们通常用搜索引擎来解决互联网时代的信息过载问题,但当用户的意图不明确或者很难用清晰的语义表达,搜索引擎就无能为力。此时,借助推荐系统通过用户行为的分析理解其意图,为其推送个性化的结果,便成为一种更好的选择。美团作为国内发展较快的 O2O 网站,有着大量的用户和丰富的用户行为,这些为推荐系统的应用和优化提供了很好的条件。本文由美团技术团队成员撰写,介绍其推荐系统的构建和优化过程中的一些做法。

原文地址:http://tech.meituan.com/mt-recommend-practice.html

框架

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(16).jpg)

从框架的角度看,推荐系统基本可以分为数据层、触发层、融合过滤层和排序层。数据层包括数据生成和数据存储,主要是利用各种数据处理工具对原始日志进行清洗,处理成格式化的数据,落地到不同类型的存储系统中,供下游的算法和模型使用。候选集触发层主要是从用户的历史行为、实时行为、地理位置等角度利用各种触发策略产生推荐的候选集。候选集融合和过滤层有两个功能,一是对出发层产生的不同候选集进行融合,提高推荐策略的覆盖度和精度;另外还要承担一定的过滤职责,从产品、运营的角度确定一些人工规则,过滤掉不符合条件的 item。排序层主要是利用机器学习的模型对触发层筛选出来的候选集进行重排序。

同时,对与候选集触发和重排序两层而言,为了效果迭代是需要频繁修改的两层,因此需要支持 ABtest。为了支持高效率的迭代,我们对候选集触发和重排序两层进行了解耦,这两层的结果是正交的,因此可以分别进行对比试验,不会相互影响。同时在每一层的内部,我们会根据用户将流量划分为多份,支持多个策略同时在线对比。

数据应用

数据乃算法、模型之本。美团作为一个交易平台,同时具有快速增长的用户量,因此产生了海量丰富的用户行为数据。当然,不同类型的数据的价值和反映的用户意图的强弱也有所不同。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(17).jpg)

  1. 用户主动行为数据记录了用户在美团平台上不同的环节的各种行为,这些行为一方面用于候选集触发算法(在下一部分介绍)中的离线计算(主要是浏览、下单),另外一方面,这些行为代表的意图的强弱不同,因此在训练重排序模型时可以针对不同的行为设定不同的回归目标值,以更细地刻画用户的行为强弱程度。此外,用户对 deal 的这些行为还可以作为重排序模型的交叉特征,用于模型的离线训练和在线预测。负反馈数据反映了当前的结果可能在某些方面不能满足用户的需求,因此在后续的候选集触发过程中需要考虑对特定的因素进行过滤或者降权,降低负面因素再次出现的几率,提高用户体验;同时在重排序的模型训练中,负反馈数据可以作为不可多得的负例参与模型训练,这些负例要比那些展示后未点击、未下单的样本显著的多。用户画像是刻画用户属性的基础数据,其中有些是直接获取的原始数据,有些是经过挖掘的二次加工数据,这些属性一方面可以用于候选集触发过程中对 deal 进行加权或降权,另外一方面可以作为重排序模型中的用户维度特征。通过对 UGC 数据的挖掘可以提取出一些关键词,然后使用这些关键词给 deal 打标签,用于 deal 的个性化展示。

策略触发

上文中我们提到了数据的重要性,但是数据的落脚点还是算法和模型。单纯的数据只是一些字节的堆积,我们必须通过对数据的清洗去除数据中的噪声,然后通过算法和模型学习其中的规律,才能将数据的价值最大化。在本节中,将介绍推荐候选集触发过程中用到的相关算法。

1. 协同过滤

提到推荐,就不得不说协同过滤,它几乎在每一个推荐系统中都会用到。基本的算法非常简单,但是要获得更好的效果,往往需要根据具体的业务做一些差异化的处理。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(18).jpg)

下表表示了 Event A 和 Event B 之间的相互关系,其中:

k11 :Event A 和 Event B 共现的次数
k12 :Event B 发生,Event A 未发生的次数
k21 :Event A 发生,Event B 未发生的次数
k22 :Event A 和 Event B 都不发生的次数

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(19).jpg)

则 logLikelihoodRatio=2 * (matrixEntropy – rowEntropy – columnEntropy)

其中

rowEntropy = entropy(k11, k12) + entropy(k21, k22)
columnEntropy = entropy(k11, k21) + entropy(k12, k22)
matrixEntropy = entropy(k11, k12, k21, k22)

(entropy 为几个元素组成的系统的香农熵)

2. location-based

对于移动设备而言,与 PC 端最大的区别之一是移动设备的位置是经常发生变化的。不同的地理位置反映了不同的用户场景,在具体的业务中可以充分利用用户所处的地理位置。在推荐的候选集触发中,我们也会根据用户的实时地理位置、工作地、居住地等地理位置触发相应的策略。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(20).jpg)

区域消费热单

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(21).jpg)

区域购买热单

3. query-based

搜索是一种强用户意图,比较明确的反应了用户的意愿,但是在很多情况下,因为各种各样的原因,没有形成最终的转换。尽管如此,我们认为,这种情景还是代表了一定的用户意愿,可以加以利用。具体做法如下:

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(22).jpg)

4. graph-based

对于协同过滤而言,user 之间或者 deal 之间的图距离是两跳,对于更远距离的关系则不能考虑在内。而图算法可以打破这一限制,将 user 与 deal 的关系视作一个二部图,相互间的关系可以在图上传播。Simrank[2] 是一种衡量对等实体相似度的图算法。它的基本思想是,如果两个实体与另外的相似实体有相关关系,那它们也是相似的,即相似性是可以传播的。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(24).jpg)

5. 实时用户行为

目前我们的业务会产生包括搜索、筛选、收藏、浏览、下单等丰富的用户行为,这些是我们进行效果优化的重要基础。我们当然希望每一个用户行为流都能到达转化的环节,但是事实上远非这样。

当用户产生了下单行为上游的某些行为时,会有相当一部分因为各种原因使行为流没有形成转化。但是,用户的这些上游行为对我们而言是非常重要的先验知识。很多情况下,用户当时没有转化并不代表用户对当前的 item 不感兴趣。当用户再次到达我们的推荐展位时,我们根据用户之前产生的先验行为理解并识别用户的真正意图,将符合用户意图的相关 deal 再次展现给用户,引导用户沿着行为流向下游行进,最终达到下单这个终极目标。

目前引入的实时用户行为包括:实时浏览、实时收藏。

6. 替补策略

虽然我们有一系列基于用户历史行为的候选集触发算法,但对于部分新用户或者历史行为不太丰富的用户,上述算法触发的候选集太小,因此需要使用一些替补策略进行填充。

子策略融合

为了结合不同触发算法的优点,同时提高候选集的多样性和覆盖率,需要将不同的触发算法融合在一起。常见的融合的方法有以下几种:

目前我们使用的方法集成了调制和分级两种融合方法,不同的算法根据历史效果表现给定不同的候选集构成比例,同时优先采用效果好的算法触发,如果候选集不够大,再采用效果次之的算法触发,依此类推。

候选集重排序

如上所述,对于不同算法触发出来的候选集,只是根据算法的历史效果决定算法产生的 item 的位置显得有些简单粗暴,同时,在每个算法的内部,不同 item 的顺序也只是简单的由一个或者几个因素决定,这些排序的方法只能用于第一步的初选过程,最终的排序结果需要借助机器学习的方法,使用相关的排序模型,综合多方面的因素来确定。

1. 模型

非线性模型能较好的捕捉特征中的非线性关系,但训练和预测的代价相对线性模型要高一些,这也导致了非线性模型的更新周期相对要长。反之,线性模型对特征的处理要求比较高,需要凭借领域知识和经验人工对特征做一些先期处理,但因为线性模型简单,在训练和预测时效率较高。因此在更新周期上也可以做的更短,还可以结合业务做一些在线学习的尝试。在我们的实践中,非线性模型和线性模型都有应用。

目前我们主要采用了非线性的树模型 Additive Groves[4](简称 AG),相对于线性模型,非线性模型可以更好的处理特征中的非线性关系,不必像线性模型那样在特征处理和特征组合上花费比较大的精力。AG 是一个加性模型,由很多个 Grove 组成,不同的 Grove 之间进行 bagging 得出最后的预测结果,由此可以减小过拟合的影响。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(25).jpg)

每一个 Grove 有多棵树组成,在训练时每棵树的拟合目标为真实值与其他树预测结果之和之间的残差。当达到给定数目的树时,重新训练的树会逐棵替代以前的树。经过多次迭代后,达到收敛。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(26).jpg)

目前应用比较多的线性模型非 Logistic Regression 莫属了。为了能实时捕捉数据分布的变化,我们引入了 online learning,接入实时数据流,使用 google 提出的 FTRL[5] 方法对模型进行在线更新。

![](file:///D:/Users/c_jia/AppData/Local/Temp/enhtmlclip/Image(27).jpg)

主要的步骤如下:

2. 数据

3. 特征

在我们目前的重排序模型中,大概分为以下几类特征:

对于非线性模型,上述特征可以直接使用;而对于线性模型,则需要对特征值做一些分桶、归一化等处理,使特征值成为 0~1 之间的连续值或 01 二值。

总结

以数据为基础,用算法去雕琢,只有将二者有机结合,才会带来效果的提升。对我们而言,以下两个节点是我们优化过程中的里程碑:

  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    45 引用 • 19 回帖
回帖   
请输入回帖内容...