（计算机应用技术专业论文）基于酉变换的权威页面挖掘算法研究.pdf

， 八 - c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h e l i l li fi iii i i i i iii iii i l y 18 0 8 3 2 9 d e g r e eo f m e n g r e s e a r c ho n a l g o r i t h m o fa u t h o r i t a t i v e p a g em i n i n gb a s e d o n u n i t a r yt r a n s f o r m a t i o n c a n d i d a t e ：s u ny u a n s u p e r v is o r ：p r o f y i ng u is h e n g a c a d e m i cd e g r e ea p p l l e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l l e dt e c h n o l o g y d a t eo fs u b m is s i o n ： j a n u a r y ，2 0 1 0 d a t eo f o r a le x a m i n a ti o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：孙啄 日期：劫o 年弓月侈日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可叼在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： 蜀番 e t 期：为o 年专月f 厂日 翩湓字) 劬年弓月fr 日 广 ， 哈尔滨t 程大学硕士学位论文 摘要 因特网目前是一个巨大、分布广泛、全球性的信息服务中心。它涉及新 闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其它信息服 务。w e b 包含了丰富和动态的超链接信息，以及w e b 页面的访问和使用信息， 这为数据挖掘提供了丰富的资源。w e b 挖掘就是从w e b 文档和w e b 活动中抽 取感兴趣的潜在的有用模式和隐藏的信息。 首先，本文对搜索引擎和w e b 页面挖掘进行了系统性的综述，内容包括 搜索引擎的工作原理、搜索引擎分类和w e b 挖掘分类等方面，并重点分析和 总结了经典权威页面挖掘算法的优缺点。然后，对酉变换理论及乘幂法基础 知识进行了介绍，详细介绍了奇异值分解变换( 简称s v d ) 和截断奇异值分 解变换( 简称t s v d ) ，这些内容是本文研究内容的数学理论基础。 本文研究的核心内容是w e b 挖掘技术，将w e b 内容挖掘与w e b 结构挖掘 两种思想相融合，给出基于截断奇异值分解的权威页面挖掘算法。基于t s v d 的权威页面挖掘算法的处理过程主要分为两个部分，在w e b 结构挖掘基础上 结合页面权重的内容挖掘变换算法，得到一个权重链接矩阵，然后对该矩阵 进行t s v d 变换，得到最终权威页面的排序。已有的文献所采用的权威页面 挖掘算法基本上都是只采用一种挖掘机制，其中基于w e b 内容挖掘的算法较 多，研究也比较成熟，基于w e b 结构挖掘的算法相对较少，两种机制各有优 缺点。在此基础上，本文提出的基于t s v d 权威页面挖掘算法，实质上是尝 试将两种w e b 挖掘方式结合起来，以一种互补的方式，实现权威页面的挖掘， 目的是有效提高查准率和查全率。使用截断奇异值分解变换的目的是能降低 计算量，过滤掉冗余的数学计算，提高搜索响应时间。 最后，借助m a t l a b 仿真工具，对三种权重计算方案进行比较分析。详细 介绍t s v d 算法对典型的静态页面链接拓扑结构的权威页面挖掘过程，将经 产 a c c e s sp a t t e r na n dh i d d e ni n f o r m a t i o nf r o mt h eh u g ec o l l e c t i o no fd o c u m e n t sp l u s h y p e r l i n ki n f o r m a t i o n a c c e s sa n du s a g ei n f o r m a t i o n w e bm i n i n gi sf r o mw e b d o c u m e n t sa n dw e ba c t i v i t i e so fp o t e n t i a li n t e r e s tt oe x t r a c tu s e f u lp a t t e r n sa n d h i d d e nm e s s a g e f i r s t l y t h i sp a p e rm a k e sas y s t e m a t i cs u r v e ya b o u ts e a r c he n g i n ea n dw e b p a g em i n i n g t h i sp a p e rd e p i c t st h ep r i n c i p l eo fs e a r c he n g i n eo p e r a t i o n ，t h e c l a s s i f i c a t i o no fs e a r c he n g i n ea n dw e bm i n i n g m o r e o v e r ，s e v e r a l t y p i c a l s c h e m e sf o rc l a s s i c a la u t h o r i t a t i v ep a g em i n i n ga l g o r i t h ma r er e v i e w e d ，a n dt h e t a x o n o m i e sa red e s c r i b e d m o r es p e c i f i c a l l y ，t h e s es c h e m e sa r ed i s c u s s e di nd e t a i l ， a n da d v a n t a g e sa n dd i s a d v a n t a g e so ft h es c h e m e sa r es u m m a r i z e d t h e n ，u n i t a r y t r a n s f o r m a t i o na n d p o w e ra l g o r i t h mf o u n d a t i o nk n o w l e d g e i si n t r o d u c e d ， e s p e c i a l l y ，t h es v dt r a n s f o r m a t i o na n dt h et s v dt r a n s f o r m a t i o n t h e s ec o n t e n t s a r et h ef o u n d a t i o n so fo u rr e s e a r c h the c o r ec o n t e n to ft h ep a p e ri sw e bm i n i n gt e c h n o l o g y o nt h eb a s i so f c o m b i n i n gw e bc o n t e n tm i n i n gw i t hw e bs t r u c t u r em i n i n g t h et h e s i si n t r o d u c e s an e wa l g o r i t h mw h i c hi sc a l l e da u t h o r i t a t i v ep a g em i n i n ga l g o r i t h mb a s e do nt h e t r u n c a t e ds i n g u l a rv a l u ed e c o m p o s i t i o n t h ep r o c e s s i n go ft h en e wm i n i n g a l g o r i t h mb a s e do nt s v d i sd i v i d e di n t ot w op a r t s i n t h ew e bs t r u c t u r em i n i n g b a s e do nt h ec o m b i n e dw e i g h to ft h ec o n t e n t so ft h ep a g em i n i n gt r a n s f o r m a t i o n a l g o r i t h m ，i tg e t s al i n k w e i g h tm a t r i x t h e nt h ea l g o r i t h m d o e st s v d ，l o w na d v a n t a g e sa n dd i s a d v a n t a g e s b a s eo na b o v ec o n s i d e r a t i o n ，t h i sp a p e r p r e s e n t st s v d - b a s e da l g o r i t h mf o rm i n i n gt h ea u t h o r i t yo ft h ep a g e t oa c h i e v e t h ea u t h o r i t yo ft h ep a g em i n i n g ，t h ep a p e re s s e n t i a l l yt r i e st oc o m b i n et h et w o k i n d so fw e bm i n i n gm e t h o d si nc o m p l e m e n t a r ym a n n e r i ta i m st oe f f e c t i v e l y i m p r o v et h ep r e c i s i o nr a t ea n dr e c a l lr a t e t h ep u r p o s eo fu s i n gt h et r u n c a t e d s i n g u l a rv a l u ed e c o m p o s i t i o nt r a n s f o r m a t i o ni s t or e d u c ea m o u n to fc a l c u l a t i o n ， f i l t e ro u tr e d u n d a n tm a t h e m a t i c a lc a l c u l a t i o n sa n di m p r o v es e a r c hr e s p o n s et i m e f i n a l l y ，w i t h t h e h e l p m a t l a bs i m u l a t i o n t o o l ，t h e t h e s i sc o n d u c t s c o m p a r a t i v ea n a l y s i so ft h r e ek i n d so fw e i g h t i n gc a l c u l a t i o ns c h e m e s t h i sp a p e r d e s c r i b e st h eu s eo ft s v da l g o r i t h mt oa t y p i c a lt o p o l o g yo fs t a t i cp a g e sl i n kt o t h ep r o c e s so fm i n i n gt h ea u t h o r i t yo ft h ep a g e t h es o r t i n gr e s u l t so fc l a s s i c p a g e r a n ka l g o r i t h mw a su s e dt oc o m p a r ew i t ht h er e s u l t so ft s v da l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a tt h ea u t h o r i t a t i v ep a g em i n i n ga l g o r i t h mb a s e do n t s v dh a sb e r e rq u e r yp e r f o r m a n c ea n dh i g h e ra c c u r a c yo fq u e r yt h a nc l a s s i c p a g e r a n ka l g o r i t h m k e yw o r d s ： w e bm i n i n g ；u n i t a r yt r a n s f o r m a t i o n ；t s v dt r a n s f o r m a t i o n ；p a g e r a n k ；w e i g h tc o m p u t i n g ， - 哈尔滨t 程大学硕七学位论文 口罩 目冰 第1 章绪论l 1 1 选题背景和意义“1 1 2 国内外研究现状一l 1 3 论文主要工作一3 1 4 论文结构安排4 第2 章权威页面挖掘相关理论知识5 2 1 搜索引擎”5 2 1 1 搜索引擎工作原理5 2 1 2 搜索引擎分类8 2 2w e b 挖掘及分类1 0 2 2 。1w e b 挖掘定义10 2 2 2w e b 挖掘分类“1 0 2 3 经典页面挖掘算法研究及分析1 4 2 3 1 经典权威页面挖掘算法研究1 5 2 3 2 经典页面挖掘算法分析18 2 4 本章小结1 9 第3 章酉变换及数值分析2 0 3 1 酉变换基础知识2 0 3 1 1 奇异值分解( s v d ) 2 0 3 1 2 截断奇异值分解( t s v d ) 一2 2 3 2 乘幂法2 4 3 3 本章小结2 7 第4 章基于t s v d 的权威页面挖掘算法2 8 4 1 基本概念和定义2 8 广 一 致谢5 9 产 一 哈尔滨t 程大学硕士学位论文 1 1 选题背景和意义 第1 章绪论 随着互联网技术的快速发展，网络信息资源呈现一种爆炸式的增长态势 j ，比如在2 0 0 5 年，g o o g l e 搜索引擎能够遍历到的w e b 网页数量就已经达到 近6 0 亿【2 】。这些网络信息资源在给人们带来丰富知识和极大便利同时，也暴 露出一些亟待解决的问题。其中，最主要的问题表现在这种信息的增长速度 远远超出了人们能够处理他们的能力，动辄千万兆的信息量让用户实际上难 以获取所需的有效信息，更难以对收集来的海量信息进行分析和获取知识【3 】。 针对上述特点，人们在传统信息检索系统的基础上开发出新的w e b 信息 检索系统，就是搜索引擎 4 】。中国互联网络信息中心( c n n i c ) 于2 0 0 6 年7 月1 9 日发布的第十八次中国互联网络发展状况统计报告显示，搜索引擎 已经成为中国最经常使用的三大网络服务之一，调查中网民选择搜索引擎的 比例6 6 3 。而2 0 0 4 年5 月n i e l s e nn o r m a ng r o u p 发布了其2 0 0 4 的w e b 可用性调 查结果，调查结果表明访问搜索引擎己成为8 8 的w e b 会话中的第一步 2 1 。 面对互联网上的海量信息，搜索引擎为人们提供了检索w e b 上相关信息 的方法，搜索引擎对w e b 上的文档进行索引并进行分类，为人们提供一个w e b 内容的层次化的目录结卡勾【5 】；有的搜索引擎对上的页面进行全文索引，提供 基于关键词的检索【6 】。 1 2 国内外研究现状 目前国内外对w e b 挖掘的研究集中在以下两个方面： 一是w e b 挖掘的理论研究：它的目标就是建立发现用户个性化模式的完 整理论体系，建立通用有效的处理模型和适用于w e b 领域的快速高效挖掘算 法【7 1 。近年来提出了许多处理模型、系统框架和原型系统【8 】。例如，通用w e b 日志挖掘模型提出了日志挖掘的完整过程及各个步骤的任务和方法，由批处 户 一 哈尔滨下程大学硕士学位论文 理模块和实时推荐模块组成的个性化网站的体系结构桫j 。 二是w e b 挖掘的应用研究：w e b 挖掘技术在智能的为用户采集相关网页、 提供个性化服务、改善w e b 站点系统性能以及提供智能电子商务等方面的应 用研究已经取得了较大的进展【1o 】。由于服务器日志中详细的记录了用户的浏 览记录，利用w e b 日志挖掘技术就可以从中发现用户浏览模式，据此来改进 站点结构或动态推荐用户感兴趣的页面，从而实现个性化服务j 。w e b 日志 挖掘技术也是w e b 挖掘领域中的一个新的研究热点。如w e b w a t c h e r 系统提出 了一种基于w e b 日志挖掘的个性化服判1 2 】，用户的每一个请求页面都要经过 代理服务器，代理服务器根据用户的兴趣、收集网页的位置和相关性、其他 用户访问过的页面等信息引导用户沿着合适的路径浏览【l3 1 。 w e b 内容挖掘研究目前主要集中在文本分类、文本聚类、自动摘要、文 本可视化等方面【7 j ，出现了像i b m 的i m e l l i g e n tm i n e rf o rt e x t ，s e m i o 公司开 发的s e m i o m a p ，m e g a p u t e r 公司开发的t e x ta n a l y s t 等w e b 内容挖掘工具j 。 w e b 结构挖掘主要集中在p a g e r a n k ，h i t s 算法的研究与改进上。1 9 9 8 年 s t a n f o r d 大学的b r i n 和p a g e 提出tp a g e r a n k 算【3 】。19 9 9 年j o h nk l e i n b e r g 等人 提出t h i t s 算法【”】，由于p a g e r a n k 在搜索引擎g o o g l e q b 的应用并获得了巨大 成功，使得p a g e r a n k 更加成为近几年的研究热点。 欧洲核子研究中心( c e r n ) 研制开发了“方维网”，由于采用超文本 技术、多媒体技术、支持多种网络协议，并可以同时使用f t p 、g o p h e r 等传 统的i n t e m e t j 艮务，以及具有界面友好、使用简便的特点，w e b 推出后很快就 成为发展最快和应用最广的信息服纠1 6 】。 第一代搜索引擎起初分目录式( d i r e c t o r y ) 和全文式( f u l l t e x t ) 两类i 】7 j 。 例如y a h o o l l 最初属于典型的目录式分类结构，将不同的站点、信息按类归 于各个栏目中，用户按栏目查找信息( 有点像g o p h e r ) ，得到所需要的站点、 网络地址、站点提要【博】。而a l t a v i s t a 贝j j 属于全文搜索引擎，此类搜索引擎使 用的技术主要有网络浪人( w e b w a n d e r ) 、蜘蛛( s p i d e r ) 、机器人( r o b o t ) 等，使用自动软件在网上自动抓取、分析被它发现的每个网面，将网页部分 ， 一 哈尔滨工程大学硕+ 学位论文 i i i i i i i i i i i i i i i i i i i i ii ii i 内容( 如关键词) 加入站点数据库中，然后从该网页跳转到与之相关的另一 个网页，再分析，再抓取。如此不断扩张，搜索引擎数据库里的信息越来越 多，越来越丰富。使用此类引擎得到的结果往往是一些单独的、包含用户查 询时所带关键词的方面【1 9 】。 w e b 挖掘必须和其研究手段结合起来 2 0 】。由于涉及到很多的知识领域， w e b 挖掘现在是多个研究方向的交汇点，包括数据库、信息获取、人工智能、 机器学习、模式识别、统计学、自然语言处理等。 1 3 论文主要工作 本文的研究目的在于将截断奇异值分解变换和页面权重计算方案引入到 w e b 页面挖掘中，在w e b l 为容挖掘基础上结合w e b 结构挖掘，通过提出新的 算法以期进一步提高w e b 挖掘的效率，发现用户感兴趣、与查询主题相关度 最大的权威页面。 本文的主要工作有以下几点： ( 1 ) 深入研究搜索引擎的工作原理、w e b 挖掘含义及分类，深入分析了 经典的权威页面挖掘算法，总结经典权威页面挖掘算法的优点和缺陷。 ( 2 ) 对酉变换进行介绍，包括奇异值分解变换和截断奇异值分解变换。 t s v d 变换是本文研究的重点。通过截断奇异值分解变换，将高维数据量降 维，可以大大减小计算量。研究乘幂法，是计算矩阵的主特征值及其相应特 征向量的一种迭代方法。 ( 3 ) 根据w e b 内容挖掘，给出了三种页面权重计算方案，页面局部权重、 关键字全局权重和关键字主题权重，可以提高页面挖掘的查准率。结合网页 链接结构特点，将t s v d 变换和页面权重计算方案引入到w e b 页面挖掘中，提 出了基于t s v d 的权威页面挖掘算法。 ( 4 ) 详细介绍t s v d 算法对典型的静态页面链接拓扑结构的权威页面挖 掘过程，将经典p a g e r a n k 算法的排序结果与t s v d 算法的排序结果对比。 哈尔滨工稃大学硕十学伊论文 i i |ie li ii 1 4 论文结构安排 论文共分5 章，具体结构如下： 第l 章绪论，阐述了论文的研究背景和意义以及国内外研究现状，介绍了 论文的主要研究内容，最后给出论文的组织结构。 第2 章权威页面挖掘相关理论知识，介绍了搜索引擎的工作原理和分类、 w e b 的分类、以及基于w e b 超链接经典的w e b 权威页面挖掘算法，并重点分 析和总结了经典权威页面挖掘算法的优缺点。 第3 章酉变换及数值分析基础知识，详细介绍了奇异值分解变换( s v d ) 、 截断奇异值分解变换( t s v d ) 和数值分析中乘幂法的基本原理及性质。这 些内容是本文研究内容的数学理论基础。 第4 章基于截断奇异值分解的权威页面挖掘算法，引入三种页面权重计算 策略，分别是页面局部权重、关键字全局权重和关键字主题权重。以酉变换 和数值分析为研究的理论基础，提出基于截断奇异值分解的权威页面挖掘算 法，对构造算法进行了详细描述，阐述了算法的步骤，并给出方案实例。 第5 章仿真实验与分析，以m a t l a b 为辅助工具，对三种权重计算方案进行 比较分析。详细介绍t s v d 算法对典型的静态页面链接拓扑结构的权威页面 挖掘过程，将经典p a g e r a n k 算法的排序结果与t s v d 算法的排序结果对比， 最后得出可信结论。 4 哈尔滨工程大学硕十学位论文 第2 章权威页面挖掘相关理论知识 2 1 搜索引擎 搜索引擎技术是随着计算机网络的不断发展而应运而生的技术。随着 i n t e m e t 的飞速发展，互联网蕴涵了全世界丰富的信息资源，从爆炸性增长的 数字信息中迅速获取用户需要的信息变得日益困难【2 1 1 。信息检索的效率和质 量成为一个亟待解决的问题。这为充当这一角色的搜索引擎提供了一个更为 广阔的平台【2 6 1 。 搜索引擎是随着w e b 信息的迅速增加，从1 9 9 5 年开始逐渐发展起来的技 术。据1 9 9 5 年起就开始跟踪网络发展变化的美国互联网监测公司“网器”公 司( n e t c r a f l ) 发布的监测信息，截至至1 j 2 0 0 6 年1 1 月，全球具有域名和内容的 站点数量已经达到1 0 1 亿，并且仍在飞速增长。用户在如此浩瀚的信息海洋 里寻找信息，必然会出现“大海捞针”无功而返【2 7 1 。搜索引擎正是为了解决 这个“迷航”问题而出现的技术。搜索引擎是一种在w e b 上应用的软件系统， 它以一定的策略在w e b 上搜集和发现信息，在对信息进行处理和组织后，为 用户提供w e b 信息查询服务 2 8 1 。 2 1 1 搜索引擎工作原理 搜索引擎的工作原理大致可以分为： 搜集信息：搜索引擎的信息搜集基本都是自动的。搜索引擎利用称为网 络蜘蛛( s p i d e r ) 的自动搜索机器人程序来连上每一个网页上的超连结【3 】。机 器人程序根据网页链到其他中的超链接，就像日常生活中所说的“一传十， 十传百”一样，从少数几个网页开始，连到数据库上所有到其他网页的 链接。理论上，若网页上有适当的超连结，机器人便可以遍历绝大部分网页。 整理信息：搜索引擎整理信息的过程称为“建立索引”。搜索引擎不仅 要保存搜集起来的信息，还要将它们按照一定的规则进行编排【2 9 1 。这样，搜 哈尔滨t 程大学硕士学位论文 索引擎根本不用重新翻查它所有保存的信息而迅速找到所要的资料。想象一 下，如果信息是不按任何规则地随意堆放在搜索引擎的数据库中，那么它每 次找资料都得把整个资料库完全翻查一遍，如此一来再快的计算机系统也没 有用。 接受查询：用户向搜索引擎发出查询，搜索引擎接受查询并向用户返回 资料【3 0 1 。搜索引擎每时每刻都要接到来自大量用户的几乎是同时发出的查 询，它按照每个用户的要求检查自己的索引，在极短时间内找到用户需要的 资料，并返回给用户。目前，搜索引擎返回主要是以网页链接的形式提供的， 这些通过这些链接，用户便能到达含有自己所需资料的网页。通常搜索引擎 会在这些链接下提供- - d , 段来自这些网页的摘要信息以帮助用户判断此网页 是否含有自己需要的内科1 7 j 。 图2 1 搜索引擎工作原理 搜索引擎系统一般由网络蜘蛛( s p i d e r ) 、分词器、索引器、检索器几 部分组成【1 6 1 ，见图2 1 。蜘蛛负责网页信息的抓取工作，一般情况下分词器和 索引器一起使用，它们负责将抓取的网页内容进行分词处理并自动进行标引， 6 哈尔滨工程大学硕十学何论文 建立索引数据库。检索器根据用户查询条件检索索引数据库并对检索结果进 行排序和集合运算，如并集、交集运算，再提取网页简单摘要信息反馈给查 询用户。 网络蜘蛛虽1 w e b s p i d e r ，是一个很形象的名字。把互联网比喻成一个蜘蛛 网，那么s p i d e r 就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地 址来寻找网页，从网站某一个页面( 通常是首页) 开始，读取网页的内容， 找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这 样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互 联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页 都抓取下来【3 。 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目 前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百 分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网 页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处 理技术的问题，如果按照每个页面的平均大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是1 0 0 2 0 0 0 g 字节，即使能够存储，下载也存在问题( 按照一 台机器每秒下载2 0 k 计算，需要3 4 0 台机器不停的下载一年时间，才能把所有 网页下载完毕) 3 2 】。同时，由于数据量太大，在提供搜索时也会有效率方面 的影响。因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓 取的时候评价重要性主要的依据是某个网页的链接深度。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先瞵j 。 广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其 中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方 式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是 指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路 之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在 设计的时候比较容易。 哈尔滨t 程大学硕士学位论文 2 1 2 搜索引擎分类 从基本原理上讲，搜索引擎都包含爬行器、索引器和检索器等三个部分， 但是在实现方式上采用了不同的解决方案，所以它们具有各自不同的特点 【1 8 】。按照搜索引擎采集w e b n 页的方式来划分，目前的搜索引擎大致可以分 为目录式搜索引擎、爬行器式搜索引擎、元搜索引擎和客户搜索引擎等四类。 1 目录式搜索引擎 目录式搜索引擎是以y a h o o 为代表的搜索引擎，它们主要依靠人工维护 网站索引。关于目录式搜索引擎，需要关注的是开放目录( o p e nd i r e c t o r y p r o j e c t ，o d p ) 3 3 】。目录式搜索引擎通过人工浏览各站点的信息，按照一定 的分类规则或分类体系，对网站进行分类。目录式搜索引擎的优势在于内容 比较好的站点更容易被编辑所认同，更容易被索引，所以它们的索引质量比 较高。目录式搜索引擎分类结构清晰、错误较少，比较符合人们的阅读习惯 【1 9 】。缺点是工作人员多、整理周期长、速度慢、人工干预成份多，不能适应 w e b 资源的规模发展。 2 爬行器式搜索引擎 爬行器( c r a w l e r ) 是指可以在w e b 上漫游并按照一定规则自动从w e b 上 下载网页的计算机程序。爬行器式搜索引擎的全部工作基本上由程序自动完 成，人工参与成份很少【3 4 1 。它通过爬行器在网上爬行，将搜索到的网页自动 地加入到本体索引数据库中，用户可以很快从索引数据库查到更新后的信息。 如果某个网站的网页内容更新了，搜索引擎会自动发现这些变化，并很快更 新本地索引数据库，及时反映到用户的检索结果中。它的优势在于自动化程 度高、维护费用低，更强调技术上的创新和提高，也更适合于开展研究工作， 因而成为当前研究的热点。现代搜索引擎一般将上述两种方法结合，形成混 合式搜索引擎。j z l g o o g l e 、北大天网等等，它们在爬行器式搜索引擎的基础 上，提供目录服务。 3 元搜索引擎 哈尔滨t 程大学硕士学位论文 元搜索引擎是指在统一的用户查询界面与信息反馈形式下，共享多个搜 索引擎的资源库为用户提供检索服务的系统。它的最大特点是没有自己的索 引数据库，只提供一个统一的检索界面【3 5 1 。当用户向元搜索引擎提交查询式 时，它将该查询式翻译成相对应的搜索引擎查询式并分别发送出去，接受各 搜索引擎的检索结果，按照一定的规则，将结果返回给最终用户。元搜索引 擎的优势在于：用户不需要记忆不同搜索引擎的地址和查询语法；查询多个 索引数据库，可以大大提高查询结果的覆盖度；不用维护庞大的索引数据库， 而将工作重心放在检索结果的整合上，提高查询的准确度。但是元搜索引擎 的网络资源开销比较大，从多个搜索引擎返回的结果中常常有很多重复信息， 相关度排序十分困难。 4 客户搜索引擎 客户搜索引擎，是把搜索机器人的爬行算法内置于客户端，从已知w e b 网页出发，沿着网页中的超链，不断发现更多的网页，重复上述动作直至满 足结束条件1 36 i 。客户搜索引擎不需要第三方的搜索接口，可以使用任意的本 地搜索爬行器，且不一定要通过w e b 浏览器。这就意味着客户搜索引擎可以 方便地提高用户接口性能；同时，由于是实时搜索，搜索结果中基本不存在 无效连接的信息，但存在的突出问题是搜索速度很慢，如果每个w e b 客户程 序都使用它们自己内嵌的搜索引擎，这将带来很大的网络负载和服务器负载， 导致i n t e r n e t 不堪重负，因此难以在较大范围内推广使用。客户搜索引擎更适 合建立具有交互功能的个性化搜索服务。 这四种搜索引擎各有优缺点，在不同的领域有不同的应用【4 6 】。目录式搜 索引擎和爬行器式搜索引擎现在己经紧密结合在一起；没有搜索引擎也就没 有元搜索引擎；客户搜索引擎则更强调与用户的交互和个性化定制。它们互 为补充，不会出现一种搜索引擎完全取代另一种的可能。 9 哈尔滨丁程大学硕士学位论文 2 2w e b 挖掘及分类 2 2 1w e b 挖掘定义 数据挖掘，从大型数据库的数据中提取人们感兴趣的知识，这些知识是 隐含的事先未知的、潜在有用的信息，提取的知识可以表示为概念( c o n c e p t ) 、 规则( r u l e ) 、规律( r e g u l a r i t y ) 、模式( p a t t e r n ) 等形式【3 7 1 。 上述定义把数据挖掘的对象仅定义为数据库，所以传统的数据挖掘技术 所处理的信息主要包括数据库中的结构化信息。但是随着对w e b 网页信息处 理要求的出现，数据挖掘技术也开始逐渐应用到互联网的海量w e b 信息上， 包括大规模的文本信息和多媒体信息 9 】。这种利用数据挖掘技术对互联网 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 9 ，而w e b 挖掘的对象则是大量、 异质、分布的w e b 网页文档，非结构化现象相当明显。 2 2 2w e b 挖掘分类 w e b 挖掘建立在对w e b 资源的有效获取上，按照挖掘客体的不同，可以 将w e b 挖掘分为三类，见图2 2 - w e b l 内容挖掘( 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 ) 【4 0 1 。 前两者可以合并为广义w e b l 为容挖掘，而w e b 使用挖掘也称为w e b 日志挖掘。 1 0 哈尔滨 二程大学硕士学伊论文 图2 2w e b 挖掘分类 1 w e b 内容挖掘( w e bc o n t e n t m i n i n g ) w e b 内容挖掘从总体上分为基于文本的挖掘和基于多媒体的挖掘两种形 式。文本挖掘是现在w e b 内容挖掘的主要组成部分之一，最早是由f e l d m a n 和d a g a n 首先提出来的。其中，w e b 文本信息挖掘主要是指从网页文档内容或 其描述中抽取有价值知识的过型4 1 1 。w e b t 为容挖掘指对w e b 大量文档集合的 内容进行总结、分类、聚类、关联分析以及利用w e b 文档进行预测。 w e b 内容挖掘的方法主要有基于智能a g e n t 的方法和基于在线分析挖掘 的数据库方法。 ( 1 ) 基于智能a g e n t 方法 基于智能a g e n t 的w e b 挖掘涉及到智能a g e n t 技术。一般来说，基于a g e n t 的w e b 挖掘有三大类：智能搜索a g e n t ，信息滤波和分类a g e n t ，个性化w e b 服务a g e n t 。 目前已经出现的几种智日r “, a g e n t ，利用领域的特征信息和个性化模式，组 织、解释己经发现的信息。例如，h a r v e s t 、f a q f i n d e r 、信息m a n i f o l d 和p a r a s i t e 系统利用对于特定文档的预定义的和领域的特征信息，或者利用信息源的编 哈尔滨工稗大学硕十学位论文 码信息，检索并解释文档。 信息滤波和分类a g e n t 示l j 用各种信息检索技术和超文本标记的特点，实现 自动信息检索、过滤和分类【4 2 1 。例如，h y p u r s u i t 利用体现超链接结构和文档 内容的语义信息，对超文本进行层次聚类，并且结构化信息空间，y s m a r e k 将层次聚类技术和用户交互信息结合起来，对w e b 文档集合进行概念重组。 个性化w e b 服务智能a g n e t 通过获取或学习用户的爱好或兴趣，发现匹配 用户兴趣的w e b 信息源，甚至可以发现其它具有相似兴趣的用户。目前已经 知道的例子有w e b w a t c h e r ，p a i n t 等。 ( 2 ) 基于数据库的方法 对于w e b 挖掘来说，数据库方法主要用于集成和组织异质、半结构化的 w e b 数据，使之成为结构化的多层数据集，如关系数据库【4 3 1 。然后，利用标 准数据库查询机制和数据挖掘技术访问和分析这些数据。 w e b 内容挖掘的基本技术是文本挖掘，也可以认为是基本的w e b 信息检 索( i n f o r m a t i o nr e t r i e v a l ，i r ) 和信息抽取( i n f o r m a t i o ne x t r a c t i o n ，i e ) 的延续。 w e b 内容挖掘主要应用【4 9 】： ( 1 ) 关键词的检索，改进传统的搜索引擎； ( 2 ) 挖掘项目关联，不是将注意力放在孤立的词的相同活相似信息上， 而是聚焦在页面的信息之间的关联信息挖掘上，从而避免传统的信息检索技 术带来的信息不精确和信息量过大等问题上； ( 3 ) 把半结构化的w e b 信息重构得更结构化一些； ( 4 ) 相似性检索，找出内容相似的网页； ( 5 ) 信息分类和聚类：利用数据挖掘的分类和聚类技术实现页面的分类。 一种可行的方法就是将网页的词取出后，对词进行聚类或分类，从而对网页 进行聚类或分类： ( 6 ) 自然语言处理：揭示自然语言处理技术中的语义； ( 7 ) 根据用户经常访问的网页的内容，得到用户的喜好，提供个性化的 服务，或将用户进行聚类。 1 2 哈尔滨工程大学硕+ 学位论文 2 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 按照挖掘的客体可以将w e b 结构挖掘分为网页外部结构挖掘和网页内部 结构挖掘。 网页外部结构挖掘主要是针对网页间存在的链接进行分析，从而发现网 页间链入和链出的规律，并以此得到网页重要性的客观性指标。网页的链入 网页数越高，说明该网页的重要性越高【4 7 】。 网页内部结构挖掘主要是指按照页面内部不同板块的组织方式，挖掘出 蕴含在页面内部的结构信息】。从页面内部的组织上看，网页设计者为了人 们浏览的方便，常常将页面划分成多个语义不相关的部分，各个部分构成了 网页中的不同版块，在每个版块内，各条记录格式是相同的。通过对页面内 部结构进行挖掘，可以按照主题重新组织网页内容，也可以针对特定的用户 需求提取网页的特定版块，如面向主题及个性化的信息采集，基于版块粒度 的w e b 文档分类、聚类和信息抽取，基于内容的w e b 文档信息重构等。 w e b 结构挖掘挖掘的数据源：w e b 页面超链接关系。 对w e b 页面之间的连接结构进行挖掘以得出有用的知识是提高检索效率 的重要手段。w e b 页面的链接类似学术上的引用，因此一个重要的页面可能 会有许多页面的链接指向它【5 1 1 。 3 w e b 使用挖掘( w e bu s a g em i n