（计算机软件与理论专业论文）基于数据挖掘的web权威页面搜索.pdf

萆于数据挖掘的w e b 权威页面搜索 基于数据挖掘的w e b 权威页面搜索 计算机软件与理论 曹王华 印鉴教授 摘要 当在因特网上搜索信息时，通常会使用基于分词的搜索引擎。这些搜索 引擎返回内容与检索相匹配的网页集合作为检索结果。对于主题广泛的检 索，返回结果往往包含大量与我们需求无关的数据。 论文详细描述了一个所设计的搜索引擎结构框架，介绍了两种链接分析 算法，然后针对目前这两种链接分析算法的不足，提出了一个改进算法。最 后建立了一个测试用的搜索引擎，并使用抓取的网页对算法进行了详尽的检 索对比，实验结果表明改进的算法在准确性方面比经典算法有很大的提高。 【关键词】权威页面、搜索引擎、链接分析、数据挖掘 苎主塑塑堡塑塑鉴! 壑壁壅查丝墨 a u t h o r i t a t i v ew e b p a g es e a r c h i n gb a s eo n d a t a m i n i n g c o m p u t e rs c i e n c e c a o w a n g h u a y i n j i a n a bs t r a c t t o d a y ，w h e ns e a r c h i n g f o ri n f o r m a t i o no nt h ei n t e r n e t ，w e u s u a l l y p e r f o r m s a q u e r yt h r o u g h at e r m b a s es e a r c he n g i n e t h e s es e a r c he n g i n er e t u r n al i s to fw e bs i t e sw h o s ec o n t e n t sm a t c h e st h eq u e r ya st h eq u e r y sr e s u l t b u t f o rb r o a dt o p i cq u e r i e s ，s u c hs e a r c h e so f t e nr e s u l ti n h u g es e t o fr e t r i e v e d d o c u m e n t s ，m a n y o fw h i c ha r ei r r e l e v a n tt ot h eu s i nt h i sp a p e r ，f i r s t ，w ed e s c r i b et h ef r a m e w o r ko fas e a r c he n g i n ed e s i g nb y u s ，a n di n t r o d u c i n gt w ol i n ks t r u c t u r ea n a l y s i sa l g o r i t h m s s e c o n d ，w ep o i n to u tt h e s h o r t c o m i n g o ft h e a l g o r i t h m s f o r a n a l y s i s i n g l i n ks t r u c t u r e t oo v e r c o m et h e s h o r t c o m i n gw ed e s c r i b ean e wi m p r o v e da l g o r i t h m t h e nw eb u i l tu pas e a r c he n g i n e a n dt , t s ei tt oc o m p a r et h ei m p r o v e da l g o r i t h m st ot h eo l d o u re x a ms h o wt h a tt h e i m p r o v e da l g o r i t h m si s m o r ea c c u r a t et h a nt h eo l d k e y w o r d s ：a u t h o r i t i e s ，s e a r c he n g i n e ，l i n ka n a l y s i s ，d a t am i n i n g i i 基十数据挖掘的w e b 权威页向搜索 丹i j吾 我们现在已经生活在一个网络化的时代，通信、计算机和网络技术正在 改变整个人类和社会。 一方面，随着信息技术的发展，人们从网络上获取的数据越来越多。让 我们来看一些身边俯拾即是的现象：门户网站y a h o o 由最初的1 0 0 0 多个网 页扩张至现在的近百万的网页；中国门户网站新浪的网页也已经达到数十万 个。然而在现实社会中，人均日浏览阅读时间通常为3 0 4 5 分钟，只能浏 览一个或者两个的门户网站。大量信息在给人们带来方便的同时也带来了 大堆问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是 信息安全难以保证。人们开始提出一个新的口号：“要学会抛弃信息”。人们 开始考虑：“如何才能不被网络上的信息淹没，而是从中快捷、准确的找出 有用的信息、提高信息利用率? ” 另一方面，随着因特网技术的迅速发展以及w e b 网站的广泛应用，人 们积累的网页数据越来越多。激增的数据背后隐藏着许多重要的信息，人们 希望能够对其进行多层次的分析，以便更好地利用这些数据。目前因特网上 的搜索引擎可以提供基于关键词的检索、查询、统计等功能，但无法智能化 的根据检索关键词找出网页数据中与该关键词关系最紧密的部分。缺乏对网 页结构结合网页内容乃至结合网页日志的综合检索预处理的手段，导致了 “检索只能得到形似而神不似”的现象。面对这一挑战，包含数据挖掘的w e b 权威页面搜索引擎技术应运而生，并显示出强大的生命力。 搜索引擎一面世就以其强大的实用性得到了人们的认同。世界上数以亿 计的网民都在通过搜索引擎查找自己需要的信息，著名的搜索引擎g o o g l e 的访问量更是惊人。这些搜索引擎提供的服务极大提高了人们在因特网上查 找信息的效率。为人们的网上信息获取带来了极大的便利。 虽然搜索引擎技术已被广泛接受，但如何提高搜索引擎的检索准确性， 使得搜索引擎工作的更有效率，如何针对现实问题改进搜索引擎技术仍然有 待我们去深入研究。尤其是如何将w e b 数据挖掘与搜索引擎适当的结合起 束。 本文详细介绍了作者在这方面的一些工作，包括一个具有基于数据挖掘 的w e b 权威页面搜索功能的搜索引擎的设计与实现，分析了目前使用比较 广泛的两种w e b 权威页面搜索算法，并针对目前w e b 权威页面搜索算法的 基于数据挖掘的w e b 权威页面搜索 不足，提出了一个改进的算法。且通过大量的实验数据检验该算法。实验表 明，该算法比传统的算法有更高的准确性。 基于数据挖掘的w e b 权威页面搜索 1 1 问题概述 l 1 1 问题描述 第1 章概述 因特网( i n t e r n e t ) 是一个巨大的、分布式的、全球的信息服务中心，并正 以飞快的速度发展。按照2 0 0 0 年4 月在波士顿举行的第5 届搜索引擎年会 的会议报告h 】，我们可以知道现今的网页数目已经超过了1 0 亿。因特网上 的文档是分布的、异构的、无结构或半结构的，人们迫切需要一种工具能快 速准确的从中找出最需要的内容，这就对传统信息处理技术提出了新的挑 战。 搜索引擎正是一种从“爆炸式”增长的因特网信息资源中快速、有效地 发现有价值的资源的工具。近几年来，随着因特网上信息的高速增长，导致 了搜索引擎的出现并迅速成为人们在因特网上查询信息的首要工具。搜索引 擎起源于对单独网站的检索系统，而目前搜索引擎己成为国际上信息处理领 域的最前沿研究方向之一，其目的是希望从海量因特网信息中寻找有用的信 息。 搜索引擎自1 9 9 4 年面世后，迅速成为人们网上搜索的有效工具。根据统 计，大约8 5 的用户使用搜索引擎去定位他们需要的信息；并且，几个著名 的搜索引擎一直都稳定的处于全球访问量最大的前1 0 名网站之列。 目前有许多基于索引的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 权威贞面搜索 1 1 2 目前国内外对该问题的研究 在过去的几十年中，随着条形码在大部分商业产品中的广泛使用，产生 和收集数据的能力迅速提高以及全球信息系统万维网的流行，数据挖掘技术 得到飞速发展并闩益受到人们的关注。其中基于因特网的w e b 挖掘相对针对 数据库和数据仓库的挖掘具有更复杂、动态性更强的特点，对于科研机构和 学者而言更具有挑战性。1 9 9 7 年，在8 “i e e ei n t l c o n f o nt o o l sw i t h a i 上，w e b 挖掘作为数据挖掘中的新课题出现，引来极大关注。在近年的发 展中，随着各大搜索引擎的激烈竞争，w e b 挖掘技术特别是w e b 结构挖掘越 来越受到重视，且与应用的结合愈来愈紧密。 对w e b 结构挖掘技术研究的需求最先来源于搜索引擎的开发，随着第一 个基于w e b 结构挖掘技术的搜索系统c l e v e r 的成功，越来越多的科研机构 和公司投入到w e b 结构挖掘技术的研究中去。目前包括m i ta r t i f i c i a l i n t e l l i g e n c el a b 、s t a n f o r du n i v e r s i t y 、u n i v e r s i t yo fw a s h i n g t o n 、 i b ma l m a d e nr e s e a r c hc e n t e r 、c o r n e l lu n i v e r s i ty 、u n i v e r s i t yo fp a s s a u ( g e m a n y ) 、b e r k e l e yu n i v e r s i t y 、t h eu n i v e r s i t y o fi o w a 、n e cr e s e a r c h i n s t i t u t e 、r e n s s e l a e rp 0 1 y t e c h n i ci n s t i t u t e 以及g o o g l e 等。国内的 北大天网也采用了w e b 结构挖掘技术，国内科研机构中国科学院计算技术研 究所、清华大学等均有此类研究探索。 1 2 本文的工作 本人以中文网页检索为应用背景，基于分布式计算技术开发了一个搜索 引擎。详细描述了它的设计思路与实现，然后针对目前中文网页检索排名算 法的不足之处，提出了一个改进的p a g e r a n k 排名算法，并通过自主开发的 搜索引擎抓取网页构造实验数据，最后使用这些数据对p a g e r a n k 算法和改 进后的p a g e r a n k 算法进行了详尽的比较，并得出实验结论。 1 3 本文的组织 本文章节组织如下： 第l 章简单地介绍一些相关研究背景，主要包括研究目的、意义以及 国内外的相关研究状况。 第2 章介绍了搜索引擎的一些相关知识，包括搜索引擎的产生，范围， 当前国际上的研究动念。 4 某于数据挖掘的w e b 权威页面搜索 第3 章详细描述了所设计的一个搜索引擎，以及实现。 第4 章详细描述了对网页检索排序算法p a g e r a n k 的改进算法，最后给 出了实验结果比较。 基十数据挖掘的w e b 权威页面搜索 第2 章搜索引擎简介 2 1 搜索引擎的产生与发展历史 搜索引擎是因特网技术自然演化的结果。在最近几年里，因特网得到了 长足的发展，不仅成为了企业不可或缺的组成部分，同时也开始进入家庭。 随着因特网的迅猛发展、w e b 信息的快速增加，用户要在因特网的信息海洋 罩查找信息，就象大海捞针一样，因此人们迫切的需要有效的信息发现工具 在因特网上进行导航。目前因特网上主要有2 种信息发现工具：一种是目录 系统，它是由具有专业网页知识的网页编辑人员对因特网上的网页进行精 选，建立相关的索引目录，并提供给用户使用，这种方式提供的网页准确率 高，但是收集所花的时间较长且覆盖的范围有限。另一种是搜索引擎系统， 它通过程序自动的在网上下载和分析网页，建立索引，提供给用户检索，这 种方式覆盖范围较广，自动化程度较高，但是搜索的准确率较低。 1 9 9 0 年以前，没有任何人能搜索互联网。所有搜索弓1 擎的祖先，是1 9 9 0 年由m o n t r e a l 的m e g i l lu n i v e r s i t y 学生a l a ne m t a g e 、p e t e rd e u t s c h 、b i l l w h e e l a n 发明的a r c h i e ( a r c h i ef a q ) 。当时因特网还未出现，a r e h i e 是第一 个自动索引互联网上匿名f t p 网站文件的程序，但它还不是真正的搜索引 擎，只是一个可搜索的f t p 文件名列表：用户必须输入精确的文件名搜索， 然后a r c h i e 会告诉用户哪一个f t p 地址可以下载该文件。由于a r c h i e 深受 欢迎，受其启发，n e v a d as y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了 一个g o p h e r ( g o p h e rf a q ) 搜索工具v e r o n i c a ( v e r o n i c af a q ) 。j u g h e a d 是后来另一个g o p h e r 搜索工具。 由于专门用于搜集下载信息的r o b o t 程序象蜘蛛( s p i d e r ) - - 样在网络间爬来 爬去，因此，搜索引擎的r o b o t 程序被称为s p i d e r ( s p i d e rf a q ) 程序。世界 上第一个s p i d e r 程序，是m i t 的m a t t h e wg r a y 开发的w o r l dw i d ew e b w a n d e r e r ，用于追踪互联网发展规模。刚开始它只用来统计互联网上的服务 器数量，后来则发展为也能够捕获网址( u r l ) 。与w a n d e r e r 相对应， i9 9 3 年1 0 月m a r t i j nk o s t e r 创建了a l i w e b ( m a r t i j nk o s t e ra n n o u c e st h e a v a i l a b i l i t yo f a l i w e b ) ，它相当于a r c h i e 的h t t p 版本。a l i w e b 不使用网 络搜寻r o b o t ，如果网站主管们希望自己的网页被a l i w e b 收录，需要自己 提交每一个网页的简介索引信息，类似于后来大家熟知的y a h o o 。1 9 9 3 年底， 一些基于此原理的搜索引擎开始纷纷涌现，其中最负盛名的三个是：s c o t l a n d 基于数据挖掘的w e b 权威页血搜索 的j u m p s t a t i o n 、c o l o r a d o 大学o l i v e rm c b r y a n 的t h ew o r l dw i d ew e bw o r m ( f i r s tm e n t i o no f m c b r y a n s w o r l dw i d ew e bw o r m ) 、n a s a 的 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 。19 9 4 年4 月，s t a n f o r d 两名博士生，美籍华人j e r r y y a n g ( 杨致远) 和d a v i df i l o 共同创办了y a h 0 0 。 随着访问量和收录链接数的增长，y a h o o 目录开始支持简单的数据库搜索。 因为y a h o o ! 的数据是手工输入的，所以不能真正被归为搜索引擎，事实上 只是一个可搜索的目录。搜索效率明显提高。1 9 9 4 年初，w a s h i n g t o n 大学 c s 学生b r i a np i n k e r t o n 开始了他的小项目w e b c r a w l e r ( b r i a np i n k e r t o n a n n o u n c e st h ea v a i l a b i l i t yo fw e b c r a w l e r ) 。l 9 9 4 年4 月2 0 日，w e b c r a w l e r 疵式亮相时仅包含来自6 0 0 0 个服务器的内容。w e b c r a w l e r 是互联网上第一 个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过u r l 和摘要搜索，摘要一般来自人工评论或程序自动取正文的前1 0 0 个字。d e c 的a l t a v i s t a 是一个迟到者，1 9 9 5 年1 2 月才登场亮相( a l t a v i s t ap u b l i cb e t a p r e s sr e l e a s e ) 。但是，大量的创新功能使它迅速到达当时搜索引擎的顶峰。 a l t a v i s t a 最突出的优势是它的速度。同时a l t a v i s t a 的一些新功能永远改 变了搜索引擎的定义。a l t a v i s t a 是第一个支持自然语言搜索的搜索引擎， a l t a v i s t a 是第一个实现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) ， 用户可以用a l t a v i s t a 搜索n e w s g r o u p s ( 新闻组) 的内容并从互联网上获得 文章，还可以搜索图片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s 、搜索 a c t i v e xo b j e c t s 。a l t a v i s t a 也声称是第一个支持用户自己向网页索引库提交 或删除u r l 的搜索引擎，并能在2 4 小时内上线。1 9 9 8 年1 0 月之前，g o o g t e 只是s t a n f o r d 大学的一个小项目b a c k r u b 。1 9 9 5 年博士生l a r r yp a g e 开始学 习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册了g o o g l e t o n i 的域名，1 9 9 7 年 底，在s e r g e yb r i n 和s c o t t h a s s a n 、a l a ns t e r e m b e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月，g o o g l e 完成了从a l p h a 版到b e t a 版的蜕变。 g o o g l e 在p a g e r a n k 、动态摘要、网页快照、d a i l y r e f r e s h 、多文档格式支持、 地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，象 a l t a v i s t a 一样，再一次永远改变了搜索引擎的定义， 2 2 搜索引擎的功能与结构 搜索引擎用于为用户提供对网页的准确检索结果。作为一种搜索的技 术，搜索引擎通常是先从网上通过u r l 链接搜集、下载网页信息；再对收 集下来的信息分析并建立索引；最后提供一个界面供用户查询并通过索引计 算且返回查询结果。因此搜索引擎主要包括以下功能：1 、网页收集；2 、网 页分析；3 、索引建立：4 、前端检索。 下面将以个典型的搜索的引擎为例，分别介绍搜索引擎的功能及其相 应的结构。 2 2 1 网页收集 网页收集主要完成从因特网上获耿网页和超链接结构信息的工作。因特 网结构是一个以网页为结点，超链接为边的有向图，网页收集的工作可以抽 象为一个有向图的遍历过程。它从用户配置的一些“种子”网页出发，根据一 定的算法，获取新的网页和超链，从而递归的实现不停的从网上收集网页的 功能。从因特网上收集下来的网页和超链接结构信息一般保存在搜集端数据 库或者是专门的存贮文件结构中，等待网页分析部分的程序对这些数据进行 分析。 2 2 2 网页分析 网页分析是根据因特网上数据的特点，按照一定的算法对已经收集获得 的网页和超链接信息进行分析，从中提取和用户检索相关的网页描述信息 ( 如：网页标题、网页关键词、网页的编码类型、网页的文件类型、网页大 小、被其他网页链接次数等) ，并将提取所得的网页描述信息交给索引器建 立索引的过程。这个过程中通常也进行排除相似网页的运算。 2 2 3 索引建立 索引建立主要用于对已经分析好的网页描述信息数据建立索引。网页分 析步骤分析所得的网页描述信息，都是从页面到页面的描述数据的正排表。 索引建立的主要工作就是重新整理、编排这些网页描述信息，对必要的描述 数掘项建立倒排表( 包括关键词到网页的倒排表、站点到网页的倒排表等) ， 为提供用户的检索功能做准备。 2 2 4 前端检索 前端检索用于响应用户的检索请求并跟踪用户的检索行为。当用户提交 一个请求后，前端检索部分从索引中倒排表中通过描述数据项得到相关的网 页信息，再根据一定的相关度算法或者是已经计算好的相关值对这些数据进 行排序，然后组合输出给用户。用户得到结果页面后，会对这些结果进行一 定操作( 如访问结果页面中的某一个网页) ，这些操作信息都由前端检索部分 基于数据挖掘的w e b 权威页面搜索 予以跟踪，并记录在用户数据库中，以备以后提高用户检索的质量。 2 3 当前国际上对搜索引擎的相关研究 搜索引擎自1 9 9 4 年面世后，迅速成为人们网上搜索的有效工具。几个著 名的搜索引擎一直都稳定的处于全球访问量最大的网站之列。因此自1 9 9 8 年到现在这段时期内，对搜索引擎的研发空前的繁荣。在这种情况下，对搜 索引擎技术相关领域的学术研究得到了大学和科研机构的重视。如s t a n f o r d 大学在其数字图书馆项目中开发了g o o g l e 搜索弓1 擎【3 】，在w e b 信息的高效 搜索、文档的相关度评价、大规模索引等方面作了深入的研究，取得了很好 的成果。n e c 美国研究所的s t e v el a w r e n c e 和c l e eg i l e s1 9 9 8 年和1 9 9 9 年连续两年在自然和科学杂志上撰文对搜索引擎技术的研究进行评 述。著名的信息检索会议t r e c 也从1 9 9 8 年开始增加了w e bt r a c k 课题， 以考察w e b 文档与其它类型文档在检索性质上的不同之处，并将测试在大 规模的w e b 库上进行信息检索的算法性能。另外如i e e e 主办的国际万维网 会议、人机交互会议也有越来越多关于搜索引擎技术研究的文章发表。 很多的大公司也对搜索引擎的开发应用投入了大量的精力与人力，经过 近十年的努力，关于搜索引擎的应用的研究已经取得了丰硕的成果。一些公 司已经开发出了既覆盖面广又查询较为准确的搜索引擎，并提供给人们检 索。据不完全统计，目前因特网上已有上百个的商用搜索引擎。如s t a n f o r d 大学的g o o g l e 搜索引擎；挪威f a s t 公司的搜索引擎a l l t h e w e b 等。 搜索引擎的应用很广，现在因特网上访问量最大的网站都是搜索引擎或 者提供了搜索引擎的功能。如s t a n f o r d 大学的g o o g l e 搜索引擎已经收集了 4 2 亿的网页，成为因特网上最受欢迎的搜索引擎。在我国，搜索引擎技术 的研究也引起了学术界和工业界的高度重视，大量的有关搜索引擎的文章已 经在各级期刊，各种会议发表。同时也出现了一些中文搜索引擎。1 9 9 7 年 1 0 月2 9 日，“天网”搜索引擎正式在c e r n e t 上提供查询服务，受到了学术 界广泛好评。2 0 0 0 年1 月，超链分析专利发明人、前l n f o s e e k 资深工程师 李彦宏与好友徐勇( 加州伯克利分校博士) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年8 月发布b a i d u c o m 搜索引擎b e t a 版( 此前b a i d u 只为其它 门户网站搜狐、新浪、t o m 等提供搜索引擎) ，2 0 0 1 年1 0 月2 2 臼正式发布 b a i d u 搜索引擎。b a i d u 虽然只提供中文搜索，但目前收录中文网页超过9 0 0 0 万，是最大的中文搜索引擎。 因特网上的数据最大的一个特点就是数据量巨大，数据增长速度快。因此 搜索引擎如何能够最大限度、最高效的获取网络上的网页，成为搜索引擎的 一个重要研究课题。而超文本链相关的研究也是搜索引擎研究的一个重要的 基于数据挖掘的w e b 权威页面搜索 方向。同时通过对搜索引擎用户检索行为进行统计分析，可以从中获取大量 的有用信息，这些信息可以大大提高搜索引擎结果的准确率，提高检索的质 量，这也是目前搜索引擎研究的一个重点。 l o 基于数据挖掘的w e b 权威页面搜索 第3 章结合数据挖掘的搜索引擎设计 3 1 搜索引擎的开发背景及设计思想 3 1 1 搜索引擎的开发背景 传统的因特网搜索引擎大多数是基于关键字匹配的，返回的结果是包含 查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不能 令人满意，因为有些站点有意提高关键字出现的频率来提高自身在搜索引擎 中的重要性，破坏搜索引擎结果的客观性和准确性；相反的，有些重要的网 页并不包含查询项。同时搜索引擎的分类目录也不可能把所有的分类考虑全 面，并且目前分类目录大多靠人工维护，主观性强，费用高，更新速度慢。 目前对搜索引擎的研究是因特网上的热点，不断的有国外文献报道对搜 索引擎的改进。最近几年来，许多研究者发现，因特网上超链接结构是个非 常丰富且重要的资源，如果能够充分利用的话，可以极大的提高检索结果的 质量。基于这种超链接分析的思想，斯坦福大学的博士研究生s e r g e yb r i n 和l a w r e n c ep a g e 在i 9 9 8 年提出了p a g e r a n k 算法”1 ，同年j k l e i n b e r g 提 出了h i t s 算法3 ，其它一些学者也相继提出了另外的链接分析算法，如 s a l s a ，p h i t s ，b a y e s i a n 等算法。这些算法有的已经在实际的搜索引擎系 统中实现和应用，并取得了突出的效果。可见，在搜索引擎中对超链接结构 进行分析且应用到查询结果排名上已成为搜索引擎研究的一种趋势。 本章描述的搜索引擎就是在这样的应用背景之上，基于超链接分析的思 想开发一个搜集网页并提供相关的检索功能的系统上设计并建立的。 3 1 2 搜索引擎的设计思想 搜索引擎在因特网上有广泛的应用，而当前因特网上有一些开放源代码 的网页搜索器，我们在设计系统的同时也参考了一些开放源代码的网页搜索 器的设计，在实现中也提取了这些网页搜索器的抓取网页的算法，结合在我 们的搜索引擎系统中。用j a v a 编写了相关的网页分析、索引建立、前台检 索等代码，并且将抓取的网页分析后直接存储在数据库中。最核一i i , 的对超链 接进行分析的代码也是用j a v a 来实现的。出于j a v a 具有良好的跨平台性， 基于数据挖掘的w e b 权威页面搜索 我们的搜索引擎也能在多种支持j a v a 虚拟机的平台上运行，如w i n d o w s 、 l i n u x 、u n i x 等。 3 2 搜索引擎系统结构 3 2 1 搜索引擎系统的整体结构 搜索引擎系统主要包括以下子系统：网络扫描子系统、索引创建子系统、 前端检索子系统、数据挖掘子系统以及系统管理子系统和网页以及相关信息 主要存储在数据库中。搜索引擎系统的整体架构如图3 - 1 所示。 网页 网络扫 数据库 系统管理子系统 图3 - 1 搜索引擎系统整体结构图 搜索引擎系统各部分功能描述如下： 1 2 幕于数据挖掘的w e b 权威页面搜索 3 2 2 网络扫描子系统功能及特点 网络扫描子系统主要实现搜索引擎系统从因特网上抓取网页的功能。它 从用户配置的一些“种子”网页出发，使用多线程的程序根据宽度优先的算 法，抓取网页并判断是否是已经抓取过的网页，如果是新的网页则提取该新 网页的超链接，并继续抓取这些提取出来的超链接，从而实现不停的从网上 获取网页的功能。它抓取下来的网页经过分析处理后保存在网页存储的数据 结构中( 可能是数据库、也可能是文件结构) 。在实际上的设计中我们采用了 一些优化程序的方法： 1 ) 采用了高效的线程池技术( t h r e a dp 0 0 1 ) 及线程调度算法，所有的空 闲线程都保存在线程池中，当有新的网页需要扫描时，则调度线程从线 程池中取出线程工作，线程工作完成后又回到线程池中。这样就避免了 每扫描一个网页都要建立一个线程的巨大开销，保证了最快的响应速 度。同时由于对线程数目的控制，系统更加健壮，不易瘸溃。 2 ) 使用了数据库连接池技术( c o n n e c t i o np 0 0 1 ) ，所有的数据库连接都 从连接池中获取，当一个连接用完之后并不会销毁掉，而是放回连接池 中以待别的线程使用，从而使得系统不用频繁建立数据库连接，大大减 少了数据库连接建立所带来的巨大开销，而且极大的提高了速度和效 率。 3 ) 使用r i s 算法，巧妙的通过内存限用阈值来调节内存使用量，使得小容 量网页在处理肘就在内存中进行，速度很快，效率很高，面对大容量网 页就结合硬盘临时存储来处理，这样即使在下载很多大容量网页时也不 至于使系统内存不够用而导致系统崩溃。 4 ) 支持网站的r o b o t s 协议。只下载站点允许下载的内容，保证了站点的 安全性。例如：政府网站中某些机密网页不允许搜索引擎搜索，并写在 了网站的r o b o t s t x t 文件中，扫描程序会自动跳过这些网页不予处理。 对r o b o t s ，t x t 的处理使用了l r u ( 最近最少使用) 算法，减少了网络传输 及磁盘操作、大大提高了系统运行的效率。 5 ) 利用“指纹识别技术”实现了u s t ( u r ls e e nt e s t ) ，c s t ( c o n t e n ts e e n t e s t ) 算法，加快了对相同网址和相同网页内容的判断速度，避免了对 相同网址的重复访问及相同网页的重复处理。 6 ) 使用单线程处理单域名的算法，实现了对网站的“礼貌”访问，减轻了 网站服务器的负担，避免了由于搜索引擎对某个网站的多线程下载而产 生的d o s ( d e n yo fs e r v i c e ) 攻击。而其他的一些类似软件则不能克服 这一难点，当它们多线程同时处理某个服务器时，要么就是被服务器拒 绝连接，要么由于负担太重而导致服务器崩溃。 一一垩王墼塑丝塑堕兰竺壑塑曼亘望室 7 ) 支持d n s 域名解析缓存，当扫描程序要解析某个域名时，它先查询缓存 中是否有该域名对应的i p 地址，若有则直接提取，若无，则再访问d n s 服务器，查询域名对应的i p 。该技术有效的提高了域名解析速度。 3 2 3 索引创建子系统功能及特点 索引文件使得用户搜索速度大大增加，因此，索引创建子系统在搜索引 擎系统中起着关键作用。索引创建子系统为网络扫描程序得到的网页信息建 立索引文件，为检索程序提供检索源。索引创建予系统具有如下特点： 1 ) 通过特殊的索引结构实现了传统数据库不擅长的全文索引机制，将数据 源( 在这个系统中我们数据源是数据库) 中的数据都通过全文索引一一 建立反向索引，而传统的数据库索引在全文检索方面与之根本不可比 拟。传统的数据库中的l i k e 查询操作需要逐个遍历记录进行g r e p 式的 模糊匹配，这比有索引的搜索速度要有多个数量级的下降。 2 ) 可以进行增量( a p p e n d ) 的索引，可以对大量数据进行批量索引，并且可 优化批量索引和小批量的增量索引，大大缩短了索引创建时间，提高了 运行效率。其他很多系统只支持批量的索引，有时数据源有一点增加也 需要熏建索引，效率极低。 3 ) 可灵活的对各种数据源进行处理，如对数据库中的内容建立索引，对各 类文件建立索引。同时还可对多种信息进行索引，索引的单位为文档对 象，文档对象由多个字段组成，索引的字段分为：需要进行分词的索引， 比如：标题，文章内容；不需要进行分词的索引，比如：作者日期字 段。处理各种格式文档的非常灵活。 4 ) 使用了基于词典的最小匹配算法，巧妙解决了中文分词问题，极大地提 高了索引的速度和准确性。 3 2 4 前端检索子系统功能 前端检索子系统主要是为用户提供一个友好的查询w e b 页面，用户通过 在该w e b 页面提交相应的关键词，便可检索出与该关键词相关的结果。在 前端检索子系统中我们使用了基于词典的最小匹配算法，巧妙解决了中文信 息的理解问题，极大地提高了搜索的准确性、快速性和查全率。同时前端检 索子系统也记录下用户访问的日志记录，用于优化索引，改进检索结果。 1 4 基十数据挖掘的w e b 权威页面搜索 3 2 5 数据挖掘子系统 数据挖掘子系统通过对超链接信息以及前端检索同志的挖掘，对网页进 行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。优化了 索引，从而提高检索返回结果的准确率。数据挖掘子系统的结构如图3 - 2 所 示： 3 2 6 系统管理子系统 图3 - 2 数据挖掘子系统内部结构 系统管理子系统主要提供了对整个搜索引擎功能强大、使用简单的管理 界面。该程序中，系统管理员登陆以后可对搜索引擎中所有程序的运行参数 进行配置，控制并调度各个程序的运行，管理词库，查看日志等等a 包括一 个g u i 图形操作的管理界面和一个w e b 操作的管理界面，方便系统管理员远 程操作。 3 2 搜索引擎的应用 随着信息技术的普及和互联网的蓬勃发展，很多企事业单位及政府机构 都建立了自己的局域网，组建了自己的内部网站，然而，信息的膨胀、网页 基于数据挖掘的w e b 权威页面搜索 数量的急剧增加，使得通过浏览网页来查询信息非常不方便。目前有因特网 上有许多开放的搜索引擎供用户查询，方便了用户检索网页信息，但其往往 只针对广域网中公开的网页进行信息搜索，而企事业单位及政府机构往往出 于安全的考虑，很多信息并不对外公开，只供内部浏览，这样，使用公用搜 索引擎查询内部网站信息时将无能为力。因此，企事业单位及政府机构迫切 需要一个针对内部网站的专用搜索引擎系统。 我们拟应用该搜索引擎系统来协助企事业单位及政府机构建立针对内 部网站的专用搜索引擎系统，使内部网的检索和因特网上的检索一样方便。 1 6 基于数据挖掘的w e b 权威页面搜索 4 1w e b 挖掘简介 第4 章算法及实现 对w e b 结构挖掘技术研究的需求最先来源于搜索引擎的开发，随着第一 个基于w 曲结构挖掘技术的搜索系统c l e v e r 的成功，越来越多的科研机构 和公司投入到w e b 结构挖掘技术的研究中去。目前在w 曲挖掘领域开展的 研究主要有：w e b 内容的挖掘、w e b 结构的挖掘、w e b 使用记录的挖掘。 w e b 超链分析算法通常是w 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 b 结构的挖掘( w e bs t r u c t r u em i n i n g ) 。这是从因特网的组织结构和 链接关系中推导知识。u n i v e r s i t yo f p a s s a u ( g e m a n y ) 的m a r c u sr a i t n e r 等 人提出了图形标记语言g m l ，可以描述具有结点和边的基本图形。以此为 基础，r e n s s e l a e rp o l y t e c h n i ci n s t i t u t e 的j o h nr p u n i n 等人提出了符合 x m l 2 0 标准的扩展图形标记语言x g m m l 【l ，它将w e b 页视为结点，将 链接视为边，成功的描述了网络结构，并与传统的图形挖掘算法相结合。i b m a l m a d e nr e s e a r c hc e n t e r 的s o u m e nc h a k r a b a r t i 提出将分析链接及其相关文 字、文本结合，能更有效的实现对w 曲结构的挖掘。 w e b 使用记录的挖掘( w e bu s a g em i n i n g ) 。通过挖掘w e b 日志记录来 发现用户访问w e b 页面的模式。 4 2w e b 超链分析算法 w e b 超链分析算法可以用来提高搜索引擎的查询效果，可以发现因特网 上的重要的社区，可以分析某个网站的拓扑结构，声望，分类等，可以用来 实现文档的自动分类等。目前w e b 超链分析算法主要有两种：基于随机漫游 模型的，搜索引擎g o o g l e 使用的p a g e r a n k 元算法和基于h u b 和h u t h o r i t y 相互加强模型的h i t s ( h y p e r l i n k i n d u c e dt o p i cs e a r c h ) 算法。 4 2 2 p a g e r a n k 超链按分析算法 1 7 基十数据挖掘的w e b 权威页面搜索 p a g e r a n k 超链接分析算法是在搜索引擎g o o g l e 中采用的算法【3 】【2 引。搜 索引擎g o o g l e 最初由是斯坦福大学的博士研究生s e r g e yb r i n 和l a w r e r i c e p a g e 实现的一个原型系统，现在已经发展成为因特网上最受欢迎的搜索引 擎之一。g o o g l e 的体系架构与传统的搜索引擎类似，与传统的搜索引擎最 大的不同处在于它对网页进行了排序处理，使在检索结果中最重要的网页出 现在最前面。这个排序处理是通过p a g e r a n k 超链接分析算法计算出网页的 p a g e r a n k 值，从而由该值决定网页在查询返回结果集中的出现位置： p a g e r a n k 值越高的网页，在结果中出现的位置越靠前。 该算法基于下面2 个前提： 前提1 ：一个网页被多次引用，则它可能是很重要的；一个网页虽然没 有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页 的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威 ( a u t h o r i t i v e ) 网页。 前提2 ：假定用户一开始随机的访问网页集合中的一个网页，以后跟随 网页的向外链接向前浏览网页，不回退浏览，浏览下一个网页的概率就是被 浏览网页的p a g e r a n k 值。 简单p a g e r a n k 算法描述如下：u 是一个网页，l “j 是t l 指向的网页集合， 曰( 甜) 是指向u 的网页集合，( “) 是u 指向外的链接数，显然有( “) = j f ( “) ，c 是一个用于规范化的因子( g o o g l e 通常取值为0 8 5 ) ，则网页u 的 p a g e r a n k 值r ( u ) 计算如下： r ( “) = c r o , ) n ( v ) v b f “、 这就是算法的形式化描述也可以用矩阵来描述此算法，设a 为一个方阵， 行和列对应网页集的网页。如果网页i 有指向网页j 的一个链接，则 以u2 “r ，否则a = 0 。设v 是对应网页集的一个向量，有v = c a v ，v 为 a 的特征根为c 的特征向量。实际上，只需要求出最大特征根的特征向量， 就是网页集对应的最终p a g e r a n k 值，这可以用迭代方法计算。 由于因特网的网页是非结构的，对这些特别的网页，g o o g l e 中采用的 p a g e r a n k 算法也进行了特别处理，如： 2 个相互指向的网页a ，b ，他们不指向其它任何网页，另外有某个网页c ， 指向a ，b 中的某一个，比如a ，那么在迭代计算中，a ，b 的p a g e r a n k 值由 一苎三墼堡丝塑塑兰竺壑堕蔓亘堡鲞 于无法分布出去而不断的累计。如图4 - 1 ： 图4 - 1 为了解决这个问题，s e r g e yb r i n 和l a w r e n c ep a g e 改进了算法，引入了衰 退因子e ( u ) ，e ( u ) 是对应网页集的某一向量，对应p a g e r a n k 的初始值，算 法改进如下： r ( 甜) = e r ( v ) n ( v ) + c e ( u )、7 v e b ( u 其中，j j l = l ，对应的矩阵形式为v = c ( a v + e ) 。 还有些特殊的链接，指向的网页没有向外的链接。p a g e r a n k 计算时， 把这种链接首先除去，等计算完以后再加入，这对原来计算出的网