（计算机软件与理论专业论文）基于文本挖掘的web信息检索研究.pdf

华北电力大学硕士学位论文摘要 摘要 i n t e r n e t 中的信息越来越丰富，使得搜索引擎准确率不高等问题愈发严重。本 文对如何利用文本挖掘技术解决w e b 信息检索中准确率不高等问题进行研究。 本文详细阐述了w e b 文本挖掘尤其是w e b 文本聚类技术，w e b 信息检索原理， 以及w e b 文本模型针对w e b 文本的特点，对向量空间模型进行了改进。结合模糊 c 一均值聚类与自组织映射神经网络，给出了一种改进的模糊自组织映射神经网络聚 类算法。 最后应用改进的模糊自组织映射神经网络算法。实现了一个聚类搜索引擎实验 系统，验证了上述模型与算法对搜索引擎准确率的提高。 关键词：w e b 文本聚类，搜索引擎，向量空同模型，模糊自组织映射 a b s t r a c t i tm a k e ss e a r c he n g i n e sp r o b i e m ss u c ha sl o wv e r a c i t ym o r ea n dm o r e s e r i o u st h a tt h ei n f o r m a t i o ni nt h ei n t e r n e ti sg e t t i n gr i c h e ra n dr i c h e r t h i sp a p e rd o e sr e s e a r c ho nh o wt or e s o l v et h ep r o b l e mo fl o wv e r a c i t yi n w e bi n f o r m a t i o nr e t r i e v a lw i t ht e x tm i n i n g w e bt e x tm i n i n g ，e s p e c i a l l yw e bt e x tc l u s t e r i n g ，w e bi n f o r m a t i o n r e t r i e v a lp r i n c i p l e sa n dw e bt e x tm o d e l sa r ei n t r o d u c e di nd e t a i i v e c t o r s p a c em o d e li si m p r o v e da c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ew e bt e x t m o d e l f u z z yc m e a n sc l u s t e r i n ga n ds e l f - o r g a n i z e dm a pn e u r a ln e t w o r ka r e c o m b i n e da n dac l u s t e r i n ga l g o r i t h mo fi m p r o v e df u z z ys e l f o r g a n i z e dm a p n e u r a ln e t w o r kisp r o p o s e d f i n a l l yi m p l e m e n tac l u s t e r i n gs e a r c he n g i n ee x p e r i m e n t a ls y s t e mw i t h t h ei m p r o v e df u z z ys e l f o r g a n i z e dm a pn e u r a ln e t w o r k t h ei m p r o v e m e n to f v e r a c i t yb ya b o v em o d e la n da l g o r i t h mi sv e r i f i e d l i2 i q i a n g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f w a n gc u i r u k e yw o r d s ：w e bt e x tc l u s t e r i n g ，s e a r c he n g i n e 。v e c t o rs p a c em o d e l ， f u z z ys e l f o r g a n iz e dm a p 声明 本人郑重声明：此处所提交的硕士学位论文基于文本挖掘的w e b 信息检索研 究，是本人在华北电力大学攻读硕士学位期间。在导师指导下进行的研究工作和 取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：至鱼蕴 日 期：圣塑z 。z ! 梦 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不 同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：奎鱼毽 日 期：兰盟乙! 签 华北电力大学硕士学位论文 1 1 选题背景及其意义 第一章绪论 1 1 1研究基于文本挖掘的w e b 信息检索的背景及意义 据最新调查统计，i n t e r n e t 中的w e b 页面总数超过十亿，并且正在以每四个月 翻一番的速度增长。i n t e r n e t 包含了从技术资料、商业信息到新闻报道、娱乐信息 等多种类别和形式的信息，是一个极具价值的信息源。i n t e r n e t 是一个开放、动态、 异构的全球分布式互连网络，并且没有统一的管理机构，这导致了信息获取的困难。 如何有效地获取w e b 信息，以帮助用户快速、准确地从浩瀚的信息资源中寻找所需 信息己经成为一个亟待解决的问题，即“信息爆炸”问题。 为了从海量信息中辨别出有用信息，发现信息背后隐藏的有价值的知识，出现 了多种搜索引擎。搜索引擎基本解决了i n t e r n e t 上的资源发现问题，但检索结果 仍不能令人满意。通过关键词进行检索，一般都会得到大量的检索结果，而且其中 大部分页面都与用户需要的信息无关，有用信息往往淹没在众多无用信息当中。利 用w e b 文本挖掘可更合理的组织检索结果，按照主题将页面分为若干类别，这样用 户就可以选择浏览他所关心的类别。 w e b 文本挖掘技术，可使w e b 搜索引擎上升到新的高度。把w e b 文本挖掘技术 应用到搜索引擎中去，为w e b 信息的利用提出了新的解决方案，将会引起搜索引擎 方面一场新的革命。因此，进行基于文本挖掘的w e b 信息检索研究有着十分重要的 理论与现实意义。 1 1 2 搜索引擎存在的主要问题 当前，搜索引擎技术已有初步的发展，在一定程度上解决了在i n t e r n e t 中查找 所需信息的问题，但仍存在一些问题。 ( 1 ) 准确率不高。w e b 信息检索通常会得到数目庞大的结果，其中包含的信息资 源类型多样、质量良莠不齐，大量对用户无用的信息混杂其中，因此w e b 信息检 索准确率一般较低。 ( 2 ) 检索结果的展现形式简单。大多数搜索引擎都只返回一张冗长的检索结果列 表，简单地包含u r l 、标题、摘要等少量信息，缺乏必要的组织，视图单一，给用 户带来不便。 华北电力大学硕士学位论文 ( 3 ) 智能化程度低。如何利用智能化方法从页面中自动地抽取关键词、分类、摘 要等重要信息，并对信息资源各种特征之间的关联和整体分布进行分析，是一个难 点问题。 ( 4 ) 检索速度慢。用户提交检索请求后，通常需要等待较长时间，才能得到检索 结果n 儿封”。 从上面分析的情况可以看出，要提高搜索引擎的性能和效率，使搜索引擎具有 “智能”，已不能仅从信息检索技术上来考虑，而必须将w e b 文本挖掘引入搜索引 擎中。 1 1 3w e b 文本挖掘 w e b 挖掘是从i n t e r n e t 资源中抽取有用模式和隐藏知识的过程，是将数据挖掘 技术和理论应用于i n t e r n e t 资源的一个新兴研究领域。按照处理对象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 多媒体挖掘，其中w e b 文本挖掘是当前研究与应用的 热点。 w e b 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息 检索技术，从大量的文本数据中发现和提取隐含的、事先未知的信息，最终形成用户 可理解的、有价值的知识的过程“1 。w e b 文本的分类和聚类是最重要、最基本的挖 掘功能。 文本分类是在已分类数据的基础上构造一个分类模型( 称为分类器) ，它按照预 先定义的分类体系( 即分类模型) ，将w e b 文本集合中的每个文本归纳入某个类别。 文本分类的主要步骤包括：预处理、特征抽取、特征匹配。文本分类的方法主要有 统计法、机器学习法、神经网络法、矩阵变换法等。 文本聚类是将文本集合分成若干个类，要求同一类内文本内容的相似度尽可能 地大，而不同类间文本内容的相似度尽可能地小。文本聚类算法可以分为两种类型： 层次聚类法和平面划分法层次聚类法能够生成层次化的嵌套类，平面划分法将文 本集合水平地分割为着于个类嘲州” 1 1 4 课题的提出 针对目前搜索引擎存在的主要缺点和不足，本课题试图利用w e b 文本挖掘技术 加以改进。主要思路是：根据w e b 文本的特点，归纳出w e b 文本模型，研究并改进 2 华北电力大学硕士学位论文 w e b 文本挖掘技术；然后利用改进的w e b 文本挖掘技术，对w e b 信息检索结果进行 聚类等处理，将w e b 信息检索结果划分为若干类，便于用户浏览及筛选所需信息。 1 2 国内外研究动态 1 2 1国外研究动态 v i c e n ct o r r a ，s a d a a k im i y a m o t o 和s e r g il a n a u 在g a m b a l 系统基础上提出 了w e b 文本的模糊层次聚类方法嘲。g a m b a l 系统不仅根据w e b 文本中词的语法相似 性，而且根据字典和潜在语义分析，分析计算文本的相似度。模糊方法使得聚类结 果以一定的隶属度属于若干类，避免了聚类的绝对化，更加符合实际。 t a r u n k l e r 和j c b e z d e k 提出了a c e ( a l t e r n a t i n gc l u s t e re s t i m a t i o n ) 模型m ，进行w e b 文本聚类。a c e 模型采用交互的、迭代的方法，在聚类的过程中， 用户可以改变聚类和聚类中心的更新函数，系统根据用户的选择修正模型，使得模 型更加符合所处理数据的特点。 c h e k u r ic 。g o l d w a s s e rm h 和r a g h a v a np 提出了网页自动分类与关键字 查询相结合的技术“”。文中采用的分类方法最后返回和待分类网页最接近的类别列 表。这种改进的好处在于，算法结果不过分依赖网页自动分类的精确性。 i b m 公司的w e b 挖掘软件包，包括t e x t m i n e r ，n e t q u e s t i o n ，w e b c r a w l e r 及文 本分析工具，支持文本数据的信息搜索，为文本按主题创建目录及创建索引等功能。 这些产品利用了高质量的机器学习算法，能够处理大量的数据，并保证理想的响应 时间 1 2 2 国内研究动态 四川联合大学的徐代刚、唐常杰等在机译系统的支持下，结合数据挖掘和文本 分析技术，研究了从w e b 文本中挖掘语言知识的基本方法，提出了一个文本挖掘系 统的基本框架。 南京大学的黄豫清，戚广志，张福炎等对w e b 文本的信息抽取进行了研究，提 出了对象交换模型( o b j e c te x c h a n g e m o d e l ，简称o e m ) “”，用以建立w e b 信息模型 其中的半结构化信息的抽取算法，可以抽取结构化和半结构化的信息，比现有的抽 取方法通用性更强。 中国科学院计算技术研究所的宫秀军、史忠植等。提出了基于b a y e s 潜在语义 模型的半监督w e b 挖掘算法“”该算法分为两个阶段：第一阶段利用贝叶斯潜在语 义模型来标注含有潜在类别主题词变量的网页的类别，第二阶段利用简单贝叶斯模 3 华北电力大学硕士学位论文 型。在第一阶段类别标注的基础上，通过e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法对不 含有潜在类别主题词变量的文本作类别标注。该算法具有很高的精度和召回率。 哈尔滨工程大学的张健沛、刘洋、杨静等提出了一种新的基于p a t 树的搜索引 孥结果聚类算法“”。该算法把p a t 树数据结构和s t c ( s u f f i xt r e ec l u s t e r i n g ) 算 法结合起来用于中文文本聚类，它使用p a t 树数据结构克服s t c 算法处理中文信息 的不足，使用s t c 框架来保证聚类能有效地执行。 1 3 课题研究内容 针对搜索引擎存在的主要问题，本课题就基于文本挖掘的w e b 信息检索进行研 究。着重在以下几方面进行研究： ( 1 ) 对w e b 文本( 主要是h t m l 文本) 的结构、内容等方面的特点进行深入的分析 和探讨，抽象出w e b 文本模型。 ( 2 ) 对现有的w e b 文本挖掘算法加以改进。对现有的w e b 文本挖掘技术进行深入 研究，归纳分析各种方法的优势与缺陷。掌握各种方法的适用范围与约束条件，针 对w e b 文本模型的特点使改迸的算法产生高质量的结果。 ( 3 ) 利用改进的w e b 文本挖掘算法，建立聚类搜索引擎应用系统，力图在检索结 果的准确性方面有所提高 1 4 研究方案，工作特色及难点 1 4 1 研究方案 ( 1 ) 根据实际问题建立w e b 文本模型，该模型要包含足够的信息以准确描述w e b 文本，并且要尽可能的简练以便于处理。 ( 2 ) 对w e b 信息检索结果中的w e b 文本进行简化与抽象，表示为w e b 文本模型的 形式。 ( 3 ) 编程实现基于文本挖掘的w e b 信息检索，包括w e b 文本聚类等处理。 ( 4 ) 将处理后的w e b 信息检索结果以便于用户理解与操作的形式展现出来。 1 4 2 工作特色与难点 本课题的特色在于在w e b 信息检索结果的基础上进行文本挖掘，通过搜索引擎 的前期处理，大大缩小了数据的规模，并使数据在一定程度上相对集中于某几个主 题，有利于针对挖掘对象的特点提出更加优化的算法。 4 华北电力大学硕士学位论文 本课题的难点在于针对w e b 文本模型的特点，选择并改进w e b 文本挖掘算法， 以及如何评价挖掘结果的质量。 1 5 预期成果和可能的创新点 ( 1 ) 能够对w e b 信息检索结果进行有效的文本挖掘，得到高质量的w e b 文本聚类。 ( 2 ) 有助于解决搜索引擎在准确率等方面存在的问题，提高w e b 信息检索的速度 与质量。 ( 3 ) 通过对该课题的研究与实现，对相关理论进行总结，发表1 - 2 篇论文。 5 华北电力大学硕士学位论文 2 1 概述 第二章w e b 信息检索原理 随着i n t e r n e t 的迅速发展，信息量以爆炸性的速度不断增长，i n t e r n e t 用户 在能够获取几乎无限量信息的同时，面临一个突出的问题：在以百万计的网站中， 如何快速有效地找到有用的信息? 搜索引擎( s e a r c he n g i n e ) 正是为解决用户的w e b 信息检索问题而出现的。它是i n t e r n e t 上的一个网站，该网站专门提供用户查询 i n t e r n e t 上的信息。当用户输入关键字查询时，该网站会向用户返回包含该关键字 信息的所有网址，并提供通向这些网站的链接。搜索引擎是w e b 信息检索的基本工 具。凡是通过获得网站页面资料建立数据库，并提供信息查询的系统，都可以称为 搜索引擎。 2 2 搜索引擎的产生与发展 从1 9 9 3 年起。一些站点为了方便用户浏览阅读，将手工收集到的站点信息写成 h t m l 文件，按一定的方式组织、分类成为目录式结构，这些结构被人们称为分类目 录。几乎是同时，另一批技术人员着手研究用计算机代替人工进行超链接的跟踪， 并记录下各站点的u r l 及摘要信息，利用它们建立起来的查询系统就被称为搜索引 擎。这两类系统在不断的发展中互相借鉴，这个阶段可以看作搜索引擎的雏形期。 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 y c o s 公司建立l y c o s 。1 9 9 4 年底y a h o o 公司创办，正式建立y a h o o 站点。1 9 9 5 年下半年e x c i t e 公司发布了e x c i t e 搜索引擎。这一时期的搜索引擎处于试运行期， 数据库容量较小，但是已经对i n t e r n e t 的发展起到了极大的促进作用，这一阶段 就是搜索引擎的基础建设期。 1 9 9 6 年进入搜索引擎的容量建设期，这时候的主流搜索引擎所引用的页面一般 都超过一千万。1 9 9 7 年竞争的焦点是制作高质量的索引，搜索引擎的发展处于质量 建设期，这一时期的代表是h o t n o t 。1 9 9 8 年之后，国外搜索引擎的发展进入了多 向型发展期“”。 中文搜索引擎的发展是从1 9 9 6 年开始，台湾的“番薯藤”中文搜索引擎于1 9 9 6 年2 月正式启动，是较早的中文搜索引擎。1 9 9 7 年5 月“悠游”公司在香港建立了 “悠游”中文搜索引擎。1 9 9 7 年5 月4 日y a h o o 发布了“雅虎”中文搜索弓l 擎。国 内的搜索引擎的建设是在1 9 9 7 年底及1 9 9 8 年初起步的，“网易”搜索引擎于1 9 9 7 6 华北电力大学硕士学位论文 年5 月开始建设，“北极星”中文站点信息检索系统于1 9 9 7 年1 2 月开通，1 9 9 8 年 5 月“搜狐”搜索引擎建立“。 2 3 搜索引擎的基本原理 2 。3 1 搜索引擎的结构 典型的搜索引擎主要由网页自动搜索( s p i d e r ) 模块、网页分析索引( i n d e x i n g ) 模块、网页检索查询( r a n k i n g ) 模块、用户接口( s e a r c he n g i n ei n t e r f a c e ) 模块等 四部分组成“”，如图2 。l 所示： 图2 1 搜索引擎的模块结构 ( 1 ) 网页自动搜索模块：在为用户提供信息检索服务之前，搜索引擎需要了解网 络上的资源，这需要搜索引擎有独立的网页搜索模块。网页自动搜索模块与用户检 索过程并行进行，负责在互联网上漫游，获取互联网上信息的信息，如新出现的网 址、网页，u r i 文件的摘要、关键字等，并将结果提供给系统。该部分通过运行一 些能够通过h t t p 等标准协议下载所漫游到的页面的软件，沿着w w w 上页面的各种 链接自动在网上漫游，不断获取信息，形成信息检索系统的原始数据库。搜索器的 实现常常用分布处理和并行计算技术，以提高信息发现和更新的速度。 ( 2 ) 网页分析索引模块：网页分析索引模块的功能是理解搜索器所搜索的信息， 从中抽取出索引项，对网络上的相关信息建立索引，主要是将搜集来的信息进行预 7 华北电力大学硕士学位论文 处理、分类、整理，建立索引数据库，用于表示文本以及生成文本集的索引表。目 前大部分搜索引擎建立索引的方式和传统的图书资料检索系统类似，但不同的系统 会在搜索结果的数量和质量上产生明显的不同。 ( 3 ) 网页检索查询模块：网页检索查询模块的功能是根据用户的查询要求在索引 库中快速检索出文本，进行文本与需求的相关度评价，对将要输出的结果进行排序， 并实现某种用户相关性反馈机制。常用的信息检索模型有集合理论模型、代数模型、 概率模型和混合模型等四种。 ( 4 ) 用户接口模块：用户接口是搜索引擎的终端程序，为用户提供浏览器界面下 的信息查询，是整个系统与用户交互的界面。用户接口的功能是获取用户需求、显 示查询结果、提供相关性反馈机制。用户接口的设计和实现使用人机交互( c o m p u t e r h u m a ni n t e r a c t i o n ) 的理论和方法，要充分适应人类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口面向普通非专业的 查询用户，一般只提供内容浏览和简单的输入框。复杂接口面向专业的查询用户， 可以让用户指定查询条件和查询限制，如逻辑运算( 与、或、非) 、相近关系( 相邻、 n e a r ) 、域名范围( 如e d u ，c o m ) 、出现位置( 标题、内容) 、信息时问等等。 组成搜索引擎的几个模块互相联系。网页自动搜索模块、网页分析索引模块属 于后台过程，是w e b 信息检索的前提与基础；网页检索查询模块和用户接口模块属 于前台过程，实现w e b 信息检索与人机交互。而系统的工作效率与性能是由四个模 块共同决定的。 2 3 2 搜索引擎的工作流程 搜索引擎的工作流程分为两个步骤：首先，建立i n t e r n e t 网页信息的全局索引 数据库；然后，根据用户的检索要求检索索引库返回检索结果1 6 1 8 1 。 ( 1 ) 建立索引数据库 网页自动搜索模块从一个事先制定好的网址列表出发，这个列表中的网址通常 是从以往访问记录中提取出来的，特别是一些热门网站，此外，很多搜索引擎还接 受用户提交的网址，这些网址也会被安排在列表中供网页自动搜索模块访问。网页 自动搜索模块访问一个网页后，对它进行分析，提取出新的网址，将之加入到访问 列表中，如此递归地访问i n t e r n e t 。网页自动搜索模块可以采用宽度优先或深度优 先策略来遍历整个i n t e r n e t 。 网页自动搜索模块提取的网页将被传递给网页分析索引模块中以建立索引数据 库。不同的搜索引擎会采取不同方式来建立索引，有的对整个h t m l 文件的所有单 8 华北电力大学硕士学位论文 词都建立索引。有的只分析h t m l 文件的标题或前几段内容，还有的能处理h t m l 文 件中的m e t a 标记或其它不可见的特殊标记。网页分析索引模块在建立索引时，一 般会给网页中每个关键词赋予一个等级值，表示该网页与关键词之间的符合程度。 当用户查询一个关键词时，检索软件将搜索索引数据库，找出所有与关键词相符合 的网页，有时候搜索到的网页可能有成千上万，等级值的用途就是作为一种排序的 依据。 不同的搜索引擎在计算等级值时使用了不同的方法，但它们都以关键词在网页 中出现的位置和频率为基本依据，例如，关键词出现在标题中的网页可能比只出现 在其它地方的网页更符合要求，关键词出现在网页的前面可能比只出现在网页的后 面更符合要求，同一个关键词出现多次的网页又可能比只出现一两次的网页更符合 要求，把这些因素综台起来考虑便可得出一个计算等级值的公式。不过，绝大多数 搜索引擎都没有只按照上述因素来确定计算公式，它们还加入了一些特殊考虑，例 如，g o o g l e 通过对网页的链接结构进行分析从而确定一个网页的等级值( 被更多的 高权威值的网页指向的网页同样具有高权威值) 。 ( 2 ) 检索并返回结果 检索并返回结果是搜索引擎根据用户检索需求表达式进行查找与输出结果的过 程。在用户系统提交查询时启动，它接受用户的查询，将之解析成一个个词组，然 后通过全文索引数据库找到含有这些词组的网页，采用某种算法( 例如根据网页中 关键词的匹配程度，出现的位置与频率，链接质量等) 计算出各网页的相关度及排 名等级，然后根据相关度由高到低把这些网页排序，最后返回这些网页u r l 地址的 列表。 2 3 3 现代搜索引擎技术 ( 1 ) 元搜索引擎 元搜索弓l 擎相当于多个独立搜索弓l 擎的集成，对用户提供一个统一的查询接口， 底层调用多个独立搜索引擎，并将多个搜索引擎的返回结果进行集成和处理再返回 给用户，如图2 2 所示1 9 埘1 州 ( 2 ) 信息检索a g e n t 搜索引擎、元搜索引擎等w e b 信息检索系统通常作为一种大型的服务器程序运 行，同时响应多个用户的请求。这些系统不能够根据用户的兴趣需求来定制检索结 果。信息检索a g e n t 提供了一种完全不同的w e b 信息检索模型，它具有以下特征： 9 华北电力大学硕士学位论文 第一，可适应性。信息检索a g e n t 能够从用户日常的检索、浏览等行为中学习 用户的兴趣，推理用户的需求，为用户提供个性化的服务。 第二，主动性。信息检索a g e n t 能够主动地根据用户的兴趣需求从w e b 上检索 相应信息，甚至能够监控信息源的变化，及时地报告给用户。这些工作的开展不需 要用户的参与，而由a g e n t 利用自身的控制机制、知识等进行任务规划、问题求解。 第三，协作性。信息检索a g e n t 之间可以共享和交流信息，实现协作式信息检 索。例如，一个用户的a g e n t 可以从具有相同兴趣需求用户的a g e n t 那儿获得很多 有用信息。 第四，移动性信息检索a g e n t 能够移动到远程服务器上，并在服务器上进行 信息检索，以避免将信息下载到客户端。在服务器上信息量很多，客户与服务器之 间没有持久、稳定的网络连接，或者客户机的处理能力不够时，移动a g e n t 十分有 用c 2 3 】。 图2 2 元搜索引擎的工作原理 ( 3 ) 面向特定主题的信息检索 面向主题的信息搜索其基本思想就是，利用一个聚焦搜索软件代理( f o c u s e d c r a w l i n g ) ，根据给定的主题内容要求说明，有选择地从互联网中搜索出与给定主 题相关的信息资源。与一般搜索引擎最大的不同就是，这种聚焦搜索方法，能够通 过分析所发现的网页链接来确定搜索的边界，使自己只在可能与所要求主题相关的 w e b 区域内进行搜索，从而避免了盲目搜索其它无关的互联网区域。显然这样不仅 可以大大降低信息搜索对硬件和网络资源的要求，而且也有助于提高信息更新的频 率。其中主题的定义描述是通过一连串实例文本来加以说明的扭研。 ( 4 ) 检索结果的联机聚类 尽管搜索引擎采用了各种方法来提高检索结果的精度，但是结果中仍然包含了 与用户查询请求不相关的文本，其比例高达7 5 以上。此外，搜索引擎返回给用户 的通常是一个线性的文本列表，虽然经过了相关度排序，但是相关文本和不相关文 1 0 华北电力大学硕士学位论文 本仍然混杂于其中。用户必须逐个地浏览以找到相关文本，花费了大量的精力。当 返回的结果数目众多时，这个问题更为突出。为了方便用户的浏览，一些研究人员 开始将聚类技术用于w e b 信息检索结果的可视化输出。h e a r s t 等人的研究己经证明 了聚类假设，即与用户查询相关的文本通常会聚集得比较靠近，而远离与用户查询 不相关的文本。可以利用聚类技术将搜索引擎的检索结果集合划分为若干个集合， 这样用户只需要考虑那些相关的集合，大大缩小了所需浏览的结果数量嘶m ”。 2 4 搜索引擎的评价指标 克里维顿( c m c l e v e r d o n ) 首次提出评价信息检索系统效率与精度的重要指标 召回率和准确率嘲。召回率和准确率的定义如下： 召回率：害襄譬霎譬望霎氅 ( 2 1 ) 系统中的相关记录篇数 “ 准确率= 蒜鬻燃 亿z ， 目前，研究人员进行研究，得出准确率和召回率之间的五种关系： ( 1 ) 召回率与准确率都保持不变； ( 2 ) 召回率保持不变，准确率增大或减小； ( 3 ) 准确率保持不变，召回率增大或减小： ( 4 ) 召回率与准确率之间呈互逆关系； ( 5 ) 召回率与准确率之间呈互顺关系等等。 搜索引擎的其它评价指标包括响应时间、检索结果的有效性、易用性等。高质 量的搜索引擎应该具有较短的响应时间以及较高的召回率和准确率。 2 5 搜索引擎的现状 2 5 1 国外搜索引擎现状 在国外，搜索引擎已有比较成熟的实用产品，并应用于许多著名的w e b 站点， 比如a l t a v i s t a 、i n f o s e e k 、e x c i t e 、y a h o o 等。主要特点包括： ( 1 ) 在搜索引擎上同时支持目录导航和页面全文搜索； ( 2 ) r o b o t 向智能化和自动化方向发展，不需入工干预，有选择地收集有用信息 自动分类，周期性自动更新； 华北电力大学硕士学位论文 ( 3 ) 支持海量数据管理，提供快速检索； ( 4 ) 提供查询的自然语言接口； ( 5 ) 对检索结果提供相关性排序输出，并可对检索结果作优化处理； ( 6 ) 支持相似性检索。 国外搜索引擎也存在一些缺点，需要不断完善。除了在自然语言接口、相关排 序、结果优化等方面需要继续完善以外，还体现在对搜索引擎缺乏标准和有效的评 估方法，包括： ( 1 ) 由于i n t e r n e t 上信息的数量极大，搜索引擎只能提供其中一部分站点的信 息搜索； ( 2 ) 每种搜索引擎有各自的信息收集方式和范围，互不相同； ( 3 ) 每种搜索引擎有各自的检索算法和结果排序方法，互不相同； ( 4 ) 相同的检索条件在不同的搜索引擎上可能得到互不相同的结果。 2 。5 。2 中文搜索引擎现状 1 9 9 7 年国内开始发展面向中文信息检索的中文搜索引擎“盯啪，目前在一些领域 和条件方面已经得到很大的发展，并建立起若干著名的中文搜索引擎，主要包括： ( 1 ) 搜狐( h t t p ：w w w s o h u c o m c n ) ：它是以提供分类目录为主的中文搜索引 擎，其分类原则是以图书分类为基础，与日常应用习惯相结合，由编辑人员分类， 因而分类质量较高，但更新速度慢，查全率较低。 ( 2 ) 新浪( h t t p ：w w w s i n a c o r n c n ) l “新浪”是最大的中文门户网站，收录了 全球资讯逾万的中文网址，并分成娱乐休闲、商业经济、社会科学、教育就业、社 会文化、参考资料、政法军事、体育健身、科学技术、新闻媒体、文学艺术、电脑 网络、医疗健康、生活服务、参考资料、国家地域等1 5 大类，其下分多个小类； 并提供了中文关键词的搜索功能。 ( 3 ) 百度( h t t p ：w w w b a i d u c o r n ) ：采用了基于超链分析的方法进行相关度评 价，能够客观分析网页所包含的信息，提高了检索结果相关性。为用户提供“网页 快照”功能，在快照中对用户的查询字符串用不同颜色在网页中标记，方便了用户 的查询。 ( 4 ) 天网( h t t p ：e p k u e d u c n ) ：“天网”是网页资源索引的查找服务系统， 是c e r n e t “九五”攻关项目的一部分，信息来源是国内c e r n e t ，c h i n a n e t ，c a s n e t 。 华北电力大学硕士学位论文 g b n e t 四大网络，采用r o b o t s 自动发现和收集信息。该系统有中、英文两个界面， 可进行中英文关键词的检索，支持复杂查询，检索速度快，反馈信息丰富，包括网 址、摘要、最后修改时间、长度、相关度、编码类型等。 目前国内的中文搜索引擎与国外优秀的搜索引擎还有一定的差距。相对于国外， 中文搜索引擎的发展尚处起步和发展阶段，仍存在以下不足： ( 1 ) 搜索引擎对自然语言提问没有理解能力。目前大多数搜索引擎只提供分 类浏览查询方式和关键词全文检索查询方式，不支持自然语言理解； ( 2 ) 网络信息不断更新与搜索引擎相对不变之闯的矛盾啪1 。i n t e r n e t 上的信息 源是动态变化的，搜索引擎无法做出调整，使用户及时得到有关信息； ( 3 ) 没有用户兴趣反馈服务m 1 没有个性化服务，对用户一贯查询的信息进行 重复查找，也不能对用户的意见进行跟踪，获取用户对查询结果的评价，以便为以 后的查询做预先分析； ( 4 ) 收集范围有限o ”i n t e r n e t 上信息资源具有分散、多结构、多服务类型的 特点，搜索引擎很难收集到全部信息，一般只能收集很少的一部分； ( 5 ) 用户和检索系统的交互方式比较单调。现有系统普遍采用相关反馈技术作 为用户和系统进行交互的主要手段，但这种反馈相当简单，只停留在用户满意、不 满意、一般这一层，并没有进行推理或机器学习。 华北电力大学硕士学位论文 3 1w e b 挖掘 3 1 1w e b 挖掘概述 第三章w e b 文本挖掘技术 随着计算机技术与管理信息系统( m i s ) 的发展，数据库与数据库管理系统在各行 各业的应用越来越普及，逐渐产生并存储了不计其数的数据。面对不计其数的数据， 从中查找所需数据变得愈加困难。为了解决这一难题，数据挖掘技术应运而生。数 据挖掘在大量数据的基础上，对数据进行分析处理，揭示出隐藏于数据背后的规律。 i n t e r n e t 是一个巨大的数据资源仓库，可以从中获取几乎无限量的数据。 i n t e r n e t 用户的迅速增加，电子商务两站的蓬勃发展，更加剧了i n t e r n e t 上数据 的增长。为了解决从如此大量的数据中找到有用数据的难题，数据挖掘与i n t e r n e t 技术相结合，产生了w e b 挖掘。 w e b 挖掘就是以啊w 上的数据为分析对象，以抽取有用知识为目标，把传统数 据挖掘技术和万维网相结合的研究。使用的技术和工具涉及到人工智能、机器学习、 数据库、统计学、信息检索、可视化、自然语言理解等相关领域。 3 。1 。2w e b 挖掘分类 根据所分析数据对象的不同，w e b 挖掘研究可以分为不同的类型，包括w e b 内 容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使用 挖掘( w e bu s a g em i n i n g ) ，挖掘的数据对象分别是w e b 上的内容数据、结构数据 和使用数据。 ( 1 ) w e b 内容挖掘 w e b 内容挖掘是从w e b 数据中抽取知识，以实现w e b 资源的自动检索，提高w e b 数据的利用效率。随着i n t e r n e t 的进一步延伸，w e b 数据越来越庞大，种类越来越 繁多，数据的形式既有文本数据信息，也有图像、声音、视频等多媒体数据信息， 既有来自于数据库的结构化数据，也有用h t m l 标记的半结构化数据及非结构化的 自由文本数据信息。因而，对w e b 内容信息挖掘主要从下面两个角度进行瞰1 。 一是从信息检索的角度，主要研究如何处理文本格式和超级链接文本，这些数 据是非结构化或半结构化的。处理非结构化数据时，一般采用词集方法，用一组词 条来表示非结构化的文本，先用信息评价技术对文本进行预处理，然后采取相应的 1 4 华北电力大学硕士学位论文 模型进行表示。另外，还可以用最大字序列长度、划分段落、概念分类、机器学习 和自然语言统计等方法来表示文本。处理半结构化数据时，可以利用一些相关算法 给超级链接分类，寻求w e b 页面关系，抽取规则。同处理非结构化数据相比，由于 半结构化数据增加了h t m l 标记信息及w e b 文本内部超链结构，使得表示半结构化 数据的方法更加丰富。 二是从数据库的角度，主要处理结构化的w e b 数据库，也就是超级链接文本， 数据多采用带权图或者对象嵌入模型( o m e ) ，或者关系数据库表示，应用一定的算 法，寻找出网站页面之间的内在联系，其主要目的是推导出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 上的查询语言来实现建立并维护w e b 站点的途径口”。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘的对象是w e b 本身的超链接，即对w e b 文本的结构进行挖掘。对 于给定的w e b 文本集合，应该能够通过算法发现他们之间连接情况的有用信息，文 本之间的超链接反映了文本之间的包含、引用或者从属关系，引用文本对被引用文 本的说明往往更客观、更概括、更准确。 w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之间的 关系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同一网站内部以 及不同网站之间的链接关系。在w e b 结构挖掘领域最著名的算法是h i t s m l 算法和 p a g e r a n k 。7 1 算法。他们的共同点是使用一定方法计算w e b 页面之间超链接的质量， 从而得到页面的权重。著名的c l e v e r 和g o o g l e 搜索引擎就采用了该类算法。 此外，w e b 结构挖掘另一个尝试是在w e b 数据仓库环境下的挖掘，包括通过检 查同一台服务器上的本地链接衡量w e b 结构挖掘w e b 站点的完全性，在不同的w e b 数据仓库中检查副本以帮助定位镜像站点，通过发现针对某一特定领域超链接的层 次属性去探索信息流动如何影响w e b 站点的设计。 ( 3 ) w e b 使用挖掘 w e b 使用挖掘也称为w e b 日志挖掘( w e bl o gm i n i n g ) ，研究的对象是w e b 日志 数据，有些挖掘任务也结合用户的简档数据。w e b 使用挖掘的目的是通过挖掘w e b 日志记录，来发现用户访问w e b 页面的模式、识别电子商务的潜在客产、提高w e b 上服务信息发布的质量、改进w e b 服务器的系统性能、入侵检测、改进w e b 站点设 华北电力大学硕士学位论文 计和帮助提高个性化搜索的性能等。w e b 使用挖掘研究面临的主要难题包括上网代 理和动态i p 技术导致的用户识另i j ，页面缓存导致的w e b 日志记录不全以及w e b 页 面内容的动态更新等。 3 1 3w e b 挖掘的常用方法 ( 1 ) 路径分析技术 网站上的页面定义成节点，页面之间的超级链接定义成图中的边，这样形成网 站结构图。从图中确定最频繁的访问路径。 ( 2 ) 关联挖掘技术 挖掘出用户在一个访问期间从服务器上访问的页面或文件之间的联系。最常用 的技术是用a p r i o r 算法，从事务数据库中挖掘出最大频繁访问项集，这个项集就 是关联规则挖掘出来的用户访问模式。 ( 3 ) 序列模式挖掘技术 挖掘出交易集之间有时间序列关系的模式。它与关联挖掘技术都是从用户访问 留下的日志中寻找用户普遍访问的规律，关联挖掘技术更注重事务内的关系，序列 模式技术则注重事务间的关系 ( 4 ) 分类技术 主要是根据用户群的特征，寻找用户群的访问特征。 ( 5 ) 聚类技术 则是对符合某一访问规律特征的用户进行用户特征挖掘。最后进行模式分析， 挖掘出的模式解释为人们可理解的知识。 3 2w e b 文本挖掘 3 2 1w e b 文本挖掘的定义 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息检 索技术，从文本数据中发现和提取独立于用户信息需求的文本集中的隐含知识啪) 。 文本挖掘是近几年来数据挖掘领域的一个新兴分支，其基本思想是：首先利用文本 切分技术，抽取文本特征。将文本数据转化为能描述文本内容的结构化数据，然后 利用聚类、分类技术和关联分析等数据挖掘技术，形成结构化文本树，并根据该结 构发现新的概念和获取相应的关系 1 6 华北电力大学硕士学位论文 w e b 文本挖掘是从w e b 文本和w e b 活动中发现、抽取感兴趣的潜在的有用模式 和隐藏的信息的过程o 。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 内容的，也可能是关于w e b 结构的。由于w e b 文本是一个半结构化或无结 构化的，且缺乏机器所能理解的语义，从而使有些数据挖掘技术并不适用子w e b 挖 掘。因而，开发新的w e b 文本挖掘技术以及对w e b 文本进行预处理，以提取该文本 的特征，便成为w e b 文本挖掘研究的重点。 3 2 2w e b 文本挖掘的作用 w e b 文本挖掘对我们充分利用w w w 资源很有帮助，可以使用户比较准确找到需 要的资料，可以帮助用户节约检索时间，可以提高w e b 文本的利用价值等。 ( 1 ) 可以对搜索结果进行有效的组织 搜索引擎的搜索结果并不尽如人意，使用者输入一些关键词，一般都会得到成 千上万的检索结果，而且其中大部分页面都是不需要的无关资料。虽然有一些技巧 试图给那些有较多关键词或者罕见关键词的页面赋予更大的权重，却仍