（计算机应用技术专业论文）基于实体聚类的网络信息检索处理.pdf

中文摘要 中文摘要 随着计算机技术的不断发展与应用，数字化的文本数据数量不断增长，互联 网的发展更加剧了数字文本的膨胀。搜索引擎成为人们生活中获取信息的重要工 具。虽然现在搜索引擎技术得到飞速发展和广泛应用，但是搜索引擎在使用中还 是有很多不方便的地方，还有改进的必要。 在这种情况下，利用聚类分析技术对文本数据进行简化表示，通过聚类分析 技术对信息检索结果进行重新组织、加速信息检索速度、实现信息的个性化服务 都是一系列极具发展前景的应用。 尽管在搜索引擎中关于聚类的研究很多，但是由于聚类算法本身的一些缺点， 其实际应用并不多。本文提出聚类技术在搜索引擎中作为一种辅助的方式存在， 帮助用户重新组织检索出的网页。基于网络信息检索的特点，本文提出一种分两 阶段进行的快速网页聚类策略。 在网页聚类中，h a c ( h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r i n g ) 算法和 k - m e a n s 算法都是经常用到的，但它们都有各自的不足。在本文两阶段聚类方法中， 第一阶段利用h a c 聚类算法对网络检索结果的标题进行聚类，第二阶段以第一阶 段结果作为初始中心用k - m e a n s 聚类标题和文本摘要，取得了比较合理的聚类结 果。由于标题一般都比较短，这样可以大大减少h a c 算法的运行时间。这样既满 足网络检索对时间的要求又可以得到较好的聚类结果。 本文的主要贡献是：明确聚类在网络信息检索中应该起到的辅助作用，并提 出了一个新的实现方法。 关键词：搜索引擎；聚类；快速网页聚类策略：两阶段聚类 黑龙江大学硕士学位论文 a b s t r a c t a st h ec o n t i n u a ld e v e l o p m e n ta n da p p l i c a t i o no fc o m p u t i n gt e c h n o l o g y , t h e q u a n t i t yo fd i g i t i z e dt e x td o c u m e n t su n c e a s i n g l yg r o w s a n dt h ed e v e l o p m e n to fi n t e m e t i n t e n s i f i e dt h ei n f l a t i o no fd i g i t a lt e x t s e a r c he n g i n eh a sb e c o m eam a i nt o o lf o rp e o p l e t og e ti n f o r m a t i o n s e a r c he n g i n eh a sd e v e l o p e dv e r yf a s ta n db e e nu s e dw i d e l y , b u ti t h a sm a n yd i s a d v a n t a g e sa n di si n c o n v e n i e n ti np r a c t i c e s ou t i l i z i n gt h ec l u s t e r i n ga n a l y s i st e c h n o l o g yt os i m p l i f yt h er e p r e s e n t a t i o no f m a s st e x td a t a , r e o r g a n i z et h er e s u l t sf r o ms e a r c he n g i n e s ，s p e e du pt h ei n f o r m a t i o n r e t r i e v a la n dr e c o m m e n dc u s t o m i z e di n f o r m a t i o nw o u l db ep r o m i s i n ga p p l i c a t i o n s t h e r ea l em a n yr e s e a r c h e so nt h ec l u s t e r i n gm e t h o du s e di ns e a r c he n g i n e s ，b u t c l u s t e r i n gm e t h o dh a si t so w nd i s a d v a n t a g e sa n do n l ya l i t t l eh a sb e e nu s e di nt h ea c t u a l a p p l i c a t i o n t h i sp a p e rd e m o n s t r a t e st h a tc l u s t e r i n gm e t h o dc o u l db ea l la u x i l i a r y f u n c t i o ni nw e bi n f o r m a t i o nr e t r i e v a l t h ec l u s t e r i n gm e t h o dw i l lr e o r g a n i z et h ew e b s e a r c hr e s u l t sf o rt h eu s e r s b a s e do nt h ep r o p e r t i e so fi n f o r m a t i o nr e t r i e v a lt h i sp a p e r p r o p o s e sa t w os t a g ef a s tc l u s t e r i n gs t r a t e g yo fw e bs e a r c hr e s u l tp a g e s i nw e bs e a r c hr e s u l tc l u s t e r i n g ，h a c ( h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r i n g ) a n d k - m e a n sa r eu s u a l l yu s e d b u te a c ho ft h e mh a st h e i ro w nf a u l t s t h i sp a p e ra d v a n c e sa t w o s t a g ec l u s t e r i n gm e t h o d i nt h ef i r s ts t a g e ，w ec l u s t e rt h et o p i c sb yh a c ，a n di nt h e s e c o n ds t a g e ，w ec l u s t e rt h et o p i c sa n da b s t r a c t sb yk m e a n sw i t ht h ei n i t i a lc l u s t e r c e n t e r sf r o mt h ef i r s ts t a g ec l u s t e r i n gt og e tar e a s o n a b l ec l u s t e r i n gr e s u l t b e c a u s et h e t o p i c sa l ea l w a y ss h o r t , t h er u n n i n gt i m eo fh a ci sg r e a t l ys h o r t e r t h i sm e t h o dw i l l m a k et h et i m ec o n d i t i o no fw e bs e a r c hb es a t i s f i e dw e l la n dg e tab e t t e rc l u s t e r i n g r e s u r t h em a i nc o n t r i b u t i o no ft h i st h e s i si st h a tc l u s t e r i n gm e t h o di sr e g a r d e da st h e a u x i l i a r yf u n c t i o ni ni n f o r m a t i o nr e t r i e v a lc l e a ra n dan e wi m p l e m e n tm e t h o dh a sb e e n p r o p o s e d k e y w o r d s ：s e a r c he n g i n e ，c l u s t e r i n gm e t h o d ，af a s tc l u s t e r i n gs t a t e g yo f w e bp a g e s ，t w o - s t a g e c l u s t e r i n gm e t l l o d i i 独创性声明 ii i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨蕉婆太堂或其他教育机构的 学位或证书而使用过的材料。 ， 学雠文储孙渤室 签字日期必步年衫月夕日 l， 学位论文版权使用授权书 本人完全了解墨蕉堑盔堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨蕉堑盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本学位论文。 学位论文作者毕业后去向： 工作单位：里岳砾以 通讯地址： 翮始韩孔式 签字日期：夕即岁年厂月夕日 嗡； 3 。j 毛也7 诩 邮编： 掳嘭 各 淬 签 (磁一哆 第1 章绪论 1 1 1 第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 1 课题研究的背景 随着互联网技术的快速发展，人们越来越强烈地感受到信息所带来的冲击， 而文本是信息的重要载体，人们日常生活中所接触到的信息有8 0 左右以文本的 形式存在。信息内容和格式的多样化、复杂化，信息更新速度之快，使人们无法 遍历所有感兴趣的内容，所以如何收集、管理互联网上的海量信息，如何快速准 确的查找出用户所需要的信息，就成为一个非常值得研究的问题。于是，高质量 的搜索引擎不断出现d 1 ，y a h o o ，g o o g l e ，b a i d u 等等。通过采用先进的蜘蛛机器 人来浏览网络，采集相关的网页内容存入数据库中，然后，使用高效率的查询系 统，在海量的数据库位1 中找出与用户查询信息相关的网页，并将其按照一定的顺序 反馈给使用者，从而完成整个查询任务。可以看出，在整个过程中，如何高效的 将含有所需信息的网页寻找出来是很重要的问题，各个领先搜索引擎无不在这方 面投入巨大的精力，花费大量的人力、物力、财力，力求在这方面能掌握领先地 位。目前的搜索引擎在实际使用中，在根据关键字进行搜索方面已经取得较大的 进步，能较完整快速的将与用户输入的关键字相关的网页按着一定的顺序反馈给 用户。但是，当检索用户在实际的使用中，输入关键字并得到相关的网页结果后， 却发现搜索引擎给出的搜索结果情况并不是十分令人满意。 从检索用户的实际使用中可以发现，同样的关键字会出现在很多不同的网页 中，这些网页所含的内容可以说是种类繁多，而检索用户所需的信息往往包含在 黑龙江大学硕士学位论文 相同类别的网页中。因此，若是我们能将搜索引擎反馈的网页结果按着内容进行 聚类，建立一个明确清晰的类别表，使得用户在得到搜索引擎根据关键字返回搜 索结果的同时，再由网页聚类系统提供的网页内容分类列表来进一步缩小范围， 使一定类别的网页能集中统一的显示出来，就能比直接由搜索引擎按顺序将结果 反馈给用户这样的方法更有效率，也更能明确的将结果提供给用户筛选。 文本聚类1 是根据文本数据的不同特征，将其划分为不同数据类的过程。其 目的是要使同一类别的文本间的距离尽可能小，而不同类别的文本间的距离尽可 能的大。主要的聚类方法有统计方法、机器学习方法、神经网络方法和面向数据 库的方法。在统计方法中，聚类也称聚类分析，主要研究基于几何距离的聚类。 在机器学习中聚类称作无监督学习。文本聚类由于其实用性强，应用方面多而广 泛地受到关注，对其进行的研究非常多，各种各样新的高效的方法也是层出不穷。 作为一种无监督的机器学习方法，聚类技术已经成为对文本信息进行有效地组织、 摘要和导航的重要手段。 研究文本聚类的最初目的是为了提高信息检索系统的查准率和查全率，并被 作为寻找文本最近邻居的有效方式。近年来，文本聚类用于浏览文本、显示文本 集合，或者在响应用户查询时，用于组织搜索引擎返回的结果。文本聚类也被用 于自动产生文本的多层次的类，并利用这些生成的类对新文本进行效率较好的归类。 针对这种情况，近些年来开始了有关w e b 信息检索系统的聚类研究，在传统 搜索引擎工作的基础上，将文档集合自动分成若干个簇( c l u s t e r s ) ，用户可以在 自己感兴趣的簇中查看结果，或者根据聚类情况提出更精确的查询。这样，将大 大缩小用户所需浏览的结果数量，缩短用户查询所需要的时间。 1 2 国内外研究现状 网页聚类( w e bc l u s t e r i n g ) 是网络信息检索的一种重要改进方法，用于从大 量半结构化数据( 即网页) 中发现知识或信息。网页聚类陋1 是从半结构化或未标记的 包含用户信息( 比如用户登录信息) 或文本信息( 网页文本) 的数据中抽取结构信息 的过程。 第1 章绪论 利用搜索引擎返回的标题和摘要信息进行聚类哺1 是一种非常新颖的想法，它不 需要下载整个网页，所以大大提高了聚类的时间效率。虽然利用了较少的信息， 但是聚类效果几乎可以和用网页全文聚类相媲美。本文尝试利用网页标题和摘要 进行网页聚类，并在前人基础上研究了一种新的聚类方法。试验表明该方法时间 复杂度相对较低，聚类效果较好，非常适合用于快速网页聚类。 s c a t t e r g a t h e r 帅系统是第一个利用网页摘要进行聚类的系统。但是该聚类 方法是基于传统的聚类算法( 类似于k - m e a n s 算法) 基础上，有一些缺点，如k 的取值必须事先确定、聚类速度较慢，聚类时间复杂度比较高等。但是它创新地 提出了利用搜索引擎返回的摘要进行聚类，避免了下载整个网页，极大地提高了 聚类效率，此后越来越多的系统尝试利用网页摘要进行聚类。 0 z a m i r 等人提出的s u f f i xt r e ec l u s t e r i n g ( s t c ) 睁1 3 1 聚类算法是对传统聚 类算法的一个巨大创新，它避免了计算两两文档之间的相似度，从而大大提高了 聚类效率。s t c 首先构造一棵后缀树，其中每个内部节点对应一个短语；然后把 包含相同关键短语的文档归为一类，从而形成基类；最后把基类中具有较大重叠 的类合并。s t c 算法利用文档之间共享短语的方法来对文档进行聚类，从而大大 降低了聚类算法的时间复杂度；然而它在空间复杂度方面较差，模型中存储了很 多冗余信息；另外在算法的通用性不够好，对于像中文这样的大字符集语言来说 处理起来非常困难。 国外的学术研究组织如：s i g i r ( s p e c i a li n t e r e s t i n gg r o u pi n f o r m a t i o n r e t r i e v a l ，美国计算机学会信息检索特别兴趣小组) 、t r e c ( t e x tr e t r i e v a l c o n f e r e n c e ，文本检索学术年会) 、m u c ( m e s s a g eu n d e r s t a n dc o n f e r e n c e ，消息 理解学术年会) n 钔等，它们的研究中有不少关于网页聚类的工作。 国外利用网页聚类方法来解决搜索引擎问题的研究已有很长时间的历史，国 内相关研究也逐步发展起来。复旦大学和中科院计算所n 钔对t r e c 测试中的分类任 务进行了长期的跟踪和研究，北京大学和清华大学较早在搜索引擎“天网n 和 “网络指南针n 盯”上研究网页分类技术。 虽然关于网页聚类的研究很多，但是目前对于聚类搜索的实际应用仍然处于 黑龙江大学硕士学位论文 刚起步的阶段，比较典型的聚类搜索引擎有v i v i s i m o ( h t t p ：v i v i s i m o c o m ) 和 比比猫( h t t p ：w w w b b m a o t o m ) 等。聚类搜索通过对搜索引擎的索引结果进行 聚类，使广大搜索引擎用户能够按照各自的需求点击相应的类别，用户能够更快 捷地找到自己想查询的内容。但是，目前的聚类搜索引擎普遍存在聚类速度较慢， 聚类结果准确率不高等特点。所以并没有得到广大检索用户的重视和广泛应用。 这就给科研工作者提出新的挑战，并被越来越多的研究人员所关注。今后聚类技 术必将在搜索引擎中得到广泛的应用。本文也致力于这方面的工作。 1 3 论文的贡献 本文的主要贡献有三点：( 1 ) 将聚类技术在网络信息检索中的作用定位为辅助 作用，允许用户选择是否聚类和聚类网页数目的大小；( 2 ) 本文提出一种两阶段聚 类方法，第一阶段我们意识到了标题在网页中的重要性，利用h a c 聚类算法对检 索到的结果网页的标题进行聚类；( 3 ) 如果聚类效果不好，不能满足用户的需求， 第二阶段以第一阶段的结果作为初始聚类数目和初始类中心用k - m e a n s 聚类算法 对标题加摘要进行聚类，并取得了比较合理的聚类结果。 由于标题一般都比较短，这样可以大大减少时间复杂度较高的h a c 算法的运 行时间。而k - m e a n s 算法因为有了初始值的输入而提高聚类的精度和效率。这样 既满足网络检索对时间的要求又可以得到较好的聚类结果。 1 4 论文的结构 本文主要分为五个部分。第一章引言。介绍了本文的研究背景、国内外研究 现状、本文的研究目的和贡献，阐明了本文研究的应用价值。第二章网页聚类相 关知识。介绍了与网页聚类相关的信息检索、网络搜索引擎、聚类算法等方面的 知识。第三章基于实体聚类的网络信息检索处理。介绍了网页聚类的一般过程， 提出一种网页快速聚类策略，并简要介绍了网页聚类的常用评价方法和指标。第 四章两阶段快速聚类实验及结果分析。详细介绍了实验的整个过程，并对实验结 果进行了分析。最后，给出了本文的结论、不足和对未来工作的建议。 第2 章网页聚类相关知识 第2 章网页聚类相关知识 在i n t e r n e t 被广泛应用之后，信息检索更多是在网络上进行。在当今文献和 知识急剧增长的信息时代，如何在浩如烟海的文献信息流中迅速找到所需知识和 信息，并加以合理有效的利用，是摆在科研工作者面前的一道重要课题。 聚类分析的研究已经有很长的历史了，其重要性及其与其它研究方向的交叉 特性得到人们的肯定和重视。聚类是数据挖掘、模式识别、机器学习等研究方向 的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用。长期以 来，人们已经将聚类方法引入到搜索引擎的研究和应用当中。本章将介绍网页聚 类的相关知识。 2 1 信息检索概述 信息检索涉及数据库技术、图书和情报科学、人工智能、自然语言处理、机 器学习等众多知识和学科领域。信息检索的主要目的是对信息表示、存储与组织， 使用户更容易得到所需要或者感兴趣的信息。信息检索的过程可以简单地描述为 用户提交查询条件，信息检索系统根据该查询条件在文档集中检索出与其相关的 文档子集，对这些相关文档子集中的文档按照与查询条件的相关性进行排序，最 后返回给用户有序的文档子集。 2 1 1 信息检索概念 信息检索n n 力是从非结构化的文档集中找出与用户需求相关的信息。是沟通 广大检索用户和各种信息源的主要渠道，也是大量情报信息进行广泛传递的集中 表现形式，最能体现信息存贮的目的。互联网的发展为我们提供了一种全球范围 的信息基础设施，也极大地推动了信息检索技术的发展和应用i 目前，信息检索已经发展到网络化和智能化的阶段。信息检索的对象从相对 封闭、稳定、由独立数据库集中管理的信息内容扩展到开放、动态、更新快、分 布广泛、管理松散的内容。信息检索的用户也由原来的情报专业人员扩展到包括 黑龙江大学硕士学位论文 商务人员、管理人员、教师学生、各专业人士等在内的普通大众，他们对信息检 索从结果到检索方式提出了更高、更多样化的要求。适应网络化、智能化以及个 性化的需要是目前信息检索技术发展的新趋势。 综上所述，互联网的发展使得信息呈爆炸式增长，传统文献的猛增，促使信 息检索领域的独立，网络文献的猛增，使得信息检索技术发展不断适应网络化、 智能化以及个性化的需要，这一新的发展趋势加速了搜索引擎的发展。 2 1 2 信息检索的意义 信息检索在用户与信息源之间充当媒介作用，它是联系信息生产者与信息需 求者的中间环节，是信息交流和传递的重要过程，是提高文献利用率和科研效率 的重要手段。 信息检索是获取知识的有效途径。在当今文献和知识急剧增长的信息时代， 如何在浩如烟海的文献信息流中迅速找到所需文献信息，并加以合理有效的利用， 是摆在科研工作者面前的一道重要课题。据测算，人类知识总量在1 9 世纪每5 0 年增加一倍，2 0 世纪初每1 0 年增加一倍，2 0 世纪7 0 年代每5 年增加一倍，8 0 年 代几乎是每3 年增加一倍。而且，文献信息的分布己极不平衡，同一学科的论文 分散在几十种、甚至几百种期刊上，导致文献的查找越来越困难。因此，如何以 最少的精力、最短的时间充分获得信息，成了人们亟待解决的实际问题，而信息 检索正是有效解决这一问题的最好途径，它可以帮助人们快、准、全地获取所需 信息，最大限度地节省查找时间，使信息得以充分的利用。 2 1 3 信息检索效果的评价 所谓检索效果，就是利用检索系统( 或检索工具) 开展检索服务时产生的有 效结果。检索效果评价着眼于整个检索系统，着眼于系统的使用效果和服务质量， 因而它直接反映了检索系统性能。 目前，衡量检索效果的方法主要有三个方面：检索结果有效性的评价，即 检索的技术效果的评价，这是对检索系统检出相关文献以满足用户提问要求能力 第2 章网页聚类相关知识 的一种测度，主要以查全率和查准率为评价标准。检索系统实用性的评价，包 括系统对用户是否需要，是否实用，有多大的实用效果，即检索的社会效果的评 价，其中要涉及到社会学及其方法。检索费用，即检索的经济效果的评价，包 括检索服务的成本和时间消耗，这涉及到信息检索系统的经济学问题。然而，由 于检索效果的评价涉及到许多问题，可以从不同的角度采用不同的检索效果评价 方法。 查全率和查准率n 刀是由j w 佩里和a 肯特于5 0 年代中期提出来的，后经不 断改进和完善，至今已成为评价检索效果最常用的两项关键指标。相关的定义见 表2 一l 。 表2 1查全率和查准率相关定义 t a b l e2 1d e f i n i t i o n sa b o u tr e c a l la n dp r e c i s i o n 一 相关文 非相关文献总计 献 系统相关性预报 被检出文献 aba + b 未检出文献 cdc + d 总计 a + cb + da + b + c + d 其中a 表示被检出的相关文献，即查准的文献； b 表示被检出的非相关文献，即误检的文献； c 表示未检出的相关文献，即漏捡的文献； d 表示未检出的非相关文献，即正确拒绝的无关文献。 存贮在文献检索系统文档中，参加检索的全部文献量为( a + b + c + d ) 。从检索 系统角度来看它们可以分为两部分：一部分是被检出文献( a + b ) ，也就是与检索 策略相匹配的部分；另一部分是未检出文献( c + d ) ，即与检索策略不相匹配的部 分。因为两部分文献反映了检索系统处理是否与检索提问相关，故称之为系统相 关性预报。 另一方面，从用户的角度来看，检索系统文档中参加检索的全部文献也可以 分为两个部分：一部分与用户需要相符，称为相关文献( a + b ) ；另一部分与用户 黑龙江大学硕士学位论文 需求不符，称为非相关文献( b + d ) 。因为这两部分文献反映了用户判断是否与检 索需要相关，故又称之为用户相关性判断。 这样，便可以根据这些定义来确定查全率与查准率的含义。 查全率就是系统在进行某一检索时，被检出的相关文献量与系统文档中实有 的相关文献量的比率，可用下式表示： 查全率( r ) = 蒜黼* 1 0 0 = 熹* 1 0 0 ( 1 - 1 ) 查准率就是被检出的相关文献量与被检出的文献总量的比率，可用下式表示： 查准率( p ) =鍪坌些塑羞窒堕重奉 被检出文档总量 1 0 0 ：旦幸1 0 0 a + b ( 卜2 ) 可见，查全率是用来描述检索系统检出相关文献的能力；查准率用来描述检 索系统拒绝非相关文献的能力。 显而易见，查全率考察系统找全答案的能力，而查准率考察系统找准答案的 能力，两者相辅相成，从两个不同侧面较为全面地反映了系统性能。现代信息检 索的研究中，非常重视检索结果在前1 0 或2 0 个结果处的查准率，因为这是最贴 近实际应用的情况。对商用搜索引擎用户使用状况的研究表明，很多用户只关心 前一页到两页的检索结果。查全率反映了检索系统对某个查询返回的结果中正确 结果占全部正确结果的比例。 在具体评价检索系统的检出效果时，一般应将查全率与查准率结合起来，否 则难以准确反映检索系统的功能和检索效果。 虽然查全率与查准率能较好地反映出一个检索系统的检索效果，但是，它们 也存在一些难以克服的局限性和固有的缺限。首先，一个检索系统中总共有多少 相关文献( a + c ) 难以确切计算，而只能是大概估算；其次，对于全部相关文献对 用户的价值是建立在假定具有同等价值上的，然而实际上并非如此。不同的用户 对相关文献的认识也可能不致，因此存在着太多的主观成分和一些模糊概念， 所以说明上述方法求得的查全率与查准率并不是绝对的，而只能是相对近似地描 述检索效果。 第2 章网页聚类相关知识 现在，多使用手工方式对某一代表性的搜索建立搜索标准，然后和计算机检 索的结果进行对比，评价检索结果的好坏。 2 2 网络搜索引擎 2 2 1 网络搜索引擎的概述 现代意义上的搜索引擎最早出现于1 9 9 4 年7 月，就是大家现在熟知的l y c o s 。 同年4 月，斯坦福大学的两名博士生d a v i df i l o 和美籍华人杨致远共同创办了超 级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高 速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其检索的信息量 也与从前不可同日而语。g o o g l e 的数据库中存放的网页数量惊人。 搜索引擎n 8 1 ( s e a r c h e n g i n e ) 是指根据一定的策略、运用特定的计算机程序搜 集互联网上的信息，在对信息进行组织和处理后，为用户提供检索服务的系统。 在浩如烟海的互联网信息中，如何找到自己想要的信息就变得十分重要了。从早 期用人工分类的方法为网站建立索引，到现在的关键词搜索，搜索引擎让我们越 来越方便的找到自己想要的信息。在互联网上不会用搜索引擎，那只能被动的接 受各网站提供给的信息，而熟练的使用各种搜索引擎则能主动的找到自己想要的 信息。 搜索引擎是一种能够通过i n t e r n e t 接受用户的查询指令，并向用户提供符合 其查询要求的信息资源网址的系统。它是一些在w e b 中主动搜索信息( 网页上的 单词和特定的描述内容) 并将其自动索引的w e b 网站，其索引内容存储在可供检 索的大型数据库中。一些搜索引擎搜索网页的每一个单词，而另一些搜索引擎则 只搜索网页的前二百至五百个单词。当用户输入关键词( k e y w o r d ) 查询时，该搜 索引擎会告诉用户包含该关键词信息的所有网址，并提供通向该网络的链接。搜 索引擎既是用于检索的软件，又是提供查询、检索的网站。所以，搜索引擎也可 称为i n t e r n e t 上具有检索功能的网页。 搜索引擎的数据检索方式主要是关键字的匹配方式，如泛匹配、模糊匹配、 黑龙江大学硕士学位论文 正则匹配以及多关键字的处理方式等。能为用户提供全文索引、约束性检索、基 于布尔关系的查询方式，并对查询结果根据某种算法和规则评分和排序，例如著 名的p a g e r a n k n 9 1 和h i t 算法。 搜索引擎将向智能化、个性化、精确化、专业化、交叉语言检索、多媒体检 索等适应不同用户需求的方向发展，更好的理解用户的需求。 2 2 2 网络搜索引擎的主要功能 各种搜索引擎的主要功能都包括以下三个方面： 1 、信息搜集 各个搜索引擎都派出绰号为蜘蛛( s p i d e r ) 或机器人( r o b o t s ) 的“网页搜 索软件 ，在各网页中爬行，访问网络中公开区域的每一个站点并记录其网址， 将它们带回搜索引擎，从而创建出一个详尽的网络目录。由于网络文档的不断变 化，机器人也不断地把以前已经分类组织的目录更新。 2 、信息处理 将“网页搜索软件”带回的信息进行分类整理，建立搜索引擎数据库，并定 时更新数据库内容。在进行信息分类整理阶段，不同的搜索引擎会在搜索结果的 数量和质量上产生明显的差异。有的搜索引擎把“网页搜索软件发往每一个站 点，记录下每一页的所有文本内容，并收入到数据库中从而形成全文搜索引擎； 而另一些搜索引擎只记录网页的地址、篇名、有特点的段落和重要的词。故有的 搜索引擎数据库很大，而有的则较小。当然，最重要的是数据库的内容必须经常 更新、重建，以保持与外部世界信息的同步发展。 3 、信息查询 每个搜索引擎都必须向用户提供一个良好的信息查询界面，一般包括分类目 录及关键词两种信息查询途径。分类目录查询是以资源结构为线索，将网上的信 息资源按内容进行层次分类，使用户能依线性结构逐层逐类检索信息。关键词查 询是利用建立的网络资源索引数据库向网上用户提供查询“接口 。用户只要把 想要查找的关键词或短语输入查询框中，并按“搜索”按钮，搜索引擎就会根据 第2 章网页聚类相关知识 输入的提问，在索引数据库中查找相应的词语，并进行必要的逻辑运算，最后给 出查询的命中结果( 均为超文本链接形式) 。用户只要通过搜索引擎提供的链接， 就可以访问到相关信息。 2 2 3 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引 擎( m e t as e a r c he n g i n e ) 。 1 、全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的是g o o g l e 等，国内著 名的有百度( b a i d u ) 等。它们都是通过从互联网上提取的各个网站的信息以网页 文字为主而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定 的排列顺序将结果返回给用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种：一种是拥有自己的 检索程序，俗称“蜘蛛”程序或“机器人刀程序，并自建网页数据库，搜索结果 直接从自身的数据库中调用，如上面提到的几家搜索引擎。另一种则是租用其他 引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 2 、目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而己。用户完全可以不用进行关键词查询，仅靠分 类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的y a h o o 。 国内的搜狐、新浪、网易搜索也都属于这一类。 3 、元搜索引擎 元搜索引擎娩1 1 在接受用户查询请求的同时，在其他多个引擎上进行搜索，并 将结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等，中 文元搜索引擎中具代表性的有b b m a o 搜索引擎。在搜索结果排列方面，有的直接 按来源引擎排列搜索结果，如d o g p i l e ；有的则按自定的规则将结果重新排列组合， 黑龙江大学硕士学位论文 如v i v i s i m o 。 2 2 4 网络搜索引擎存在的不足 i n t e r n e t 的飞速发展让搜索引擎成为人们生活中获取信息不可或缺的工具。 尽管搜索引擎已经有了长足的发展，但是依然存在很多不利于人们使用的问题。 1 、检索效率低下 由于网络信息导航只支持单步信息定位，只允许导航系统一步一步地追踪信 息，客户机在追踪过程中接受了诸多冗余信息造成效率降低。由于搜索引擎本身 技术的限制，很多对用户没有意义的网页也会被作为结果返回给用户，造成用户 检索中不必要的负担。 2 、检索结果显示不明晰 在检索过程中用户往往带有很大的盲目性，有时只是碰碰运气，缺乏明确的 目标。基于搜索引擎的网络检索同基于超文本超媒体浏览一样，用户不易对检索 到的内容产生明确印象。当用户检索到一个网络地址并以此作为检索入口时，可 以“顺链而行”一步步浏览，但此过程中不断会有新鲜的主题跳出来吸引检索者 注意力，用户可能偏离主题，完全忘记检索目标，最后一无所获。 2 2 5 网络搜索引擎的发展方向 搜索引擎将向智能化、个性化、精确化、专业化、交叉语言检索、多媒体检 索等适应不同用户需求的方向发展，更好的理解和满足用户的要求。 1 、智能化的检索 它是未来搜索引擎的发展方向。搜索引擎的智能化体现在两方面：一是对搜 索请求的理解、也就是对人意图的理解；二是对网页内容的分析。利用智能代理 技术对用户的查询计划、意图、兴趣方向进行推理，自动进行信息搜集过滤，自 动地将用户感兴趣的、对用户有用的信息提交给用户。 2 、跨语言的搜索引擎 搜索引擎对多种语言的数据库进行交叉语言信息检索，返回能够回答用户问 第2 章网页聚类相关知识 题的所有语言的文档。若配上机器翻译，就可使返回结果以用户熟悉的语言显示。 虽然该技术目前还处于初步研究阶段，其难点在于语言之间在表达方式和语义对 应上的不确定性，但在国际化的前提下，这是一个研究的方向。 3 、提供对自然语言检索支持的问答系统 为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言， 为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询，如 g o o g l e 有专用于回答问题的g o o g l ea n s w e r 。搜索引擎在对提问进行结构和内容 的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再 选择。自然语言的优势在于，一是使网络交流更加人性化，二是使非专业的用 户查询变得更加方便、直接、有效。 4 、多媒体搜索引擎 网络资源丰富多彩，具有很多类型的信息，用户需要的信息也不完全是网页 的形式或者文本的形式，从用户的角度来看，必然要求搜索引擎能够覆盖更多的 网络资源。现在有很多搜索引擎已经提供了网页、新闻、图片、音乐等资源搜索， 当然范围还可以更广，再如可以搜索新闻组、软件、f t p 、f l a s h 、论文等等。 5 、专业化垂直搜索引擎 是为了专门收录某一行业、某一学科、某一主题和某一地区的信息而建立，非 常实用，这种专业化的搜索引擎是将来的方向之一。现在这方面的研究也比较热 烈。 此外还有一些其它值得注意的技术发展，如桌面搜索引擎，移动代理和x m l 技术，语音检索技术等。随着技术的不断发展进步，搜索引擎将会成为人们获取 知识和信息的重要手段。 2 3 聚类算法 2 3 1 聚类概述 迄今为止，聚类陇旧1 还没有一个学术界公认的定义，这里给出e v e r i t t 在1 9 7 4 黑龙江大学硕士学位论文 年关于聚类所下的定义：一个簇内的实体是相似的，不同类簇的实体是不相似的； 一个簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的 任意两个点间的距离：簇可以描述为一个包含密度相对较高的点集的多维空间中 的连通区域，它们借助包含密度相对较低的点集的区域与其他区域( 簇) 相分离。 聚类算法广泛应用在模式识别、图像处理、自动控制等领域。聚类方法包括 统计方法、机器学习方法、神经网络方法和面向数据库的方法。所谓聚类就是把 数据分成不同的组或类，并且使得簇与簇之间的相似度尽可能的小，而组内数据 之间具有较高的相似度。将一群物理的或抽象的对象，根据它们之间的相似程度， 分为若干组，其中相似的对象构成一组，这一过程就称为聚类过程。一个聚类就 是由彼此相似的一组对象所构成的集合，不同聚类中对象通常是不相似的。聚类 分析就是从给定的数据集中搜索数据对象之间所存在的有价值联系。与分类不同， 在开始聚类之前用户并不知道要把数据分成几组，也不知道分组的具体