（计算机应用技术专业论文）基于web视图高效查询系统的研究.pdf

基于w e b 视图高效查询系统的研究摘要 基于w e b 视图高效查询系统的研究 学科专业：计算机应用技术 指导老师：李立新 内容摘要 研究方向：计算机网络与电子商务 研究生：姜强 w e b 网是一个巨大的、分布广泛的、全球性的信息服务中心，它包含了丰富的信息。 进入2 1 世纪后，随着网络的普及，电子商务的发展越来越多的引起研究者们的关注， 期望在这种新型的商务模式下，利用它的诸多优点，获得更多的客户以提高收益。但是， 电子商务在加速社会电子化进程的同时，也使“数据爆炸”问题进一步加剧。在茫茫的 信息海洋中如何快速有效的获取所需要的有用信息，一直是困扰网上用户的难题。 w e b 数据挖掘可以从这个信息海洋中提取出所需要的有用知识，在一定程度t 解 决了用户的困扰。w e b 网实际上就是一个巨大的异构分布式数据库系统。为了支持高级 的、健壮的和可靠的应用，在w w w 上应当加强其数据库功能，引进新的机制和概念 以便将数据库的功能移植到w w w 上。构建这样一个w e b 数据查询系统，是近几年来 计算机技术在电子商务领域中研究的一个热点，本文正是基于这样一个背景下开展研究 的。 在本论文中，首先给出了国内外的研究现状和论文本身的意义，以及相关的理论支 持。接着，考虑在i n t e r n e t 上w e b 站点的特点和w e b 数据多样性的特点以及网络处理的 分布性，构建了一个基于w e b 视图的最优化查询系统模型( w e b v i e w s ) ，并对系统中各 模块的功能给予了详尽的说明，同时运用了c o r b a 规范集成各个模块为一个b s 三层 结构的查询系统。将系统分成客户层、服务器层、和数据层。 论文接下来根据w e b 数据的特点，构建了一个清楚且结构良好的w 曲网站的关系 抽象，并使用一种优化手段来转换这些关系抽象的申请查询，来设计一种导航方案。本 论文使用a d m ( t h ea r a n e u s d a t am o d e l ) 数据模型的一个子集来描述w e b 网站。这种 基于w e b 视图高效查询系统的研究摘要 a d m 数据模型是依靠增加链接约束来获取网站上的冗余。论文使用包含约束( i n c l u s i o n c o n s t r a i n t ) ，它规定所有能被一个确定的路径访问到的页面，同样也可以使用另一条路 径访问到页面。我们使用引导代数( n a v i g a t i o n a la l g e b r a ) 作为描述导航方案的目标语言， 同时我们在研究最优化关系抽象中使用重写规则，将链接约束和包含约束引入到运算 中，以便在回答查询中，减少大量需要访问的页面数量。 当根据关系视图发出一个查询时，它被重复的使用重写规则来重写，这个过程产生 大量的导航方案来运算查询。这些方案的代价是根据代价模型来评估的。代价模型是用 网络访问作为原始的代价参数。用这种方式，就可以查询过程选择一个高效的执行方案。 然后，论文对优化算法做了相关验证性实验，优化结果的有效性，说明了优化算法 的正确性。最后是工作小结和未来展望。 关键词： w e b 数据挖掘查询语言最优化查询视图的维护查询系统c o r b a 规范b i s 三层结构代价模型引导代数n a g l 萤写规则a d m 数据模型链 接约束包含约束 苎三兰! 望里塑垫奎塑墨竺竺! 窒塑矍 r e s e a r c ho ne f f i c i e n tq u e r i e so v e rw e bv i e w s a b s t r a c t m a j o r ：c o m p u t e r a p p l i c a t i o nd i r e c t i o n ：c o m p u t e r n e t w o r k a n d e - c o m m e r c e s u p e r v i s o r ：l i l i x i na u t h o r ：j i a n g q i a n g w o r l d w i d ew e b ( w w w ) i sa ne n o r m o u s , w i d e l y d i s t r i b u t e d ，g l o b a li n f o r m a t i o ns e r v i c e c e n t e r , w h i c hc o n t a i n sr i c hs o u l - g e s w i t ht h ep o p u l a r i z a t i o no fn e t w o r k ，e l e c t r o n i cc o m m e r c e s h a sc o u g h tm o r ea t t e n t i o nf r o mr e s e a r c h e r s t h e yw a n tt ot a k et h ea d v a n t a g eo ft h en e w c o l i l r n e r c et og a i nm o r ec u s t o m sa n dp r o f i t b u tt h e “d a t ae x p l o d i n g h a sb e c o m es e r i o u s a s w ea r ek n o w n ，t h eu s e r so ni n t e r n e tf i n di ti sad i f f i c u l tp r o b l e mt oa c q u i r eu s e f u li n f o r m a t i o n q u i c k l y t h ew w wi sah u g eh e t e r o g e n e o u sd i s t r i b u t e dd a t a b a s e t o s u p p o r ta d v a n c e d r o b u s t a n dr e l i a b l e a p p l i c a t i o n s d a t a b a s ef u n c t i o n a l i t i e sn e e db ea d d e dt ow w w t h i sn e e dt o i n t r o d a c ei l e wm e c h a n i s ma n d c o n c e p t si no r d e rt oa d dd a t a b a s ef u n c t i o n a l i t i e st ot h ew w w b u i l d i n gaw e b d a t aq u e r ys y s t e m l m sg o tm o r ea t t e n t i o nr e c e h t l y , t h ec u r r e n ti sj u s tb a s e do n t h ep o i n t sm e n t i o n e da b o v ef o rf u r t h e re x p a n s i o ni nm a n yr e l a t e df i e l d s f i r s tt h ep a p e ro u t l i n e st h ec u r r e n tr e s e a r c hs t a t u sa th o m ea n da b r o a d ，i n t r o d u c e st h e s i g n i f i c a n c e o ft h e p a p e r a n ds o m er e l a t i v et h e o r i e s t h e n c o n s i d e r i n g w e bs i t e s c h a r a c t e r i s t i c s ，w e b d a t a s d i v e r s i t y a n dd i s t r i b u t e d c o m p u t a t i o n c h a r a c t e r i s t i c so fn e t w o r k , t h ep a p e rb u i l d sao p t i m i z i n gq u e r ys y s t e mm o d e lb a s e do nw e bv i e w sa n dr e l a t e s e v e r y f u n c t i o nm o d u l ei nd e t a i l f u r t h e r m o r et h e p a p e ri n t e g r a t e s a l lm o d u l e si n r e c o m m e n d a t i o ns y s t e mm o d e li n t ob st h r e el a y e r sb a s e do nc o r b ac r i t e r i a ：c u s t o m e r l a y e r , s e r v e rl a y e r , d a t a b a s el a y e r s e c o n d l y , u s i n gw e bd a t ac h a r a c t o r s , t h ep a p e ri s t ob u i l dr e l a t i o n a la b s t r a c t i o n so f 1 1 1 苎王兰! 望望塑塑奎塑墨竺塑竺塞塑鐾一 l a r g ea n df a i r l y w e l l s t r u c t u r e dw e bs i t e sa n dt ou s ea no p t i m i z e rt o t r a n s l a t ed e c l a r a t i v e o u e r i e so nt h e s er e l a t i o n a la b s t r a c t i o n st oe f f i c i e n tn a v i g a t i o np l a n s w eu s e a s i m p l es u b s e to f t h ea r a n e u sd a t am o d e l ( a d m ) t od e s c r i b ew e b s i t e s t h i sa d ms c h e m ei sa u g m e n t e d w i t h l i n kc o n s t r a i n t st h a tc a p t u r et h er e d u n d a n c yp r e s e n ti nm a n yw e bs i t e s t h i sp a p e ra l s ou s e i n c l u s i o nc o n s t r a i n t st h a ts t a t et h a ta l lt h ep a g e st h a tc a nb ea c c e s s e du s i n gac e r t a i np a t hc a n a l s ob ea c c e s s e du s i n ga n o t h e rp a t h w eu s ean a v i g a t i o n a la l g e b r aa st h et a r g e tg a n g u a g et h e d e s c r i b e sn a v i g a t i o np l a n sa n dw es h o wh o wt ou sr e w r i t er u l e si nt h es p i r i to fr e l a t i o n a l o p t i m i z e r sa n d , t a k i n gl i n ka n di n c l u s i o nc o n s t r a i n t si n t oa c c o u n t , t or e d u c et h en u m b e ro f p a g e a c c e s s e sn e e d e dt oa n s w e raq u e r y w h e naq u e r yo nt h er e l a t i o n a lv i e w si s i s s u e d ，i t i s r e p e a t e d l yr e w r i t t e nu s i n gt h e r u l e s t h i sp r o c e s sg e n e r a t e sn u m b e ro fn a v i g a t i o np l a i st oc o m p u t et h eq u e r y ；t h ec o s to f t h e s ep l a n si st h e ne s t i m a t e db a s e do na s i m p l ec o s tm o d e l t h a tt a k e sn e t w o r ka c c e s s e sa st h e p r i m a r yc o s tp a r a m e t e r i nt h i sw a y , a ne f f i c i e n te x e c u t i o np l a ni ss e l e c t e df o rp r o c e s s i n gt h e q u e r y t h ep a p e r g i v e ss o m ev a l i d a t i o ne x p e r i m e n ta b o u tt h ea b i l i t y o fq u e r yo p t i m i z a t i o n a l g o r i t h mt od e p i c tt h ea c c u r a c y a n da tl a s t , t h ep a p e rp u t sf o r w a r dt h es u m m a r i z i n go ft h e p a p e ra n d n e x t s t e p sw o r k k e y w o r d s ：w e bd a t a m i n i n gq u e r yl a n g u a g eq u e r yo p t i m i z a t i o n v i e w m a i n t e n a n c e q u e r ys y s t e m c o r b a a l g e b r a n a g l r e w r i t i n gr u l e s t h e i n c l u s i o nc o n s t r a i n t b st h r e el a y e r sc o s tm o d e l n a v i g a t i o n a l a r a n e u sd a t am o d e l ( a d m ) l i n kc o n s t r a i n t 第一章前言 1 1 引言 第一章前言 w w w 的迅速发展使其成为全球信息传递与共享日益重要和最具潜力的资源，它作 为一种新的环境资源，为新技术的产生开辟了新的领域，同时也为传统技术( 如数据库、 人工智能等) 的研究提出了新的方向。如何管理及查询w 懈，上的大量信息，以满足 用户不断增长的信息需求，是研究人员面临的新课题。 随着电子数据数量的激增和w e b 规模的快速增长，使用传统的信息检索方法在这样一个 无限的信息海洋中要准确、快速定位所需信息时，越来越显得力不从心，在未来的w e b 发展中，如何提高信息检索的准确性和效率成为关键问题。另一方面，目前出现了超越 浏览方式而使信息面向应用访问的迫切需求，从而为各种服务提供自主性、互操作性和 w e b 意识。无结构的i - r i m l 文档及其相应的信息检索技术将不再适应下一代更复杂的 w e b 应用。 由于i n t e r n e t 的发展，网上数据不断激增，对网上信息的应用需求也不断提高，原 有的对文本文件的链接测览和关键词检索已无法满足一些复杂的应用需求。近年来，大 量的研究致力于将数据库技术应用于网上数据的管理和查询，使奄询可以在更细的粒度 上进行，并集成多个数据源的数据。但是，将传统数据库技术直接应用于网上数据的最 大困难在于，网上数据缺乏统一的、固定的模式，数据往往是不规则且经常变动的。因 此，半结构化数据模型应运而生，其无模式及自描述的特点适宜于描述网上数据。事实 上，a t z e n i 等人4 1 使用的数据模型一- - a i l a _ n e u s 数据模型( a d m ) 就是一种自描 述的半结构化数据，它的出现推动了w w w 在电子商务、电子数据交换和电子图书馆等多 方面的应用。但对于如何有效地存储管理和查询这类数据，目前却莫衷一是，已有的数 据库技术，如关系数据库、面向对象数据库。都不能完全适应于新的应用需求，而专用 的半结构化数据管理系统目前仍处于初步实验阶段。 本文的工作正是基于这样的一个背景下开展的，在研究和实践中，试图将a i ) m 数 据模型和引导代数学( n a d 。g ) 用于w e b 查询中，建立个性化网站的查询系统。 第一章前苦 1 2 国内外研究领域和现状 信息集成技术是w e b 站点建设的基础，描述性的w e b 查询语言可以成为用于w e b 站点重构的方便和功能强大的工具。目前，国内外已有相当多的机构正在研究以数据库 技术和最优化查询技术相结合的系统。 1 ) 这方面比较典型的例子是s t r u d e l ，它是一个w e b 站点管理系统，它的语言s t r u q l 可以定义集成的数据图和w e b 站点的结构图。 2 ) l a mw a i 等人利用基于事例的机器学习和查询反馈技术实现了文本的自动分类 并用于文本检索，实现了其优化性。 3 ) m a n d a l ar i l a 等人采用加权方法从多类信息中实现了查询的扩展。 4 ) c h a k r a b a r t is o u m e n 等人探讨的基于矩阵代数的主题提取算法、组合词汇和索引 文本等特征提取，也是在这方面作出的努力。 5 ) 伯克利丈学的x s e t 系统就为x m l 数据采用了一种索引。这种索引综合了路径 信息，也是树结构。 6 ) 斯坦福大学的d a t a g u i d e 系统实现了任意结构的半结构化数据的索引，它是关于 半结构化数据的路径信息的一个精确、简洁的索引结构，可以有效地用来辅助建 立查询和进行查询优化。 7 ) d o a gl e n a t 研制的搜索系统，通过建立常识库和推理机来于用户交谈，进而实现 对用户的理解。 8 ) c h o i y o n gs 等人实现了一种具体的自动构建系统，其可从网上发现文本并归入 本地数据库供查询，它相当于智能代理。 国内在这方面的探索刚剐有所起步，在清华和中科院等做过相应的讨论。 目前已有的系统虽然在相关的领域取得了一定的成果，但仍然存在些问题，总的 来说有以下几点： 1 ) 查询需求时，有些需求难以用自然语言精确的描述。 2 ) 多个用户之间的查询需求肯是矛盾的，难以建立统一的用户查询模型。 3 ) 系统难以在众多的查询方案中选择出一个最优化的查询方案，因而使系统的性 第一章前言 能难以提高。 1 3 本论文研究的内容 随着w 曲成为各种信息的首选媒体，在很多w e b 网站中的页面集合，已经出现了 有规则而且复杂的结构。由于现在的网站变得越来越大，手工导航这些结构( “浏览”) 并不适用于高效地查找信息。典型地，一个特定查询接口规定，在网站的所有页面使用 纯文本的索引。但是，虽然纯文本查询在寻找相关条件的文档中比较适用，但不能回答 精确的问题，如：“找出所有在最后三次v l d b 会议中发表论文的作者。”如果我们能利 用诸如数据库中的提取方法，即一个关系模式，使我们能够使用强大的数据库查询语言， 如s q l ，来形成查询，让系统将它们转换成为一种存在于超文本导航的查询。 论文则针对上述问题，以w e b 数据挖掘作为模式建立的技术，在分布式的环境下， 运用c o r b a 规范建立b s 三层结构的查询系统。讨论了系统各个模块的功能以及它们 之问怎样协调一致的工作。此外，还对优化查询系统进行了研究，并提出了代价模型和 优化算法。 1 4 论文所做的工作 本论文主要研究有关转换方面的论点，并开发了一个能在现实网站中使用的系统。 大体上，申请查询会允许各种不同的转换，相当于取得数据的不同导航路径。举例来说， 回答上面的查询就会产生大量的查询方案，如果我们使用一些被访问的页面，作为粗略 地评估一下查询的执行代价，我们可以观察到所有可能的访问路径，它们的代价有着巨 大的差异。这就在性能上产生巨大的差异。因此可以得出，一个最优化查询必须将一个 申请查询转换为一个高效的导航方案，就像一个最优化关系映射一个高效的s q l 查询 访问方案。 本论文针对上述问题，提出了构建一个具有良好结构的w e b 网站的关系抽象，并 根据这些关系抽象，使用最优化技术将查询申请转换为高效的导航方案。本论文使用 兰二兰望童 a d m 数据模型( t h e a r a n e u s d a t am o d e l ) 4 】的一个子集来描述w 曲网站。本论文提 出了一个代价模型，并利用此代价模型来评估一个查询方案所需要的代价，最后在所有 的方案中选择最优化的方案。此外还阐述了系统所采取的优化策略和优化算法。 论文还考虑了在分布式环境下依托c o r b a 规范，建立了一个b s 三层结构的查询 系统，并对系统中的各个模块功能以及它们之间协调工作做了详细的描述。 本论文的重点是查询系统的构建和查询系统所采用的优化策略和优化算法。在研究 优化策略和优化算法的同时，还考虑了w e b 数据的同步性问题。 本论文是基于下面的设想开始分析工作的：到页面唯一的访问结构是构建在超文本 中的。首先，将虚拟关系视图上的查询映射到超文本下的导航，并根据适当的代价模型， 为了选择一个高效的执行方案而开发一个算法。然后，研究有关实例化视图的问题，并 展示如何运用同样的技术来开发能被扩展到实例化视图管理的虚拟视图。 1 5 论文的意义 随着电子数据数量的激增和w e b 规模的快速增长，使用传统的信息检索方法在这样 一个无限的信息海洋中要准确、快速定位所需信息时，越来越显得力不从心，在未来的 w e b 发展中，如何提高信息检索的准确性和效率成为关键问题。另一方面，目前出现了 超越浏览方式而使信息面向应用访问的迫切需求，从而为各种服务提供自主性、互操作 性和w e b 意识。无结梅的一h t m l 文档及其相应的信息检索技术将不再适应下一代更复 杂的w e b 应用。因此，未来的w e b 信息将由更近似于数据库的方式进行管理，而不是 目前采用的单一的信息检索方式。w e b 资源需要以有结构的方式进行组织和访问。本查 询系统采用a d m 数据模型，结合数据库查询技术，将引导代数( n a l g ) 和代价模型运 用于查询系统中，提高了查询系统的性能，因此，对查询系统进行研究是具有相当价值 的。 本论文的创新之处主要体现在以下几个方面： 1 考虑了w e b 数据的特点，在缺乏控制的前提下，数据往往是不规则且经常变动， 利用系统在查询时实际地导航到站点上检查页面是否更新，维护这些数据结构。 第一章前言 2 遵循c o r b a 规范，建立了b s 三层结构的查询系统，体现了查询系统处理上的 分布式特点。 3 针对目前站点中数据缺乏统一的、固定的模式，数据往往是不规则的现状，本论 文使用a d m 数据模型( t h ea r a n e u s d a t am o d e l ) 4 】的一个子集来描述w e b 网 站，用a d m 模型描述的超文本信息集成为传统的关系表，用户在关系的基础上 实现信息的集成与查询。 4 使用引导代数( n a v i g a t i o n a la l g e b r a ) 作为描述导航方案的目标语言，同时我们研 究在最优化关系抽象中使用重写规则，将链接和包含约束引入到运算中，这就极 大地方便了方案的优化过程。 5 将传统的s e l e c t i o n - - - p r o j e c t i o r r l o i n 数据库技术应用到w e b 数据查询系统中，极 大地提高了系统的性能。 6 在系统中建立了评估查询方案的代价模型，这就使得系统能够在众多的查询方案中 选择出一个最优化的查询方案，这样在回答查询中，就减少了大量需要访问的页面 数量。 1 6 论文内容的安排 在余下的章节中，将在第二章给出相关的理论支持：在第三章给出查询系统基于 c o r b a 的b s 三层结构，并在其中讨论了各个功能模块，实现了基于a d m 来描述网 站的数据模型；第四章给出了查询策略和相关的算法；第五章是相关实验；第六章是小 结和展望。 第二章相关理论 第二章相关珲论 2 1 w e b 数据挖掘技术 2 1 1 数据挖掘技术简介 数据挖掘是数据库技术、人工智能、机器学习和统计学等多门学科相结合的产物。 简单的说，数据挖掘是从大量数据中提取或挖掘知识。一种比较公认的定义是：数据挖 掘是指从数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信息的非平凡过 程。许多人将数据挖掘与k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 视为同义词，而另 外一些人则将数据挖掘作为k d d 的一个基本步骤，数据库中知识发现的过程如图2 1 所示： 图2 1 它由下列基本步骤组成： ( 1 ) 数据清理：包括消除噪音、推导计算缺值数据、消除重复记录、完成数据类型 转换和消除不一致数据等。 ( 2 ) 数据集成：将多种数据库中的数据组合在一起。 ( 3 ) 数据选择：从数据库中检索与分析与任务相关的数据，它的目的是确定发现任 务的操作对象，即目标数据( t a r g e td a t a ) ，它是根据用户的需要从原始数据库 中抽取的一组数据。 ( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式，它的主要目的是消除数据维 6 翦二章相关理论 数或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少 数据开采时要考虑的特征或变量个数。 ( 5 ) 数据挖掘：它是基本步骤，使用智能方法提取数据的模式。 ( 6 ) 模式评价：经过数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能 存在冗余或无关的模式，这时需要将其剔除。 ( 7 ) 知识表示：对发现的模式使用可视化和知识表示技术，或者把结果转换为用户 易懂的另一种表示，如把分类决策树转换为“i f t h e n ”规则，向用户提 供挖掘出来的知识 从上述步骤可以看出，数据挖掘只是整个过程中的一个步骤，然而，在大多数场合， 人们采用广义的数据挖掘观点，即数据挖掘是指从存放在数据库、数据仓库或其它信息 库中的大量数据中挖掘有趣知识的过程。 2 1 2w e b 挖掘简介 据估计，w e b 已经发展成为拥有3 亿页面的分布式信息空间，而且这个数字仍以每 4 至6 个月翻一番的速度增加。在这个分布式信息空间中蕴涵着具有巨大潜在价值的知 识，如何从这些海量数据源( 主要是一异质、非结构化数据集合) 中发现有用的知识或 者模式，成为急待解决的问题。为了从大量数据的集合中发现有效、新颖、潜在有用的、 可理解的模式，在数据库中领域采用了数据挖掘技术；但是，数据挖掘技术的绝大部分 工作所涉及的是结构化数据库，很少有处理w e b 上异质、非结构化信息的工作。所以， 在w e b 上解决这些问题的一个途径，就是将传统的数据挖掘技术和w e b 结合起来，进 行w e b 挖掘。 w e b 挖掘是- - f l 交叉性学科，涉及数据挖掘、机器学习、模式识别、人工智能、统 计学、计算机语言学、计算机网络技术、信息学等多个领域。w 曲挖掘是指从大量非结 构化、异构的w e b 信息资源中法西有效的、新颖的、潜在有用的及最终可理解的知识 ( 包括概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、约束 ( c o n s t r a i n t s ) 、及可视化( v i s u a l i z a t i o n s ) 等形式) 的非平凡过程。 这个描述性的定义是借鉴了数据挖掘的定义而给出的，这里将解释几个概念：过程 第二章相关理论 通常是指多阶段的一个过程，涉及数据预处理、学习与知识模式的生成，意思是要有一 定程度的智能化、自主性( 仅仅给出所有数据的总和不能算是一个发现过程) 。而以上 所提及的有效性、新颖性、潜在有用性和最终会理解性综合在起可成为兴趣性 ( i n t e r e s t i n g n e s s ) 。 w 曲挖掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘技术定义相类 似。但是w e b 挖掘与传统的数据挖掘相比有许多独特之处。首先，w e b 挖掘对象是海 量、异构、分布的w e b 文档。我们认为w e b 以作为中间件对数据库进行挖掘，以及对 w e b 服务器上的日志、用户信息等数据展开的挖掘工作仍属于传统的数据挖掘技术的范 畴。其次。w 曲在逻辑上是一个有文档节点和超链接构成的图，因此w e b 挖掘所得到 的模式可能是关于w e b 内容的，也可能是关于w e b 结构的。此外，由于w e 文档本身 是半结构化或无结构的，且缺乏机器可理解的语义，而数据挖掘对象局限于数据库中的 结构化数据，并利用关系表格等存储结构来发现知识，因此有些数据挖掘技术并不适用 于w e b 挖掘技术以及对w e b 文档进行预处理以得到关于文档的特征表示，变成为w e b 挖掘的研究重点。 2 1 3 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 u s a g em i n i n g ) 和w 曲结构挖掘( w e b s t r u c t u r em i n i n g ) ，其分类的结构图如图2 2 所 示： 第- 章相关理论 1 w e b 内容挖掘( w e bc o n t e n tm i n i n g ) w e b 内容挖掘就是从w e b 页面内容或其描述中进行挖掘，进而抽取知识的过程。 其中内容的挖掘从其挖掘对象来说，又可分为两类：对于文本文档的挖掘( 包括t e x t 、 h t m l 等格式) 和多媒体文档( 包括i m a g e ，a u d i o ，v i d e o 等媒体类型) 的挖掘。w e b 上多媒体挖掘主要是利用多媒体提取工具进行特征提取，然后对这些特性进行关联规则 或者分类的挖掘操作。 w e b 文本挖掘可以对w e b 上大量文档集合的内容进行摘要、分类、聚类、关联分析， 以及利用w e b 文档进行趋势预测等。文本摘要是指从文档中抽取关键信息，用简捷的 形式对文档内容进行摘要或解释。这样，用户不需要浏览全文就可以了解文档或文档集 合的总体内容。在搜索引擎向用户返回查询结果时，通常需要给出文档的摘要。目前， 绝大部分搜索引擎采用的方法是简单的截取文档的前几行。 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目标是将 文档集分成若干类，要求同一类内文档内容的相似度尽可能大，而不同内间的相似度尽 可能地小。h e r s t 等人的研究已经证明“类聚假设”，即与用户查询相关的文档通常会聚 类的比较近而远离用户查询不相关的文档。因此，我们可以利用文本聚类技术将搜索 引擎的检索结果划分为若干类，用户只需要考虑那些相关的类，大大缩小了所需要的浏 览结果数量。 关联分析是指从文档集合中找出不同语句之间的关系。b r i n 提出了一种从大量文档 中发现一对语句出现模式的算法，并用来在w e b 上寻找作者和书名的出现模式，从而 发现了数千本在a m a z o n 网站上找不到的新书籍。w a n g 等人以w e b 上的电影为测试文 档，通过使用o e m 模型从这些半结构化的页面中抽取语句项，进而得到一些关于电影 名称、导演、演员、编剧的出现模式。 分布分析与趋势预测是指通过对w e b 文档的分析，得到特定数据在某个历史时刻 的情况和将来的取值趋势。f e l d m a n 等人使用多种分析模式对路透社的两万多篇新闻进 行了发现，得到了主题、国家、组织、人、股票、交易之间的相对分布，揭示了一些有 趣的趋势。 2 w e b 访问信息挖掘( w 曲u s a g em i n i n g ) w e b 访问信息挖掘就是对用户访问w e b 时，在服务器留下的访问记录进行挖掘， 即对用户访问w e b 站点的存取方式进行挖掘，以发现用户访问站点的浏览模式，页面 的访问频率等信息。在用户浏览模式分析中主要包括了针对用户群的一般的访问模式追 踪。挖掘的对象是在服务器上包括s e r v e r l o g d a t a 等日志。其挖掘得到的模式可以用来 知道站点管理员改进w e b 站点的设计及组织结构或提供可以带来经济效益的信息。 3 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 9 第= 章柙关理论 w e b 结构挖掘就是从w w w 的组织结构和链接关系中推导知识。由于文档之间的 互连，w w w 能提供出文档内容之外的有用信息。利用这些信息，可以对页面进行排序， 发现重要的页面。这方面的代表有p a g e r a n k 和c l e v e r 。w e b 结构挖掘不仅仅包括文 档之间的超链接结构，还包括文档内部的结构、u r l 中的目录路径结构等。 目前，与w e b 挖掘相关的各种项目涉及了上述任务的某个方面，也有一些项目综 合考虑了w e b 的内容和结构因素，将文本发现与结构结合起来，以取得更好的效果。 由于目前w e b 上主要还是以文本作为记载和传播的最主要的媒体，而且文本挖掘又相 对容易取得技术突破，因此对文本挖掘技术的研究具有十分重要的意义和广泛的应用前 景。 2 2n a l g 引导代数 引导代数学( n a v i g a t i o n a l a l g e b r a ) ，它是给提供给原始的导航一种包含关系的代数 学。n a l g 是从应用语言u l i x e s 4 6 0 抽象出来的，在表达方面类似于w e b o q l 3 的- - 种子集，它可以根据一个a d m 模式来表示查询表达式。 除了传统的s e l e c t i o n ，p r o j e c t i o n ，和j o i n 操作之外，在引导代数中，为了描述导航， 我们引入了两个简单的操作符。第一个操作符称之为非嵌套页面( u n n e s t p a g e ) ，它是一 种传统的非嵌套操作符( 肚) ，它允许在一个页面内，访问不同嵌套级别的数据；取代传 统的前缀符号斗a ( r ) ，( 其中，r 表示一个页面关系，a 是r 的一个内嵌的属性) 。在本 文中，我们使用一个不同的符号，作为一个中缀符号：r a 。 第二，我们称子为后继链接( f o l l o wl i n k ) ，表示为符号：+ ，它用来表示一 个链接。大体上来说，我们可阻用来表示在页面内的导航，也就是在一个页面的不同 结构中导航；反之，卜则是用于外部导航，也就是两个页面之间的导航。 s e l e c t i o n - - - p m j e c t i o 旷_ j o i n 代数是引导代数学的一个子语言。在这种情形下，可以 在适当的w e b 框架下，同时操作关系和导航查询。举例来说，参考图3 - - 5 ，假定我们 对计算机科学系里所有教授的名字和e - m a i l 感兴趣。为了取得我们感兴趣的数据，首先， 我们需要以下面的方式导航站点： p r o f l i s t p a g e p r o f l i s t 卫堕峰p r o f p a g e o 第= 幸相关理论 从直观上来看，此表达式所表达的语义如下： 登录点p r o f l i s t p a g e 是通过它的u r l 来访问的，它所对应的页面关系是非嵌套的 ( u n n e s t e d ) 。为了能够访问属性t o p r o f ，它有一个p r o f l i s t 的属性列表；最后，每个链 接可以理解为到达对应的p r o f p a g e 。操作符鱼q ，从本质上来讲，就是通过连接目 标对象上的详细数据来“扩展”源关系。 由于后继链接是按自然法则的一种链接，所以它通过目标对象的u r l 属性，隐含 的使用源关系的链接属性。我们假定属性在任何需要的时候，都可以重新命名。根据以 上的表达式，可以产生查询：“在计算机科学系的所有教授的名字和e - m a i l ”。如下所示： , t p n a m c , o - l n a i l ( n e ： c o m p u t e r s c i e n c e ( p r o f l i s t p a g e p r o f l i s t 皿吟p r o f p a g e ) ) 引导代数就是用来表达a d m 模型，它工作在页面关系上，并返回到页面关系中。 我们用盯表示选择( s e l e c t i o n ) ，7 表示投影( p r o j e c t i o n ) ，阏表示连接( j o i n ) 。然后， 我们定义如下操作符： 非嵌套页面( u n n e s tp a g e ) ，是一个双目操作符，它的两边是一个页面关系r 和 一个此页面关系内含的属性b ；它所表达的语义为，带有属性b 的非嵌套页面关系 r 的结果：r b = b ( r ) 。为使其一般化，我们让r 为一个具有模式( a 1 ，a 2 ，a n ， b ) 的一个嵌套的一个页面关系。假设b = l i s t o f ( b i ，b 2 ，b 。) ，那么，r b 是如下所示的一个嵌套的页面关系r ： r 7 的模式为：( a i ，a 2 ，b l ，b 2 ，b 。) r = t j 如果存在个元组“r ，那么，t a l ，a 2 ，a 。】= p 【a l ，a 2 ，a 。】a t 【b i , b 2 ，b 。】p b 】) 后继链接( f o l l o wl i n k ) l 一- ，也是一个双目操作符，它的两边是俩个页面关 系r l 和r 2 ，并且从r l 到r 2 存在个链接属性：执行表达式 r 1 l + r 2 等于链接属性运算r l 和r 2 的连接，也就是： r l l + r 2 = r 1 冈r 1 l ：r 2 u r lr 2 这样，就根据相关的链接属性l ，“扩展”了页面关系的资源。 第二章相关理论 万c n m e d e i d t i o n a 岛n 。，c 。， i c o u r s e p a g e p n a m e = d e p t p a g e p r o f l i s t p n a m e c o u r s e p a g e d e p t p a g e p r o f l i s t w dd s e s s i o n p a g e c o t t r s e l i s t t o s d d e p t l i s t p a g e d e p t l i s t l i s t s e s s i o n l i s t p a g e s e s l i s t 刀h d 州一d 赢w # ，c s ( ( s e s s i o n l i s t p a g e s e s l i s t j 立坠 s e s s i o n p a g e c o u r s e l i s t 卫业噬，c o u r s e p a g e ) 阁 c o t 岵e p a g ep n a 聪d | ! p i p l 萨p r o f l i s tp n 蜘e ( d e p t l i s t p a g e o d c p t l i s t 型2 虹卜d e p t p a g e o p r o f l i s t ) ) ) 基于一个模式s 的n a l g 表达式，是在s 中任何页面关系操作的结合。在通常情 况下，每个表达式是与一个查询树( 或称之为查询方案) 相关联。在查询是树中，叶节 点总是与页面关系和节点中的操作符相关联。在图2 3 中，给出了一个比较复杂的表 达式，它所对应的查询表达式为：“计算机科学系中开设课程的名称和描述。”同时，图 2 - - 3 也给出了一个查询方案。注意，我们在查询方案中的符号与规范的引导代数表达 式有细微的差别。事实上，我们可以为非嵌套操作符保持中缀符号，并在链接的边上给 出链接操作符。 运算一个引导代数表达式，就等于利用引导代数中的操作符，访问包含在页面模式 中的页面关系。但是，只有在w e b 模式中，可直接访问的页面