基于用户行为的广告点击率预测框架及算法

本发明涉及一种广告点击率预测算法，尤其涉及一种基于用户行为的广告点击率预测框架及算法。

互联网的快速发展，为广告业提供了广阔的平台。互联网广告[1-2]具有受众范围广、交互性强、实时灵活等优点，使得广告行业逐渐向其倾斜。互联网广告可以利用用户上网行为，挖掘用户兴趣，达到广告的精准推送，既提升了用户体验，又带来了经济效益。点击率预测算法是广告系统的核心算法之一，是基于会话日志在给定用户查询与广告时，预测用户点击广告的概率。

准确的广告点击率预测会给用户带来良好的体验，也会给网站拥有者和广告商带来更大的经济效益[3-5]，因此，无论是工业界中还是学术界中，都出现了越来越多的计算广告的研究者。MJ Effendi[6]等人提出了基于线性回归的上下文广告点击率预测算法，该算法利用上下文信息对广告间的相互影响进行建模，利用聚类算法辅助计算文本相似度，该算法简单高效，易于调参，但很难学习特征之间的复杂关系。Y Juan[7]等人提出了基于域的因子分解机的在线广告点击率预测算法，该算法能够解决数据稀疏性问题，但模型参数较多，模型效率较低，同时，很难学习特征之间的高阶关系。N Yin[8]等人采用基于MapReduce的耦合逻辑回归模型对广告点击率进行预测，该算法利用MapReduce的分而治之思想来处理大量稀疏数据，同时，利用基于方向导数的拟牛顿优化方法来处理非凸非光滑数据集，但模型很难学习特征间的复杂关系。H Guo[9]等人采用基于因子分解机与神经网络的融合模型对广告点击率进行预测，该算法利用因子分解机的特性和神经网络的体系结构，来学习特征之间的复杂关系，提高模型预测准确率。

目前研究存在以下难点[10-12]：1、广告点击日志文件数据量大且增长较快；2、广告点击日志文件包含大量取值较多的类别特征；3、广告点击率数值较小且呈长尾分布，同时，存在类别不平衡问题；4、很难基于某种假设对兴趣漂移现象建模。

本发明为了解决上述问题而提供一种基于用户行为的广告点击率预测框架及算法。

本发明通过以下技术方案来实现上述目的：

本发明首先采用基于K_Means模型的下采样算法来解决类别不平衡问题，然后，采用启发式思维对特征进行特征分类，再然后，利用梯度提升树对感性特征进行特征组合，最后，将组合后的特征与理性特征按一定权重输入逻辑回归模型进行广告点击率预测；

特征提取:

基于实验数据集及实际业务分析，进行特征提取工作，目的是降低特征冗余度和特征稀疏性以及提高特征表达性；主要特征如下：

查询相关度:

本发明文本特征属于短文本且经过加密处理，同时，广告关键字、广告标题、广告描述互为强相关，所以，本发明采用Dice系数、Jaccard距离、tf_idf来联合计算文本相似度；

Dice系数计算公式如公式1所示：

其中，comm(t,t)表示文本1与文本2的共同部分，len(t)表示文本1的总词数；

Jaccard距离计算公式如公式2所示：

其中，comm(t,t)表示文本1与文本2的共同部分，union(t,t)表示文本1与文本2去重后的总词数；

tf_idf计算公式如公式3所示：

其中，count(w,t)表示查询词在文本中出现的次数，size(t)表示文本的总词数，tf(w,t)表示词频，idf表示逆文本频率；

最终相似度计算公式如公式(4)所示；

sim＝α*dice+β*Jaccard+λ*tf_idf (4)

网站吸引度:

网站吸引度是指展示在特定网站上广告的点击率的方差；计算公式如公式(5)所示；

其中，表示展示在网站上广告的平均点击率，ctr表示网站i的广告点击率；

广告商宣传力度:

广告商宣传力度是指特定广告商所投放广告的点击率方差；计算公式如公式(6)所示；

其中，表示广告商所投放广告的平均点击率，ctr表示网站i的广告点击率；

广告位置:

广告位置是指广告实际位置；基于数据分析，广告点击率与广告实际位置呈负相关，与广告相对位置呈非相关；

广告受众分析：

广告具有定向性，即每个广告都有自己的目标体；本发明将特定广告下点击次数最多的年龄、性别作为广告受众的年龄、性别；

广告点击率：

广告点击率是指在给定用户与广告时，预测用户点击广告的概率；计算公式如公式7所示；

其中，clicks表示广告的实际点击次数，impression表示广告的总展示次数；

基于实际业务分析，理性特征包括用户查询相关性和广告展示位置分，感性广告包括网站吸引度、广告商宣传力度、性别、年龄、受众性别、受众年龄以及广告深度；

认为每个用户都是感性与理性的混合体，而感性与理性的占比会随时间地点环境发生变化；为了更加准确地定位用户，本发明将特征分为两个互不相交的特征集合，然后基于用户输入查询词的详细程度来衡量特征集权重；

理性特征集权重计算公式如公式8所示；

感性特征集权重计算公式如公式9所示；

其中，qNum表示用户i输入的查询词个数，kNum表示待点击广告j所包含的关键字个数，w1表示在给定用户i和待点击广告j时，理性特征集的权重，w2表示在给定用户i和待点击广告j时，感性特征集的权重。

本发明的有益效果在于：

本发明是一种基于用户行为的广告点击率预测框架及算法，与现有技术相比，本发明具有如下技术效果：1、为降低特征冗余度和稀疏性，将ID类特征与其他特征联合转换为有意义的数值特征；2、为提高文本特征的计算准确率，采用三种不同的方法进行文本相似度计算；3、为缓解类别不平衡问题，提出了基于K_Means模型的下采样算法；4、为提高特征表达性和处理大量稀疏数据，采用梯度提升树与逻辑回归的融合模型进行广告点击率预测；5、利用用户输入查询词的详细程度来实时预测用户发生兴趣漂移的概率。

将ID类特征与其他特征在不同层次上进行联合转换为有意义的数值特征，该特征能降低特征稀疏性和冗余度以及提高特征表达性；同时，为进一步提高特征表达性，本发明利用了GBDT模型进行特征选择与特征组合，利用LR模型来处理高维特征；最后为解决类别不平衡问题，本发明提出了基于K_Means模型的下采样算法。实验过程中，首先对原始特征进行特征提取，然后采用启发式思维进行特征分类，将感性特征输入GBDT模型进行特征组合，最后，将理性特征与组合特征以一定的权值输入LR模型进行广告点击率预测。实验结果表明，本发明算法在RMSE与R2指标上均有改善。

图1是本发明的算法框架图

图2是本发明的不同k值下DBI的变化曲线图

图3是本发明的不同采样比例下rmse和r2的变化曲线图

图4是本发明的不同学习速率与基学习器个数下测试集

(a)损失函数为huber，最大特征数为sqrt；(b)损失函数为ls，最大特征数为all；(c)损失函数为ls，最大特征数为sqrt；

图5是本发明的不同最大树深度下rmse的变化曲线；

图6是本发明的不同叶子节点最少样本数下rmse的变化曲线；

图7是本发明的不同内部节点再划分所需最小样本数下rmse的变化曲线；

图8是本发明的不同特征下的rmse对比条形图；

图9是本发明的不同特征下的R2对比条形图；

图10是本发明的在不同数据集下RMSE对比条形图；

图11是本发明的在不同数据集下R2对比条形图；

图12是本发明的不同算法下RMSE和R2对比条形图。

下面结合附图对本发明作进一步说明：

算法框架

本发明首先采用基于K_Means模型的下采样算法来解决类别不平衡问题，然后，采用启发式思维对特征进行特征分类，再然后，利用梯度提升树对感性特征进行特征组合，最后，将组合后的特征与理性特征按一定权重输入逻辑回归模型进行广告点击率预测。本发明算法框架如图1所示。

特征提取：

本发明基于实验数据集及实际业务分析，进行特征提取工作，目的是降低特征冗余度和特征稀疏性以及提高特征表达性。主要特征如下：

查询相关度：

本发明文本特征属于短文本且经过加密处理，同时，广告关键字、广告标题、广告描述互为强相关，所以，本发明采用Dice系数、Jaccard距离、tf_idf来联合计算文本相似度。

Dice系数计算公式如公式1所示：

其中，comm(t,t)表示文本1与文本2的共同部分，len(t)表示文本1的总词数。

Jaccard距离计算公式如公式2所示：

其中，comm(t,t)表示文本1与文本2的共同部分，union(t,t)表示文本1与文本2去重后的总词数。

tf_idf计算公式如公式3所示：

其中，count(w,t)表示查询词在文本中出现的次数，size(t)表示文本的总词数，tf(w,t)表示词频，idf表示逆文本频率。

最终相似度计算公式如公式(4)所示。

sim＝α*dice+β*Jaccard+λ*tf_idf (4)

网站吸引度：

网站吸引度是指展示在特定网站上广告的点击率的方差。计算公式如公式(5)所示。

其中，表示展示在网站上广告的平均点击率，ctr表示网站i的广告点击率。

广告商宣传力度：

广告商宣传力度是指特定广告商所投放广告的点击率方差。计算公式如公式(6)所示。

其中，表示广告商所投放广告的平均点击率，ctr表示网站i的广告点击率。

广告位置：

广告位置是指广告实际位置。基于数据分析，广告点击率与广告实际位置呈负相关，与广告相对位置呈非相关。

广告受众分析：

广告具有定向性，即每个广告都有自己的目标体。本发明将特定广告下点击次数最多的年龄、性别作为广告受众的年龄、性别。

广告点击率：

广告点击率是指在给定用户与广告时，预测用户点击广告的概率。计算公式如公式7所示。

其中，clicks表示第i广告的实际点击次数，impression表示第i广告的总展示次数。

基于实际业务分析，理性特征包括用户查询相关性和广告展示位置分，感性广告包括网站吸引度、广告商宣传力度、性别、年龄、受众性别、受众年龄以及广告深度。

本发明认为每个用户都是感性与理性的混合体，而感性与理性的占比会随时间地点环境发生变化。为了更加准确地定位用户，本发明将特征分为两个互不相交的特征集合，然后基于用户输入查询词的详细程度来衡量特征集权重。

理性特征集权重计算公式如公式8所示。

感性特征集权重计算公式如公式9所示。

其中，qNum表示用户i输入的查询词个数，kNum表示待点击广告j所包含的关键字个数，w1表示在给定用户i和待点击广告j时，理性特征集的权重，w2表示在给定用户i和待点击广告j时，感性特征集的权重。

基于K_Means模型的下采样算法：

由数据分析可得，本发明训练样本正负样本比例为1:8，属于类别不平衡。本发明提出了基于K_Means模型的下采样算法，从数据层面解决类别不平衡问题，同时，缓解了由下采样造成的有用信息丢失问题。

待聚类簇数参数实验：

本发明先采用K_Means模型对大众类样本聚类，目的是学习大众类样本的分布特性。不同k值下DBI的变化曲线图如图2所示。

由图2所得，当K为3时，DBI值最小为0.551。所以，在后续的随机下采样率参数实验过程中，将待聚类簇数设置为3。

下采样率参数实验：

本发明通过随机下采样算法和GBDT_LR模型进行下采样率参数实验。不同采样比例下rmse和r2的变化曲线图如图3所示。

由图3所得，当下采样率为0.28时，GBDT_LR模型效果最好，此时，训练集中正负样本的数量比例为1:2。

梯度提升树+逻辑回归：

本发明利用GBDT的结构特性进行特征选择和组合，利用LR模型来处理大量稀疏数据，目的是提高模型预测准确率和模型训练效率。

GBDT模型参数实验：

在GBDT模型参数训练部分，本发明先进行过程参数训练，再进行基分类器参数训练。

1)GBDT模型的过程参数实验

测试集在不同学习速率与迭代次数下的rmse变化曲线图如图4所示。

由图4所得，当GBDT模型的损失函数为ls，最大特征数为sqrt，学习率为0.05，基分类器个数为700时，此时，模型效果最好。

2)GBDT模型的基分类器参数实验

在损失函数为ls，最大特征数凭为sqrt，学习率为0.05，基分类器个数为700下，RMSE在不同树深度、叶子节点最少样本、内部节点再划分所需最小样本数的变化曲线图如图5-7所示。

由图5-7所得，当GBDT模型的最大树深度为8，叶子节点最少样本数为25，内部节点再划分所需最小样本数为20，此时，模型效果最好。

实验：

实验数据：

本发明数据是腾讯搜搜的广告点击日志文件。具体的数据描述如表1所示。

表1字段描述

由数据分析及实际业务分析可得，本发明原始数据中存在未知用户和误点情况。本发明对数据清理后的数据进行了统计性分析。不同类别下的样本数统计表如表2所示。

表2不同类别下的记录数

算法实验

参数设置：

本发明参数由基于K_Means模型的下采样算法参数实验和GBDT参数实验可得。本发明参数列表如表3所示。

表3本发明参数列表

对比算法：

为了验证本发明算法的有效性，本发明选择了2个传统算法和3个流行算法进行性效果对比实验。对比算法及参数设置如下所示。

逻辑回归算法：最大迭代次数为700，学习率为0.05。

梯度提升树：最大子模型数为700，学习率为0.05，损失函数为均方误差函数，划分时考虑的最大特征数为总特征数的平方根，决策树最大深度为8，内部节点再划分所需最小样本数为20，叶子节点最少样本数为25。

文献4(FNN算法)：输入层12个节点，第一层隐藏层300个节点，第二层隐藏层100个节点，输出层1个节点，学习率为0.05，输入层节点的激活函数为linear函数，隐藏层激活函数为sigmoid函数。

文献5(GBDT_LR算法)：最大子模型数为700，学习率为0.05，损失函数为均方误差函数，划分时考虑的最大特征数为总特征数的平方根，决策树最大深度为8，内部节点再划分所需最小样本数为20，叶子节点最少样本数为25。

文献7(FFM算法)：学习率为0.05，损失函数为Logloss，迭代次数为700。2.2.3评价指标

均方根误差是点击率的预测值与真实值差值的平方和，除以测试集大小后的平方根，其能衡量预测值的离散程度，从而能度量算法预测的稳定性。RMSE指标计算公式如公式4所示。

R2指标就是将模型预测的数值与不使用模型进行预测而用均值作为预测值的方法，进行误差对比，以此来衡量模型的预测能力。R2指标计算公式如公式5所示。

其中，tctr表示样本i的预测点击率，pctr表示样本i的真实点击率，n表示测试集的样本个数。

实验结果：

本发明先从特征提取和类别不平衡两个角度验证本发明处理有效性，最后，验证本发明算法-基于用户行为的广告点击率预测算法的有效性。

1)特征提取

本发明采用逻辑回归算法、随机森林算法、梯度提升树算法、线性回归算法和GBDT_LR算法，从RMSE和R2上验证本发明特征提取有效性。

由上图所得，新特征在RMSE、R2方面优于原始特征，说明了本发明特征处理的有效性。

2)类别不平衡

本发明采用逻辑回归算法、梯度提升树算法、GBDT_LR算法、FMM算法、FNN算法，从RMSE和R2上验证基于K_Means模型的下采样算法的有效性。

由上图所得，采用基于K_Means模型的下采样算法处理后的数据集在RMSE、R2方面优于原始数据集，说明了基于K_Means模型的下采样算法的有效性。

3)本发明算法

本发明采用逻辑回归算法、梯度提升树算法、GBDT_LR算法、FMM算法、FNN算法，从RMSE和R2上验证本发明算法的有效性。

由上图所得，本发明算法在RMSE、R2方面优于前人算法以及经典算法，说明了本发明算法的有效性。

结束语：

本发明基于目前研究难点，首先根据实验数据及实际业务分析，进行特征提取工作，目的是降低特征冗余度与特征稀疏性以及提高特征表达性；然后，基于用户行为分析，通过用户输入查询词的详细程度来实时预测用户发生兴趣漂移的概率；然后，提出了基于K_Means模型的下采样算法，目的是缓解由下采样所造成的有用信息丢失问题和类别不平衡问题；再然后，利用GBDT模型进一步进行特征选择与特征组合，提高特征表达性；最后，利用逻辑回归模型处理大量高维数据。

因为本发明利用GBDT模型来学习特征间的复杂关系，所以，当处理大规模训练数据时，本发明算法的时间性能较差。基于上述分析，未来工作将集中于两个部分，一是特征引用方面，主要考虑用户历史点击信息；二是时间性能方面，主要考虑限制LR模型的输入特征-即GBDT的叶子节点个数。

参考文献：

[1]刘庆振.“互联网+”时代的计算广告学:产生过程,概念界定与关键问题[J].新闻知识,2016(6):9-15.

[2]McMahan H B,Holt G,Sculley D,et al.Ad click prediction:a view fromthe trenches[C]//Proceedings of the 19th ACM SIGKDD international conferenceon Knowledge discovery and data mining.ACM,2013:1222-1230.

[3]Gai K,Zhu X,Li H,et al.Learning Piece-wise Linear Models fromLarge Scale Data for Ad Click Prediction[J].2017.

[4]Zhang W,Du T,Wang J.Deep learning over multi-field categoricaldata[C]//European conference on information retrieval.Springer,Cham,2016:45-57.

[5]He X,Pan J,Jin O,et al.Practical lessons from predicting clicks onads at facebook[C]//Proceedings of the Eighth International Workshop on DataMining for Online Advertising.ACM,2014:1-9.

[6]Effendi M J,Ali S A.Click Through Rate Prediction for ContextualAdvertisment Using Linear Regression[J].arXiv preprint arXiv:1701.08744,2017.

[7]Juan Y,Lefortier D,Chapelle O.Field-aware Factorization Machinesin a Real-world Online Advertising System[J].2017.

[8]Yin N,Li H,Su H.CLR:coupled logistic regression model for CTRprediction[C]//ACM Turing,Celebration Conference-China.ACM,2017:21.

[9]Guo H,Tang R,Ye Y,et al.Holistic Neural Network for CTR Prediction[C]//Proceedings of the 26th International Conference on World Wide WebCompanion.International World Wide Web Conferences Steering Committee,2017:787-788.

[10]Ling X,Deng W,Gu C,et al.Model Ensemble for Click Prediction inBing Search Ads[C]//International Conference on World Wide WebCompanion.International World Wide Web Conferences Steering Committee,2017:689-698.

[11]An experimental comparison of three methods for constructingensembles of decision trees:Bagging,boosting,and randomization[J].

Machine learning,2000,40(2):139-157.

Xia Y,Liu C,Li Y Y,et al.A boosted decision tree approach usingBayesian hyper-parameter optimization for credit scoring[J].Expert Systemswith Applications,2017,78:225-241.

以上显示和描述了本发明的基本原理和主要特征及本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。