《RTB实时竞价算法》由会员分享，可在线阅读，更多相关《RTB实时竞价算法（10页珍藏版）》请在金锄头文库上搜索。
1、1.算法简介41.1算法用途41.2算法概述42.算法详细说明52.1广告活动匹配52.2实时竞价算法63.算法改进方向123.1特征属性的选择123.2点击率预测123.3竞价调整方式124.补充问题124.1无历史数据阶段124.2利用历史数据阶段124.3展示的分布控制135.参考文献146.附件156.1名词156.2算法总体流程图166.3输入输出表166.4数据预处理流程186.5计算权重算法流程206.6模型检验231. 算法简介1.1 算法用途RTB（Real-Time Bidding）实时竞价，是一种利用第三方技术在数以百万计的媒体上针对每一个用户展示行为进行评估以及出价的竞
2、价技术。与大量购买投放频次不同，实时竞价规避了无效的受众到达，只针对有意义的用户进行购买。它的核心是DSP平台（需求方平台），在DMP数据的支持下根据媒体，广告特点和人的属性进行定向投放。RTB对于媒体来说，可以带来更多的广告销量、实现销售过程自动化及减低各项费用的支出。而对于广告商和代理公司来说，最直接的好处就是提高了效果与投资回报率。RTB算法有几种常见的策略：展现优化（针对品牌推广）目标，点击率（CTR）优化目标和ROI(投资回报率)优化目标。其核心都是要做到合适的广告展现给合适的人。ROI优化是最直接能体现广告主的投资收益率的指标，但是目前情况下受RTB业界技术限制和公司数据支持情况的
3、限制，点击率优化是现实可行的RTB竞价方法。虽然该方法不能直接体现在用户的投资收益率指标上，但是优良的点击率很大程度上会带来良好的收益。目前针对RTB算法中的点击率预测有很多种方法，如：逻辑回归，决策树，两阶段广义线性模型，非线性规划模型，典型方程等。选用逻辑回归的主要原因在于该算法成熟，对输入变量要求较低，既可以处理枚举型变量，又可以处理连续型变量。输出结果较稳定可靠。本算法主要以点击率（CTR）为优化目标，并选择逻辑回归作为主模型进行设计。1.2 算法概述首先对RTB的竞价流程总结如下图所示：图1 RTB竞价流程图从上图中可以看出，实时竞价算法的输入主要包括以下信息：1） Exchange
4、端提供的广告位信息；2） 用户id， DMP收集的用户属性信息；3） 广告主发布的活动信息及竞价策略；4） 竞价历史（媒体信息，广告位，获胜竞价，用户id等）。表1: RTB算法输入之竞价历史广告 媒体信息用户ID时间戳是否点击是否成功报价成交价格创意类型权重尺寸实时竞价算法的输出主要是获胜的(广告活动信息，竞价)组。实时竞价算法主要由两部分构成，一是广告活动的匹配，二是根据媒体，广告活动及用户属性等进行出价。图2 RTB竞价算法流程2. 算法详细说明2.1 广告活动匹配广告活动匹配的目的是为了筛选出满足媒体广告位要求，以及符合用户属性特征的广告活动集合。首先，根据请求中的媒体广告位信息对广告
5、活动进行初步筛选，过滤掉一些无效的广告活动，如：不满足广告位要求的广告活动等。然后，利用DMP系统中查找到的用户特征信息，以及广告活动的投放人群属性定向再次筛选广告活动。广告活动的投放人群属性定向主要包括访客所在地区，年龄，性别，婚姻状况，教育程度，兴趣爱好，购买偏好等。主要包括以下步骤：第一步，将请求中的媒体广告位信息与DSP系统中的广告活动信息进行初步匹配，筛选出满足条件的广告活动集合；如果不存在广告活动，则不参与此次请求的竞价。第二步，利用DMP系统，根据用户id，获取用户特征信息。第三步，将筛选出的广告活动集合与用户特征进行匹配，进一步筛选广告活动集合。图3 广告匹配流程表2 广告活动
6、匹配需要考虑的信息广告位信息广告活动用户属性属性1广告位宽投放媒体偏好性别属性2广告位高访客所在地区年龄属性3不允许的属性id集合访客年龄地域属性4允许的广告技术类别访客性别婚姻属性5排除的敏感类别访客婚姻状况教育程度属性6排除的产品类别访客教育程度兴趣属性7媒体提供的限制列表访客兴趣爱好属性8访客购买偏好 关于匹配度的计算问题涉及到商业策略及广告本身估值，用户的估值，媒体的估值及DSP端广告集合的分析等情况，在综合分析的情况下，才能给出在特定商业策略上的匹配度，该部分计算放在后续进行。2.2 实时竞价算法通过广告匹配算法能够筛选出符合媒体信息和用户特征的广告活动，接下来需要对筛选出的广告活动
7、进行竞价，并排序，返回一系类(广告活动，竞价)结果组。广告活动的投放类型一般有CPC和CPM两种，目前只考虑CPC投放类型，如果是投放类型是CPM，可以将CPM转化为CPC进行竞价，转换原则为：CPM = CPC*CTR*1000总体来说，实时竞价算法可以分为以下两个步骤：1. 获得每次广告展示的价值，即在给定的相关展现水平和需求数据的情况下，对该次广告展现预期成本，表示形式如下： 其中表示每次展现的预期成本，即最优竞价估值。在给定的广告系列中是已设定的常数。预测CTR是一个关键的步骤：其中条件中的impression包括了与该次展示机会相关的数据，比如用户信息；campaign包括了广告活动
8、的相关数据。 2实时竞价的调整根据竞价策略以及历史竞价数据调整实际竞价。2.2.1 广告展示估值为了准确地评估每次广告展示的价值，需要对该广告的点击率进行预测。初次使用系统时，由于缺乏获胜的历史竞价信息，可以使用默认的点击率，如：该品牌往常的点击率或其他平台媒体经验值等。随着历史数据的增加，需要根据用户和媒体等信息，对每次展示机会预测点击率。当获得足够多的历史数据时，可以利用媒体特征信息（如：广告位置等），用户特征（如：年龄，兴趣等），广告活动特征（如：创意，关键字等）构建点击率预测模型。由于特征属性信息非常多，首先需要进行属性特征提取，获得有价值的属性特征。然后根据历史数据，构建点击率预测模
9、型。当获得一个展示机会的时候，针对每个广告活动，根据用户和媒体的属性值进行点击率预测。图4 点击率预测流程2.2.1.1 特征提取在一个广告系统中，每一次出价和服务事件，包括广告机会，拍卖的获胜者，以及浏览该广告展现的用户都能够被记录。每一个广告机会通过其属性进行描述，包括url，出版商，广告位置以及用户统计信息，geo位置信息。获胜信息包括获胜的竞价值，实际的花费等。通常，有很多的目标属性值。它们中的大多数是复杂的布尔逻辑规则来匹配广告商想作为目标的广告库存，作为竞价需要考虑的因素也不应过多，造成算法的复杂程度过大，难以满足实时竞价的时间要求。因此，特征选择是系统中至关重要的一个因素。在选择
10、特征的时候，有两个方面的方法可以选用。1） 经验法。通过对行业的了解及属性的分析，对属性进行筛选。2） 采用适当的算法对属性对竞价的影响进行分析，计算每个属性对竞价的影响程度。选择影响因素大的属性作为特征属性。表3 需要考虑的特征属性信息广告位信息广告活动用户属性属性1媒体id投放类型性别属性2广告所属频道活动创意年龄属性3广告位宽广告主id地域属性4广告位高广告类型兴趣属性5广告位的可视性活动人群属性消费水平属性6地理信息投放媒体偏好我们采用基于过滤的Fast-Correlation(FCBF)方法选择特征子集1，该方法对处理特征数目较大时非常有效。其基本原理描述如下：设数据集D有n条记录，
11、且每条记录由m个非目标特征和一个目标特征C来刻画。如果非目标特征与目标特征之间的相关性过低（给定阈值），则将该特征作为不相关特征去除，如果两个非目标特征之间的相关性过大，超过了这两个特征与目标特征的相关性时，则认为两个特征之间存在冗余，这两种情况均需要进行删除。FCBF是一个确定性算法来消除与目标值相关度较低的属性或非目标属性过度相关的属性冗余。它能使我们在很大程度上消减特征搜索时间。它依据对称不确定性计算特征和目标值的相关性，定义如下：其中是信息增益（Information Gain），是熵（Entropy）。的值是给带来的信息增益，并且。是的一个归一化值。通过对目标属性与非目标属性及非目标
12、属性之间SU的计算，在给定的阈值基础上，进行属性选择。2.2.1.2 点击率预测在特征子集选择的基础上，对点击率进行预测。点击率预测问题可以看成是一个分类问题，把(媒体，广告活动，用户)看成是一个多元组，针对每一个多元组，有一个预测目标，是否点击。该问题可以看成是一个典型的逻辑回归问题。假设有n个训练样本集，其中表示由多元组（媒体，广告活动，用户）属性值构成的一个d维向量， 是相应的分类标签(+1，点击，或者0：没有点击)。给定一个媒体p，广告活动a，以及用户u，需要计算点击的概率。采用逻辑回归模型，表示形式如下：其中表示从多元组获得的第个属性的值，w关于它的权重。给定训练样本集合，模型通过减
13、少数据中的总损失计算权重向量w，公式如下：可以用L-BFGS算法3求解这种大规模的凸优化问题。具体方法如下。L-BFGS算法步骤如下：Step1:选初始点，允许误差，存储最近迭代次数m（一般取6）；Step2:；其中：令，则。Step3:如果，则返回最优解，否则转Step4；(注：)Step4:计算本次迭代的可行方向：；Step5:计算步长，对下面式子进行Backtracking线性搜索：；Step6:更新权重：；Step7:如果 ，只保留最近次的向量对，需要删除；Step8: 计算并保存：，；Step9:用two-loop recursion算法近似计算；k=k+1，转Step3。two-l
14、oop recursion算法:令，步骤1：对，循环以下运算：，；步骤2：；步骤3：对，循环以下运算：，。其中：，Backtracking线性搜索算法：任选，令，重复直到 ，结束(重复)终止 。表4: 点击率预测输入向量媒体（impression）属性p广告活动（campaign）属性a用户（user）属性u类型权重创意人群性别地域收入兴趣注：如果属性值是分类型变量，特别是名义型变量，则需要将其转化为哑变量，再进行Logistic回归分析。如：多分类变量有四个取值（A/B/C/D），这时需要设置三列哑变量，比如D2,D3,D4,如果变量值是B，则D2=1，否则取0，如果是C，则用D3=1，否则取0，如果是D，则D4=1，否则取0。可以以如下的矩阵方式进行存储。ABCDD20100D30010D40001如果属性值是连续型变量，则需要对变量进行标准化处理，以消除因数据单位不同而引起的计算结果的偏差，一般采用z-score标准化方法，方法如下：令，则，如果属性值是连续型变量，则需要对变量进行标准化处理，以消除因数据单位不同而引起的计算结果的偏差，一般采用z-score标准化方法，方法如下：经变换，各变量落入0, 1区间。
