2. 上海市农业技术推广服务中心, 上海 201103;
3. 深圳腾讯计算机系统有限公司, 北京 100080;
4. 林西县职业技术教育中心, 内蒙古 林西 025250
2. Shanghai Agricultural Technology Extension and Service Center, Shanghai 201103, China;
3. Shenzhen Tencent Computer System Co. Ltd., Beijing 100080, China;
4. Vocational and Technical Education Center of Linxi County, Linxi Inner Mongolia 025250, China
随着互联网、物联网和云计算技术的发展, 每时每刻人们都被海量的信息所包围, 而且信息还在呈爆炸式地增长.因此, 当前我们正处于一个信息严重过载的时代.人们要从数量庞大并且纷繁复杂的信息中获取到自己所需要的信息, 是一件非常困难的事情.就观看视频而言, 用户可能会花费大量的时间在寻找自己感兴趣的视频上; 而对于视频服务提供商来说, 如果能将用户感兴趣的视频精确地推送给用户, 可以大大改善用户观影体验, 从而留住更多的用户, 在增加网站流量的同时也增加网站收益.视频的点击率预测技术正是为了应对上述问题而提出的, 该问题利用用户观影历史行为, 挖掘用户的兴趣和偏好等信息, 从而实现用户观影的预测.
然而, 视频点击率预测是一个极具挑战性的难题.首先, 大部分用户点击的视频数量普遍较少, 用户历史行为数据中Positive(点击的)数据远少于Negative(未点击的)数据, 数据的稀疏性特征造成Positive和Negative的数据极度不平衡, 这给点击率预测带来很大的挑战.其次, 用户和视频数据的类型和内容丰富多样, 呈现出异构性的特点, 点击率预测算法需要从纷繁复杂的数据中发掘出对点击率预测精度有积极作用的特征, 这也是一项艰难的问题.最后, 由于新用户和新视频缺乏历史观看数据, 因此在预测点击率时, 准确度很难达到预期目标, 这种问题称为冷启动问题, 如何应对冷启动也是点击率预测问题中的一个难题.
为了解决上述问题, 本文提出了一种将特征工程和机器学习技术相结合的点击率预测算法.在机器学习模型方面, 此算法分别基于逻辑回归、因子分解机[1]以及梯度提升决策树-逻辑回归[2-3]实现点击率预测模型.在特征工程方面, 此算法基于特征选择方法从原始数据中选取出用户和视频的相关特征, 并采用人工组合以及基于矩阵分解两种方式形成用户和视频的交互特征.另外, 此算法基于聚类方法选取训练数据, 从而优化点击率预测的效果.在实验部分, 本文使用腾讯用户观看视频的真实行为数据测试本文提出算法的性能, 实验结果表明, 基于因子分解机模型和基于梯度提升决策树-逻辑回归模型的预测精度要优于基于逻辑回归的模型, 并且将用户特征和视频特征进行交叉组合能够改进点击率预测的精度.
1 相关工作点击率预测等相关问题的研究已取得了大量的进展[4]. Richardson等人提出了基于逻辑回归模型实现点击率预测算法[5], 这种方法较为简单, 易于实现, 且时间复杂度低, 但在稀疏的数据下效果不够好, 预测的精确度较低; Chapelle等人提出了基于动态贝叶斯网络的点击率预测模型[6]; Graepel等人提出了在线贝叶斯概率回归模型[7].以上这些方法主要是针对用户的行为进行建模, 有利于个性化的推荐.但是基于贝叶斯方法的模型存在无法处理新用户和新视频的问题, 并且在处理稀疏数据时表现也不够好.基于SVM模型[8]的好处是可以处理多维非线性的数据, 但在处理稀疏数据时表现不够好, 点击率预测精度较低. Shan等人提出了一种基于张量分解的点击率预测模型[9], 该模型在处理稀疏数据时的表现相对较好, 但更新张量分解模型所需的时间较长, 且无法并行化; Yan等人提出了一种基于Group Lasso的点击率预测模型[10], 该模型可以自动建立特征之间的关联, 在应对稀疏数据时表现较好, 但是计算复杂度较高; Angarwal等人将普通的逻辑回归算法进行改进, 实现了名为"LASER"的点击率预测系统[11], 该系统在应对冷启动问题时表现良好, 但在处理稀疏数据时表现较差; 文献[12]提出了一种利用视频点击流数据预测用户行为的方法, 该方法从点击流数据中提取特征并进行特征选择, 利用经过筛选的特征预测用户行为; 文献[13]基于卷积神经网络构建模型, 预测搜索广告的点击率.
2010年, Rendle提出了因子分解机[1](Factorization Machine, FM)模型, 该模型能够缓解数据稀疏性对预测模型的影响, 在数据稀疏的情况下表现良好. 2014年, 文献[3]提出了一种将梯度提升决策树和逻辑回归融合的模型, 梯度提升决策树模型利用提升(Boosting)的方法[14]集成多棵决策树.决策树[15]算法的特点是能高效地处理非线性的问题, 但是容易出现过拟合.梯度提升决策树并不要求在单棵决策树上达到最优解, 而是集成多棵决策树的结果, 使集成的结果达到最优, 这种方法解决了过拟合的问题.本文所提出的点击率预测算法, 就是基于以上两种模型实现的.
2 算法主要框架本文提出的视频点击率预测算法主要包括特征工程和学习模型构建两部分, 其中特征工程是从原始数据中提取特征, 而学习模型构建旨在基于特征工程提取的特征, 运用监督学习框架训练点击率预测模型.本文提出的算法的主要框架如图 1所示.
|
图 1 视频点击率预测算法框架 Fig.1 Framework of algorithm for video click-through rate prediction |
原始数据中数据的格式复杂, 冗余数据多, 无法将原始数据直接应用到点击率预测算法中.因此, 视频点击率预测算法首要解决的是从原始数据中获取特征.本文算法使用特征工程方法从原始数据提取特征:从用户行为数据中提取出用户特征, 包括用户自身属性、用户的兴趣偏好以及用户所使用的设备属性; 同时从视频数据中提取出视频特征, 包括视频的基本信息以及视频的类型特征.交叉特征对于视频点击率预测的精度具有重要意义, 在提取出用户特征和视频特征之后, 将两者进行交叉组合形成交叉特征.
对于一些非数值型或者无数值意义的特征, 需要进行特征编码操作.特征编码会将一个特征离散到多个维度, 使编码后的每一维特征都具有数值上的意义.通过特征工程处理得到的特征数量如表 1所示.
|
表 1 特征数量 Tab.1 Number of features |
本文基于监督学习模型实现点击率预测算法, 并且由于点击率预测问题实质上是一个二分类问题, 即预测用户点击或者不点击视频.因此需要构建Label为1的正例样本(用户点击视频的数据), 以及Label为0的负例样本(用户不点击视频的数据), 来训练监督学习模型.正例数据可以直接从用户观看视频的历史记录中获取.然而, 由于单个用户只会点击少量的视频, 对于单个用户来说, 绝大多数视频都是未点击的, 但并不表示用户一定不会点击这些视频.因此, 需要从大量未点击的视频中挑选出具有代表性的视频用来产生负例训练样本.若采用随机抽样的方法, 挑选出的视频可能不具有代表性.针对这个问题, 本算法使用基于聚类[16]的方法选择用户未点击视频中的一部分, 用于产生负例数据.具体方法将在第3节中详细说明.
离线训练好模型后, 点击率预测模型可以在线预测每个到访用户对每一个视频的点击概率, 并依据预测结果, 为用户推荐其最有可能点击的视频.
3 视频点击率预测算法 3.1 特征工程特征工程是本文算法的首要任务, 也是算法的重点.本文算法以各个特征的重要性为依据选择特征.特征重要性使用袋外数据(Out Of Bag, OOB)误差作为度量指标[17].首先, 基于Bagging方法构建
| $ \begin{align} F(x)=\dfrac{\sum^N_{i=1}({\rm errOOB2}_i(x)-{\rm errOOB1}_i(x))}{N}. \end{align} $ | (1) |
使用上述特征选择方法, 从原始数据中提取出对点击率预测重要的相关特征, 如表 2所示.
|
|
表 2 用户和视频特征 Tab.2 User and video features |
对于一些具有数值意义的特征, 例如用户活跃天数和用户年龄, 可以直接从原始数据中切分出来; 但是对于一些无数值意义的特征, 例如视频大类的编号(编号在数值上的大小没有意义), 或者字符串类型的特征, 例如演员、导演等, 需要对特征进行编码操作.特征编码采用一种类似于One-Hot Encoding[19]的操作.以本文所使用的数据集中用户感兴趣的演员标签为例:某用户感兴趣的演员在原始数据中如表 3所示, 其中, 用户感兴趣的演员用“#”隔开, “%”前面是演员名字, 后面是该用户喜欢该演员的权重值.
|
|
表 3 用户感兴趣的演员标签 Tab.3 Tags for actors of user-interest |
对于这种类型的特征, 首先需要预处理popular的值, 例如最受欢迎的100位演员.然后将这100个演员中的每一个当作特征向量中的一维特征, 特征的值为每个用户对该演员的喜爱程度.按照这种编码方式, 表 3中的演员标签将被编码成表 4所示的形式.
|
|
表 4 用户感兴趣的演员编码 Tab.4 Encoding of tags for actors of user-interest |
除了用户特征和视频特征, 用户和视频的组合特征对视频点击率的预测也是至关重要的.本文产生组合特征的方式为人工组合特征和基于矩阵分解产生组合特征.
(1) 人工组合交叉特征.可以将用户的兴趣偏好和视频的特征交叉生成新的特征.例如, 用户的演员偏好特征和视频的演员都经过特征编码, 形成了两个维数相同, 并且相应维度含义也相同的向量.通过计算这两个向量的相似度, 可以得到用户对于视频中演员喜欢程度的"综合分数", 该"综合分数"可以作为一个新的组合特征.
(2) 基于矩阵分解的组合特征.根据用户观看视频的记录生成用户观看视频时长的
|
图 2 基于矩阵分解生成组合特征 Fig.2 Schematic diagram for generating new features based on matrix factorization |
分别基于逻辑回归、梯度提升决策树-逻辑回归和因子分解机建立预测模型, 其中, 逻辑回归的优势是模型简单、易于实现且效率高.给定特征
| $ \begin{align} P(y=1|x)=\dfrac{1}{1+{\rm {e}}^{-g(x)}}, \end{align} $ | (2) |
其中
| $ \begin{align} g(x)=\omega_0+\omega_1x_1+\omega_2x_2+\omega_3x_3+\cdots+\omega_px_p=\theta^{\rm {T}}x. \end{align} $ | (3) |
梯度提升决策树是一种利用梯度提升方法集成多棵决策树的算法.其主要特点是能够处理高维非线性的数据, 并且解决了普通决策树算法容易出现过拟合的问题.其表达式为
| $ \begin{align} f_M(x)=\sum \limits^M_{m=1}T(x;\Theta_m), \end{align} $ | (4) |
其中,
梯度提升决策树-逻辑回归融合模型是一种将梯度提升决策树和逻辑回归相结合的一种模型, 通过梯度提升决策树, 可以发掘某些特征之间的潜在关系, 因此可以自动对某些特征进行交叉组合.利用梯度提升决策树的这一特点, 使用梯度提升决策树生成逻辑回归模型的输入特征.梯度提升决策树模型中, 每一棵决策树的每一个叶子节点维护逻辑回归的一维输入特征.对于每个样本, 只需找到其在梯度提升决策树中的路径, 就能将该样本转化为逻辑回归的输入特征.
因子分解机模型的特点是能够缓解数据的稀疏性带来的影响, 能自动发掘特征之间的关联.与逻辑回归类似, 对输入特征建立模型
| $ \begin{align} \Phi(\omega, x)=\omega_0+\sum \limits^{n}_{i=1}\omega_ix_i+\sum \limits^{n-1}_{i=1}\sum \limits^{n}_{j=i+1}\omega_{ij}x_ix_j. \end{align} $ | (5) |
式(5)中等号右边前两项与逻辑回归类似, 为普通的线性模型部分, 最后一项为交叉项部分,
| $ \begin{align} \Phi(\omega, x)=\omega_0+\sum\limits ^n_{i=1}\omega_ix_i+\sum\limits^{n-1}_{i=1} \sum\limits^{n}_{j=i+1}<v_i, v_j>x_ix_j. \end{align} $ | (6) |
可以注意到, 对于隐向量
模型建立好之后, 需要进行训练.如何产生训练样本也是点击率预测算法需要考虑的问题.原始数据集中含有用户点击视频的历史记录, 因此可以直接用来产生正例数据.但是负例数据的产生则要复杂很多.由于单个用户点击的视频数量极少, 因此负例数据的数量庞大, 远多于正例数据, 而且用户未点击的视频并不意味着用户不会点击这些视频.因此, 不能将所有未点击的视频作为负例样本用于训练.为了解决这个问题, 需要从未点击的视频中挑选出一部分最可能成为负例样本用于模型训练.
本文使用一种基于聚类的方法挑选负例样本.首先, 提取视频特征向量; 然后根据视频特征向量的欧氏距离将视频聚类, 分成
为了测试点击率预测算法的效果, 我们利用算法的预测结果为用户推荐视频:对于每个用户, 使用训练好的模型预测该用户对每个视频的点击概率, 然后将该用户最有可能点击的视频推荐给该用户, 并通过用户点击视频的记录计算推荐的成功率.推荐的流程如图 3所示, 当用户访问视频网站时, 获取用户特征、视频特征和它们的组合特征, 计算用户点击视频的概率, 根据预测的点击概率, 向用户推荐视频.
|
图 3 为用户推荐视频 Fig.3 Workflow for recommending videos to users |
本实验使用的数据集为腾讯用户观看视频的真实行为数据, 其中包含147 213个用户和67 027个视频的数据, 用户数据中包括新注册的用户.此外, 数据集中还包括30 849 964条用户观看记录.将其中观看时长不足5 min的无效观看记录去除后, 还剩下19 389 876条观看记录.
4.2 评价指标分别使用精度(Precision)、召回率(Recall)、F1-Score、对数损失(Log loss)、AUC (Area UnderCurve), 以及时间效率作为算法的评价指标.精度的定义为, 点击率预测算法预测用户会点击的视频中, 被用户真正点击的视频比例, 即
| $ \begin{align} P=\dfrac{TP}{TP+FP}, \end{align} $ | (7) |
其中,
召回率为用户实际点击的视频中被预测正确的视频比例, 即
| $ \begin{align} R=\dfrac{TP}{TP+FN}. \end{align} $ | (8) |
F1-Score为综合考虑精度和召回率的一个指标, 其表达式为
| $ \begin{align} F1=\dfrac{2\times P\times R}{P+R}. \end{align} $ | (9) |
对数损失的计算公式为
| $ \begin{align} {\rm Log\; loss}=-\dfrac{1}{n}\sum^n_{i=1}(y_i\log(p_i)+(1-y_i)\log(1-p_i)), \end{align} $ | (10) |
其中,
通过将本文算法的预测结果与朴素贝叶斯(Naive Bayes, NB)算法和决策树(Decision Tree, DT)算法的预测结果对比来验证本文算法的效果.为了验证加入组合特征的作用, 我们分别在加入组合特征和不加入组合特征两种情况下测试算法的性能.
在实际应用中, 单个用户点击视频的数量普遍较少, 数据的正负样本比例会极度不平衡, 因此我们分别使用正负样本比例为1:300和1:2 000的测试数据集测试算法效果.
训练集正负样本比例为1:10, 测试集正负样本比例为1:300, 仅使用用户特征和视频特征而不加入组合特征.基于因子分解机(FM)的点击率预测模型、基于梯度提升决策树-逻辑回归(GBDT+LR)的点击率预测模型和基于逻辑回归(LR)的点击率预测模型的预测效果如表 5所示. 表 5中还包括相同训练数据和测试数据下, 朴素贝叶斯(NB)算法和决策树(DT)算法的预测效果.
|
|
表 5 实验结果1 Tab.5 Result 1 |
图 4为本文3种模型以及朴素贝叶斯(NB)算法和决策树(DT)算法预测结果的ROC(Receive Operation Characteristic)曲线.
|
图 4 ROC曲线一 Fig.4 ROC curve 1 |
训练集正负样本比例为1:10, 测试集正负样本比例为1:2 000, 仅使用用户特征和视频特征而不加入组合特征.基于因子分解机(FM)的点击率预测模型、基于梯度提升决策树-逻辑回归(GBDT+LR)的点击率预测模型和基于逻辑回归(LR)的点击率预测模型的预测效果如表 6所示. 表 6中还包括相同训练数据和测试数据下, 朴素贝叶斯(NB)算法和决策树(DT)算法的预测效果.
|
|
表 6 实验结果2 Tab.6 Result 2 |
本文3种模型以及朴素贝叶斯(NB)算法和决策树(DT)算法预测结果的ROC曲线如图 5所示.
|
图 5 ROC曲线二 Fig.5 ROC curve 2 |
从以上两组实验可以看出, 本文所提出的点击率预测算法表现良好.基于梯度提升决策树-逻辑回归的模型和基于因子分解机的模型, 在点击率预测效果方面要优于基于逻辑回归的模型, 但基于逻辑回归的算法时间复杂度较低.通过对比两组实验的结果发现, 面对正负样本比例不平衡的数据时, 很多负例样本会被预测成正例, 这会导致如下情况:尽管召回率较高, 但是精度和F1-Score会很低.这说明在正负样本极度不平衡的情况下, 点击率预测是一个非常困难的问题.本文算法在正负样本不平衡的情况下依然能够有较好的表现.
在用户特征和视频特征的基础上, 加入用户和视频的组合特征.在训练集正负样本比例为1:10, 测试集正负样本比例为1:300的情况下, 基于因子分解机(FM)的点击率预测模型、基于梯度提升决策树-逻辑回归(GBDT+LR)的点击率预测模型和基于逻辑回归(LR)的点击率预测模型的预测效果如表 7所示.
|
|
表 7 实验结果3 Tab.7 Result 3 |
通过对比实验结果3和实验结果1发现, 加入组合特征后, 基于3种不同模型的算法效果都有了显著的提升.由此可知, 在点击率预测问题中, 特征工程非常关键, 尤其是特征之间的交叉组合, 对点击率预测算法的效果有十分重要的影响.
基于本文所提出算法的点击率预测结果, 为每个用户推荐其最有可能点击的视频.分别为点击视频的总次数大于20、30、40和60次的用户推荐视频, 推荐的成功率如表 8所示.
|
|
表 8 推荐成功率 Tab.8 Accuracy of recommendations |
我们对特征进行重要性分析, 发现组合特征、用户兴趣偏好以及视频类型对视频点击率预测较为重要, 并且预测不同类型视频的点击率, 各个特征的重要性也不相同.预测电影的点击率时, 导演特征和演员特征的重要性基本相同; 而预测电视剧的点击率时, 导演特征的重要性远低于演员特征的重要性.基于以上分析, 我们将电影和电视剧从视频数据中分离出来, 分别做推荐, 推荐的成功率如表 9所示.
|
|
表 9 推荐电影和推荐电视剧的成功率 Tab.9 Accuracy of movie and TV recommendations |
从表 9可以看出, 将电影和电视剧分别做推荐, 成功率略有提高.
5 总结本文基于特征工程和3种机器学习的模型实现了一种视频点击率预测算法.算法利用特征工程的方法提取用户特征和视频特征, 并将用户特征和视频特征交叉组合, 且分别基于逻辑回归、梯度提升决策树-逻辑回归和因子分解机实现点击率预测模型.本文算法在正负例样本不平衡且数据较为稀疏的情况下依然表现良好.未来可以在特征工程方面进行更多的工作, 从而提高视频点击率预测算法的性能.
| [1] | RENDLE S. Factorization machines[C]//IEEE International Conference on Data Mining. IEEE Computer Society, 2010: 995-1000. |
| [2] | FRIEDMAN J H. Greedy function approximation:A gradient boosting machine[J]. Annals of Statistics, 2001, 29(5): 1189-1232. |
| [3] | HE X, PAN J, JIN O, et al. Practical lessons from predicting clicks on ads at Facebook[C]//Proceedings of the 8th International Workshop on Data Mining for Online Advertising. ACM, 2014: 1-9. |
| [4] | 纪文迪, 王晓玲, 周傲英. 广告点击率估算技术综述[J]. 华东师范大学学报(自然科学版), 2013(3): 1-14. |
| [5] | RICHARDSON M, DOMINOWSKA E, RAGNO R. Predicting clicks: Estimating the click-through rate for new ads[C]//International Conference on World Wide Web. ACM, 2007: 521-530. |
| [6] | CHAPELLE O, ZHANG Y. A dynamic bayesian network click model for web search ranking[C]//International Conference on World Wide Web. ACM, 2009: 1-10. |
| [7] | GRAEPEL T, CANDELA J Q, BORCHERT T, et al. Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft's Bing Search engine[C]//International Conference on Machine Learning. DBLP, 2010: 13-20. |
| [8] | JOACHIMS T. Optimizing search engines using click-through data[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2002: 133-142. |
| [9] | SHAN L, LIN L, SUN C, et al. Predicting ad click-through rates via feature-based fully coupled interaction tensor factorization[J]. Electronic Commerce Research & Applications, 2016, 16(C): 30-42. |
| [10] | YAN L, LI W J, XUE G R, et al. Coupled group lasso for web-scale CTR prediction in display advertising[C]//International Conference on Machine Learning. 2014: 802-810. |
| [11] | AGARWAL D, LONG B, TRAUPMAN J, et al. LASER: A scalable response prediction platform for online advertising[C]//ACM International Conference on Web Search and Data Mining. ACM, 2014: 173-182. |
| [12] | AQUIAR E, NAGRECHA S, CHAWLA N V. Predicting online video engagement using clickstreams[C]//IEEE International Conference on Data Science and Advanced Analytics (DSAA). IEEE, 2015. DOI: 10.1109/DSAA.2015.7344873. |
| [13] | 李思琴, 林磊, 孙承杰. 基于卷积神经网络的搜索广告点击率预测[J]. 智能计算机与应用, 2015(5): 22-25. |
| [14] | SCHAPIRE R E. A brief introduction to boosting[C]//16th International Joint Conference on Artificial Intelligence. [S. l. ]: Morgan Kaufmann Publishers Inc, 1999: 1401-1406. |
| [15] | QUINLAN J R. Induction on decision tree[J]. Machine Learning, 1986(1): 81-106. |
| [16] | HARTIGAN J A, WONG M A. Algorithm AS 136:A k-means clustering algorithm[J]. Applied Statistics, 1979, 28(1): 100-108. DOI:10.2307/2346830 |
| [17] | BREIMAN L. Out-of-bag estimation[R]. Berkeley: University of California, 1996. |
| [18] | BREIMAN L. Bagging Predictors[M]. [S.l.]: Kluwer Academic Publishers, 1996. |
| [19] | CHEN T, GUESTRIN C. XGBoost: A scalable tree boosting system[C]//ACM SIGKDD International Conference. ACM, 2016: 785-794. |