作者：傅凌进      部门：跨境电商·数据平台与分析部 

摘要：之所以同时提到广告/搜索/推荐三个系统，是因为这三者有一定的相似性，即通过一次请求（基于上下文、用户场景、关键词等）给用户呈现一篮子元素，这些元素包括如文章、商品、活动、专辑、音乐、视频等等。这一篮子需要展示的元素尽管是根据权重进行过排序，但一个很常见的问题就是基于视觉效果的考虑需对这个列表进行类别打散，最常见的一个例子是在电商领域，对推荐的商品进行类目/品牌等属性打散开，从而增加阅读舒适性。

关键词：[推荐系统][规则排序][细节优化][体验提升]

一、引言

  根据摘要的描述，广告/搜索/推荐系统中经常可能需要对结果进行按类别重排序，以便得到更好的视觉体验，这类需求场景，很多时候是出现在综合性展示区域，如考拉的首页，新闻的首页、音乐的每日推荐等等，如果是专用栏位，比如电商中同品牌推荐、相似推荐等并不需要这种考虑的，但是可能仍然可能需要根据颜色、包装样式打散等等。

图1展示了4个商品结果，如果是在搜索结果中，这样的排列可能并不会觉得有任何问题，如果呈现在根据兴趣的推荐中，这一连串特别是相似的药瓶可能会让用户觉得系统出了bug，更常见的一个场景是某搜索的广告中，经常给你展示一堆某系医院的广告，一个挨着一个。

图1在推荐中一次效果不太好的呈现示例

图2给出了一种基于内容推荐APP中的一例子，出现这样的情况有种让用户觉得进入了娱乐频道的感觉。

图2某内容推荐中经常连续推荐两篇娱乐新闻

  所以我们需要对输出结果按特定的类别进行打散，这里统称用“类别”，具体可以指分类、种群、一二级三级类目、物理属性、来源、产地、品牌、广告主、色系、款式等等。如果涉及到多种类别同时考虑，则情况比较复杂，暂时此讨论范围内。本文基于自己的经验以及几个版本的迭代成果，结合在考拉推荐中的实践经验，提出一种可以实现比较通用鲁棒的排序方法，并给出实际一步一步解读，分享对这个细节的一些思考，有错误和改进之处多多指教：）

  实际上，这一方面公开的资料不太丰富，但只要做过类似的数据后期处理的，一定有自己的经验或者实现方式，先看看最通常能想到的基于窗口滑动的，图3的第一行数据是原始数据，窗口尺寸为2（定义考虑的窗口中最大位置减去最小位置的差值）其中文字颜色代表某种类别（红黄白三类），数值代表元素id（可以认为是商品id等等）。原理是通过一个窗口区域内逐步排查，发现有冲突的类别，就和后面最近一位类别不冲突的id做交换，如第二行中2和3同时存在窗口中，那么3和后面的4交换能保证第一窗口中没有类别冲突的元素，依次类推，直到第四窗口的时候发现，没有任何其他元素可以填充进窗口4中能满足要求。那么最终的结果中同类别的7和8就会连续出现。基于窗口滑动的这种算法直接简易常见，时间复杂度是O（n*k），通常需要排序的元素（n值）不会上三位数，所以实际应用中可以忽略时间的损耗影响。窗口滑动方法容易实现和理解但主要的问题是不太鲁棒，如果不加以控制容易出现连续（未分散）的情况（当然实际中可以有其它更复杂手段加以控制）。

图3窗口滑动法打散类别

二、方法

(1) 说明

定义：窗口尺寸为winlen为考虑的窗口中最大位置减去最小位置的差值，比如可以将同类别的放置到0（程序员数数从0开始）号位和2号位，那么winlen=2，故而如果winlen<2,实际无意义；实际使用中，用得多的值是2/3/4（很特别）。此外，下文中会经常进行“轮询”和“摘取”两个过程，轮询表示依次对类别进行遍历，目的是查看该类别排序中的第一个元素是否满足要求，如满足要求，就摘取（类似弹出、pop）到候选队列，并在该类别的原存储出中删除这个元素。

假定：原始数据一般是有序的，通常根据用户喜好的预测程度排序，重排序必然会打乱其预测，也就是违背初衷，本文提出的方法尽量保证原有顺序，为了部分环节的快速处理，会有地方忽略本身的顺序权重，所以我们假定了给出的原始数据，均是满足要求，其顺序在一些地方同等对待。

效果：本方法通用鲁棒，所谓通用，一方面是场景通用，一方面是指刚才提到的可以对各种类别进行打散，还有一方面是只可以对各种类型的数据（Long和String居多）进行处理；所谓鲁棒，是指同样的输入数据列表，不管其结构是怎样的排列方式，都能同样程度的得到分散效果。

条件：不难证明，如果最多类别元素是k，列表大小是n，窗口尺寸是winlen，如果符合：

  则无论如何也不能满足打散的需求，只能以最大可能对列表前部分的类别打散，后尾部数据采用贪心算法降级处理（比如采取winlen-1、winlen-2的尺寸等），上述公式中中括号是取整。

(2) 实现思路和框架

  本文提出的算法思路主要是通过做数据预处理，将元素和类别按原有顺序填充到动态数据类别矩阵，行坐标是元素，列坐标是类别，在同一类别中，元素按输入顺序排列。在选取过程中，优先轮询元素多的类别，再进行日常轮询，轮询的结果和参数（返回个数limit、打散窗口尺寸winlen等）进行对比，如果满足条件，则摘取相应的元素到输出队列，再进行下一轮的摘取。

图4

   首先将数据和参数进行变换（主要是输出个数limit，通常和输入一致，以及窗口尺寸winlen），依次得到基础数据含：类别最新位置记录器L（用于记录每个类别最新的一个位置）、类别元素字典D（记录映射关系）、动态数据类别矩阵M（，若一个元素被摘取，则同类别的其它元素自动向上补，同类别的顺序和输入时候的顺序保持一致），富元素类别指针P（每次元素摘取后，更新该指针指向新的最多元素的类别，可能多个）；

其次将输入数据放进候选器进行筛选，对动态数据类别矩阵M在每一轮按类别对元素挨个日常轮询，且在每次轮询前优先询问一次富元素类别指针P指向的类别（若是同一个，则忽略），无论是优先询问的还是日常轮询，其判断依据是对被询问的元素根据最新位置记录器L的数据和设定的窗口winlen的关系来判定，若成功得到候选集，根据当前环境的使用参数和类别元素字典D对应关系更新相应数据；

经过一轮的轮询问下来，摘取的元素依次更新到输出数据，并响应的对摘取过后的基数数据进行排序，如果有类别的元素被摘空，则更新空类别的集合，如果满足特定条件，则退出循环，否则进行下一轮的日常轮询。刚才所述特定条件包括：空类别集合是所有类别、输出的元素数量达到传入的limit个、再也没有新的候选集生成等；

若流程已经退出轮询的步骤，且输出列表的元素个数未达到设定的个数，说明要么设定值过大要么动态数据类别矩阵M里面还有元素无论如何也无法按设定条件进行足够的打散后放到输入列表，这时候只能通过填充策略今天填充，填充策略采用贪心法，依次对存在元素的类别进行轮询，哪个类别和当前最新位置记录器L的值差异最大则选哪个元素，直到满足条件。

以上就是架构的整体思路，用一句话来总结核心思想就是通过将原始输入数据存放到动态数据类别矩阵M对类别进行多轮的轮询同时优先考虑当前拥有最多数据的类别，进行类别的打散排序输出，若实在无法打散，则尽可能采取贪心算法进行填充。

(3) 算法流程示例

以上框架中核心算法流程总体如下：

图5总体算法流程

下面以一个示例简短的对以上算法做说明，假定一列原始数据如下，颜色表示类别，数字表示商品id：

该示例数据大致和上文中基于窗口滑动了的类似，但为了增加说明几个算法细节，做了适当修改，整个算法流程示意图如下。

图6：第一轮摘取元素的过程

图7：第二轮摘取元素的过程

 

图8：第三轮摘取元素的过程，完成

  通过图6-图8之后，剩下两个元素不能按规则分配，于是按贪心法遍历类别（贪心是指计算此时能进行最大窗口处理的情况就选择该元素），很容易理解的得到将12和10一次填入到输出列表中，如下：

 

(3) 再进一步优化

对比原始数据，经过本文提出的算法已经尽量做到按窗口尺寸为3的打散，留下最后两个元素不满足需求，观察过程发现，在某一步优先轮询的时候，去掉了类别A之后，A和B的元素数量一致且为最大，这个时候应增加循环差集算法作优先轮询(可以有最大优先轮询次数限制)，这样可以在6之后优先排3而非11.

图9：某两步中可以优化的地方

通过以上优化思想，可以最终得到更好的结果，如下对比所示，第一行是原始数据，第二行是优化后的算法，此时只有最后一个元素（元素id=10）未做到按窗口尺寸3进行排列，观察该数据发现，这已经在理论上已经无法实现，故而目前的状况为最优解（严谨的说是并列之一）。

原始输入

结果输出

三、结尾

   本文提出了一种类别分散算法，从结构和实例详细做了阐述，通过本文的方法，在广告/搜索/推荐系统中，可以按特定的类别和特定的数据类型对最终结果进行规则分散，以提高用户体验。实际应用中，还可能结合这种思想按当前场景的特性进一步优化；另外，工程部署中还应该注重上游算法本身对类别数目的控制，要是出来的所有元素都是同一个类别，直观来看就不可能；再有，第一个元素的排列可能需要考虑之前的展示结果，比如每次刷新10个元素的应用场景，从第一个元素开始，就应该考虑和上一次请求的最后几个元素的窗口问题；最后如果是多种类别，比如类目+品牌，可以将类目和品牌作为一个联合类别输入进行打散。

    理论上讲，本文提出的时间损耗均为O(nlogn)，经测试对1000的商品排序时间损耗不超过1ms，而实际应用场景多为几到几十个商品，所以时间不成问题。通过提出的动态数据类别矩阵的摘取方式，可以做到比较鲁棒的得到全局最优之一的解，实际上全局最优解在对算法细节做微调后会以不同的结果呈现，还可以通过AB测试进行微小的细调（如果场景需要）。本文示例的k=5，n=12，winlen=3，通过条件公式很显然不能满足所有条件，故而只能牺牲最后一个元素的达到标准（10和9只间隔了2）来近似满足需求要求。

网易云新用户大礼包：https://www.163yun.com/gift

本文来自网易实践者社区，经作者付凌进授权发布。