基于模式满足频控的在线广告分配

发布时间：2020-12-04 08:28

　　随着互联网应用的快速发展,互联网用户数量也急速增长。互联网广告成为众多互联网企业的重要收入来源。大部分广告主对媒体商的广告投放过程有所要求。比如1)投放给具有固定属性的人群(定向),2)在一定期限内投放的广告数量(保量),3)每个投放周期中,对于同一个用户最多投放的次数(频控)等。因此对每一个在线到来的用户访问,媒体商如何选择为其投放的广告以满足众多广告主的需求,并能获得尽量大的收益成为媒体商关心的重点。本文针对真实投放系统,如腾讯视频的广告主需求及数据预测技术现状,将广告投放问题抽象为一系列理论模型。并提出一套三段式的广告投放方案以满足系统需求。具体工作如下:1.本文针对目前的投放系统中用户频次不可预测的现状,提出了一套先生成一组模式后将模式分割为子模式的线下方案,以及在线上为每个到达的用户分配一个子模式并可动态修改子模式的线上方案。同时本文还提出一个轻量级的模式生成算法,满足了投放系统中每轮投放周期仅24h而数据量庞大的时效性需求。2.本文收集了部分腾讯视频的真实访问数据,并使用该数据进行多组实验对比。实验结果显示,相比于适用于用户频次可预测的传统方案,本文的算法仅有少量的利益损失... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：65 页

【学位级别】：硕士

【部分图文】：

图１．１?２０１０－２０１８各项媒体广告收入规模??

假设Ｍ为Ｇ的一个子图，且Ｍ的边集中的任意两条边之间都没有公共??顶点，则称Ｍ是一个匹配。其中顶点个数最多的匹配称为最大匹配［５］。最大二??分图匹配可以在使用匈牙利算法在多项式时间内求解［６］。图１．３为一个最大匹配??的例子。而由于广告分配问题中的曝光数量及每个曝光的属性并非事先已知，故??广告分配问题实质上为在线二分图匹配问题。即ｔ／中的顶点为在线到达的，对??于每个到达的顶点，选择是否匹配Ｋ中的顶点，如果匹配，考虑选择哪个顶点??进行匹配以得到最大匹配。??图１．３最大二分图匹配（Ｍａｘｉｍｕｍ?Ｍａｔｃｈｉｎｇ）??在线二分图匹配问题最早由Ｋａｒｐ教授引入，并设计了一个竞争比（Ｃｏｍｐｅｔ？??ｉｔｉｖｅ?Ｒａｔｉｏ）?为?１?－?｜?的随机算法，称为?Ｒａｎｋｉｎｇ?算法?，同时证明了?１?－?＞．６３２）??为该问题的竞争比［７］。算法的竞争比是指对于一个线上问题，给定任意ｋ输入，??若该算法能保证得到的结果至少是对应的线下问题的最优结果的一个常数比例。??则该常数即为该算法对于此问题的竞争比［８］。由于此模型对于在线到达顶点的??信息是完全未知的（Ａｄｖｅｒｓａｒｉａｌ?ｏｒｄｅｒ），随后人们对于未知的信息提出一系列的??假设以打破竞争比的上界。包括随机顺序（Ｒａｎｄｏｍ?Ｏｒｄｅｒ）

设计了一种将模式进行分段并重组的方法，随后为了式打破频控或步长的限制，提出了一种动态修改模式的方案。此动方案保证了本算法的可扩展性。??对腾讯视频等广告投放系统中存在的用户量庞大的现状，本文级的模式生成算法，并分析了该算法的有效的原因。最后通过腾问数据验证了算法的有效性及实时性。??文结构??共分为五章，各章节的主要内容如下：第一章：绪论。本章首先配问题的背景及研究意义，主要介绍了一轮广告投放的主要过程的类型及付费模式的相关介绍。随后说明在广告市场中，广告主对于这些需求缺少相关研究的现状。第二节主要介绍了目前对题的相关理论模型及真实系统中的应用的研究现状。理论模型包匹配问题，真实系统中的应用包括竞价机制以及最小化缺量惩罚


本文编号：2897286