（计算机应用技术专业论文）基于视觉信息的上下文广告关键词提取算法研究.pdf

浙江大学硕士学位论文摘要 摘要 互联网已经成为目前最为重要的广告媒介之一，它能够以低成本将商品和服 务向全世界的各个角落展示，这种独特能力吸引了众多的网络广告投资，也无形 中带动了互联网的发展。 在几年前，由于众多互联网公司的倒闭，一度严重影响了在线广告的投资， 这种情况一直到2 0 0 2 年才有所缓解。而碰巧的是，促使在线广告在次得到发展 的原因是出现了一种新的广告形式一搜索引擎广告。据f o r r e s t 君r 研究公司预测， 到2 0 1 0 年，这种广告形式将代表超过1 0 0 亿美元的庞大市场。 关于这一领域的研究，主要由各大商业搜索引擎公司开展，并形成了多个产 品，比如g o o g l e 的a d s e n s e ，y a h o o 的p u b l i s h e r n e t w o r k 等。这些系统都很成功， 但其内部机制缺少透明性，对外仍是一个黑盒。本文尝试探索这个领域，并介绍 作者在基于内容的在线广告系统方面的研究工作。 考虑到广告的放置主要取决于所在的网页内容以及用户对该网页的理解，而 用户最终是通过网页的浏览器渲染结果来理解这个网页的，这为利用网页的视觉 信息来提取可行的广告关键词提供了一个可行的背景。 本文首先介绍了作者在识别网页标题方面的工作。作者提出了一种基于网页 标题模式学习和视觉特征的网页标题提取算法。 其次介绍了作者在识别网页正文方面的工作。作者提出了一种基于网页视觉 特征和内容特征相结合的学习机制。首先使用v i p s 算法对网页进行语意分割， 形成一棵层状语意块树，并使用网页标题提取算法定位网页的真实标题，配合 v i p s 结果一同确定网页的正文部分。 随后介绍了作者对寻找网页关键字问题的研究。我们的目标是尽量最大化网 页和广告之间的语意关联度，为此我们建立了一个基于网页正文、视觉特征、内 容特征、统计结果的学习模型，并比较了多个特征类趔对最终结果的贡献。 关键词上下文广告，网页分块，统计语言模型，视觉特征，关键字提取 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t i n t e m e th a sb e c a m et h em o s ti m p o r t a n ta d v e r t i s i n gm e d i u m ，i t su n i q u ea b i l i t yt o d i s p l a yt h ev a r i o u sg o o d sa n ds e r v i c e st oa l lc o m e r so f t h ew o r l d s 、v i ml o w - c o s th a s a 性阳c t c dal a r g en u m b e ro fn e t w o r ka d v e r t i s i n gi n v e s t m e n la n da tt h es a m e h a s b o o s t e dt h ed e v e l o p m e n to f t h ei n t e m e t af e wy e a r sa g o ，b e c a u s eo ft h eb a n k r u p t c yo fm a n yi n t e m e tc o m p a n i e s ，t h e r e o n c eh a db e e nas e r i o u si m p a c to no n l i n ea d v e r t i s i n gi n v e s t m e n t s u c hh a db e e nt h e s i t u a t i o nu n t i l2 0 0 2w h e ni tg o ta l l e v i a t e d i n c i d e n t a l l y , i tw a st h ee m e r g e n c eo fan e w f o r mo fa d v e r t i s i n g - - s e a r c he n g i n ea d v e r t i s i n g , t h a th a dp r o m o t e dt h ed e v e l o p m e n t o f t h eo n l i n ea d v e r t i s i n g u pu n t i ln o wm o s ts e a r c he n g i n ed e v e l o p m e n th a sg o n eo na tc o m p a n i e sw i t l l l i t t l ep u b l i c a t i o no ft e c h n i c a ld e t a i l s o b rg o a li st r y i n gt oe x p l o r et h ed e t a i l so fs u c h s y s t e ma n di m p r o v es u c hs y s t e m si ns o m ea s p e c t i nt h ef i r s tp a r t , w ei n t r o d u c eo u rw o r ko n t h er e s e a r c ho fan 棚w e bp a g et i t l e r e t r i e v a la l g o r i t h m n 圯a l g o r i t h mc o m b i n e st h eu s eo faw e bp a g et i t l ep a r e m e x t r a c t i o nm e t h o da n dm a n yv i s u a lf e a t u r e st oc r e a t eam o d a lt oe x t l a c tt h er e a lw e b p a g et i t l e i nt h es e c o n dp a r t , w ei n t r o d u c e0 1 1 1 w o r ko nt h er e s e a r c ho fad e wa l g o r i t h mo f w e bp a g em a i n - t e x te x t r a c t i o n f i r s t , w eu s ev i p st os e g m e n tt h ew e bp a g et og e ta t r e eo fv i s i o nb l o c k s t h e nw eu s e o u ra l g o r i t h mi n t r o d u c e di nt h ef i r s tp a r tt oe x t r a c t t h ep a g et i t l e i nt h el a s t ，w es e a r c ht h eb l o c k sw h i c hc o n t a i nt h et i t l ei nt h e v i s i o n - b l o c kt r e et oo b t a i nt h em a i n - t e x tp a r to f t h ew e bp a g e i nt h et h i r dp a r t , w ef o c u s d no u rw o r ko nt h ee x t r a c t i o no fk e y w o r d sf r o mw e b p a g e s w ea i mt of m do u ta m e t h o dt oe x t r a c tt h ek e y w o r d st om a x i m i z et h es e m a n t i c a s s o c i a t i o nb e t w e e nt h ew e b s i t ea n da d v e r t i s e m e n t s i nt h el a s tp a r t , w ei n t r o d u c et h ea r c h i t e c t u r eo f o u rc o n t e x t u a la d v e r t i s i n gs y s t e m i nd e t a i l s k e y w o r d s c o n t e x t u a la d v e r t i s i n g ，p a g es e g m e n t , s t a t i s t i c a ls e m a n t i cm o d e l ，v i s u a l f e a t u r e s ，k e y w o r de x t r a c t i o n 浙江大学硕士学位论文 图目录 图目录 图2 1 上下文广告示例7 图2 2 搜索引擎的系统构架7 图2 3v i p s 算法分块流程图1 0 图2 4 样本网页分割结果示意图。1 l 图2 5 网页语意块层次结构图1 1 图2 6 阶跃激励函数1 6 图2 7 多输入神经元1 6 图2 8 一个3 层2 输出前馈网络1 7 图3 1 酗( r 融c i a 树单节点合并2 0 图3 2 插入数据后的r i c i a 树2 l 图3 - 3 标题提取算法。2 4 图5 1 上下文广告系统的构架3 9 i 浙江大学硕士学位论文表目录 表目录 表3 1 标题识别特征集2 3 表3 2 标题提取算法实验结果性能评测2 6 表4 1 关键词提取性能比较3 7 表4 2 从算法中减少特征的系统性能，3 7 表4 3 在基准系统上添加特征的系统性能3 7 巍江大学硕士学位论文 第1 章绪论 第l 章绪论 1 1 课题背景 当今社会早已迈入信息社会，用户通过网页来获取信息的行为日益普遍。 2 0 0 5 年美国有6 6 的网民比例，而在2 0 0 6 年，这一数字已经增加到7 3 。作为世 界上第二大互联网市场的中国，现在已经拥有超过1 2 3 亿的网民m l ，这个数字 将在未来的5 年内增长到2 3 亿。互联网用户的数目在随著互联网本身的发展而 增长，网络用户对互联网的使用页是越来越广泛。当今互联网的规模已近2 0 0 亿 页面之多，这还没有考虑到可以产生无数新网页的动态( 也称为d e e p w e b ) 的结 果。这么巨大的信息量，使得由y a h o o 等早期互联网公司所倡导的传统信息获取 过程一目录式分类式导航浏览，无法满足人民不断增长的信息需要。现在，通过 搜索引擎获取所需信息的方式已经成为当前的主流，搜索引擎已经成为信息的入 口。 网络的兴起，也伴随着另一个产业的诞生一网络广告。大多数搜索引擎开始 都源于大学的研究项目，这些项目关注于构架和算法的研究和开发，而更少的关 注研究成果的回报。而即使这些成果过渡成为商品后的好长一段时间，它们也都 仅仅是面向内容提供方( 任何以w e b 网页方式向互联网用户提供信息的机构，最 普通即是我们熟知的商业网站) 和普通用户的一种免费的资源。然而，技术的提 高和产品的维护以及网络带宽等都需要大量的资金投入，这些因素迫使搜索引擎 公司开始研究对策一如何从内容提供方那产生收益。这些对策后来演变成为多种 商业机制。这之中最有名的也是过去搜索引擎采用的策略是一种称为付费放置 ( p a i dp l a c e m e n t ) 的策略。内容提供方付给搜索引擎公司一定的费用，而搜索 引擎则将该内容提供方登记在其数据库中，并在搜索返回结果中相应提高该内容 提供方的排名，或者将该内容提供方放置在搜索返回结果页面的赞助方列表中。 一个付费放置策略需要对搜索引擎的排名算法进行小小的改动或者需要对返回 结果的页面的显示方式进行一些改动，而这些改动的成本相对来说并不是很高。 现在，付费放置在搜索引擎( 如g o o g l e 、b a i d u 等) 、信息入口( 如y a h o o ) 、元 搜索引擎( 如m e t a c r a w l e r ) 等中得到了广泛的使用。 至今，互联网已经成为目前最为重要的广告媒介之一，它能够以低成本将商 品和服务向全世界的各个角落展示，这种独特能力吸引了众多的网络广告投资， 浙江大学硕士学位论文第1 章绪论 也无形中带动了互联网的发展。在几年前，由于众多互联网公司的倒闭，一度严 重影响了在线广告的投资，这种情况一直到2 0 0 2 年才有所缓解。而碰巧的是， 促使在线广告再次得到发展的原因是出现了一种新的广告形式一搜索引擎广告。 据p o r r e s t e r 研究公司预测，到2 0 1 0 年，这种广告形式将代表超过1 0 0 亿美元 的一个庞大市场。 1 2 研究意义和目的 上文分析了当前在线广告的发展。从分析看出，随着信息时代的到来，搜索 引擎已经越来越接近人们的日常生活，伴随而来的在线广告也随着这股热潮得到 了迅猛的发展，目前已经形成了一个巨大的市场，对这个方向和技术进行研究的 需求也越来越明显。另一个方面，当前的大多数在线广告形式都一定程度上会带 来人的厌烦情绪，对在线广告的研究和改进工作可以有效改善人们日常浏览网页 的体验。正是在这样的环境下，通过研究相关的上下文广告系统的优缺点，如 g o o g l e 的a d s e n s e ，y a h o o 的y a h o op u b l i s h e rn e t w o r k 系统，提出了一种基于 网页视觉信息和的网页主题的关键词提取算法，并且对这个算法进行了有效的实 验。 在算法的实现中采用了一系列的改进方法，如提取网页的真实标题的算法、 提取网页正文部分算法、利用多个特征信息过滤网页中关键字的算法等，有效的 提高了寻找到的广告关键字的主题关联程度。 1 3 论文组织 本文重点研究的是上下文广告系统中的网页关键词提取算法，我们的目标是 尝试构造出一种可以更加有效的选择和当前网页主题相关的关键字的算法，从而 一方面可以有效改善人们浏览网页的体验，另一方面也可以提高人们点击网页广 告的概率。 第2 章介绍上下文广告系统现状以及相关技术，包括在线广告的种类和优势、 搜索引擎的大体构架、上下文广告系统的大致构架、网页分块算法的相关研究、 关键词提取算法中相关的基础技术、文本相似度匹配等。 第3 章将介绍作者在寻找网页真实标题方面的工作，这里我们提出了一种基 于网页标题模式提取和视觉特征相结合的提取算法。 第4 章将介绍作者在寻找网页正文方面的工作，这里我们提出了一种基于网 页视觉分段的正文提取算法。 2 浙江大学硕士学位论文第1 章绪论 第5 章将介绍作者在寻找特定网页关键字方面的工作，这么我们提出了一种 基于网页视觉特征的关键字选择算法。 第6 章描述了作者所设计的一个上下文广告系统的构架雏形，并对系统中各 个部件进行较为详细的介绍。 本文之后对全文作一个总结并对接下来的研究方向作出展望。 1 4 相关研究工作 之前的研究工作显示，使用不同的特征信息，例如结构化信息和广告指向的 广告商页面信息，能提高广告的关联匹配概率，这里所说的有效广告指的是和当 前网页关联程序比较高的广告。例如一个介绍a p p l e 的网页，最可能与之匹配的 是a p p l e 公司相关的产品或者作为水果的苹果相关的广告。之前的研究工作只指 出了一些特征对于寻找关联广告有作用，但未指出如何来确定这些特征的相对重 要程序，也即特征的权值( w e i g h 0 ，以及如何同时使用这些特征等一些重要问题。 在t 6 1 0 e ，作者指出关键字的性质和大小将影响广告的点击率。关联度同样是 许多学者关注的焦点。 在【3 】中，作者提出了多种针对上下文广告系统的广告排序( r a n k i n g ) 策略，这 些策略考虑了广告的结构化部分以及广告所在网页的向外链接页的作用。作者提 到，通过考虑广告的结构化部分和外部链接页面可以提高候选广告的关联度。 在【1 3 j 认为，应该充分利用现有的所有证据特征，并尽量减少放置不相关广告 的概率。由于该工作比较有代表性，下面对这个工作进行简短的描述。作者使用 了一个g p 算法来训练模型。g p 算法在近几年中，已经成功的用在了多个取课 题中，包括文档聚类和分类【4 】，文档排序1 5 j 等。作者在该文中，利用一个真实的 广告数据库以及从巴西一家新闻站点中抓取下来的网页来测试模型，得到了高出 基准模型6 1 7 的效果。 不同的网页类别，在确定广告的相关度时采取的策略会存在一些差别。对于 普通的网页，我们感兴趣的是如何通过网页上的文字以及其它信息去把握网页的 主题；丽对于b l o g 来说，我们感兴趣的是通过这些信息来把握b l o g 主人的特征， 包括兴趣、关注的事务等，可以说b l o g 代表的是个人，而一般的网页代表的是信 息。从这两个方面可以看出，在寻找和网页关联的广告时，对于普通网页，我们 需要尽量寻找和网页主题相近的广告；而对于类似b l o g 这类特殊的网页形式，我 们还需要利用个人的特征来辅助选择关联的广告。 本文重点讨论针对普通网页的广告选择算法的研究工作。 浙江大学硕士学位论文 第2 章相关技术综述 第2 章相关技术综述 2 1 在线广告发展和现状 在线广告【i l 】存在多种形式，同时在线广告作为一种广告形式，和普通的广告 方式存在很大的差异，下面首先对在线广告一介绍，包括其优点以及存在的形式 等。 2 1 1 在线广告优势 网络广告是多维的，它能够融合文字、图像、声音，传递多感官的信息，让 顾客更深切的感受商品或服务。同时，网络广告的制作成本比较低、速度快、更 改也比较容易，较之电视广告形式，经营决策变化就能够即时反映出来。广告商 在制作广告时，会考虑商品或者服务所面向的群体，当前互联网用户的年龄集中 在中青年，这个群体较之其它的群体具有较高的消费能力。 网络广告相对传统广告的其他优势还体现在网络在线广告不受时间和播放 次数的限制，用户能够在任意时间任何地点看到；商家可以对用户的反应和行为 进行统计跟踪，从而有效衡量广告的效果，商家还可以通过电子邮件等形式向用 户传递广告信息或进行问卷调查，从而更加有效的获得第一手的客户反馈信息。 2 1 2 在线广告收费模式 目前存在着多种广告收费模式，下面分别进行介绍： 1 c o s t p e r t h o u s a n d i m p r e s s i o n s 收费模式，即c p m 模式。这种模式借鉴了 传统媒体广告业中以每千人成本作为确定该媒体广告价格基础的计算方 法，以每千次浏览作为计价单位。c p m 模式的优点是收费只和访问人次 相挂钩，同时避免客户只愿在首页做广告的弊病，因为按照规定，在首 页做广告和在其它页面做广告的收益和支出比是一样的。 2 c o s tp e r t h o u s a n dc l i c k e d t h r o u g h 收费模式，即c p c 模式，这种方式以 广告被用户点击并链接到广告商的网站或详细内容页面1 0 0 0 次作为计 价单位。这种方式的优势是它真实反映了用户的行为，或者说，它反映 了用户对该广告所代表的商品或者服务的感兴趣度。 3 c o s tp e rc l i c k 收费模式，这种方式按照广告被点击次数进行收费，收取 的费用和点击的次数成正比。广告商会有一个月财务支出额度，当该月 4 浙江大学硕士学位论文 第2 章相关技术综述 的额度超出后，取消显示该广告。这种模式目前主要有如下两种运用： a ) 搜索广告：递交搜索查询后返回的查询结果中显示的赞助商列表， 如在g o o g l e 中查询a p p l e 在查询结果中显示“苹果公司”相关的广 告条目。 ”上下文广告：广告提供商，如l ( 3 0 0 9 l ea d s e n s e 、y a h o op u b l i s h e r n e t w o r k ，提供给网站一段代码插入到网页中，当用户浏览该网页时， 将自动显示和当前网页主题相关的广告。 4 每行动成本收费模型。使用c p m 和c p c 的风险是广告商可能需要支付 大量的费用，而带来的收益却没有得到大幅的增长。为避免这种情况的 发生，广告商在广告带来产品的销售后按销售数量支付给网站比一般广 告价格更高的费用，这种模式大大减轻了广告商的财务压力。 2 1 3 关键词广告介绍 在这种技术中，当用户在搜索引擎中搜索某几个关键字，如a p p l e 、c o m p u t e r ， 搜索引擎在接受到这个请求后，除了返回普通的匹配网页外，还在后台自动将查 询关键字和由广告商提供的广告关键词进行匹配，并依据广告商愿意为每次广告 点击出资的数目进行排序，返回靠前的几则广告。 下图是- - n 在b a i d u 搜索引擎中查询a p p l e 关键字返回的广告图示： a p p l e 连锁店 百存搭配便用专为j p o d 设计的至 酷配件，全面武装你的i p o d 。 姗 wa p p l ec o r nc r l 目前比较有名的基于广告关键词的搜索引擎广告系统包括g o o g l e 公司的 a d w o r d s 广告计划、b a i d u 公司的竞价排名服务、y a h o o 公司的y a h o op u b l i s h e r n e t w o r k 等。 2 1 4 上下文广告介绍 这种广告方式的出现很大程度上是由于基于关键词的搜索引擎广告带来了 庞大的市场，促使众多网站以多种方式和多种上下文提供在线广告服务。例如， 当用户浏览某网页时，自动在网页的某个位置显示和当前网页主题接近的广告， 比较最有名的是g o o g l e 公司的a d s e n s e 系统。这种广告方式利用了用户在浏览 网页时的短暂信息兴趣，从而比传统的在线广告有更高关注度【9 】【1 0 1 1 2 2 1 。 基于网页内容的广告方式，也称为c o n t e n t t a r g e t e d a d v e r t i s i n g ，和基于关键 浙江大学硕士学位论文第2 章相关技术综述 词的广告方式最大的不同是前者利用的是当前浏览网页的内容这个上下文，而后 者使用搜索关键字作为匹配上下文，前者需要从网页内容中自动选择关键词或更 一步判断网页的主题，而后者已经有用户选择了关键词。 典型的基于内容的广告系统分析一个站点页面，例如一个新闻页面，或者是 个b l o g 页面来寻找该页面中那些突出的关键词，并随后将这些关键词发送到广 告系统，广告系统将这些关键词和广告数据库进行匹配，返回广告系统认为最合 适的广告交由页面进行显示。选择合适的关键词可以在两个方面有效的帮助用 户。首先，合适的关键词可以引导用户查看f 电她感兴趣并想购买的商品或者服务。 其次，和当前页面内容匹配关联程度越高，用户就越有可能点击广告、浏览广告 详细信息并进而购买该商品，这是广告商、页面所有者、中间广告系统、用户互 利的4 赢方式。 从广告商的角度，选择合适的关键词更加显得非常重要了在一些领域，如 语音识别、机器翻译，对产品1 0 的改进并不能常常带来同样的回报，但对于关 键字寻找这个问题来说，1 0 0 , 6 的改进可能带来超过1 0 的点击率提升，从而有效 提高潜在的收益。 在上面，我们对在线广告做了简单的介绍，为方便下面的讨论和描述，我们 对一些在下面需要或者涉及到的技术做一个简短的回顾。 2 2 搜索引擎构架 搜索广告业务的成功得益于搜索引擎在现在日常生活中充当着越来越重要 的作用，从查找某篇相关的论文到查询某个商品的价格，从寻找某个电脑故障的 原因到查找某个公司的网址，搜索引擎已成为我们获取信息的一个重要的途径 基于互联网的搜索技术和传统的瓜技术存在着众多的区别，最主要的区别 在于现代的搜索引擎所需要处理的巨大的信息量，以及这种信息所分布的形式。 系统需要满足如下的要求：抓取网页技术必须非常快，才能跟上网页变化的 速度；存放索引和文档的空间比较足够大；索引需要能够处理t 级别的数据量； 处理查询必须非常快；系统要足够稳定，要能有很好的容错性。 第一个真正意义上的现代搜索弓i 擎出现在1 9 9 4 年7 月。当年4 年，美国斯 坦福大学的两名博士生，大卫菲勒和美籍华人杨致远共同创办了大家熟知的超级 目录索引y a h o o ，从此搜索引擎进入高速发展的时期。 一个典型的搜索引擎可以用图2 2 进行说明： 浙江大学硕士学位论文第2 章相关技术综述 内容提供商网站广告商投标的关键词 诺基亚n 7 0 作为国内上市的首款2 0 0 万像素$ 6 0 智能手机诺基 亚n 7 0 的功能非常强大，赢得了不少朋友的青睐。 作为一款在2 0 0 5 年上市的手机，n 7 0 的价格随着诺 基亚新品推出也一路下跌，虽然此次跌价幅度不 大，但令这款产品的性价比又得到了一定提升。 关键词 匹配 广告代理公司 ( g o o g l ee t c ) 图2 - 1 上下文广告示例 显示广告 图2 - 2 搜索引擎的系统构架 一 系统包括4 个基本的组件：下载模块( c r a w l e r ) ，链接分析模块( w e bm a p ) ，索 引模块( i n d e x e r ) ，查询服务模块( q u e r ys e r v i n g ) 。下面简要介绍下搜索引擎的工作 流程，以对图2 2 进行补充说明。 首先，下载模块从互联网上下载包括普通网页在内的所有可以索引文件( 例如 网页、图像、m p 3 、视频、p d f 文档等1 ，保存在文件数据库中。 然后，链接分析模块从文件服务器中的各个网页文件中提取出链接( 包含链接 7 浙江大学硕士学位论文第2 章相关技术综述 到其它网页的u p l ) ，构建页面之间的链接关系，并进行一系列运算( 现在大部 分搜索引擎都采用p a g e r a n k 的技术) 。 接下来，索引模块利用文件数据库中的文件以及由链接分析模块得到的网络 图信息，为页面创建倒排索引，索引的结果保存在索引数据库中。一般会包含多 种索引类型，从最简单的文本索引到各类服务于特定目的的工具索引。 当查询服务模块接收到用户查询请求时，就会按照某种匹配方法从索引数据 库中查找出一系列的相关文档。 最后，使用搜索引擎特定的排序方法将这些相关的文档排序，并将排序后的 结果返回给用户。 想详细的了解搜索引擎的细节，请参考 2 1 0 1 i 3 2 i 。 2 3 网页分块算法概述 正如一个国家被划分成多个省份，每个省份相对独立一样，一个网页也可以 划分成多个块，每个块相对独立，共同组织成一个完整的整体。 例如，对于很多网页，我们可以分成如下的5 个大块：上、下、左、中、右。 上对应于网页的导航栏，菜单等部分；下对应于网页的版权栏，公司信息栏等部 分；左右块可能是信息导航栏；中可能对应于网页的正文部分。每个大块内部， 还可以细分成多个语意耦合度更高的子块。从语意的角度看，块内部的语意耦合 度要高于块间的语意耦合度。 在过去的几年内，已经提取出了多种网页分段的算法，下面对其中的3 个主 要种类进行介绍。 2 3 1 基于d o m 的分块算法 这类方法把网页视为一棵d o m 树，并通过分析网页中比较重要的t a g 标签来 分析判断网页的分块情况，这些t a g 包括 p 、 、 、 等。但 由于h t r n l 中的 和 标签不只是用于网页的内容组织，同时也用于网页的 布局组织，在很多情况下，网页的d 0 b l 结构趋向于表达网页的内容结构而非显示 结构，而我们关注的是网页的显示结构，从而这类方法并不能精确的区分出网页 中的语意块信息。这类研究工作包括【1 4 1 ”瞎。 2 3 2 基于视觉的分块算法 从人类的角度来看，当一个用户观察w e b 页面的时候，总是会自然的把一个 浙江大学硕士学位论文第2 章相关技术综述 语意块作为一个单一对象来看待，而不会考虑w e b 页面的内部结构是如何描述 的。我们可以利用视觉信息来帮助我们寻找和定位语意块，例如元素的背景颜色、 文本的字体大小颜色以及是否大写加粗、是否包含图像、块和块之间的间距等。 通过结合1 ) 0 m 树进行语意块分析，这类方法解决了【l 刀中的问题，不再依赖于 “每个网页可以划分成5 个区域”这个假定，同时具有更小的分区粒度。这类方 法比起和嘲中的方法还能更好的保证分区中的内容耦合程度。这类研究工作包 括v i p s 算法i ，基于视觉信息的页面分析算法，学习网页块的重要性算法1 3 】 等。 由于本文中要使用到v i p s 算法，下面对该算法进行一个简短的描述，详细 的算法请参考【i j 。 2 3 2 1v i e s 算法概念定义 b a s i co b j e c t ：代表树中不能在进行细分的块元素( 叶子节点) 。 l a y o u t b l o c k ：由单个或者多个基本对象组成单个语意块。 s e p a r a t o r ：位于两个布局块之间的对象，有水平垂直之分。 2 3 2 2 v i p s 算法模型描述 一个页面可以用一个三元组q = ( o ，m ，来进行刻画。其中， o = ( q 。，q 2 ，n 。) ，表示该页面上所有的语意块( 也可以称为网页予块) 集合， 这些对象之间没有重叠覆盖。对应一个语意块q 。，也可以用一个三元组 q = ( o ，o ，4 ) 刻画，从而形成一个递归定义关系。 0 = 锄，仍，q r 是一组有限数目的视觉分割条，包括水平和垂直分割条。每 个分割条包含有一个权值j 指示它的能见度，同一个d 下的所有分割条具有相同 的权重。 j = ( 蠡，乞，“) 描述了q 集合中两个语意块之间的关系，这种关系使用 占= o x o _ 中u n u l l l 来进行描述。其中的每个f 都是一个形如( q 。q ，) 的二 元组，表示块q 。和q ，之间存在一个分割条。 整个分块过程可以用图2 - 3 进行描述。它包含3 个主要的步骤：页面块提取、 分割条提取、语意块重构。这3 个步骤一起作为一次语意块检测步骤。网页首先 被分割为数个比较大的语意块，并记录下此时语意块所组成的层次结构。对于每 个大的语意块，继续执行该检测过程，直到语意块的d o c 达到预先设定的p d o c 。 9 塑垩查兰塑圭堂垒堕苎兰! 兰塑茎垫垄簦垄 图2 - ：3y i p $ 算法分块流程图 i 两圜圈脚篡兰圣娄婺苫潮 j 獬：= 器：嚣嚣“姗lj 黜：甓戤嚣l 血d 卫t 出丝n 剐血越11 缸垃m 衄f c 。删，c , m l + l l o _ - l o | 镑粉“ n n 0 日啦酶 m m m r 1 + j l y 工口k 口e 自如j 日z 赳 箸2 激- z - -嘲 篇帮等怒”一“蜒翟、 k a m 啦“h 哇等器。 | , e 1 4 、k ( 矗矗n m 十h _ h - “_ _ _ 啊f f ， l 乜m “d 舯h 洲- ta t , 5 p m k + s e e , a lk l e r e q l 月 “m m r e m w i n _ m t 削e _ h 彪m l 自l 自m 随丽 l 舳_ f “a g l 【吐n 硭刊 蛳h t 衄r e d i d h k r “月_ 帆h 瑟幽 l t h 啦h h 刚嘲h l 19 = 。：s ；i 二：一j ? 一；。 l 1 0 浙江大学硕士学位论文第2 章相关技术综述 图2 - 4 样本网页分割结果示意图 我们使用c 撑语言实现了一个基于微软正浏览器的v i p s 算法，在实现过程 中，使用微软的m s h t m l 3 ) 1 组件创建d o m 树结构以及用作内容解析工具。图2 4 显示了使用v i p s 算法对h t t p ：l l p o r t a l m o r g 主页分割后的效果，这里p d o c 值设 置为5 。整个网页被分隔成3 个大的语意块，在图中使用了3 个大的椭圆进行了 标注，每个大的语意块又包含了几个小的子语意块，在图中使用了红色和蓝色矩 形框标注，该分隔结果比较好的反映了网页的语意单元分布。 图2 5 显示了图2 - 4 所对应的语意块层次结构图。这里v b 是v i s i o nb l o c k 的简称。在v b l 1 1 和v b l 2 2 之间存在一个水平分割条，在v b l 2 1 和v b l 2 2 之间存在一个垂直分割条。 图2 - 5 网页语意块层次结构图 2 3 3 基于布局的分段算法 每个网页可以划分成5 个区域；上部、下部、左侧、右侧、中心部分。它的 缺点也很明显，该布局模型不能用在所有的网页中。针对这种思路的研究工作最 典型的是【埘。 浙江大学硕士学位论文 第2 章相关技术综述 2 4 关键字提取算法概述 2 4 1 统计概率模型 2 4 1 1 模型介绍 统计语言模型1 4 | ，简单的说，是一个在所有句子上的概率分布，记为p ( s ) ， 其常常被用在贝叶斯分类器中，充当先验函数或者似然函数的角色。比方说，在 一个自动化语音识别器中，给定一个声学信号a ，我们的目标是识别出对应的最 可能的句子s 。使用贝叶斯框架的一个解决方案如下： j 。= a r g ，m a x p ( s l 口) = a r g ，m a x p ( a is ) j c s ) 在这个模型中，语言模型p ( s ) 扮演了先验概率的角色。而在一个文档分类模 型中，给定一个文档d ，我们的目标是找到该文档所对应的种类c 。在使用中， 一般会存在k 种文档类型，对应的，我们可以构造出k 个语言模型，记为 只( d ) ，易( d ) ，最( d ) 。一种使用贝叶斯框架的解决方案如下： f = a r g 。m a x p ( c i d ) = a r g 。m a x t ( d i 力。p ( c ) 。在这个模型中，语言模型 e o ( 由扮演了似然函数的角色。 为便于引用，下面我们将统计语言模型记为s m l ( s t a t i s t i c a ll a n g u a g e m o d e l i n g ) 。 2 4 1 2 质量评定 对于任何一个随机变量x ( 比如一个商品的价格) ，它的熵定义如下： t - ( x ) = 一p ( x ) l o g j 【p ( 砷】a 变量的不确定性越大，熵也就越大比如说，当一 本书重复的内容比较多时，它包含的信息量就比较小，它的冗余度就比较大。 信息学中另一个重要的概率是相对熵，它衡量两个正函数是否相似，函数如 果完全相同，他们的相对熵就越大。将相对熵用于信息检索时导出的一个非常重 要的概念是词频率逆向文档频率 i t i d f ；e r y , + 肋e ，之中： j z f = 关键词在文档出现的频率文档中关键词的数目 i d f = l o g ( 文档的总数包含该关键字的文档的数目) 我们可以这样来解释这两个概念如果一个词在一个文档中出现的频率比较 高，但这个词是一个常用词，则它对文档的主题预测的能力就比较弱，通过为每 个词赋予一个权值，可以更好的衡量特定词的作用。在信息检索中，当一个词只 浙江大学硕士学位论文第2 章相关技术综述 在特定的几个网页中出现时，通过它可以更加有效的定位检索目标。 给定一个s m l ，为评定该模型的质量，经常使用的方法是求新数据的似然值。 随机给定样本的平均l o g 似然值如下： a v e r a g e - l o g l i k e i h o o d ( d 肘) = 吉e l o g p u ( d , ) 。d = d 1 ，d 2 ，见) 是一个 新的数据样本，m 是给定的语言模型。该式子的右半部分还可以视为关于模型分 布昂的给定数据分布p ( 概率的分布未知) 一个交叉熵经验估计。 2 4 2 文本分词算法 分词研究一直是研究界一个热门，且至今还是一个没有得到完全解决的问 题。当给定一个网页，我们需要首先对网页进行分词处理，将连续的网页文本分 成n 个词组，对这些处理进行后处理，最后从词组中挑选中最代表当前网页主题 的词组用于最后的广告匹配。 本文并不直接涉及到分词的算法研究，在实验过程中，采用了一个试验用的 分词组件。为本文的完整性，在此介绍几种常用的分词算法。 第一种办法也是最简单的是“查字典法”，把一个句子从左向右扫描一遍， 遇到字典中的词就标识出来，遇到符合词( 比如“浙江大学”) 就找最长的匹配， 遇到不认识的字串就分割成单字词。最长匹配类似程序语言词法分析中采用的方 法。这种方法的缺点很明显，过分的依赖于字典，同时，对于复合词情况，最长 匹配并不一定是最优匹配。 第2 种方法是最少词数匹配，算法的思想是将句子分割成尽量少的词组。算 法的缺点也很明显，对于处理二义性问题的能力不足。 第3 种方法使用统计语言模型来解决分词的歧义问题，这种方法目前比较流 行，错误率较前面的几种方法有了非常大的提升。算法的思想是从巨大的语料空 间中学习，统计某个分词序列( 一个字串列表) 出现的概率，并选择概率最大的 那个。 2 5 文本匹配算法概述 文本匹配算法可以简单的描述成如下的形式：给定两段小的文本s 0 ，s 1 ，计 算两者之间的相似度s i m ( s o ，s i ) ，相似度的定义方式依据问题的要求和采用 的方法有所区别。 比较两段文本( 还可以是句子，短语) 的相似度时，已经有多种方法。比较 浙江大学硕士学位论文 第2 章相关技术综述 经典的方法是使用字符串编辑距离算法。给定字符串a 和字符串b ，a 的长度不 一定和b 的长度一样，通过使用一组预定义的操作将字符串a 转化成字符串b ， 转换的代价越低，两者越接近。 但这样的算法存在以下的问题。考虑比较字符串“a r t i f i c i a li n t e l l i g e n c e ”和 字符串“a i ”，这两个字符串表达了相同的含义，但两者共享的字母和单词项却 很少，通过使用字符串编辑距离这样的算法，所得的相似度值接近于0 。在考虑 如下的两个字符串，“g r a p h i c si n t c r f a c c ”和“g r a p h i c sm o d e l s ”，两者虽然在字面 上共享了单词“g r a p h i c s ”，从而所得的相似度值可能是0 5 ，但从语意角度说，这 两者的相似度可能只有0 0 5 。 为了解决这个问题，我们需要寻找一种基于语意相似度的比较方法，而不是 简单的基于比较文本的字面值。但从简单的字符串文本，很难对两者进行比较。 在【5 】中，作者提出了一种解决这个问题的方法。通过利用互联网上巨大的信息仓 库，为这些字符串文本建立一个更大的上下文。通过检查包含这些字符串文本的 文档，我们可以发现其它的关联项，从而使原本简单字符串的语意更加清晰，并 有助于发现和解决字符串可能存在的歧义。 上面的方法可以归纳为两大类，一类基于比较文本本身，另一类基于文本的 语意。前者实现起来简单，速度也较后者快，也是实际运用的最广泛的一种方法， 如用于检测文本的改动( d i f r 工具，c v s 等) 。后者实现起来比较复杂，速度没有 前者快，且存在精度问题，但后者更加接近人的思维方式，在一些场合下，如搜 索引擎的查询关键字推荐，能起到良好的效果。本文中，我们尝试在匹配广告的 过程中添加入这个特性。 2 5 1 基于语意的匹配算法 作者的算法原理很简单，但需要借助于一个搜索引擎来辅助完成工作。将每 个小的文本碎片当成一个查询项，并递交给搜索引擎，从而获得一组包含该文本 碎片的网页集合r r i ，岛，震。，之中n 是一个阀值，指代我们关注的靠前的关联 刚页数目。当使用0 0 $ 距离函数来测量两个网页集合的距离比起直接测量单纯的 文本碎片的距离更具有鲁棒性。由于c o s 距离函数可以作为一个合法的核函数( 从 而可以用在包括支持向量机，线性回归，岭回归等场合) ，通过将返回的关联网 页向量r 作为参数使用在c o s 中，我们可以在处理短文本数据时将这个核函数用 在任何基于核函数的机器学习算法中。 算法并不复杂，故在此列出它的步骤来说明算法是如何工作的。首先来定义 1 4 浙江大学硕士学位论文 第2 章相关技术综述 几个概念。x 代表一个短文本碎片，q e ( x ) 代表对x 的查询扩展( q u e r ye x t e n d ) 。 有了关于文本串x 和y 的查询扩展值q e ( x ) ，q e ( y ) 后，可以通过下式计算x 和y 之间的相似度： s i m i l a r i t y ( x ，y ) 2q e ( x ) q e ( y ) 两个向量q e ( x ) 和q e ( y ) 之间的相似度被定义为两个向量之间的卷积，这里 的s i m i l a r i t y 函数是一个合法的核函数 2 6 神经网络模型 人工神经网络【2 l 】是仿照生物的大脑来工作的，生物的大脑由许多神经细胞组 成，模拟大脑的人工神经网络。a n n 也是由许多称为人工神经细胞( a r t i