（计算机软件与理论专业论文）文档聚类在搜索引擎结果中应用的研究.pdf

j s 塞交通盔堂亟堂焦j 金童生塞擅鼍 中文摘要 摘要：随着的i n t e m e t 飞速发展，人们利用i n t e m e t 发展和共享各种信息，使得信 息爆炸式增长，普通网络用户查找所需资料变得非常困难，搜索引擎正是为了解 决这一问题而发展起来的。而现在的搜索引擎存在明显的缺陷：一是搜索引擎结 果数量庞大；二是搜索结果线性排列。本文在现有搜索引擎各种技术研究的基础 上，对文档聚类进一步研究，致力于搜索结果的自动分类，从而使得用户更加直 观高效地找到所需结果。 本文先介绍了搜索引擎的概念和原理，文档聚类的相关原理，设计了基于 g o o g l e w e b a p l 的解决方案，将搜索引擎返回的结果进行聚类处理，最后以结构 化的方式显示给最终用户。 本文的主要研究成果包括： ( 1 ) 对s u f f i x 聚类算法进行了研充引入了p a t - t r e e 数据结构，弥补了s u f f t x 聚 类算法处理中文信息的不足，显著提高了文档聚类的性能。 ( 2 ) 将文本聚类与现代搜索引擎技术结合起来，设计了一种新的搜索引擎体系 结构，解决了当前搜索引擎存在的一些缺陷。 ( 3 ) 在以上面各项研究的基础上，开发了实际的原型系统，从而证明了提出的 新的搜索引擎体系结构的可行性。 搜索引擎是一个崭新的领域，其相关的许多技术还在发展，本文的最后对进一 步的研究工作进行了探讨。 关键词：信息过载；搜索引擎；文档聚类；g o o g l ew e ba p i j e 廛窑适盔堂鲤堂焦论塞丛s 卫迅! a b s t r a c t 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 fc o m p u t e rn e t w o 毗h t c m c ci su s e d 幻 p u b l i s ha n ds h a r ei n f o r m a t i o n ，w h i c hb r i n g sf o r w a r dm o r ti n f o r m a t i o na n dd i f f i c u l t yf o r c o b u n o nu s e f st of i n di n f o r m a t i o n s e a r c he n g i n e sa r ed e v e l o p e dt os o l v et h i sp r o b l e m a tp r e s e n t , s e a r c he n g i n e sh a v et w od i s t i n c tf l a w s ，o n ei st h en u m b e ro f r e s u r sr e t u r n e d b ys e a r c he n g i n ea l en u m e r o u s ，t h eo t h e ri st h a tt h er e s u l t sa r ed i s p l a y e dl i n e a r l y b a s e d o np r e v i o u sr e s e a r c hr e s u l t sa n dt e c h n o l o g i e so fs e a r c he n g i n e s ，w cf u r t h e rt h er e s e a r c h o nt h ed o c u m e n tc l u s t e r i n ga n dc l a s s i f y i n gw e bs e a r c hr e s u l t sa u t o m a t i c a l l y f i r s t l y , n o to n l yt h eb a s i cc o n c e p ta n dp r i n c i p l eo fs e a r c he n g i n e s ，b u ta l s o p 啦c j 棚e so f d o c u m e n tc l u s t e r i n ga r ei n t r o d u c e d , w h i c ha r eu s e f u lt of o r mt h es o l u t i o n b a s e do ng o o g i ew e ba p i t h es o l u t i o nc l u s t e r st h ew e br e s u l t sr e t u r n e db ys e a r c h e n g i n e sa n dd i s p l a y e dt on s e r ss t r u c t u r e d t h em a i na c h i e v e m e n t so f t h et h e s i sa r ef o l l o w i n g ： ( 1 ) w ei n t e g r a t ed o c u m e n tc l u s t e r i n gw i t hp a t - l r e ed a t as t r u c t u r e ，w h i c hi m p r o v e s t h ep e r f o r m a n c eo f d o c u m e n tc l u s t e r i n g ( 2 ) w ei n t e g r a t ed o c u m e n tc l u s t e r i n gw i t hm o d e mt e c h n o l o g i e so fs e a r c he n g i n e s a n db r i n gf o r w a r dan e wa r c h i t e c t u r eo fs e a r c he n g i n e ，w h i c hs o l v e ss o m ep r o b l e m so f m o d e r ns e a r c he n g i n e s ( 3 ) b a s e do np r e v i o u sr e s e a r c ho ns e a r c he n g i n e ，w ed e v e l o pad e m os y s t e m ， w h i c hp r o v e st h ef e a s i b i l i t yo f t h en e wa r c h i t e c t u r eo fs e a r c he n g i n e s e a r c he n g i n ei ss t i l lan e wc o n c e p t i o n ，a n dm a n yt e c h n o l o g i e si n v o l v e da r en o t y e tm a t u r ea n db e i n gd e v e l o p e d t h ef u t u r er e s e a r c hp r o b l e m sa r ea l s od i s c u s s e di nt h e e n do f t h ep a p e r k e y w o r d s ：i n f o r m a t i o no v e r l o a d ；s e a r c he n g i n e ；d o c u m e n tc l u s t e r ；g o o g l ew e b a - p i 致谢 本论文的工作是在我的导师卢苇教授的悉心指导下完成的，卢苇教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来卢苇 老师对我的关心和指导。 卢苇教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向卢苇老师表示衷心的谢意。 卢苇教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢。 在清华国家信息实验室工作及撰写论文期间，张尧学老师，方存好、田鹏伟 等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的父母、亲人和很多朋友，他们的理解和支持使我能够在学校 专心完成我的学业。 1 1研究背景 1 1 1i n t e r n e t 的发展 1 引言 计算机网络技术是2 0 世纪人类最伟大的发明之一。自1 9 6 9 年i n t e m e t 的前身 a r p a n e t 诞生以来，计算机网络技术飞速发展。以t c p i p 协议为核心的网络互 联技术实现了计算机硬件的连通，形成了一个全球范围内计算机互联的基础设施， 即i n t e r n e t 。在此基础上，基于h t t p 协议和超文本规范的w e b 技术实现了信息资源 的互联，使i n t e r n e t 进一步演变成为一个信息资源平台和分布式计算机平台。 i n t e m e t 已经从根本上改变了人们生活和工作的方式，成为一项不可或缺的技术手 段。 进入新世纪以来，网格技术逐渐兴起。网格的研究试图将i n t e m e t 上所有资源 融合成为一个整体，使人们随时随地从i n t e m e t 得到按需的计算服务和其他各种服 务。这是i n t e r n e t 的又一次革新，并将进一步改变人们的生活和工作方式，带来社 会的新革命。图1 1 给出了i n t e r n e t 发展变化的几个主要阶段，它们是： 囊纛善瑟藩：蠹。聩! ：蠹 囊，i ”f 。鼍拳i 移i 0 i ：* 蟹：。：落 蒸赫螽羹蒿蠹 i j 。“= 。：。”i ! 奠i 一：* 芝* ：。 ：i 。一：= 。：。? 一 警戳貔瀚i 麟缝：鬟“ i ”戮翰麟。 ”舔辫巍l 瓣鹣粼鞠院蠡 f 、 霸溅e i 黪”黝粼l 罄 w i 。嚣僦联 绚粼燃锄的 l 赣翻燃 自蘸鬟酾泌q 镟 ! 。娜够趟懈 蟊r 0 粥匿翼 s a f v p 。r er e 铀鞠罄昏! 。嚣搬e 撑淤 h 斛t e x t 觏o w l e d f e1 e s o u r c e 一棒露p 毋雳萨”。 “ 、* 二 1 9 6 91 9 8 0 g1 9 9 0 s2 0 0 0 $ ，计算机互联阶段 图1 1i n t e m e t 的主要发展过程 韭塞銮道盍堂亟堂僮论塞 l 宣 1 9 6 9 年8 月美国国防部高级计划署( d a r p a ) 推出的分组( p a c k e t ) 交换式网络系 统a 狐n e t 标志着计算机网络的诞生。此后，t c p ，m 的出现以及t c p p 和u n i x 的结合促进了网络技术与应用的发展和普及，经过二十多年的发展，a r p a n e t 逐 渐演变成为一个全球范围的计算机互联的基础设施，即i n t e r n e t 。 2 w e b 互联阶段 1 9 8 9 年，欧洲粒子物理实验室开发成功w e b 技术( w w ww o r l dw i d ew e b ) ， 为在h l t c m e t 存储、发布和交换文字、图像、音频、视频等多媒体信息提供了新的 平台。9 0 年初，w e b 技术与n e t s c a p e 以代表的w e b 浏览技术相结合，极大地促进 了i n t e m e t 的发展，i n t e m e t 从一个计算机互联的基础设施进一步演变成为信息资 源共享平台和分布式计算平台。 这一阶段i n t e r n e t 的主要应用是信息共享和发布，包括w w w 、新闻组和多媒 体等。 3 网格互联阶段 随着新一代互联网络协议i p v 6 ，光通信网络、移动无线网等网络互联技术的 研究，下一代的i n t e m c t 将提供更高的网络带宽，更可靠的传输质量和更广泛的网 络应用，以此为基础，目前网格技术研究逐渐兴起。 如果说，早期的i n t e r n e t 实现了计算机硬件的连通，w e b 互联实现了网页的连 通，那么网格则从应用驱动的角度实现i n t e m e t 上所有资源的互通和共享，包括计 算资源、存储资源、通信资源、软件资源、知识资源等。网格是一个i n t e m c t 上集 成的计算与资源环境，它试图吸纳各种计算资源，并将它们转化成一种随处可得 的，可靠的，标准的和经济的计算能力，并最终实现i n t e m e t 环境下的资源共享和 协同工作，消除信息资源孤岛；使i n t e m e t 如同一台超级计算机，向用户提供一体 化的服务。 1 1 2i n t e r n e t 的发展对信息检索的推动 i n t e m e t 的发展为我们提供了一种全球范围的信息基础设施，也极大地推动了 信息检索技术的发展和应用。 信息检索( i n f o r m m i o nr e t r i e v a l ) ，通常指文本信息检索，包括信息的存储、 组织、表现、查询、存取等各个方面，其核心为文本信息的索引和检索。从历史 2 韭塞銮逼太堂亟堂鱼j 金室 i 直 上看，信息检索经历了手工检索、计算机检索到现在的网络化、智能化检索等多 个发展阶段。 目前，信息检索已经发展到网络化和智能化的阶段。信息检索的对象从相对 封闭、稳定一致、由独立数据库集中管理的信息内容扩展到开放、动态、更新快、 分布广泛、管理松散的w e b 内容；信息检索的用户也由原来的情报专业人员扩展 到包括商务人员、管理人员、教师学生、各专业人士等在内的普通大众，他们对 信息检索从结果到方式提出了更高、更多样化的要求。适应网络化、智能化以及 个性化的需要是目前信息检索技术发展的新趋势。 综上所述，i n t e r n e t 的发展使得信息呈爆炸式增长，传统文献的猛增，促使信 息检索领域的独立，网络文献的猛增，使得信息检索技术发展不断适应网络化、 智能化以及个性化的需要，这一新的发展趋势加速了搜索引擎的发展。 1 1 3搜索引擎的发展 在i n t e m e t 发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生了。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的a r c h i e 。虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是相当 频繁的，而且由于大量的文件散布在各个分散的f t p 主机中，查询起来非常不便， 因此a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便有了 a r c h i e 。 a r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网 上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于a r c h i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年 开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外， 己能检索网页。 当时，“机器人”一词在编程者中十分流行。电脑“机器人”( c o m p u t e r r o b o t ) 是指某个能以人类无法达到的速度不问断地执行某项任务的软件程序。由于专门 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 。刚开始它只用来统计互联网上的服务器数量，后 来则发展为能够检索网站域名。 与w a n d e r e r 相对应，m a r t i n k o s t e r 于1 9 9 3 年1 0 月创建了a l i w e b ，它是a r c h i e 的 r r r p 版本。a l l w e b 不使用“机器人”程序，而是靠网站主动提交信息来建 立自己的链接索引，类似于现在我们熟知的y a h o o 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因此， 在m a t t h e wg r a y 的w a n d e r e r 基础上，一些编程者将传统的“蜘蛛”程序工作原理 作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟 踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一些基于此原 理的搜索引擎开始纷纷涌现，其中以j u m p s t a t i o n 、t h ew o r l dw i d ew e bw o r m ( g o t o 的前身，也就是今天o v e r t u r e ) ，和r e p o s i t o r y - b a s e ds o f t w a r ee n g i n e e r i n g ( r b s e ) s p i d e r 最负盛名。 然而j u m p s t a t i o n 和w w w w o r m 只是以搜索工具在数据库中找到匹配信息的 先后次序排列搜索结果，因此毫无信息关联度可言。而r b s e 是第一个在搜索结 果排列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将j o h n l c a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月， 斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索 引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其 检索的信息量也与从前不可同日而语。比如最近风头正劲的g o o g l e ，其数据库中 存放的网页已达3 0 亿之巨! 随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗己无法适应目 前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索 引擎技术和搜索数据库服务提供商。象国外的i n k t o m i ( 己被y a h o o 收购) ，它本 身并不是直接面向用户的搜索引擎，但向包括o v e r t u r e ( 原g o t o ，已被y a h o o 收 4 韭塞奎道太堂亟堂焦盈毫i i 壹 购) 、l o o k s m a r t 、m s n 、h o t b o t 等在内的其他搜索引擎提供全文网页搜索服务。 国内的百度也属于这一类( 注1 ) ，搜狐和新浪用的就是它的技术( 注2 ) 。因此从 这个意义上说，它们是搜索引擎的搜索引擎。 ( 注1 ) ：百度已于2 0 0 1 年9 月开始提供公共搜索服务。 ( 注1 ) ：搜狐二级网页搜索现己改为中搜的引擎，而新浪则已转用g o o g l e 的 搜索结果。 1 2本文的研究目标和主要解决的问题 随着互联网的迅猛发展，信息爆炸式增长，产生了信息过载( i n f o r m a t i o n o v e r l o a d ) ，而在相当大的程度上，搜索是面临信息过载的唯一选择。但是，现在 的搜索引擎缺陷也很明显，几乎快成了新的信息过载：一是搜索结果数量庞大： 二是搜索结果的线性排列。 针对上面提到的问题，我们将数据挖掘中的聚类知识引用到现有搜索引擎， 构建“聚类搜索引擎”。“聚类搜索引擎”以认知模式等心理学为理论基础，提出 “三到五次点击之内”得到用户所需要的信息。它实现的功能就是把检索出来的 结果自动分类，使得用户能很直观的根据需求点击，直接定位到要查找的网页。 针对本文的主要内容：基于聚类酸法的搜索引擎研究和原型系统的设计与实 现，先介绍了搜索引擎相关的基本知识，即概念，发展背景，发展趋势等。 然后将聚类知识引入到搜索引擎，并介绍了g o o g l e 提供的w e ba p i ，在此基 础上给出了设计的基本思路，即通过聚类算法自动组织搜索引擎的结果，方便用 户找到需要的信息。我们之所以对搜索引擎的结果进行聚类，而不是对整个w w w 数据信息进行聚类分析，是因为w w w 数据规模巨大而且质量参差不齐，导致信 息与垃圾混杂、知识与谬误共存。搜索引擎在这里起到信息过滤的作用，对搜索 引擎的结果进行聚类更高效，更可行。 最后，介绍了原型系统的设计结构与实现，并用一个实例，说明了聚类的有 效性，证明了将聚类引入搜索引擎的可行性。 j e 立变通太堂亟堂僮论塞 曼i 直 1 3本文的组织 本论文共分六章，各章的主要内容如下： 第一章引言。首先介绍了研究背景，指出随着i n t e r n e t 从计算机互联到w e b 互联，再到网格互联的发展，对信息检索的极大推动作用，说明在互联网迅猛发 展，信息爆炸性增长的年代，研究搜索引擎的重要性，指明了这一课题的研究意 义，最后介绍了本文的研究内容和组织结构。 第二章搜索引擎的概述。介绍了搜索引擎的概念，工作原理以及对搜索引擎 的分类，然后说明了当前搜索引擎发展的热点和趋势。 第三章搜索引擎中聚类算法的特点和要求。首先介绍了文本聚类的概念和聚 类算法的分类，列出了一些流行的常用聚类算法，分析了搜索引擎中应用聚类算 法其自身的特点，最后给出了一种比较合适的聚类算法。 第四章应用文本聚类搜索引擎的体系结构。首先分析了搜索引擎中应用聚类 算法的分析，介绍了g o o g l ew e ba p i 及其应用的格式，最后给出了应用聚类后搜 索引擎的体系结构。 第五章原型系统的设计与实现。根据给出的体系结构，按步由数据获取，文 档清理，确定基类，到最后合并基类，并通过不同界面展示给不同的用户。 第六章结论与进一步工作。对本文进行总结，并提出进一步研究工作的方向。 6 韭童銮通太堂亟堂焦论窒毽塞曼l 鏊援述 2 搜索引擎概述 2 1为什么要有搜索引擎 随着i n t e m e t 的飞速发展，信息爆炸性增长，产生了信息过载( i n f o r m a t i o n o v e r l o a d ) ，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众 信息检索需求的专业搜索网站便应运而生了，可以说而在相当大的程度上，搜索 是面临信息过载的唯一选择。 固民在圈上查找信息构方式 舅胃麦辞柏净畴专重 擅索引上进栉掇索 耐用强讨j 孰畦莽嘲t 兰娃 亍攮索 f 直接藿地雌输人识宇直达同 舅兴瓤于新谁擅瓤辱门户霸站的 攥棠入口l 斟，擅索 叠副属扯必啊鲭如h a 0 1 2 3 或砒m 辱 i 避t o o b a 睫栉栅蜘再寞 t a 。b 口喇细0 bf o o b a r 其他 2 2 搜索引擎原理 懑瀚溺缀湖缨麓瀚溺湖缀囫鬻a 6 8 再 燮麓淄缫黼1 4 2 1 霁 瀚麟渤露粼a 1 7 异 豳图籍珊 潮z ，册 | 1 骺 0 再柏再再舶骺l 睇 比舅f ) 图2 1 网民查找信息方式统计图 搜索引擎是一个对互联网上的信息资源进行搜集整理，然后供你查询的系统， 它包括信息搜集，信息整理和用户查询三部分。 7 j e 廛銮煎太堂亟堂鱼途塞搜塞l 鏊撅述 图2 2w e b 服务体系架构模型 如图2 2 可以看出搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理 好的网页索引数据库。搜索引擎，也不能真正理解网页上的内容，它只能机械的 匹配网页上的文字。真正意义上的搜索引擎，通常指的是收集了互联网上几千万 到几十亿个网页并对网页中的每一个文字( 即关键词) 进行索引，建立索引数据 库的全文搜索引擎。当用户查找某个关键词的时候，所有在页面内容中包含了该 关键词的网页都将作为搜索结果被搜出来。在经过复杂的算法进行排序后，这些 结果将按照与搜索关键词的相关度高低，依次排列。 现在的搜索引擎已普遍使用超链分析技术，除了分析索引网页本身的文字， 还分析索引所有指向该网页的链接的u r l 、a n c h o r t e x t 、甚至链接周围的文字。 所以，有时候，即使某个网页a 中并没有某个词比如“恶魔撒旦”，但如果有别的 网页b 用链接“恶魔撒旦”指向这个网页a ，那么用户搜索“恶魔撒旦”时也能找到网 页a 。而且，如果有越多网页( c 、d 、e 、f ) 用名为“恶魔撒旦”的链接指向 这个网页a ，或者给出这个链接的源网页( b 、c 、d 、e 、f ) 越优秀，那么 网页a 在用户搜索“恶魔撒旦”时也会被认为更相关，排序也会越靠前。 8 韭塞交通太堂亟堂焦论塞攫塞l 塞拖述 由图2 2 可以看出搜索引擎的原理，可以看做三步：从互联网上抓取网页一建 立索引数据库一在索引数据库中搜索排序。 2 2 1从互联网上抓取网页 这个工作是通过网络蜘蛛来完成的，网络蜘蛛即w e bs p i d e r ，是一个很形象的 名字。把互联网比喻成一个蜘蛛网，那么s p i d e r 就是在网上爬来爬去的蜘蛛。网 络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面( 通常是首页) 开 始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻 找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。 如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所 有的网页都抓取下来。 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公 布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十 左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网 页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，如 果按照每个页面的平均大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是 1 0 0 x 2 0 0 0 g 字节，即使能够存储，下载也存在问题( 按照一台机器每秒下载2 0 k 计算，需要3 4 0 台机器不停的下载一年时间，才能把所有网页下载完毕) 。同时， 由于数据量太大，在提供搜索时也会有效率方面的影响。因此，许多搜索引擎的 网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某 个网页的链接深度。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先( 如下 图所示) 。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选 择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方 式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网 络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转 入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比 较容易。两种策略的区别，下图的说明会更加明确。 9 北京变通盔堂亟堂焦i 金室理塞i i 鏊援述 图2 3 网页抓取层次图 由于不可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置了 访问的层数。例如，在上图2 3 中，a 为起始网页，属于0 层，b 、c 、d 、e 、f 属于第1 层，g 、h 属于第2 层，i 属于第3 层。如果网络蜘蛛设置的访问层数为 2 的话，网页i 是不会被访问到的。这也让有些网站上一部分网页能够在搜索引擎 上搜索到，另外一部分不能被搜索到。对于网站设计者来说，扁平化的网站结构 设计有助于搜索引擎抓取其更多的网页。 2 2 2建立索引数据库 由分析索引系统程序对s p i d e r 抓取回来的网页进行分析，提取相关网页信息 ( 包括网页所在u r l 、编码类型、页面内容包含的所有关键词、关键词位置、生 成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进行大量复杂 计算，得到每一个网页针对页面文字中及超链中每一个关键词的相关度( 或重要 性) ，然后用这些相关信息建立网页索引数据库。 2 2 3在索引数据库中搜索排序 1 0 j i 塞銮逼太堂亟堂焦：l 金塞搜塞i 鐾挺适 当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该 关键词的所有相关网页。因为所有相关网页针对该关键词的相关度早已算好，所 以只需按照现成的相关度数值排序，相关度越高，排名越靠前。最后，由页面生 成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。 搜索引擎的s p i d e r 一般要定期重新访问所有网页( 各搜索引擎的周期不同， 可能是几天、几周或几月，也可能对不同重要性的网页有不同的更新频率) ，更新 网页索引数据库，以反映出网页文字的更新情况，增加新的网页信息，去除死链 接，并根据网页文字和链接关系的变化重新排序。这样，网页的具体文字变化情 况就会反映到用户查询的结果中。 互联网虽然只有一个，但各搜索引擎的能力和偏好不同，所以抓取的网页各 不相同，排序算法也各不相同。大型搜索引擎的数据库储存了互联网上几千万至 几十亿的网页索引，数据量达到几千g 甚至几万g 。但即使最大的搜索引擎建立 超过二十亿网页的索引数据库，也只能占到互联网上普通网页的不到3 0 ，不同 搜索引擎之间的网页数据重叠率一般在7 0 以下。我们使用不同搜索引擎的重要 原因，就是因为它们能分别搜索到不同的网页。而互联网上有更大量韵网页，是 搜索引擎无法抓取索引的，也是我们无法用搜索引擎搜索到的。 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 a s e a r c he n g i n e ) 。 2 4全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 8 1 、 f a s t a l l t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。 它们都是通过从互联网上提取的各个网站的信息( 以网页文字为主) 而建立的数 据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返 回给用户，因此他们是真正的搜索引擎。 j e 塞銮道太堂亟堂焦：i 金塞塑塞i l 鏊援述 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的 检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序，并 自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的7 家引擎； 另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 2 4 i目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而已。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名 鼎鼎的y a h o o 雅虎c “】。其他著名懈；o p e n d i r e c t o r y p r o j e c t ( d m o z ) 、l o o k s m a r t 、 a b o u t 等。国内的搜狐、新浪、网易搜索也都属于这一类。 2 4 2元搜索引擎 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将 结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等( 元搜索 引擎列表) ，中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面， 有的直接按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则将结果重新 排列组合，如v i v i s i m o 1 0 1 。 2 4 3非主流搜索引擎 除上述三大类引擎外，还有以下几种非主流形式： i 集合式搜索引擎：如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似m e t a 搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提 供的4 个引擎当中选择，因此叫它“集合式”搜索引擎更确切些。 2 门户搜索引擎：如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但自 身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 3 免费链接列表( f r e ef o r a l ll i n k s ，简称f f a ) ：这类网站一般只简单地滚 动排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目录 索引来要小得多。 由于上述网站都为用户提供搜索查询服务，为方便起见，我们通常将其统称 为搜索引擎。 2 5 搜索引擎的发展方向 搜索引擎己成为一个新的研究、开发领域。因为它要用到信息检索、人工智 能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理 等多领域的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用 户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度 关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。 2 5 1提高信息查询结果的精度 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看 结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、 几百万篇文档，用户不得不在结果中筛选。解决查询结果过多的现象目前出现了 几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正用途， 包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反馈机制，使 用户告诉搜索引擎哪些文档和自己的需求相关( 及其相关的程度) ，哪些不相关， 通过多次交互逐步求精。二是用正文分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类， 使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。三是进行站 点类聚或内容类聚，减少信息的总量。 2 5 2基于智能代理的信息过滤和个性化服务 信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模 型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构) 、用户 1 3 j e 瘟銮逼塞堂亟堂僮j 金塞攮塞l 鏊拯述 模型( 如用户背景、兴趣、行为、风格) 知识进行信息搜集、索引、过滤( 包括 兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提交给 用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供 个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。 2 5 3采用分布式体系结构提高系统规模和性能 搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有 千秋。但当系统规模到达一定程度( 如网页数达到亿级) 时，必然要采用某种分 布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都 可以进行分布：搜索器可以在多台机器上相互合作、相互分工进行信息发现，以 提高信息发现和更新速度；索引器可以将索引分布在不同的机器上，以减小索引 对机器的要求；检索器可以在不同的机器上进行文档的并行检索，以提高检索的 速度和性能。 j e 哀銮逼盍堂亟堂僮i 金塞 搜塞i i 鏊虫鐾差簋洼的遮盐 3 搜索引擎中聚类算法的设计 3 1文本聚类概述 聚类【1 ( c l u s t e r i n g ) 是一个将数据集划分为若干组( c l a s s ) 或类( c l u s t e r ) 的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对 象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。通常 就是利用( 各对象间) 距离来进行表示的。许多领域，包括数据挖掘、统计学和 机器学习都有聚类研究和应用。 文档聚类嘲主要是依据著名的聚类假设：同类的文档相似度较大，而不同类 的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程， 以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处 理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来 越多的研究人员所关注。 文本聚类的应用方面有很多： 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，比 较典型的例子是哥伦比亚大学开发的多文档文摘系统n e w s b l a s t e r 。n e w s b l 髂t e r 将 每天发生的重要新闻文本进行聚类处理，并对同主题文档进行冗余消除、信息融 合、文本生成等处理，从而生成一篇简明扼要的摘要文档； 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。对 用户感兴趣的文档( 如用户浏览器c a c h e 中的网页) 聚类，从而发 现用户的兴趣模式并用于信息过滤和信息主动推荐等服务。 聚类技术还可以用来改善文本分类的结果。 数字图书馆服务。通过s o m 神经网络等方法，可以将高维空间的文档拓扑 保序地映射至j j _ - 维空间，使得聚类结果可视化和便于理解，如s o m l i b 【】系统； 文档集合的自动整理。如s c a r e r g a t h e r 【】是一个基于聚类的文档浏览系统。 而微软的j i - r o n g w e n 等人则利用聚类技术对用户提出的查询记录进行聚类，并利 用结果更新搜索引擎网站的f a q 。 韭立銮通太堂亟堂焦i 金塞 搜塞l 鏊生塞差簋鎏数遮让 3 2 聚类算法的分类 广泛的应用使得聚类分析成为一个很活跃的研究领域，并产生了许多聚类算 法。这些算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和 基于模型方法。 ( i ) 划分方法 划分方法( p a m ：p a r t i t i o n i n gm e t h o d ) 首先创建k 个划分，k 为要创建的划分个 数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改 善划分质量。典型的划分方法包括： k - m e 纽s ，k - m e d o i d s ，c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n ) ； c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o n r a n d o m i z e ds e a r c h ) ； f c m ( f u z z yc l u s t e r i n ga r i t h m e t i c ) ； e m ( e x p e e t a t i o nm a x i m i z a t i o n ) ：不将对象明显地分到么个簇，而是根据表示隶 属可能性的权来分配对象。 ( i i ) 层次方法 层次方法( h i e r a r c h i c a lm e t h o d ) 创建一个层次以分解给定的数据集。该方法可 以分为自上而下( 分解) 和自下而上( 合并) 两种操作方式。为弥补分解与合并 的不足，层次合并经常要与其它聚类方法相结合，如循环定位。典型的这类方法 包括： 第一个是b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 方法，它首先利用树的结构对对象集进行划分；然后再利用其它聚类方法对这些 聚类进行优化。 第二个是c u r e ( c l u s t e r i n g u s i n g r e p r i s e n t a t i v e s ) 方法，它利用固定数目代表 对象来表示相应聚类；然后对各聚类按照指定量( 向聚类中心) 进行收缩。 第三个是r o c k 方法，它利用聚类间的连接进行聚类合并。 最后一个c h e m a l o e n ，它则是在层次聚类时构造动态模型。 1 6 j e 宝銮迢盔堂亟堂僮i 金塞撞塞l 鍪生鏊羞差洼啦篮让 ( i i i ) 基于密度方法 基于密度方法，根据密度完成对象的聚类。它根据对象周围的密度( 如 d b s c a n ) 不断增长聚类。典型的基于密度方法包括：g d b s c a n ，d b c l a s d ， d e n c l u e ( d e n s i t y - b a s e dc l u s t e 血g ) 。 d b s c a n e n s i t - b a s e ds p a t i a lc l u s t e r i n go f a p p l i c a t i o nw i t hn o i s e ) ：该算法通过 不断生长足够高密度区域来进行聚类；它能从含有噪声的空间数据库中发现任意 形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。 o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) ：并不明确产生一个 聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。 ( i v ) 基于网格方法 基于网格方法，首先将对象空间划分为有限个单元以构成网格结构；然后利 用网格结构完成聚类。 s t i n g ( s t a t i s t i c a