（计算机软件与理论专业论文）web文档查询与信息检索导航技术的研究与实现.pdf

东北大学硕士学位论文 摘要 w e b 文档查询与信息检索导航技术的研究与实现 摘要 在i n t e m e t 上充斥着海量的信息，这些信息一方面为人们的生活提供了方便和 帮助，另一方面也使得人们淹没在信息的海洋中而无所适从，无法有效地获取有 用的信息。为了解决这些问题，数据挖掘和信息检索技术应运而生。尽管以往的 研究人员在w e b 数据挖掘和信息检索领域取得了丰硕的成果，为用户提供了巨大 的方便，但现有的技术仍然存在着不足，例如：x m l 格式文档的查询及w e b 信息 检索导航等方面存在着不能很好满足用户需求的问题。 针对这些问题，本文首先介绍了数据挖掘和文本挖掘、w e b 数据挖掘和信息 检索、x m l 文档及其查询的相关概念和技术，并将研究重点放在x m l 文档查询 和w e b 文档检索导航上。 在x m l 文档查询方面，针对关键词查询和半结构查询，分别提出了有效的索 引结构和查询算法。介绍了l c a ( l o w e s tc o m m o na n c e s t o r ) 的概念并将其扩展 到p l c a ( l c ao f l a b e lp a t h ) ，提出了p l c a 规则用于有效地判断x m l 文档节点 间的语义相关性，利用x m l 文档模式与实体的概念进一步提高查询的准确率；提 出了p n 倒排索引和p e 索引，并基于此设计了x m l 文档关键词查询算法和半结 构查询算法。对于本文提出的各种算法，作了充分全面的实验，用于验证结果和 比较其性能。 在w e b 文档检索导航方面，本文提出了在文献中挖掘最大序列频繁词组作为 文献的特征，从而为用户提供辅助的w e b 文档检索结构；根据特征之间的层次关 系建立扩展的特征层次树，依据树中特征与文献的关系推导出文献之间的关系， 从而使用户在查询时根据上述关系，借助于搜索引擎尽快地获得所需的文献。在 系统实现时，我们设计了基于w e b 文档特征层次结构的三种检索导航方式，并实 现了一个原型系统将这三种导航方式有机地结合在一起，以简洁有效的方式为用 户的检索过程提供帮助。 关键词：数据挖掘，文本挖掘，w e b 挖掘，信息检索，x m l 查询 东北大学硕士学位论文a b s t r a c t s t u d ya n di m q u e r y a n di n p l e m e n t a t i o no fw e bd o c u m e n t f o r m a t i o nr e t r i e v a ln a v i g a t i o n a b s t r a c t t h e r ea r e l a r g ea m o u n to fi n f o r m a t i o no nt h ei n t e r a c t t h e yp r o v i d em u c h c o n v e n i e n c ea n dh e l pt oh u m a n l i f e ，w h i l em a k i n gp e o p l eg e tl o s ti nt h eo c e a no fd a t a a n dc a n n o tf i n dn e e d e di n f o r m a t i o ne f f e c t i v e l ya n de f f i c i e n t l y t os o l v et h i sp r o b l e m ， p e o p l eh a v ep r o p o s e dd a t am i n i n ga n di n f o r m a t i o nr e t r i e v a lt e c h n i q u e s ，a n dm a d e f r u i t f u lr e s e a r c hi nt h e s ea r e a s h o w e v e r , t h e r es t i l le x i s tm a n yu n s o l v e dp r o b l e m s ， s u c ha sq u e r yo nx m ld o c u m e n ta n dw e b b i b l i o g r a p h yr e t r i e v a l i nt h i st h e s i s ，w ef i r s ti n t r o d u c e dt h eb a s i cc o n c e p t sa n dt e c h n i q u e so nd a t am i n i n g ， t e x tm i n i n ga n dw e b m i n i n g ，i n f o r m a t i o nr e t r i e v a l ，a n dx m ld o c u m e n tq u e r y t h e nw e f o c u so u rs t u d yo nt h ek e y w o r dq u e r ya n ds e m i s t r u c t u r a lq u e r yo nx m ld o c u m e n t ， a n dt h ew e b b i b l i o g r a p h yr e t r i e v a ln a v i g a t i o n i nt h ex m ld o c u m e n tq u e r y , w ep r o p o s e de f f i c i e n ta l g o r i t h m st ob o t hk e y w o r d q u e r ya n ds e m i s t r u c t u r a lq u e r y w ef i r s ti n t r o d u c e d t h ec o n c e p to fl c a ( l o w e s t c o m m o na n c e s t o r ) a n de x t e n di tt op l c a ( l c ao fl a b e lp a t h ) ，a n dt h e np r o p o s e da p l c ar u l et oj u d g et h es e m a n t i cr e l a t i o n s h i pa m o n gt h en o d e si nx m ld o c u m e n t w e a l s ou s e dt h ec o n c e p to fs c h e m a - e n t i t yi nx m ld o c u m e n tt om a k ef u r t h e ri m p r o v e m e n t o nt h eq u e r yp r e c i s i o n t h e nw ep r o p o s e dt h ep n - i n d e xa n dp e - i n d e x ，a n ds o m eq u e r y a l g o r i t h m sb a s e do nt h e s ei n d i c e s f o ra l lt h ei n d i c e sa n da l g o r i t h m s ，w em a d e s u f f i c i e n te x p e r i m e n t st ot e s t i f ya n dc o m p a r et h e i rp e r f o r m a n c e i nt h ew e bb i b l i o g r a p h yr e t r i e v a ln a v i g a t i o n ，w ei n t e n d e dt op r o v i d ea na s s i s t a n t w e bb i b l i o g r a p h yr e t r i e v a ln a v i g a t i o nt o o lt ou s e r s w ep r o p o s e dn e wa l g o r i t h m st o m i n et h em s f p ( m a x i m u ms e q u e n t i a lf r e q u e n tp h r a s e ) f r o mt h eb i b l i o g r a p h ya si t s f e a t u r e ，a n db u i l ta l le f h t ( e x t e n d e df e a t u r eh i e r a c h yt r e e ) b a s e do nt h eh i e r a c h i c a l r e l a t i o n s h i pa m o n gt h ef e a t u r e s f i n a l l y , w ed e s i g n e dar e t r i e v a ln a v i g a t i o nf r a m e w o r k a n di m p l e m e n t e dap r o t o t y p e t h i sr e t r i e v a ln a v i g a t i o nt o o lp r o v i d e dt h r e ek i n do f r e t r i e v a ln a v i g a t i o nt ou s e r , a n dc a ne f f e c t i v e l yh e l pu s e rf i n dt h en e e d e di n f o r m a t i o n k e yw o r d s ：d a t am i n i n g ，t e x tm i n i n g ，w e bm i n i n g ，i n f o r m a t i o nr e t r i e v a l ，x m lq u e r y 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 凌刽 e t 期：砂易争纠 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：蒙刽 签字日期：渺6 年。目 导师签名： 签字日期： 东北大学硕士学位论文第一章绪论 1 1 问题提出 第一章绪论 i n t e m e t 的出现是信息社会的一个划时代的飞跃，为我们的社会带来了前所未 有的变革。在i n t e m e t 上充斥着海量的信息，它们内容丰富，并且形式各异，如： 平面文本，h t m l 网页，x m l 文档等。这些信息一方面为人们的生活提供了极大 的方便和帮助，另一方面也使得人们淹没在信息的海洋中而无所适从，无法有效 地查找有用的信息。 为了解决这些问题，数据挖掘和信息检索技术应运而生。数据挖掘，又称知 识发现，是在数据库或数据仓库中提取隐含的、先前未知的、潜在有用的知识或 信息模式的决策支持方法【1 7 】。利用数据挖掘技术，可以对i n t e m e t 上的信息中进行 分析处理，从而得到其中隐含的知识或者规律。信息检索是一种在文本中查找与 用户输入相匹配的过程，它可以帮助人们在i n t e m e t 上搜索用户指定的信息。搜索 引擎作为信息检索技术的产物，已经成为i n t e m e t 最为广泛的应用之一。 以往的研究人员在w e b 数据挖掘和信息检索领域作了大量的研究，并取得了 丰硕的成果。这些技术和研究成果为用户提供了巨大的方便，人们可以很容易的 在i n t e m e t 上获取信息。但是，现有的技术仍然存在着不足，典型的问题有： ( 1 ) x m l 格式文件的信息检索。传统的信息检索技术主要探讨的检索对象为平 面文档，在平面文档中仅仅包含内容信息，而不包含结构信息。而x m l 文档不同 于平面文档就在于它其中包含大量的结构信息，即：文档的某部分和另一部分之 间存在着语义层次包含关系。在这种情况下，传统的信息检索技术由于不能较好 地利用这种结构信息，因而其检索结果往往不尽如人意。 ( 2 ) w e b 信息检索导航。现有的搜索引擎都是在原始的文档上进行检索，如： 网页，d o c 或p d f 格式的论文等。但是，它们既没有对文档的内容进行挖掘，也没 有分析文档内容之间关系，如：网页的关键词，网页描述主题的语义层次关系。 因此，无法为用户的搜索提供导航和个性化的搜索服务。 1 2 课题来源 本文的研究来源于以下课题：“i n t e m e t 上支持高质量e s e r v i c e s 的零输入个 性化技术的研究 ( 国家自然科学基金资助，项目批准号：6 0 1 7 3 0 5 1 ) 和“面向 新一代搜索引擎的用户动机模型推导的研究 ( 国家自然科学基金资助，项目批 准号：6 0 5 7 3 9 0 ) 。前者在对个性数据采集技术、w e b 数据仓库技术、面向个性化 东北大擘硕士学位论文第一章绪论 的w e b 数据挖掘技术、个性化规则解析技术以及个性化服务推荐技术等关键技术 进行研究的基础之上，提出了一种结台数据挖掘、规则解析和信息集成技术的c m r ( c o l l e c t i n gm i n i n gr e c o m m e n d i n g ) 个性化方法，并设计和实现了个性化推荐系 统s m a r t w e b 。后者研究面向新一代搜索引擎的用户模型的特点、结构及建模技术， 从分析“用户想要查询什么”和“用户为什么要进行这样的查询”问题入手，采 用机器学习、概率统计、人工智能、自然语言处理、w e b 流数据挖掘和文本挖掘 技术，结台行为科学和认知科学理论，研究并实现用户模型的分析和推演机制以 及辅助信息的内容和结构，最终建立一个具有辅助搜索引擎分析和推演功能的用 户模型原型，并且在现有搜索引擎环境下，实现个基于该用户模型的、具有新 一代搜索引擎功能的前端工具。 1 3 本文的研究工作 在后面的章节中，首先介绍了本文的研究工作涉及到的基本理论和背景知识， 包括：数据挖掘和文本挖掘、w e b 数据挖掘和信息检索、x m l 文档及其查询的相 关概念和技术等；然后，针对前面所提出的问题，本文分别提出了相应的解决方 案，并给出了实验结果和结论。 在x m l 文档的查询方面，本文根据现有的x m l 文档查询语义，提出了x m l 文档模式和实体的概念，用于提高查询的准确度；对于x m l 文档关键词查询和半 结构查询，设计了相应的索引结构和商效的查询算法。在w e b 信息检索导航方面， 本文提出了挖掘文献的最大序列频繁模式、以及构建w e b 文档特征层次的算法， 并在此基础上设计并实现了一个w e b 信息检索导航框架，该框架包含了三种有机 结合的w e b 信息检索导航的方式。 1 4 本文的组织结构 本文共分六章，各章的主要内容如下： 第一章为绪论。介绍了在w e b 数据挖掘和信息检索领域存在的问题，并概述 了本文的研究工作。 第二章为介绍了和本文工作相关的概念与技术，包括：数据挖掘的基本概念， 文本挖掘的预处理和主要技术w e b 挖掘和信息检索的研究现状，以及x m l 文档 模型、编码、索引和查询技术等。 第三章为基于语义的x m l 文档信息检索。论述了本领域的相关工作，阐述了 x m l 文档检索语义相关的概念，并在此基础上提出了一种新的索引结构和查询算 法，并作了实验比较和分析。 法并作了实验比较和分析。 东北大学硕士学位论文第一章绪论 第四章为基于x m l 文档模式与实体的半结构查询。提出了x m l 文档模式和 实体的概念，用以x m l 查询的精确语义相关；提出了x m l 文档半结构查询并解 释了其语义，设计了相应的索引和高效的查询算法，作了全面的实验比较和分析。 第五章为基于w e b 文档特征层次的信息检索导航。首先介绍了本领域的相关 工作，然后依次介绍了最大序列频繁模式的概念和挖掘算法，w e b 文档特征层次 的定义和创建，以及w e b 信息检索导航的框架和设计实现。本章最后给出了该系 统的实验和用例分析。 第六章总结了本文所做的工作和贡献，并指出了进一步的研究方向。 东北大学硕士学位论文第二章相关概念与技术 第二章相关概念与技术 本章将介绍与本文研究相关的概念、理论和技术，包括：数据挖掘，文本挖 掘，w e b 挖掘和信息检索，x m l 文档查询等。 2 1 数据挖掘 若干年来，随着计算机技术的不断发展，特别是数据库技术和i n t e m e t 的应用 和普及，各行各业都积累了海量的、以不同形式存储的数据资料，并且这些数据 资料正在以指数速度增长。如何让这些数据资料为决策服务，已成为极其艰巨的 任务。首先，用户感兴趣的不是大量的数据，而是隐藏在数据中的知识、模式或 趋势；其次，知识的提取，靠用户手工是难以完成的。因此，一种新的、由控制 程序自动完成知识提取的技术数据挖掘技术应运而生。 数据挖掘( d a t am i n i n g ) ，又称知识发现，是在数据库或数据仓库中提取隐 含的、先前未知的、潜在有用的知识或信息模式的决策支持方法。数据挖掘技术 自出现以来，经过不断的探索与开发，已经取得了长足的发展，并在银行、保险、 电信和公司管理等许多部门得以应用。 数据挖掘一般由3 个主要阶段组成：数据准备、挖掘操作、结果的表述和解 释。数据准备阶段包括数据选择和样本数据预处理。首先根据数据挖掘方法和工 具的要求选择合适的数据( 样本、训练集、测试集等) ，并对选择的数据进行预 处理( 离散化、连续化、编码等) 。挖掘操作包括规则发现和规则分析及建模。 首先将确定的数据挖掘算法在预处理后的数据中执行，得到相应的结果( 规则) ， 再对结果进行辨证分析并将其用于预测、预报等建模工作中。结果的表述和解释 阶段是将建模的结果以用户容易理解的、能够接受的形式信息可视化技术展 现给用户，为其提供满意的决策支持。 2 2 文本挖掘 随着网络上w e b 页面的激增，以及文本数据库对各种形式文本统一管理和存 储，仅仅依靠手工来对这些文本资源进行处理是不可能的。人们迫切需要由计算 机自动地对这些大规模的文本集合进行有效地处理和分析，其中包括分类、聚类、 自动摘要等等。于是，针对于文本的数据挖掘方法应运而生。相对于传统数据挖 掘算法所针对的关系的、事务的和数据仓库的数据，文本挖掘面对的是由来自各 种数据源( 如新闻文章、研究论文、书籍、数字图书馆、电子邮件消息和w e b 页 东北大学硕士学位论文 第二章相关概念与技术 面) 的大量的文档集合。文本挖掘所处理的是半结构化的或者是非结构化的数据。 半结构化的数据如w e b 页面、x m l 文档等，它们中可能包含结构字段，如标题、 作者、出版日期、长度、分类等，也可能包括大量的非结构化的文本成分，如摘 要和内容。相对于结构化数据，半结构化和非结构化数据上的数据挖掘面临着更 大的挑战，同时，也具有非常广阔的应用前景。 2 2 1 文本预处理 在文本上进行挖掘与传统数据库上挖掘的一个重要的区别就是，文本是非结 构化的数据。为了把数据挖掘的算法应用与文本对象之上，就必须对文本进行预 处理，使文本最终表示成为一种结构化形式，同时需要保证这种结构化的形式能 够充分体现出文本对象自己的特点，突出文本对象间的差异，以便于对文本的区 分。主要包括以下几个步骤： ( 1 ) 分词。分词是将一篇连续的文本分解为词的集合的过程【1 3 1 。对于英文文本 来说，分词是容易的，因为英文单词之间是用空格分隔开的。然而对于中文，词 与词之间往往没有间隔，同时语法灵活多变，分词要复杂的多。实际应用中使用 的中文分词的方法有两种：基于语义的分词和简单的匹配算法。前者是根据建立 的语言模型，通过概率统计或者自然语言处理的方法来确定词之间的划分。后者 将文本中的最长公共字符串作为分词的结果。 ( 2 ) s t e m m i n g 。在英文文本中，由于时态和语态的差异，同一个单词可能会有 不同的后缀，从而构成了不同的单词。但在文本处理时，若将他们看作不同的单 词则会影响算法的质量。s t e m m i n g 操作是针对英文文本的，它将不同时态和语态 下的英文单词作标准化处理，即：把各种时态和语态下的单词，进行词干还原处 理。本文采用文献1 3 l 】中的s t e m m i n g 算法。 ( 3 ) 停用词处理。在中文和英文的文本中，都存在一些对文本内容识别意义不 大的词，称之为停用词，如：“的”，“了”，“o f 等。在预处理过程中，这些 词将从文本中除去。 ( 4 ) 特征选取。文本经过上述步骤处理之后，可以得到一个词空间7 。特征选 取的目的就是得到t 。ct ，使得r 中的词能够最大程度的反映文本的内容特征。特 征选取的方法可以分为两类：一类是在单独的文本中选组，另一类是在文本集合 中选取。后者由于选取的词不仅仅能体现单独文本的内容，而且能较好的区分不 同的文本，因此应用较为广泛。常用的有t f i d f 1 9 ，潜在语义索引【9 】等方法。 ( 5 ) 文本表示。文本预处理的最终目的是将无结构的文本，转换为利于算法处 理的结构化数据。一般作法是用文本词空间中的词构成特征向量，并添加词的权 东北大学硕士学位论文第二章相关概念与技术 重等信息，以此表示文本。常用的文本表示方法有向量空间模型和b o w ( b a go f w o r d ) 方法等。 2 2 2 文本聚类 聚类是将物理的或者抽象的对象集合分组成为由类似的对象组成的多个簇的 过程。文本聚类的处理对象是文本的集合，根据文本的语义或主题，将其分为不 同的簇。它有着广泛的应用，如：网页搜索引擎结果聚类，信息检索推荐，以及 和文本分类协同工作等。 按照单个文本所属的簇的数目，文本聚类可分为硬聚类和软聚类。前者聚类 结果中，一个文本只能属于一个簇，而后者可以属于多个。按照聚类过程使用的 方法，文本聚类有如下几种典型的方法【17 】： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) f 2 6 】：给定一个m 个对象的数据集，在其 上构建n 个划分，每个划分表示一个簇，且n m 。同时满足：每个簇至少包含 一个对象；每个对象属于且只属于一个簇。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) 【2 l 】：对给定的数据对象集合进行层次分解。 具体可采取凝聚的方法，即将每个对象视为一个簇，相继合并相近的簇构成更大 的新簇，直至达到一个终止条件。也可采取分裂的方法，即将所有的对象视为一 个簇，然后相继分裂不相近的簇为若干个更小的新簇，直至满足终止条件。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 1 1 , 1 2 , 1 8 ：这类方法根据每个簇的密 度阈值、而不是簇的数目阈值控制聚类的过程，即：只要临近簇的密度超过某个 阈值，就继续聚类，聚类终止的条件是满足密度要求。其优点是可以发现任意形 状的簇。 ( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d ) 1 2 0 ：这类方法将对象空间量化为有 限数目的单元。形成一个网格结构，所有的聚类操作均在此网格结构上进行。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 4 5 】：为每个簇假定一个模型，寻 找数据对给定模型的最佳拟合。模型的类型一般需要提前指定，再通过模型选择 算法来确定模型的结构，最后进行模型参数估计。 事实上，在实际应用中，根据具体应用领域的聚类要求，其聚类方法常常要 综合多种聚类技术。 2 2 3 文本分类 文本分类是一种有指导的的文本处理过程。它先用带有类标签的文本训练一 个文本分类器或分类规则，然后以此对未知类别的文本进行分类。常用的文本分 东北大学硕士学位论文第二章相关概念与技术 类方法有如下几种： ( 1 ) 支持向量机【37 3 8 】：该模型建立在v c 维理论和结构风险最小原理基础上的。 支持向量机的基本思想是使用简单的线形分类器划分样本空间。通过学习算法， s v m 可以自动寻找那些对分类有较好区分能力的支持向量，由此构造出可以最大 化类和类的间隔的分类器，因而有较好的推广性能和较高的分类准确率。它的优 点是：对高维、稀疏数据不敏感，较好的捕捉了数据的内在特征，以及准确率较 高。缺点在于样本映射核函数选择困难，且召回率较低。 ( 2 ) k n n ( k 最近邻) 算法【4 4 】：该算法的基本思路是：在给定一篇新文本后， 考虑在训练文本集中与该新文本距离最近( 最相似) 的k 篇文本，根据这k 篇文 本所属的类别判定新文本所属的类别。它的优点是适合于概率密度函数的参数形 式未知的场合。缺点在于计算时间长，以及很难找到一个最优的k 值。 ( 3 ) 朴素贝叶斯算法【1 7 】：该算法利用了贝叶斯后验概率公式，并假设各个类的 先验概率和文档概率二致，以及词与词相互独立。它首先利用词空间中所有词的 概率训练一个分类器，再用词分类器做文本分类。它的优点在于：对于文本数据 和数值数据分类效果较好，且易于实现和计算。缺点是独立性假设在现实中很容 易被打破；在特征项之间高度相关的情况下，算法性能很差。 2 3w e b 挖掘和信息检索 2 3 1w e b 挖掘技术 w e b 挖掘是以w w w 上的资源( 如网页内容、用户访问数据、w e b 网站结构 等) 作为数据源的数据挖掘技术，所以，w e b 挖掘定义为从w w w 上相关数据中 抽取用户感兴趣的、潜在有用的模式和隐含的信息的过程【5 ，4 7 1 。w e b 挖掘是将传统 的数据挖掘和w e b 结合起来的一种技术。目前，在i n t e m e t 上存在着海量并且不断 增长的信息，如何对这些信息进行有效地挖掘和知识发现具有重大的现实意义。 根据w e b 数据源的不同种类，可以将w e b 挖掘分为如下几种： ( 1 ) w e b 内容挖掘。w e b 内容挖掘是从网页上的数据，如：w e b 文档或者脚本 中抽取知识的过程。w e b 上的文档内容不同于其他数据源，是半结构化或者非结 构化的，而且其内容的语法和语义是机器难以表达的。因此，需要采用一些新的 技术对w e b 文档进行重构。同时，由于w e b 页面的内容包括文本、图形、图像、 音频和视频等多种形式，所以，w e b 内容挖掘实际上也是对多媒体数据的挖掘。 ( 2 ) w e b 结构挖掘。w e b 结构指w e b 内容的组织形式，w e b 结构挖掘是从w w w 组织结构和w e b 页上引用链之间抽取知识的过程。由于文档之间的互连，w w w 东北大学硕士学位论文 第二章相关概念与技术 能够提供除文档内容之外的有用信息。利用这些信息，可以挖掘出新的知识或模 式。 ( 3 ) w e b 使用挖掘。w e b 使用数据是指网页被用户使用的记录，而 w e b 使用挖 掘是从这类记录文件中抽取感兴趣的模式的过程。i n t e r n e t 上每个服务器都保留了 访问日志和与之相关的一些日志文件，记录了关于用户访问和交互的信息。分析 这些数据可以帮助网站管理者理解用户的行为，从而改进网站的结构，或者为用 户提供个性化的服务。 表2 1 从五个方面对三种w e b 挖掘技术做了比较1 4 6 】。 表2 1w e b 挖掘分类 t a b l e 2 1t h ec l a s s i f i c a t i o no fw e bm i n i n g w e b 内容挖掘w e b 结构挖掘w e b 使用挖掘 数据 非结构化半结构化 半结构化、数据库形 交互形式 形式式的网站，链接结构 数据服务器日志记录，浏 来源 文本文档，超文本文档超文本文档，链接 览器日志记录 数据 b a go f w o r d s 、n - g r a m s 、 边界标志图( o e m ) 、 词、短语、概念或实体、关系型表、图形 表示 关系型数据、图形 关系型数据 所用 t f i d f 和变体、机器学 p r o p r i e t a r y 算法、i l p 、p r o p r i e t a r y 算法、机器 习、统计学( 包括自然( 修改后) 的关联规学习、统计学、( 修 方法 语言处理)则改后) 的关联规则 主要 归类、聚类、发掘抽取发掘高频的子结构、站点建设、改进与管 规则、发掘文本模式、发掘网站体系结构、理、营销、建立用户 应用 建立模式归类、聚类模式 2 3 2w e b 信息检索 信息检索并不是w e b 所特有的一个研究课题。早在上一世纪5 0 年代，当计算 机被图书馆等部门用于存储和管理文档时，信息检索就作为一个研究领域而诞生 了。到二十世纪8 0 年代，信息检索领域己经在文档内容表示、索引模型、匹配策 略等方面取得了丰硕的成果，并成功地开发了一些系统。w e b 的出现为信息系统 检索提供了一个前所未有的实验环境和应用环境，许多w e b 信息检索系统应运而 生，例如：y a h o o ，a r a v i s t a ，g o o g l e 等。同时，w e b 信息的大容量、异构性、分 布性和动态性给信息检索领域带来了新的挑战。需要在传统信息检索技术的基础 上开展针对w e b 特点的研究工作。 信息检索的基本原理是对信息集合与需求集合的匹配与选择，信息检索的主 要特征为：信息表示、信息需求表示、匹配计算和有效性评价。目前评价检索系 东北大学硕士学位论文第二章相关概念与技术 统性能或质量的主要指标是查全率( r e c a l l ) 和查准率( p r e c i s i o n ) 。查全率指系统 在实旆某一检索作业时，检出相关文献的能力。查准率指系统在实施某一检索作 业时，拒绝不相关文献的能力。常用的数学模型般有布尔检索模型、向量空间 模型和概率检索模型和模糊集合模型。目前i n t e r n e t 上信息检索模型多采用布尔检 索模型和向量空间模型及其变种。检索方法主要可分为三种：搜索引擎、个性化 信息过滤系统和辅助浏览系统( a s s i s t e db r o w s i n gs y s t e m ) 。 基于w e b 的信息检索与传统的信息检索相比，既有着许多共同点，也有如下 特点： ( 1 ) 信息服务的综合性。由于采用知识库导航，搜索引擎给用户提供更全面、 更综合的信息服务，在这里，信息检索只是信息服务的一部分。 ( 2 ) 信息服务的智能性。w | e b 信息检索，有综合知识库作为背景，信息检索和 导航服务将更智能化。因为w e b 中的语言层面知识有助于解决“表达差 问题， 同义词关系可以消除用户由于使用不同的词表达同一概念而带来的检索困难。另 一方面，根据w e b 的常识性和层次性知识对用户的查询进行相关性联想，提供引 导用户进行下一步查询的线索。 ( 3 ) 信息服务的个性化。i n t e r n e t 的知识库可以存放与具体用户相关的知识( 用 户专业兴趣、购买力等) ，搜索引擎将利用这些知识来为用户提供个性化信息服务。 ( 4 ) 具有支持代理( a g e n t ) 的能力。由于w n 服务器端有综合性知识库，为 智能代理的活动提供了基础。例如：活动在客户端的智能代理可以对用户正在浏 览的网页进行主动观察、分析内容，根据服务器端的知识库来推荐内容相近的其 他网页提供给用户参考。 2 4 舭文档查询 互联网目前已经成为全球信息传递与共享的重要资源和途径。随着i n t e m e t 的 发展，异构信息源集成以及存储技术的进步，网络中涌现出大量诸如w e b 页面和 x m l 文档等半结构化数据资源。x m l 逐渐成为数据表示、存储和交换标准之一。 如何高效表示、存储和查询x m l 文档引起越来越多的研究人员的关注。 2 4 1x m l 文档模型 o e m 模型是由斯坦福大学y p a p a k o n s t a n t i n o u 等人于1 9 9 5 年提出的，用于描 述半结构化数据，并被用于斯坦福大学的t s i m m i s 系统中，该系统用于异构数据源 的集成。由于x m l 数据是由半结构数据发展而来的，因此o e m 模型逐渐成为主 要x m l 数据模型之一。 东北大学硕士学位论文 第二章相关概念与技术 目前，典型x m l 文档数据模型有两种：对象交换模型( o b j e c te x c h a n g em o d e l ， o e m ) 和文档对象模型( d o c u m e n to b j e c tm o d e l ，d o m ) 。 ( 1 ) 对象交换模型( o e m ) 在o e m 模型中，半结构化数据可以用一个有向的标记图来表示，如图2 1 所 示。一个o e m 对象由一个四元组 表示，其每个域的意义 如下： ( a ) l a b e l ( 标注) ，变长字符串，描述对象的意义； ( b ) t y p e ( 类型) ，对象值的类型，包括两种：一种为原子型( a t o m i c ) ，如i n t e g e r ， s t r i n g ，r e a l ，i m a g e 等；另外一种为复杂类型( c o m p l e x ) ，包含零个或多个子对象， 每个子对象用一条带标记的边与其相连。 ( c ) v a l u e ( 值) ，对象的值； ( d ) o i d ( 对象标识) ，用于唯一标识每个o e m 对象。 。2is 。4 。5 巷吉三6 凼t i t k o 7 东北大学硕士学位论文 第二章相关概念与技术 5 0 0 , - 劝拶柳 对x m l 文档进行编码是x m l 文档处理的基础，x m l 文档编码的过程就是对 x m l 文档中所有元素节点分配一个唯一标示的过程。典型的x m l 文档的编码方 案有两类：基于区间的编码( r e g i o n - b a s e de n c o d i n g ) 和基于路径的编码( p a t h b a s e d e n c o d i n g ) 。 ( 1 ) 基于区间的编码利用x m l 文档的有序特点，根据每一个元素节点在原 x m l 文档中出现的先后顺序给每一个元素节点赋予一个编码。编码中一般包含该 节点的起始位置、结束位置、节点层次和大小等信息。 ( 2 ) 基于路径的编码是利用x m l 文档的嵌套特点，根据从x m l 文档的根节 点各个元素节点的路径的节点信息，构成该节点的编码。因此，由某个节点的路 径编码，可以得到该节点所有祖先节点的编码信息。 2 4 3x m l 文档索引 索引技术是数据库中广泛采用的一种优化数据访问的技术。对于x m l 文档， 其中往往包含着大量的节点和丰富的信息。为了避免频繁地扫描整个x m l 文档， 需要对x m l 文档中的节点及其中的信息建立索引。 ( 1 ) 结构索引。针对x m l 文档和节点结构所建立的索引称作结构索引。结构 索引保持了原x m l 文档中所有的路径信息，路径查询可以在结构索引的辅助下加 快查询速度。典型的结构索引有d a t a g u i d e 16 1 、1 - i n d e x 2 8 1 、a ( 妨。i n d e x ：2 1 和 d ( 妨i n d e x 4 1 等。 东北大学硕士学位论文第二章相关概念与技术 ( 2 ) 倒排索引。倒排索引是针对x m l 文档中包含的节点信息的索引，如：节 点编码和包含的文本信息等。倒排索引中每一项通常由两部分组成：关键字k 和 索引链表，在x m l 查询中，索引列表中每一项通常为一个三元组( d o c i d ，n o d e i d ， w e i g h t ) ，其中d o c i d 为包含关键字k 的x m l 文档i d ，n o d e l d 为包含关键字k 的节点编码。 2 4 4x m l 文档查询 对于x m l 文档查询，根据查询表达式所包含的目标x m l 文档结构信息的多 少，可以分为三类：结构查询，关键词查询和半结构查询。其中，结构查询表达 式中的结构信息准确地描述了对于查询结果的结构性要求，如：查询结果中节点 的父子、祖孙关系等；关键词查询中不包含任何结构性要求，而只包含内容性要 求；半结构查询介于二者之间，查询用户可以根据对于x m l 文档结构的了解程度， 在查询表达式中指定部分结构信息。 2 4 4 1x m l 文档结构查询 结构查询是指用户根据x m l 文档完整的结构信息说明而编写的准确反映用 户查询意图的查询表达式。对于结构查询，查询结果与用户的查询意图之间不存 在差异，返回的结果是精确的。例如：对于图2 3 ( a ) 所示的x m l 文档，如果用户 要查找作者是m a r y 的文章的题目，就可以用图2 3 ( b ) 所示的x q u e r y 查询表达式 来描述用户的查询意图。 c o n f e r e n c e ( 1 ) a r t i c l e ( 2 )a r t i c l e ( 7 ) a u t h o r ( 3 ) t i t l e ( 5 ) a u t h o r ( 8 ) t i t l e ( 1 0 ) 图2 3 ( a ) 一个x m l 文档 f i g 2 3 ( a ) a nx m ld o c u m e n t f o r $ a ri nc o n f e r e n c e a r t i c l e ， s a ui n $ a r a u t h o r , $ ti ns a r t i t l e w h i l e $ a u = “m a n ， r e t u ms t 图2 3 ( b ) x q u e r y 查询表达式 f i g 2 3 ( b 1x q u e r yq u e r ye x p r e s s i o n 其中，x q u e r y l 4 3 1 是w 3 c 发布的x m l 文档查询语言。常用的x q u e r y 查询表 达式有路径表达式和f l w o r 表达式： ( 1 ) 路径表达式。x q u e r y 中的路径表达式沿用了x p a t h 4 2 1 的语法，使用标签 东北大学硕士学位论文第二章相关概念与技术 路径从x m l 文档中选取需要的节点。例如：c o n 诧r e n c e a n i c l e t i t l e 。 ( 2 ) f l w o r 表达式。f l w o r 表达式是x q u e r y 的重要的语法类型。f l w o r 分别代表f o r ，l e t ，w h e r e ，o r d e r 和r e t u r n 关键词。每个f l w o r 表达式可以有一 个或多个f o r 子句和l e t 子句、一个可选的w h e r e 子句和o r d e r 子句、以及一个r e t u r n 子句。其中，f o r 子旬和l e t 予句为每个表达式赋予一个变量，前者利用变量循环遍 历表达式指定的每个节点，后者将该变量绑定到整个节点序列：w h e r e 子旬指定条 件对绑定的变量进行过滤；o r d e r 子句指定返回结果的排列顺序；r e t u r n 子句构造 f l w o r 表达式中的结果。 2 4 4 2x m l 文档关键词查询 关键词查询是在用户事先不知道目标文档结构的情况下，提交的x m l 文档查 询。在查询表达式中仅仅包含指定的关键词，因此，查询表达式不能准确地反映 用户的查询意图，返回的结果是不精确的。它基于传统文本的信息检索技术，主 要解决查询语义、结果排序等问题。 ( 1 ) 查询语义。在关键词查询中，查询表达式包含了若干关键词。其查询结果 通常是基于l c a ( l o w e s tc o m m o na n c e s t o r ) 3 4 】方法，即：返回一个x m l 文档中 层次最低的节点，并且在该节点及其祖孙节点中包含了查询表达式中的所有的关 键词。例如：对于图2 3 ( a ) 所示的x m l 文档，如果提交的关键词查询为“m a r y x m l ”，则包含m a r y 和x m l 节点的a r t i c l e 节点是一个查询结果。 ( 2 ) 查询结果排序。在查询结果排序中考虑的因素通常有：通过t f i d f 方法 计算x m l 文档中关键词和标签的权重，查询结果与查询表达式的相似性，以及查 询结果的大小等。 2 4 4 3x m l 文档半结构查询 半结构查询是查询表达式中包含部分结构性要求的查询。用户对x m l 文档的 结构有部分了解时，可根据对其结构的了解程度，在查询表达式中指定相应的信 息。例如：对于图2 3 ( a ) 所示的文档，如果用户要查询作者为m a r y ，标题为x m l 的文档，并且知道目标文档中作者节点的标签名为a u t h o r ，标题节点的标签名为 t i t l e ，则查询表达式为a u t h o r ：m a r y ，t i t l e ：x m l ；如果知道需要查询的a u t h o r 节 点和t i t l e 节点都是c o n f e r e n c e 节点的孩子节点，则查询表达式为c o n f c r e n c e a u t h o r ： m a r y