（电路与系统专业论文）一种基于XML的信息搜索技术[电路与系统专业优秀论文].pdf

摘要 近年来，x m l 技术及其应用正受到越来越广泛的重视，随着更多的数据以x m l 的格式组织起来，基于) ( m l 的数据挖掘技术也正日益受到关注，其中，如何从 x m l 数据库中进行信息的搜索是较为活跃的研究领域之一。本文对“基于x m l 的 信息搜索”这一题目进行了研究，主要工作有以下几个方面： 1 在单一源文档t 中搜索用户需求d t 目前，诸多关于此类的研究都致力于已经存在的两个文档t 。，t 。之间的相似 性比较上，而对如何进行信息搜索的研究相对较少。本文首先分析了文档间相似 性的衡量问题，针对以往算法所普遍具有的运算复杂度高的缺点，从文档本身具 有的结构特性出发，提出了基于倒向路径( l r ) 的信息搜索方法，并在该方法 的基础上，给出了d t 同t 之间的匹配度计算公式，从算法可以看出，该算法的 运算复杂度随着j ( m l 文档结构的复杂程度而线性地变化。 2 在x m l 数据库( 即) ( m l 文档集合) 中搜索用户需求d t 在实际应用中，普遍发生的情况是从某一x m l 数据库s t 中搜索同用户需 求d t 相关的信息。对于庞大的x m l 数据库而言，不可能从中拿出每一个文档同 d t 加以比较，尤其是当用户一次提出多个搜索需求d t 或多个用户同时提出需求 时，其运算的量也将加大，为解决这一问题，本文对x m l 数据库进行预处理，将 那些同d t 相关的信息先整理出来，以各后用。这种想法对于多需求的搜索来说 尤为重要。 首先，本文对数据库的预处理进行了研究，基本思想是：将用户的搜索需求 d t 归入到) ( l 数据库s t 中，形成新的x 札文档集合s t 。在新的文档集合s t 上进行聚类操作，以找到那些在结构和描述内容上同d t 相关的文档。 其次，针对x m l 本身所具有的结构化，自描述性等特点，在聚类操作中引入 了p b c ( p a t h b a s e d c l u s t e r i n g ) 聚类算法，并分析了该算法在用于信息搜索 时的不足，根据这一不足提出d t d 映射的概念并加以改进，解决了诸如“结点缺 失”“结构拓展”等问题，使算法对同一结构的不同组织方式的辨别能力更加灵 活，与此同时，d t d 映射中所创建的路径表识结点a 。和“层次”属性有助于进行 搜索和匹配度运算( 第三章) 时对被搜索内容进行准确的定位。在文章的最后部 分，本文还在已做讨论的基础上给出了基于x m l 的信息搜索模型。 关键词：信息搜索； ) ( m l ；聚类；匹配度； p b c a b s t r a c t t h e s ey e 甜s ，w ep a ym o r e 觚dm o r ea t c e n t i o nt ot h ex m lt e c h n i q u ea n di t s a p p l i c a t i o n w i t hm o r ed a t ai so 昭a n i z e di l lm ef o r n lo fx m l ，t h er e s e a r c h e so fx m l b a s e dd a t m i n i n gb e c o m ep o p u l 毗i nt h e s es t u d i e s ，h o wt oe x t r a c tt 1 1 en e e d e d i n f o n n a t i o nf r o max m ld a 协b a s ei sav e r ya c t i v ed i r e c t i o n 1 1 1m i sp 印e r ，w e d i s c u s st h ea n i c l eo fx m lb a s e di n f o m a “o nq u e r yt h em a i nw o r k si n c l u d e s 也e f 0 1 l o w i n gs e v e r a la s p e c t s ： 1 i h eq u e r yb e t w e e nu s e r _ d e s c r i b e dd ia n d 廿l cs o u r c ed o c u m e n t i r e c e n t l y ，m o s tr e s e a r c h e sa b o u tt 1 1 i sd i r c c t i o np a ym o r ca t t e n t i o nt om e s i m i i i a r i 哆o ft 、v og i v e nd o c u m e n tt ia 1 1 dt 2l e s sa t t e n t i o ni sg i v e nt o 也eq u e r y i n g m e t h o d “s e l f i nt h i sp 印e r ，w ef i r s td i s c u s ss o m ea l g o r i t h mo fc o m p u t 协gt h e s i m i l i a r i t yb e t w e e nx m ld o c u m e n t s b e c a u s et 1 1 e i rc o m p u t i t o nn e x i b i l i t yi sh i g h ，w e c o n s i d e rt 1 1 es 协l c t u r eo ft l l ed o c 啪e n tt os o l v e 血i sp r o b l e m t h c nw ep r o p o s et h e r e v e r s e d i r e c t i o n - r o u t eb a s e dq u e r ym e t h o dp rw b i c hs t a n d sf o rl e a f i r o o t ) w e a l s od i s c u s sh o wt oc o m p u _ t et o p o l o g i c a lm a t c hd e 伊e e ( 1 h d ) b e t 、e e nd ta i l dt t h e r e s u l tm e a n s ：t l i sa l g o r i t l i l li sa v l i l a b l ea 1 1 de a s yt 0r e a d ，a n o t l e ra d v a l l t a g ei s ：w i m d i 虢r e n tu s e r sn e e d t h ef i n a lr e s l l l t so ft m dc a nb es c a l a b l e 2 t h eq u e r ym e t h o do f u s e r - d e s c i i b e dd ti nx m ld a t a 出a s es t 】 a 洲l yi n 印p l i c a t i o h ，t l l em o s tl i k e l yc a s ei s ：t oe x t m c tt h ei l o l 砒i o ns i m i l a r t 0u s e r _ d e s c r i b ed tf r o max m ld a t a _ b a s es 【t t bt h eh u g cx m l d a t a - b a s e ，i ti s i m p o s s i b l et oc o m p a r ee v e r yd o c u r n e n ti ns t 】谢t hd t i ti sm o r cc o m p l e xw h e nt h e u s e r sg i v eo u ts e v e r a ln e e d so rs o m eu s e r sg i v eo u tt h c i rn e e d si nt 1 1 es 姗et i m e t h u s i ti sn e c e s s a r yt od oap r e p r o c e s so nt h ex m l d a t a - b a s e ，c h e c ko u tm o s ei n f o m a t i o n a s s o c i a t i e dw i t hd it h i si sv e r yu s e f u 1w h e nt h e r ea r em o r em a no n eu s e r sn c e d s d t f i r s t ，w ed i s c u s s 廿l ep r e p r o c e s so ft h ex m ld a t a b a s e t h eb a s i ci d e a i s ，c o m b i n em eu s e r _ d e s c m e dd ti n t o 也ex m ld a b a b 船es m ，s ow eg e tan e w d o c u m e n ts e ts f t ，m a k eac l u s t e r i n go ns mt oe x 廿a c tt h c 如c u m e n tw h o s e s t r u c t u r ea 1 1 dc o n t e i l ti ss i m i l a rw i t hd t n e x t ，w ed i s c u s s 廿l ep b cc l u s t e r i n gm e t h o d ， 矗n d0 u ts o m eo fi t sd i s a d v a 芏1 t a g ea n di m p r o v ei tw k nw eu s ei ti nt h ex m lb a s e d q u e 研g i v eo u tt h ed e f i n i t i o no fd t i ) 一m a p p i n gt os o l v em ep m b l e m1 i k e “1 0 s tn o d e a n d “t o p o l o g i c a lm a t c h ”i n 也ex m l b a s e dq u e r y0 u rm a i nc o n 砸b u t i o ni s ：m a l ( et h e a l g o 矾l n lc a nw o r kw h e nm es 锄es t m c t l l r ei sd e s c r i b e di nd m r e n ts t y l e t h ep a t h n o d ea a n dt h e h i e r a r c h i c a l a t t r i b u t ei nt h ed t d m 印p i n gc a t lh e l pu sc o m p u t em e t o p 0 1 0 9 i c a lm a t c hd e g r e e ( t m d ) a t l de x t r a c tt 1 1 en e e d e di n f o m a t i o ne x a c u yf r o mt 1 1 e s o u r c ed o c m e n tt k e yw o r d s ：i n f o r m a t i o nq u e r y ；x m l ；c l u s t e r i n g ；t o p o l o g i c a lm a t c hd e g r e e ； p b c i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：孳逝数日期：2 亟! 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即：东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：徽 指导教师签名：圈： 日 期：迎1 6 ： 日 期：迎区璺 学位论文作者毕业后去向 工作单位： 通讯地址： 电话 邮编 第一章：引言 1 1 数据挖掘背景 自从计算机问世以来，人们便开始用它做各种事情。f j f j 途涉及数值计算，信 息储存，多媒体娱乐等诸多领域，其中熏要的一项是：人们将口常生活中所产生 和应用的一些数据储存在计算机中。由于计算机的用途越来越广泛因而这些储 存于计算机中的数据量也越来越庞大。数据组织的格式也愈加的繁杂。这些庞大 的数据不仅仅是一条条的记录。更重要的是，它们之中可能包含了人们所感兴趣， 或对我们有重要参考价值的信息。为此，需要对这些数据进行规范的组织并随时 供我们进行查询，数据库技术在此种要求下应运而生。它叫以轻松的实现数据信 息的写入，删除，排序，检索等管理工作。 随着数据库规模的不断扩大，囊括的内容越来越广泛，人们不再满足于它所 能提供的管理工作本身，更多的人开始想知道，这些规模庞大的数据能否为我们 展示出些包含其中的规律，目u 那些“数据背后的故事”。数据挖掘便在这样的 需求背景下诞生了。 1 。2 数据挖掘的概念 数据库中发现知识( k d d ) 词首先出现在1 9 8 9 年举行的第十一届国际联合 人工智能学术会议上“3 ，起初，k d d 的研究内容主要集中于知识模型的发现方法， 随着k d d 技术的逐渐艘展，其研究的内容也从知识发现方法扩大到了系统的应用 领域，同时，k d d 所能处理的数据格式的范围也随之扩大，从传统的关系型数据， 扩展至今天的包含关系型数据库，面向对象的数据库，空间数据库，时态数据库， 文本数据源，多媒体数据库，异构数据库，结构与半结构化数据库以及w e b 在内 的多种数据格式和数据来源。 数据挖掘的基本定义为1 “：从大量的数据中提取出潜在的，新颖的，有价值 的，能被人所理解的模式或信息的高级处理过程。数据挖掘的目的是利用各种分 析工具在大量数据中发现模型和规则，这些模型和规则可以为人们的决策提供指 导或被用来被预襁4 。 1 3 数据挖掘的主要方法 数据挖掘的主要方法可分为分类模型发现、聚类、关联规则发现、序列分析、 数据挖掘的主要方法可分为分类模型发现、聚类、关联规则发现、序列分析、 偏差分析、数据可视化等。针对不同的挖掘需求和数据类型，选择的方法也不同。 1 3 1分类( c l a s s i f i c a t i o n ) 其旨在生成一个分类函数或分类模型，该模型能把数据库中的数据项映射到 给定类别中的某一个。既可以用此模型分析已有的数据，也可以用它来预测未来 的数据。 1 3 2 聚类( c 1 u s t e r i n g ) 聚类是对记录分组，把相似的记录划分在同一个聚类的簇里。聚类和分类的 区别是聚类不依赖于预先定义好的类，不需要训练集。聚类分析的主要依据是把 相似的样本归为一类，而把差异大的样本区分开来。在由m 个变量组成的t n 维的 空间中可以用多种方法定义样本之间的相似性和差异性统计量。聚类的主要方法 有k 均值聚类方法，层次聚类方法等。聚类的主要依据是如何定义两个样本间的 相似性和差异性。聚类可以被应用在信息搜索方面的一个重要理由是，通过聚类， 相似或者有较强相关性的信息被划分为一簇，因此，对某一被搜索信息来说，有 可能使的搜索的范围缩小为其中的一个或几个类中。 1 3 3 数据可视化( d e s c r i p t i o na n dv i s u a l i z a t i o n ) 数据可视化严格地讲不是一个单独的数据挖掘任务，它被用来支持其他挖掘 任务。可视化是采用图形、图表等易于理解的方式表达数据挖掘结果。 1 3 4 关联规则( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l e s ) 关联规则是寻找数据库中值的相关性，主要是寻找在同一个事件中出现的不 同项的相关性，比如在一次购买活动中所买不同商品的相关性。 1 3 5 序列分析( s e q u e n c ea n a l y s i s ) 序列模式分析同样也是试图找出数据之间的联系。但它的侧重点在于分析数 据之间前后( 因果) 关系，因此对数据往往要求引入时间属性。序列模式分析非 常适于寻找事物的发生趋势或重复性模式。 1 3 6 偏差分析( d e v i a t i o na n a l y s i s ) 是用来发现与正常情况不同的异常和变化，并进一步分析这种变化是否是有 意的诈骗行为，还是正常的变化。如果是异常行为，则提示预防措施；如果是正 常的变化，那么就需要更新数据库记录。 1 4 数据挖掘系统 一个完整的数据挖掘系统建立在某一个数据库和某一个挖掘任务之上，并有 对应的挖掘算法为其服务，数据挖掘的最终目的是产生知识，该知识可以被人所 解释和接受，并对人们的行为判断有指导作用。 图1 1 为一个典型的数据挖掘系统原型。，在该系统中，数据挖掘管理器和 挖掘内核即挖掘算法是其重要组成部分，担当了整个挖掘任务中的大部分工作。 用户首先产生其需求，然后由用户向数据挖掘管理器提出请求，确定挖掘任务。 根据挖掘任务选择一定的算法应用于数据库之上，挖掘产生的信息经过一定的解 释及表达，产生可被用户理解的信息并最终反馈给用户。在整个数据挖掘原型中， 还包含了“数据预处理”等同挖掘相关的重要步骤。 图1 1 一个数据挖掘系统原型 对于基于x m l 的信息搜索，其中的用户需求同d t 相对应，被挖掘的对象为原始 数据即x 札文档集合，挖掘算法对应搜索方法。模式表达与解释即为x m l 信息片 断的抽取与再现。 1 5 数据挖掘的应用 数据挖掘目前在医学、电信、零售业等多个应用领域均有成功的应用案例。 随着越来越多的业务需求被不断明确，数据挖掘应用的领域和解决的问题会越来 越广泛；一些应用系统，如e r p 、s c m 、h r 等系统也逐渐与数据挖掘集成起来， 用以提高系统的决策支持能力。这方面的研究热点包括数据挖掘与商业智能 ( b i ) 、c r m 、w e b 应用的结合。 1 6 数据挖掘和w 阻挖掘 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检 索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和 推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据 对未来的活动进行预测。随着数据挖掘技术的研究逐步走向深入，人们发现，数 据挖掘的研究主要有3 个技术支柱，即数据库、人工智能和数理统计。 目前，国外在数据挖掘方面的发展趋势及研究主要有：对知识发现方法的进 一步研究，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提 高：统计学回归法在k 叻中的应用；k d d 与数据库的紧密结合；对网络信息挖掘 方法的研究等。国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软 都成立了相应的研究中心，一些公司的相关软件也开始在国内销售，如 p l a t i n u m 、b 0 以及i b m 。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行的，如 国家自然科学基金、8 6 3 计划、”九五”计划等。 数据挖掘渗透于人们工作生活的每一个领域，尤其是在那些大量产生数据的 行业和领域中，数据挖掘正扮演着越来越重要的角色。其中一个重要的应用是基 于1 i r e b 的数据挖掘。近年来，随着i n t e r n e t w e b 技术的快速普及和迅猛发展， 使各种信息可以以非常低的成本在网络上获得，由于i n t e r n e t w w w 在全球互连 互通，可以从中取得的数据量难以计算，而且i n t e r n e t w 唧的发展趋势继续看 好，特别是电子商务的蓬勃发展为网络应用提供了强大支持，如何在w w w 这个全 球最大的数据集合中发现有用信息无疑将成为数据挖掘研究的热点。w e b 挖掘指 使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信息。w e b 挖掘研究 覆盖了多个研究领域，包括数据库技术、信息获取技术、统计学、人工智能中的 机器学习和神经网络等。与传统数据和数据仓库相比，w e b 上的信息是非结构化 或半结构化的、动态的、并且是容易造成混淆的，所以很难直接对w e b 网页上的 数据进行数据挖掘，必须经过必要的数据处理。典型w e b 挖掘的处理流程如下： 1 查找资源：任务是从目标w e b 文档中得到数据，值得注意的是有时信息资源 不仅限于在线w e b 文档，还包括电子邮件、电子文档、新闻组，或者网站的日志 数据甚至是通过w e b 形成的交易数据库中的数据。 2 信息选择和预处理：任务是从取得的w e b 资源中剔除无用信息和将信息进行 必要的整理。例如从w e b 文档中自动去除广告连接、去除多余格式标记、自动识 别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。 3 模式发现：自动进行模式发现。可以在一个站点内部或在多个站点之间进行。 4 4 模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也可以 是与分析人员进行交互来完成。 根据对w e b 数据的感兴趣程度不同，w e b 挖掘一般可以分为三类：w e b 内容 挖掘( 评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 ) 。 w e b 内容挖掘是指从w e b 内容数据文档中发现有用信息，w e b 内容挖掘的 对象包括文本、图象、音频、视频、多媒体和其他各种类型的数据。其中针对无 结构化文本进行的w e b 挖掘被归类到基于文本的知识发现( k o t ) 领域，也称文 本数据挖掘或文本挖掘，是w e b 挖掘中比较重要的技术领域，也引起了许多研究 者的关注。最近在w e b 多媒体数据挖掘方面的研究成为另一个热点。所采用的主 要研究方法有信息增益，交叉熵、差异比等。w e b 内容的组织格式决定了w e b 内 容挖掘的方法，在传统的w e b 页面中，大多使用h t m l 组织信息，h t m l 注重的是 文档的格式化，即如何显示文档。所以，基于h t m l 的w e b 内容挖掘会被归入到 文本知识发现领域，所作的搜索大多也是基于关键词的搜索。近年来，x m l 技术 逐渐兴起，越来越多的w e b 页面用x m l 格式组织信息。因此，基于 ( m l 的w e b 内容挖掘正受到关注。 w e b 结构挖掘的对象是w e b 本身的超连接，即对w e b 文档间的结构进行挖掘。 w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之间的关 系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同一网站内部以 及不同网站之间的连接关系。在w e b 结构挖掘领域最著名的算法是h 工t s 算法和 p a g e r a n k 算法。他们的共同点是使用一定方法计算w e b 页面之间超连接的质量 ，从而得到页面的权重。著名的c l e v e r 和g o 0 9 1 e 搜索引擎就采用了该类算法。 w e b 用法挖掘( w e bu s a g em i n i n g ) ：即w e b 使用记录挖掘，在新兴的电子 商务领域有重要意义，它通过挖掘相关的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析日志记录中的规律，可以识别用户的忠实度、喜好、满意 度，可以发现潜在用户，增强站点的服务竞争力。w e b 使用记录数据除了服务器 的日志记录外还包括代理服务器日志、浏览器端日志、注册信息、用户会话信息、 交易信息、c o o k i e 中的信息、用户查询、鼠标点击流等一切用户与站点之间可 能的交互记录。可见w e b 使用记录的数据量是非常巨大的，而且数据类型也相当 丰富。根据对数据源的不同处理方法，w e b 用法挖掘可以分为两类，一类是将 w e b 使用记录的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系 表中的数据进行常规挖掘：另一类是将w e b 使用记录的数据直接预处理再进行 挖掘。w e b 用法挖掘中的一个有趣的问题是在多个用户使用同一个代理服务器的 环境下如何标识某个用户，如何识别属于该用户的会话和使用记录，这个问题看 起来不大，但却在很大程度上影响着挖掘质量，所以有人专门在这方面进行了研 究。通常来讲，经典的数据挖掘算法都可以直接用到w e b 用法挖掘上来，但为 了提高挖掘质量，研究人员在扩展算法上进行了努力，包括复合关联规则算法、 改进的序列发现算法等。根据数据来源、数据类型、数据集合中的用户数量、数 据集合中的服务器数量等将w e b 用法挖掘分为五类： ( 1 ) 个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本 信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众 不同的个性化服务。 ( 2 ) 系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量用 户满意度的关键指标，w e b 用法挖掘可以通过用户的拥塞记录发现站点的性能瓶 颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机制和 数据的分布策略。此外，可以通过分析网络的非法入侵数据找到系统弱点，提高 站点安全性，这在电子商务环境下尤为重要。 ( 3 ) 站点修改：站点的结构和内容是吸引用户的关键。w e b 用法挖掘通过挖掘 用户的行为记录和反馈情况为站点设计者提供改进的依，比如页面连接情况应如 何组织、那些页面应能够直接访问等。 ( 4 ) 智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的重 点，用户次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 用法 挖掘可以通过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销售 商合理安排销售策略。 ( 5 ) w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各个 用户在页面上的交互情况，对用户访问情况进行特征描述。 尽管w e b 挖掘的形式和研究方向层出不穷，但随着电子商务的兴起和迅猛发 展，未来w e b 挖掘的一个重要应用方向将是电子商务系统。而与电子商务关系最 为密切的是用法挖掘( u s a g em i n i n g ) ，也就是说在这个领域将会持续得到更多 的重视。另外，在搜索引擎的研究方面，结构挖掘的研究已经相对成熟，基于文 本的内容挖掘也已经有许多研究，下一步将会有更多的研究者把多媒体挖掘最为 研究方向。 近年来，随着x m l 技术的兴起，一个新的数据挖掘的研究方向正逐渐被人们 所认识，瑚l 颠覆了以往传统的数据库及w e b 页面的数据组织格式。从另一个侧 面：即信息的语义来描述信息本身，) ( m l 使得信息的组织格式更加结构化，也使 w e b 上的数据由偏重格式描述的平版型数据向着有着树型结构的结构化数据转 变。随着越来越多的数据以l 的格式组织，基于x m l 的数据挖掘也变的越来越 有意义，因此，也成为未来数据挖掘领域的又一个热点。 第二章基于x m l 的数据挖掘 2 1 什么是x 札 ) ( m l e x t e n s i b l em a r k u pl a n g u a g e 的全称为可扩展标记语言，同其他类别 的标记语言，诸如h t m l 一样，是从所有的标记语言的元语言一一标准通用标识 语言s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u p1 a n g u a g e ) 中派生而来，是由w 3 c 制 定的标准【4 o 随着互联网技术和数据挖掘技术的飞速发展，w 3 c 的成员意识到， 面对w e b 这样的一个庞大的异构数据库，必须要找到一种方法将w 髓中的数据的 表现方式和数据本身分离开来，因而他们制定了x m l 这一标准 ) ( m l 是一种数据储存和交换的格式，允许在不同的系统或应用程序之间交换 数据，它将数据本身同其显示外观分离，因而，相同的x m l 数据可通过使用不同 的外观文件以多种方式显示。 同w e b 上存在的传统的平版型数据不同，x m l 是一种用于设计数据格式和结 构的规则和方法，它易于生成便于不同的计算机和应用程序读取的文件，) ( m l 表 示的是文档的结构和语义。 2 2x m l 的应用特点 x m l 让许多h t m l 难以解决的任务变的简单，使h t m l 不可能完成的任务得以 完成。例如：在h t m l 中，内容总是与格式混编在一起，阅读一个h t m l 文档常常 是一件头疼的事，人们总要区分哪些描述是信息，哪些描述是格式。在x m l 中， 信息同显示格式相剥离，x m l 文档仅仅用来保存信息，至于信息的显示则交给x s l 去完成，因此同h t m l 相比，x m l 的可读性更强，交换数据也更加便利。除此之 外，x m i 。还能表现出信息之间的联系，这是以往h t m l 所无法实现的。x m l 的另一 个重要的特点是它是可扩展的，用户可以自己定义出现在x l 文档之中的标签。 2 2 1 设计与特定领域相关的标识语言 由于x m l 的可扩展性，它允许各种不同的专业开发与自己的特定领域相关的 标识语言。这将使得该领域中的人们可以方便的交换笔记，数据和信息而不必担 心接收方是否有特定的软件和系统来解释这些数据。1 。在同一领域中的工作者 们，甚至可以形成该领域所特有的) ( m l 标识规范，这使得数据的组织更加严密而 专业。医疗和化学领域已经首先建立了自己的x m l 规范。通过这些规范，本领域 的人可以更方便的交换信息，更重要的是，这些领域的规范并不影响到其他领域 规范的制定，而对于一个不懂医学或者化学的人来说，用这些规范组织的x m l 文档又是可以被理解的。这是因为) ( m l 文档的另一个重要特点一自描述性 2 2 2x m l 数据的自描述性 有报道说过去4 0 年来的数据都丢失了”1 ，不是因为储存这些数据的媒质被 损坏，一个重要的原因是，随着计算机技术的飞速发展，人们逐渐淡忘了如何读 取和解释这些数据格式的数据，因此这些数据所记载的信息也就随之而丢失了 【5 】o ) ( m l 并不存在这样的问题，它使用非常简单的数据格式，甚至可以用记事本 或1 0 0 的纯a s c i i 文本来书写。从更高的水平解释。x m l 是自描述的，文档本 身即可以向数据的拥有者解释出该文档到底包含了哪些方面的内容，这些方面的 具体内容又是什么。如下是一个己知的x m l 文档 m a r y c h o u 2f e b1 9 8 5 9d e c2 0 6 5 即使这个数据的拥有者并不了解x m l 技术，但是，只要他会英语，便可以从 文档中了解到，该文档记录一个叫m a r yc h 。u 的人，生于1 9 8 5 年2 月2 日，死 于2 0 6 5 年1 2 月9 日。 2 2 3 快捷而便利的数据交换 由于x m l 是非专有的，其阅读和编写存在所谓的“平台无关性”，使得它成 为在不用的应用程序和应用系统间交换数据的一个理想格式。人们可以利用任何 理解x m l 的工具来处理数据，可以为不同的目的使用不同的工具，对于数据的拥 有者和发送者来说，不必再担心接收方是否和自己拥有相同的操作系统和软件平 台。例如，所发送的数据格式为w o r d 文档时。则接收方也必须有必要安装w 0 r d 软件才可以完整的阅读该文档，当数据以x m l 格式组织并传输时，接收方只需要 一台安装了w i n d o w s 或者其他基本操作系统的p c 就可以了。 2 2 4x m l 是结构化数据 同其他数据格式不同，心l 是一种结构化的数据，对于一个x m l 文档中的数 据来说，该文档不仅仅定义了数据的属性和内容，更为重要的是，文档还定义了 存在于该文档内的各项数据之间的结构关系。这种结构型的数据除了规范了数据 的组织形式之外，更重要的是，为我们进行基于语义的信息搜索打开了方便之门， 在x m l 数据格式上进行数据挖掘时，所得到的知识也是更为精确的具有语义描述 知识。 2 3 有关基于x m l 的信息搜索的研究 同本文相关的基于x m l 的信息搜索的研究主要有以下几方面的内容。 2 3 1 衡量x m l 文档问的相似性 研究的主要目的是，给定两个或者更多的已知的x m l 文档，如何计算它们 之间的相似程度以用来判断文档间描述的是否是同一个或者同一类信息。由于 x m l 是结构化标识语言，因此这种相似性是结构上的相似性。相关的相似性衡量 方法列举如下： ( 1 ) 经典的e d i t d i s t a n c e 方法 利用经典的e d i t d i s t a n c e 方法衡量2 个x m l 文档之间的相似性是经常被 使用的方法之一，在有关此类的研究中，通过结点的插入，删除，替换等操作试 图将一个文档转化为另一个文档【6 o 算法可以通过为每一种操作( 插入，删除， 替换) 赋予一定的代价值一c o s t 。，并计算完成变换时所需要的最小和代价 m i n ( c o s f 。) 做为两个文档间的距离d i s ( c 。，c 。) 【”。d i s ( c 。，c 。) 越小，则文档c 。，c j 在结构上越为相似。这种方法可以有效的衡量两文档间的结构相似性，其缺点为， 当文档的规模变大时，其运算复杂度成几何数量级增大。 ( 2 ) 基于时间序列和d f t 变换的方法 在”3 和。3 中作者以一种新颖的方法讨论了) ( m l 文档间相似性的衡量问题。在 这种方法中，一一个x m l 文档被映射成为一个时问序列。文档中的一个标签对应为 一个脉冲信号。通过对该文档所对应的脉冲序列的d f t 变换形成具有直观反映的 频谱图像。最后的结果直观简洁，容易被人理解。但是，如何给出一个量化的结 果以表示出这种相似性是一个值得解决的问题。 相似性的衡量发生在已经给定的几个x m l 文档之间，关心的问题是“谁象谁， 有多象”，被比较的双方已经被给出。但是，通常发生的情况是，数据的拥有者 提供一个庞大的数据集合给用户，用户并不知道，也不必知道其中每个文档的 结构是如何组织的，它们仅仅关心这个数据源中是否包含了他们所需要的信息。 到此，问题转变为：从一个结构未知的数据源s t 中搜索出确定的用户需求d t 。 所以在相似性衡量的基础上，接下来的问题是：基于x 她的信息搜索。 2 3 2 基于x m l 的信息搜索 目前较为普遍的搜索技术有基于关键词匹配的搜索技术和针对结构型数据 库的说明性搜索语言。问题在于，这两种技术都不能直接应用于) ( m l 。另一方面， 基于x m l 搜索找到的内容更加精确。所以有关于x m l 的搜索技术的研究就十分有 意义。国内外不少学者作了有关于此的研究“。“”目前已有的一些主要方法有 ( 1 ) 数据库映射的方法 该方法的核心思想是，将x m l 格式的数据转化为传统关系型数据库所能接受 的数据格式，利用已经相对成熟的数据库技术实现信息的搜索目的“3 ”“3 。 ( 2 ) ) ( m l 文档流编码的方法 主要思路是，通过解析，将x m l 文档转变为) ( m l 流( ) 【m ls t r e a m ) ，通过为 x m ls t r e a m 编码将删l 流转变为代码流，并在此基础上实现搜索。在这种方法 中，一个关键的问题是如何对解析后的) ( 1 d l 文档和标签进行编码。常用的对标签 的编码方式有 8 ：d i r e c tt a ge n c o d i n g ，p a i r w i s et a ge n c o d i n g ，n e s t e dt a g e n c o d i n g ，对应的x m l 文档的编码方式有t r i v i a ld o c u m e n te n c o d i n g ，1 i n e a r d o c u 明e n te n c o d i n g ，叫l t i l e v e ld o c u m e n te n c o d i n g 等 ( 3 ) 基于关系代数的查询方法“” 基于关系代数的搜索是一种过程化的搜索，包括了一个运算集合( 选择，投 影，并集，差集，笛卡尔积) ，关系代数的内容类似于结构化查询语言中的查询 语句，用关系代数描述的x m l 具有如下定义： x m l 表达式：包含变量的x m l 元素称为x m l 表达式。变量可以出现在元素名， 属性名，元素值或者属性值中。x 肌表达式中的变量类型及其前缀分别为：名变 量( $ n ) ，变量表达式( $ e ) ，中间表达式( $ i ) ，字符串变量( $ s ) ，属性一值对 变量( $ p ) 。变量数目为零的x m l 表达式称为基本表达式。 x m l 子句：定义在r 。上的) ( m l 子句c 的形式是h b ；，b 2 ，b 。，n o ，其中h a x ，b 。是x m l 表达式或约束。f 称为子句头，记作h e a d ( c ) ，b ，称为子句体，记 作b o d y ( c ) 。子旬体中的表达式和约束分别记为o b j e c t ( c ) 和c o n ( c ) 。 语义的描述说明：若p 是定义在h 上的说明描述，p 的语义m ( p ) 定义为： m ( p ) = 【j ) 夥( 巾) 其中。表示空集： 孟t t p ( x ) = h e a d ( c p ) | c p ，目s x ，c 口为基本子旬，o b j e c t ( c 们x ，c o n ( c 们 t 。) 分析上述方法，不难发现，一个共同之处是：都将x m l 文档做了某种处理 和变换，从而使搜索成为可能。在( 1 ) 中，将) ( m l 格式的文档转化为了传统关 系型数据库所能接受的信息。在( 2 ) 中，则是将x m l 文档转化为了x m l 流。在 ( 3 ) 中更是将x m l 文档转化为了关系代数中的子句。这种转化增加了搜索的复 杂程度和额外的负担。既然x m l 文档的内容和其结构是可以被解析的，因而，能 否从文档本身的内容和其结构出发来进行搜索工作是一个值得讨论的问题。 2 3 3 ) 【m l 文档聚类 x m l 文档聚类可以被看做是一个单独的研究领域，聚类的目的是对已有的 x 札文档集合划分分组，聚类不依赖于预先定义好的类的信息，聚类后处在同一 簇里的文档间具有很强的相关性。 这里本文对x m l 文档聚类加以讨论，理由是，在以x m l 文档结构为出发点进 行信息搜索工作时，对于一个用户需求d t 来说，需要解析数据源中的每一个文 档t ，对于多用户同时提出需求或者一个用户提出多个需求时，则需多次的解析 整个数据源，这样做显然过于烦琐。同时，大量的同用户需求d t 无关或者相关 不大的文档也被一次次重复解析，这大大降低了搜索的效率。为此，在做信息搜 索工作之前，引入x m l 文档聚类作为数据的预处理工作，对于多用户，多需求来 说，不同的需求d t 被归入到不同的类别中，无须重复操作，对于信息搜索来说， 聚类后，可以使我们仅仅搜索那些同d t 相关的文档，对于那些不相关的则不予 讨论。同此相关的一些x m l 文档聚类方法有： ( 1 ) sg r a c e 算法 s g r a c e 算法从文档中所存在的e d g e 关系出发来衡量) ( m l 文档间的距离“， 并在此基础上讨论了x m l 文档聚类。其中e 趣e 关系是指文档中具有直接父子关 系的两结点间的联系，这种e d g e 关系反映了文档的结构特性，两个文档间所存 在的公共e d g e 关系越多，则他们的相似性越大，距离越小。算法给出两文档间 的距离公式为 i 粥( c 1 ) n 阳( c 2 ) i 以，( c lc 2 ) = ；2 二二二l 坛x 阳( c 1 ) ，5 6 ( c 2 ) j 对于信息搜索来说，用户之间描述信息的方式与结构会有所不同。如图2 1 ： t 乙 图2 1 同一信息由千描述不同所带来的结构差异 1 1 b 只 (吾 移 呷 嚼 。 对于同一个信息t 来说，甲用户可能将它描述成t 甲，而乙用户可能将其描 述为t 乙，基于直接父子e d g e 关系的s g r a c e 算法显然不能适应这种变化，按 照原算法，t 甲，t 乙两个文档间的距离为 岬即耻摆器_ l s ， 这主要是因为e 趣e 关系a b 在乙的描述方法中并不存在。但是在乙中，a 、b 间的先后辈关系没有发生任何改变，仍然存在。所以说，甲乙之间仍然具有很强 的相似性，而绝不仅仅是区区的1 3 。这是值得解决的问题。 ( 2 ) p b c 方法 作者在“7 3 中给出了一种基于文档中存在的一种特殊的子结构一一路径的聚 类算法p b c ( p a t h b a s e d c l u s t e r i n