（计算机应用技术专业论文）网络定向广告投放算法研究.pdf

浙江大学硕士学位论文摘要 摘要 随着互联网广告业的快速发展，定向广告作为一种新兴的网络广告模式也随 之迅速发展，这种广告模式以其精准、及时、高效的特点备受人们的关注。定向 广告是一种投放在网页上的与网页内容或者用户自身的行为特征相关的广告投 放模式，按定向模式的不同可以分为内容定向广告和行为定向广告。针对内容定 向广告问题，本文提出了一种高效的基于语义的内容定向广告投放算法，该算法 首先利用词之间的语义关系对网页关键词进行词汇扩展，然后利用类贝叶斯权重 计算模型来计算这些扩展词在网页中的权重并用改进后的向量空间模型计算网 页与文本广告之间的相似度，最后按照这种相似度找出与网页内容最相关的广 告。针对行为定向广告问题，本文提出了一种全新的基于用户行为特征分析的行 为定向广告投放算法，该算法首先根据用户行为特征模型对用户最近访问的网页 按主题进行聚类，然后利用用户行为特征分析算法对每一类网页进行行为特征分 析并计算该类网页的权重，最后利用该权重以及该类网页的质心与广告的相似度 来计算最后得分，并按照这个得分对广告进行排序从而选出与用户行为特征相匹 配的广告。大量实验表明，这两种算法都是十分有效的定向广告投放算法，能够 高效地匹配出与网页内容或用户行为特征相关的广告，具有十分广阔的应用前 景。 关键词：内容定向广告，行为定向广告，向量空间模型，语义，用户行为特征 分析 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o ft h ei n t e r a c t a d v e r t i s i n gi n d u s t r y ，t a r g e t e d a d v e r t i s i n ga san e wn e t w o r ka d v e r t i s i n gm o d e li sa l s od e v e l o p i n gv e r yq u i c k l y t h i s k i n do fa d v e r t i s i n gi sv e r ya t t r a c t i v eb e c a u s ei t sa c c u r a t e ，t i m e l ya n de f f i c i e n t t a r g e t e da d v e r t i s i n gi sak i n do fa d v e r t i s i n gw h i c hi sd e l i v e r e do nw e bp a g e s w i t ht h e p a g ec o n t e n to ru s e rb e h a v i o rr e l a t e d t a r g e t e da d v e r t i s i n gc a n b ed i v i d e di n t oc o n t e n t t a r g e t e da d v e r t i s i n ga n db e h a v i o r a lt a r g e t i n ga d v e r t i s i n ga c c o r d i n gt o t h ed i f f e r e n t t a r g e t s f o rt h ec o n t e n tt a r g e t e da d v e r t i s i n g ，w ep r e s e n ta ne f f i c i e n ts e m a n t i c b a s e d c o n t e n tt a r g e t e da d v e r t i s i n ga l g o r i t h m t h i sa l g o r i t h mf i r s to fa l lu s e st h es e m a n t i c r e l a t i o n sb e t w e e nw o r d st oe x p a n dw e bp a g ek e y w o r d sa n dc a l c u l a t e st h ew e i g h t so f t h e s ee x p a n d e dw o r d sw i t ht h eh e l po fa p p r o x i m a t eb a y e s i a nw e i g h tc o m p u t i n g m o d e l ，t h e nc o m p u t e st h es i m i l a r i t i e sb e t w e e ne x p a n d e dw e bp a g e sa n da d su s i n gt h e i m p r o v e dv e c t o rs p a c em o d e l a tl a s tw es o r ta d sa c c o r d i n gt ot h e s es i m i l a r i t i e sa n d f i n dp r o p e ra d sf o rw e bp a g e s f o rt h eb e h a v i o r a lt a r g e t i n ga d v e r t i s i n g ，w ep r o p o s ea n e wb e h a v i o r a lt a r g e t i n ga d v e r t i s i n ga l g o r i t h mw h i c hi sb a s e do nt h eu s e rb e h a v i o r f e a t u r ea n a l y s i s t h ea l g o r i t h mf i r s to fa l lc l u s t e r st h eu s e r s r e c e n t l yv i s i t e dw e bp a g e s a c c o r d i n gt ot h eu s e rb e h a v i o rf e a t u r em o d e l ，t h e na n a l y z e se a c hc l u s t e ro fw e b p a g e su s i n gt h eu s e rb e h a v i o rf e a t u r ea n a l y s i sa l g o r i t h ma n dc a l c u l a t e si t sw e i g h t a c c o r d i n g l y w i t ht h i sw e i g h ta n dt h es i m i l a r i t yb e t w e e nt h ec l u s t e rc e n t e ra n da d s ，w e c a nc a l c u l a t et h ef i n a ls c o r e so fa d s a tl a s tw es o r ta d sa c c o r d i n gt ot h e i rs c o r e sa n d f i n dp r o p e ra d sf o rt h eu s e r s al a r g en u m b e ro fe x p e r i m e n t ss h o wt h a tt h e s et w o a l g o r i t h m sa r ev e r ye f f e c t i v et a r g e t e da d v e r t i s i n ga l g o r i t h m sw h i c hc a nm a t c ha d sa n d t h ew e bp a g ec o n t e n to ru s e rb e h a v i o re f f e c t i v e l ya n dh a v eav e r yb r i g h tf u t u r e k e y w o r d s ： c o n t e n tt a r g e t e da d v e r t i s i n g ，b e h a v i o r a lt a r g e t i n ga d v e r t i s i n g ，v e c t o r s p a c em o d e l ，s e m a n t i c ，u s e rb e h a v i o rf e a t u r ea n a l y s i s 浙江大学硕士学位论文图目录 图目录 图1 1 搜索引擎的基本架构2 图1 22 0 0 3 2 0 0 8 年美国网络广告市场规模3 图1 32 0 0 4 2 0 0 8 年中国网络广告市场规模和结构4 图1 4g o o g l e 提供的赞助搜索广告7 图1 5g o o g l e 提供的定向广告7 图1 6 网页与广告之间的阻抗1 0 图3 1 定向广告的系统架构17 图3 2 定向广告投放算法基本流程2 0 图5 1 内容定向广告投放算法流程2 7 图5 2 类贝叶斯网络3 0 图5 3 关键词互为同义词时形成环3 0 图5 4 将关键词加入扩展词避免环的形成3 1 图6 1 行为定向广告投放算法流程3 4 图6 2 用户行为模型示意图3 6 图7 1 论坛类网页改进的模型或算法对匹配精度的影响4 3 图7 2 新闻类网页改进的模型或算法对匹配精度的影响4 3 图7 3 博客类网页改进的模型或算法对匹配精度的影响4 4 图7 4 论坛类网页九1 对匹配精度的影响4 5 图7 5 新闻类网页九1 对匹配精度的影响4 5 图7 6 博客类网页九1 对匹配精度的影响4 6 图7 7 论坛类网页不同内容定向广告投放算法对比实验结果4 7 图7 8 新闻类网页不同内容定向广告投放算法对比实验结果4 7 图7 9 博客类网页不同内容定向广告投放算法对比实验结果4 7 图7 1 0 用户短期行为对广告投放的影响5 0 图7 1 1 用户长期行为对广告投放的影响5 1 图7 1 2 新鲜因子尥对广告投放的影响5 1 i i i 浙江大学硕士学位论文表目录 表目录 表7 1 关键词扩展前后关键词列表的变化4 2 表7 2 行为因子芎对广告投放的影响5 2 i v 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 课题背景与意义 随着互联网在全球的快速发展，互联网上的信息成指数式的增长并且已经深 入到经济、政治、教育、科技、文化等各个领域，成为人们生活、工作、娱乐不 可或缺的一部分。在全球的信息化浪潮中，中国的互联网也随之迅猛发展，根据 中国互联网络信息中心( c n n i c ) 的统计，截至2 0 0 8 年底，中国的网站数已经达到 2 8 7 8 万个，较2 0 0 7 年增长9 1 4 ，中国的网页总数已经超过1 6 0 亿个，较2 0 0 7 年增长9 0 1 1 1 。 互联网的迅猛发展使得人们的生活变得十分方便快捷，但是面对如此海量的 数据，怎样进行高效的检索从而快速、准确、方便的获得有价值的信息成为摆在 人们面前的一个难题，搜索引擎的产生使这一难题得到了解决。搜索引擎起初是 大学的科研项目，主要着眼于高效的索引和检索算法的研究以及原型系统的开 发，后来逐渐发展为商业应用产品，商业搜索引擎中最著名的是诞生于斯坦福大 学的搜索引擎g o o g l e 和诞生于中国的中文搜索引擎百度。 搜索引擎通过称为网络爬虫的网络机器人以某种策略自动地在互联网上发 现并抓取网页信息，并且将其存储到本地的网页数据库中，然后对这些信息进行 一些预处理，主要包括关键词的提取、镜像和转载网页的去重、链接分析和网页 重要程度的计算等，接着通过索引器将预处理后的网页建立倒排索引并将这些索 引存储在索引数据库中，当用户提交查询关键词给检索器时，检索器根据特定的 算法在倒排索引中进行检索，然后将检索结果按照与查询关键词的相关程度进行 排序并以列表的形式返回给用户，搜索引擎的基本架构如图1 1 所示。 浙江大学硕士学位论文第1 章绪论 发现与抓取- 二 存 预处理 索引器 图1 。1 搜索引擎的基本架构 免费的搜索引擎为用户提供了简洁高效的检索服务，大大方便了人们的学 习、工作与生活，但免费也使商用搜索引擎的发展受到了限制。随着风险投资的 逐渐减少1 2 3 】，商业搜索引擎公司被迫寻找合适的盈利模式来维持自身的生存。在 商业模式的探索中，诞生了一种称为竞价排名的商业模式，这种模式获得了很大 的成功，但是也产生了一些问题，由于这种商业模式根据商业客户的出价来对检 索结果进行排序，因此用户不能在最开始的几条结果中就获得想要的信息1 4 ，5 】，从 而影响了用户的体验，降低了搜索引擎的可信性【6 j ，并且导致搜索引擎用户的流 失，因此这种商业模式逐渐被淘汰。取代它的是一种新的称为赞助搜索广告 ( s p o n s o r e d a d v e r t i s i n g ) 7 8 】的商业模式，这种商业模式在用户进行查询的同时对一 个特定的广告数据库进行检索，在返回网页检索结果的同时将相关的赞助广告投 放在检索结果页面的右侧或者项部，当放在顶部时用不同的底色区别于网页检索 结果，并且明确告诉用户这是赞助商提供的广告，如果用户点击了赞助搜索广告， 广告商就支付相应的广告费用给搜索引擎公司。赞助搜索广告模式不仅能满足用 户获得有价值网页搜索结果的需求，也能满足为广告商的网站带去高质量访问流 量的要求。用户向搜索引擎提交关键词进行查询说明用户对这个关键词所包含的 2 浙江大学硕士学位论文 第1 章绪论 信息感兴趣，所以这些用户很可能对与该关键词相关的广告也感兴趣并最终产生 购买行为，因此这种模式能够有效的将广告投放给它的目标人群，被认为是目前 非常有效的搜索引擎盈利模式。 有效的盈利模式使商用搜索引擎获得了飞速的发展，同时也催生了巨大的赞 助搜索广告市场，但是赞助搜索广告仅仅是网络广告的一种，整个网络广告的市 场规模更加巨大，随着全球经济朝数字化经济迈进，网络广告市场还将继续增大。 根据i a b 的统计，2 0 0 8 年美国网络广告市场规模达2 5 8 亿美元，尽管受到了金 融危机的影响，美国的实体经济受到严重冲击，广告投放能力大幅下滑，但互联 网与其他媒体相比优势明显，同时在奥运会、美国大选等利好因素拉动下，美国 网络广告市场虽然未能实现之前爆发式增长的预期，但增速依然达到2 1 7 【9 1 。 2 0 0 3 2 0 0 8 年美国网络广告市场规模如图1 2 所示，从图中可以看出美国网络广 告市场成逐年增长的态势。 图1 22 0 0 3 2 0 0 8 年美国网络广告市场规模 2 0 0 8 年中国网络广告市场规模达到1 7 0 亿，相比2 0 0 7 年增长5 0 4 ，预计 女大m 十学位论女第l $ 绪论 0 9 年中国网络广告市场规模将达到2 1 6 4 亿元，同比增长将达2 72 1 9 1 。2 0 0 4 2 0 0 8 年中国网络广告市场规模和结构如图i3 所示，从图中可以看出中国网络广告市 场的发展速度十分迅猛，其中2 0 0 8 搜索引擎广告营收达到5 03 亿，获得7 0 以 上的广告营收增速，从而实现了对综合门户的超越吼 幽i32 0 0 4 2 0 0 8 年中国网络广告市场规模和结构 虽然中国网络广告市场规模已经很大，但是整个中国广告市场却更为庞大， 达到2 0 1 4 亿，网络广告所占的比例仅为8 4 ，因此网络广告凭借其便捷、快速、 高效的优势还有很大的潜力。另外市场对于网络广告的需求也十分庞大，目前赞 助搜索广告发展已经比较成熟，而且比较高效，因为它能自动找到广告的目标用 户群，但是当前投放在网页上的广告大多比较低效广告商无法将广告投放给他 的目标客户群，只能广泛撒网，用户则大多视广告为影响阅读的干扰因素因为 用户对这些广告并不感兴趣，因此需要有针对性地投放与用户相关的广告，使用 户对投放的广告产生兴趣并展终点击它，这种与用户相关的广告的称为精准广 告，近年来，市场对于这种精准广告的需求变得十分迫切。巨大的商机驱使搜索 引擎公司尝试用新的盈利模式来占领精准广告市场，从而获得更高的市场占有 4 浙江大学硕士学位论文第1 章绪论 率。在这种背景下，一种新的广告投放模式一定向广告诞生了，这是一种投放在 网页上的与网页内容或者用户自身的行为特征相关的广告投放模式，广告的相关 性越高，越有效【10 1 。 定向广告对于广告商来说可以将广告投放给他们的目标用户群，从而带来高 质量的网络流量；对于数以百万计的中小型网站和个人站点也具有十分重要的意 义。在定向广告出来之前，这些小网站从未打过广告或者从没大规模的打过广告， 这些网站因为用户流量小，广告商大都对它们不屑一顾，但是定向广告的出现降 低了广告投放的门槛，广告不再高不可攀，它是自助而且价廉的，谁都可以做的， 在他们自己的站点放上广告只是举手之劳，通过投放定向广告可以为这些网站带 来不小的收入；另外定向广告对于商业搜索引擎公司也是十分重要的，由于长尾 效应的存在，这些小网站的流量累计起来形成了一个巨大的长尾广告市场， g o o g l e 是最典型的“长尾”公司，它目前有一半的收入来自这些小网站上的定向 广告。 综上所述，互联网的迅猛发展导致了搜索引擎的产生，搜索引擎公司为了维 持自身的生存与发展，进行了有效商业模式的探索，而赞助搜索广告模式的成功 使得搜索引擎得以飞速发展，但是盈利模式的单一和整个广告市场规模的巨大促 使搜索引擎公司进行更多盈利模式的探索，于此同时，网页上现有的低效广告投 放模式使得市场对于精准广告的需求变得十分迫切，于是诞生了新的广告投放模 式一定向广告。在庞大的市场需求推动下，定向广告凭借其自身的优势以及搜索 引擎公司的推动必将迎来极大的发展机遇。作为一种新兴的广告投放模式，学术 界的研究以及产业界的实践目前都还处在初级阶段，在这种背景下，开展对定向 广告有效投放算法的研究具有十分重大的意义，它不仅能够有效地推动广告投放 技术的发展，还能产生十分可观的经济效益，实现多方的共赢，因此及时开展对 定向广告投放算法的研究十分有必要。 1 2 网络定向广告介绍 网络广告是相对于传统媒体广告而言的，传统媒体广告是指电视、广播、杂 浙江大学硕十学位论文第1 章绪论 志、报纸上投放的广告，目前这类广告在整个广告市场仍然占据主导地位，前面 已经提到网络广告的市场占有率还不高，但是网络广告凭借其固有的优势正占据 越来越多的市场份额，而传统媒体广告的市场占有率正在逐步下滑，特别是报纸。 网络广告对比于传统媒体广告的优势是：低成本、高互动性、效果易监测。 由于传统媒体广告位和广告时间稀缺，因此广告费用比较昂贵，而网络广告由于 广告位较多，而且可以动态展示因此广告费用较低，另外网络广告可以实现与用 户的互动，用户对感兴趣的广告进行点击并且链接到广告商的网页，而对不感兴 趣的广告则可以忽略，由于这种互动性，广告商可以十分方便地根据用户的点击 情况来检测广告的投放效果，并且进行适当的调整，从而达到最佳的广告投放效 果，正因为具有以上这些优势，网络广告必将获得更大的发展。 网络广告主要分为多媒体广告和文本广告，前者主要只采用多媒体手段进行 投放的广告，如视频广告、图像广告、动画广告等，这些广告大多出现于用户访 问量较大的门户网站或者一些网站的首页等重要位置，这类广告大多是品牌广 告，主要用于宣传品牌或提升公司形象，其目的是要提高用户的覆盖率，它对用 户没有特别的偏好，因此不属于定向广告的范畴，同时由于这类广告的广告位比 较稀缺，费用也比较高；而文本广告通过文字来传递广告信息，其主要目的是向 用户介绍某种产品或服务，促使用户产生网上消费行为，这类广告是搜索引擎的 主要广告类型。文本广告可以分为赞助搜索广告和定向广告( t a r g e t e d a d v e r t i s i n g ) ，其中后者按定向的方式又分为内容定向广告( c o m e n tt a r g e t e do r c o n t e x t u a l a d v e r t i s i n g ) 【l l j 和行为定向广告( b e h a v i o r a l t a r g e t i n g a d v e r t i s i n g ) 。 定向广告与赞助搜索广告的相同之处在于它们同属于文本广告，文本广告主 要由以下几部分组成：广告商竞价的广告关键词、广告标题、一段简短的广告描 述以及目标网站的链接。文本广告的特点是用较少的语言传达尽量多的信息，要 尽量让用户能够记住或者引起情感共鸣，使之印象深刻。 定向广告与赞助搜索广告的不同之处是赞助搜索广告显示在查询结果页面 上，由用户查询驱动，目前所有大型搜索引擎( g o o g l e ，y a h o o ，b a i d u ，m i c r o s o f t ) 都支持这种广告，并且是搜索引擎公司收入的主要来源之一。搜索引擎作为网页 6 塑垩查兰竺! ：羔垡堡兰 整! 童堕望 搜索工具的同时也作为广告代理商，广告商对某个或某些关键词进行竞价，搜索 ；r 擎根据竟价结果对广告进行排序。赞助搜索广告投放在查询结果页面上如图 l4 所示，而定向广告显示在用户访问的网页上，由称为广告网络的中介( 主要 是各大搜索引擎) 负责优化选择合适的广告投放到用户访问的页面上，如图15 所示。 鬻! 簪鼍蒋黥。， 意孺畿黑鬻畿器；憨。，+ 黧黧薹鼙筘“” 旒黑糕漂瓣蒜怒壤黜籍黼 豢麓爨曩霉“ 慧筲嚣怒舞勰i 鬻案馨。 鍪墨毽= ” 4 j 二f # 胂黼目下量- c 月h0 # * 图1 4g o o g l e 提供的赞助搜索r 告 女自h 盗上拙 女i n i 要壁h 匡m i 拄5 # 拙 卜月* 镕* 毒竺嚣= 鬈嚣嚣嚣r 嚣：， 断 1 c * c * 、；：盎。盘骶。0 ，。矗二。矗。， 臻麓缈攀；囊器戮一z o 啼o 1 闰15 g o o g l e 提供的定向广告 骶勰驯滑螂埔孙 o 辑 刊酿冀纠制制料州 浙江大学硕士学位论文 第l 章绪论 定向广告通过特定的算法将广告投放给它的目标用户群体，从而达到改善用 户体验、增加用户的广告点击率的目的，而更高的点击率可以带来更高的广告收 入。对于内容定向广告，主要是选出与网页内容描述的主题关联度最高的广告， 强调网页内容与广告相关的重要性，而行为定向广告主要分析出用户的兴趣爱好 和当前关注的事物并选择出与之相关的广告，强调广告与用户行为特征相关的重 要性，当前主要的搜索引擎公司也都支持定向广告模式，如g o o g l e 的a d s e n s e ， 百度的百度搜索推广等。 广告的最终效果是由广告产生的收入来衡量的，但是广告定价模型本身是个 非常复杂的问题，需要综合考虑各种因素【1 2 】。定向广告的定价模型与赞助搜索广 告一样，主要可以分为以下几种：1 每次点击付费( p a y p e r - c l i c k ，p p c ) ，即每当 广告被点击时广告商支付相应的广告费用，目前商用搜索引擎的赞助搜索广告和 定向广告大都是采用这种定价模型；2 每次曝光付费( p a y p e r - i m p r e s s i o n ，p p i ) ， 即每当广告被曝光时支付，这种定价模型主要用于门户网站的多媒体广告，因为 这种广告主要是用于宣传品牌和提升公司形象，这种模型比较方便；3 每次交易 付费( p a y p e r - t r a n s a c t i o n ，p p t ) ，即只有当用户在广告商的网站上完成一次交易时 才支付【1 3 】。 对于定向广告目前普遍流行的是p p c i l 4 1 ，本文采用的也是这种定价模型。给 定一个页面p ，广告收入可以用公式( 1 1 ) 【1 3 】计算： r = p ( c l i c kp ，a o p r i c e ( a i ，f ) ( 1 1 ) j 毒l 一七 其中k 代表在网页p 上投放的广告数目，p ( c l i c kl p , a j 代表网页p 上的广告a ， 被点击的概率，p r i c e ( a t , 0 代表在位置，上的广告每次点击的收入，它依赖于呈现 在网页上的具体广告，为了简化起见，本文不考虑p r i c e ( a 。砂的影响而专注于找出 使p ( c l i c ki 刃口最大的广告，可以用公式( 1 2 ) 【1 3 】表示： a r g m a x p ( c l i c kp ，口f ) ( 1 2 ) ， 本文假定网页p 上的广告口，被点击的概率仅由广告与页面内容或者用户行为 特征的相关度决定，而忽略广告在网页上所处位置的影响，因此定向广告的选择 r 浙江大学硕士学位论文第1 章绪论 即转变为找出与网页内容或者用户行为特征相关度最大的广告。 1 3 网络定向广告的特点与难点 定向广告本质上与赞助搜索广告是一致的，它们都尝试在网络中寻找出目标 用户群并且投放与之相关的广告，从而提高广告的点击率。因为用户只有对他们 感兴趣的广告才会进行点击，与他们不相关的广告不仅不会被点击，反而会招来 用户的厌烦和讨厌，因此投放广告时必须找出目标用户群。 赞助搜索广告在寻找目标用户群方面具有天生的优势，因为它是根据用户的 查询关键词进行匹配的，而用户只有对某一事物感兴趣才会在搜索引擎中检索 它，从而投放与关键词相关的广告自然也是用户关心的。比如某用户近期想买手 机，他自然会在搜索引擎中查询有关手机的信息，他会根据自己喜欢的品牌、型 号和价格进行相关信息的搜索，若此时搜索引擎能恰到好处的投放与用户感兴趣 的手机相关的广告，不仅不会招来用户的厌烦，反而帮助了用户更快的获得所需 要的信息从而获得用户的喜欢，因此对于赞助搜索广告，这种优势是天生的。 对于定向广告，寻找目标用户是一件不容易的事情，用户根据自己的喜好和 最近关心的事情在网上浏览网页，但是网页结构复杂并且千变万化，而且h t m l 标签本身也允许错误的存在，因此要从网页中提取出内容的主题是非常困难的。 另外由于网页内容十分宽泛，各种各样的信息都有，而广告的主题则较为局限， 大多是一些具体的产品或者公司品牌，而且广告大多非常简短，内容非常精练紧 凑，因此网页主题与广告的失配情况非常严重，必须找出一种有效的算法来减少 这种失配。内容定向广告投放时会遇到以上这些问题，而对于行为定向广告除了 这些问题之外，还存在着其它问题例如怎样从用户的网页访问历史记录中挖掘出 用户的行为特征，并且怎样分析这种行为特征并且投放与之想适应的广告等，这 些都是定向广告研究中的难点问题。 1 4 本文的研究内容与创新点 上面提到由于网页的数量极其巨大，包含了各种各样的主题，而文本广告数 量相对较小，而且主题也没有网页宽泛，因此网页与广告之间必然存在着失配， 9 浙江大学硕士学位论文 第l 章绪论 但这种失配并不一定是由于网页内容与文本广告不相关造成的，可能网页内容与 文本广告虽然主题相关，但是它们没有包含相同的描述该主题的词，例如网页中 描述的主题是“减肥”，但是广告中描述的是“瘦身”，这种失配称之为网页和文 本之间存在着词汇阻抗问题( v o c a b u l a r yi m p e d a n c ep r o b l e m ) 1 1 5 】，如图1 6 所示： 阻抗 圃、办、m ，臣习 。网页词汇扩剧 l 广告词扩剥 图1 6 网页与广告之间的阻抗 为了减少网页与广告之间的阻抗，必须对网页和广告使用的词汇进行扩展， 这种词汇扩展技术称之为阻抗耦合( i m p e d a n c ec o u p l i n g ) 【”】，阻抗耦合可以从两 方面来考虑，一是对描述网页主题的关键词进行扩展，二是将广告商指定的广告 词进行扩展，但是越多的广告词意味着需要支付越多的费用，广告商一般不愿意 选择过多的广告词，所以一般只考虑对网页关键词进行扩展。 为了提高网页与广告匹配的准确率，减少他们之间的失配，本文提出了一种 新的基于语义的内容定向广告投放算法，该算法的主要创新点有：1 发现了不同 类型的网页具有不同的客观属性称之为网页特征，并将这种网页特征应用在内容 定向广告投放算法中；2 针对内容定向广告问题，提出了一种改进的向量空间模 型，该模型能够区分网页和广告不同特征的重要性；3 提出一种改进的短文本相 似度测量算法来计算词与词之间的相似度；4 提出一种新的基于语义的内容定向 广告投放算法，该算法利用词与词之间的关系如同义词、近义词等，对描述网页 主题的关键词进行扩展，然后利用改进的空间向量模型将扩展后的网页与文本广 告进行匹配，实验表明j 对比于现有的基于经典向量空间模型和相似网页词汇扩 展技术的算法【”】，这种算法较好地解决了网页内容与文本广告之间存在的失配问 题，较大幅度地提高了广告投放的准确率和召回率。 行为定向广告的主旨是利用用户的网络浏览行为，提供符合用户意图的广告 信息，它主要通过分析用户的网页历史访问记录来挖掘有价值的用户行为信息， l o 浙江大学硕士学位论文 第1 章绪论 并针对这种信息投放与之相关的广告，因此行为定向广告能给予更符合用户需求 的广告内容。针对行为定向广告问题，本文提出了一种全新的基于用户行为特征 分析的行为定向广告投放算法，该算法的主要创新点有：1 根据用户的历史访问 记录，提出了一种用户行为特征模型；2 根据用户行为特征模型，提出了一种用 户行为特征分析算法来计算反映用户行为特征网页簇的权重；3 根据用户行为特 征模型和用户行为特征分析算法提出了一种高效的行为定向广告投放算法，实验 表明这是一种有效的行为定向广告投放算法。 1 5 本文的组织方式 本文按如下方式进行组织：第2 章将介绍定向广告目前的研究现状以及一些 相关的研究工作，第3 章将介绍网络定向广告的系统架构，第4 章将介绍用于计 算网页和广告之间相似度的模型一改进的向量空间模型，第5 章将详细介绍本文 提出的基于语义的内容定向广告投放算法，第6 章将介绍本文提出的基于用户行 为特征分析的行为定向广告投放算法，第7 章将介绍所做的定向广告实验以及相 应的结果分析；第8 章对全文进行总结并进行展望。 1 6 本章小结 本章先对定向广告的发展背景以及研究意义进行了讲解，然后较为详细地介 绍了网络定向广告，接着又介绍了定向广告的特点和难点，最后针对定向广告问 题，介绍了本文将要研究的内容和创新点。 浙江大学硕士学位论文第2 章相关工作介绍 第2 章相关工作介绍 2 1 内容定向广告相关工作 在内容定向广告出现之前，大多数的研究都集中在赞助搜索广告上，赞助搜 索广告的投放算法相对来说较为直观，广告商向搜索引擎公司购买广告关键词， 当用户在搜索引擎中进行搜索时，将用户提交的查询关键词与广告商购买的关键 词进行匹配，或者将用户的查询关键词进行一些适当的词汇扩展后在与广告关键 词进行匹配，对匹配的广告然后按广告商的出价，或者按照广告与关键词的相关 度，又或者是根据用户可能的点击情况进行排序，并最终显示在搜索结果页面上， 搜索引擎公司一般会综合考虑这些因素形成一个最终得分并按这个最终得分进 行排序。尽管赞助搜索广告已经取得了很大的成功，但是对于用户来说，他们上 网的大部分时间都花在了浏览页面上，而不是在查询结果页面上，因为用户只有 对某些事物有疑问或者好奇时才会到搜索引擎上进行搜索，当用户获得搜索结果 后，会点击他感兴趣的链接，从而离开搜索结果页面而进入目标网站的网页，对 比于用户花在普通网页上的时间，用户停留在查询结果页面上的时间是非常少 的，因此内容定向广告具有很大的潜力，是信息检索领域目前一个非常热门的研 究课题。 相比于赞助搜索广告，内容定向广告的投放算法则没有这么直观，它需要对 网页和文本广告的内容和结构进行分析，自动地提取出网页内容的主题，并且根 据这个主题快速有效的从广告库中选择出最相关的广告，这是一个非常有挑战性 的课题。定向广告是非常新的研究领域，先前的研究人员已经从不同的角度开展 了一些卓有成效的研究工作。 c w a n g ，ez h a n g 等人在文献 1 6 1 中的研究工作证实了投放与用户兴趣相关 的广告可以改善用户体验并且增加广告的点击率。ec h a t t e r j e e 等人在文献 1 7 】中 也指出广告越有针对性，效果就越明显。他们的研究工作证明了网页内容与广告 主题相关的重要性。 1 2 浙江大学硕士学位论文第2 章相关工作介绍 r i b e i r o - n e t o 等人在文献【1 5 】中提出了十种网页与文本广告的匹配策略，这些 策略都基于向量空间模型 1 8 ，在这个模型中网页和文本广告都表示为同一空间 中的向量，网页和广告的相似度由这两个向量之间夹角的c o s i n e 值来衡量。虽然 网页和文本广告都被映射到统一的向量空间，但是网页和文本广告之间仍然存在 失配问题，为了解决这个问题，作者提出了一种基于相似网页的内容定向广告投 放算法，该算法基于与目标网页相似的网页集，利用这个网页集对目标网页的词 汇进行扩展，然后将扩展后的网页与文本广告进行匹配，找出最适合该网页的广 告，实验表明广告匹配的准确率和召回率得到了一定程度的提高。 r i b e i r o - n e t o 和a l a c e r d a 等人又进行了后续的研究工作，在文献 1 9 1 5 b 提出 一种新的匹配算法，该算法利用遗传规划算法来生成一个匹配函数，实验表明对 比于文献 1 5 】中提出的匹配算法，该匹配函数能够提高网页与文本广告之间的匹 配精度。 m u r d o c k 等人在文献 2 0 】中又提出了一种基于机器翻译的定向广告投放算法 来解决广告投放时网页与文本广告之间的词汇失配问题，实验表明对比于基准方 法，机器翻译的方法可以在匹配精度上获得较为显著的提高。 b r o d e r 等人则从语义的角度对投放算法进行了改进，在文献 1 3 】中提出一种新 的投放算法，该算法利用了一颗人工构建的分类树来对网页和文本广告进行分 类，分到同一类中的网页和广告有很好的主题相关性，网页和广告匹配的最终的 相关度是网页和广告所属类型的相似度和它们本身相似度之间的加权和，实验表 明对比于只考虑句法的方法，同时考虑语义和句法的方法可以在准确率和召回率 上得到较大的提高。 定向广告的投放过程中涉及到复杂的语义推理过程，因此仅依赖于信息检索 中的相关性概念以及传统的搜索概念是不够的，c i a r a m i t a 等人在文献 2 1 中提出 了一种基于机器学习的投放算法，该算法通过捕捉网页内容与广告内容词之间微 小的语义关联来建立一个用于匹配广告和网页的机器学习模型，该模型中使用了 网页和广告中词的统计相关性，当两个词在外部的语料库如搜索引擎的查询日志 或索引中具有很高的相关性时，这两个词被认为是统计相关的。实验表明这种利 浙江大学硕士学位论文第2 章相关工作介绍 用了词之间语义关联关系的算法能有效的提高广告投放的准确率。 另一种解决内容定向广告的办法是通过从网页中抽取主题相关的关键词并将 它与广告进行匹配进而把内容定向广告问题转换赞助搜索广告问题。w y i h ，j g o o d m a n 等人在文献 2 2 】中提出了一种用于广告的关键词抽取算法，该算法综合 考虑了词的t f - i d k 词的长度、词在网页中出现的位置等诸多特征来决定词的重要 性，并根据候选词的重要性进行排序最终选出代表该网页主题的关键词。通过研 究他们发现候选词的t f - i d f 特别是候选词在搜索引擎日志中出现的频率是提取网 页关键词最有用的特征。虽然这是一种较为有效的网页关键词提取算法，但是将 该算法应用在内容定向广告中究竟能达到多高的准确率仍是一个有待研究的问 题。 由于内容定向广告需要处理成千上万的网页和广告，因此整个系统的效率以 及计算代价是十分关键的，上面提到的大多数算法都是线下处理的，它们将网页 内容与广告事先匹配好，当用户访问网页时，直接选择匹配好的广告展现给用户， 这种方法对于静态网页是比较有效的，但是网上存在很多动态网页，这些动态网 页是根据用户输入的参数实时生成的，因此无法实时获取，如果要在这类网页上 投放内容定向广告，必须对这些动态生成的网页进行实时处理。基于先前在网页 摘要生成方面的研究【2 3 ，2 4 ，2 5 ，2 6 ，2 7 ，2 8 ，2 9 ，针对在动态网页投放内容定向广告的 问题，a f i s 等人在文献 3 0 中提出了一种较为有效的实时投放算法，由于网页内 容太大，网络负载吃不消，因此该算法根据网页内容生成内容摘要，然后根据内 容摘要选择主题相关广告，实验表明这是一种较为有效的实时广告投放算法。 对于内容定向广告，怎样评价投放算法的有效性也是一个十分关键的问题， 在信息检索领域，一个比较普遍的衡量方法是跟踪用户的点击情况，根据点击率 来衡量算法的有效性【3 l 】，文献 3 2 ，3 3 】提出了两种预测广告点击率的方法。但是广 告的有效性不仅取决与用户的点击情况，有时虽然用户没有点击广告，但是它仍 然给用户传递了有用的信息，对于品牌广告尤为如此，文献 3 4 表明广告的有效 性可以根据广告与它所在网页内容主题的相关性来衡量。 本文将目光集中在网页内容与文本广告之间的词汇失配问题上，在该领域， 1 4 浙江大学硕士学位论文 第2 章相关工作介绍 目前的研究工作虽然已经取得了不错的成果，但是也存在这一些不足之处，例如 由r i b e i r o - n e t o 等人提出的基于相似网页的内容定向广告算法是找出与目标网页 相似的网页集合，然后从这个网页集合中找出描述网页主题的关键词，该算法存 在两点不足，一是与目标网页相似的网页不一定存在，即便存在，要从众多的网 页中找出相似网页并非一件易事，而且该算法仅仅把网页和广告当成普通的文 本，没有区分网页和广告不同特征的重要性，并利用这些特征来进一步提高匹配 的准确度；二在扩展关键词时仅从句法上考虑而没有从语义上进行考虑，而且相 似的网页中不一定存在能够描述目标网页主题的同义词或者近义词。 本文提出了一种新的基于语义的内容定向广告投放算法，该算法根据词汇之 间的语义的相似度来对目标网页的关键词进行词汇扩展，从而减少网页与文本广 告之间的失配，并且在匹配网页和广告时考虑了网页和广告的不同特征，实验表 明该算法能够显著的提高网页与文本广告之间匹配的准确率和召回率。 2 2 行为定向广告相关工作 行为定向广告的主旨是利用用户的网络浏览行为，提供符合用户意图的广告 信息，它主要通过分析用户的网页历史访问记录来挖掘有价值的用户行为信息， 并针对这种信息投放与之相关的广告。行为定向能够提高广告的投放效果，这一 点之前是基于人们的实践经验得出的，但最近j y a n 等人 3 5 】通过研究证实了这一 点，他们发现行为定向能够切实的改善网络广告的投放效果。 行为定向广告是一种全新的广告投放技术，在产业界，g o o g l e 已经开始这方 面的探索与实践，它的定向广告产品a d s e n s e 通过用户浏览器中c o o k i e 来跟踪用 户的网页浏览和搜索行为，并且根据用户的行为记录将用户划分到一个事先建好 的分类中，在投放广告时优先考虑该分类的广告。在学术界，目前对行为定向广 告的研究还非常少，之前将用户行为运用于广告仅局限于根据用户反馈来改善广 告与查询关键词或网页的匹配效果 3 6 ，3 7 ，3 8 ，如d c h a k r a b a r t i 等人在文献 3 9 】 中将用户的点击行为运用到了内容定向广告中。 最近，基于j y a n 等人的研究成果【3 5 】，t i n gl i 等人在文献 4 0 q h 提出了一种 浙江大学硕士学位论文第2 章相关工作介绍 基于马尔可夫链模型的算法，将行为定向整合到了内容定向广告中，他们提出了 一种新的行为相关性，在计算相关性的时候同时考虑了这种行为相关性和广告与 网页内容主题的相关性，将这两种相关性进行线性组合，并且通过交叉验证获得 了最佳的组合参数，通过实验发现，这种新算法要比只考虑内容相关性的算法在 准确率上高出1 8 。 本文在现有研究的基础上，针对行为定向广告问题，提出了一种全新的高效 的行为定向广告投放算法，该算法能够在用户网页浏览网页时实时地分析用户行 为特征，并且针对用户行为特征的变化实时的对投放的定向广告做出相应的调 整，以便跟踪用户最新关注的事物，同时算法还能够挖掘出用户长期关注的事物， 这类事物一般是用户的兴趣爱好所在，因此算法在投放广告会对这类事物的广告 有所偏好，大量实验表明这是一种较为高效的行为定向广告投放算法。 2 3 本章小结 本章先从阻抗耦合、语义、关键词抽取、实时广告投放和广告效果评价等多 方面介绍了内容定向广告的现有的研究成果，并且针对现有工作的不足提出了新 的内容定向广告投放算法，然后对行为定向广告的相关研究工作做了详细的介 绍，并在现有基础上提出了新的行为定向广告投放算法。 1 6 浙