背景

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

数据清洗

数据清洗的主要工作是为离线模型训练准备标注数据，同时洗掉不合法数据。数据清洗的数据源主要有团购的曝光、点击和下单。
整个数据清洗的流程如下：

• 序列化
  曝光、点击和下单数据从Hive表中读取，采用schema的处理方式，可以直接根据日志字段名来抽取相应的字段，不受日志字段增加或者减少的影响。
  曝光日志存储了一次用户行为的详细信息，包括城市、地理位置、筛选条件及一些行为特征；点击日志主要记录了用户点击的POIID、点击时间；下单日志记录了用户下单的POIID、下单时间和下单的金额。数据清洗模块根据配置文件从数据源中抽取需要的字段，进行序列化（Serialization）之后存储在HDFS上。
  序列化的过程中，如果日志字段不合法或者单一用户曝光、点击或下单超出设定的阈值，相关日志都会被清洗掉，避免数据对模型训练造成影响。
• 数据标注
  数据序列化之后在HDFS上保存三份文本文件，分别是曝光（Impression）、点击（Click）和下单（Order）。数据标注模块根据globalid（一次搜索的全局唯一标示，类似于sessionid）和相应的团购id为key，将曝光、点击和下单关联起来，最终生成一份标注好是否被点击、下单、支付的标注数据。同时这份标注数据携带了本次展现的详细特征信息。
  数据标注通过一次Map/Reduce来完成。
  Map阶段：Map的输入为曝光、点击和下单三种HDFS数据。 用三个Mapper分别处理三种日志。数据分发的key为globalid。其中，如果点击和下单数据中的globalid字段为空（""），则丢弃该条日志（因为globalid为空无法和曝光日志join，会出现误标注）。
  Reduce阶段：Reduce接收的key为globalid, values为具有相同globalid的曝光、点击、下单数据List，遍历该List, 如果
  日志类型为曝光日志，则标记该globalid对应的曝光日志存在（imp_exist=true）。
  日志类型为点击日志，则将曝光日志的clicked字段置为1。
  日志类型为下单日志，则将曝光日志的ordered字段置为1。
  日志类型为下单日志，如果pay_account字段>0， 则将曝光日志的paid字段置为1。
  遍历List之后，如果imp_exist == true, 则将标注好的数据写入HDFS， 否则丢弃。
  数据标注的流程图如下：
  

特征矩阵

特征矩阵的作用是提供丰富的特征集合，以方便在线和离线特征调研使用。

特征矩阵的生成

特征矩阵的生成框架为：

下面我们来详细说明一下流程。
基础特征按来源可分为三部分：
1、Hive表：有一些基础特征存储在Hive标注，如POI的名字、品类、团购数等。
2、离线计算：一些特征需要积累一段时间才能统计，如POI的点击率、销量等，这部分通过积累历史数据，然后经过Map/Reduce处理得到。
3、HDFS：特征矩阵可能融合第三方服务的特征，一般第三方服务将产生的特征按照约定的格式存储在HDFS上。
数据源统一格式为： poiid/dealid/bizareaid '\t' name1:value1'\t' name2:value2...
特征合并模块，将所有来源合并为一个大文件，通过feature conf配置的特征和特征顺序，将特征序列化，然后写入Hive表。
特征监控模块每天监控特征的分布等是否异常。 特征矩阵的特征每日更新。
添加新的特征来源，只需要按照约定的格式生成数据源，配置路径，可自动添加。
添加新特征，在feature conf文件末尾添加相应的特征名，特征名字和数据源中的特征name保持一致，最后修改相应的特征Hive表结构。

特征矩阵的使用

特征矩阵的使用框架为：

我们来详细说明一下流程。
其中特征矩阵既提供在线的特征仓库，又可提供离线的特征调研。线上服务需要大量的特征来对POI/DEAL质量打分，特征分散会造成服务取用特征很耗时，特征矩阵将特征整合，很好的解决了特征耗时的问题。一般调研一个新特征需要积累一段时间的数据，将特征放入特征矩阵，
然后和已有的数据进行融合，可方便的构造包含新特征的训练数据。下面我们分别来看一下在线、离线和特征融合的流程。

• 在线使用
  在线方面的使用主要是方便特征的获取，将线上需要的特征纳入特征矩阵统一管理，通过配置文件读取特征矩阵的特征，封装成Proto Buffers写入Medis（美团自主构建的Redis集群，支持分布式和容错），通过Medis key批量读取该key对应的特征，减少读取Medis的次数，从而缩减特征获取的时间，提高系统的性能。
  特征矩阵在线使用框架如下：
  

流程说明：

1. 序列化模块通过特征配置文件从特征矩阵抽取需要的特征，调用protoBuffer Lib将特征封装成protoBuffer的格式，写入Medis。
2. 线上通过featureLoader服务从Medis读取数据，然后通过protoBufferLib反序列化数据，取到相应的特征值。

• 离线使用
  离线方面的使用主要是方便调研新特征。如果从线上获取新特征，由于需要积累训练数据，特征调研的周期会变长；而如果将待调研的特征纳入特征矩阵中，可以很方便地通过离线的方法调研特征的有效性，极大的缩短了特征调研的周期，提高开发效率和模型迭代的速度。
  特征矩阵离线使用框架如下：
  

其中，从特征矩阵取出待调研的新特征，格式化为 joinKey '\t' FeatureName:FeatureValue， 例如 12345 '\t' CTR:0.123，joinkey为poiid, 新特征为CTR，特征值为0.123。格式化后的新特征文件和标注好的rerank日志作为输入，经过Map/Reduce处理生成新的标注日志，用于模型训练。

• 特征融合
  特征融合作用于离线特征调研，上篇我们提到数据标准会输出拥有丰富特征的标注日志，特征融合的目的在于将待调研的新特征通过某一个joinkey 合并到在线特征列表中，从而在模型训练中使用该特征。
  特征融合的框架：
  

流程说明： 特征融合模块可以指定任意一个或者多个join key，将离线特征加入在线特征列表。

监控系统

监控系统的目的是确保在线和离线任务的正常运行。监控系统按照作用范围的不同又分为线上监控和离线监控。

• 线上监控
  线上监控主要是监测收集的在线特征日志是否正常，线上特征监控主要检测特征的覆盖度、阈值范围、分布异常三方面。
  三方面的监控主要分以下几个场景：
  覆盖度：监控特征的数据源是否存在或者有数据丢失。
  阈值范围：监控特征的阈值是否符合预期，防止因为生成特征的算法改变或者在线计算方法的不同等因素造成特征的最大值或者最小值发生比较明显的变化，导致特征不可用。
  分布异常：监控特征值的分布是否符合预期，主要防止因为获取不到特征，使得特征都使用了默认值，而又没有及时发现，导致线上模型预估出现偏差。分布异常主要用到了卡方距离[ 3]。
  特征覆盖度监控效果图：
  下图是用户到POI距离的覆盖度监控。从图中可以直观的看出，该特征的覆盖度约为75%，也即只有75%的用户能得到距离特征，另外25%可能没有开手机定位服务或者得不到POI的坐标。75%的覆盖度是一个比较稳定的指标，如果覆盖度变的很高或者很低都说明我们的系统出现了问题，而我们的监控系统能及时发现这种问题。
  

• 离线监控
  离线监控主要检测两方面：1、离线任务是否按时完成及生成的数据是否正确。 2、特征矩阵特征的有效性。
  当离线定时任务多达数十个的时候，很难每天去逐个检查每个任务是否如期完成，这时候离线任务监控的重要性就凸显出来。当前离线监控可以根据配置文件，监控需要关注的任务，以及这些任务生成的数据是否正常。如果不正常则发出报警给任务负责人，达到任务失败能够及时处理的目的。
  特征矩阵监控的目的与在线特征的监控目的一样，监控指标也相同，所不同的是因为监控数据的获取不同，监控实现也不尽相同，这里不再赘述。

模型调研

模型训练

模型训练框架支持多种模型的训练，将训练数据格式化为模型需要的输入格式。修改模型训练的配置文件，就可以使用该框架训练模型了。
模型训练框架：

其中，顶层是训练数据和测试数据的输入层，该层是原始训练和测试数据。
中间是模型训练的框架，框架支持多个配置项，包括配置模型算法、相应的参数、数据源的输入及模型的输出等。
底层是多种模型的实现，算法之前相互独立，每种算法封装成独立的jar，提供给模型训练框架使用，目前支持的算法包括GBDT[ 4]、FTRL[ 5]。
为了实现模型的快速迭代，模型训练支持在Spark上运行。

效果评估

模型的效果评估主要是对比新模型和老模型的效果，以评估结果来决定是否更新线上模型。
我们的系统支持两种效果指标的评估，一种是AUC[ 1]，另一种是MAP。

MAP(Mean Average Precision)[ 2]是一种对搜索排序结果好坏评估的指标。

• Prec@K 的定义： 设定阈值K，计算排序结果topK的相关度。
  
  注：绿色表示搜索结果与搜索词相关，红色表示不相关。
• AP（Average Precision）的定义： Average Precision = average of Prec@K
  

• AP作为排序好坏的直观理解
  
  灰色表示与搜索相关的结果，在团购中表示被点击的DEAL，从召回结果看Ranking#1要好于Ranking#2，反映在MAP指标上，Ranking#1的MAP值大于Ranking#2的MAP值。
  所以可以简单地使用AP值来衡量模型排序的好坏。

• MAP的计算
  
  对于多个query的搜索结果，MAP为这些搜索结果AP的均值。
  实验结果表明MAP作为排序指标，对模型好坏的评估起到很好的指导作用。
  在AUC的近似计算方法中，主要考虑有多少对正负样本组合中正样本的得分大于负样本的得分，与正样本在排序中的具体位置没有绝对的关系。当正负样本的分布变化，如某一小部分正样本得分变大，大部分正样本得分变小，那么最终计算的AUC值可能没有发生变化，但排序的结果却发生了很大变化（大部分用户感兴趣的单子排在了后边）。
  因此AUC指标没法直观评估人对排序好坏的感受。

总结

本文重点介绍了美团排序系统离线各个部分的工作。离线工作在O2O排序服务中占据着举足轻重的地位，为线上排序效果的提升提供了强有力的支持。为了更好的优化我们的服务，我们仍在探索中不断前进。

参考

1. Approximating area under the curve . Khan Academy.
2. Information retrieval . Wikipedia.
3. Pearson's chi-squared test . Wikipedia.
4. Friedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189-1232.
5. 在线学习算法FTRL. CSDN blog.