CIKM 2019 挑战杯冠军方案分享：「初筛-精排」两阶求解框架

2019 年 11 月 8 日 AI科技评论

作者 | 杨鲤萍

编辑 | 唐里

近日，在中国北京举办 CIKM 2019 AnalytiCup 中，由来自浙江大学、中央财经大学、阿里巴巴等机构组成的团队 WWG 摘得「用户行为预测」赛道的桂冠。

CIKM 是中国计算机学会（CCF）推荐的数据库/数据挖掘/内容检索领域的 B 类会议。CIKM AnalytiCup 挑战赛是会议同期举行的国际数据挖掘比赛，今年由 CIKM、阿里妈妈、阿里巴巴算法大学、阿里云天池共同承办，挑战赛分为两个赛道，用户兴趣高效检索（Efficient User Interests Retrieval）和用户行为多样性预测（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。

我们将 WWG 团队冠军方案整理如下，希望能给开发者们一些经验与启发。（关于「用户兴趣高效检索」赛道冠军方案，我们也正在整理中，敬请期待~）

赛题简介和分析

基本问题

根据历史用户-商品交互行为、用户属性和商品属性，对给定用户进行未来点击预测，选出该用户未来三天最可能点击的商品 top50；其中，在复赛中需特别注意一点，即用户历史点击商品并不在未来可能出现的点击商品可选池中。

评估指标 Recall@50

其中为用户在未来三天内的实际点击商品集合，为用户在未来三天内的预测点击商品集合，此处需要注意，预测点击商品集合的数量需满足，即返回商品数量严格约束为 50 个。

简要分析

仅仅看题目描述我们可以发现，这个题目本质上是一个召回预估问题。更具体的，这个问题应该以 u-i 对为输入，经过一定模型的判断，最终给出一个 u-i 对对应的分数，再根据每个 user 对应的 u-i 对分数从大到小的排序，取出 top50 的 item 作为最终得到预测点击商品集合。

同时，考虑到规模问题，对于千万级别的独立 user 和 item，直接去做全集的 u-i 对预测显然既不现实又不经济，因此我们在结题初期就确定了「初筛-精排」两阶段求解框架，如图 1 所示：

图 1 「初筛-精排」两阶段求解框架

然而，这个题目的标题为用户行为预测，在赛题官方的描述里也多次提到 Graph 的概念。从这一角度思考，这个问题可以描述为 u-i 二部图的 link prediction 问题，虽然从模型的角度来看可能和刚刚说到的类似，但这一特点似乎在暗示图结构信息在这一比赛当中的重要性。

因此，我们决定从两个角度对此问题进行分析和求解：传统的基于静态属性信息的统计特征工程，以及基于 u-i 二部图的结构特征工程。

解题思路

统计特征的提取在我们的工作中相对简略，因此在本节中，我们着重介绍我们对图结构特征的思考和使用。

算法动机

为了可以预测用户未来的点击行为，我们需要对用户和商品进行更为精准的刻画和表达，由于本次赛题的主视角是用户视角（用户会点哪些商品），所以我们认为，解决 u-i 对预测问题的核心思想是：如何更好的表达用户的偏好。即什么样的商品用户会点击，历史的交互行为所传达出来的哪些信息对未来点击的预测是有效的。

通过对用户的行为进行思考和分析，我们发现用户的偏好存在如下两类的关系：

如果一名用户点击了某个商品，那么该用户对该商品所在类目的商品具有一定程度的偏好，如：iPhone，Mate 30->MI MIX Alpha（智能手机类目）；
如果一名用户点击了某个商品，那么该用户对该商品所在主题的商品具有一定程度的偏好，如：沙滩裤，太阳眼镜->防晒霜（沙滩旅行主题）。

层次关系

更深入的，我们发现这两类关系存在相对明晰的层次关系，如：

基于类目的层次偏好：iPhone，Mate 30->MI MIX Alpha（智能手机）->Canon EOS 相机（电子产品）；
基于用户兴趣主题的层次偏好：沙滩裤，太阳眼镜->防晒霜（沙滩旅行）->运动鞋（户外旅行）。这里的沙滩旅行和户外旅行都是用户兴趣层面的表达。

这两类偏好关系广泛存在与用户的历史行为中，具体如图 2 所示；因此，如何合理捕捉这两类层次特征，是我们接下来算法的重点。

图 2 层次偏好特征表达示意图

解决方案

在接下来的算法中，我们将基于类目的层次偏好称为显式层次偏好，将基于用户兴趣主题的层次偏好称为隐式层次偏好。我们的解决方案一共包含以下四部分：

图 3 解决方案大纲

数据预处理

由于数据集本身是存在不同日期，不同交互行为（点击，购买，加购，收藏）的，我们首先通过引入时间衰减因子和行为衰减因子两个超参数，对原始数据集进行处理，并构建完成 user-item 二部图（如图 4）。

与此同时，也根据 user 特征数据集和 item 特征数据集构建一系列统计特征，以及 user 和 item 的属性特征。

图 4 user-item 二部图

显式层次特征提取

显式层次特征主要基于 item-cate-cate1 的层次关系，通过将历史行为与 item 特征进行匹配，可以分别构建出 user-item，user-cate，user-cate1 三张二部图，对三个层次分别实现协同过滤算法，从而得出 user 对不同 item，不同 cate 以及不同 cate1 的相似性得分。我们可以看到显性的层次特征是只有 item 维度的。

图 5 显性层次特征提取

隐式层次特征提取

隐式层次特征的提取相对困难，因为兴趣主题并不像类目一样，每个商品并没有被标定一个显式的兴趣主题。为了比较好的解决这一问题，我们提出 Hierarchical Graph Neural Network（HGNN）算法，对图结构进行表达。

具体的，我们对原始的 u-i 二部图做 GraphSAGE 算法，以具有边的 user，item 的向量表达相似（余弦相似度）为目标（注意，这里严格意义上应该区分两个向量空间，在比赛中我们为了提高效率将两个向量空间的维度设定成了相同的 16 维，因此可以实现余弦相似度的计算），做无监督的 Graph Embedding 训练。待网络稳定后，我们可以得到每个 user 和 item 的向量表达。这一向量即为该 user/item 的一级隐式特征。

为了表达出层次特性，我们根据 user/item 的一级隐式特征，分别在 user 和 item 的向量空间中做聚类（比赛中采用 K-means 聚类），以聚类簇的平均特征向量作为簇节点的向量，以簇间原始节点关联关系的统计作为簇与簇之间的关联（边）。这样，我们便通过聚类操作，将原始 u-i 二部图粗化，变为了一个以主题用户簇和主题商品簇为节点，节点数量更少的粗化图。对粗化图做和原始 u-i 二部图相同基于 GraphSAGE 的 Graph Embedding 操作，我们便可以得到粗化隐式特征，原始节点的二级隐式特征即为其所属簇的粗化隐式特征。

对于每个 user/item，将其一级隐式特征和二级隐式特征级联，即得到该节点的隐式层次特征。在实际计算 u-i 对相似度时，将层次隐式特征分级比较即可得到这一部分的相似分。我们可以看到隐性层次特征是既有 user 维度，也有 item 维度的。

图 5 隐性层次特征提取

排序模型

在 Candidate Generation 阶段（初筛阶段），我们采用计算效率相对较高的显式层次特征（即采用协同过滤分）对所有商品进行初筛，对每个 user，保留其最有可能点击的 2000 个商品进行 Ranking 阶段的精排。需要注意的是，在初赛中历史商品也可能在未来曝光并被点击，所以历史商品无需特殊处理。而复赛阶段由于历史商品不会在未来曝光，所以复赛阶段在初筛阶段的结尾要对历史出现过的商品做筛除，以避免无效精排。

Ranking 阶段基本上每个 user 要处理 2000 个左右的商品，因此我们的预测模型选择了相对简单高效的 LR 模型，将前置工作中得到的显式层次特征，隐式层次特征和统计特征进行不同阶的特征交叉后引入 LR 模型后，将 LR 模型的输出作为排序分数, 取分数 top50 作为最终的预测结果进行输出。

这里交叉特征的引入本质是一个 kernel 函数的思想, 辅助提高了 LR 模型的非线性能力，我们先后采用了显性层次特征和隐性层次特征之间 2 阶的特征交叉以及 3 阶特征交叉; 分别对最后的模型效果有一定提升。