（计算机软件与理论专业论文）基于概率模型的名人网页相关度评价研究.pdf

摘要 摘要 个性化检索是当前信息检索的研究热点之一。它根据用户的个性化需求，实 现信息的自动收集、分析和推送等服务。与一般的信息检索相比，服务的针对性 更强，质量更高。相关网页排序结果的优劣是检索服务质量好坏的最根本体现， 凶此网页的相关度评价是个性化检索系统的关键环节。概率模型在用户兴趣建模 上有独特的优势，它引入概率参数，可以更准确地刻画用户的需求，适合个性化 检索的相关度评价。 本文咀名人网页为基础，研究实体网页的个性化检索，旨在提高实体网页的 相关度评价准确率。本文设计并实现了基于概率模型的名人网页相关度评价算 法，探讨了概率模型的训练、模型的改进及查询扩展等三方面问题，总结了概率 模型的规律，提出了多种提高网页相关度评价准确率的方法，并给出了翔实的实 验结果。 本文研究工作的主要创新点有： ( 1 ) 提出了种实体网页的概率模型的训练集选择方法，提高训练效果的 l 司时降低了算法：销。 ( 2 ) 改进模型的概率计算公式，引入更细致的用户反馈信息，优化特征项 的分布概率；改进相关度计算公式，引入词频、网页长度、h t m l 标记等网页信 息，提出对实体分类定制相关度计算公式的思想。 ( 3 ) 针对实体属性信息的特点，提出相关网页和用户查询楣结合抽取相关 特征项进行查询扩展的方法。 实验表明，与名人网页相关度评价的原有模型相比，本文模型在很大程度上 提高了相关度评价的准确率，并且可以真接应用到其他类型实体网页的检索，文 中的方法和结论为实体网页的个性化检索研究提供了参考。 关键词：个性化检索，概率模型，相关度评价，查询扩展 a b s t r a c t a b s t r a c t p e r s o n a l i z 。di n f 0 h n a t i o nr e 砸“a 1i so n eo ft h em o s tp o p u l a rr e s e a r c hd i r e c t i o n s n o w a d a y s i tp r o v i d e s s e n r i c e sl i k ea u t o m a t i ci n f o r n l a t i o nc 0 1 l e c t i o n ，a n a l y s i s ， d d i v e r y 柚ds oo n i t ss e r v i c e sa r ei n o r es p c c i a l i z e d 锄do f 城g h c rq u a l i t yc o m p a r e d w i t ht l l o s eo fg e n e r a li l l f o n n a t i o nr “e v a ls y s t 啪s t h es e i c eq u a l i t yi sm a i n l y r e n e c t e db ym es o n i n gf e s u l t so fw 曲p a g e s ，t h u st h er e l e v a l l c ee v a l u a t i o no f w 曲p a g 粥i st h ek e yp r o c e s si n t 1 1 ep e r s o n a l i z 。di n f o n n a t i o nr e t r i e v a l s y s t e r n p r o b a b i l i s t i cm o d e lh a si t sa d v 柚t a g e si nu s e ri n t e r e s tm o d e l i n g w i t hp m b a b i l i s t i c a r g 啪e n t s ，i tc a i ld e s 谢b eu s c rr c q u i 舢e n t sm o r ee x a c t l y t h l l si t s s u i t a b l ef o rt h e r e l c v 锄c ee v a l u a t i o no f w 曲p a g e si np 廿潮a l i z 。d 血f o m l a t i o nr c 城e v a ls y s t e m n l i sd i s s e r t a t i o ni sm a 血l ya b o u tp c r s o n a l i z e di n f o 肌a t i o nr e 缸e v a lo fe n t i t y w e b p a g c s ，乜矾n gt o6 n d o u tt h ew a yt 0i r n p r o v ct h cr e l c v a n c ee v a l u a t i o np r e c i s i o n t h ea u t | 1 0 r d e s i g n sa n di m p l e n l e n t st h ep m b a b i l i s t i cm o d db a s e d r e l e v a n c e e v a l u a t i o na l g o r i t h mo ff 孤o u sp e o p l e 、) 呦p a g e s a r e rat h o r o u g hd i s c u s s i o no f i s s u e s1 i k et h om o d e lt r a i n i n gs t r a t e g i e s ，m o d e li m p r o v e m e n t s ，q u e r ye x p a n s i o na n ds o o n ，t h ep a p e rm a l ( e ss o m ec o n c l u s i o n sa b o u tp r o b a b i i is t i cm o d e la i l dm ew a yt o i m p r o v et h er e l e v a n c ee v a l u a t i o np r e c i s i o na i l dp r o v i d e sd e t a i l 。de x p 耐m e n tr e s u l t s t h ei 1 1 1 1 0 v a t i o n so fm i sd i s s e r t a t i o na r ea sf 0 1 l o w s ： ( 1 ) i tp u t sf o n a r da r i 印p r o p r i a t e 仃咖i n gs e t sc h o o s m gm e t h o d ，t h u sa c h i e v e s b e t t e rt r a i n i n gr e s u l t sa n d1 0 w e ro v e r h e a da sw d l ( 2 ) u s i n gi m p r o 、刊p r o b d b i l i s t i cf o 】f i n _ i l l a ，“a b s o r b sm o f ed e t a i l e du s e rf e e d b a c k ， t h u so p t i m i z e st h ed i s t r i b u t i o np r o b a b i l i t i e so ft e n n s i t p e r f c c f sm er e l e v a n c e c o m p u t i n gf o r m u l a ，i n t r o d u c i n gt e mf 嘲u e n c y w e b p a g e1 e n g t h ，h r m lt a g sa n d o t h e rw e b p a g ef a c t o r s ，a 1 1 df o r m st h ei d e ao ft a i l o r i n gr e l e v a n c ec o m p u t i n gf o h r l u l a b a s e do ne n t i t yc l a s s e 8 ( 3 ) b a s e do nm ef e a t u r eo fe n t i t ya t t r i b u t e s ，i tp r o p o s e sm e m o dt oe x t r a c t r e l e v a l l t t e m l so nt h eb a s i so f b o mr e l e v a l l tw 曲p a g e sa i l de n t i t y 删b u t e sf o rq u e r y e x o a j l s i o n i i a b s i m c t a si ss h o w ni nt h ee x p 嘶m e i l t s ，c o m p a r c dw i t ho t h e rr e l e v a l l c ee v a l u a t i o n m o d e l s ，o u rm o d e la c h i e v e sm u c hh i 曲e rr e l e v a l l c ee v a l u a t i o np r e c i s i o na 1 1 di tc a nb e u s e dd i r e c t l yi no t h e rc l a s s e so fe n 石t y w e b p a g e sr e t r i e v a l t h em e t h o d sa n d c o n c l u s i o n si nt h i sd i s s c r t a t i o nc a l la l s op r o v i d eg o o dr c f c r 吼c e sf o rr e s e a r c ho nt h e p e r s o n a l i z e di n f 0 h n a t i o nr e m e v a lo fe 1 1 t i t yw 曲p a g e s k e y w o r d s ： p e r s o n a l i z e di n f o h n a t i o nr e t r i e v a i ，p r o b 曲i l i s t i c m o d e l r e l e v a n c e e v a l u 撕o n ，q u e r ye x p a l l s i o n i i i 图表目录 图表目录 图2 一l 信息检索系统的体系结构 图2 - 2 信息检索处理过程 表2 1 检索系统文档分类 图3 一1 名人网页相关度评价的概率模型 图3 2 两批语料库存储方式比较 表3 1 伪反馈和用户反馈确定相关网页集实验结果 图3 3 伪反馈和用户反馈确定相关网页集实验结果比较 表3 2 用户属性信息词数 表3 3 确定不相关网页集的不同方案 表3 4 各不相关网页集选择方案的实验结果 图3 4 各不相关网页集选择方案的实验结果比较 表3 5 相关度定义的不同加权方案 图3 5 概率计算公式改进前后网页相关度评价准确率比较 图3 6 概率模型与组合向量空问模型相关度评价结果比较 图3 7 词频对相关度评价的影响 图3 8 网页长度对相关度评价的影响 图3 9 引入词频和网页长度 图3 一1 0h t m l 标记对相关度评价的影响 图3 n 同时考虑词频、网页长度和h t m l 标记 表4 1 抽取特征子串的实验结果 图4 1 抽取特征子串前后相关度评价准确率比较 图4 2 体育类名人个体 表年2 抽取高频特征项的实验结果 图4 3 抽取高频特征项前后相关度评价准确率比较 表4 3 印p 1 扩展结果 表4 - 4a p p 2 扩展结果 v 1 “ _ 培 鲍 巧 拍 拍 驷 如 如 弛 娩 叭 舵 拍 拍 图表日录 表4 - 5a p p 3 扩展结果一 表4 6h a n d w o r k 扩展结果一 表4 7c c d 2 0 0 4 扩展结果 表4 8 最佳结果及对应方案 v i i 4 6 4 7 4 7 4 8 郑重声明 本人学术论文在导师指导下独立撰写完成，没有剽窃、抄袭等 违反学术道德、学术规范的侵权行为。否则，本人愿意承担由此产 生的一切法律责任和法律后果，特此郑重声明。 学位论文作者：硬盘车军 如6 年6 月2 日 第一章，i 二 第一章引言 i n t e n l c t 的快速发展把我们带到一个信息爆炸的时代，这给我们带来及时、 丰富信息的同时，也使准确定位所需要的信息变得越来越困难。w 曲信息具有海 量、异质、分布、动态等特点，传统的信息检索技术面临严峻挑战，一种用户定 制信息的个性化检索服务正成为主流。 1 1 研究背景 w w w 作为互联网上最常用的信息服务系统，为人们提供了丰富的信息资 源。中国互联网络信息中心c n n i c “2 0 0 4 年中国互联网络信息资源数量调查报 告”显示，截至2 0 0 4 年1 2 月3 1 目，全国域名数为1 8 5 2 3 0 0 个，比2 0 0 3 年同 期增长5 6 ；网站数为6 6 8 9 0 0 个，同比增长1 2 3 ；网页总数为6 5 亿个，同 比增眨1 0 8 6 ；平均每个网站的网页数为1 2 9 7 个，同比增长1 4 7 5 。截至2 0 0 5 年5 月，g o o g l e 公布其网页索引量f 2 】达8 ，0 5 8 ，0 4 4 ，6 5 1 。大量实验和研究表 明，w w w 上整体网页的数量仍蹦指数形式增长1 3 4 i 。 搜索引擎是人们在网上搜索信息常用的工具。登录到一个搜索引擎网站，如 w w w g o 0 9 1 e c o m ，输入自己想要查找的内容，搜索引擎就会迅速返回与查询相关 网贝的网址及摘要列表。c n n i c 的统计信息表明，目前搜索引擎已绎成为继电 子邮件之后人们用得最多的网上信息服务系统】。 然而，搜索引擎服务还存在一些问题。例如，对每一条查询都返回成干上万 个网页，很多并非用户想要的，用户只好逐页察看，寻找自己需要的信息。另外， 对于那些检索目标明确、需求相对稳定的用户，每次检索都要提交重复的查询， 察看以前已经浏览过的网页，很不方便。原因在于，现在的搜索引擎般都是通 用的，要准各响应任何用户提出的任何查询，没有预先保存用户及其查询的任何 特征，因此给出的返回信息只能尽量“包罗万象”，谈不上针对性。 还有一些需求，搜索引擎不能很好地满足 ”。例如，一个人可能会灭心最近 半年来网上出现了哪些关于他( 她) 的信息，一个企业可能要关心它做了次大 规模促销活动后一个月内网上有什么反应，一个政府机构可能会关心存一项政策 第一章日茸 法规颁布后网上的舆论。这些检索需求是针对特定目的，搜集并分析网页，将网 页按照与用户关心实体( 名人、企业或机构等) 信息的相关度排序，并随时间自 动更新。 因此迫切需要一种能够根据用户的特定需求，实现信息的自动收集、分析和 推送服务的网上信息检索系统，其特点是：系统持续不断地从w w w ( 或企业网 内部) 上收集和保存网页，并把满足要求的网页以指定的方式加工、存储和分发 ( 例如按照评分、更新时间、文件大小等指标进行排序、分类、自动摘要和e m a i l 通告等) 。 在上述需求的驱动下，北京大学设立了天网知名度项目。为进一步明确信息 的预定特性，该项目限定用户提供的预定信息为一个或多个实体( 包括人、企业 或机构等) 的描述信息( 例如人名、工作单位、行业与社会职务分类，或者企业 机构名称、主要业务、产品等) ，这样系统将自动为用户指定的实体对每个网页 进行相关度评价，并把相关的网页进行汇集、排序和加工。用户可以由此定期和 定量地获得网上对其自身( 或其他任何人) 做了报道或描述的相关网页，山此l 叮 以产牛一种优质的个性化网上知名度信息服务。 犬网知名度项目以名人实体为起点，针对名人w w w 网页的特点，创建用 于表示其特征的用户属性信息表示，建立相关度评价模型，进行名人网页的过滤 和评价工作，并提供个性化检索和定制信息的主动推送服务。 1 2 相关工作 名人是人们关注的焦点，很多网站上推出了名人录、名人堂、名人访等栏e j ， 发布关于名人的各种信息。名人网页是人们搜集名人信息的主要资源，名人网页 的检索服务也成为一种需求。以名人网页为突破口，研究网页个性化检索，越来 越引起人们的火注。 下面简要介绍一个名人搜索引擎和天网知名度系统。 1 2 1f a m o u sp e o p l es e a r c h 2 0 0 4 年8 月，著名搜索引擎a s kj e e v e s 增加了名人搜索5 1 f a m o u sp e o p l e s e a r c h ”，该功能是为了满足大量搜索用户关于名人信息的搜索请求而推出。“名 2 第章0 f 高 人搜索”包括音乐家、电影明星、体育明星、政治家、历史人物及其他被关注人 群。根据用户输入的人名，将人物图片、背景传记或者新闻等不同类型的信息资 源综合成一个结果，形成对该名人的一个答案返回给用户。 例如，输入a b r a l l 锄l i n c 0 1 n ，会返回美国前总统林肯的信息，包括图片、 传记及官方网站，还提供“n a r r o w y o i 】f s e a r c h ”、“e x p a n d y o u r s e a r c h ”及“r e l a t c d n 锄e s ”等链接提示，帮助用户更准确全面地了解目标名人。a s kj v e sf 锄o u s p e o p l es e a f c h 的目标是对已收录的名人给出一个包括其传记等信息的答案，所有 查询同一个名人的用户会得到相同的答案。 1 2 2 天网知名度系统 查询输入、文档表示和相关度评价是信息检索模型的三个基本方面。在天嘲 知名度系统中，查询是用户在注册时填写的名人属性信息，系统中为了对其进行 更好的描述建立了名人实体模型，包括8 类属性信息：领域、姓名、工作单位、 职业职务、兼职、社会形象、特征词、代表作；文档是系统收集的网贝。 相关网页排序结果的优劣是系统服务质量的最根本体现，因此名人网页的相 关度评价算法是系统的关键所在。相关度，在该系统中认为是用户注册信息( 代 表用户信息需求) 与网页的匹配程度。 系统现有以下四个相关度评价模型m 】： ( 1 ) 基于信息抽取的布尔加权模型。把信息抽取中的命名实体识别和元 关系抽取技术应用于网页内容的分析，利用实体属性信息特征提出加权的布尔模 型。 ( 2 ) 组合向量空问模型( c o m b i n e d 、惋c o rs p a c em o d d ，c v s m ) 。在传统 的向量空间模型的基础上，利用实体的结构化属性信息提出了一种组合的向量空 间模型，改善了用户注册实体的存储结构，使网页相关度评价更加合理。 在评测中，组合向量空间模型优于布尔模型。然而，组合向量空间模型仍有 不足之处。针对这些不足之处，文献【7 】探讨了基于概率模型的网页相关度评价， 工作主要集中在相关度计算公式的改进上。 ( 3 ) 概率模型。在o k a p i b m 2 5 【8 】检索模型的基础上引入h t m l 标记权重系 数，改进o k 印ib m 2 5 的相关度计算公式，弥补其没有考虑h t m l 标记的不足。 第幸引吉 ( 4 ) 支持多层次实体模型的概率模型。由于不同领域名人的各类属性信息 对其相关度评价有不同贡献，在( 3 ) 中模型的基础e 引入属性信息权重系数， 利用实体属性的结构化特性，使模型从不支持结构化查询改进为支持多层次实体 模型。 1 3 本文工作 从名人网页个性化检索的需求来看，它是一个能够对网页进行相关度排序的 信息过滤系统。它的用户查询相对稳定，系统持续不断地搜集网页，把满足用户 需求的网页按相关度排序后，向用户推送。概率模型适合该系统，模型训练得到 每个特征项的分布概率，作为实体属性信息的一部分。这一额外的概率信息m 是 概率模型优于布尔模型和向量空问模型的地方，概率模型的训练也应成为模型研 究的重点。 本文以经典概率模型b l r ( b i n a r yh d 印e n d 趾c e r e t r i c v a l ) 模型例为基础，首 先讨论模型的训练问题，重点讨论训练集的选择策略。通过实验比较了用户反馈 和伪反馈方法在确定相关网页集时的性能优劣；对于不相关网贝集的确定，提出 同类实体中其他个体的网页作为不相关网页的方案，同时取得了较好的训练效果 和效率。 其次，讨论了概率模型的改进方法。b i r 模型简洁清晰地体现了概率模型的 思想，在此基础上进行模型改进，町以清楚地展示每一步改进的效果。本文从两 个方面对概率模型进行改进：( 1 ) 概率计算公式的改进。通过改进概率计算公式， 引入更细致的用户相关反馈信息，得到更准确的特征项分布概率。( 2 ) 帽关度计 算公式的改进。在b i r 基本公式的基础上，引入词频、网页长度和h t m l 标记 等网页信息，考察各因素对相关度评价的影响，提出对实体分类定制相关度计算 公式的思想。 最后讨论查询扩展。查询扩展对查询进行优化，是解决关键词不匹配问题， 改进检索性能的重要方法。文中实现了两种查询扩展方法：( 1 ) 基于相关网页的 查询扩展，从用户反馈的相关网页中按一定的规则抽取相关特征项进行扩展。( 2 ) 基于中文概念词典( c 1 1 i n e s ec o n c e p td i c t i o n 盯y ，c c d ) 的查询扩展，使用c c d 对实体属性信息进行多种策略、多个侧面的概念扩展，比较分析了各种扩展的性 4 第一章引占 能优劣。 本文以名人网页为载体，注重概率模型自身问题的探讨，模型的训练策略、 模型的改进方法、查询扩展等都是概率模型的一般性问题。本文的相关度评价模 型可以直接应用到其他类型实体网页的检索，文中的方法和结论可以为实体网页 的个性化检索研究提供参考。 1 4 论文组织 本文共分为五章，按照如下方式组织。 第一章，引言。介绍了本文的研究背景及已有的一些相关研究成果，接着介 绍了本文工作的主要内容及意义，最后是论文的组织结构。 第二章，信息检索综述。本章对信息检索的相关知识作一综述。首先介绍了 信息检索的基本概念；接着介绍了信息检索的几个基本模型，分析了各模型的基 本思想及优缺点；最后介绍了网页相关度评价的方法和评测指标。 第三章，基于概率模型的相关度评价。首先介绍了名人网页相关度评价的概 率模型的实现特点：接着介绍了名人网页语料库的准备；然后介绍了名人网页相 关度评价的测试方法：最后分别详细讨论了模型的训练和改进。 第四章，查询扩展。首先介绍了查询扩展的概念和常用扩展方法，然后洋细 讨论了基于相关网页的查询扩展和基于c c d 的查询扩展。第三章和第四章介绍 了本文的主要工作。 第五章，总结和展望。本章总结了全文，并提出了下一步的工作。 第二章信息检索综述 第二章信息检索综述 信息检索( i n f o m a t i o nr e m e v a l ，i r ) 起源于h p l u h n 在2 0 世纪5 0 年代对 文献进行的统计分析，这一时期计算机的应用和电子文本的大量出现成为数据检 索向信息检索过渡的主要推动力【jo 】。早期的信息检索主要是文本信息检索，服务 于情报机构的文献检索和情报检索。 2 0 世纪9 0 年代中期，人们把文本信息检索引入到了i n t e n l e t 上，从而大大 促进了信息检索的发展和应用。此时的检索对象从相对封闭、稳定一致、有独立 数据库集中管理的信息内容扩展到开放、动态、更新快速、分布广泛、管理松散 的w c b 内容。信息形式也从简单的文本扩充到了声音、文本、图像、音频、视 频等多媒体形式。目前相当多的研究仍然集中在文本数据的检索上，同时以文本 检索作为其他媒体内容检索的有效辅助手段，如基于周围文字的图片检索等。 图2 - 1 信息检索系统的体系结构 信息检索系统的体系结构如图2 1 所示，主要包括文本处理、查询处理、用 户界面、索引与搜索以及相关度排序等几个模块。文本处理模块对文本进行词法、 句法等分析，得到文本的特征项表示形式，为建立索引做准备，常见的索引结构 有倒排文档( i n v e n e df i l e ) 、签名文件( s i 鲫a t u r cf i l e ) 等。用户需求以文本的 笫章信息榆索综述 形式表示，首先也要经过文本处理。相关度排序模块对搜索出的文档计算相关度 并按照相关度从大到小的顺序对文档排序，它直接影响信息检索的效果，是本文 研究的主要内容。用户通过用户界面输入需求、接收查询结果以及向系统提交反 馈信息。查询处理模块根据用户反馈信息进行查询扩展等处理。 按照提供服务的不同特点，信息检索可以分为以下三类： ( 1 ) a d h o c ，这类检索的查询多变，而信息源相对固定不变，是最常见的 检索模式，如图书情报资料检索、网上搜索引擎服务等属于这类检索。 ( 2 ) f i h 鲥n g ，这类检索的查询相对固定不变，而信息源多变，一般按照用 户查询的要求将文档分为相关或不相关的两个子集，将相关文档返回给用户。例 如用户定制信息、邮件过滤等属于这类检索。 ( 3 ) r o 砸n g ，与f i l t 舐n g 类似，只是对相关文档做了排序，给用户返回按 照与查询相关程度高低排序后的文档列表。 2 1 信息检索基本模型 模型是采用数学工具，对现实世界某种事物或某种运动的抽象描述。模型抽 取现实问题的主要特征，忽略次要特征，采崩严格的数学方法进行分析并给m 模 型的解，从而现实问题也得到了解决。图2 2 给出了信息检索的处理过程“j 。 图2 2 信息检索处理过程 系统首先对用户需求和文档进行处理，转换成查询和索引文档的形式；然后 计算查询和文档之间的匹配关系( 相关度) ，并按照相关度从大到小对文档进行 第二章信息检索综述 排序；最后返回排序后的文档。 对上述过程进行抽象，信息检索模型可以用四元组m = 【d ，q ，f r ( q ，d i ) 表示， 其中： d 代表文档集的机内表示； q 代表用户需求的机内表示； f 代表文档表示、查询表示和它们之间关系的模型框架( f r 唧e ) ； r ( q d j ) 是给查询q 和文档d j 评分的函数。 信息检索模型决定于从什么样的视角去看待查询式和文档，基于什么样的理 论去看待查询式和文档的关系，以及如何计算查询式和文档之间的相关度。信息 检索的基本模型【1 2 ，】有布尔模型、向量空间模型、概率模型及基于知识的模型等。 布尔模型的理论基础是布尔代数和集合论，基于模糊集的模型和扩展的布尔模型 都是布尔模型的推广。向量空间模型的理论基础是线性代数，广义向量空删模型、 隐含语义标引( l a m e n ts e m a n t i c si n d e x ，l s i ) 和基于神经网络的模型都源自向 量空问模型。概率模型的理论基础是贝叶斯概率论，语言模型、推理网络及信念 网络都属于概率模型，其中语言模型的应用较广。基于知识的模型的理论基础是 人工智能原理，常见的是基于本体论( o n t o l o g y ) 的模型。下面简要介绍三种基 小模型。 2 1 1 布尔模型 布尔模型是最简单的信息检索模型【1 4 】，其理论基础为布尔代数和集合沦。文 档表示为关键词的集合，查询表示为关键词的布尔组合，一个文档当且仅当满足 布尔查询式时，才被检索出来。 一般地，文档d j 和查询q 的相关度定义如卜， s 吣，q ) = 3 一门“i ：竺。霸q p 镏“吼j ( 公船1 ) 其中t ，为查询的特征项，q d l l f 为用户查询的析取范式，q 。为q d n i 的任一个合 取项。当t 。在d j 中出现时，( d j ) = l ，否则( d j ) = o ；当t i 在吣中出现时昏( q 。) = l ， 否则g i ( q 。) = o 。文档的相关度为l 或o ，相关度等于1 的文档被检索出来。 布尔模犁的优点是简单、快速，查询表达式易于掌握；缺点是功能较弱，不 第一章竹息愉索综述 支持部分匹配，有些需求不易用布尔表达式表示，计算结果不能反映文档与查询 相关程度的差异，无法对文档进行排序。为了克服这些缺点，人们对布尔模型进 行推广，提出了扩展布尔模型，如p n o m 模型。 2 1 2 向量空间模型 向量空间模型于2 0 世纪6 0 年代末由g s a l t o n 等人提出，它将文档和查询表 示为向量的形式，向量每一维的元素可以是字、词或短语等特征项的某种统计值， 然后依据某种度量计算向量之间的相关度并按照计算结果对文档进行排序1 ”。 般地，假设特征项的集合t = t l ，t 2 ，t n ) ，每个文档d i 表示为文档向量d i = ( w l i w 2 i ，w n i ) ，查询表示为查询向量q = ( “1 q ，w 2 q ，w i l q ) ，向量的每一个元 素可以根据其在文档( 查询) 中出现的频率、位置等的不同进行加权，其中最常 用的计算权值的方法有t f i d f 等。 t f ( t e m lf r e q u e n c y ) 是特征项频率，基本思想是：特征项在文档中出现的 次数越多，对文档相关度计算的贡献越大。考虑到文档长度等因素，还需要对义 档频率进行规范化处理。 i d f ( i n v e r s ed o c u m e n tf r c q u e n c y ) 是逆文档频率，基本思想是：在大多数 文档中都出现的特征项区分文档的能力较弱，应给以较低的权值；反之，在少数 文档中出现的特征项区分文档的能力较强，应给以较高的权值。设m 是文档集 中文档的数目，d f ( t j ) 是文档集中含有t 的文档数目，l d f 的定义为： i d f ( t i ) = l 。8 西南或d f ( t i ) = 1 0 9 ( 1 + 斋) ( 公式2 2 ) t f - i d f 的计算方法综合考虑了t f 和i d f ，采用二者的乘积为特征项的权值： w 。= 嵩l o 鲋+ 赢，。m “k 1 1 f ( d t ，1k )一d f ( t 1 ) 这样，文档集合d = d 1 ，d 2 ，d ，。) 通过特征项一文档矩阵来表示，矩阵中的元 素值为特征项( 行) 在对应文档( 列) 中的权值。 文档向量和查询向量之间的相关度计算有多种不同的方法，常用的度量函数 有： 向量内积s 洫( d j ，q ) = d jq = wo w 自 ( 公式2 - 4 ) l ：l 9 筘乖信息榆索综述 夹角余弦 。! ! !( 公式2 5 ) 撰w ：。 向量空间模型的优点是考虑特征项权重，支持部分匹配，结果文档可以按照 与查询的相关度排序，是目前使用较为广泛的一种检索模型，代表系统为s m a r t ( s y s t 锄f o rm em a t l i p u l a t i o na l l dr e 埘e v a lo f t e x t ) 。然而，向量空l 列模型将原 本有关联的篇章、段落、句子等表示为一组字、词或短语的列表，抹煞了语言元 素之间的相关性和顺序性，丢失了一定的语法和语义信息。 2 1 3 概率模型 概率模型1 8 ，1 9 1 基于贝叶斯概率论原理，利用相关反馈的归纳学习方法，获取 匹配函数。概率模型有着良好的理论依据，它通过严格的形式化模型，估计文档 与查询的相关概率；根据文档与查询的相关概率来对返回结果进行排序。 文档和查询均表示为特征项的集合。给定查询q ，概率模型假设存在理想文 档集r ，是所有与q 相关的文档组成的集合；其他文档组成不相关文档的集合丽。 p ( r | d ，) 表示吐为相关文档的概率，p ( _ id ) 表示d j 不相关的概率。文档和查询的 相关度定义为 ( 公式2 6 ) 可见相关度与p ( r h ) 成正比，与p ( - h ) 成反比。 利用贝叶斯公式，得 。i i n ( d 洲) ：! 垫i 竺：! 些( 公式2 7 ) 幽。j 舻赢蒜 和。 其中，p ( d 。r ) 表示从r 中随机选择一个文档为d j 的概率，p ( r ) 表示从整个 文档集中任选一个文档是相关文档的概率。p ( 4 jl _ ) 和p ( _ ) 的定义与之类似。 对于给定q ，p 皿) 和p ( _ ) 的值一定，不影响各文档的相关度排序。因此， s 咻q ) 糕 1 0 笫一章信息榆索综述 。吣小9 坠坐磐竺2 。蛾 l 兀洲= l p ( t - l 两j 【丌“d j ) ；。呕i - ) j 其中，p ( t 。ir ) 表示从r 中任选一个文档出现特征项t i 的概率，p ( - 1r ) 表示从 r 中任选一个文档不出现t i 的概率。p ( t tl _ ) 和p ( - ；l _ ) 的定义与之类似。目( d j ) = l 代表t 在d j 中出现，而( d j ) = o 代表b 不在d j 中出现。 取对数，且p ( t ir ) + p ( _ ；ir ) = 1 ，忽略对所有文档都不变的因素，可得 s 埘吣喜w 。w 。( 崦芒篙+ o s 气署粤 c 公式z - - 。， 其中，w i q ( 或w 日) = 1 ( 或0 ) ，如果h 在q ( 或d j ) 中出现( 或不出现) 。因 此，公式2 1 0 可以写作 s i m 幢小默。s 芒器礼s 器】t d n o i 、。f 、， 概率可以由对文档集的统计获得 邺) = 导，p ( t 睁器 其中，n 表示整个文档集的文档总数，n t 表示其中含有特征项t 的文档数f 1 ， v 表示相关文档集r 中的文档总数，v 。是其中含有t 的文档数目。 对公式2 1 2 ，当v t 等于o 或n 。时，会出现概率等于o 的情况，这种数据稀 疏现象可能是由于文档集合不够大而造成的假象。这种情况可以使用数据平滑技 术2 1 1 加以避免。这里，我们使用加一平滑，有 p ( t 卧等，p ( t 孵等 ( 公越 在实际应用中，对于查询q ，完整的相关文档集合和不相关文档集合是不町 能获得的，只能通过有限的文档集合来近似表示。通常使用的方法是，在初始检 索时假设 p ( t i r ) = o 5 ，p ( t l _ ) = 告( 公式2 一1 4 ) 计算文档与查询的相关度，并按照相关度从大到小对文档排序。然后使用某 种相关反馈方法选定一个相关文档集合，对完整的相关文档集合进行近似模拟， 第章信息榆索练述 再计算得到优化的特征项分布概率p ( t r ) 和p ( t i 瓦) ，进而改善文档的相关度排序。 以上就是经典概率模型b i r 模型。概率模型的优点是它呵以通过相关概率 对文档排序，有着很强的理论基础。缺点在于开始时需要把文档分为相天和不相 关的两个集合，没有考虑特征项在文档中的出现频率，并且需要特征项之间的独 立性假设，但在实际应用中没有实验明确表明它是个不良的假设f 2 1 1 。 s t 印h c nr o b e n s o n 是现代概率模型的创始人之一，他开发的著名概率检索方 法o k a p l ，在t r e c ( t e x tr e 啊c v a lc o n 衙锄c e ) 评测中屡屡获得好成绩吲。另 外，美国马萨诸塞大学开发的i n o r e r y f 2 4 】文本检索系统所依据的也是概率模型。 2 2 网页相关度评价 相关度是信息检索中关于文档内容相关性的度量。相关性是指信息检索系统 针对用户的查询从文档集中检出的文档与查询之间的一种匹配关系。为了f 确地 解释检索过程，必须给相关性一个合理的度量。在信息检索中，相关性是个关 键性的概念，但一直缺乏准确的定义，在这个问题上中文信息检索目前仍然处_ j 一种直觉和感性的阶段，具有很大的主观性1 2 5 】。 相关度评价是信息检索系统的个关键环节，它直接决定了检索结果的排 序。搜索引擎观察的编辑丹尼曾表示【2 6 】：“谁的索引规模最大并不重要，匹配 程度最重要。”他还建议各搜索引擎公司联合丌发一种评测匹配程度的方法。 2 2 1 相关度评价方法 传统i r 主要基于文本内容进行相关度评价。从初始的字符串简单匹配到词 法分析、浅层分析 2 ”等，内容分析逐步深入，相关度评价准确率也不断提高。 w e b 页而检索的复杂性给传统瓜带来挑战的同时也带来了新的机遇。 首先，h t m l 标记信息有助网页内容的准确分析；其次，页面问的超链接信 息有助于网页的准确排序。很多搜索引擎引入了链接分析并取得了成功，但链接 分析还要以基于内容的分析为基础。链接分析用来找出有价值的页面，而内容分 析则保证页面是用户所需要的。 1 2 第一市俯息榆索综述 2 2 1 1 基于内容的分析 早期的信息检索系统通过简单的字符串匹配来查找文档，返回那些包含或不 含查询串的文档。这种方法会返回大量无关信息和垃圾信息，效果很差。比如， 要了解日本和服的有关信息，输入“和服”，“青岛东和服装设备”、“流动人口计 划生育管理和服务工作若干规定”等内容也被检索出来。 语言是人表达思想的工具。人们逐渐认识到，只有对文本进行分板，让机器 理解了文本的内容，才能真正找到人们想要的信息。 词是自然语言中有意义的，可以独立运用的最小的语法单位。词法分析是内 容分析的第一步，在汉语中称为分词。在词法分析的基础上，以词为索引单位， 引入词的各种统计信息，如词频、逆文档频率、文档长度等，就可以按照检索模 型的不同使用不同方法计算文档和查询的相关度。当前使用的搜索引擎基本上都 对网页文本进行了分词处理，检索性能得到了很大提高。 近年来，信息检索技术越来越多地采用更高级别的语言分析技术，以进一步 提高信息检索系统的表现，如自动词性标注、命名实体识别、二元关系识别、短 语识别等浅层分析技术。 语义分析存自然语吉+ 处理巾占有晕要地位，对于文本内容的理解有重要作 用，当前信息检索中主要使用各种语义词典进行查询扩展，如w o r d n d 、h o w n e t 、 c c d 和同义词词林等。 与普通文本不同的是，网页含有丰富的h t m l 标记，用于将刚贝的不 州部 分以不同的形式呈现给用户，包括文字的布局，字体、字号的变化等，主要追求 视觉效果。因此，标记能给我们提示其中文字的重要程度。例如，常识告诉我们， 一篇文字中，标题点明了文章的主题，而比较大的字体往往是作者比较强调的内 容，等等。利用h t m l 标记信息，有助于网页内容的准确分析。 基于文本内容的分析是网页相关度评价的关键。由于信息检索对实时性有较 高的要求，现在还不可能对网络文档进行全面完备的语法、语义乃至语用分析。 但大量研究已经显示，浅层分析技术2 9 1 在信息检索中已经表现出了梢当大的应 用潜力。随着语言分析技术的不断完善以及分布式技术、硬件水平的不断提高， 信息检索中文本内容的分析将进一步深入。 第一二章信息检素综述 2 2 1 2 链接分析 w c b 页面内容包罗万象，网页的组织性、结构性也比较差，通过错综复杂的 超链接，形成一个庞大的页面网络。这给传统r 带来极大的挑战，同时也带来 了新的机遇。利用网页间的链接关系进行链接分析，可以挖掘出很多用于网页相 关度评价的信息。 链接3 0 1 反映的是网页之间形成的“参考”、“引用”和“推荐”关系。可以合 理地假设，若一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应 该是较重要、或者较有用。因此，可以认为一个网页的“入度”( 指向它的网页 的个数) 是衡量它重要程度的一种有意义的指标。这和科技论文的情况类似，被 引用较多的往往是较好文章。同时，人们注意到，网页的“出度”( 从它出发的 链接个数) 对分析网上信息的状况也是很有意义的，因此可以考虑同时用这两个 指标来衡量网页。 g o o 西e 的p a g e r a n 出1 1 算法是链接分析最成功的算法之一，它的思想可以用 一种“随机冲浪”模型来描述： ( 1 ) 用户随机选择一个网页作为上网的起始网页； ( 2 ) 肴完这个网页后，从浚网页所含的超链内随机地选择一个页面继续进 行浏览； ( 3 ) 沿着超链前进一定数目的网页后，用户对这个主题感到厌倦，蕈新随 机选择一个网页进行浏览，如此反复。 按照以上的用户行为模型，每个网页可能被访问到的次数越多就越莺要，这 样的“可能被访问的次数”也就定义为网页的权值，即p a g e r a n k 值。p a g e r a n k 采用以下公式进行计算： ( 公式2 15 ) 其中w j 代表第j 个网页的权值；1 日取o 、l 值，代表从网页i 到网页j 是甭存在 链接；n i 代表网页i 有多少个指向其他网页的链接；d 代表“随机冲浪”中沿着 链接访问网页的平均次数。选择合适的初始数值，递归地使用上述公式，即可得 到理想的网页权值。 p a g c r a n k 【2 1 并不计算直接链接的数量，而是将从网页a 指向网页b 的链接 1 4 第一二章信息检索综述 解释为由网页a 对网页b 所投的一票。这样，p a g e r a l l k 会根据网页b 所收到的 投票数量来评估该页的重要性。 此外，p a g e r 锄k