RTB实时竞价算法.doc

1. 算法简介 21.1 算法用途 21.2 算法概述 22. 算法详细说明 32.1 广告活动匹配 32.2 实时竞价算法 43. 算法改进方向 93.1 特征属性的选择 93.2 点击率预测 103.3 竞价调整方式 104. 补充问题 104.1 无历史数据阶段 104.2 利用历史数据阶段 104.3 展示的分布控制 105. 参考文献 116. 附件 126.1 名词 126.2 算法总体流程图 136.3 输入输出表 136.4 数据预处理流程 156.5 计算权重算法流程 176.6 模型检验 201. 算法简介1.1 算法用途RTB（ Real-Time Bidding ）实时竞价，是一种利用第三方技术在数以百万计的媒体上针对每一个用户展示行为进行 评估以及出价的竞价技术与大量购买投放频次不同，实时竞价规避了无效的受众到达，只针对有意义的用户进行购买 它的核心是DSF平台（需求方平台），在 DMP数据的支持下根据媒体，广告特点和人的属性进行定向投放 RTB对于媒体来说，可以带来更多的广告销量、实现销售过程自动化及减低各项费用的支出而对于广告商和代理公司来说，最直 接的好处就是提高了效果与投资回报率。

RTB算法有几种常见的策略：展现优化（针对品牌推广）目标，点击率（ CTR优化目标和ROI（投资回报率）优化目标其核心都是要做到合适的广告展现给合适的人 ROI优化是最直接能体现广告主的投资收益率的指标，但是目前情况下受RTB业界技术限制和公司数据支持情况的限制，点击率优化是现实可行的 RTB竞价方法虽然该方法不能直接体现在用户的投资收益率指标上，但是优良的点击率很大程度上会带来良好的收益目前针对RTE算法中的点击率预测有很多种方法，女口：逻辑回归，决策树，两阶段广义线性模型，非线性规划模型， 典型方程等选用逻辑回归的主要原因在于该算法成熟，对输入变量要求较低，既可以处理枚举型变量，又可以处理连 续型变量输出结果较稳定可靠本算法主要以点击率（CTR为优化目标，并选择逻辑回归作为主模型进行设计1.2 算法概述首先对RTB的竞价流程总结如下图所示:广告主策略图1 RTB竞价流程图 从上图中可以看出，实时竞价算法的输入主要包括以下信息：1） Exchange端提供的广告位信息；2） 用户id，DMP攵集的用户属性信息；3） 广告主发布的活动信息及竞价策略；4） 竞价历史（媒体信息，广告位，获胜竞价，用户id等）。

表1: RTB算法输入之竞价历史广告媒体信息用户ID时间戳是否点是否成报价成交价创意类型权重尺寸］击功格实时竞价算法的输出主要是获胜的（广告活动信息，竞价）组实时竞价算法主要由两部分构成，一是广告活动的匹配，二是根据媒体，广告活动及用户属性等进行出价请求中媒体信息， 用户ID,广告活动 集,DMP系统信息计算竞价值并排序输出（广告活动，竞 价）信息组图2 RTB竞价算法流程2. 算法详细说明2.1 广告活动匹配广告活动匹配的目的是为了筛选出满足媒体广告位要求，以及符合用户属性特征的广告活动集合首先，根据请求 中的媒体广告位信息对广告活动进行初步筛选，过滤掉一些无效的广告活动，如：不满足广告位要求的广告活动等然 后，利用DMF系统中查找到的用户特征信息，以及广告活动的投放人群属性定向再次筛选广告活动广告活动的投放人 群属性定向主要包括访客所在地区，年龄，性别，婚姻状况，教育程度，兴趣爱好，购买偏好等主要包括以下步骤：第一步，将请求中的媒体广告位信息与DS系统中的广告活动信息进行初步匹配，筛选出满足条件的广告活动集合; 如果不存在广告活动，则不参与此次请求的竞价第二步，利用DM系统，根据用户id，获取用户特征信息。

第三步，将筛选出的广告活动集合与用户特征进行匹配，进一步筛选广告活动集合图3广告匹配流程表2广告活动匹配需要考虑的信息X广告位信息广告活动用户属性属性1广告位宽投放媒体偏好性别属性2广告位高访客所在地区年龄属性3不允许的属性id集合访客年龄地域属性4允许的广告技术类别访客性别婚姻属性5排除的敏感类别访客婚姻状况教育程度属性6排除的产品类别访客教育程度兴趣属性7媒体提供的限制列表访客兴趣爱好属性8访客购买偏好关于匹配度的计算问题涉及到商业策略及广告本身估值，用户的估值，媒体的估值及DSP端广告集合的分析等情况, 在综合分析的情况下，才能给出在特定商业策略上的匹配度，该部分计算放在后续进行2.2 实时竞价算法通过广告匹配算法能够筛选出符合媒体信息和用户特征的广告活动，接下来需要对筛选出的广告活动进行竞价，并 排序，返回一系类（广告活动，竞价）结果组广告活动的投放类型一般有 为CPC进行竞价，转换原则为：CPC和CPM两种，目前只考虑CPC投放类型，如果是投放类型是 CPM可以将CPM转化CPM = CPC*CTR*1000总体来说，实时竞价算法可以分为以下两个步骤：1.获得每次广告展示的价值，即在给定的相关展现水平和需求数据的情况下，对该次广告展现预期成本，表示形式如下：eCPI 二 CTR * CPC其中eCPI表示每次展现的预期成本，即最优竞价估值。

CPC在给定的广告系列中是已设定的常数预测CT是 一个关键的步骤：CTR 二 p(click | impression,campaign, user)其中条件中的impression包括了与该次展示机会相关的数据，比如用户信息； campaign包括了广告活动的相关数据2 .实时竞价的调整根据竞价策略以及历史竞价数据调整实际竞价221 广告展示估值为了准确地评估每次广告展示的价值，需要对该广告的点击率进行预测初次使用系统时，由于缺乏获胜的历史 竞价信息，可以使用默认的点击率，如：该品牌往常的点击率或其他平台媒体经验值等随着历史数据的增加，需要根 据用户和媒体等信息，对每次展示机会预测点击率广告当获得足够多的历史数据时，可以利用媒体特征信息（如：广告位置等） ，用户特征（如：年龄，兴趣等）活动特征（如：创意，关键字等）构建点击率预测模型由于特征属性信息非常多，首先需要进行属性特征提取，获得 有价值的属性特征然后根据历史数据，构建点击率预测模型当获得一个展示机会的时候，针对每个广告活动，根据 用户和媒体的属性值进行点击率预测离线部分/ 7竞价历史数据K\}J1特征提取构建点击率 预测模型<—V输出点击率媒体，用户，广告活动信息图4点击率预测流程2.2.1.1 特征提取获胜在一个广告系统中，每一次出价和服务事件，包括广告机会，拍卖的获胜者，以及浏览该广告展现的用户都能够 被记录。

每一个广告机会通过其属性进行描述，包括 url，出版商，广告位置以及用户统计信息，geo位置信息 信息包括获胜的竞价值，实际的花费等通常，有很多的目标属性值它们中的大多数是复杂的布尔逻辑规则来匹配广 告商想作为目标的广告库存，作为竞价需要考虑的因素也不应过多，造成算法的复杂程度过大，难以满足实时竞价的时 间要求因此，特征选择是系统中至关重要的一个因素在选择特征的时候，有两个方面的方法可以选用1） 经验法通过对行业的了解及属性的分析，对属性进行筛选2） 采用适当的算法对属性对竞价的影响进行分析，计算每个属性对竞价的影响程度选择影响因素大的属性作 为特征属性表3需要考虑的特征属性信息X广告位信息广告活动用户属性属性1媒体id投放类型性别属性2广告所属频道活动创意年龄属性3广告位宽广告主id地域属性4广告位高广告类型兴趣属性5广告位的可视性活动人群属性消费水平属性6地理信息投放媒体偏好我们采用基于过滤的Fast-Correlation(FCBF)方法选择特征子集［1］，该方法对处理特征数目较大时非常有效其 基本原理描述如下：设数据集 D有n条记录，且每条记录由m个非目标特征和一个目标特征 C来刻画。

如果非目标特征 与目标特征之间的相关性过低(给定阈值)，则将该特征作为不相关特征去除，如果两个非目标特征之间的相关性过大， 超过了这两个特征与目标特征的相关性时，则认为两个特征之间存在冗余，这两种情况均需要进行删除FCBF是 一个确定性算法来消除与目标值相关度较低的属性或非目标属性过度相关的属性冗余它能使我们在很大 程度上消减特征搜索时间它依据对称不确定性计算特征和目标值的相关性，定义如下：SU(X,Y)=2 IG(X|Y)H(X)+H(Y)其中IG是信息增益(Information Gain )， H是熵(Entropy )GX Y )的值是Y给X带来的信息增益，并且 IG(X |Y) =IG(Y |X)SU是IG的一个归一化值通过对目标属性与非目标属性及非目标属性之间 SU的计算,在给定的阈值基础上，进行属性选择点击率预测在特征子集选择的基础上，对点击率进行预测点击率预测问题可以看成是一个分类问题，把(媒体，广告活动，用户)看成是一个多元组，针对每一个多元组，有 一个预测目标，是否点击该问题可以看成是一个典型的逻辑回归问题假设有n个训练样本集，D ={( f j(pj ,aj,uj), cj)}l，其中f j(Pj, aj,Uj)三二d表示由多元组(媒体，广告 活动，用户)属性值构成的一个d维向量，cj = {0,1}是相应的分类标签(+1，点击，或者0：没有点击)。

给定一个 媒体P,广告活动a,以及用户U,需要计算点击的概率p(c| p,a,u)采用逻辑回归模型，表示形式如下：p(c|p，a,u) J1+exp(乙土Wif (p,a,u))其中f(p, a, u)表示从多元组(p, a, u)获得的第i个属性的值，wi三w关于它的权重 减少数据中的总损失计算权重向量 w,公式如下：给定训练样本集合，模型通过dn _^wifij(pj,aj ,uj)f (w) = L(w)八[cj ln(1 e i-j壬d迟w fjj(Pj，aj ,Uj))(cj 一1)1 n(1 eT )]可以用L-BFGS算法［3］求解这种大规模的凸优化问题具体方法如下L-BFGS算法步骤如下:Step1:选初始点w 0，允许误差，＞ 0，存储最近迭代次数m (—般取6)；step2： k = 0, H0 = I ,r = '■ f (w0)；n其中：令 xj= f j(pj,aj,uj)，则' f(w)八[cjjm-xjT j1+ewxStep3:如果| f (wk彳)| * 〔，则返回最优解 wk计，否则转Step4；(注: ||x|| =(巧|订)2)Step4:计算本次迭代的可行方向： pk - -r ；。