（计算机应用技术专业论文）web文档聚类在搜索引擎中的应用研究.pdf

江 苏 大 学 硕士 学位论 文 摘要 随着互联网上数据量爆炸式的增长，搜索引擎技术得到广泛的研 究，并且出现了一批非常优秀的搜索引擎。但是，现有的搜索引擎只 是将返回结果简单地进行线性排列，用户想要的信息可能被淹没在庞 大的返回结果列表中，给用户带来极大的不便。 本文致力于将搜索引擎返回结果进行聚类，把搜索引擎返回的结 果组织成具有层次的类结构，同一类中的文档之间的相似度尽可能的 大，不同类中的文档之间的相似度尽可能的小，并给每个类赋予一个 具有良好描述性的标签，从而便于用户浏览，缩短用户查找自己所需 信息的时间。 通过对当前主流聚类算法的研究，设计了一种基于s t c 算法的改 进算法s t c i 。s t c i 算法的提出是因为s t c 算法有两个缺点特征 空间维数过高和未考虑查询关键字与文档的相关度。针对s t c 的这两 个缺点，s t c i 算法通过剔除同义词、近义词来给文档降维，从而降低 算法的时间复杂度。计算文档对于查询的相关度，不让与查询相关度 较低的文档参与聚类，从而提高聚类的准确率。实验数据表明改进后 的算法在时间复杂度和聚类的准确性方面较原算法有较大的改善。 考虑到日常生活中人们将文档分类的主要参考因素是文档的主 题，设计了一种基于主题的聚类方法一h t b c 。h t b c 首先根据文档 的标题和正文提取文档的主题词向量，然后通过训练文本集生成词类， 将每个主题词向量归类到其应属的词类，将同属于一个词类的主题词 i 江 苏 大 学 硕士 学 位论文 向量对应的文档归并到用对应词类的名字代表的类，从而达到聚类的 目的。h t b c 共分四个步骤：预处理、建立主题向量、生成词类和主 题聚类。实验表明h t b c 在准确率和召回率方面较k m e a n s 、a h c 、 s t c 这几个常用聚类算法要好。 最后，在上述研究的基础上设计了一个带聚类模块的搜索引擎系 统，该系统主要包括搜集器、索引器、检索器和聚类模块四个部分， 聚类模块采用了h t b c 算法。通过分析系统运行情况，证明了该系统 设计的合理性。 关键词：文本聚类，搜索引擎，后缀树，互信息，主题 i i 江 苏 大 学 硕士 学位论 文 a b s t r a c t w i t ht h ee x p l o s i v ei n c r e a s eo fi n t e r n e td a t a ，s e a r c he n g i n et e c h n o l o g y h a sb e e nw i d e l yr e s e a r c h e d ，a n dan u m b e ro fe x c e l l e n ts e a r c he n g i n e sa r e e m e r g e d h o w e v e r , t h ec u r r e n ts e a r c he n g i n e so n l ya r r a n g eas i m p l eli n e a r a r r a yf o rt h er e t u r n e ds e a r c h e dr e s u l t s t h ei n f o r m a t i o nw h i c hu s e r sr e a l l y w a n tm a yb es u b m e r g e di nah u g er e t u r n e dl i s to fr e s u l t s ，b r i n g i n gg r e a t i n c o n v e n i e n c et ou s e r s t h i sp a p e ri sc o m m i t t e dt oc l u s t e rt h er e s u l t sr e t u r n e df r o mt h es e a r c h e n g i n e ，a n d t h er e s u l t sa r eo r g a n i z e dt ot h e h i e r a r c h ys t r u c t u r e t h e s i m i l a r i t yb e t w e e nt h ed o c u m e n t so ft h ed i f f e r e n tc l u s t e ri sa ss m a l la s p o s s i b l e e a c hc l u s t e ri sl a b e l e da sag o o dd e s c r i p t i o ni no r d e rt of a c i l i t a t e u s e r st ob r o w s ea n dr e d u c et h et i m ef o ru s e r st of i n dt h er e s u l t s t h r o u g ht h er e s e a r c h o nt h ec u r r e n tm a i nc l u s t e r i n ga l g o r i t h m ，a n i m p r o v e da l g o r i t h ms t c - ib a s e do na l g o r i t h ms t c h a sb e e nd e v i s e d t h e a l g o r i t h ms t c - ii si n t r o d u c e dt oc o n q u e rt h et w of l a w so fa l g o r i t h ms t c ， w h i c ha r et e r ms p a c ed i m e n s i o ni st o oh i g ha n dt h ec o r r e l a t i o nb e t w e e n k e y w o r dq u e r ya n dd o c u m e n ta r en o tc a l c u l a t e d ，r e s p e c t i v e l y s t c i a l g o r i t h mr e m o v e ds y n o n y m s ，n e a r - s y n o n y mt or e d u c ed i m e n s i o n a l i t yo f t h ed o c u m e n ts e t ，t h u sr e d u c i n go ft h ea l g o r i t h m c a l c u l a t i n go fd o c u m e n t s r e l e v a n ta n dn o tc l u s t e r i n gw i t ht h el o w e rc o r r e l a t i o ni st oe n h a n c et h e c l u s t e r i n g t h ee x p e r i m e n tp r o v e st h i sa l g o r i t h mi si m p r o v e dl a r g e l yb o t h i l l 江 苏大 学 硕 士 学 位论文 i nt i m ec o m p l e x i t ya n dt h ec l u s t e r i n ga c c u r a c y f o rt h em a i nr e f e r e n c ef a c t o rf o r c l a s s if y i n gt h ed o c u m e n t si st h e t h e s i so fd o c u m e n t s ，ac l u s t e r i n gm e t h o d h t b ci sd e v i s e d i te x t r a c t s t h ek e y w o r d sa c c o r d i n gt ot h et i t l ea n dt h eb o d yo ft h ed o c u m e n t ，t r a i n st h e t e x ts e t st og e n e r a t et h ew o r dc l u s t e r i n g ，c l a s s i f i e se a c hk e y w o r dt os o m e w o r dc l u s t e r , c o m b i n e st h es a m et h e s i sa t t r i b u t et ow o r dc l u s t e ra n df i n a l l y r e a l i z e sc l u s t e r i n g t h e r ea r ef o u rs t e p sf o rh t b cs u c ha sp r e t r e a t m e n t ， c o n s t r u c t i n gt h et h e m ev e c t o r , g e n e r a t i n g t h ew o r dc l u s t e ra n dt h e m e c l u s t e r i n g t h ee x p e r i m e n t a l d a t a r e p r e s e n t s h t b ca r eb e t t e rt h a n k m e a n s ，a h ca n ds t ci nt e r m so fa c c u r a c ya n dr e c a l lr a t i o f i n a l l y , s e a r c he n g i n es y s t e mw i t hac l u s t e r i n gm o d u l ei sd e v e l o p e d b a s e do nt h ea b o v er e s e a r c h t h es y s t e mi n c l u d e sw e bc r a w l e r s ，i n d e x s y s t e ma n dr e t r i e v a ls y s t e mw i t h ac l u s t e r i n gm o d u l ei nw h i c ht h e a l g o r i t h mh t b ci sa p p l i e d t h r o u g ht h ea n a l y s i so ft h es y s t e mo p e r a t i n g ， t h ed e s i g no fs y s t e mi sp r o v e dt ob er e a s o n a b l e k e yw o r d s ：d o c u m e n tc l u s t e r i n g ，s e a r c h e n g i n e ，s t c ，m u t u a l i n f o r m a t i o n ，t h e m e 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的 规定，同意学校保留并向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅。本人授权江苏大学可以 将本学位论文的全部内容或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 学位论文作者签名 刁年占月f 指导教师签名：撇 叫年6 只协 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究工作所取得的成果。除文中已注明引用的内 容以外，本论文不包含任何其他个人或集体已经发表或撰写过 的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 学位论文作者签名： 日期：川年乡月 江苏大学硕士学位论文 1 1 论文选题的意义 1 1 1 研究背景 第1 章绪论 随着全球网络化、信息化的高速发展，网络已经成为全球最大的资料库，w e b 已经成为人们获取信息的重要手段。w e b 上的数据正以每天新增数百万张页面的 速度增长，页面数目已超过l 万亿张。以下数据从不同角度反映了当前w e b 的规 模： ( 1 ) 来自互联网名字与编号管理机构( i c a n n ) 罗马会议的一份全球域名产业 报告显示，截至2 0 0 8 年2 月底，我国c n 域名注册量已突破1 0 0 0 万大关，注册规 模直逼德国d e 域名，成功晋级全球千万级域名之列【l j 。 ( 2 ) 2 0 0 9 年7 月，中国互联网络信息中心( c n n i c ) 在北京发布了第二十三次 中国互联网络发展状况统计报告，报告显示1 2 j 截止到2 0 0 8 年底，全国域名数为 1 6 ，8 2 6 ，1 9 8 个，网站个数为2 8 7 8 万个，网页超过1 6 0 亿张。 ( 3 ) 目前，全球最大的搜索引擎g o o g l e 的官方网站称他们目前索引的网页数 量已经达l 万亿张p j 。 如何从如此庞大的w e b 数据海洋中找到有价值的信息，并从中提取出知识内 容已经成为目前信息检索、数据挖掘和知识管理等研究领域的重要课题。 1 1 2 搜索引擎面临的问题 尽管搜索引擎已成为互联网用户浏览w e b 信息的主要手段，但互联网用户对 现有的搜索引擎的满意程度并不乐观。搜索引擎的主要缺陷表现在： ( 1 ) 查准率低。多数搜索弓l 擎的检索功能单一，信息加工深度不够，这导致 信息查询的查准率不高。并且其数据库多为非全文数据库，不能提供原文，复杂 高级的精确检索方式明显不足，不易于处理多次检索和限定词检索。按分类目录 浏览常常检索到很多无关的信息。 ( 2 ) 检索效率不高。主要问题是数据更新速度慢，查询响应时间长。由于网 络资源的爆炸式增长和互联网用户需求的日益增加，多数搜索引擎的日处理检索 请求量很可能是上亿的。如何处理如此繁重的任务并提高处理效率，是目前搜索 引擎必须要考虑的问题。 江苏大学硕士学位论文 ( 3 ) 语义性差。目前的搜索引擎只能支持关键词的查询方式，通过这种方式 来猜测用户要查询什么并不能充分理解用户的需求，只有自然语言的查询才能满 足用户的需求和兴趣。 ( 4 ) 信息过量。返回太多的无关内容。若干个关键词构成的一个查询组合可 能返回上万个相关页面链接，很多检索结果和用户查询毫无关系，而且返回的信 息很少具有个性化的相关度排序，用户最满意的信息并不是最先呈现给用户。研 究指出，大概有7 5 搜索结果可能是和查询条件无关的。 ( 5 ) 返回结果组织不够。目前绝大多数搜索引擎只是简单地按网页重要性将 返回结果排序，然后呈现给用户。但是这种排序只是局限于考虑网页和搜索关键 词的相关度和网页被其它网页“引用 的次数，即所谓的重要性。但用户的感兴 趣网页可能不在搜索引擎认为重要的网页范围内，因此对结果的组织也是目前搜 索引擎应该考虑的问题。 1 1 3 国内外研究现状 因为搜索引擎用户数量巨大，具有较好的经济价值，又因为搜索引擎综合研 究性强，其研究涉及到计算机网络、人工智能、信息论、数据挖掘、分布式处理、 w e b 挖掘、数据库等多门学科，所以近年来搜索引擎得到广泛的研究。当前国内外 的研究热点主要有以下几个方面： ( 1 ) 对用户查询的理解 目前的搜索引擎还是基于关键词查询的，但是关键词并不能很好地表达用户 真正的需要，因此目前自然语言处理是信息检索研究的一个重点。 ( 2 ) 索引数据库的组织和管理 由于w e b 海量的数据，所以搜索引擎的索引数据库非常庞大，如何对这些大 容量、非结构化的信息进行组织和管理也是当前研究的一个热点问题。 ( 3 ) 检索结果的排序 将检索结果进行重要性排序一直是搜索引擎研究的一个重要课题，其中一个 值得关注的成果就是g o o g l e 的p a g e r a n k 算法。 ( 4 ) w 曲信息挖掘 w e b 是信息的海洋，如何在如此庞大的信息库中挖掘知识，找出关联是值得 研究的问题。当前搜索引擎研究的一个主要问题就是如何对信息进行准确的分类， 对检索结果进行自动分类以便用户查找。 江苏大学硕士学位论文 1 2 搜索引擎简介 1 2 1 搜索引擎发展史 早在w e b 出现之前，互联网上就已经存在许多旨在让人们共享的信息资源了。 这些资源当时主要存在于各种允许匿名访问的f t p 站点( a n o n y m o u sf t p ) ，它们以 计算机文件的形式存在，文字材料的编码通常是p o s t s c r i p t 或者纯文本( 那时还没 有h t m l ) 。 为了便于人们在分散的f t p 资源中找到所需的东西，1 9 9 0 年加拿大麦吉尔大 学( u n i v e r s i t yo f m c g i l l ) 计算机学院的师生开发了一个软件a r c h i e 。它通过定 期搜集并分析f t p 系统中存在的文件名信息，提供查找分布在各个f t p 主机中文 件的服务。a r c h i e 能在只知道文件名的前提下，为用户找到这个文件所在的f t p 服务器的地址。a r c h i e 实际上是一个大型的数据库，再加上与这个大型数据库相 关联的一套检索方法。该数据库中包括大量可通过f t p 下载的文件资源的有关信 息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。尽 管所提供服务的信息资源对象( 非h t m l 文件) 和本文所讨论搜索引擎的信息资源 对象( h t m l 网页) 不一样，但基本工作方式是相同的( 自动搜集分布在广域网上的 信息，建立索引，提供检索服务) ，因此人们公认a r c h i e 为现代搜索引擎的鼻祖。 以w e b 网页为对象的搜索引擎和以f t p 文件为对象的检索系统的一个基本的 不同点在于搜集信息的过程。前者是利用h t m l 文档之间的链接关系，在w e b 上 一个网页一个网页的“爬取 ( c r a w l ) ，将那些网页“抓”( f e t c h ) 到本地后进行分 析。后者则是根据已有的关于f t p 站点地址的知识( 例如得到了一个站点地址列 表) ，对那些站点进行访问，获得其文件目录信息，并不真正将那些文件下载到系 统上来。因此，如何在w e b 上“爬取 ，就是搜索引擎要解决的一个基本问题。在 这方面，19 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r ，它是世晃上第一 个利用h t m l 网页之间的链接关系来监测w e b 发展规模的“机器人 ( r o b o t ) 程序。 刚开始时它只用来统计互联网上的服务器数量，后来则发展为能够通过检索网站 域名。鉴于其在w e b 上沿超链接“爬行”的工作方式，这种程序有时候也称为“蜘 蛛 ( s p i d e r ) 。因此，在文献中c r a w l e r ，s p i d e r ，r o b o t 一般都指的是相同的事物， 即在w e b 上依照网页之间的超链接关系一个个抓取网页的程序，通常也称为“搜 集 。在搜索引擎系统中，也称为网页搜集子系统。 现代搜索引擎的思路源于w a n d e r e r ，不少人在m a t t h e wg r e y 工作的基础上对 它的蜘蛛程序做了改进。1 9 9 4 年7 月，m i c h a e lm a u l d i n 将j o h nl e a v i t t 的蜘蛛程序 接入到其索引程序中，创建了大家现在熟知的l y c o s ，成为第一个现代意义的搜索 江苏大学硕士学位论文 引擎。在那之后，随着w e b 上信息的爆炸性增长，搜索引擎的应用价值也越来越 高，不断有更新、更强的搜索引擎系统推出。这其中，特别引人注目的是 g o o g l e ( h t t p ：w w w g o o g l e c o m ) ，虽然它1 9 9 8 年才推出，但由于其采用了独特的 p a g e r a n k 技术，使它很快后来居上，成为当前全球最受欢迎的搜索引擎。 互联网上信息量在不断增加，信息的种类也在不断增加。例如除了我们前面 提到的网页和文件，还有新闻组、论坛、专业数据库等。同时上网的人数也在不 断增加，网民的成分也在发生变化。一个搜索引擎要通过覆盖所有的网上信息而 查找需求已经出现困难，因此各种主题搜索引擎、个性化搜索引擎、问答式搜索 引擎等纷纷兴起。这些搜索引擎虽然还没有实现如通用搜索引擎那样的大规模应 用，但随着互联网的发展，我们相信它们的生命力会越来越旺盛。另外，即使通 用搜索引擎的运行现在也开始出现分工协作，有了专业的搜索引擎技术和搜索数 据库服务提供商。例如美国的i n k t o m i ，它本身并不是直接面向用户的搜索引擎， 但向包括o v e r t u r e ( 原g o t o ) 、l o o k s m a r t 、m s n 、h o t b o t 等在内的其他搜索引擎提 供全文网页搜集服务。从这个意义上说，它是搜索引擎数据的来源。 搜索引擎出现虽然只有1 0 年左右的历史，但在w e b 上已经有了确定不移的地 位。据c n n i c 统计，它已经成为继电子邮件之后的第二大w e b 应用。虽然它的基 本工作原理已经相当稳定，但在其质量、性能和服务方式等方面的提高空间依然 很大，研究成果层出不穷，是每年w w w 学术年会的重要论题之一。下面介绍当 前一些主流的搜索引擎。 g o o g l e ( h t t p ：w w w g o o g l e c o m ) 。四次荣获s e a r c he n g i n ew a t c h 读者选举出的 “最杰出搜索引擎”称号的g o o g l e 作为在网络上搜索页面的首选是无愧于这个称 号的。它基于搜集器的服务既保证了能够覆盖广泛的网页，同时在查询效果上也 表现得极其优秀。 a l l t h e w e b ( h t t p ：w w w a l l t h e w e b c o m ) 。a l l t h e w 曲作为一个优秀的基于搜集 器的搜索引擎，a l l t h e w e b 提供广泛的网络覆盖与显著的相关性。除了提供网页查 询，a l l t h e w e b 还提供新闻、图像、视频和音频的检索。a l l t h e w e b 于1 9 9 9 年5 月推出，先是由f a s t 运作；2 0 0 3 年4 月o v e r t u r e 收购了a l l t h e w 如；后来y a h o o 买下了o v e r t u r e ，现在的a l l t h e w 曲由y a h o o 运作。 a s kj e e v e s ( h t t p ：w w w a s k c o m ) 。a s kj e e v e s 最初获得名声是在1 9 9 8 和1 9 9 9 年。作为自然语言搜索引擎，能够让用户通过输入问题来得到查询结果，并且所 得到的结果看起来好像是对的。 h o t b o t ( h t t p ：w w w h o t b o t c o m ) 。h o t b o t 提供便于访问三个搜索引擎( h o t b o t ， g o o g l e ，a s kj e e v e s ) 的入口，但是不同于元搜索引擎的是，它不能将各个搜索引擎 江苏大学硕士学位论文 的返回结果综合显示。 t e o m a ( h t t p ：w w w t e o m a c o m ) 。t e o m a 是基于搜集器的搜索引擎，2 0 0 1 年9 月被a s kj e e v e s 收购。它索引的网页比同样基于搜集器的竞争对手g o o g l e 索引的 网页要少，然而对于通常的查询检索，索引网页的数量并不会产生很大的分别。 自从2 0 0 0 年t e o m a 出现，就因为它很好的网页相关性为它赢得了称赞。一些人喜 欢t e o m a 的“相关检索”特性，比如，您先输入一个简单词语搜索，然后t e o m a 会为您提供其他相关搜索词作为参考。“专家推荐资源”部分也是t e o m a 的一个特 色，指导用户去访问不同主题的链接。 l y c o s ( h t t p ：w w w l y c o s c o m ) 。l y c o s 是一个资格最老的搜索引擎，1 9 9 4 年开 始服务。在1 9 9 9 年4 月它停止了自己基于搜集器的工作方式，取而代之的是利用 l o o k s m a r t 人工整理的常用查询分类结果和其他基于搜集器的搜索引擎，如： y a h o o ，i n k t o m i 等搜集器提供的结果。在搜索框的下方l y c o s 会建议其他的与用户 检索主题相关的查询词，也许正是用户想要的和感觉更确切的查询词。在这之下， 就是l y c o s 提供的与其他搜索引擎一样的既相关又广泛覆盖的结果。 w i s e n u t ( h t t p ：w w w w i s e n u t t o m ) 。与t e o m a 类似，w i s e n u t 也是基于搜集器 的搜索引擎，在2 0 0 1 年出现的时候吸引了大家的注意力。w i s e n u t 的结果也有很 好的相关性，并且有很大的数据库，几乎像g o o g l e 、a l l t h e w e b 和i n k t o m i 一样大。 然而，w i s e n u t 的数据库更新很慢，查询结果经常是几个月前的内容。l o o k s m a r t 在2 0 0 2 年4 月并购了w i s e n u t 。最初它叫t o t 0 ，2 0 0 1 年更名为o v e r t u r e 。o v e r t u r e 是一个非常流行的竞价排名搜索引擎，它提供广告给许多搜索引擎排在检索结果 的上方。o v e r t u r e 在2 0 0 3 年3 月购买了a 1 1 t h e w e b ，2 0 0 3 年4 月又收购了a l t a v i s t a 。 y a h o o 在2 0 0 3 年1 0 月购买了o v e r t u r e 。 v i v i s i m o ( h t t p ：w w w v i v i s i m o t o m ) 。v i v i s i m o 于2 0 0 0 年6 月由卡耐基梅隆大 学( c m u ) 推出，作为不同于基于搜集器的元搜索引擎，有自己的独到之处。它把 其他搜索引擎的返回结果利用自动聚类的办法来满足不同类型客户的需要。在搜 索引擎上，任何人搜索同一个词的结果都是一样。这样明显不能满足访问者。科 学家搜索“星球”，可能是希望了解星球的知识，但普通人可能是想找“星球大战 电影，但搜索引擎所给的都是一样的结果。如何满足这些不同类型的访问者，需 要对搜索结果进行个性化处理。搜索结果排序从单一化到个性化，v i v i s i m o 已经迈 出了一步。 b a i d u ( h t t p ：w w w b a i d u c o m ) 。百度于2 0 0 0 年推出，是目前在中国最成功的一 个商业搜索引擎，主要提供中文信息检索，并且为门户站点提供搜索结果服务。 搜索范围涵盖了中国内地、香港、台湾、澳门、新加坡等华语地区以及北美、欧 江苏大学硕士学位论文 洲的部分站点。拥有的中文信息总量达到1 亿2 千万张网页以上，并且还在以每 天几十万页的速度快速增长。 1 2 2 搜索引擎分类 据统计，各种各样的网络信息搜索工具已经有上千种。从不同的角度，其分 类也各不相同。搜索引擎按其工作方式可以分为以下三类： ( 1 ) 全文搜索引擎： 全文搜索引擎是名副其实的搜索引擎，通过从互联网上提取的各个网站的信 息建立数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将 结果返回给用户。具有代表性的全文搜索引擎有g o o g l e 、a l l t h e w e b 、a l t av i s t a 、 i n k t o m i 、t e o m a 、w i s e n u t 、百度等。从搜索结果来源的角度，全文搜索引擎又可 细分为基于搜集器的搜索引擎和租用其他引擎的数据库的搜索引擎。 ( 2 ) 目录型搜索引擎： 除了基于网页分析建立索引的网页搜索引擎外，还有一种以人工方式或半自 动方式搜集信息的搜索引擎目录型搜索引擎。目录型搜索引擎也称为分类式 搜索引擎，这种搜索引擎是由编辑人员根据信息资源的内容按一定的主题进行分 类组织，并形成信息摘要。将信息置于确定的分类框架中，组织成一层一层的分 类目录，目录下面有更具体的子目录。信息的类别也由大到小、由粗到细。整个 搜索引擎形成了一个层次性的类别目录，用户可以逐层浏览选择不同的主题对网 络信息进行过滤，所选择的主题类别越小，信息的相关度就越高，用户就越有可 能找到自己所需要的信息。这类搜索引擎的性能主要取决于对于获取网页的人工 归类，或自动分类算法的精确度如何，其代表有：y a h o o 、l o o k s m a r t 、o p e n d i r e c t o r y 、 s n a p 、l y c o s 、g o g u i d e 等。 ( 3 ) 元搜索引擎( m e t as e a r c he n g i n e ) 由于单个搜索引擎的覆盖范围往往不会太大，为了找到自己所需要的信息， 用户常常需要使用多个搜索引擎，以期找到更好更全的信息，但由于不同的搜索 引擎其查询语法、接口界面往往不同，需要用户重新学习和适应不同的检索方法， 这给用户使用多个搜索引擎带来了极大的不便。为了解决这个问题，研究人员开 发了元搜索引擎。元搜索引擎是独立于索引系统的查询工具，它统一了不同的搜 索引擎的查询接口，用户面对的多个搜索引擎的界面是一样的，由统一的元搜索 引擎的接口对用户的查询请求进行处理，分别将其查询转换为符合底层搜索引擎 查询语法的子查询，同时向多个搜索引擎递交，由底层搜索引擎在各自的索引数 据库中进行查询。在各个搜索引擎发回检索结果后，元搜索引擎将子查询结果进 江苏大学硕士学位论文 行汇总、去重、重新安排等处理，最后向用户返回搜索引擎的检索结果。元搜索 引擎一般都没有自己的数据库，而是利用其它的搜索引擎的数据库来进行服务。 在层次上，元搜索引擎要比检索型搜索引擎和目录型搜索引擎要高，缺点是不能 够充分使用下层搜索引擎的排序功能，用户需要做更多的筛选。这类搜索引擎的 代表是m e t a c r a w l e r 、s a v v y s e a r c h 、i n f o r m a k e r 等。 1 2 3 搜索引擎评价标准 w w w 上的搜索引擎众多，各具特色。要合理评价一个搜索引擎的性能优势 并不是一件容易的事，因为搜索引擎设计的因素很多，且各因素之间相互影响， 不管是强调哪方面都是会忽略另一个方面的作用。下面将从几个基本的衡量标准 进行介绍。 ( 1 ) 查全率和查准率 查全率( r e c a l l ) 又称为召回率，它和查准率一样是很重要的衡量信息检索系统 的性能指标。查全率是指检索出的相关文档和文档中所有的相关文档数的比率。 查准率( p r e c i s i o n ) 又称为精确度，是检索出的相关文档数与检索出的文档总数的比 率1 4 1 。 ( 2 ) 覆盖率 覆盖率是搜索引擎的一个重要的衡量标准，一个搜索引擎收录的网页的多少， 索引的主题范围的大小，决定了它能为用户提供多大的范围的检索服务。 ( 3 ) 死链接率 很多搜索引擎总有些搜索结果是无法获取的，比如在点击搜索结果超链接时， 却得到“4 0 4 n o t f o u n d ”的错误提示。这类情况称为死链接，是由于搜索引擎不 能及时更新索引数据库而造成的。 ( 4 ) 便利性 搜索引擎提供的查询功能应具有使用的便利性。如除了支持简单搜索，是否 还支持逻辑查询和多次查询，是自动分词还是须加标记，是否能自动识别中英文。 1 3 论文研究内容及结构安排 1 3 1 研究内容 正如1 1 2 节中分析的搜索引擎面临的问题( 5 ) 所说，目前通常的搜索引擎只 是将返回的结果简单排序，但是搜索引擎返回的结果数量庞大，用户想要的信息 可能会淹没其中，这给用户带来不便。 江苏大学硕士学位论文 针对这个问题，我们将数据挖掘中的聚类知识应用到搜索引擎中，构建“聚 类搜索引擎”。目前的搜索引擎主要查找的是h t m l 文档，所以我们将文本聚类的 知识应用到搜索引擎结果的处理，对检索结果进行自动分类以便用户查找。本文 的主要研究内容如下： ( 1 ) 设计了一种基于后缀树聚类( s t c ) 算法的改进算法s t c i 。s t c i 算法的 提出是基于s t c 算法的两个缺点特征空间维数过高和未计算查询关键字与文 档的相关度考虑的。针对s t c 的这两个缺点，s t c i 算法通过剔除同义词、 近义词来给文档降维，从而降低算法的时间复杂度，并计算文档关于查询关键词 的相关性，不让与查询相关性较低的文档参与聚类，从而提高聚类的准确率。 ( 2 ) 设计了一种基于主题的聚类方法h t b c 。h t b c 首先根据文档的标题 和正文提取文档的主题词向量，然后通过训练文本集生成词类，将每个主题词向 量归类到其应属的词类，将同属于一个词类的主题词向量对应的文档归并到用对 应词类的名字代表的类，最终达到聚类的目的。h t b c 共分四个步骤，预处理、建 立主题向量、生成词类和主题聚类。并通过实验证明h t b c 在准确率和召回率方 面较k m e a n s 、a h c 、s t c 这几个常用聚类算法要好。 ( 3 ) 设计了一个带聚类模块的搜索引擎系统，该系统包括网络爬虫、索引系 统、带聚类模块的检索系统几个部分，聚类模块采用了h t b c 算法。通过分析系 统运行情况，证明了该系统设计的合理性。 1 3 2 文章的组织结构 第1 章绪论。介绍了本文选题的意义，包括研究背景和搜索引擎面临的问题， 进而确定了本文的研究内容与研究目标。然后，介绍了搜索引擎的发展史、分类 及评价标准。 第2 章相关理论介绍。介绍了本课题研究涉及到的相关知识，包括搜索引擎 的相关知识和文本聚类的相关知识，为后面的研究做铺垫。其中包括搜索引擎的 工作原理、文本聚类的概念、文本聚类系统的概念和应用、文本聚类经典算法等 内容。 第3 章后缀树聚类算法的改进。指出后缀树聚类算法的缺点，并针对这些缺 点作了改进。通过实验证明改进后的算法具有更高的聚类准确性和更低的时间复 杂度。 第4 章基于主题的聚类算法的研究。设计了一种基于主题的聚类方法一 h t b c 。该算法的思想是抽取文档主题，通过计算主题的相关性来进行聚类。并通 过实验证明该算法的高召回率和准确率。 江苏大学硕士学位论文 第5 章带聚类模块的搜索引擎设计。设计了一个带聚类模块的搜索引擎，通 过分析运行的结果证明设计的合理性。聚类模块使用h t b c 聚类方法。 第6 章总结与展望。对全文作总结，并指出了本课题进一步的研究方向和目 标。 江苏大学硕士学位论文 第2 章相关理论介绍 2 1 搜索引擎工作原理 搜索引擎的工作原理，大致可分为3 步：获取网页、建立索引数据库、在索 引数据库中搜索并排序。 ( 1 ) 从互联网上获取网页，就是利用能够从互联网上自动收集网页的网络爬 虫( 网络蜘蛛) 系统程序，自动访问互联网，并沿着任何网页中的所有u r l 爬到其 他网页，重复这一过程，并把爬过的所有网页收集回来。 ( 2 ) 建立索引数据库，就是由分析索引系统程序对收集回来的网页进行分析， 提取相关网页信息，根据一定的相关度算法进行大量复杂计算，得到每一个网页 针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然后用这些相关信 息建立网页索引数据库。 ( 3 ) 在索引数据库中搜索并排序，就是当用户输入关键词搜索后，由搜索系 统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相关网 页针对该关键词的相关度早已计算好，所以只需按照现成的相关度数值排序，相 关度越高，网页排名越靠前。最后，由页面生成系统将搜索结果的链接地址和页 面内容摘要等内容组织起来返回给用户。 2 1 1 网页搜集 搜索引擎的网页搜集过程并不是在用户提交关键词后进行即时的搜索，而是 预先将网页搜集好并进行相关的处理之后等待用户的查询。我们知道，在网络比 较畅通的情况下，从网上下载一篇网页大约需要1 秒钟，因此如果用户在查询的 时候即时去网上抓来成千上万的网页，一个个分析处理后再和用户的查询匹配， 这样查询的时间就会很慢也不可能满足用户的需求。甚至有可能多个用户重复抓 取同一个网页，使系统的效率降低。面对大量的用户查询，不可能每来一个查询， 系统就到网上“搜索”一次。大规模的搜索引擎是将一批预先搜集好的网页进行 管理和维护。维护有以下两种基本方法： ( 1 ) 定期搜集法 每次搜集替换上一次的内容，称为“批量搜集”。由于每次都是重新来一次， 对于大规模搜索引擎来说，每次搜集的时间通常会花费几周的时间。这样做的开 销比较大，通常两次搜集的间隔时间也很长。这种方法的好处是系统实现比较简 江苏大学硕士学位论文 单，缺点是实时性不高，还有重复搜集所带来的额外带宽的消耗。 ( 2 ) 增量搜集法 最初时搜集好一批数据，以后只是搜集新出现的网页和改变的网页并删除不 再存在的网页。除了新闻网站外，许多网页的内容并不是经常变化的，这样一来 每次搜集的网页量不会很大，于是可以经常进行搜集。3 0 万张网页，一台p c 机， 在一般的网络条件下，半天也就搜集完了。这样的系统表现出来的信息实时性就 会比较高，主要缺点是系统实现比较复杂。 在具体搜集过程中，如何抓取一篇篇的网页，可以有不同的考虑。最常见的 一种是所谓“爬取”，具体过程是，将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 e b ) 上爬行。一个真 正的系统其实是多个“蜘蛛”同时在爬，网络蜘蛛因此得名。 另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的u r l 集合 s ，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有新的 u r l ，则将它们对应的网页也抓回来，并将这些新u r l 也放到集合s 中。如果s 中某个u r l 对应的网页不存在了，则将它从s 中删除。这种方式也可以看成是一 种极端广度优先搜索，即第一层是一个很大的集合，往下最多只延伸一层。 还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址，系统在一定 时间内向那些网站派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存在 数据库中。大型商业搜索引擎一般都提供这种功能。 2 1 2 网页处理 互联网上大部分信息都是以h t m l 格式存在，对于索引来说，只处理文本信 息。因此需要把网页中文本内容提取出来，过滤掉一些脚本标识符和一些无用的 广告信息，同时记录文本的版面格式信息。网页处理主要包括4 个方面：关键词 的提取、重复或转载网页的消除、链接分析和网页重要程序的计算。 ( 1 ) 关键词的提取 由于h t m l 文档产生来源的多样性，许多网页在内容上比较随意，不仅文字 不讲究规范、完整，而且还可能包含许多和主要内容无关的信息( 如广告，导航条， 版权说明等) 。为了支持查询服务，需要从网页源文件中提取出能够代表它的内容 的一些特征关键词。网页处理阶段的一个基本任务，就是要提取出网页源文 江苏大学硕士学位论文 件的内容部分所包含的关键词。对于中文来说，就是要根据一个词典，用一个所 谓的“切词软件”，从网页文字中切除词典所含的词语来。在那之后，一篇网页主 要由一组词来近似表示了，如旷 ，j ，t 2 ，乙) 。 ( 2 ) 重复或转载网页的消除 w e b 上的信息存在大量的重复现象，网页的重复率平均大约为4 。这种现象对 于搜索引擎来说，它在搜集网页时要消耗机器时间和网络带宽资源，而且如果在 查询结果中出现，将消耗查询者计算机的资源，也会引来用户的抱怨。 ( 3 ) 链接分析 从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我们能依据关键 词和关键词在文档集合中出现的频率来统计该词的相对重要性以及和某些内容的 相关性。有了h t m l 标记后，情况还可能进一步改善，例如，在同一篇文档中， 和 之间的信息很可能就比在 和 之间的信息更重要。尤其 h t m l 文档中所含的指向其他文档的链接信息是人们特别关注的对象，认为它们 不仅给出了网页之间的关系，而且还对判断网页的内容有很重要的作用。 ( 4 ) 网页重要程度的计算 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的 顺序是很重要的一个问题。不同的顺序得到的结果是不一样的，因此搜索引擎实 际上追求的是一种统计意义上的满足。著名的p a g e r a n k 算法的核心想法就是“被 引用多的就是重要的”。 2 1 3 查询服务 为了完成查询服务，需要有相应的元素来进行表达，这些元素主要有：原始 网页文档、u r l 和标题、编号、所含的重要关键词的集合以及它们在文档中出现 的位置信息、其他的一些指标，如重要程度、分类代码等。 用户通过搜索引擎看到的不是一个“集合”，而是一个“列表”。如何从集合 生成一个列表，是服务子系统的主要工作。服务子系统是在服务进行的过程中涉 及的相关软件程序，而网页处理子系统事先为这些软件程序准备了相应的数据。