美团O2O排序解决方案——线上篇

标签: 美团 o2o 排序 | 发表时间:2015-11-17 01:00 | 作者:美团技术团队
出处:http://tech.meituan.com/

美团的愿景是连接消费者和商家,而搜索在其中起着非常重要的作用。随着业务的发展,美团的商家和团购数正在飞速增长。这一背景下,搜索排序的重要性显得更加突出:排序的优化能帮助用户更便捷地找到满足其需求的商家和团购,改进用户体验,提升转化效果。

和传统网页搜索问题相比,美团的搜索排序有自身的特点——90%的交易发生在移动端。一方面,这对排序的个性化提出了更高的要求,例如在“火锅”查询下,北京五道口的火锅店A,对在五道口的用户U1来说是好的结果,对在望京的用户U2来讲不一定是好的结果;另一方面,我们由此积累了用户在客户端上丰富准确的行为,经分析获得用户的地理位置、品类和价格等偏好,进而指导个性化排序。

针对美团的O2O业务特点,我们实现了一套搜索排序技术方案,相比规则排序有百分之几十的提升。基于这一方案,我们又抽象了一套通用的O2O排序解决方案,只需1-2天就可以快速地部署到其他产品和子行业中,目前在热词、Suggestion、酒店、KTV等多个产品和子行业中应用。

我们将按线上和线下两部分分别介绍这一通用O2O排序解决方案,本文是线上篇,主要介绍在线服务框架、特征加载、在线预估等模块,下篇将会着重介绍离线流程。

排序系统

为了快速有效的进行搜索算法的迭代,排序系统设计上支持灵活的A/B测试,满足准确效果追踪的需求。

搜索排序系统

美团搜索排序系统如上图所示,主要包括离线数据处理、线上服务和在线数据处理三个模块。

离线数据处理

HDFS/Hive上存储了搜索展示、点击、下单和支付等日志。离线数据流程按天调度多个Map Reduce任务分析日志,相关任务包括:

  • 离线特征挖掘
    产出Deal(团购单)/POI(商家)、用户和Query等维度的特征供排序模型使用。

  • 数据清洗标注 & 模型训练
    数据清洗去掉爬虫、作弊等引入的脏数据;清洗完的数据经过标注后用作模型训练。

  • 效果报表生成
    统计生成算法效果指标,指导排序改进。

  • 特征监控
    特征作为排序模型的输入是排序系统的基础。特征的错误异常变动会直接影响排序的效果。特征监控主要监控特征覆盖率和取值分布,帮我们及时发现相关问题。

在线数据处理

和离线流程相对应,在线流程通过Storm/Spark Streaming等工具对实时日志流进行分析处理,产出实时特征、实时报表和监控数据,更新在线排序模型。

在线服务(Rank Service)

Rank Service接到搜索请求后,会调用召回服务获取候选POI/Deal集合,根据A/B测试配置为用户分配排序策略/模型,应用策略/模型对候选集合进行排序。

下图是Rank Service内部的排序流程。

排序内部流程

  • L1 粗粒度排序(快速)
    使用较少的特征、简单的模型或规则对候选集进行粗粒度排序。

  • L2 细粒度排序(较慢)
    对L1排序结果的前N个进行细粒度排序。这一层会从特征库加载特征(通过FeatureLoader),应用模型(A/B测试配置分配)进行排序。

  • L3 业务规则干预
    在L2排序的基础上,应用业务规则/人工干预对排序进行适当调整。

Rank Service会将展示日志记录到日志收集系统,供在线/离线处理。

A/B测试

A/B测试的流量切分是在Rank Server端完成的。我们根据UUID(用户标识)将流量切分为多个桶(Bucket),每个桶对应一种排序策略,桶内流量将使用相应的策略进行排序。使用UUID进行流量切分,是为了保证用户体验的一致性。
bucket testing
下面是A/B测试配置的一个简单示例。

  {
    "search": {
        "NumberOfBuckets": 100,
        "DefaultStrategy": "Base",
        "Segments": [
            {
                "BeginBucket": 0,
                "EndBucket": 24,
                "WhiteList": [123],
                "Strategy": "Algo-1"
            },
            {
                "BeginBucket": 25,
                "EndBucket": 49,
                "WhiteList": [],
                "Strategy": "Algo-2"
            }
        ]
    }
}

对于不合法的UUID,每次请求会随机分配一个桶,以保证效果对比不受影响。白名单(White List)机制能保证配置用户使用给定的策略,以辅助相关的测试。

除了A/B测试之外,我们还应用了Interleaving[ 7]方法,用于比较两种排序算法。相较于A/B测试,Interleaving方法对排序算法更灵敏[ 9],能通过更少的样本来比较两种排序算法之间的优劣。Interleaving方法使用较小流量帮助我们快速淘汰较差算法,提高策略迭代效率。

特征加载

搜索排序服务涉及多种类型的 特征,特征获取和计算是Rank Service响应速度的瓶颈。我们设计了FeatureLoader模块,根据特征依赖关系,并行地获取和计算特征,有效地减少了特征加载时间。实际业务中,并行特征加载平均响应时间比串行特征加载快约20毫秒。

特征类型

FeatureLoader的实现中我们使用了Akka[ 8]。如上图所示,特征获取和计算的被抽象和封装为了若干个Akka actor,由Akka调度、并行执行。

特征和模型

美团从2013年9月开始在搜索排序上应用机器学习方法(Learning to Rank[ 1]),并且取得很大的收益。这得益于准确的数据标注:用户的点击下单支付等行为能有效地反映其偏好。通过在特征挖掘和模型优化两方面的工作,我们不断地优化搜索排序。下面将介绍我们在特征使用、数据标注、排序算法、Position Bias处理和冷启动问题缓解等方面的工作。

特征

特征类型

从美团业务出发,特征选取着眼于用户、Query、Deal/POI和搜索上下文四个维度。

  • 用户维度
    包括挖掘得到的品类偏好、消费水平和地理位置等。

  • Query维度
    包括Query长度、历史点击率、转化率和类型(商家词/品类词/地标词)等。

  • Deal/POI维度
    包括Deal/POI销量、价格、评价、折扣率、品类和历史转化率等。

  • 上下文维度
    包括时间、搜索入口等。

此外,有的特征来自于几个维度之间的相互关系:用户对Deal/POI的点击和下单等行为、用户与POI的距离等是决定排序的重要因素;Query和Deal/POI的文本相关性和语义相关性是模型的关键特征。

模型

Learning to Rank应用中,我们主要采用了Pointwise方法。采用用户的点击、下单和支付等行为来进行正样本的标注。从统计上看,点击、下单和支付等行为分别对应了该样本对用户需求的不同的匹配程度,因此对应的样本会被当做正样本,且赋予不断增大的权重。

线上运行着多种不同类型模型,主要包括:

  • Gradient boosting decision/regression tree(GBDT/GBRT)[ 2]
    GBDT是LTR中应用较多的非线性模型。我们开发了基于Spark的GBDT工具,树拟合梯度的时候运用了并行方法,缩短训练时间。GBDT的树被设计为三叉树,作为一种处理特征缺失的方法。
    三叉树
    选择不同的损失函数,boosting tree方法可以处理回归问题和分类问题。应用中,我们选用了效果更好的logistic likelihood loss,将问题建模为二分类问题。

  • Logistic Regression(LR)
    参考Facebook的paper[ 3],我们利用GBDT进行部分LR特征的构建。用FTRL[ 4]算法来在线训练LR模型。

对模型的评估分为离线和线上两部分。离线部分我们通过AUC(Area Under the ROC Curve)和MAP(Mean Average Precision)来评价模型,线上则通过A/B测试来检验模型的实际效果,两项手段支撑着算法不断的迭代优化。

冷启动

在我们的搜索排序系统中,冷启动问题[ 6]表现为当新的商家、新的团购单录入或新的用户使用美团时,我们没有足够的数据用来推测用户对产品的喜好。商家冷启动是主要问题,我们通过两方面手段来进行缓解。一方面,在模型中引入了文本相关性、品类相似度、距离和品类属性等特征,确保在没有足够展示和反馈的前提下能较为准确地预测;另一方面,我们引入了Explore&Exploit机制,对新商家和团单给予适度的曝光机会,以收集反馈数据并改善预测。

Position Bias

在手机端,搜索结果的展现形式是列表页,结果的展示位置会对用户行为产生很大的影响。在特征挖掘和训练数据标注当中,我们考虑了展示位置因素引入的偏差。例如CTR(click-through-rate)的统计中,我们基于Examination Model[ 5],去除展示位置带来的影响。

总结

本文主要介绍了美团搜索排序系统线上部分的结构、算法和主要模块。在后续文章里,我们会着重介绍排序系统离线部分的工作。

一个完善的线上线下系统是排序优化得以持续进行的基础。基于业务对数据和模型上的不断挖掘是排序持续改善的动力。我们仍在探索。

参考文献

  1. Learning To Rank. Wikipedia
  2. Friedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189-1232.
  3. He, X., Pan, J., Jin, O., Xu, T., Liu, B., Xu, T., ... & Candela, J. Q. (2014, August). Practical lessons from predicting clicks on ads at facebook. In Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1-9). ACM.
  4. McMahan, H. B., Holt, G., Sculley, D., Young, M., Ebner, D., Grady, J., ... & Kubica, J. (2013, August). Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1222-1230). ACM.
  5. Craswell, N., Zoeter, O., Taylor, M., & Ramsey, B. (2008, February). An experimental comparison of click position-bias models. In Proceedings of the 2008 International Conference on Web Search and Data Mining (pp. 87-94). ACM.
  6. Cold Start. Wikipedia
  7. Chapelle, O., Joachims, T., Radlinski, F., & Yue, Y. (2012). Large-scale validation and analysis of interleaved search evaluation. ACM Transactions on Information Systems (TOIS), 30(1), 6.
  8. Akka: http://akka.io
  9. Radlinski, F., & Craswell, N. (2010, July). Comparing the sensitivity of information retrieval metrics. In Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval (pp. 667-674). ACM.

相关 [美团 o2o 排序] 推荐:

美团O2O排序解决方案——线上篇

- - 美团技术团队
美团的愿景是连接消费者和商家,而搜索在其中起着非常重要的作用. 随着业务的发展,美团的商家和团购数正在飞速增长. 这一背景下,搜索排序的重要性显得更加突出:排序的优化能帮助用户更便捷地找到满足其需求的商家和团购,改进用户体验,提升转化效果. 和传统网页搜索问题相比,美团的搜索排序有自身的特点——90%的交易发生在移动端.

美团O2O排序解决方案——线下篇

- - 美团技术团队
针对美团90%的交易发生在移动端的业务特点,我们实现了一套适用于O2O业务的搜索排序技术方案,已在许多产品和子行业中得到应用. 在之前的 线上篇中,我们已经介绍了服务的框架、排序算法等. 本文为线下篇,主要讲述数据清洗、特征矩阵、监控系统、模型训练和效果评估等模块. 数据清洗的主要工作是为离线模型训练准备标注数据,同时洗掉不合法数据.

O2O 的起点

- - 极客公园-GeekPark
[核心提示]O2O在2013年,会迎来怎样的爆发. 说起 2013 年移动互联网的爆发点, O2O 应该能排上前列,毕竟包括三巨头在内的众多互联网玩家,已经瞄准了这个领域,开展进行战略布局. 很多人预测,在 淘宝十年之后,将会出现有一个颠覆性的变革,让传统领域的商家们再一次融入到互联网的大潮中.

电子商务下一座金矿:O2O

- 的鸟 - 互联网的那点事
B2C、C2C这些概念相信大家已经不陌生了,从1999年到现在我们已经看到,电子商务已经改变了大众的生活方式. 说到大众的生活,作为C端,更多的是在网上购买商品,然后B端或者店主把商品塞到箱子里,通过物流公司送到消费者面前. 这种电子商务的模式经历了12年的变迁使得市场不断的细分:从综合型商城(淘宝为代表)到百货商店(当当、卓越)再到垂直领域(红孩子、七彩谷)接着进入轻型品牌店(PPG、凡客),用户的选择越来越趋于个性化,不再是一家独大的局面.

腾讯O2O,动了谁的地盘?

- - 派代网 - 资讯
在很多人看来,O2O(线上到线下)领域是诞生下一波千亿市值大公司所在. 相关报道称,2010年—2011年11月,共有64家O2O企业获得风险投资的青睐,2011年前11个月,在O2O市场的投资金额近70亿元人民币. 此外,2011年中国O2O市场规模为562.3亿元,预计2012年将达到986.8亿元,增长率为75.5%.

一家海鲜排档的O2O尝试

- - i天下网商
但现实社会中,很多实际因素的制约反而导致“过程”的难度远远大于“目的”. 开一家饭馆最耗费精力的可能并非找一个好厨师,维持店租、发放广告、进销存管理乃至客源维护,往往占有了更多的精力. 这其中,很大一部分是基于“注意力”与“数据”的管理. 这两点正是计算机与互联网的优势所在. 当传统商业与互联网结合,会发生什么.

被忽视的社区服务O2O

- - 钛媒体TMTpost—把脉科技资本论
上周撰写了一篇 《O2O. 》的文章,之后又与不少O2O从业者进行了交流,其中有一家北京的物业公司在从事的O2O项目让我很感兴趣. 在O2O大行其道之时,这家物业公司也认识到O2O是一次机遇,准备为其服务的社区提供O2O服务. 》这篇文章中,我整理了过去一年比较主流的、热门的、大家熟知的六种O2O模式,分别是团购、优惠券、微信、支付宝、线上线下结合、万达电商.

O2O供应链系统架构设计

- - 美团技术团队
本文是美团技术沙龙第一期, O2O技术架构与实践上的分享内容. 请在微信搜索“美团技术团队”关注我们的公众账号,了解更多活动信息. 英国知名供应链专家Martin Christopher曾经说过一句非常深刻的话:“21世纪的竞争不是企业和企业之间的竞争,而是供应链和供应链之间的竞争. 在风云变幻、寡头纷争的O2O战场,美团屡出重拳并步步为营,战绩不俗.

什么是O2O商业模式,6个很好的O2O模式解析

- 峄峰 - FeedzShare
来自: 窝窝Web2.0博客 - FeedzShare  . 发布时间:2011年10月05日,  已有 2 人推荐. 所谓O2O就是online to offline,也就是说将线下商务的机会与互联网结合在了一起,让互联网成为线下交易的前台. 这样线下服务就可以用线上来揽客,消费者可以用线上来筛选服务,还有成交可以在线结算,很快达到规模.