推荐系统并不是新鲜的事物，在很久之前就存在，但是推荐系统真正进入人们的视野，并且作为一个重要的模块存在于各个互联网公司，还是近几年的事情。
随着互联网的深入发展，越来越多的信息在互联网上传播，产生了严重的信息过载。如果不采用一定的手段，用户很难从如此多的信息流中找到对自己有价值的信息。
解决信息过载有几种手段：一种是搜索，当用户有了明确的信息需求意图后，将意图转换为几个简短的词或者短语的组合（即query），然后将这些词或短语组合提交到相应的搜索引擎，再由搜索引擎在海量的信息库中检索出与query相关的信息返回给用户；另外一种是推荐，很多时候用户的意图并不是很明确，或者很难用清晰的语义表达，有时甚至连用户自己都不清楚自己的需求，这种情况下搜索就显得捉襟见肘了。尤其是近些年来，随着电子商务的兴起，用户并非一定是带着明确的购买意图去浏览，很多时候是去“逛”的，这种情景下解决信息过载，理解用户意图，为用户推送个性化的结果，推荐系统便是一种比较好的选择。
美团作为国内发展较快的o2o网站，有着大量的用户和丰富的用户行为，这些为推荐系统的应用和优化提供了不可或缺的条件，接下来介绍我们在推荐系统的构建和优化过程中的一些做法，与大家共享。
从框架的角度看，推荐系统基本可以分为数据层、触发层、融合过滤层和排序层。数据层包括数据生成和数据存储，主要是利用各种数据处理工具对原始日志进行清洗，处理成格式化的数据，落地到不同类型的存储系统中，供下游的算法和模型使用。候选集触发层主要是从用户的历史行为、实时行为、地理位置等角度利用各种触发策略产生推荐的候选集。候选集融合和过滤层有两个功能，一是对出发层产生的不同候选集进行融合，提高推荐策略的覆盖度和精度；另外还要承担一定的过滤职责，从产品、运营的角度确定一些人工规则，过滤掉不符合条件的item。排序层主要是利用机器学习的模型对触发层筛选出来的候选集进行重排序。
同时，对与候选集触发和重排序两层而言，为了效果迭代是需要频繁修改的两层，因此需要支持ABtest。为了支持高效率的迭代，我们对候选集触发和重排序两层进行了解耦，这两层的结果是正交的，因此可以分别进行对比试验，不会相互影响。同时在每一层的内部，我们会根据用户将流量划分为多份，支持多个策略同时在线对比。
数据乃算法、模型之本。美团作为一个交易平台，同时具有快速增长的用户量，因此产生了海量丰富的用户行为数据。当然，不同类型的数据的价值和反映的用户意图的强弱也有所不同。
| 行为类别 | 行为详情 |
|---|---|
| 主动行为数据 | 搜索、筛选、点击、收藏、下单、支付、评分 |
| UGC | 文本评价、上传图片 |
| 负反馈数据 | 左滑删除、取消收藏、取消订单、退款、负评、低评 |
| 用户画像 | 用户人口属性、美团DNA、品类偏好、消费水平、工作地与居住地 |
上文中我们提到了数据的重要性，但是数据的落脚点还是算法和模型。单纯的数据只是一些字节的堆积，我们必须通过对数据的清洗去除数据中的噪声，然后通过算法和模型学习其中的规律，才能将数据的价值最大化。在本节中，将介绍推荐候选集触发过程中用到的相关算法。
提到推荐，就不得不说协同过滤，它几乎在每一个推荐系统中都会用到。基本的算法非常简单，但是要获得更好的效果，往往需要根据具体的业务做一些差异化的处理。
清除作弊、刷单、代购等噪声数据。这些数据的存在会严重影响算法的效果，因此要在第一步的数据清洗中就将这些数据剔除。
合理选取训练数据。选取的训练数据的时间窗口不宜过长，当然也不能过短。具体的窗口期数值需要经过多次的实验来确定。同时可以考虑引入时间衰减，因为近期的用户行为更能反映用户接下来的行为动作。
user-based与item-based相结合。
| 群体/个体 | 计算代价 | 适用场景 | 冷启动 | 可解释性 | 实时性
---|----|----|----|----|----|----
user-based | 更依赖于当前用户相近的用户群体的社会化行为 | 适用于用户数较少的场合 | 时效性强，用户个性化兴趣不太显著的场合 | 新加入的物品能很快进入推荐列表 | 弱 | 用户新的行为不一定导致推荐结果的变化
item-based | 更侧重用户自身的个体行为 | 适用于物品数较少的场合 | 长尾物品丰富，用户个性化需求强烈的场合 | 新加入的用户能很快得到推荐 | 强 | 用户新的行为一定导致推荐结果的变化
尝试不同的相似度计算方法。在实践中，我们采用了一种称作loglikelihood ratio [1]的相似度计算方法。在mahout中，loglikelihood ratio也作为一种相似度计算方法被采用。
下表表示了Event A和Event B之间的相互关系，其中：
k11 ：Event A和Event B共现的次数
k12 ：Event B发生，Event A未发生的次数
k21 ：Event A发生，Event B未发生的次数
k22 ：Event A和Event B都不发生的次数
| Event A | Everything but A
---|----|----
Event B | A and B together (k_11) | B, but not A (k_12)
Everything but B | A without B (k_21) | Neither A nor B (k_22)
则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为几个元素组成的系统的香农熵)
对于移动设备而言，与PC端最大的区别之一是移动设备的位置是经常发生变化的。不同的地理位置反映了不同的用户场景，在具体的业务中可以充分利用用户所处的地理位置。在推荐的候选集触发中，我们也会根据用户的实时地理位置、工作地、居住地等地理位置触发相应的策略。
区域消费热单
区域购买热单
当新的线上用户请求到达时，根据用户的几个地理位置对相应地理位置的区域消费热单和区域购买热单进行加权，最终得到一个推荐列表。
此外，还可以根据用户出现的地理位置，采用协同过滤的方式计算用户的相似度。
搜索是一种强用户意图，比较明确的反应了用户的意愿，但是在很多情况下，因为各种各样的原因，没有形成最终的转换。尽管如此，我们认为，这种情景还是代表了一定的用户意愿，可以加以利用。具体做法如下：
对用户过去一段时间的搜索无转换行为进行挖掘，计算每一个用户对不同query的权重。
计算每个query下不同deal的权重。
当用户再次请求时，根据用户对不同query的权重及query下不同deal的权重进行加权，取出权重最大的TopN进行推荐。
对于协同过滤而言，user之间或者deal之间的图距离是两跳，对于更远距离的关系则不能考虑在内。而图算法可以打破这一限制，将user与deal的关系视作一个二部图，相互间的关系可以在图上传播。Simrank [2]是一种衡量对等实体相似度的图算法。它的基本思想是，如果两个实体与另外的相似实体有相关关系，那它们也是相似的，即相似性是可以传播的。
Let s(c,d) denote the similarity between items c and d, for c != d
O(A),O(B): the set of out-neighbors for node A or node B
I(c),I(d): the set of in-neighbors for node c or node d
simrank的计算（采用矩阵迭代的方式）
计算得出相似度矩阵后，可以类似协同过滤用于线上推荐。
目前我们的业务会产生包括搜索、筛选、收藏、浏览、下单等丰富的用户行为，这些是我们进行效果优化的重要基础。我们当然希望每一个用户行为流都能到达转化的环节，但是事实上远非这样。
当用户产生了下单行为上游的某些行为时，会有相当一部分因为各种原因使行为流没有形成转化。但是，用户的这些上游行为对我们而言是非常重要的先验知识。很多情况下，用户当时没有转化并不代表用户对当前的item不感兴趣。当用户再次到达我们的推荐展位时，我们根据用户之前产生的先验行为理解并识别用户的真正意图，将符合用户意图的相关deal再次展现给用户，引导用户沿着行为流向下游行进，最终达到下单这个终极目标。
目前引入的实时用户行为包括：实时浏览、实时收藏。
虽然我们有一系列基于用户历史行为的候选集触发算法，但对于部分新用户或者历史行为不太丰富的用户，上述算法触发的候选集太小，因此需要使用一些替补策略进行填充。
为了结合不同触发算法的优点，同时提高候选集的多样性和覆盖率，需要将不同的触发算法融合在一起。常见的融合的方法有以下几种 [3]：
目前我们使用的方法集成了调制和分级两种融合方法，不同的算法根据历史效果表现给定不同的候选集构成比例，同时优先采用效果好的算法触发，如果候选集不够大，再采用效果次之的算法触发，依此类推。
如上所述，对于不同算法触发出来的候选集，只是根据算法的历史效果决定算法产生的item的位置显得有些简单粗暴，同时，在每个算法的内部，不同item的顺序也只是简单的由一个或者几个因素决定，这些排序的方法只能用于第一步的初选过程，最终的排序结果需要借助机器学习的方法，使用相关的排序模型，综合多方面的因素来确定。
非线性模型能较好的捕捉特征中的非线性关系，但训练和预测的代价相对线性模型要高一些，这也导致了非线性模型的更新周期相对要长。反之，线性模型对特征的处理要求比较高，需要凭借领域知识和经验人工对特征做一些先期处理，但因为线性模型简单，在训练和预测时效率较高。因此在更新周期上也可以做的更短，还可以结合业务做一些在线学习的尝试。在我们的实践中，非线性模型和线性模型都有应用。
主要的步骤如下：
在我们目前的重排序模型中，大概分为以下几类特征：
对于非线性模型，上述特征可以直接使用；而对于线性模型，则需要对特征值做一些分桶、归一化等处理，使特征值成为0~1之间的连续值或01二值。
以数据为基础，用算法去雕琢，只有将二者有机结合，才会带来效果的提升。对我们而言，以下两个节点是我们优化过程中的里程碑：
以上是我们在实践中的一点总结，当然我们还有还多事情要做。we are still on the way!