小叽导读：双十一是网购的狂欢节，每到大促的时候，平台就会发放数量不少，金额不同的优惠券给用户带来实惠，比如今年就有满400减50的优惠券等。满减常常会涉及到凑单这个环节，如何用凑单撬动更多的成交，让买家拥有更好的线上购物体验，下面，搜索事业部的算法专家云志将为我们详细解读。
前言
凑单项目的目标就是当用户加购了某个商品之后，在属于同一个优惠券下面的商品池中为用户推荐他还感兴趣的商品。所以凑单有多方面的目标：
一方面，尽可能增加用户在凑单场景下的成交，能证明通过优惠券来引导购物的场景确实能为用户带来实惠与惊喜；
另一方面，我们也希望通过凑单去撬动更多的成交，比如当用户已经加购了300元商品，正在犹豫不决时，如果再凑上100多元的商品刚好满足满减的金额时，能够正向的激励用户去购买这些商品；
最后我们也是希望能够给用户带来更好的体验，方便用户能够更容易，也更实惠的买到喜欢的东西。
同时凑单项目又是一个带约束条件下的推荐问题，需要解决以下的问题：
首先，凑单中很大一部分流量是来自于购物车中的“凑单”按钮，那么我们所要推荐的凑的商品或多或少需要与当前的商品有一点关系，尤其是在一些特定的行业，如针对手机凑手机壳，或者在图书行业，如果用户加购了军事类的图书，那么凑同样是军事类的图书则更能让用户感到惊喜，所以决定凑什么品类的商品，是需要解决的第一个问题；
其次，既然是凑，那么用户还是希望能在一定的价格限制条件下完成所有商品的打包购买，所以我们推荐的商品，价格不能太高，这样就失去了凑的定位，总不能买一双运动鞋，我给你凑一个跑步机，但是价格也不能太低，这样会给用户带来较大的购买成本，让用户挑花了眼，所以我们推荐的商品需要价格上能够更好地匹配用户的需求，能够让用户一眼看过去就决定要买这几件商品；
最后，是凑单的效率与体验上的平衡问题，效率与体验总是有一些矛盾的，所以我们通过了多种方法来保障体验，如基于虚拟类目的打散、曝光过滤等，同时也使用了online-ltr，ctrcvr模型来保障我们的效率。
凑单的产品形态如下图所示，今年我们还增加了Query推荐这个模块，因为我们发现当用户刚进凑单页时，往往因为商品太多，而不知道有哪些商品可以凑：
整体解决方案
除了本文所提到的方法之外，我们凑单项目还有其它的多种优化算法与思路，如：分布式跨类目Graph Embedding算法的实现与应用；交互tag推荐；用户疲劳度的感知初探。
我这里主要就前面提到的三个问题讲一下我们的解决思路与方案：
基于认知的场景推荐方法
基于组合背包问题的价格约束算法
基于虚拟类目等多种方法的体验保障机制
基于认知的场景推荐方法
凑单场景下首先要考虑的问题就是给用户凑什么样的商品，当用户通过购物车点进凑单页时，他首先期望的是出现的商品与购物车中的商品有一定的关系，如果两者之间没有任何的联系，同时与用户的偏好也没有什么关系，则用户的满意度就不高。所以对于商品的召回方式，我们有以下几种方法：
基于用户长期偏好类目的召回
基于用户短期偏好类目的召回
基于认知的场景推荐方法
当前比较热门的Graph Embedding的方法，是基于用户对item的点击与成交等信息，构造一张图，然后基于图进行随机游走，得到节点的embedding信息，再根据该embedding信息进行后续的成交预测等步骤，Graph Embedding已经被证明是一种行之有效的方法。
而我们这里从对用户认知的思路出发，加入对用户更深入的意图理解，比如用户加购了一个“登山鞋”，那可能是有“登山装备”相关的需求，因此我们从场景概念入手，首先进行场景概念的挖掘，其次是对场景下所对应的商品进行打标。
场景概念挖掘
对于场景概念的挖掘，主要是通过用户的query信息，提取里面较宽泛的短语，其中包括两个方面，一是对该类短语的新词发现，二是判断这些短语有较宽泛的意图。对于短语的新词发现，我们使用了互信息与左右熵的方法从query中进行提取，这样可以得到一批新的短语，同时又针对用户搜索这些query之后点击的商品的类目宽泛度，来判断它是否为较宽泛的query，从而得到一个场景，比如：
应用
我们在应用时，首先获取用户当前加购的商品，然后得到其对应的场景概念，再基于该场景概念取点击商品最多的类目，对其进行召回。
基于场景认知的推荐，是我们找搭配类目的其中一个手段，另外我们也根据用户的行为数据，基于Memery Based的协同过滤方法，来计算类目之间的相似度，从而得到了一份1级类目到1级类目的搭配数据，如：电脑硬件/显示器/电脑周边->3C数码配件，影音电器，电子元器件市场，网络设备/网络相关，闪存卡/U盘/存储/移动硬盘，电子词典/电纸书/文化用品。
同时用户的长期短期偏好的类目信息也会与场景知识进行结合，从里面筛选出更加个性化的类目进行推荐。最后得到了我们基于用户认知的场景推荐数据。
比如我们在加购了某个洗面奶之后：
图4. 加购商品
我们会为其推荐如下类目的商品 - 护发素、沐浴露、洗发水、香皂。
又比如我们在加购了某个茶座之后：
图5. 加购商品
我们会为它召回以下几个类目的商品：茶盘、公道杯、茶杯、茶巾、茶叶罐、茶宠摆件、功夫茶具、茶滤、茶壶。
基于组合背包问题的价格约束算法
通过上面的方法，我们得到了在当前购物车中有某种商品的情况下，会召回哪些类目下的商品，但是每个类目下的商品价格不同，同时用户对每个类目的偏好程度也不一样，那么在这么多不同的类目以及不同的价格情况下，我们应该以怎样的方式将合适价格的商品呈现给用户呢？这里我们使用了分组背包的方法来解决这个问题。
分组背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。首先看一下基本的0-1背包问题：
0-1背包问题：假设有N个物品，每个物品j的价值为
，重量为
，背包所能承受的最大重量为W(W≥0)，问题可以形式化为：
0-1背包问题是一种特殊情况下的组合问题，不太适合我们现在的情况。
分组背包(Multiple-Choice Knapsack Problem)：MCKP则是一种更泛化的背包问题，它是将N个物品分在M个组里面，每组中有
个物品，同时每组中的商品相互冲突，只能选一个，但是最终可以从M组中分别选择一个物品，以使得价值最大，其形式化描述如下：
其中
为第i组中第j个物品的价值，
为其重量，
为是否选择该物品，它只能为0或1。
凑单场景下的分组背包问题
很明显，分组背包问题是比较适合我们的凑单问题的：
首先，我们推荐商品是基于类目的维度来推荐的，这里的类目就对应于分组M。
其次，在一页推荐中，一个类目下的商品最多只出一次，相当于每组商品只能选一个。
最后，我们的问题也是希望求在有约束条件下（满400），尽可能提高用户的成交GMV。
我们建模方法如下：假如当前召回类目为M个，对于每个类目i，有个商品可选，且
表示其价格，同时
表示该商品被购买的概率，因此当前情况下的收益为
，同时还要保证当前的商品总价大于满减的金额。形式化描述如下：
这里我们在约束条件那里加上了一个变量δ，是一个松弛变量，因为虽然是满400的金额下有优惠，但是我们仍然希望根据不同的用户，让他有更多的成交，比如购买力高的用户可以让δ更大一点，比如令δ=100，对于购买力稍微低一点的用户，可以让δ小一点，如δ=50，这样可以尽可能的提高用户的成交金额。
接下来就是将上面的公式转化为满足分组背包问题的形式，如下：
这里引入了一个常数C，使得右边的式子满足大于0的限制。在我们的情况下，因为提前知道满减的金额，所以这里的C就比较好确定。
再转化为标准的分组背包问题，有：
现在对于公式里面的变量有M，δ以及
，这里的M与δ目前是基于规则来定的：
因为首屏为4个商品，所以我们这里将限定M≤4，通过当前总的满减金额P与当前购物车内加购的商品价格padd来确定，
，以尽可能的在加购金额少的情况下多推荐几种品类的商品。
δ是与用户有关，当用户的购买力高时，增加的价格稍微高一些，这里我们根据用户的1-7档购买力，取P×0.1到P×0.7。
最后就是的确定，它是与用户相关的。我们这里并没有针对单个的商品去预测用户的偏好，因为针对单个的商品排序我们放在了最后面的online-ltr以及ctrcvr模型中去完成，我们这里主要的目标是对特定类目下应该给用户推哪个价位的商品，使得既能够满足凑单的价格限制条件，又能够让用户尽可能的成交，所以这里面的是计算的用户对类目i下第j个价格档位的偏好。价格档位的确定按照现在主搜的方法，将每个类目下的价格分为7档，并通过用户的历史行为去预测他对于每个价格档位的偏好程度，得到!
对于MCKP问题的求解，目前已经有比较成熟的O(n)复杂度的方法，由Dyer与Zemel分别提出，详情可查看后面参考文献。
通过前面的方法，我们得到了推荐的几个类目以及类目下对应的最适合价格区间，在排序时，我们将满足这个价格区间的商品进行相应的加权，同时我们也在一个桶的小流量下将这些商品进行置顶的操作，以查看具体的效果。
下面是其中的效果展示，当我加购了一个100多元的男士用品时，给我推荐了相关类目下合适价格的商品，使得总金额恰好超出400。
图6. 价格组合效果1
下面是通过汽车用品进凑单页之后出现的效果，价格组合出来也是恰好超出400元。
基于多种方法的体验保障机制
在我们的凑单项目中，我们一方面使用了online-ltr以及ctrcvr模型来保障效率，另一方面，我们也追求体验上的不断优化，我们这里采用了几次方法来优化体验：
基于虚拟类目的类目打散
曝光过滤
用户疲劳度模型
我这里主要讲一下基于虚拟类目的类目打散机制。类目打散是指在一页10个宝贝中，某种维度的商品最多出现固定次数，比如按照一级类目为2，叶子类目为1打散，则是指10个宝贝中最多有2个商品属于同一个一级类目，而每个叶子类目的商品只能有1个。这样是为了避免用户产生疲劳的感觉，比如一眼看过去全是鞋的情况。这在推荐场景是非常重要的。
现有的类目体系在进行类目打散方面不能很好的满足当前的推荐场景，因此我们根据品类的方式建立了一套虚拟类目的体系，既避免了一级类目打散过粗，叶子类目打散过细的问题。
图8. 基于品类关系的虚拟类目体系
图9. 类目树构建
在我们凑单场景下，按照虚拟类目的维度进行打散，避免了一页全是不同类目下的鞋的情况，较好地解决了体验上的问题。虚拟类目的详细构造方法请见参考文献。
算法效果
今年我们在系统以及算法上都做了一次较为全面的升级，在算法模型上部署了深度学习模型，分组背包优化模型，跨类目Graph Embedding模型，在权重的学习方面引入了实时的LTR，同时我们在产品形态上也做了优化，加上了Query推荐的形式。整体上同比去年直接引导进店支付金额+XX%，转化率+XX%，直接引导宝贝支付金额+XX%，转化率+XX%。
线上A/B对比基准桶曝光价值+XX%，转化率+XX%。
总结与展望
今年我们第一次在凑单的场景上尝试了组合优化的方式来解决如何在有价格约束的前提下尽可能的提高用户成交的问题，也第一次将对用户的场景认知应用到了凑单的场景上，取得了一定的效果。
同时因为这次的项目时间太紧，还有很多的尝试没来得及做，比如在价格模型中，如何基于用户反馈来动态化的确定分组个数M，以及价格松弛因子δ，同时对于用户对于类目下价格的偏好还可以做得更细致一些，在后面的优化中，会尝试用强化学习的方法对这些因子进行学习。
同时还有几点可以细化的，我们现在做价格组合的时候，并没有显式的让用户感知到，如果在产品形态上，有一个单独的承接页，里面就是已经按照价格约束打好包的商品，这样能够让用户的体验更好，更能体现出“凑”的感觉出来。
团队介绍：搜索事业部是阿里巴巴集团的核心业务和核心算法团队，包括双十一在内的大规模数据场景实战经验的团队，不停追求技术边界突破和业务创新的团队，包括来自世界各地的优秀算法工程师，成果屡次获得集团大奖，并被主流媒体报道过，同时也和海内外一流高校和实验室有长期科研合作项目，发表过包括WWW，SIGIR，KDD，CIKM等会议在内的多篇顶级学术会议文章。如果你对搜索事业部有兴趣欢迎发送简历，社招校招&实习生均可联系邮箱：tanjun.tj@alibaba-inc.com。
原文发布时间为：2019-12-05
本文作者： 云志
本文来自云栖社区合作伙伴“ 阿里巴巴机器智能”，了解相关信息可以关注“ 阿里巴巴机器智能”。
