（信号与信息处理专业论文）基于用户日志聚类的查询扩展.pdf

i l l i 、q 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：整睦茑 本人承担一切相关责任。 同期：三：! 鱼三旦奎旦 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书 本人签名； 导师签名： r 期： 日期： i 哞孑郎日 _ 基于用户日志聚类的查询扩展 摘要 随着i n t e r n e t 的发展，网络信息量不断增长，通过搜索引擎获取 所需信息已经成为用户使用网络的一个重要方面。研究表明，用户使 用查询词的平均长度为1 8 个，长度不超过3 的查询词占总查询的 9 3 1 5 ，这比c r a i gs i l b e r s t e i n 等人分析的英文查询词的平均长度2 3 5 个更短，说明在中文搜索引擎得到的用户需求信息更少，需要对用户 查询进行特定处理，才能准确返回检索结果。 查询扩展即利用计算语言学，信息处理等技术在原有查询的基础 上加入与用户输入的检索词相关联的新词，组成新的更长、更准确的 查询，修改后的查询字段会发布给搜索引擎，这样可以在一定程度上 弥补用户查询信息不足的缺陷。它可以有效充分地挖掘用户查询意图， 从而提高信息检索查全率和查准率。 本文首先提出了基于词语物理距离的简单查询扩展方法，该方法 简单易用，速度快可移植性高，有效利用文档中词语与原查询词的距 离构造权值向量，但存在使用伪相关文档和中文分词中短语未识别的 问题。 针对以上问题，本文提出基于用户日志聚类的查询扩展方法，该 算法通过对s o g o u 用户日志的预处理和聚类得到输入检索词对应的 查询扩展词。它首先对用户点击相关网页进行可信度去噪，然后对网 页进行预处理，得到标题、正文、网页关键词等，利用向量空间模型 ( v s m ) 建立权值矩阵，并通过l s i 算法进行特征降维，再用k 均 值算法进行文本聚类，得到的文本聚类中心作为类别标注词语。另外， 查询词是从用户角度进行信息描述，因此本文认为指向同一u r l 的 两个查询词是高度相关，并将原查询的反向检索词作为扩展候选词； 最后，结合类别中心、用户查询短语、文档标题、反向检索词进行查 询扩展融合，得到该查询词的查询扩展词组。本文还创新性提出了百 科术语识别的方法，该算法采用人工编辑的词典实时提取具有一定意 义的术语，极大地提高了分词的准确性。 关键词：查询扩展用户日志聚类百科术语识别网页去噪 一 苛 q u e r ye x p a n s i o nb a s e do nu s e rl o gc l u s t e r i n g a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，i th a sb e e na ni m p o r t a n tw a y f o ru s e r st or e t r i e v et h en e c e s s a r ym e s s a g eb ys e a r c he n g i n e r e s e a r c h p o i n t e do u tt h a tt h ea v e r a g el e n g t ho fc h i n e s eq u e r yt e r m si s1 8w o r d s ， w h i c hi ss h o r t e rt h a ne n g l i s hq u e r i e s ，2 3 5a s c r a i gs i l b e r s t e i ns a i d t h e r ea r e9 3 15 q u e r i e sw h i c ha r en ol o n gt h a n3w i t h i nt h et o t a lq u e r y l o g s i ts h o w st h a tc h i n e s es e a r c he n g i n e sg e tl e s si n f o r m a t i o nf r o mu s e r s ， i ti s n e c e s s a r yt op r o c e s st h eq u e r yt e r mt ou n d e r s t a n dt h eu s e r s i n t e n t i o n s q u e r ye x p a n s i o nc a ns o l v et h ea b o v ep r o b l e mb ya d d i n gt h e a s s o c i a t ei n f o r m a t i o nt ot h e o r i g i n a lq u e r y ，i tc a nf o r mal o n g e ra n dm o r e a c c u r a t ei n p u t i nt h i ss t u d y ，w es h o was i m p l ea n df a s t q u e r ye x p a n s i o nm e t h o d b a s e do nt h ew o r dp h y s i c a ld i s t a n c e ，a n dt h ew e i g h tv e c t o ri sc a l c u l a t e d b yt h eo r d e ro ft h et e r m sa n do r i g i n a lq u e r y t w op o i n t sa f f e c tt h er e s u l t s ： p g e u d of e e d b a c ka n da u t o m a t i ct e r mr e c o g n i t i o ni nt h ec h i n e s ew o r d s e g m e n t a t i o n t os o l v et h ea b o v ep r o b l e m s ，w ep r e s e n tan o v e la l g o r i t h mq u e r y e x p a n s i o nb yc l u s t e r i n gt h er e a lu s e rl o g s b e c a u s en o ta l lo ft h ec l i c k e d p a g e sa r es u i t i b l ef o rq u e r ye x p a n s i o n ，w ed e n o i s e dt h ec l i c k e dr e s u l t s b yr e l i a b i l i t yt oe n h a n c et h ep e r f o r m a n c e a f t e rh t m ll a b e l sr e m o v i n g ， t h ep a g eb o d yc o n t e n t sa r ec l u s t e r e da n dt h ec l u s t e rc e n t e r sc o v e rv a r i o u s a s p e c t so ft h eo r i g i n a lq u e r y t h et e r m su s e di nl o gq u e r i e sc a np r o v i d ea b e t t e rc h o i c eo ff e a t u r e s ，f r o mt h eu s e r sp o i n to fv i e w ，f o rs u m m a r i z i n g t h ew e bp a g e st h a tw e r ec l i c k e df r o mt h e s e q u e r i e s t h e r e f o r e ，t h e a s s o c i a t e dq u e r i e s ，r e v e r s eq u e r i e s ，w e b p a g et i t l ea n dk e y w o r dp h r a s e s a r ec o m b i n e dw i t ht h ec l u s t e rc e n t e r st oa t t a i nh i g h q u a l i t ye x p a n s i o n t e r m sf o rn e w q u e r i e s k e y w o r d s ：q u e r ye x p a n s i o n ，l o gm i n i n g ，l s ic l u s t e r i n g ，b a i k e t e r m i n o l o g ye x t r a c t i o n ，w e b p a g ed e - n o i s i n g t 0 ” ， 蚤 北京邮电大学硕 ：研究生学位论文 基于用户 j 志聚类的查询扩展 目录 第一章绪论l 1 1 课题研究背景和意义1 1 2 国内外研究现状及发展趋势2 1 2 1 全局分析方法3 1 2 2 查询扩展的局部方法3 1 2 3 查询扩展发展趋势。4 1 3 本文的工作重点5 1 4 论文的结构框架6 第二章信息检索及查询扩展关键技术背景7 2 1 搜索引擎基本框架原理7 2 1 1 网页搜集8 2 1 2 预处理一9 2 1 3 查询服务1 l 2 2 中文分词及命名实体识别一1 4 2 2 1 中文自动分词技术1 4 2 2 2 术语自动识别技术1 4 2 3 网页去噪1 5 2 4 文本聚类。1 7 第三章基于词语物理距离的查询扩展2 0 3 1 算法理论基础2 0 3 2 算法测试一2 l 3 3 存在的问题及解决方案2 3 第四章基于用户日志聚类的查询扩展。2 4 4 1 系统框架设计2 4 4 2 系统关键技术2 5 4 2 1 百度百科术语识别2 5 4 2 2 用户日志匹配2 7 4 2 3 网页预处理2 8 反向检索词2 9 的k 均值文本聚类3 0 融合3 3 京邮电大学硕t ：研究生学位论文 基于用户口志聚类的查询扩展 4 3 系统实现3 4 4 4 两种查询扩展算法比较3 6 第五章个性化检索模型及查询扩展3 8 5 1 什么是个性化检索3 8 5 2 个性化检索研究现状3 9 5 2 1 知名成型系统3 9 5 2 2 个性化检索分类3 9 5 3 用户个性化模式的表达方式4 0 5 3 1 向量表示法4 0 5 3 2 概念层次表示法4 0 5 4 个性化检索的相关技术一4 l 5 5 个性化检索模块4 2 5 5 1 用户模型的建立4 2 5 5 2 用户模型的更新4 3 5 5 3 用户模型的应用4 3 5 6 个性化查询扩展4 4 第人章总结与展望4 6 6 1 论文主要工作总结4 6 6 2 下一步工作展望4 7 参考文献4 9 致谢5l 发表论文目录5 2 n 北京邮电人学硕- j ：研究生学位论文 基于用户u 志聚类的查询扩展 1 1 课题研究背景和意义 第一章绪论帚一早珀下匕 伴随着中国网民人数增加与互联网应用的不断深入，中国互联网行业发展迅 速，中国互联网络信息中心统计，截至2 0 0 9 年6 月底，中国网民已经达到3 3 8 亿人，较2 0 0 7 年增长4 1 9 ，互联网普及率达到2 2 6 ，略高于全球平均水平 ( 2 1 9 ) 。这是继2 0 0 8 年6 月中国网民规模超过美国，一举成为全球第一之后， 中国的互联网普及再次实现飞跃，赶上并超过了全球平均水平。与此同时，调查 显示，过去半年来，9 0 6 的中国网民使用过宽带接入互联网，也就是说，2 7 亿中国网民使用了宽带访问互联网，较2 0 0 7 年增长一个多亿。c n n i c 报告显示： 网络求职、博客和网络购物位列增长最快的应用前三甲。这说明互联网商业模式 的变化，尤其是电子商务的个人网站和博客营销呈现明显增长趋势。如：个人网 站数量的增加，网站交易行为更比往年有成倍增长。又如：博客自诞生以来，一 直保持快速的增长势头，截至2 0 0 8 年底，中国博客作者已经达到1 6 2 0 0 万人。 它是博客营销的基础，也带给企业良好的发展契机。 中国互联网络信息中心( c n n i c ) 于2 0 0 9 年9 月2 1 日下午发布( 2 0 0 9 年中国 搜索引擎用户行为研究报告，报告显示，中国搜索引擎用户已达2 3 5 亿人， 半年增长率达1 5 6 。搜索引擎在全国网民中的使用率为6 9 4 ，比2 0 0 8 年底增 长了1 4 个百分点，2 0 0 7 年以来搜索引擎使用率首现增长趋势。成为网民重要 的网络应用之一。随着s n s 、3 g 等网络新技术的快速发展使搜索引擎的发展向更 加进一步专业化、社区化、移动化的方向发展，出现了更多的热点。中文搜索、 图片搜索、地图搜索更加专业、精准，同时在社区搜索、移动搜索等领域也展现 良好地发展前景，成为相关从业者关注的焦点。另一方面，搜索引擎公信力遭遇 了前所未有的质疑和挑战，如何树立搜索引擎公信力，打造可信的信息渠道，成 为社会各方关注的焦点。 从以上数据中可以看出，随着i n t e m e t 的发展，网络信息量不断增长，通过 搜索引擎获取所需信息已经成为用户使用网络的一个重要方面。余慧佳【l 】等人对 2 0 0 6 年2 月的搜狗搜索引擎用户查询日志的研究表明，用户所使用的查询词的 平均长度为1 8 个，长度不超过3 个词的查询词占总查询的9 3 1 5 。这比c r a i g s i l b e r s t e i n 等人分析的英文查询词的平均长度2 3 5 个更短，说明在中文搜索引擎 得到的用户需求信息更少，需要对用户的查询词进行一定处理，才能准确返回检 交的查询请求之间、查询请求到系统对查询请求的理解之间均存在一定的偏差。 查询扩展是提高信息检索性能的有效技术手段之一，能极大地改善系统性能，减 少这些偏差对系统造成的负面影响，也是信息检索领域一直在研究的课题。查询 扩展技术通过一定的策略向初始查询中增加一些相关词语形成新的查询，以提供 更多有利于判断文档相关性的信息，使用新的查询再次检索文档集，从而使更多 的相关文档被检索出来。查询扩展是解决信息检索中“词不匹配”问题的重要方 法，解决“查询漂移 问题，提高信息检索的性能。 2 北京邮电大学硕。t ：r c 究生学位论文基于用户【l 志聚类的查询扩展 1 2 1 全局分析方法 查洵扩展的全局方法【5 j 基本思想是：对全部文档中的词或词组进行相关分析， 计算每对词或词组间的关联程度。当一个新的查询到来时，则根据预先计算的词 间相关关系，将与查询用词关联程度最高的词及词组加入原查询以生成新的查询。 典型的全局分析的方法通常是将文档中出现的词按共同发生的频率先行聚类，其 后，根据词的不同集合对查询进行扩展。常见的全局分析方法包括l s i ( 1 a t e n t s e m a n t i ci n d e x i n g ) 系列模型、相似性词典等。全局分析的优点是可以最大限度地 探求词间关系，并在词典建立之后以较高的效率进行查询扩展。但是，当文档集 合非常大时，建立全局词关系词典的时空复杂度是无法忍受的，并且在文档集合 改变后的更新代价巨大。文档中所有词集合w ( l ，6 02 ，i ) 之间的全相似度 矩阵s i m ( w ) 如下： s i m ( w ) = ： 跳l 研7 ，1 1 2 溉f s m z ls m 2 2 瓯f s m i ls m f 2 当文档集合非常大时，建立全局的词关系词典在时间和空间上往往是不可行 的，并且在文档集合改变后的更新代价巨大。 1 2 2 查询扩展的局部方法 局部上下文分析方法是由x u 和c r o f t t 6 ，7 】提出来的。它在整体上是一种局部 分析方法，但利用全局分析的词共同出现频率的思想避免了向原查询加入不相关 的词。局部上下文分析的方法被用于i n q u e r y 系统中，并在t r e c 标准测试集 上取得了良好的效果。实验表明，该方法的检索结果明显优于传统的全局分析和 局部分析。 局部上下文分析的工作流程是： ( 1 ) 首先使用检索系统初始检索得到的前n 篇文章作为与原查询最相关的n 篇文章。 ( 2 ) 从该n 篇文章中选取与原查询最相关的词与词组。相关度计算公式为： s i m ( q ，c ) = 兀 8 + l o g ( a f ( c , ) + 1 ) i d f 。l o g ( 咒) 】颂 式( 1 - 2 ) k q 其中， 统中，所构造的检索模型相当于一种简单的语义模型，并且可以根据阈值来控制 查询扩展的程度。但是该试验中的两个条件：( 1 ) 查询结构语句为修饰词加中心 词。通过对用户的查询日志的调查发现，大多数的查询记录都不属于这种情况， 实验中采用的长语句的查询也和短查询的现状不符。( 2 ) 所有的查询短语均可被 扩展，随着网络用语的发展，出现很多未登陆词，因此，这点也是不能保证的， 这种方法在t r e c 上的测试结果比无扩展的效率提高了约4 0 。 相关反馈是最常见的查询重构方法之一。在相关反馈循环中，系统向用户返 回一组文档，用户在检查完这些文档之后，标出那些相关的文档。在实际操作中， 4 北京邮电人学硕上研究生学位论文基于用户同志聚类的查询扩展 用户往往只需要检查排在前1 0 ( 或前2 0 ) 位的文档。该方法的主要思想是从用户 认为相关的文档中选择重要的词语或表达式，然后在新的查询表达式中不断提高 这些词语的重要性，希望新的查询能够将相关文档与不相关文档区分开来。一种 基于潜在语义分析的查询扩展算法【lo 】对正反馈和负反馈页面分别进行词频统计， 并聚类，找到每篇文章的聚类中心向量，对其协方差奇异值分解后选择奇异值较 大的前k 个关键词做查询扩展候选，通过区分同义词，关联词和区分词达到查询 扩展的目的。 个性化查询扩展j 提出了基于用户个性化的查询扩展，将用户模型存放在客 户端，并针对不同的用户进行相关的查询扩展。而基于用户兴趣的局部上下文分 析方法则是用y a h o o 分类网页训练出的分类器对返回结果进行分类，对用户感兴 趣类别的文档中利用局部上下文的方法查询扩展。 文献【5 】选择用户点击文档中对于查询词条件概率最大的词语作为查询扩 展词，这种算法选择出来的扩展词很难涵盖检索词的各个方面。为了解决这个问 题，我们根据相似度对用户点击文档进行基于隐含语义索引聚类，聚类中心分别 反映了查询词的各方面信息。最后，用聚类中心结合用户日志中的相关检索词短 语得到查询扩展词。 1 3 本文的工作重点 本文首先提出了一种基于词语物理距的查询扩展算法，实验表明，这种方案 运行速度快，效果良好，能够有效利用文档中词语与原查询词的位置距离信息构 造权值向量，但是该算法存在使用伪相关文档和中文分词中短语未识别的问题。 为了解决上述算法存在的问题，本文提出一种新的基于用户日志聚类的查询 扩展算法，该算法通过对s o g o u 用户日志的预处理和聚类得到输入检索词对应的 查询扩展词。它首先对用户点击相关网页进行可信度去噪，然后对网页进行预处 理，得到标题、正文、网页关键词等，利用向量空间模型( v s m ) 建立权值矩 阵，并通过l s i 算法进行特征降维，最后用k 均值算法进行文本聚类，并将文 本聚类中心作为类别标注词语。另外，查询词是从用户角度进行信息描述，因此 本文认为指向同一u r l 的两个查询词是高度相关，并将原查询的反向检索词作 为扩展候选词；最后，结合类别标注词语、用户查询短语、文档标题、反向检索 词进行查询扩展融合，得到该查询词的查询扩展词组。此外，本文还创新性提出 了百科术语识别的方法，该算法采用人工编辑的词典实时提取具有一定意义的术 语，极大地提高了分词的准确性。 基于用户日志聚类的查询扩展算法主要包括下面的内容：用户日志的获取， 5 北京邮电大学硕十研究生学位论文基二卜用户u 志聚类的查询扩展 所需的用户r 志包括：用户i d ，用户查询词，该查询词点击的网页。用户点击 网页的预处理工作：包括根据u r l 下载相关页面的h t m l 代码，对该代码进行 去标签后，得到该页面的标题、摘要、正文等。对页面进行可信度去噪，得到符 合条件的页面。对可信度高的页面进行文本聚类，得到聚类中心，并选择权值较 高的术语及短语作为查询扩展词语。 最后，本文还对个性化检索领域进行了研究，提出了一种个性化查询扩展模 型。 1 4 论文的结构框架 第一章：介绍了本文的研究背景、研究目的、国内外相关研究、本文工作重 点以及论文的结构框架。 第二章：介绍了信息检索中的基础知识，包括信息检索概念、搜索引擎的基 本框架等，并综述了查询扩展用到的关键技术：中文分词、命名实体识别、网页 去噪、文本聚类等相关背景知识。 第三章：本章提出了一种基于词语物理距离的查询扩展算法，分析搜索引擎 返回结果中排名较前的网页摘要，提取其中和查询词距离最小的词项作为查询扩 展词。该算法采用伪相关文档，过于依赖初次检索结果；另外中文分词过程中未 进行短语识别，也影响了算法的性能。 第四章：针对上章节中查询扩展中采用伪相关文档，导致扩展词偏离查询意 图的问题，本文提出了基于用户同志聚类的查询扩展方法。通过对真实的用户点 击网页进行分析，并通过网页去噪过程，得到最原始的网页文档正文：基于百度 百科的术语识别方法，能够识别出目前网络上出现的大量的未登录词和专有名词， 有力地提高了中文分词的准确度；最后通过l s i 潜在语义索引技术对文档特征矩 阵降维后进行聚类分析，得到聚类中心作为查询扩展词。 第五章：详细介绍了个性化检索的背景和相关技术，提出将查询扩展与个性 化检索结合起来的思想，提高查询扩展的性能。 第六章：对全文工作进行总结，讲述了本文的工作重点和存在的不足，并对 未来研究方向进行了展望。 6 北京邮电大学硕士研究生学位论文基于用户日志聚类的盘询扩展 。 第二章信息检索及查询扩展关键技术背景 2 1 搜索引擎基本框架原理 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是指信息按一定的方式组织起来，并根据 信息用户的需要找出有关的信息的过程和技术。狭义的信息检索就是信息检索过 程的后半部分，即从信息集合中找出所需要的信息的过程。 所谓“搜索引擎”，即一个计算机应用软件系统，或者说一个网络应用软件 系统，能够接受用户通过浏览器提交的查询词或短语，记作q ，例如“非典 ，“伊 拉克”，“床前明月光 等。在一个可以接受的时间内返回一个和该用户查询匹配 的网页信息列表( 标题，网址链接，摘要) ，记作l 。 其中，响应时间对于在w 曲上面向广大用户日工服务的软件来说，通常在 “秒”这个量级，系统应该在额定吞吐率的情况下保证秒级响应时间。而“网页 信息列表”蕴含一种序r a n k ，在绝大多数情况下，返回网页数量超过1 万个条目， 用户没有耐心也没有时间看完所有的返回结果，因此，需要对返回网页按照相关 性排序。 搜索引擎的工作模块大致可以分为：网页搜集，预处理和查询服务。如下图 所示： 7 ( 1 ) 搜索器在互联网上搜集成千上亿的网站，通过控制器进行预处理，存 入原始数据库。 ( 2 ) 索引器对数据库中的网页建立倒排索引，并把结果存入索引数据库中。 ( 3 ) 当用户在用户接口中输入检索词时，检索器在索引库中找出和用户查 询最相关的网页并按照相关性从高到低输出。 7 扩展 2 1 1 网页搜集 网页搜集可以包括两种方式，一种是定期搜集，一种是增量搜集。 定期搜集，每次搜集替换上一次的内容，称之为“批量搜集 。由于每次都 是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。而由 于这样做开销较大，通常两次搜集的间隔时间也不会很短( 例如早期天网的版本 大约每3 个月来一次，g o o g l c 在一段时间曾是每隔2 8 天来一次) 。这样做的好 处是系统实现比较简单，主要缺点是：“时新性 ( f r e s h n e s s ) 不高，还有重复搜 集所带来的额外带宽的消耗。 增量搜集，开始时搜集一批，往后只是( 1 ) 搜集新出现的网页，( 2 ) 搜集 那些在上次搜集后有过改变的网页，( 3 ) 发现自从上次搜集后已经不再存在了的 网页，并从库中删除。由于除新闻网站外，许多网页的内容变化并不是很经常的 ( 有研究指出5 0 网页的平均生命周期大约为5 0 天) 。这样的系统表现出来的信 息时新性就会比较高，主要缺点是系统实现比较复杂。 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见 的一种是所谓“爬取 ：将w e b 上的网页集合看成是一个有向图，搜集过程从给 北京邮电大学硕上研究生学位论文基于用户只志聚类的查询扩展 定起始u r l 集合s ( 或者说“种子 ) 开始，沿着网页中的链接，按照先深、先 宽、或者某种别的策略遍历，不停的从s 中移除u r l ，下载相应的网页，解析 出网页中的超链接u r l ，看是否已经被访问过，将未访问过的那些u r l 加入集 合s 。整个过程可以形象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w 曲) 上爬行( c r a w l ) 。 2 1 2 预处理 得到海量的原始网页集合，距离面向网络用户的检索服务之间还有相当的距 离。，一个合适的数据结构是查询子系统工作的核心和关键。这里只是指出：现 行最有效的数据结构是“倒排文件”( i n v e r t e df i l e ) ；倒排文件是用文档中所含关 键词作为索引，文档作为索引目标的一种结构( 类似于普通书籍中，索引是关键 词，书的页面是索引目标) 。预处理主要包括四个方面，关键词的提取，“镜像网 页( 网页的内容完全相同，未加任何修改) 或“转载网页”( n e a r - r e p l i c a s ，主 题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网 页 ) 的消除，链接分析和网页重要程度的计算。 关键词提取 一篇网页的源文件，除了从浏览器中能够正常看到的文字内容外，还有大量 的h t m l 标记。根据天网统计，网页文档源文件的大小( 字节量) 通常大约是 其中内容大小的4 倍。由于h t m l 文档内容多种多样，不仅文字不讲究规范、 完整，而且还可能包含许多和主要内容无关的信息( 例如广告，导航条，版权说 明等) 。为了支持后面的查询服务，需要从网页源文件中提取出能够代表它的内 容的一些特征，其中所含的关键词即为这种特征最好的代表。因此预处理的一个 任务，就是要提取出网页源文件的内容部分所含的关键词。对于中文来说，就 是要根据中文分词的词典，通过切分得到网页中包含在该词典内的所有的中文词 语。在那之后，一篇网页主要就由一组词来近似代表了，p a g e = w ，w ，w ) 。 一般来讲，我们可能得到很多词，同一个词可能在一篇网页中多次出现。从效果 和效率考虑，还应该要去掉诸如“的 ，“在”等没有内容指示意义的词，称为“停 用词”( s t o pw o r d ) 。这样，对一篇网页来说，有效的词语数量大约在2 0 0 个左右。 -网页去重 由于网络信息发展迅速，网页的复制以及转载和修改再发表现象非常常见， 因此我们看到w e b 上的信息存在大量的重复现象。天网在2 0 0 3 年的一次大规模 统计分析表明，网页的重复率平均大约为4 。也就是说，当你在网上看到一篇网 页的时候，平均还有另外3 个不同的u r l 也给出相同或者基本相似的内容。这 种现象对于广大的网民来说是有正面意义的，因为有了更多的信息访问机会。但 9 北京邮电大学硕十研究生学位论文基于用户f j 志聚类的查询扩展 对于搜索引擎来说，则主要是负面的；它不仅在搜集网页时要消耗机器时间和网 络带宽资源，而且如果在查询结果中出现，无意义地消耗了计算机显示屏资源， 也会浪费用户的浏览时间。因此，消除内容重复或主题内容重复的网页是预处理 阶段的一个重要任务。 链接分析 网页h t m l 信息和文本的一个很大不同就在于，前者包含很多h t m l 标签， 从前面的分析得出，这些标签在预处理过程中产生噪声，浪费存贮容量，影响检 索结果。通常，应该选择能够代表文本信息的权重较大的词语来表示，即对文档 进行词频统计( t e r mf r e q u e n c yt f ) 和词在文档集合中出现的文档频率( d o c u m e n t f r e q u e n c yi d f ) ，选择t f * i d f 较大的词语来表示。有了h t m l 标记后，情况还 可能进一步改善，在同一篇文档中， 和 之间的信息很可能就比在 和 之间的信息更重要。另外，h t m l 文档中所含的指向其他文档的链接信 息是人们近几年来特别关注的对象，认为它们不仅给出了网页之间的关系，还对 判断网页的内容有很重要的作用。 网页重要程度计算 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的 顺序是很重要的一个问题。由于面对各种各样的用户，加之查询的自然语言风格， 对相同的查询词返回的结果列表不能保证让所有提交该查询词的用户满意( 或者 都达到最高的满意度) ，所以搜索引擎实际上追求的是一种统计意义上的满意。 人们认为g o o g l e 目前比天网好，是因为在多数情况下前者返回的内容要更符合 用户的需要，并不是所有情况下都如此。在预处理阶段可能形成的所谓“重要性 因素。顾名思义，既然是在预处理阶段形成的，就是和用户查询无关的，并不能 表现出一篇网页比另外一篇网页重要。人们参照科技文献重要性的评估方式，核 心想法就是“被引用多的就是重要的 ，“引用”这个概念恰好可以通过h t m l 超链在网页之间体现得非常好，作为g o o g l e 创立核心技术的p a g er a n k 就是这 种思路的成功体现。此外，人们还注意到网页和文献的不同特点，即一些网页主 要是大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些网页则 被大量的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这种关系 使得人们可以在网页上建立另外一种重要性指标。这些指标有的可以在预处理阶 段计算，有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果排 序的部分参数。 1 0 北京邮电人学硕士研究生学位论文基于用户n 志聚类的查询扩展 2 1 3 查询服务 从前面的网页所搜集和预处理的过程中得知，文档的表示形式为： 1 ) 原始网页文档； 2 ) u r l 和标题； 3 ) 编号； 4 ) 所含的重要关键词的集合；( 以及它们在文档中出现的位置信息) 5 ) 其他一些指标；( 例如重要程度，分类代码等) 而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得 一旦得到一个关键词输入，系统能迅速给出相关文档编号的集合输出。查询服务 主要包括下面几个内容： 查询方式和匹配 网页1 网页2 网页k 网页m 特征项1 特征项2 特征项1 特征项2 特征项k 特征项n 网页l 网页2 网页l 网页2 网页3 图2 2 由正向俚引j l i 立量向俚引 搜索引擎用户对实时性要求很高，因此大量计算工作需要在简历索引时完成， 建立索引包括正向索引和倒排索引，如图2 2 所示。正向索引就是将网页表示为 特征项( 分词) 序列，构成文档空间。倒排索引，即将每个特征向量表示为一组 相关文档的集合。数据规模增大后，可以采用分组索引，然后再归并索引的策略。 该策略是，建立索引的模块根据当时运行系统所在的计算机的内存大小，将索引 分为k 组，使得每组运算所需内存都小于系统能够提供的最大使用内存的大小。 按照倒排索引的生成算法，生成k 组倒排索引。然后将这k 组索引归并，即将相 同索引词对应的数据合并到一起，就得到了以索引词为主键的最终的倒排文件索 引，即反向索引。 一查询结果排名 目前的搜索引擎对于查询结果列表中的排名采用的是预处理网页的重要性 指标和查询过程中得到的网页的权重相结合的方式，前者在预处理中已提到过， 采用的“被引用多的就是重要的”的基本思想。下面主要讨论查询过程中如何确 里里行 征一征一征黼一黼一牦 北京邮电大学硕? l 二研究生学位论文摹于用户r 志聚类的查询扩展 定结果页面的重要性问题。目前大多数的信息检索系统使用布尔模型、向量空间 模型、概率模型、神经网络模型、聚类模型、基于规则的模型、模糊模型和语义 模型等。其中向量模型是现代信息检索，特别是搜索引擎中普遍使用的一种检索 模型，具体内容如下： 给定某个文档集合d ，大小为m ；设两篇文档d l ，d 2 d ，一个查询q 。 用什么样的标准来讲“d 1 与d 2 相比，前者和q 更相关 ? 这方面最经典、最有 影响的工作是g s a l t o n ，a w o n g 1 2 1 等在3 0 多年前提出的“向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) 。该模型的基础是如下假设：文档d 和查询q 的相 关性可以由它们包含的共有词汇情况来刻画，用t f 和i d f 相结合的方法，t f 是词频统计的结果，但是如果该词在所有的文档中都出现过，那么它对于文档只 具有很低的区分度，i d f 就是统计该词在多少篇文章中出现过，作为词语的一个 重要性指标。 这样，文档d 和查询q 就都被简化成词汇的集合( 多重集) 。不失一般性， 令 = ( t 1 ，t 2 t n ) 式( 2 - 1 ) 为一个词典，t 为词项，n 为它的规模，则： d = ( t ? 1 ，t 罗2 一t ：n ) 式( 2 - 2 ) q = ( t 2 ，t 2 n 2 t n n n ) ， 式( 2 - 3 ) 其中，m ：，n ；，i = 1 ，2 ，n 表示相应词项出现的次数，即词频t f ；如果次 数为零，则表示该词项在文档或查询中没有出现。在实际应用中，人们通常去掉 而t 而直接用m 和n 表示d 和q 。 上述表示中，需要对词频进行归一化处理，使t f 值落在 0 ，1 】内。 d = w l ，w r 2 w r n ) 式( 2 - 4 ) w i = 而m 丽l 式( 2 - 5 ) 查询q 也有同样的表达形式。这里，w 也称为词频，称这种方式为用词频来 表示词项在文档或查询中的权重。 若一个词项t 在许多文档中都有出现( 例如“我们”，“大家”等) ，尽管它 可能在文档内部出现的频度也很高，它对于不同文档的区分能力就不会很强，因 此它的权重应该相对较小。将这种观念刻画出来，用k ；表示词项t ：在文档集合d 中涉及的文档个数，m 是集合d 的大小，则文档频率d f 为 d f ( t i ) = l m t i 式( 2 6 ) 1 2 北京邮电人学硕士研究生学位论文基于用户口志聚类的查询扩展 我们需要的是和d f 成反比的一个量，称之为倒置文档频率i d f ，常用的一 种定义为i d f ( t i ) = l o g ( 。这样结合词频，就有了经典的t f * i d f 词项权重的设 计。 w i = t f 宰i d f = 意札g 尊 式( 2 7 ) 给定了权重的定量设计，求文档和查询的相关性就变成了求d 和q 向量的某 种距离，最常用的是余弦距离： 咖似印卜翻2 茬雨e t = i ( i 丽) l j x ( 1 ) i o q 加剐 向量空间模型v s m 源于传统信息检索领域，针对的是普通文本，从根本上 看是将文本近似成一个词项集合，完全忽略了语义和语用信息，但几十年来在大 量真实语料评估的驱动下，经过不断完善和无数实验证明，该算法能够为信息检 索提供良好的效果，因此本文在构造权值矩阵方面，也采用了该模型中的权值计 算方法，见4 2 5 。 文档摘要 搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素： 标题，网址和摘要。搜索引擎生成摘要可以归纳为两种方式，一是静态方式，即 独立于查询，按照某种规则，事先在预处理阶段从网页内容提取出一些文字，例 如截取网页正文开头的3 5 句话，或者将每一个段落的第一个句子拼起来。这种 方式对查询子系统来说是最轻松的，不需要做另外的处理工作。但它的一个最大 的缺点是摘要和查询无关一当用户输入某个查询，用户一般是希望摘要中能够突 出显示和查询直接对应的文字，希望摘要中出现和他关心的文字相关的句子。因 此，需要有一种“动态摘要 方式，即在响应查询的时候，根据查询词在文档中 的位置，提取出周围的文字来，在显示时将查询词标亮。这是目前大多数搜索引 擎采用的方式。为了保证查询的效率，需要在预处理阶段分词的时候记住每个关 键词在文档中出现的位雹，以便以后高亮显示。 本文在基于词语物理距离的查询扩展算法中，分析的语料为百度检索结果中 提供的文档摘要，该摘要采用的是动态摘要的方式，提取出查询词的周围文字， 表明该文档的主要内容。由于摘要篇幅较小，且能突出表示与查询相关的部分， 因此，采用文本摘要可以大大提高算法运行的速度，减低时间复杂度。 1 3 术语【1 4 】的定义：据中华人民共和国国家标准g b f r l 5 2 3 7 1 2 0 0 0 术语工作 词汇的定义，术语是在特定专业领域中一般概念的词语指称。各门学科中的专 门用语。术语可以是词，也可以是词组，用来正确标记生产技术、科学、艺术、 社会生活等各个专门领域中的事物、现象、特性、关系和过程。 一术语自动抽取方法 1 4 北京邮电大学硕r l ：研究生学位论文基于用户l 1 忐聚类的查询扩展 就术语提取来说，目前国外已经推出了一些相关的成熟产品，这其中以著名 的文本信息处理公司a u t o n o m y 的系列产品为代表，这些产品在经过训练后能够 自动从文本中提取概念和术语。目前该公司已拥有一大批国际知名企业客户。而 关于中文文本信息中的术语识别和提取的研究则更多的体现于对人名、地名和组 织名等命名实体的识别和提取。 术语抽取【陌j 的方法主要分为3 种： ( 1 ) 基则的方法，主要是利用一些语言学的知识，如j u s t c s o n & k a t z 利用术 语的前缀信息，只接受前缀是名词的串为术语；规则方法的优点是识别准确率高， 主要缺点在于规则由人为编写，费时费力，规则覆盖面有限； ( 2 ) 基于统计的方法，主要