（计算机软件与理论专业论文）web信息智能检索研究.pdf

w e b 信息智能检索研究 摘要 随着w e b 的不断增长，人们对w e b 信息检索系统提出了更高的要求。w e b 信息检索也逐渐成了互联网研究中的一个热点。近年来，又有一些学者提出了 面向特定主题的w e b 信息检索方法，以满足些专业用户的信息需求，同时也 克服了综合搜索引擎的一些不足。 本文对面向特定主题的w e b 信息检索所涉及到的关键技术进行了深入的 讨论。对面向特定主题的w e b 信息检索系统中的网页主题识别方法( 网页分类 方法) 作了深入的研究。目前对网页的分类主要是采用基于网页内容的分类方 法，这种分类方法没有充分利用w e b 的链接信息，因而分类效果不是很好。本 文给出了一个结合网页链接结构的网页分类方法。同时，在对网页分类技术进 行研究的基础上，本文构造了一个基于网页链接结构的面向特定主题的w e b 信 息搜索系统。 最后本文使用v c + + 6 0 开发环境实现了一个实验系统平台，并在这一平台 上进行了相关的实验。 关键词：互联网，万维网，信息检索系统，搜索引擎，分类算法 t h er e s e a r c ho n i n t e l l i g e n tw e b i n f o r m a t i o nr e t r i e v a l a b s t r a c t w i t ht h ei n c r e a s i n go f 彤w e bi n f o r m a t i o nr e t r i e v a l s y s t e m sw i t hh i g h e r p e r f o r m a n c ea r er e q u i r e d s u b s e q u e n t l y ，t h er e s e a r c ho nw e bi n f o r m a t i o nr e t r i e v a l h a sb e i n gaf o c u s r e c e n t l y ，f o c u sc r a w l i n gs y s t e mw a s p r e s e n t e dt os a t i s f yp e o p l e w h on e e dp r o f e s s i o n a lk n o w l e d g ef r o mw ww i nt h i sd i s s e r t a t i o na l lk e y a s p e c t so f af o c u sc r a w l i n gs y s t e ma r ei n t r o d u c e d a n dt h e nt h ec l a s s i f i c a t i o np r o b l e mi nf o c u sc r a w l i n gs y s t e mi s d e e p l yd i s c u s s e d n o w , m o s tc l a s s i f i c a t i o nm e t h o d sf o rw e b p a g eo n l yu s et h ec o n t e n t so fw e bp a g e t h e s em e t h o d si g n o r el i n k sb e t w e e n p a g e sc o m p l e t e l y i nf a c t ，l i n k sb e t w e e nw e b p a g e ss o m e t i m e sr e f l e c tt o p i c so ft h e s el i n k e dp a g e s s ot h i sd i s s e r t a t i o nd e s i g n sa n e wm e t h o dt o c l a s s i f yw e bp a g e s t h i sm e t h o du s e sl i n k sa n dc o n t e n t so fw e b p a g et od e c i d eap a g e sc l a s s t h er e s u l to fe x p e r i m e n ts h o w sa ni m p r o v e m e n to n m e t h o d s ，w h i c hc o n s i d e rc o n t e n t so fw e b p a g eo n l y t h e nt h i sd i s s e r t a t i o nd e s i g n s ab e t t e rf o c u sc r a w l i n gs y s t e m ，w h i c hu s eac l a s s i f i e rb a s e do nc o n t e n t sa n dl i n k s o faw e b p a g et od e c i d et h ep a g e sc l a s s ，a n dt h er e s u l to fe x p e r i m e n t ss h o w sa n i m p r o v e m e n to nc o m m o nm e t h o d i no r d e rt oc h e c ko u rm e t h o d s ，w e d e v e l o p af o c u sc r a w l i n gs y s t e mu s i n gv c + + 6 _ o k e yw o r d s ：i n t e r n e t ，w o r l dw i d ew e b ，i n f o r m a t i o nr e t r i e v a l s y s t e m ，s e a r c h e n g i n e ，c l a s s i f i c a t i o na l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得金卫王些叁堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字：签字日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解盒目b 王些盍堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 妲王些盔堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名导师签名： 签字日期：年月日签字日期：年月日 学位论文作者毕业后去向 工作单位； 通讯地址： 电话 邮编 致谢 在论文完成之际，首先要感谢我的导师吴国风副教授! 本论文从选题到最 后修改的全部过程都是在吴老师的精心指导下完成的。吴老师以她敏锐的洞察 力、渊博的学术造诣、严谨求实的治学态度、使我获益良多。在学习、工作和 生活上，吴老师一直给我无微不至的指导、关心和照顾。如果没有吴老师的支 持和帮助，我不可能按时完成我的毕业论文，在此对吴老师表示最衷心的感谢! 感谢胡学钢老师、候整风老师、王浩老师! 他们在论文的完成过程中，给 我提出了许多宝贵的建议，使我深受启发，在此向他们表示最衷心的谢意! 感谢我的同学曹祝君、刘建华、沈国海! 感谢他们在论文完成过程中给我 的无私帮助。 最后要特别感谢我的父亲、母亲、姐姐和弟弟! 他们的关心、支持、和帮 助是我前进道路上最大的动力! 忠心感谢理解、支持和帮助过我的所有人! 作者：韩巍 2 0 0 4 年5 月 1 1 问题的提出 第一章绪论 随着互联网的不断发展，其作用已经从最初的信息发送与接收发展成为各 种信息流的主要传输渠道。随之而来的是：网上信息的不断增长和上网用户的 不断增长。面对这一不断增长的趋势，人们急需要一种类似传统信息搜索系统 的超文本信息搜索系统来帮助寻找自己感兴趣的网页。于是以y a h o o c ：o m 为代 表的第一代互联网搜索引擎出现了。第一代搜索引擎的出现从很大程度上方便 了用户发现互联网上的有用信息，但是它们存在很多不足。于是，各种采用新 技术的互联网信息搜索引擎不断涌现，其中比较有代表性的搜索引擎就有： g o o g l e c o m 和d i r e e c t h i t t o m 等( 人们习惯称之为第二代搜索引擎) 。这些 新一代互联网信息搜索引擎的出现与发展，从一定程度上弥补了早期搜索引擎 的一些不足，而且在搜索结果的有效性方面也有了较大的提高。但是这些提高 相对于互联网信息的增长却显得微不足道，因为它们所能覆盖的网页占整个互 联网网页总量的比例越来越小( 据估计目前这个比例大概从3 到3 4 ) ，更 主要的问题是，随着互联网搜索引擎所覆盖的网页数不断增加，互联网用户将 会发现越来越难有效地利用这些搜索引擎来帮助自己发现所需要的互联网信息 资源。人们常常需要对搜索引擎返回的数以千计的结果进行费时费力的手工筛 选。 为了更好、更准确地满足用户的检索要求，人们提出了面向特定主题的信 息检索( f o c u s e d c r a w l i n g ) 1 1 1 。面向特定主题的信息检索技术可以很好地弥补 类似y a h o o 这样的综合搜索引擎的不足。其基本思想就是：根据所给定的面向 主题的内容说明，有选择地从互联网中搜索出与给定主题相关的信息资源。它 能够通过分析所发现的网页来确定搜索的边界，使自己只在可能与所要求主题 相关的w e b 区域内进行搜索，从而避免了盲目搜索其它无关的互联网区域。这 样不仅可以大大降低对硬件和网络资源的需求，而且也有助于提高信息更新的 频率。其中主题的定义描述是通过一系列示例网页来加以说明的。面向特定主 题的信息检索要解决以下两个问题： 1 ) 如何有效地描述用户的信息需求，目前主要通过预先给定的示例网页来 描述用户的信息需求。 2 ) 如何准确有效的搜索出所需要的网页，也就是如何在搜索过程中判断识 别主题相关的网页，搜索相关的网页而放弃不相关的网页。 1 2 本文的研究内容 本文对面向特定主题的w e b 信息检索进行了深入讨论，对如何在搜索过程 中判断识别主题相关的网页进行了较为深入的研究。在面向特定主题的信息检 索系统中，判断网页的主题相关性主要是通过预先训练的文本分类器来实现， 所以，分类器的分类性能直接影响整个系统的有效性。鉴于此，我们对网页的 分类技术进行了深入研究。目前，对网页的分类主要是采用基于网页内容的分 类方法，这种分类方法没有充分利用w e b 的链接信息，因而分类效果不是很好。 最近，一些学者对基于网页链接结构的网页分类进行了一些研究【2 ，3 ，4 ，5 ，6 l 。本文 在这些工作的基础上对基于文本的网页分类技术进行了改进，并提出了一个结 合网页链接结构的网页分类方法。 同时，在对网页分类技术进行研究的基础上，本文构造了一个基于网页链 接结构的特定主题信息搜索系统。 最后本文使用v c 开发环境实现了一个实验系统平台，并在这一平台上进行 了相关的实验。 1 3 本文的组织结构 第一章，主要介绍了问题的来源和论文的研究内容。 第二章，主要对w e b 信息检索技术进行简单的描述，给出了当前w e b 信息 检索技术的研究热点。 第三章，对网页分类技术进行了全面的探讨。讨论了基于网页内容的分类 技术和基于网页链接结构的分类技术，并且给出了一个网页分类算法。 第四章，对面向特定主题的w e b 信息检索进行了讨论，分析了面向主题的 w e b 信息检索系统的组成和关键技术，并且对其中的主题识别技术进行了改进。 第五章，主要进行了一些实验并且对实验数据进行了一些分析 第六章，对整个研究内容进行了总结，指出了不足之处和今后的进一步工 作。 2 第二章w e b 信息检索简介 w e b 信息检索系统一一搜索引擎，已经成为人们查找互联网信息必不可少 的工具，同时它也是互联网研究的一个热点。本章对搜索引擎技术进行了全面 的讨论，同时指出了当前搜索引擎技术存在的一些问题和相关的一些研究热点。 2 1 搜索引擎的起源和发展 i n t e r n e t 不象图书馆那样，向用户提供的是经过选择和分类的、有序的、系 统的、完整的信息；也不象商用联机系统，信息是按照一定格式加工处理，并 按照类型或学科分别建立数据库以便于检索利用。i n t e r n e t 信息具有以下几个特 点： 1 ) 信息内容覆盖全社会领域，涉及范围广，数量惊人。 2 ) 信息分散、无序、无组织。 3 、信息动态化，存放位置缺乏固定性，信息的增删更新、更换地址每时每 刻都在进行。 4 1 信息利用价值差异大，有用和无用的相互混杂交织在一起。 上述特点造成了网络信息检索和利用的困难，成为人们查询信息的障碍。 在这种情况下，长期以来习惯的信息获取方式己经不能满足人们的需要，为了 获取信息，用户需要自己来完成对所需信息的组织、整理、优化。从目前来讲， 即使是一个对i n t e r n e t 有许多了解，并积累了丰富上网经验的用户，在寻找信 息资料也会经常迟到很多困难，会得到大量的“信息垃圾”，而真正有用的信 息被淹没在这些垃圾中，有些人甚至称i n t e r n e t 为“信息垃圾站”。因此，需 要建立一个能在i n t e r n e t 网上高效查找信息的工具，这个工具就是搜索引擎。 从1 9 9 3 年起，一些站点为了方便用户浏览阅读，将手工收集到的站点信息 写成h t m l 文件，按一定的方式组织、分类成为目录式结构，这些结构被人们 称为c a t a l o g 或d i r e c t o r y 。几乎是同时，另一批技术人员着手研究用计算机代 替人工进行超链接的跟踪，并记录下各站点的u r l 及摘要信息。这釉程序被称 为r o b o t 、s p i d e r 或c r a w l e r s ，利用它们建立起来的查询系统就被称为s e a r c h e n g i n e 。这两类系统在不断的发展中互相借鉴，这个阶段可以看作搜索引擎的 雏形期。1 9 9 4 年4 月2 0 日w e b c r a w l e r 公司的w e b c r a w l e r 搜索引擎在网上正 式发布，六月l v c o s 公司建立l y c o s ；9 4 年底y a h o o 公司创办，正式建立y a h o o 站点；9 5 年下半年e x c i t e d 公司发布了e x c i t e 搜索引擎：这一时期的搜索引擎 处于试运行期，数据库容量较小，但是已经对i n t e r n e t 的发展起到了极大的促 进作用，这一阶段就是搜索引擎的“基础建设期”。1 9 9 6 年进入搜索引擎的“容 量建设期”，这时候的主流搜索引擎所引用的页面一般都超过一千万。1 9 9 7 年 竞争的焦点是制作高质量的索引，搜索引擎的发展处于“质量建设期”，这一 3 时期的代表是h o t n o t 。1 9 9 8 年之后，国外搜索引擎的发展迸入了“多向型发展 期”。有下面几个发展趋势： 1 ) 大型搜索引擎在诸多技术方面走向成熟，比如智能化“网络机器人的出 现”。 2 ) 一批小型的搜索引擎从通用型转向专业化。 3 ) 出现了m e t as e a r c he n g i n e ( 元搜索引擎) ，使得小型搜索引擎利用分 布式技术，可以在大型搜索引擎的数据库中进行搜索。 中文搜索引擎的发展是从1 9 9 6 年开始，台湾的“番薯藤”中文搜索引擎于 9 6 年2 月正式启动，是较早的中文搜索引擎。9 7 年5 月“悠游”公司在香港建 立了“悠游”中文搜索引擎。9 7 年5 月4 日y a h o o ! 发布了“雅虎”中文搜索 引擎；国内的搜索引擎的建设是在9 7 年底及9 8 年初起步的，“网易”搜索引 擎于9 7 年5 月开始建设；“北极星”中文站点信息检索系统于9 7 年1 2 月开通， 9 8 年5 月“搜狐”搜索引擎建立。 2 2 搜索引擎的体系结构和工作原理 2 2 1 搜索引擎的组成部分 一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成，下 面介绍一下这几个部分的功能和作用： 1 ，搜索器 搜索器的功能是在互联网中漫游，发现和搜集信息。它常常是一个计算机 程序，日夜不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息， 同时因为互联网上信息更新很快，所以还要定期更新已经搜集过的旧信息，以 避免死连接和无效连接。目前有两种搜集信息的策略 1 ) 从一个起始u r l 集合开始，顺着这些u r l 中的超链接( h y p e r l i n k ) ， 以宽度优先、深度优先或启发方式循环地在互联网中发现信息。这些起始 u r l 可以是任意的u r l ，但常常是一些非常流行、包含很多链接的站点， 如：y a h o o ! 。 2 ) 将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责一个 子空间的穷尽搜索。 搜索器搜集的信息类型多种多样，包括h t m l 、x m l 、n e w s g r o u p 文章、 f t p 文件、字处理文档、多媒体信息。 搜索器的实现常常采用分布式、并行计算技术，以提高信息发现和更新的 4 速度。商业搜索引擎的信息发现可以达到每天几百万网页。 2 索引器 索引器的功能是理解搜索器所搜索的信息，从中抽取索引项，用于表示文 档以及生成文档库的索引表。 索引项有客观索引项和内容索引项两种。客观项与文档的语意内容无关， 如作者名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等 等；内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。 内容索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索引项 对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空 格) ；对于中文等连续书写的语言，必须进行词语的切分。在搜索引擎中一般 要给单索引项赋一个权值，以表示该索引项对文档的区分度，同时用来计算查 询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项 的提取方法有统计法、概率法和语言学法。 索引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) 即由索引项查找相应 的文档。索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索 引项之间的相邻或接近关系。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必 须实现即时索引( i n s t a n ti n d e x i n g ) ，否则跟不上信息量的急剧增加。索引算 法对索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。一个搜 索引擎的有效性在很大程度上取决于索引的质量。 3 检索器 检索器的功能是根据用户的查询在索引库中快速检索出文档，进行文档与 查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈 机制。检索器常用的信息检索模型有集合论模型、代数模型、概率模型和混合 模型四种。 4 用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机 制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得 到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以 充分适应人类的思维习惯。用户输入接口可以分为：简单接口和复杂接口两种。 简单接口只提供用户输入查询串的文本框；复杂接口可以让用户对查询进行限 制，如逻辑运算( 与、或、非、十、一) 、相近关系( 相邻、n e a r ) 、域名范 围( 如：e d u 、t o m ) 、出现位置( 如标题、内容) 、信息时间、长度等等。 目前一些公司和机构正在考虑制定查询选项的标准。 5 2 2 2 搜索引擎的工作流程 总的来说，搜索引擎的工作流程分为两个过程：一是关于互联网网页信息 的全局索引数据库的建立；二是根据用户的检索要求检索索引库返回检索结果 的过程。前者可称为信息标引过程后者可称为提供检索过程。 1 建立索引数据库 机器人( 即上文所说的搜索器) 从一个事先制定好的网址( u r l s ) 列表 出发，这个列表中的网址通常是从以往访问记录中提取出来的，特别是一些热 门站，此外，很多搜索引擎还接受用户提交的网址，这些网址也会被安排在列 表中供机器人访问。机器人访问了一个网页后，会对它进行分析，提取出新的 网址，将之加入到访问列表中，如此递归地访问w e b 。机器人可以采用宽度优 先或深度优先策略来遍历整个w e b 。 机器人提取的网页将被放入到索引器中以建立索引数据库，不同的搜索引 擎会采取不同方式来建立索引，有的对整个h t m l 文件的所有单词都建立索 引，有的只分析h t m l 文件的标题或前几段内客，还有的能处理h t m l 文件 中的m e t a 标记或其它不可见的特殊标记。索引器在建立索引时，一般会给网 页中每个关键词赋予一个等级值，表示该网页与关键词之间的符合程度。当用 户查询一个关键词时，检索软件将搜索索引器，找出所有与关键词相符合的网 页，有时候这些网页可能有成千上万，等级值的用途就是作为一种排序的依据， 搜索软件将按照等级值从高到低的顺序把搜索结果送回到用户的浏览器中。不 同的搜索引擎在计算等级值时使用了不同的方法，但它们都以关键词在网页中 出现的位置和频率为基本依据，例如，关键词出现在标题中的网页可能比只出 现在其它地方的网页更符合要求，关键词出现在网页的前面可能比只出现在网 页的后面更符合要求，同一个关键词出现多次的网页又可能比只出现一两次的 网页更符合要求，把这些因素综台起来考虑便可得出一个计算等级值的公式。 不过，绝大多数搜索引擎都没有只按照上述因素来确定计算公式，它们还加入 了一些特殊考虑，例如，g o o g l e 通过对网页的链接结构进行分析从而确定一个 网页的等级值( 被更多的高权威值的网页指向的网页同样具有高权威值) 。 2 提供检索过程 提供检索过程是搜索引擎根据用户检索需求表达式进行查找与输出结果的 过程。它建立在网络信息标引的索引库、文摘库等基础之上。其工作流程如图 2 1 所示： 2 3 搜索引擎的主要指标及其分析 搜索引擎的主要指标有响应时间、召回率、准确率、受欢迎程度、建立索 引的方法和相关度排序方法等等。所谓召回率是指：检索出的相关文档数和文 6 档库中所有的相关文档数的比率，衡量的是检索系统( 搜索引擎) 的查全率； 准确率是指：检索出的相关文档数与检索出的文档总数的比率，衡量的是检索 系统( 搜索引擎) 的查准率。相关度是指用户查询与搜索结果之间相似度的一 种度量。响应时问、召回率、准确率和受欢迎程度是搜索引擎的主要评价指标， 建立索引的方法和相关度是搜索引擎有代表性的技术指标。搜索引擎的技术指 标决定了搜索引擎的评价指标。好的搜索引擎应该具有较快的响应速度和高的 召回率和准确率，当然这些都需要搜索引擎的技术指标来保障。下面将详细讨 论搜索精度、搜索引擎的受欢迎程度、搜索引擎建立索引的方法以及相关度。 图2 - 1 搜索引擎的检索流程 1 搜索引擎的精度 搜索引擎的准确率是个复杂的概念，一方面表示搜索引擎对搜索结果的排 序能力，另一方面却体现了搜索引擎对垃圾网页的抗干扰能力。对搜索结果的 排序能力主要取决于搜索引擎采用的排序( r a n ka l g o r i t h m ) 算法的优劣。互 联网中大多数网页是比较正式的：但是有些人为了赢利( 由于他可以通过用户 访问他的站点，使他从一些点击付费网站中获取利益) ，通过非法途径欺骗搜 索引擎使得自己有较高的排名，从而使得使用该搜索引擎的用户获得无用的信 息。例如，在“莱温斯基事件”炒得沸沸扬扬的时候，很多人想了解有关该事 件的最新报到，但是通过搜索引擎找到的却是很多无关紧要的东西。这主要是 有些站点的垃圾信息、影响了正常搜索结果的排序。对付垃圾网页的办法主要 是让网络蜘蛛具有判别是否是垃圾网页的能力。 2 搜索引擎的受欢迎程度 搜索引擎的受欢迎程度体现了用户对搜索引擎的偏爱程度。知名度高、性 能稳定和搜索质量好的搜索引擎将备受青睐。 3 搜索引擎建立索引的方法 7 网络蜘蛛将信息存放到搜索引擎本地数据库中。为了加快检索的速度，搜 索引擎要对这些数据库中的信息建立倒排索引，建立倒排索引的时候，不同的 搜索引擎有不同的选项。 1 1 全文索引和部分索引 有些搜索引擎对于信息库中的页面建立全文索引，有些只建立摘要部分， 或者每个段落前面部分的索引，还有些搜索引擎( 如g o o g l e ) 建立索引的 时候，同时考虑超文本的不同标记所表示的不同含义。如粗体、大字体显 示的东西往往比较重要；放在锚链中的信息往往是它所指向页面的信息的 概括，所以用它来作为它所指向的页面的重要信息。g o o g l e 、i n f o s e e k 还 在建立索引的过程中收集页面中的超链接。这些超链接反映了收集到的信 息之间的空间结构。利用这些结果信息可以提高页面相关度判别时候的准 确度。 2 1 是否过滤无用的词汇 由于网页中存在着许多无用的单词( s t o pw o r d s ) ，例如英文单词“a ”、 “a n ”、“t h e ”等。中文中的“的”、“啊等。这些词汇不能明确表达 该网页信息。所以有些搜索引擎保存一个无用词汇表，在建立索引的时候 将不建立这些词汇的索引。我们可以通过简单的方法来测试搜索引擎是否 过滤掉了无用词汇。选择针对性的几个无用词汇，然后将这些无用词汇作 为检索的关键词提交给搜索引擎。如果搜索引擎检索不到结果，则该搜索 引擎具有过滤无用词汇的功能。但是有些搜索引擎在利用用户的查询串进 行查询之前，先过滤掉查询串中的无用词汇，这样通过我们的方法就不能 检测粗搜索引擎建立索引的时候是否过滤了无用词汇。 3 1 是否使用m e t a 标记中的信息 网页中的m e t a 标记用来标注一些非显示性的信息。有些网页将页面的关 键词等信息放在其中，便于建立索引的过程中提高这些词汇的相关度。 g o o g l e 与i n k o t o m i 在建立索引的时候考虑了页面中的m e t a 标记。 4 1 是否对图像标记中的替换文本或者页面中的注解做索引 由于现有的搜索引擎对于图像的检索技术还不成熟，大多数搜索引擎不支 持图像的检索。在超文本的结构页面中，图像标记中往往存放着图像的替 换信息。这些信息说明了该图像标记对应的图像的基本信息。如果能够对 这种图像替换信息进行索引，将可以进行某种程度上的图像检索。 a l t a v i s t a 、g o o g l e 专门针对图像的替换文本建立了索引。页面中的注解 ( c o m m e n t s ) 信息主要是页面的设计者在页面设计过程中添加的一些附加 信息，它不在浏览器中显示。i n k o t o m i 在索引过程中建立对注解信息的索 引。 5 ) 是否支持词干提取技术 词干提取技术是指搜索引擎在建立索引的过程中。只对词汇的词干部分建 立索引。如对单词“c o m p u t e r s ”、“c o m p u t i n g ”等单词“c o m p u t e ”的词 性变换形式，统一建立单词“c o m p u t e ”的索引。我们可以通过向搜索引擎 交同一词汇的不同变化形式如果得到相同的搜索结果，那么该搜索引擎己 经使用了词干提取技术。有些搜索引擎在用户提交查询请求的时候，首先 对查询请求中的词条进行词干提取然后再送给后台的搜索程序。有些搜索 引擎在对查询请求中的词条进行词干提取后，将词干的所有变化形式一起 作为搜索请求提交给搜索程序。 4 搜索引擎相关性考虑 搜索引擎在决定关键词与页面的相关性的时候主要考虑关键词在页面中的 位置和频率，即所谓的“位置频率”如果关键词出现在页面的头部，或者在它 的标题( t i t l e ) 标记中，那么显然该页面比较重要。如果关键词在页面中重复 多次出现，显然该页面跟那关键词的相关度越高。近年来，出现了一些计算相 关度的新方法。这些方法的出现大大提高了搜索的精度。e x c i t e 、g o o g l e 等充 分挖掘超文本本身的结构特点，考虑页面之间的链接关系对页面相关度的影响。 它们基于这样一种直觉：如果一个页面被重要的页面所指向，那么被指向的页 面也相对重要。h o l b o t 和l y c o s 则考虑用户的点击行为对页面相关度的影响g o 和i n k o t o m i 考虑了m e t a 标记对页面相关性的作用。一些混合结构( 搜索引擎 和目录共存) 的搜索引擎可能会把那些目录中己存在的站点的网页靠前，因为 一个站点足够好才能放到目录中，就应该有机会比那些不被列在目录中的站点 的网页靠前。 2 4 存在的问题 w e b 信息检索在关键技术、系统设计等各个方面已经取得了初步的进展， 研究成果向实用转化也比较成功。目前w e b 信息检索系统已成为全球科研、教 学、商务等活动中不可缺少的重要工具，在一定程度上解决了网络信息资源查 找的问题。但是，正如一些文献中所讨论的，w e b 信息检索仍然在精度、易用 性等方面存在诸多问题： 1 查询语言 现有的搜索引擎提供给用户的提问函数是相当有限的，大多数的搜索引擎 只提供关键词间最基本的布尔连接。例如y a h o o 只提供a n d 和o r 两种运算 符，并且强制个逻辑运算符应用于所有的关键词。o p e n t e x t l n d e x 允许用户用 不同的布尔运算符，但是仅仅允许4 个运算符且必须按出现次序运算。像s q l 语言那样复杂的查询语言在现有的搜索引擎中还不能应用。现有的搜索引擎的 查询语言甚至比成熟的商业性的情报检索系统的查询语言还要简单。当然这是 由搜索引擎所处的环境所决定的。一套能充分表达用户要求但是又不增加网络 9 负载的查询语言是搜索引擎给用户的第一个好印象。 2 搜索结果精度不够 页面具有创建日期，修改日期，页面大小，页面作者，页面主题，关键词 等描述性特征和语义性特征。现有的搜索引擎基本上通过对w e b 页面的全文建 立索引来描述页面。无法全面描述页面的所有特征，损失了页面的部分属性特 征、页面结构及内容语义。此外，用户通常只能使用关键词来表达查询，对页 面的全文进行检索，得到所有包含该词条的页面。但是关键词无法清楚描述用 户的真正需求。虽然用户可以通过使用布尔操作符来组合多个词条以构造条件 严格的查询、精华检索结果，但是，这要求用户具有明确的检索目标，并对检 索语法和检索内容相当熟悉，否则会同时过滤掉很多有用的资源。实际的使用 状况表明，绝大部分用户查询所使用的词条数目不多于2 个。因此w e b 信息检 索通常会得到数目相当庞大的结果，包含的信息资源类型多样、质量良莠不齐， 大量对用户无用的信息混杂其中。因此w 曲信息检索精度一般较低。如何提高 搜索引擎的精度是当前研究的重点问题。 3 检索手段单一 现有的搜索引擎仅允许用一组关键词及逻辑运算符组成提问。但是关键词 不能完全满足用户的要求，而且它是一种盲目的匹配。而自然语言理解是解决 检索单一的关键技术之一，是目前的研究热点 4 覆盖率的限制 由于现在w e b 上的信息量变得越来越大。索引机器人的能力，索引数据库 的大小，系统维护开销等，都限制了一个搜索引擎的能力。各个搜索引擎为了 在竞争中获胜而不断地增加其索引的w e b 页面数目，但是却跟不上w e b 的发 展速度。据最新统计表明：任何一个搜索引擎索引的w e b 页面与可索引页面总 数的比例( 通常称为覆盖率，c o v e r a g e ) 均不到3 0 ，而且最主要的1 1 个搜索 引擎组合起来的覆盖率仅仅为4 2 。为了尽可能地保持索引数据库与w e b 之间 的同步，w e b 信息检索系统还要不断地重复页面下载和索引过程。搜索引擎的 索引更新周期通常为几个月，索引数据库越大，更新也越困难。另外由于搜索 引擎索引更新不及时，搜索结果中往往会包含一些无效的页面链接。 5 动态页面的搜索 目前w e b 上大量的资源以数据库的方式存放，通过动态页面而不是静态页 面的方式提供给用户。对于门户网站与专业网站来说很难对此类网站的所有页 面，特别是动态页面部分进行索引。即使门户网站与专业网站可以对这些动态 页面进行索引，但是这些动态页面的更新速度往往超过门户网站与专业网站索 引的更新速度 举例来说，电子商务网站的商品信息一般都存放在后台数据库中，而且商 品信息的更新速度非常快，往往每天都有大量的商品信息更新，而门户网站与 1 0 专业网站的搜索引擎索引的更新速度往往是达到几个月，两者的更新速度差别 甚至可以达到几个数量级。 2 5 当前的研究热点 1 元搜索引擎1 4 , 1 5 , 1 6 , 1 7 , 18 从上一节的分析可见，目前大部分独立搜索引擎的覆盖率都较低。因此用 户经常需要检索多个搜索引擎以提高检索的召回率( r e c a l l ) 。于是元搜索引擎 应运而生，元搜索引擎相当于多个独立搜索引擎的集成：对用户提供一个统一 的查询接口，底层调用多个独立搜索引擎并将多个搜索引擎的返回结果进行集 成和处理再返回给用户，如图2 2 所示： 图2 - 2 元搜索引擎的工作原理 2 信息检索a g e n t 搜索引擎、元搜索引擎等w e b 信息检索系统通常作为一种大型的服务器程 序运行，同时响应多个用户的请求。这些系统不能够根据用户的兴趣需求来定 制检索结果。例如，研究“信息检索”和研究“机器人”的用户在查询“r o b o t ” 时，所得到的检索结果及相关性排序完全相同。事实上，不同领域背景、知识 结构的用户对文档相关性的判断以及检索结果的要求是不一样的。即使同一个 用户，在不同的时期也有所侧重。信息检索a g e n t 提供了一种完全不同的w e b 信息检索模型，它具有以下特征： 1 ) 可适应性：信息检索a g e n t 能够从用户日常的检索、浏览等行为中学习 用户的兴趣，推理用户的需求，为用户建立个性化的p r o f i l e 。 2 ) 主动性：信息检索a g e n t 能够主动地根据用户的兴趣需求从w e b 上检索 相应信息，甚至能够监控信息源的变化，及时地报告给用户。这些工作的 开展不需要用户的参与，而由a g e n t 利用自身的控制机制、知识等进行任 务规划、问题求解。 3 ) 协作性：信息检索a g e n t 之间可以共享和交流信息，实现协作式信息检 索。例如，一个用户的a g e n t 可以从具有相同兴趣需求用户的a g e n t 那儿获 寻很多有用信息。 4 ) 移动性：信息检索a g e n t 能够移动到远程服务器上，并在服务器上进行 信息检索，以避免将信息下载到客户端。在服务器上信息量很多，客户与 服务器之间没有持久、稳定的网络连接，或者客户机的处理能力不够时， 移动a g e n t 十分有用。 3 面向特定主题的信息检索( f o c u s e dc r a w l i n g ) 1 1 0 ，3 4 5 】 面向主题的信息搜索其基本思想就是，利用一个聚焦搜索软件代理 ( f o c u s e d c r a w l i n g ) ，根据给定的主题内容要求说明，有选择地从互联网中搜索 出与给定主题相关的信息资源。与一般搜索引擎最大的不同就是，这种聚焦搜 索方法，能够通过分析所发现的网页链接来确定搜索的边界，使自己只在可能 与所要求主题相关的w e b 区域内进行搜索，从而避免了盲目搜索其它无关的互 联网区域。显然这样不仅可以大大降低信息搜索对硬件和网络资源的要求，而 且也有助于提高信息更新的频率。其中主题的定义描述是通过一连串实例文档 来加以说明的。 4 基于链接结构的网页分类m ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 】 大家都知道，一篇论文的好坏与其被引用的次数有很大关系。在w e b 上网 页之间的相互链接也反映了这一规律。所以说一个网页的链接结构能够很好地 反映该网页的内容，因此人们在网页分类中引入了链接分析。这就是所谓的基 于链接的网页分类。网页分类在w e b 信息抽取和面向特定主题的w e b 信息搜 索中有重要的应用，所以也是本文研究的主要内容。 5 基于超链的相关度排序f 1 9 , 2 0 , 2 1 , 2 2 , 2 3 , 2 4 , 2 5 所谓相关度排序是指：搜索引擎对一次查询结果按照和查询的接近程度进 行排序的过程。互联网发展早期的搜索引擎，对w e b 页面的排序，魁根据搜索 的词组( 短语) 在页面中的出现次数，并用页面长度和h t m l 标签的重要性提 示等进行权重修订。当人们注意到：链接和页面内容的相关性后，基于链接的 相关度排序技术出现了。这种技术通过统计其它文档链接到当前页丽的链接数 量来决定当前页面的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索 引擎的手法。典型的算法是g o o g l e 的p a g e r a n k 算法。 6 检索结果的联机聚类 2 6 , 2 7 , 2 8 1 尽管搜索引擎采用了各种方法来提高检索结果的精度，但是结果中仍然包 含了与用户查询请求不相关的文档，其比例高达7 5 以上。此外，搜索引擎返 1 2 回给用户的通常是个线性的文档列表，虽然经过了相关度排序，但是相关文 档和不相关文档仍然混杂于其中。用户必须逐个地浏览以找到相关文档，花费 了大量的精力。当返回的结果数目众多时，这个问题更为突出。为了方便用户 的浏览，一些研究人员开始将聚类技术用于w e b 信息检索结果的可视化输出。 聚类是指将文档几何分成若干个簇，要求同一簇内文档内容的相似度尽可能地 大，而不同簇间的相似度尽可能地小。h e a r s t 等人的研究已经证明了“聚类假 设”，即与用户查询相关的文档通常会聚类得比较靠近，而远离与用户查询不 相关得文档。因此我们可以利用聚类技术问搜索引擎的检索结果集合s 划分为 若干个簇( s 1 s i ，s m ) ，这样用户只需要考虑那些相关的簇，大大缩小 了所需浏览的结果数量。 第三章网页分类算法研究 网页分类在面向特定主题的w e b 信息搜索中有重要作用，分类器的性能好 坏会直接影响到系统的性能。同时，网页分类技术在网页信息自动抽取和w e b 挖掘中也有重要的应用。因此本章对网页分类技术进行研究并提出了一个基于 网页间链接结构的网页分类算法。 3 1 基于文本的网页分类 如果把网页简单地看成文本，则网页分类就是文本分类的一个特例。其实， 目前基于网页文本的分类技术就是已有文本分类技术的一个范例。 3 1 1 文本分类简介 文本分类( t e x tc a t e g o r i z a t i o n ) 是在给定的分类体系下，根据文本的内 容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程， 它将未标明类别的文本映射到已有的类别中。该映射可以是一一映射，也可以 是一对多的映射，因为通常一篇文本可以同多个类别相关联，用数学公式表示 为：厂：a b 。其中，a 为待分类的文本集合，b 为分类体系中的类别集合。文 本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结出分 类的规律性而建立的判别公式和判别规则；然后在遇到新文本时，根据总结出 的判别规则确定文本相关的类别。长期以来文本分类都是自然语言处理的一个 重要的应用领域。直到8 0 年代末，在文本分类方面占主导地位的一直是基于知 识工程的分类方法，即由专业人员手工编写分类规则来指导分类，其中最著名 的系统是为路透社开发的c o n s t r u e 系统。9 0 年代以来，随着信息存储技术和 通信技术的迅猛发展，大量的文字信息开始以计算机可读的形式存在，并且其 数量每天仍在急剧增加。这一方面增加了对于快速、自动的文本分类的迫切需 要，另一方面又为基于机器学习的文本分类方法准备了充分的资源。在这种情 况下，基于机器学习的文本分类通常由训练和分类两个阶段组成，在训练阶段， 从训练文本学习分类知识，建立分类器；在分类阶段，根据分类器将输入文本 分到最可能的类别中。在机器学习领域，分类属于监督学习。文本分类作为组 织和管理数据的一种有力手段，可被用于各种应用中。 3 1 2 文本分类中的关键技术 3 1 2 1 文本表示 大规模文本处理的对象是大量的真实文本，要使得计算机能够高效率、高 性能地处理自然文本，就必须找到一种理想的文本表示方法。文本表示最理想 1 4 的境界就是模拟人所理解的语义，通过函数f ，使得 人所理解的语义= f ( 文本) 一旦找到了合适的函数来表示人所理解的语义，那么整个问题就变得很简 单了。对于文本分类的过程就可以转化为一个搜索问题，即寻找和新文本函数 值差异最小的文本类。但是不幸的是，这种精确反映人所理解语义的函数是很 难定义的，或者更极端一点说，也许根本就是不存在。对于形式语言而言，语 义还可以通过机器状态的改变来描述，我们也正是通过这种方式来学习和掌握 机器语言的；可是对于自然语言而言，由于涉及到人这个认知主体的思维活动， 不同的认知主体往往会有不同的理解，自然语言的形式及其意义之间是一种多 对多的关系，很难合理地定义一个反映语义的函数。 既然这种寻求精确反映人所理解语义的道路是不可行的，那么我们只好退 而求其次，寻求一种能够量化、能够形式化、最终可以计算和操作的表示方法。 唯一可行的方案就是走统计的路线，研究从大规模语料库中发现出来的统计规 律，利用文本在字集合或词集合上的分布来近似表示语义，并且做如下的假设： a ) 两个分布完全一致的文本被认为是语义相同的。 b ) 两个分布相近的文本被认为是语义相近的。 自然，仅仅采用这种分布是不能精确反映人所理解的语义的，然而这种方 案却能够很方便地计算和操作，对于信息处理等应用领域，其表达效果还是可 以接受的。 根据以上思路，我们来考察文本，众所周知，文本是字词等代表特定含义 的符号按顺序连接的字符流，从这里可以看出，文本有两个基本的特征：一是 组成文本的所有字词符号，二