美团的愿景是连接消费者和商家,而搜索在其中起着非常重要的作用。随着业务的发展,美团的商家和团购数正在飞速增长。这一背景下,搜索排序的重要性显得更加突出:排序的优化能帮助用户更便捷地找到满足其需求的商家和团购,改进用户体验,提升转化效果。 和传统网页搜索问题相比,美团的搜索排序有自身的特点——90%的交易发生在移动端。一方面,这对排序的个性化提出了更高的要求,例如在“火锅”查询下,北京五道口的火锅店A,对在五道口的用户U1来说是好的结果,对在望京的用户U2来讲不一定是好的结果;另一方面,我们由此积累了用户在客户端上丰富准确的行为,经分析获得用户的地理位置、品类和价格等偏好,进而指导个性化排序。 针对美团的O2O业务特点,我们实现了一套搜索排序技术方案,相比规则排序有百分之几十的提升。基于这一方案,我们又抽象了一套通用的O2O排序解决方案,只需1-2天就可以快速地部署到其他产品和子行业中,目前在热词、Suggestion、酒店、KTV等多个产品和子行业中应用。 我们将按线上和线下两部分分别介绍这一通用O2O排序解决方案,本文是线上篇,主要介绍在线服务框架、特征加载、在线预估等模块,下篇将会着重介绍离线流程。 排序系统为了快速有效的进行搜索算法的迭代,排序系统设计上支持灵活的A/B测试,满足准确效果追踪的需求。 美团搜索排序系统如上图所示,主要包括离线数据处理、线上服务和在线数据处理三个模块。 离线数据处理HDFS/Hive上存储了搜索展示、点击、下单和支付等日志。离线数据流程按天调度多个Map Reduce任务分析日志,相关任务包括:
在线数据处理和离线流程相对应,在线流程通过Storm/Spark Streaming等工具对实时日志流进行分析处理,产出实时特征、实时报表和监控数据,更新在线排序模型。 在线服务(Rank Service)Rank Service接到搜索请求后,会调用召回服务获取候选POI/Deal集合,根据A/B测试配置为用户分配排序策略/模型,应用策略/模型对候选集合进行排序。 下图是Rank Service内部的排序流程。
Rank Service会将展示日志记录到日志收集系统,供在线/离线处理。 A/B测试A/B测试的流量切分是在Rank Server端完成的。我们根据UUID(用户标识)将流量切分为多个桶(Bucket),每个桶对应一种排序策略,桶内流量将使用相应的策略进行排序。使用UUID进行流量切分,是为了保证用户体验的一致性。
对于不合法的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和搜索上下文四个维度。
此外,有的特征来自于几个维度之间的相互关系:用户对Deal/POI的点击和下单等行为、用户与POI的距离等是决定排序的重要因素;Query和Deal/POI的文本相关性和语义相关性是模型的关键特征。 模型Learning to Rank应用中,我们主要采用了Pointwise方法。采用用户的点击、下单和支付等行为来进行正样本的标注。从统计上看,点击、下单和支付等行为分别对应了该样本对用户需求的不同的匹配程度,因此对应的样本会被当做正样本,且赋予不断增大的权重。 线上运行着多种不同类型模型,主要包括:
对模型的评估分为离线和线上两部分。离线部分我们通过AUC(Area Under the ROC Curve)和MAP(Mean Average Precision)来评价模型,线上则通过A/B测试来检验模型的实际效果,两项手段支撑着算法不断的迭代优化。 冷启动在我们的搜索排序系统中,冷启动问题[6]表现为当新的商家、新的团购单录入或新的用户使用美团时,我们没有足够的数据用来推测用户对产品的喜好。商家冷启动是主要问题,我们通过两方面手段来进行缓解。一方面,在模型中引入了文本相关性、品类相似度、距离和品类属性等特征,确保在没有足够展示和反馈的前提下能较为准确地预测;另一方面,我们引入了Explore&Exploit机制,对新商家和团单给予适度的曝光机会,以收集反馈数据并改善预测。 Position Bias在手机端,搜索结果的展现形式是列表页,结果的展示位置会对用户行为产生很大的影响。在特征挖掘和训练数据标注当中,我们考虑了展示位置因素引入的偏差。例如CTR(click-through-rate)的统计中,我们基于Examination Model[5],去除展示位置带来的影响。 总结本文主要介绍了美团搜索排序系统线上部分的结构、算法和主要模块。在后续文章里,我们会着重介绍排序系统离线部分的工作。 一个完善的线上线下系统是排序优化得以持续进行的基础。基于业务对数据和模型上的不断挖掘是排序持续改善的动力。我们仍在探索。 参考文献
发现文章有错误、对内容有疑问,都可以关注美团技术团队微信公众号(meituantech),在后台给我们留言。我们每周会挑选出一位热心小伙伴,送上一份精美的小礼品。快来扫码关注我们吧! |
|