注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

广告中的去重选择  

2014-10-21 00:13:53|  分类: 计算广告学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

广告中的去重选择

         在广告展示策略中,有一些去重的需求。本文中介绍一个去重中的细节问题。

举一个广告主去重的例子。如果在页面上一次可以展示三个广告,如果我们展示的广告中有两上广告是同一个广告主的,那么广告主会很不开心。因为他会感觉自己的展示次数是虚的,对他来讲是一次展示,但给他的报表里却说是两次。

 

广告中的去重选择 - quweiprotoss - Koala++s blog

 

再举一个素材去重的例子。如果一个用户在网页浏览时,看到大量相似素材非常接近的广告,他会有点反感,并且通常不会去点击多个相似素材的广告,这对广告主,广告受众,广告平台都是不利的。

 

广告中的去重选择 - quweiprotoss - Koala++s blog

 

看到这个问题,第一反应会是这算什么问题呀,简单去重一下不就可以吗?是的,去重一下是可以解决,但这是最优解吗?

我举一个例子说明,下图中的每一个块代表一个候选广告,一个广告有两个属性,用两个颜色表示,相同属性中相同颜色不能重复,一共需要2个广告。

广告中的去重选择 - quweiprotoss - Koala++s blog

 

现在看简单去重的逻辑,我们先选择了广告1,广告1的第一个属性(深棕色)与广告2的第一个属性冲突,广告1的第二个属性(深蓝色)与广告3第二个属性冲突。所以广告1只能与广告4搭配,它们两个的价值之和为9+1=10

而换一个思路,不一定要选择第一个广告后去重,那么我们选择广告2和广告3,它们的价值之和是8+7=15。也就是说简单的去重逻辑不是最优策略。

有了上述的问题,我们将它形式化成一个算法问题。有N个候选广告,每个广告一次展示的价值为Vi (i=[1, … N])N个候选广告已经按价值排序,一次展示需要K个广告。现要找出K个价值之和最大的广告。

再对上面的问题进行一点解释,候选广告已经按价值排序,这是广告系统中的逻辑决定的。

看完问题之后,第一反应应该是这不就是0/1背包问题吗?但仔细想一下,与0/1背包问题还是有点不一样,1. 0/1背包问题中的weight在这里是相同的,一个广告就占一个展示的位置,广告与广告所占的空间相同(我们现在正在搞不相素材规格的混排问题,就不发散了),但这个区别只是说它是0/1背包问题的一个特例。2. N个候选已经按价值排序过了,按价值排序了,那么就可以提前剪枝了。

         Talk is cheap, Show me the Code

AD_COUNT = ad_list.size();

CURRENT_MAX_VALUE = 0;

REQUIRED_AD_COUNT = 4;

FETCH_LIST = []

 

FindMaxValue(index, sum_value, fetch_list)

    if index >= AD_COUNT

       if sum_value > CURRENT_MAX_VALUE

           CURRENT_MAX_VALUE = sum_value

           FETCH_LIST = fetch_list;

       return ;

    if fetch_list.size() == REQUIRED_AD_COUNT

       if sum_value > CURRENT_MAX_VALUE

           CURRENT_MAX_VALUE = sum_value

           FETCH_LIST = fetch_list;

       return ;

 

 

    if (Pruning(index, fetch_count, sum_value))

       return ;

 

    value = ad_list[index].value;

    copy_sum_value = sum_value;

    copy_index = index

    copy_fetch_list = fetch_list.deep_copy();

    FindMaxValue(index + 1, sum_value, fetch_list);

 

    copy_sum_value += value;

    copy_fetch_list fetch_list.append(index);

    copy_index += 1;

 

    FindMaxValue(copy_index, copy_sum_value, copy_fetch_list);

 

Pruning(index, fetch_count sum_value)

    int max_value = sum_value;

    remain_count = REQUIRED_AD_COUNT - fetch_count;

    for i = index to remain_count

       if index >= AD_COUNT &&

           max_value < CURRENT_MAX_VALUE

              return true;

      

       max_value += ad_list[i].value;

 

    if max_value < CURRENT_MAX_VALUE

       return true;

 

    return false;

 
  评论这张
 
阅读(1287)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017