（计算机应用技术专业论文）基于xml的web数据抽取技术的研究.pdf

摘要 w e b 作为一个全球化信息空间，蕴含着巨大的潜在价值。尽管目 前己对w e b 数据抽取技术进行了大量的研究工作，但是现有的技术还 不能让用户满意。x m l 为w e b 提供了一致的数据模型和描述语言，已成 为表示w e b 中多样性数据的事实标准。 论文通过对w e b 数据抽取步骤的分析和研究，针对目前存在的问 题，提出一种快捷、实用的基于x m l 的w e b 数据抽取技术的解决方案， 并对其中涉及的关键技术，如搜索策略、转换算法、抽取方法等方面 进行深入研究，期望为推进本领域的发展作一点贡献。 论文的主要内容包括如下几个方面： 1 提出了一种应用于小范围w e b 的搜索策略：改进的h i t s 算法。 该算法针对小范围w e b 的链接结构特点，构造间接链接，并且根据用 户访问的频率对链接加权。改进的算法使得小范围w e b 的链接结构更 接近万维网的链接结构，同时链接加权输入结合了用户的反馈。理论 和实验证明算法是正确的。 2 提出了一种基于栈结构的h t m l 至i j x m l 的转换算法。通过栈结构 的概念，有效地将h t m l 格式转换为x m l 格式。简化了数据抽取工作， 方便地形成x m l 文档，为处理x m l 文档、抽取出适当的数据作了铺垫。 3 提出了x m l 数据抽取的健壮性标准，将该标准运用于x m l 数据抽 取的区域定位和映射合并中，并分别给出了符合健壮性标准的合适方 法，从而提高了数据抽取的效率。 4 原型系统的实现。根据上述三点的研究结果，结合数据抽取技 术、x m l 技术矛n j a v a 技术，提供了一个快速、通用的基于x m l 的w e b 数 据抽取原型系统，具有良好的适应性和可移植性。 关键词数据抽取，x m l 技术，链接结构，栈，健壮性 a b s t r a c t a st h eg l o b a li n f o r m a t i o ns p a c e w 色bc o n t a i n sl a r g ep o t e n t i a lv a l u e m u c hr e s e a r c hh a sf o c u s e do nt h es t u d yo fw e bd a t ae x t r a c t i o n ，w h i l ei t s c u r r e n ts t a t u si ss t i l lf a rf r o ms a t i s f a c t i o no fw e bu s e r s x m eh a s b e c o m et h es t a n d a r dt or e p r e s e n td a t ai nw e ba n di tp r o v i d e sau n i f o r r n d a t am o d e lf o rw e bd a t a t h ed i s s e r t a t i o nr e v i e w st h es t a t eo fw e bd a t ae x t r a c t i o na n d p r e s e n t saf a s ta p p l i c a b l ew e bd a t ae x t r a c t i o nm e t h o db a s e do nx m l t h ef u r t h e rs t u d yi sm a d ef o rs o m ek e yt e c h n o l o g i e s ，s u c ha ss e a r c h s t r a t e g y t r a n s f o r m a t i o na l g o r i t h ma n de x t r a c t i o nm e t h o d w ew i s h t o m a k es o m ec o n t r i b u t i o n sf o rd a t ae x t r a c t i o n t h em a i nc o n t r i b u t i o n so ft h i sp a d e ri n c l u d et h ef o l l o w i n g s 1 t h ed i s s e r t a t i o np r e s e n t sam o d i f i e dh i t sa l g o r i t h mi ns m a l l w e bs e a r c h a c c o r d i n gt ot h ec h a r a c t e r i s t i co fl i n ks t r u c t u r e ，w e c o n s t r u c ti m p l i c i tl i n k si ns m a l lw e b ，a n dw e i g h tl i n k sa c c o r d i n gt oh o w o f t e nt h e yw e r ea c c e s s e d t h en e wl i n ks t r u c t u r eo fas m a l lw e bi sc l o s e t ot h a to f t h eg l o b a lw e b a n dw e i g h tl i n k sc o m b i n ew i t hu s e r s f e e d b a c k t h e o r ya n de x p e r i m e n ts h o wt h a tt h em o d i f i e da l g o r i t h mi sc o r r e c t 2 as t a c k b a s e dh t m lt ox m 凡t r a n s f o r m a t i o na p p r o a c hi sp u t f o r w a r d i ts i m p l i f i e sd a t ae x t r a c t i o na n dg e t sr e a d yf o re x t r a c t a p p r o p r i a t ed a t a 3 t h ec r i t e r i o no fr o b u s td a t ae x t r a c t i o ni nx m li sp r o p o s e d t h e c r i t e r i o ni sa p p l i e di nx 匝d a t ae x t r a c t i o n ：i o c a t i o ns p e c i a la r e aa n d m a p p i n gm e r g i n gd a t a g o o dm e t h o d sa r ep r o v i d e df o re a c h t h er e s u l t s s h o wt h a tt h em e t h o d sa r ee f f e c t i v e 4 t h ep r o t o t y p ei sc o m p l e t e d d a t ae x t r a c t i o n ，x m la n dj a v aa r e c o m p r e h e n s i v e l yu t i l i z e di nt h ep r o t o t y p eb yc o m b i n i n gt h o s et h r e e t h e o r i e s t h ep r o t o t y p ep r o v i d e saf a s tg e n e r a lw 曲d a t ae x t r a c t i o n s o l u t i o nb a s e do nx m l i th a sg o o da d a p t b i l i t ya n dp o r t b i l i t y k e yw o r d sd a t ae x t r a c t i o n ，x m 吐，1 i n ks t r u c t u r e ，s t a c k ，r o b u s t n e s s 叼 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论义中特别加以标注和致谢 的地方外，沦文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名墓担铛日期：堕年兰月兰口 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位沦文被金阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其他手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位沦文。 作者签名：蚴导师签名三巡日期：堕年旦月旦日 硕士学位论文 第一章绪论 1 1背景 第一章绪论 1 11 数据抽取概念 论文提出的数据抽取概念源于数据仓库。数据仓库是在企业管理和决策中 面向主题的、集成的、与时间相关的、不可修改的数据集合。数据仓库并没有 严格的数学理论基础，也没有成熟的基本模式，且更偏向于工程，具有强烈的 工程性。因此，在技术上人们习惯于从工作过程等方面来分析，并按其关键技 术部份分为数据的抽取、存储与管理以及数据的表现等三个基本方面。 在数据仓库中，数据的抽取是将数据置于数据仓库环境的第一步，是数据 进入仓库的入口。抽取”1 意味着要先读取和了解元数据，再复制数据登台区所需 要的部分数据，以方便进一步处理。由于数据仓库是一个独立的数据环境，它 需要通过抽取过程将数据从联机事务处理系统、外部数据源、脱机的数据存储 介质中导入到数据仓库。数据抽取在技术上主要涉及互连、复制、增量、转换、 调度和监控等方面。数据仓库中的数据并不要求与联机事务处理系统保持实时 同步，因此数据抽取可以定时进行，但多个抽取操作执行的时间、相互的顺序、 成败对数据仓库中信息的有效性则至关重要。 根据数据仓库中数据抽取的步骤，论文将数据抽取定义为：搜索整个数据 源，使用某些标准选择合乎要求的数据，并把这些数据传送到目的文件中。 112w e b 为数据抽取带来的挑战 w e b 起源于1 9 9 0 年，创始人是欧洲粒子物理研究所的t i mb e m e r s l e e ”1 等 人，最初是为了便于世界各地的物理学家交流研究成果。w e b 将计算机网络技术 和超媒体技术融合起来，在很短时间内就被各个领域的用户广泛接受，信息量 呈指数式增长。w e b 上有海量的数据信息，怎样对这些数据进行复杂的应用成了 现今数据库技术的研究热点。 相对于传统的数据库中的数据而言，w e b 上的数据主要有以下特点： ( 1 ) 半结构化。所谓半结构化是相对于完全结构化的传统数据库的数据而 言。数据没有严格的结构模式，并且面向显示的h t m l 文本无法区分数据类型等。 ( 2 ) 非规范化。w e b 的开放性和用户的随意性使得w e b 上的数据几乎是无所 不包，含有不同格式的数据( 文本、声音、图像等) 。 硕士学位论文 第一章绪论 ( 3 ) 难以自动处理。由于格式及内容表示的随意性使得机器很难进行自动处 理。 正是由于w e b 数据的这些特点，传统的数据库技术显得无能为力，面向w e b 的数据抽取比面向单个数据仓库的数据抽取要复杂得多。而w e b 上不断涌现的 大量新应用( 例如电子商务、供应链等) ，又迫使人们对w e b 上的数据实施有效 的管理，以便满足越来越多的w e b 应用需求。 i 2x m l 为w e b 数据抽取带来新的希望 当前，w e b 是世界上最丰富和最密集的信息来源，h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ) 。是w e b 上信息的主要载体。无论在公司、政府机构、还是个人，w e b 和它最初用以表达信息的方法h t m l 都获得了圆满的成功。然而，h t m l 并不完美。 它的缺点包括： ( 1 ) h t m l 只是一种表达技术，不能揭示h t m l 标记的含义。 ( 2 ) 标准的h t m l 规定了固定数据的标签集合，不允许用户定义自己的扩展标 签。 ( 3 ) h t m l 使得服务器端要处理的数据量过大。 ( 4 ) 标准的h t m l 标记对于表现w e b 页面的动态性，显得力不从心。 万维网联盟( w o r l dw i d ew e bc o n s o r t i u m ，简称w 3 c ) 审视了h t m l 的缺点，制 定的x m l 规范已经成为一个研究热点，x m l 是网络应用发展的产物，是w 3 c 推荐的 取代h t m l 的网络语言。很多学者认为，x m l 作为一个手段和方法，推动着网络技 术和社会进步。 x m l 的提出，主要基于以下目的： ( 1 ) 国际化的信息发布的标准，可以独立于各种平台和系统。 ( 2 ) 允许各行各业定义平台独立的协议规范来交换数据。 ( 3 ) 实用化。用户可以通过方便简单的软件来处理数据，不需要昂贵的专业 软件。 ( 4 ) 个性化。允许用户以自己喜欢的方式显示数据，数据内容与显示方式分 离。 ( 5 ) 提供元数据。比如信息的来源和其他说明信息等，都是关于数据的解释 和描述。 由于x m l 自描述的灵活性和可扩展性，越来越多的系统采用x m l 作为建模语言 和接口语言，各行各业提出了基于x m l 的专业标准，下一代因特网也把x m l 作为 w e b 的描述语言和接口语言。 2 硕十学位论文第一章绪论 因此，x m l 技术为基于w e b 的数据抽取技术的研究带来了新的希望，对新一 代w e b 技术的发展及w e b 信息的开发利用，具有重要的理论意义和广阔的应用前 景。 1 3 基于x m l 的w e b 数据抽取技术的研究 基于x m l 的w e b 数据抽取技术已经受到数据库界、信息检索领域、网络领域等 学者的注意，大部分研究关注于w e b 页面搜索算法的研究、h t m l 包装器( w r a p p e r ) 的设计、x m l 数据的抽取等，在这些方面，学者们都进行了不同程度的深入研究。 我们把这些研究归纳为以下几个点： ( 1 ) 获取w e b 数据源：主要研究如何从大量的己存在的w e b 页面中获取用户想 要的数据源。按照用户搜索范围的不同可以分为两类：广域w e b 搜索方式和小范 围w e b 搜索方式。广域w e b 搜索方式是发生在整个w e b 的开放集合中，通常是使用 链接分析技术”1 ，例如，著名的h i t s ( h y p e r t e x ti n d u c e dt o p i cs e l e c t i o n ) 算法和g 0 0 9 l e 中的p a g e r a n k ”1 算法，以及它们的衍生算法，包括i b ma l m a d e n 实 验室开发的a r c ( a u t o m a t i cr e s o u r c ec o m p i l a t i o n ) 系统”1 等。小范围w e b 搜索 方式发生在网络中一个闭合子空间，常见的情况是在一个站点内搜索或者 i n t r a n e t 搜索，应用于小范围w e b 搜索的产品生产方兴未艾，例如，a 1 t av i s t a “0 1 、b e r k e l e y 的c h a c h a 3 搜索引擎等。然而人们多数使用的是广域w e b 搜索引 擎，由于其并不能成功地运用于小范围w e b 搜索，所以对于小范围w e b 搜索的研1 究已提到了日程上来。 ( 2 ) 基于x m l 的w e b 数据转换：由于h t m l 在w e b 中现今所占据的重要地位，主 要讨论如何将h t m i 。数据源页面转换为相应的x m l 文档。通常是使用w e b 包装器将 h t m i ，数据转换为结格式构化的x m l 文档。编写包装器的方法经历了手工编写、半 自动化生成和现在正在研究的全自动化生成三个阶段。手工编写灵活性差，典 型的系统有t s i m m i s “”和a r a n e u s “。半自动化生成采用人机交互方式，典型的 系统有w 4 f “、x w r a p ”、l i x t o “6 3 等。但是，在这些技术中都要求不仅要由用户 提供标识样本集，还要有一定的先验知识，因此，还需要进行改进。近年来提 出的全自动化生成方式大大减轻了用户的工作量，典型的系统有r o a d r u n n e r ” s d e x a l g “”算法。虽然使得转换工作取得了较大的进步，但是这两种方法都存在 着一定缺点。 ( 3 ) x m l 数据抽取：在x m l 数据抽取技术中，一个x m l 文档对应一个x s l 文件， 即使新的x m l 文档只与前一个己转换的x m l 文档存在细微的差别，也需要重写一 个x s l 文件，因而普遍缺乏修改适应性，对于已存在的x m l 文档转换成新的x m l 文 硕士学位论文 第一章绪论 档时不能很好地兼容，并且转换程序可读性差等等，这些都是现行x m l 数据抽取 技术的不足。 不难发现，在上述的基于x m l 的w e b 数据抽取技术的研究中，涉及到网络、 数据结构、信息搜索技术等领域。 1 4 研究方案 14 1 研究目标 通过对w e b 数据抽取步骤的分析以及针对目前存在的问题，本文提出一种快 捷、实用的基于x m l 的w e b 数据抽取解决方案，并对其中涉及的关键技术( 例如 搜索策略、转换算法、抽取方法等) 进行了深入研究，期望为推进本领域的技 术发展作一点贡献。 1 4 2 研究思路 论文的基本研究思路是以w e b 数据抽取为基础，根据x m l 文档的特点，结合 信息检索、网络、数据结构等相关技术，提出一种基于x m l 的w e b 数据抽取的方 案。围绕提出的解决方案，论文着重研究了三个关键技术：一是w e b 数据源的获 取策略：二是h t m l 至e i x m l 的转换技术：三是健壮的x m l 数据抽取方法。最后根据 上述研究结果，还实现了一个原型系统。本文的研究思路如图卜1 所示，给出了 基于x m l 的w e b 数据抽取研究的关键步骤。 多次运行 图1 - 1 数据抽取过程 1 4 3 研究内容 鉴于人们往往是直接进入到某些特定的站点进行站点内进行搜索，因而小 范围w e b 搜索数据源的重要性同益增加，论文对小范m w e b 搜索数据源策略进行 了详细的阐述，并在前人的算法上作了进一步的改进。论文针对当前获取的w e b 4 硕士学位论文 第一章绪论 数据源中大多数都是i - t t m l 格式的情况，提出了一种将半结构化数据的h t m l 文档 转换为结构化数据的x m l 文档的新算法。对于x m l 数据抽取技术的不足，论文也 制定了相应的健壮性标准，并给出了符合健壮性标准的合适方法。最后根据论 文的研究结果，使用相关技术开发了一个快速原型系统。论文的工作主要包括 以下几点内容： ( 1 ) w e b 数据源的获取策略：为了获取更多明确的信息，人们往往是直接进 入到i n t e r n e t 的一些特定站点进行站点内进行搜索，因而一般是进行小范围的 w e b 搜索策略。因为小范围w e b 链接结构的特殊性，所以当不加修改地将传统的 链接分析算法( 女n h i t s 算法) 应用于小范围w e b 搜索时，并不达到很好的效果。 对h l l 、s 算法提出了改进：第一，针对小范围w e b 的链接结构特点，构造间接链接： 第二，根据用户访问的频率对链接加权。改进的算法使得小范围w e b 的链接结构 更接近万维网的链接结构，同时链接加权输入结合了用，- 的反馈。理论和实验 表明该算法是合理和有效的。 ( 2 ) h t m l 到x m l 的转换算法：当f i 日w e b 信息大多数都是 i t m l 格式的，w e b 数据 抽取就是针对h t m l 格式的页面。结合x m l 的特性，提出了一种基于x m l 的h t m l 转 换算法，有机结合栈的概念，消除了h t m l 格式中不严格语法，为下一步的x m l , 数 据抽取提供了可用的格式。 ( 3 ) 基于x m l 的数据抽取方法：对于现 ? x m l 数据抽取方法存在的问题，给出 了解决手段。制定了x m l 数据抽取的健壮性标准，并对数据抽取的两个步骤区域 定位和映射合并，分别选择了符合健壮性标准的合适方法。 ( 4 ) 原型系统的丌发：结合搜索策略、转换算法和抽取方法的研究结果，使 用j s p 、j a v a b e a n 和w e b l o g i c 等相关技术，开发了一个快速原型系统。 综上所述，论文研究的重点是针对基于x m l 的w e b 数据抽取存在的问题，结 合计算机各领域的相关技术，为其提供可行的方案，并对其中涉及的关键技术， 例如搜索策略、转换算法、抽取方法等方面，展开了深入的研究，对本领域的 技术发展进行了探索。 14 4 研究意义 基于x m l 的w e b 数据抽取技术的研究将新一代的w e b 信息表达语言x m i 应 用于数据抽取，对w e b 数据获取、数据转换、数据抽取与数据映射合并提出新的 方法，并实现个快速通用的数据抽取原型系统，从而为w e b 信息集成、智能信 息处理、数据源间的相互操作、客户应用的快速构建等相关w e b 应用提供一种获 取和利用w e b 信息的通用平台。 5 硕士学位论文 第一章绪论 1 5 创新之处 论文中有创新的研究成果主要体现在以下几点： ( 1 ) 提出了一种应用于小范围w e b 搜索的改进h i t s 算法。结合小范围w e b 的链 接结构特点，通过挖掘用户访问模式而构造间接链接，并且对输入矩阵进行加 权。矩阵理论和实验都证明了改进的h i t s 算法是可行的。该算法为小范m w e b 搜 索提供了一种新的、有效方法。 ( 2 ) 提出了一种基于栈结构的h t m l 至i j x m l 的转换算法。通过数据结构中的栈 结构的概念，有效地将h t m l 格式转换为x m l 格式。简化了数据抽取工作，方便地 形成x m l 文档，为处理x m l 文档，并抽取出适当的数据作了有效的铺垫。 ( 3 ) 制定了进行健壮性x m l 数据抽取的标准，并将该健壮性抽取标准运用于 x m l 的数据区域定位和文档映射合并中。使得数据区域定位方法使用范围广，并 且节约了为映射x m l 文档编写x s l 文档的时间。 ( 4 ) 原型系统的开发集数据抽取技术、x m l 技术和j a v a 技术为一体，提供一 个快速、通用的基于x m l 的w e b 数据抽取方案。系统具有较强的适应性和良好的 可移植性，使得几乎所有的源代码都可以在任何数据抽取中重复使用。 1 6 论文组织结构 论文由以下六章组成： 第一章介绍了论文的研究背景以及主要的研究内容。 第二章对w e b 上的数据源的搜索策略进行了系统的分析，着重提出了应用于 小范围w e b 搜索的改进h i t s 算法。 第三章对h t m l 格式至t j x m l 格式的转换方法进行了分析和总结，着重提出了基 于栈结构的h t m l 至i j x m l 的转换算法。 第四章针对现行x m l 数据抽取存在的问题，提出_ v x m l 数据抽取的健壮性标 准，着重给出了符合健壮性标准的区域定位和映射合并的合适方法。 第五章基于第二、三、四章的理论研究，使用j a v a 设计开发了一个快速、 通用的w e b 数据抽取原型系统，并给出了运行结果。 第六章总结论文工作，给出继续研究的方向。 6 硕十学位论文第二章获取w e b 数据源策略 2 1引言 第二章获取w e b 数据源策略 从w e b 上获取可靠的数据源是进行w e b 数据抽取的第一步。在寻求健壮解 决方案的过程中，抽取可用的、最可靠和最稳定的数据源，使工作变得最简单。 因而考虑以下这些要素非常重要： ( 1 ) 数据源是否是在可靠的网络连接上生产可靠的数据? ( 2 ) 数据源从现在起将存在多久? 一个星期、一个月或一年? ( 3 ) 数据源的布局有多稳定? w e b 上的数据变动性很大，有时结构也会发生改变，所以通常我们选择政府 网站、大型商业网站、大型行业性网站作为w e b 数据来源。这也符合人们的习 惯。人们为了获取更多明确的、实时更新的信息，往往是直接进入到一些特定 的站点，进行站点内搜索。而且对于一个组织来说，因为其涉及到如何有效搜索 组织内部文档，i n t r a n e t 搜索的重要性也日益增加。所以，小范围w e b 搜索技 术亟待解决。 本章在对广域w e b 搜索进行分析和总结的基础上，深入分析了小范围w e b 链接结构特点，给出了一种适用于小范围w e b 搜索的改进h i t s 算法，并用理论 和实验证明算法是行之有效的。 2 2 广域w e b 搜索 每天有成千上万的人们通过像g o o g l e 或a 1 t a v i s t a 之类的搜索引擎在万维 网上直接寻找信息，搜索引擎总会把相关的结果返回给用户。广域w e b 搜索引 擎的算法是通过分析w e b 页面问的链接结构而得来。p a g e r a n k 算法和h i t s 算法 是两种影响相当广泛的链接分析算法。但是，深入研究表明，它们仍然存在一 些缺陷，因此许多学者在此基础上又提出了一些衍生算法。 221 广域w e b 链接结构分析 w e b 是一个超文本集合，且页面问的链接是有方向的，因此根据图论中有向 图的定义，w e b 可用称为链接图的有向图来建模。传统的方法是以页面粒度来对 链接图建模：结点表示页面，有向边表示从一个页面到另一个页面存在一条或 多条链接。由于一个w e b 文档通常是由其w e b 站点作者创作的多个页面链接而 硕士学位论文第二章获取w e b 数据源策略 成的超文本文档，因此也可以用站点粒度来对链接图建模：结点表示站点，有 向边表示从一个站点中至少有一个页面包含一个或多个超链接指向另一个站点 中的某几个页面，此时成为站点图。 w e b 虽然是一个分散的信息网络，但大量研究表明，w e b 的链接结构具有自 组织性“”：在全局上，信息源( 页面或站点) 问通过超链接按相同或相关的内 容主题自然地聚合在一起，形成一个个群落，群落内部的信息源之间密集链接， 而群落之间稀疏链接，甚至根本不链接：在一个群落内部，信息源之f n j 的链接 结构也有规律和特征，一个群落主要由两类信息源组成，一类主要被别的信息 源所链接( 包含高质量主题内容的信息源) ，另一类则主要链接到别的信息源( 提 供对高质量主题内容存取的信息源) ，它们均是用户想要的好信息源。w e b 的这 种自组织性为链接分析提供了依据，链接分析基于以下一个或两个简单的假设 ( 2 2 】： ( 1 ) 从页面a 到页面b 的一条超链接是页面a 作者对页面b 的一种推荐和称 赞，意味着权威性或质量。 ( 2 ) 若页面a 与页面b 被一条超链链接，则它们可能有相同或相近的主题， 意味着相关性。 大多数像( 3 0 0 9 l e 、a l t a v i s t a 这样的第二代搜索引擎己在其文档数据库中 维护了页面间的链接信息，链接分析在w e b 信息检索中已普遍运用。 2 2 2 广域w e b 搜索经典算法 经典的p a g e r a n k 算法和h i t s 算法是两种应用相当广泛的广域w e b 搜索算 法。 ( 1 ) p a g e r a n k 算法 p a g e r a n k 算法是最早并且最成功地将链接分析技术应用到商业搜索引擎 中的算法。它的基本出发点是试图为搜索引擎所涵盖的所有网页赋予一个量化 的价值度。每个网页被量化的价值通过一种递归的方式来定义，由所有链接向 它的网页的价值程度所决定。显然，一个被很多高价值网页所指向的网页也应 该具有很高的价值。这种规则可以用一种随机网上冲浪的模型来描述。具体来 说，如果假设冲浪者跟随链接进行了若干步的浏览后转向一个随机的起点网页 又重新跟随链接浏览，那么一个网页的价值程度值就由该网页被这个随机冲浪 者所访问的频率所决定。 这个过程也可以理解成一个马尔可夫过程，每个网页是个状态，从一个 网页跟随链接浏览到另一个网页可以被看作是一个状态的转移，所有这种转移 的概率是相同的。但是，考虑如果存在一类网页，这类网页中不包含任何指向 r 硕士学位论文第二章获取w e b 数据源策略 其他网页的链接，那么这种网页将成为沉积网页，并使得上述这种转移的过程 在沉积网页上永远终止。解决这个问题的方法很简单，假如一个随机冲浪者遇 到了这种沉积网页，那么他可以随机地挑选另一个网页并继续他的浏览。为了 对那些不是沉积的网页也一视同仁，这种类型的随机转移应该能以相同的概率 在任何一个网页上发生。下面是整个过程的形式化表达，并由此可以为每一个 网页计算其价值度p r ： p r ( i ) = d x d ( i ) + ( 卜d ) 。 p r ( j ) n ( j ) 公式( 2 - 1 ) 其中。作用于所有链接向网页i 的网页j ，n ( j ) 表示链接向网页i 的所有网页j 的总数。冲浪者以概率d 不再跟随链接浏览而重新从d ( i ) 分布中挑选一个网页重 新开始浏览，以卜d 的概率继续从当前网页中跟随一个链接浏览。根据这种方法 对网页排序以后，搜索引擎就可以决定以一种什么样的顺序将结果返回给查询 用户。 ( 2 ) h i t s 算法 f l i t s 算法是一种分析网络中网页间链接结构从而确定权威性网页和中心网 页的链接分析算法，其内容如下： 将查询功能提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页面， 从中取前m 个页面作为根集，用r 表示。通过向r 中加入被r 引用的页面和r 引用的页面将r 扩展成一个更大的集合初始集g 。如果将页面看作顶点，链 接看作有向边，整个w e b 就可以看作一个有向图g ( v ，e ) 。其中v 表示有限页面 ( 假设有n 个) 顶点集合，即v = w ，i1 i n ) ：e 是由v 中不同元素组成的有序 对的集合，它表示页面之间的超链接，即m 。e 表示为存在一条由页面w ，指向 页面w 。的链接。认为w e b 页面都有被指向作为权威性和指向其他页面作为中心 性的两方面属性，其取值分别用a ( w ) 和h ( w ，) 表示。a ( w ) 和h ( w ，) 如下表示： a ( w ) ：。岛帆) h ( w ，) = 。舌，( ”， 公式( 2 - 2 ) 其中，i 一 j 表示页面i 链到页面j 。 输入数据就是一个r l xn 的邻接矩阵m ，其中存在一条由页面w 。指向页面w 。 的链接则m 。= l 否则m 。= o 。设向量a = ( a ，a ：，a 。) 代表所有基础集合中网页的 权威性，而向量h = ( h ，h ：，h 。) 则代表所有的中心性。最初，将这两个向量均 置为u = ( 1 ，1 ，1 ) 。算法重复运算下列式子： a = m l h h = m a公式( 2 - 3 ) 每次迭代后对向量a 和h 进行范化，以保证其数值不会使计算溢出。k l e i n b e r g 9 硕士学位论文第二章获取w e b 数据源策略 在文献 7 中证明经过足够的迭代次数，向量a 和h 将分别收敛于矩阵f f m 和m m 7 的主特征向量。通过以上过程可以看出，初始集中网页的中心性和权威性从根 本上是由初始集中的链接关系决定的，更具体地况，是由矩阵m t m 和m 1 7 所决定。 2 2 3 广域w e b 搜索总结 可以对广域w e b 搜索的两种经典算法作进一步的探讨和比较。 p a g e r a n k 算法实质上是一种通过离线对整个互联网结构图进行幂迭代的方 法。p a g e r a n k 所计算出的价值度的值实际上就是互联网结构图经过修改后的相 。 邻矩阵的特征值。对这些值的计算有非常有效的方法( 事实上，仅需要若干次的 迭代计算即可以得到) ，因此能够很好地应用到整个互联网规模的实践中。这种 方法的另一个主要优点是所有的处理过程都是离线进行的，因此不会为在线的 查询过程付出额外的代价。但是，p a g e r a n k 算法存在一个大的问题，即价值度 的计算不是针对查询的。对于某个特定主题的查询，在返回结果中一些与主题无 关的网页将会排在较前的位置。这类问题对p a g e r a n k 算法的影响则有必要作更 进一步的研究。 h i t s 算法在概念的定义上l t p a g e r a n k 算法多提出了一个中心性网页的概 念。通过中心网页和权威网页的相互作用，h i t s 算法更好地描述了互联网的一 种重要组织特点：权威网页之问通常是通过中心网页而彼此发生关联的。h i t s 算法和p a g e r a n k 相似，也是通过迭代的方法计算相邻矩阵的特征向量。但h i t s 算法所针对的不是整个互联网结构图，而是特定查询主题的互联网子图。规模 上的极大减小可以使h i t s 算法的迭代收敛速度k t p a g e r a n k 要快得多。但因为与 查询相关，所以查询过程需要考虑排序的代价。另外，除非为h i t s 算法中所考 虑的链接赋予适当的权值，否则，相邻矩阵的主特征向量并不能反映最合理的 网页价值度排列。并且，即便对子图中的边赋予了适当的权重，如果子图的相 邻矩阵是一个可约减的矩阵( 例如图中有多个不连通的部分) ，那么很多有价值 的网页仍将无法在主特征向量中得到体现。更为严重的是，在对很多广义主题 进行查询时，h i t s 算法会错误地将许多与主题无关的网页赋予很高的价值度， 发生主题漂移。最后，应该注意至o h i t s 算法所作用的查询子图是根据查询关键 词在线构造的。通过常规的方法将无法满足在线查询响应时问的要求，但是， 如果借助专用的连接服务器，查询子图的构建时间将是毫秒级的。 很多学者在这两种算法的基础上提出了衍生算法。人们对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 0 硕十学位论文第二章获取w e b 数据源策略 定页面的链接结构决定其重要性，如h i l i t o p 系统”；对不同主题使用不同的个 性化向量，如主题敏感的p a g e r a n k ”；以及针对不同用户群使用不同的个性化向 量等。一些研究工作还对p a g e r a n k 进行了扩展，如结合特定的查询词考虑页面 的向外链接的差异性，对随机冲浪模型进行修改，从而得到d i r e c t e ds u r f 模型 ”“；用处理不确定性的方法处理页面链接信息”“；根据网页点击信息改进 p a g e r a n k 算法。“；重新考虑网页日期。“等。i b ma l m a d e n 实验室以h i t s 算法为 核一i t , 开发了a r c 系统和c l e v e r 。”1 系统。a r c 用于资源的半自动编辑，而c l e v e r 系统用于互联网的搜索。文献 3 3 提出了设置权值参数的方法，文献 3 4 构造 了h t m l 标记树，它们都是试图通过增加对网页内容信息的利用来克服h i t s 算 法的主题漂流。同时也从相似度的链接分析模型角度对h i t s 算法进行了考察 ”，或者给出了在相同查全率的条件下具有更好的查准率的方法等。 2 3 小范围w e b 搜索 为了获取更多明确的、实时更新的信息，人们往往是直接进入到一些特定 的站点对站点内进行搜索。对于一个组织来说，i n t r a n e t 搜索的重要性日益增 加，因为其涉及到如何有效搜索组织内部文档。论文将发生在网络中一个闭合 子空间的搜索定义为小范围w e b 搜索，常见的情况是在个站点内搜索或者是 i n t r a n e t 搜索。现在应用于小范围w e b 搜索的产品生产方兴未艾，例如，a 1 t a v is t a 、b e r k e l e y 的c h a c h a 搜索引擎等。然而人们多数使用的是广域w e b 搜索引 擎，由于其并不能成功的运用于小范围w e b 搜索，所以对于小范围w e b 搜索的研 究已提到了日程上来。论文将分析小范围w e b 链接结构的特点，提出一种应用与 小范围w e b 搜索的改进h i t s 算法，并通过矩阵理论以及实验证明是成立的。 2 3 1 研究背景 现今存在的大多数小范围w e b 搜索引擎使用和万维网搜索引擎相同的技术。 因而存在一些性能问题。根据一份f o r r e s t e r 调查报告。”1 显示，搜索引擎在某 个站点进行搜索时，往往因为返回太多不相关的内容而不符合用户的需要。在 调查中，对5 0 个站点进行了测试，没有一个站点得到满意的结果。而且，在文 献 3 9 的小范围w e b 任务中，使用基于链接分析的方法几乎达不到预计的性能。 这些都表明了现有的小范围w e b 搜索技术存在很大的弹性修改范围。 造成小范围w e b 搜索引擎低性能主要有以下几个方面。 第一，基于关键词相似度的查询方法存在一些缺陷。例如，查询词太短， 使得匹配的空间很大，返回的页面虽然包含查询信息，但页面本身没有什么内 硕十学位论文 第二章获取w e b 数据源策略 容或者包含的内容价值不是很大。另外，查询词的一词多义，让搜索引擎将不 同领域的内容混杂在一起提供给用户，显然这样的页面质量不高。 第二，由于万维网的链接结构与小范围网络的链接结构并不完全一样，因 而成功运用于万维网的链接分析技术不能直接运用于小范围网络。 第三，虽然人们知道用户访问日志包含大量网页重要性的信息，然而，除 了d i r e c t h i t ”0 1 之外，几乎没有其他的网站在这方面进行研究。 现在对于小范围w e b 搜索的研究已提到了r 程卜来，应用于小范围w e b 搜 索的产品生产方兴未艾。大多数产品使用的是“全文本搜索”技术，这种技术 针对查询检索出大量包含相同关键词的文档，然后根据关键词相似度对这些文 档进行重要性排序。例如，a l t a v i s t a 提供了一个基于内容的站内搜索引擎； b e r k e l e y 的c h a c h a 搜索引擎通过将搜索结果进行分类从而反映出未知的 i n t r a n e t 结构：m l e v e n c e 等人提出来的一种返回链接页面序列的浏览系统， 帮助终端用户有效地浏览结果“”。这些系统都不使用链接分析技术对于搜索结 果进行重要性排序，因而还存在相当大的空间来提高搜索的精度。 因为直接将链接分析技术应用于小范围w e b 搜索效果不佳，一些系统将他 们的重点转移到用户的使用信息上。例如，d i r e c t h i t 就是一个典型的例子，它 利用因特网上每天用户所作出的成千上万的决策来为搜索者提供相关度更高、 组织更好的搜索结果。它是基于“点击次数”的概念，现在已被l y c o s 、h o t b o t 、 m s n 、i n f o s p a c e 等大约2 0 多个搜索引擎使用。假设的前提是：根据某个特定的 查询，若一个网页被访问的次数越多，则排序的权值越高。这种方法还是有一 些缺陷。首先，它需要大量的用户日志而仅仅是为了少数的热门查询服务。其 次，它很容易陷入到一个反馈死循环中，当访问一个热门网页时会使其权值增 加，而权值的增加又使得该网页更加热门。 2 3 2 小范围w e b 链接结构 h i t s 是基于链接结构，从而计算特征向量来分辩权威网页的链接分析算法。 直观上来说，一个有很多入度的网页拥有高推荐度，因而有较高的权威性。因 而，链接分析算法有一个基本的前提：整个万维网被看作成一张推荐图，每一 条链接代表一次推荐。也就是说，从网页x 指向网页y 一条链接意味着网页y 为网页x 的作者所推崇。 对于万维网来说，链接分析算法的推荐假设在大多数情况下是正确的，因为 链接确实在相当大程度上代表了作者的判断。当然也不排除某些不是为了推荐 的目的而创建的链接，但是它们的影响可以基本上忽略不计。 然而，h i t s 算法的推荐假设在小范围w e b 应用时却普遍不成立。如图2 一l 12 硕士学位论文第二章获取w e b 数据源策略 所示，在小范围w e b 中，大多数的链接比万维网中的链接要有规律。多数链接 都是从父节点指向子节点，或者是由叶子节点指向根节点。其主要的原因是： 小范围w e b 是由为数不多的作者所创建，链接创建的目的往往是为了组织站点 内容使之成为一种继承或线性结构。因而，计算入度的方法并不能反映页面的 权威性，使得已有的h i 、s 算法不适用于小范围w e b 搜索。 图2 - i 一个小范围w e b 链接结构图 在小范围w e b 中，我们将链接分为浏览链接和推荐链接两种。后者通常用 于链接分析。然而，仅仅过滤出浏览链接远远达不到我们的目的，因为剩余的 推荐链接并不完全。换句话说，我们通过挖掘用户的访问日志可以在小范围w e b 中发现大量的间接推荐链接。 233 改进的h it s 算法( | r r t s ) ( h i t s 算法在在小范围w e b 搜索的情况下表现并不令人满意，主要体现在： ( 1 ) h i t s 算法推荐假设理论不适用于小范围w e b 的链接结构，在小范围w e b 中，链接的构造只是为了组织整个