（计算机应用技术专业论文）识别和抽取web中的关系信息及其出现模式.pdf

论文摘要 i n t e r n e t 的飞速发展以及它开放式的特点使得网上的信息不断的 膨胀，w e b 已成为人们不可缺少的信息源。w e b 中存在着大量的描述 实体问相互关联的信息，与此同时实体之间的相互关系隐藏着非常丰 富的、有价值的信息。而目前的搜索引擎依靠关键字匹配的方式查找 信息，缺乏知识处理能力和理解能力，从而无法对w e b 中的关系信息 进行识别。 本文以w e b 中信息发布与交换的新标准x m l 作为研究对象，提 出了一种从w e b 上发布的x m l 文档中识别和抽取关系信息及其出现 模式的方法。该方法按照用户的挖掘请求搜集x m l 文档：通过计算 x m l 文档的相似度来识别包含了用户需求的目标文档；建立用户挖 掘模式并与目标文档进行模式匹配实现关系数据的抽取。 实验结果表明本文提出的x m l 相似度计算方法能较好的实现目标 文档的识别，同时本文采用的模式表达和匹配方式也能较准确地从目 标文档中抽取出用户所需的关系数据。 关键词：关系信息，x m l 相似度，模式匹配，数据抽取 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t a n d o p e n i n g c h a r a c t e r i s t i co ft h e i n t e m e t ，t h e a m o u n to fi n f o r m a t i o nh a si n c r e a s e d g r e a t l y w e b h a s a l r e a d yb e c o m e a l li n d i s p e n s a b l ei n f o r m a t i o ns o u r c e sf o r p e o p l e t h e r ei s al a r g ea m o u n to fi n f o r m a t i o nt h a td e s c r i b e si n t e r r e l a t i o no fe n t i t i e so n t h e w e b ；m e a n w h i l e l o t so fv a l u a b l ei n f o r m a t i o ni sh i d d e ni nt h e i n t e r r e l a t i o n sb e t w e e nt h e e n t i t i e s h o w e v e r , t o d a y s s e a r c h e n g i n e s w h i c hs e a r c hi n f o r m a t i o nr e l y i n go nk e y w o r d sm a t c h e s ，l a c kt h ea b i l i t y o fk n o w l e d g em a n i p u l a t i n ga n du n d e r s t a n d i n g ，s oi t c a nn o td i s c e r n r e l a t i o n so nt h ew e b i nt h i sp a p e r , w et a k ex m lw h i c hi san e ws t a n d a r do fi n f o r m a t i o n i s s u ea n de x c h a n g i n go nt h ew e b a st h eo b j e c to fo u r r e s e a r c h i n g ，a n dp u t f o r w a r dam e t h o d c o n c e r n i n g a b o u t m i n i n g r e l a t i o n sa n d p a t t e r n s i nx m l d o c u m e n t so nt h ew e b t l l i sm e t h o df i r s t c o l l e c t sx m ld o c u m e n t s a c c o r d i n gt o u s e r sr e q u i r e m e n t ，a n dt h e ni td i s c e r n st a r g e tx m lf i l e s w h i c hc o n t a i nr e l a t i o n sr e q u i r e db yu s e rb yc a l c u l a t i n gs i m i l a r i t yb e t w e e n x m ld o c u m e n t s a tl a s ti te s t a b l i s h e su s e r ss e a r c h i n gp a t t e r na n du s e p a t t e m - m a t c h i n ga l g o r i t h m t oe x t r a c ta l lr e l a t i o no c c u r r e n c e sf r o mt a r g e t d o c u m e n t e x p e r i m e n t a lr e s u l t ss h o w t h a to u rs i m i l a r i t yc a l c u l a t i n gm e t h o di n t h i s p a p e r c a nb eu s e dt od i s c e r nt a r g e tx m l d o c u m e n ti nag o o d p e r f o r m a n c e a t t h es a m et i m e ，t h ew a yw e r e p r e s e n t su s e r sr e q u i r e m e n t a n dt h ep a r e m - m a t c h i n ga l g o r i t h mw et a k ei sa b l et oe x t r a c tt h em o s t t a r g e tr e l a t i o n sf r o mg i v e nx m l d o c u m e n t s a c c u r a t e l y k e y w o r d s ：r e l a t i o n s ，x m ls i m i l a r i t y , p a t t e mm a t c h i n g ，d a t ae x t r a c t i n g y7 3 3 6 2 华侨大学硕士论文 1 1 课题背景、意义 第一章绪论 互联网的迅速发展和广泛普及导致网上信息爆炸性增长。据统计，w e b 已经 拥有数十亿的网页，而这一数字仍然在不断的快速增长，它已经成为人们获取信 息的重要手段。近年来，越来越多的机构、团体和个人在w e b 上发布信息、查找 信息，然而w w w 上虽有海量的数据，但这些信息往往采用不同的格式分布在世 界各地的w 曲服务器和主机上，使w e b 呈现出异构性、动态性和开放性的特点： w e b 上的数据没有特定的模型描述，每一站点的数据都各自独立设计，并且数据 本身具有自述性和动态可变性，从而使人们要想找到自己需要的数据如同太海捞 针。目前信息检索领域开发了许多搜索引擎用于w e b 上信息的查找，而这些搜索 引擎缺乏知识理解能力和处理能力，对要检索的信息仅仅采用机械的关键词匹配 来实现，因此难以解决找信息难的问题。 w e b 中包含了大量的各种类型的实体，这些实体并不是孤立存在的，而是通 过各种各样的方式联系在起，而实体之间的相互关系特别是语义上的关联隐含 了非常丰富的、有价值的信息。例如：w e b 中包含了大量的网页，网页之间通过 超链接实现的相互引用反映出了它们在语义上的相关性；另外，出现在同一页面 中的实体之间也可能存在着某种关系，例如在描述关于书这一主题的网页中出现 的作者和作品这两种实体，它们之间可能隐含了某个作者创作了某个作品的关 系，也可能存在着某个作者引用了某个作品中的内容这样一种关系。又比如在同 一个网页中出现的人名和公司名这两种实体，它们之间的关系可能是某个人受雇 于某个公司，也可能是某公司归某人所有。 上述的这些关系都不是显式地表现出来的，计算机无法直接获取这些信息， 因此很难对相互关联的实体在语义层次上有较深入的分析，如果能让计算机识别 出w e b 中实体之间的相互关系以及这些相互关系的出现模式，那么可以帮助我 们发现隐藏在w e b 中的有价值的信息。随着人们对w e b 访问的a 益频繁，并且 越来越希望从中寻找到自己需要的可信度高的信息，识别w e b 中实体之间的相 互关系将变得越来越重要。例如，有的用户可能希望从w e b 中寻找到某一本书 的作者，或者想了解某个作者都写了哪些书，对于这样的查询需求目前的搜索引 识别和抽取w e b 中的关系信息及其出现模式 擎是无法为其提供服务的。如果我们能将与某个主题有关的关系信息从w e b 网 页中识别、抽取出来并集成在一个结构化的库中，那么这些信息将构成一个庞大 的结构化信息源。我们都知道，结构化的信息源将有助于w e b 用户方便、准确 地查询到自己需要的信息。 关于w e b 关系信息及其出现模式的挖掘，国内外的学者针对w e b 早期以及目 前仍比较流行的h t m l 格式的网页做了相关研究，并提出了一些方法。而h l t e m e t 的飞速发展使得i n t e m e t 上发布信息的早期标准h t m l ( 超文本标记语言1 变得越 来越复杂，h t m l 由于它自身存在的缺点越来越不能适应网络的发展，这是因为 h t m l 是一种显示描述语言，它的标记集合是预先定义的而且是固定的，用户不 能增加自己的有意义的标记，因此它仅仅用于描述w e b 浏览器应该如何在页面 上布置文字、图形等，并没有对i n t e m e t 上最重要的东西信息本身的含义进 行描述。通过h t m l 表现出来的文字、图形等内容很容易被人理解，而要计算 机去理解这些标记内的文字的含义就很困难。 x m l 的出现解决了上述的问题。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 ，可扩展 标记语言) 被称为“第二代w e b 语言”、“下一代网络的基石”。自它被提出后， 给基于w e b 的应用软件赋予了强大的功能和灵活性，因此正越来越广泛地为开发 者和用户所使用。x m l 以其灵活性和可扩充性已日益发展成为w e b 上数据表示和信 息交换的标准，许多集成系统都以它为中间件作为信息交换的标准，它在w e b 数 据库中也起到越来越重要的作用，它的结构比关系数据库中使用的关系更有表现 力，可以更加容易表现复杂的数据。对x m l 数据模型的研究和基于规则表达的x m l 查询已经引起了广泛的重视。 1 2 本课题的研究内容 1 2 1 本课题的主要工作 本课题是以w e b 中信息发布与交换的新标准x m l 作为研究对象，对x m l 文档中的关系信息及其出现模式的识别和抽取方法进行了研究。本课题基于w e b 内容挖掘中使用机器学习的方法从半结构化w e b 文档中自动或半自动的抽取数 据的模式这一思想，结合几种w e b 数据挖掘的经典技术以及与x m l , 柞1 关的技术， 提出了一个识别和抽取x m l 文档中的关系信息及其出现模式的方法，并建立了 一个能根据用户的描述自动地从x m l 文档中挖掘关系信息的实验系统。 2 毕侨大学硕士论文 该系统采用一种简单而且直观的方式提供用户定义其所需从w e b 中获取的 关系主题以及构成该关系主题的两类实体( 以后可扩充到多类实体) ，根据用户的 定义系统会自动地从w e b 中搜寻相关x m l 文档，从寻找到的x m l 文档集合中识别 出目标文档，并进一步从中抽取出与该关系主题相匹配的数据反馈给用户。除此 之外，系统还可以利用抽取出的模式去发现用户指定的两类实体问的未知关系。 例如：某用户想要从w e b 中获取关于“b o o k ”这一主题的作者名和书名的 对应关系，那么他只需给出“b o o k ”这一关系主题，并指出构成该关系的两类实 体( a u t h o r ，t i t l e ) 来定义自己的挖掘请求，接下来系统会自动地从网上找到尽量多 的与( a u t h o r ，r i f l e ) 相匹配的实例数据反馈给用户。又如：某用户想要从网上找出 某公司与其总部所在地的对应关系，那么他只需给出“l o c m i o n ”这一关系主题以 及构成该关系的两类实体( c o m p a n y ，c i t y ) 定义自己的挖掘请求，同样地，系统会 自动地从网上找出尽量多的满足公司名及其所在地这一关系主题的实例数据反 馈给用户。 主要工作包括： 1 提出个量化x m l 文档相似度的方法 通过计算两段x m l 文档的相似度值，来判断文档中包含用户所需关系信息 的可能性。x m l 文档相似度的计算包含了文档的元素语义和文档结构两个方面 的相似性。 由于x m l 的标记是用户自定义的，它包含了丰富的所描述数据的语义信息， 因此提出了建立x m l 文档标记矢量模型，并通过计算标记矢薰模型的余弦距离 来量化文档元素语义相似度的方法。 x m l 作为一种半结构化的数据模型，其在结构上的特点也在很大程度上放 映出了它所要表达的语义，因此x m l 文档在结构上的相似性也成为量化其相似 度的重要组成元素。在结构相似度的计算方法上，使用序列模式挖掘算法挖掘出 x m l 文档的频繁路径，并通过计算频繁路径在x m l 文档路径中的比重来量化 相似度。 2 实现相似度阈值的自动发现 将文本聚类中文本相似度闽值的自动发现方法运用予x m l 相似度闽值的自 动发现，使用五次曲线对x m l 相似度曲线进行拟合并求其拐点，从得到的一组 识别和抽取w e b 中的关系信息及其h 现模式 与拐点相对应的曲线函数值中按经验选取或由用户从中指定相似度阈值。 3 提出从x m l 数据识别和抽取关系信息的方法 本方法是将用户的挖掘请求以及x m l 文档表示为树模式，通过路径匹配抽 取出构成关系的两类实体的实例值。最后对实体实例值进行配对构成关系数据的 挖掘结果。 4 建立了个能根据用户描述自动地从x m l 文档中挖掘关系信息的实验系统。 1 2 2 国内外的相关研究 关于w e b 关系信息的挖掘，国内外的学者针对w e b 早期以及目前仍比较流行 的h t m l 格式的网页做了相关研究，并提出了以下些方法： n e e ls u n d a r e s a n 和j e o n g h e ey i 1 将w e b 中关系信息的挖掘问题定义为 w e b 中的二元性问题( d u a l i t yp r o b l e m si nt h e w o r l dw i d ew e b ) 。二元性问题 ( d u a l i t yp r o b l e m s ) 是指两个相互关联的概念集合的识别问题，它在w e b 中以两 种形式存在：( 1 ) 网页静态链接结构中隐含的网页之间的语义关联。( 2 ) w e b 页面中实体之间的相互关系与关系的出现模式之间的二元性。第一种形式的二元 性可以通过识别与某个查询相关的h u b 页面以及权威页面( a u t h o r i t yp a g e ) 来解 决。而第二种形式的二元性由某一种特定类型的关系引入，例如书和作者之间的 关系或者词语与其首字母缩写形式( a c r o n y m s ) 之间的关系与它们的出现模式之 间的二元性。 斯坦福大学的s e r g e yb r i n 2 提出了一种从大量文档中发现一对词语出现 模式的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现了数本在 a m a z o n 网站上找不到的新书籍。文中提出了一种d i p r e ( d u a li t e r a t i v ep a t t e m r e l a t i o n e x p a n s i o n ) 方法，该方法利用模式( p a t t e r n ) 和关系( r e l a t i o n ) 的二元性 ( d u a l i t y ) 从样本集合中抽取关系信息：给定一个关系主题，借助搜索引擎和w e b c r a w l e r 可以从w e b 中找出包含了该关系主题的h t m l 网页，并从网页中抽取出 关系主题的出现模式：如果模式的抽取结果得到了个具有高覆盖率和低错误率 的模式，那么通过该模式与w e b 中其他网页进行匹配，可以进一步找到更多满 足关系主题的数据。这种方法在1 5 6 ，0 0 0 个页面中发现了3 4 6 个模式和1 5 2 5 7 个 作者，书名。 e u g e n ea g i c h t e i n 等人 3 1 构造了一个从文本集合中抽取关系信息的 华侨大学硕士论文 s n o w b a l l 系统，该系统基本上采用了b r i n 的d i p r e 方法的思想，不同之处 在于s n o w b a l l 在模式的表达方式上做了一些改进。例如他在模式的表达中加 入了标注实体的标记，还引入了带权值的文本来区分实体周围不同位置的文本信 息的重要程度。此外，s n o w b a l l 还引入了一种在抽取过程中对模式和元组进 行评价的新技术。在抽取过程的每一次循环中，都自动为模式和元组进行评价， 并只保留可信度高的模式和元组。 s t e p h e ns o d e r l a n d 等人 4 】提出了一种w e b f o o t + c r y s t a l 的方法从w e b 中抽取出基于文本的信息。它首先使用w e b f o o t ( 预处理器) 对网页进行分析，按 照网页的布局将其划分成一系列连贯的逻辑片断，然后将w e b f o o t 的输出结果传 送给c r y s t a l 。c r y s t a l 是一个n l p 系统，它可以通过学习从训练样本中抽 取出特定领域的信息规则。使用w e b f o o t + c r y s t a l 可以将文本格式转换为与关 系数据库条目等价的形式化表示。 c h i a h u ic h a n g 等开发的i e p a d 5 系统，通过分析w e b 页面中的h t m l 标签 的重复规律，进行模式挖掘并生成数据抽取规则。i e p a d i 由h t m l 转换器、p a t 树、模式鉴别器和规则生成器组成。h t m l 转换器把h t m l 标签和正文编码成二 进制代码串；以该代码串作为输入生成一棵p a t 树，p a t 树可以检测代码中最大 的重复单元从而找到h t m l 页面中有规律的代码；模式鉴别嚣将错误的模式去除 并保留合理的模式；规则生成器根据发现的模式产生抽取模式。i e p a d 同时证明 了段落级h t m l 标签在模式发现中比文本级标签更重要。 文 6 】中w a n g 等人以w e b 中的电影介绍网页作为测试文档，使用o e m 模型 从这些半结构化的页面中抽取出词语项，进而得到一些关于电影的包括名称、导 演、演员、编剧等信息在内的出现模式。 1 2 3 本课题的特色和创新点 运用w e b 数据挖掘以及x m l 的相关技术，为用户构造一个x m l 文档关系 信息的挖掘系统，与以往的关系数据挖掘不同的是该系统以w e b 中的x m l 文档 为挖掘目标，识别和抽取蕴藏在嵌套结构中的关系信息。 对如何准确量化x m l 文档的相似度进行了详细的研究。本文提出的相似度 计算方法考虑到了x m l 文档的元素语义和文档结构两个方面，结合语义和结构 对x m l 文档的相似度进行了量化。在元素语义相似度的计算方法上，以文本挖 识别和抽取w e b 中的关系信息及其出现模式 掘技术中提取文本特征、用矢量空间模型( v e c t o rs p a c em o d e l ) 为文本建模的思想 为基础，提出了x m l 文档标记矢量模型，并根据这一矢量模型计算余弦距离来 量化文档元素的语义相似度。 而结构相似度的计算采用了使用序列模式挖掘算法挖掘x m l 文档的频繁路 径的方法，基于序列模式挖掘中的a 州o r i 增量算法设计了x m l 文档频繁路径 模式的挖掘算法，并依据频繁路径在文档总路径集合中所占比重构造了结构相似 度的计算公式。结合语义相似度和结构相似度，构造了x m l 文档相似度的加权 计算公式。 在数据抽取阶段，结合树匹配的思想提出了通过路径匹配抽取实例数据，并 通过寻找对象标识节点进行实例数据的配对构成关系数据挖掘结果的方法。该方 法节约了系统运行时间，使系统能更高效地得出挖掘结果并反馈给用户。 1 3 论文结构 本章首先讲述了w e b 中所包含的实体之间隐藏了非常丰富的、有价值的关系 信息以及x m l 作为w e b 数据交换的新标准给w e b 存在的问题提供了解决方案， 提出了本课题的研究任务和目标，并指出本课题在求解方案以及技术上的特色和 创新点。 本文共分五章研究了如何识别和抽取w e b 上x m l 文档中的关系信息这一问 题。 第二章简述了本课题涉及到的相关技术，包括w e b 数据挖掘以及x m l 的相 关技术； 第三章讲述了本课题提出的x m l 关系数据的挖掘方法和实现算法； 第四章介绍原型系统的设计与实现，给出实验步骤以及数据，并对实验结果 数据进行总结分析； 第五章对本文的工作进行了总结，并介绍进一步的研究工作。 华侨大学硕士论文 第二章相关技术 2 1 w e b 数据挖掘 2 1 1 w e b 数据挖掘的定义 w e b 数据挖掘是一个新兴的研究领域，它正逐步受到越来越多人的重视。这 是因为近年来i n t e r n e t 的飞速发展和广泛应用使得w e b 上的信息量以惊人的速度 增长，面对w e b 丰富的数据内容再加上w e b 分布、动态、异质、复杂、开放性 的特点，人们如何从海量的数据中查找自己想要的数据和有用信息，迫切需要一 种新的技术能自动地从w e b 资源上发现、抽取和过滤信息，因此出现了w e b 挖 掘技术。 w e b 数据挖掘 7 就是从w e b 文档和w e b 活动记录中发现、抽取感兴趣的潜 在的有用模式和隐藏的信息，它可以定义为：从大量w e b 文档的集合c 中发现 隐含的模式p 。如果将c 看作输入，尸看作输出，那么w e b 挖掘过程就是从输入 到输出的一个映射f ：c p 。w e b 挖掘从数据挖掘发展而来，但是它与传统的数 据挖掘相比有许多独特之处。这是因为： ( 1 ) w e b 是一个巨大的、异构的、分布式的数据库。 w e b 上的每一个站点就是个数据源，每个数据源都是异构的，因而每一个 站点之间的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。如果 想要利用这些数据进行数据挖掘，首先必须解决站点之间异构数据的集成问题， 只有不同站点的数据集成起来提供给用户一个统一的视图，才有可能从巨大的资 源中获取所需的东西。其次还要解决w e b 上的数据查询问题，因为如果所需的数 据不能够有效地得到，对这些数据进行分析、集成、处理就毫无意义。 ( 2 ) w e b 文档本身是半结构化的。 w e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据 模型，可以根据模型来具体描述特定的数据。而w e b 上的数据非常复杂，没有特 定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自描述性和 动态可变性，因而w e b 上的数据被称为半结构化的数据。w e b 数据挖掘技术首要 解决的是半结构化数据源模型和半结构化数据模型的查询、集成问题a 识别和抽取n 协中关系信息发其出现摸式 2 1 2 半结构化数据概述 半结构化数据f 8 是指介于模式固定的结构化数据( 如关系库中的表元组和 对象库中的类型对象) 和完全没有模式的无序数据( 如正文、声音、图像) 之间的 数据。它一般是自描述的，数据的结构和内容混在一起，没有明显的区分。半结 构化数据存在一定的结构，但这些结构或者没有被清晰地描述，或者是经常动态 变化地，或者过于复杂而不能被传统的模式定义来表现。半结构化数据模式与传 统的关系或面向对象数据模式不同，它主要有以下些特点： 对半结构化数据来说是先有数据，后有模式。 半结构化数据的模式用于描述数据的结构信息而不是对数据结构进行强制 性约束。 半结构化数据的模式规模可能很大，甚至超过源数据的规模，而且因数据的 不断更新而处于动态的变化过程之中。 半结构化数据的模式不讲求精确性，它可能描述其中一部分结构，也可能根 据数据处理的不同阶段的视角不同而不同。 非常灵活，能满足网络这种复杂分布式环境的要求。 目前，对半结构化数据及其模式主要有五神描述方法：基于图的描述形式、 基于树的描述形式、基于逻辑的描述形式、基于关系的描述形式以及基于对象的 描述形式，其中又以基于图和逻辑的描述形式为主。 基于图的描述形式一般对半结构化数据采用标记有向图来表示，其中最有代 表性的是o e m ( o b j e c te x c h a n g em o d e l ) 模型，这种描述形式的个显著优点是模 式和数据采用同一种数据模型( 图模型) ，非常便于处理。模式图数据图通常是一 个有根且带边标记的有囱图，模式图的边标记可以与数据图相同，也可以加以扩 充。对于模式图中的节点，可以加一定注释表明其代表语义或其它特定含义。 而基于逻辑的描述形式目前有描述逻辑( d e s c r i p t i o nl o g i c ) 、一阶逻辑 ( f i r s to r d e rl o g i c ) 以及d a t a l o g 等，它们非常类似但在表达能力等方面有所差 别，其中比较典型的是基于d a t a l o g 的模式描述形式。 除了上述五类模型外，还有其它的数据模型用以描述半结构化数据。例如 x m l 文档是一种常见的半结构化数据源，而煳l 文档对象模型d o m 就是一种结合树 表示方法和对象表示方法的数据模型。 华侨大学硕士论文 2 1 3 w e b 数据挖掘的分类 w e b 挖掘 9 可以分为三类，即：w e b 内容挖掘( 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 ) n l w e b 日志挖撼w e bu s a g em i n i n g ) 。其中w e b n 容挖掘是指从w e b 上的文件内容及其描述信息中获取潜在的、有价值的知识或模 式的过程，它又分为w e b 文本挖掘和w e b 多媒体挖掘，针对的对象分别是w e b 文 本文档( 包括t e x t ，h t m l 等格式) n w e b ! g 媒体信息( 包括l 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 站点的使用情况。 2 2x 3 i l 相关技术 2 2 1j ( m l 概述 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 ) ，意为可扩展标记语言，是一组定义语义 标记的规则，它是一种元标记语言，可以定义特定领域内的标记语言的语法结构。 x m l 标记只描述文档的结构和语义，而并不描述页面上元素的格式。x m l 文档中 元素格式的定义是利用专门为x m l 提供的样式表语言来为特定的x m l 文档创建相 应的样式表并附加到该文档上，那么浏览器可以通过接收到的x m l 文档的样式单 来格式化该文档的元素。 2 2 2x m l 的主要特点 作为一种新出现的标记语言，x m l 的特点决定了它可以被应用到各种不同的 场合，完成其他语言不能完成的众多工作。其特点是： ( 1 ) 简单。x m l 经过精心设计，整个规范简单明了，它由若干规则组成，这 些规则可用于创建标记语言，并能用一种常被称作分析程序的简明程序处理所有 新创建的标记语言。 ( 2 ) 开放。x m l 作为一个不错的s g m l 子集还保持了对现有的面向s g m l 的系 统的向下兼容性。开放式标准x m l 的基础是经过验证的标准技术，并针对网络做 了最佳化。 ( 3 ) 高效且可扩充。由于) ( m l 能够标记更多的信息，它可以使用户很轻松地 找到他们需要的信息。利用x m l ，w e b 设计人员不仅能创建文字和图形，还能构 建文档类型定义的多层次、相互依存的系统、数据树、元数据超链接结构和样式 表。 9 识别和抽取w e b 中的关系信息及其出现模式 ( 4 ) 国际化。w e b 是国际化的，但是大多数的文本是使用英文编写的。x m l 有助于改变这种状况，x m l 完全支持u n i c o d e 字符集，这个字符集几乎支持目 前地球上使用的、非虚构文字中的每个字符。 2 2 3x m l 文档 一篇x m l 文档由标记和内容组成。标记说明了数据的含义，使用者可以自由 定义标签( t a g ) 。x m l 中共有六种标记：元素( e l e m e n t s ) 、属性( a t t r i b u t e s ) 、 实体引用( e n t it yr e f e r e n c e s ) 、注释( c o m m e n t s ) 、处理指令( p r o c e s s i n g i n s t r u c t i o n s ) 和c d a t a 段( c d a t as e c t i o n s ) 。其中，元素是标记的最常见形式， 由尖括号分隔，大多数元素标识它所包含的内容的性质。 元素是x m l 文档的逻辑基础，一个x m l 文档实例就是一个元素，称之为根元 素或文档实体，而且一个x m l 文档有且仅有一个根元素，其他的元素都作为根元 素的子元素存在。x m l 的基本思想实际上就是利用数据标识表示数据的含义，利 用简单的嵌套和引用来实现数据元素之间的关系。 ( m l 包含三个要素：d t d ( d o c u m e n tt y p ed e s c r i p t i o n ) 或x m ls c h e m a ， x s l ( e x t e n s i h l es t y l e s h e e tl a n g u a g e ，可扩展样式表语言) 和x l i n k ( e x t e n s i b l e l in kl a n g u a g e ，可扩展链按语言) 。d t d 和x m ls c h e m a 规定了x m l 文件的逻辑结 构，定义了x m l 文件的元素、元素的属性以及元素与元素属性之间的关系：x s l 用于规定x m l 文档呈现的样式，使得数据及其表现形式相互独立：而x l i n k 将进 一步扩展目前w e b 上已有的简单链接。 x m l 文档有两个要求，即有效的( v a l i d ) 和格式良好的( w e l l f o r m e d ) 。所谓 有效的是指x 札文档必须满足d t d 或x m ls c h e m a 规定的逻辑结构；格式良好的 是指x m l 文档的物理结构必须满足x m l 的规范，如标记的匹配等。 建立一个x m l 应用的典型步骤包括： ( 1 ) 选择或写一个d i d 或) ( m ls c h e m a ； ( 2 ) 生成x m l 文档； ( 3 ) 解析x m l 文档，解析是x m l 文档应用的第一步，解析的标准有x m l 的简 单应用程序接口( s a x ) 和x m l 文档对象模型( d o m ) ，目前已有各种语言的解析器。 ( 4 ) 显示x m l 文档，可以直接用浏览器( 如i e 5 0 以上) ，将x m l 文档直接发 送给浏览器，用浏览器对其进行浏览，也可以使用x s l 将x m l 翻译成浏览器可处 华侨大学硕上论文 理的内容。 2 2 4x m l 的编程接口 1 x m l 解析器 x m l 解析器( 又称为处理器) 读取文档，并且验证文档所包含的内容是否是 形式规范的x m l 。解析器是处于应用程序和x m l 文件之间的软件组件。通过解析 器对x f f l 文件进行词法和语法分析，从而提供应用程序对文件内容进行操作。 2 x m l 解析器的分类 按解析器提供给应用程序的接口可以将解析器分为：基于对象的解析器d o m ( 文档对象模型) 和基于事件的解析器s a x ( x m l 简单应用程序接口) 。 ( 1 ) d o h ( d o c u m e n to b j e c tm o d e l ，文件对象模型) 基于对象的解析器d o m 是一套合法的w e l l - f o r m e d 文件设计的a p i ，它同时 定义了这些文件的逻辑结构，访问及操作方法。d o m 最重要的特性是必须将整个 文档解析并存储在内存中，以便建立这个文档的数据结构。这个特性对某些应用 程序而言是有影响的，这些应用程序必须在大型的文档或完整的文档处理结束之 后才能运行。另外，许多d o m 工具都需要很多内存，一些甚至需要占用百分之百 的内存，远远超过了文档的原始尺寸。d 例对于那些需要对一篇文档的不同部分 重复、随机访问的应用程序来说非常有效。 ( 2 ) s a x ( s i m p l ea p p l i c a t i o nf o r ) ( m l ，x m l 简单应用程序接口) s a x 是基于事件的解析器，它使用了回词( c a l lb a c k ) 的方式来分析x m l 文 件。s a x 接口分析x m l 文件的基本原理为：首先获得一个实现了s a x 接e l 的解析 器，然后自己编写一个符合s a x 标准的处理器类，并且把这个类注册到刚刚做好 的解析器；解析x m l 文件时，解析器会把x m l 文件作为一个流读出来，然后再把 文件流转换成个事件流，这个事件流的内容包括“文档开始”，“文档结 束”，“元素开始”，“元素结束”等等：调用注册到解析器里的处理器里面的方 法对相应类型的元素进行处理。 识别和抽取w e b 中的关系信息及其出现模式 第三章关系数据挖掘方法及实现算法设计 3 1 关系数据挖掘目标 本课题的目标是构造一个从x m l 文档中识别并提取出关系数据的系统。该系 统采用一种简单而且直观的方式提供给用户定义其需要从w e b 中获取的关系主 题，以及构成该关系主题的两类或两类以上实体。系统根据用户定义的挖掘请求 自动地从w e b 中搜寻相关x m l 文档，将寻找到的x m l 文档存入文档库中，并反馈 一部分给用户，让用户指定与挖掘请求最相似的文档作为样例文档；计算x m l 文 档与样例文档的相似度值，并从得到的这一组值中自动推导出相似度阈值；将文 档的相似度值与阈值进行比较，完成文档库中) ( m l 文档的自动聚类，并得到我们 的关系数据抽取源；创建用户的挖掘模式以及数据抽取源中欲处理文档的模式， 经过模式匹配抽取文档中的实体实例值，最后对实例值进行配对构成关系数据并 将结果反馈给用户。 识别包含用户指定的实体以及实体间相互关系的x m l 文档，并从中抽取出 关系数据，整个挖掘的任务可描述为： 设r j p 表示某个关系主题的实例数据集合，胄表示r p 中的实例数据隐含的 关系集合，p 表示兄尸中实例数据的出现模式集合，初始情况下用户指定的实体 以及实体间相互关系可以表示为，s 表示用户指定的样例文档，形表示x m l 文档库中的第i 个文档，则挖掘的实现过程可以表示为： p = g ( 风，s ) r p = p u p u f ( p ，彬) 式表示根据用户定义的挖掘请求r 从样例文档s 中抽取出关系数据的出 现模式p 。式表示利用得到的模式p ，通过模式i ! i i i i i 取出x m l 文档库中 与之相匹配的文档中的新的关系数据尼p 。 而在挖掘过程中，我们还可以从x m l 文档中获取与主题相关的未知关系。 可描述为：设r p 、r 、p 分别表示关系实例数据、关系和模式的集合，初始情 况下用户指定的实体以及实体间相互关系可以表示为r 。，s 表示用户指定的样 华侨大学硕士论文 例文档，岷表示x m l 文档库中相似度大于阈值的文档类，而彬表示相似度小 于阈值的文档类，则挖掘未知关系可以表示为： p 2g ( r ，s ) r j p = r p u f ( p ，k ) r = 月u h ( p ，旺) 式表示根据用户定义的挖掘请求r 。从样例文档s 中抽取出关系数据的出 现模式p 。式表示通过模式匹配文档库中相似度大于阈值的文档中( 岷) 抽取出 与用户需求相匹配的关系数据丑p 。而从相似度小于阂值的文档中( 职) 发现用户 指定实体间的未知关系矗，如式所示。 3 2 关系数据挖掘方法 1 提取用户定义的关系集合r o 中的关键词，并使用w o r d n e t 【1 2 】对关键词进行基 于语义的扩充得到关键词集合。使用w e b 中的搜索引擎进行基于关键词的查 询，将搜集到的x m l 文档存入x m l 文档库。 2 对文档库中x m l 文档进行数据预处理。即判断其包含了用户需求的可能性， 如果可能性太d , 贝t j 将其从文档库中删除；将经过数据预处理后的x m l 文档反 馈一部分给用户，让用户从中指定与挖掘请求最相似的文档作为样例文档s ( 又称种子文档) 。 3 计算x m l 文档与样例文档的相似度。取出x m l 文档库中的文档( 又称查询 文档) ，模式匹配通过计算样例文档和查询文档之间的相似度来实现。 4 使用三次或三次以上的曲线对相似度曲线进行拟合，求曲线的拐点，并从与拐 点相对应的曲线函数值中按经验选取或由用户从中指定相似度闽值。 5 按照相似度阈值进行文档的聚类。若查询文档的相似度值大于等于阈值，我们 认为查询文档中包含了用户的需求，匹配成功，转入数据抽取。若相似度值小 于闽值，则认为该文档中包含了用户指定实体间的未知关系，将这些文档归为 一类。将这类文档进行重新聚类，以发现未知关系。 6 关系数据的抽取。创建用户的挖掘模式以及欲处理文档的树模式，利用树匹配 识剐和抽取w e b 中的关系信息及其出现模式 抽取查询文档的目标数据。 3 3 关系数据挖掘的主要算法 3 3 1 相似度计算 x m l 文档相似度的计算是自动判别两篇文档在语义上是否相关的重要手 段。准确地量化两段x m l 文档的相似度为各种各样的x m l 文档挖掘和处理的 应用提供了一个良好的基础，例如目前w e b 中很多处理x m l 文档的应用中需要 使用到x m l 文档的聚类和分类等技术，如果在文档的聚类和归类算法中能充分 考虑到文档的语义信息，并对文档在语义上的相似程度进行准确的量化，那么各 种各样的数据挖掘应用将能够得到更精确的结果。 本文通过计算文档库中的x m l 文档与样例文档之间的相似度来衡量它们在 语义上的关联程度。根据相似度值是否大于指定的阈值来判定查询文档中是否包 含了用户需求的关系数据。 衡量两段x m l 文档的相似度可以从两个方面进行：元素的语义和文档结构。 首先分别计算x m l 文档的元素语义相似度和结构相似度，然后通过加权公式计 算出最后的相似度值。 3 3 1 1 语义相似度的计算 1 语义相似度计算的实现思想 x m l 文档的标记包含了丰富的语义信息，因此将两段x m l 文档的标记抽 取出来进行分析。文献b o 提出了一种考虑两篇x m l 文档标记的相似性和元素 嵌套关系的相似性的思想，并提出了一种构造相似度矩阵的方法。参考文 1 0 】量 化两篇文档元素的语义相似度的思想，本文提出一个关于x m l 文档元素语义相 似度的计算方法，与 1 0 】不同的是，本文以文本挖掘技术中提取文本特征、用矢 量空间模型( 、铷t o rs p a c e m o d e l ) 燃模的思想【1 1 】为基础，为诅一文档建立 关于标记的矢量模型，然后根据矢量模型计算其余弦距离来量化文档的语义相似 度。 2 元素语义相似度的计算方法 在对x m l 文档的语义信息进行分析时，我们基于以下几个方面考虑： 华侨大学硕士论文 x m l 文档中的元素反映了文档的内容 如图3 - 2 和图3 - 3 中的x m l 文档e m p l o y e e l x m l 和e m p l o y e e 2 x m l ，通过两段文 档中包含的元素，我们了解到这两段文档都是关于雇员信息的。 图3 - 2e m n l o v e e l x m l x m l 标记的同义词、合成词和缩写形式 同样的一个语义信息可以通过不同的词语、句子以及方式表达出来，因此在 考虑两段x m l 文档的语义相似度时，我们需要分析两段文档是否使用了包含相 同语义信息的标记。从上面两个x m l 文档我们可以看到：标记e m p l o y e e 和 w o r k e r ，e m p l o y e e i n f o r m a t i o n 和w o r