网络广告定位优化算法学习
网络广告现在是主流的网站收入来源，在电子商务中，无论是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），否则终止算法。
通过以上两个阶段，我们就可以得出一个比较满意的解了，既能满足广告效益最大化，同时也使得单个广告的接触人群更加的广。