4
雷锋网 AI 开发者按：近日，在中国北京举办 CIKM 2019 AnalytiCup 中，由来自浙江大学、中央财经大学、阿里巴巴等机构组成的团队 WWG 摘得「用户行为预测」赛道的桂冠。
CIKM 是中国计算机学会（CCF）推荐的数据库/数据挖掘/内容检索领域的 B 类会议。 CIKM AnalytiCup 挑战赛是会议同期举行的国际数据挖掘比赛，今年由 CIKM、阿里妈妈、阿里巴巴算法大学、阿里云天池共同承办，挑战赛分为两个赛道，用户兴趣高效检索（Efficient User Interests Retrieval）和用户行为多样性预测（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。
现雷锋网 AI 开发者将 WWG 团队冠军方案整理如下，希望能给开发者们一些经验与启发。
本次冠军团队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 阶特征交叉; 分别对最后的模型效果有一定提升。
图 6 排序模型图
以下是我们算法迭代过程中的一些重要节点：
version1 基于协同过滤+统计特征
version2 基于显性层次特征+统计特征
version3 基于显性/隐形层次特征+统计特征
version4 基于二阶结构特征交叉+统计特征
version5 基于三阶结构特征交叉+统计特征
图 7 重要节点示意图
可以发现，通过引入层次结构特征，尤其是隐式层次结构特征的提取，我们对这一问题进行了较好的求解，从结论上可以看出，结构特征确实对整个预测准确度带来了较大的性能提升，后续对结构特征信息做了特征交叉之后，性能也有了进一步的提高。
本次比赛我们尝试了 Hierarchical GNN 模型来获取用户和商品的隐性层次特征，获得了非常不错的效果，由于比赛时间非常有限，我们的排序模型使用了 LR, 以便于快速迭代并调整相应参数，使用了 point-wise 的训练方式。
如果还有足够的时间，我们还会尝试更多的排序模型，比如 xgboost, deepFM, wide&deep 等，并对模型做相应的融合，再采样 pair-wise 的训练方式，相信还会进一步提升模型效果。
图 8 冠军获奖合影
更多信息请参考大赛官网：
雷锋网 AI 开发者
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
