网络广告定位优化算法学习

网络广告现在是主流的网站收入来源，在电子商务中，无论是B2B、B2B、C2C，广告都是必不可少的。

广告作为一种收入来源，它的要求自然就是效益最大化。那么网络广告供应商要如何放置广告，才能做到效益最大呢？

提高广告效益主要的一种方法是广告的定位优化，也就是根据浏览者的需要或者兴趣，，在他们所浏览的页面提供相关的、他可能感兴趣的最有可能被点击的广告。这样可在不增大总的广告投放量的条件下，提高总的广告点击率，也就是提高单位的广告带来的效益。

那怎么样定位优化呢？

Langheinrich线性规划模型

下面我们先来了解一个Langheinrich提出的简单的线性规划模型（类似于运筹学中的运输问题模型）。

我们先假设一个如下的环境：

1.         浏览者都是按照他们的需要或者兴趣浏览网页的，也只会在他们的需求或兴趣驱动下点击广告，我们称他们的需求或兴趣为“关键词”（借用了搜索引擎里面的概念）；

2.         针对浏览者的一个“关键词”一次只显示一个广告，且只有在浏览者点击广告的情况下，广告才产生效益；

3.         浏览者所浏览的所有广告都是由一个广告供应商提供的，显示哪个广告是随机的，但显示概率是人工调整的；

4.         每个广告都有它的显示率要求（每个广告露脸的概率和他要求的概率应当不多也不少）。

我们再做如下的定义：

l  广告集（AdSet）{Ai}：广告供应商所有的广告的集合；

l  关键词集（WordSet）{Wj}：所有浏览者的关键词构成的集合；

l  hi：广告Ai要求的显示率；

l  kj：关键词Wj发生的概率；

l  cij：在关键词Wj下，浏览者会点击广告Ai的概率；

l  xij：在关键词Wj下，系统会显示广告Ai的概率。

在上面的定义当中{Ai}的大小为n（i = 1…n），{Wj}的大小为m（j = 1…m），hi是已知的，kj和cij是可通过调研获得的，xij是我们的决策变量，我们需要满足一定条件的同时，通过调整xij的大小，使广告的点击率达到最大。

 

 

以上问题可以通过运筹学的单纯形法求解。

存在问题

由于它没有考虑的广告对“广而告之”的需求，它的最优解中总是有nm –(n+m)个零元素，也就意味着每个关键词下可能显示的广告种数非常之少，这是一般的广告发布者所不希望的，也是不合常理的。

聚类方式处理的两阶段法

为了达到网络广告“广而告之”的需求，让一个广告在更多的关键词下能够显示，同时让模型更加合理，我们可以对上述模型进行一些改进。

此方法中，我们把“关键词”当作一种频道（像电视频道一样），一个频道可以有很多种广告，但是单位时间T能显示的广告个数有一个上限，我们称之为“能力配额”，也就是单位时间内浏览者通过这个关键词看到的广告个数的上限。

修改后的定义如下（很多个“概率”变为了“次数”）：

l  广告集（AdSet）{Ai}：广告供应商所有的广告的集合；

l  关键词集（WordSet）{Wj}：所有浏览者的关键词构成的集合；

l  Hi：广告Ai要求的最小显示次数；

l  sj：关键词Wj的能力配额；

l  cij：在关键词Wj下，浏览者会点击广告Ai的概率；

l  Xij：在关键词Wj下，显示广告Ai的次数。

l  N：所有广告总的显示次数（所有Xij之和）

同时，由于运输问题模型对cij的差异有很高的敏感度，而实际上cij之间细小的差异对广告的投放并没多大影响，为了降低这种影响，我们先对{cij}进行简单的聚类，即将一系列概率相近的cij放入一个“桶”中，取“桶”的平均值作为这一系列cij的值，设为{Cij}。

聚类算法如下：

（1）      定义最终需要的桶数K（由自己按需设定）。

（2）      每个cij分配一个桶（桶的总数为N，当前共nm个，桶的均值为桶中cij的和除以cij的个数）。

（3）      如果N == K，终止算法，否则进入下一步。

（4）      将均值最接近的两个桶合并为一个桶，将两桶cij都放入此桶中。

（5）      判断桶的总数N是否大于K，如果是则重复步骤（4），否则终止算法。

 

 

通过以上两个阶段，我们就可以得出一个比较满意的解了，既能满足广告效益最大化，同时也使得单个广告的接触人群更加的广。