每天点击数100以内的极小量渠道，如何精准地投放游戏广告？

作者 | 成鹏
编辑 | Vincent
微信公众号“AI 前线”，（ID：ai-front）

1 背景

1.1 为什么要有精准投放算法 – 先知

随着公司游戏业务的发展，传统的搜索技术已经不能满足用户对游戏发现的需求，原因有多种，首先用户很难用合适的关键词来描述想要玩的游戏，其次用户的兴趣和喜好在不断变化和更新，再者用户无法对自己未知而又可能感兴趣的游戏做出描述。推荐系统的出现可以帮用户获取更丰富，更符合个人兴趣的游戏。

在流量非常紧缺的互联网上，用户直面的并不是游戏本身，而是一条条广告素材，广告素材是经过美术定制加工在广告投放时播放的视频，Flash 或者展示的图片等。个性化推荐会根据用户兴趣和行为特点，向用户推荐所需的游戏素材，帮助用户在海量信息中快速发现真正所需的游戏，提高用户黏性，促进素材背后游戏的注册和收入。

在广告市场，以参与者划分可以分成平台方和买量方，与诸如淘宝直通车，腾讯广点通，微博粉丝通这类平台上广告系统不同，买量方做广告效果的优化存在以下特点：

（1）渠道流量小，特别渠道流量极小。公司的买量渠道种类众多，投放渠道近百个，流量大小不一，统计每天点击数在 100 以内的渠道广告计划量占比 65%。数据集的稀疏度应该在十万分之一或以下的量级，特征中有效信息（非 0 值）的维度很低，其中包含的噪声会对真实信息干扰很大．使得绝大部分基于关联分析的算法（譬如协同过滤）以及 CTR 预估效果都不好。这个问题本质上是无法完全克服的。因此对于这些极小量渠道的游戏广告精准投放算法需求十分迫切。

（2）买量方对于用户兴趣和行为特点的信息了解甚少，尽管与部分平台的合作能够拿到一定维度的属性数据，但是总体上大部分长尾渠道信息是非常少的，这样造成了用户属性的缺失，并且点击广告的很多均为新用户，考虑到冷启动问题。标签系统提供了解决冷启动问题的可能方案。因为标签既可以看作是素材内容的萃取，同时也反映了用户的个性化喜好。

综合以上实际情况的考虑：用于解决极小量渠道的，基于标签的精准投放算法 – 先知应运而生。

2 算法原理

2.1 算法概述

推荐系统的目的是联系用户的兴趣和素材，这种联系方式需要依赖不同的媒介。目前流行的推荐系统基本上是通过三种方式联系用户兴趣和物品：

图 2-1 推荐系统联系用户和素材的几种途径

考虑到数据稀疏性，协同过滤方式效果不好。因此考虑第三种方式：通过一些特征联系用户和素材，给用户推荐那些具有用户喜欢的特征的素材，这里的特征有不同的表现形式，比如可以表现为物品的属性集合，也可以表现为隐语义向量，而下面我们要讨论的是一种重要的特征表现形式——标签。

2.2 什么是素材标签

在美术做完一个素材后，会给素材打上对应标签，标签内容如下：

图 2-2 素材人工标签

经过标签层级处理，并且标签变量 0-1 处理后得到每个素材的标签：

进行哑变量处理得到素材标签矩阵 T：

2.3 什么是用户标签

在用户请求广告数据时，我们可以通过请求时间以及用户 Cookie 得到用户属性数据，经过正则化解析后得到用户属性矩阵 A：

2.4 如何生成标签点击率

模型根据历史数据中用户的请求，素材加载，素材点击等行为出发，最终定位用户的兴趣标签，考虑用户属性，时间衰减等因素，计算出每个属性下的标签点击率矩阵 C。流程如下所示：

图 2-3 标签点击率生成流程图

2.5 如何根据标签点击率进行推荐

当一个用户发生广告请求时，该广告所在的计划有 M[C1，C2，，，Cm] 种素材，根据用户属性 A[time，local，browser，OS，UID]，以及 2.3 生成的标签点击率矩阵 C，得到 M 个素材的推荐值：

对该计划下 M 个素材的在各个属性的评分进行加权：

对该计划下属性 A 的用户的请求，推荐 M 个素材中 R_m 值最大的那个素材。

2.6 算法整体流程

整体流程图如下：

(1) 离线计算：根据广告请求 – 点击历史数据，对于每个渠道计划，每隔一小时离线计算每个属性下的标签点击率矩阵 C。

(2) 在线计算：在线引擎需要根据当前请求用户属性 A，去读取相应特征数据，进行计算得到每个素材推荐值矩阵 R_m。

(3) 广告投放引擎：广告投放引擎返回 R_m 排序后的最佳素材给 web 服务器，最后显示给用户。

图 2-4 算法整体流程

3 算法优化

3.1 点击数据置信

由于渠道的流量小，会出现点击信息不可信的问题：首先在推荐系统中假设：

（1）每个用户的点击素材行为都是独立事件。

（2）用户只有两个选择，要么点击素材，标记为’1’；要么未点击素材，标记为’0’。

（3）如果某个素材总请求数为 n，其中点击数为 k，那么点击率就等于 p = k/n。

假设两个素材，根据频率学派计算其注册率：

A 素材：2 个请求，2 个注册，注册率：100%

B 素材：100 个请求，99 个注册，注册率：99%

但是注意到：A 素材的请求样本数据远小于 B 素材。那么 A，B 素材的注册率，其实是不可信的。

由于素材的点击与否是一个二项分布, p 可以看作”二项分布”中某个事件的发生概率，因此可以计算出 p 的置信区间。二项分布的置信区间有多种计算公式，最常见的是”正态区间”。但是，它只适用于样本较多的情况（np > 5 且 n (1 − p) > 5），对于小样本，它的准确性很差。

而对于广告的点击样本，有些小渠道的样本往往是很少的。因此采用“威尔逊区间”，能够很好地解决小样本的准确性问题。计算公式如下：

其中 u 表示正例数（点击），v 表示负例数（未点击），n 表示实例总数（总请求数），p 表示点击率，z 是正态分布的分位数（参数），S 表示最终的威尔逊得分。z 一般取值 2 即可，即 95% 的置信度。

根据威尔逊区间，上述 A 点击率修正为：33.33%，B 素材点击率修正为 94.40%。

图 3-1 威尔逊区间修正图

将威尔逊区间用于素材推荐系统后，下图可以看到标签点击率的修正情况：

图 3-2 标签点击率修正日志数据

3.2 时间窗口加权

传统的推荐算法都是基于用户过去的偏好信息来预测用户当前的喜好信息, 这其中包含了一个假设, 即：用户的兴趣是不变的。而在现实生活中, 用户的兴趣很有可能会随着时间的推移而有所变化, 只有模拟了用户这种变化着的兴趣才能更准确地向用户推荐素材。因此需要考虑用户兴趣随时间变化，这里采用时间窗口加权法，即越靠近当前时间点的点击信息越重要。在计算素材标签的点击率时，从当前时间点往前取五个时间段的请求点击数据，并赋予时间衰减权重，如下表:

那么素材标签的点击率为：

其中函数 f 为威尔逊区间函数。衰减参数为超参，需要根据实际情况进行调节。

3.3 维度数据扩充

即使使用了五份的时间窗口，发现在某些时间和地区维度，仍然存在没有广告请求数据。因此对时间维度和城市维度进行数据分析，根据分时段的请求数和点击数，将小时维度合并，1 天分为 4 个时间段；同时将城市维度合并为省份维度；通过 A/B 测试：发现数据维度的合并优化能够有效的解决数据稀疏性问题提高模型点击率。

统计每个属性下的标签的点击率矩阵 C 中请求个数的占比，如下图所示：时间地区维度扩充后，矩阵 C 中为 0 的占比有所下降，数据稀疏性有所缓解。

图 3-3 维度 – 标签请求数据分布图

3.4 维度权重确定

在上面我们提到会对计划下 M 个素材在各个属性的评分进行加权 W，推然后荐 M 个素材中 R_m 值最大的那个素材：

权重是一个相对的概念，针对某一指标而言，某一指标的权重是指该指标在整体评价中的相对重要程度。权重的确定有两种方法：主观赋权法和客观赋权法。这里采用客观赋权法：根据指标的原始数据，通过数学或者统计方法处理后获得权重。在客观赋权法中，采用标准差系数权重法：根据每个指标的变异程度大小来进行赋权，变异程度大的说明能够更好的区分各个指标，应赋予更高的权重，反之赋予较小的权重。步骤如下：

（1）获取单个渠道下历史请求数据日志：