（计算机软件与理论专业论文）基于元素层次表达式模型的xml文档相似度计算.pdf

摘要 摘要 x m l 是w 3 c 推荐的一种通用标记语言，凭借其自描述性、可扩展性、半 结构化等特点，逐渐成为w e b 上数据表示和交换的标准，在多个领域都有广泛 应用。随着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 文档的结构聚类进行研究，提出了一种新的表 示模型元素层次表达式模型( e l e m ) 。该模型以元素为中心，以元素之间的 层次关系为主体，以关系集合为表示形式。该模型以简洁的形式表示x m l 文 档的结构信息，改善了树型模型不易处理、操作难的缺点，并弥补了频繁路径 模型在表示层次信息方面的不足。 在x m l 结构挖掘中，分类、聚类是常用的挖掘方法。x m l 文档的相似度 计算是进行x m l 文档分类、聚类的基础，能对分类和聚类的效果产生重要影 响。本文综合考虑了语义信息对元素相似度的影响，层次信息对结构相似度的 影响，提出了元素层次表达式模型的相似度计算方法( l e m s ) 。为了验证基于该 模型的相似度计算的效果，本文采用了k 中心点算法进行聚类分析。实验结果 表明，基于这种相似度计算方法的聚类效果优于基于树编辑距离、p b c l u s t e r i n g 等方法得到的效果。 关键词：x m l 元素层次表达式模型文档结构相似度文档聚类 a b s t r a c t a b s t r a c t x m li sag e n e r a lm a r k u pl a n g u a g er e c o m m e n d e db yw 3 c w i t hf e a t u r e so f s e l f - d e s c r i p t i v e ，e x t e n s i b l e ，s e m i - s t m c t u r e d ，x m lh a sg r a d u a l l yb e c o m ec r i t e r i o no f d a t ar e p r e s e n t i o na n dd a t ae x c h a n g e x m li sw i d e l yu s e di nan u m b e ro fa r e a s 、m m l a r g ea m o u n to fx m ld o c u m e n t s ，h o wt od i s c o v e rv a l u a b l ei n f o r m a t i o nf r o mt h e m a s s i v ed o c u m e n t si s b e c o m i n gap r o b l e mt ob er e s o l v e d x m lm i n i n gi s a l l i m p o r t a n ta p p l i c a t i o no fk n o w l e d g ed i s c o v e r yt e c h n o l o g y x m ld o c u m e n t sm i n i n g i sc o n s i s to fc o n t e n tm i n i n ga n ds t r u c t u r em i n i n g t h es t r u c t u r eo fx m ld o c u m e n ti s a ni m p o r t a n tc h a r a c t e r i s t i c s t r u c t u r em i n i n gc o u l de x c a v a t et h ek n o w l e d g eb e t w e e n t h es t r u c t u r e so fx m l d o c u m e n t s ，a n df a c i l i t a t ex m ld a t ae x t r a c t i o n , i n t e g r a t i o n a n do t h e ra p p l i c a t i o n s x m ld o c u m e n tm o d e li st h eb a s i so fx m ld o c u m e n ts t r u c t u r em i n i n g a f t e r i n t r o d u c i n gx m l t r e em o d e la n df r e q u e n tt r e em o d e l ，t h i sp a p e rp u r p o s e san e w x m ld o c u m e n tm o d e l e l e m e n tl e v e le x p r e s s i o nm o d e l ( e l e m ) i no r d e rt o f a c i l i t a t et h es t u d yo fx m ld o c u m e n t ss t r u c t u r em i n i n g t l l i sm o d e lt r e a t st h e d e m e n t s 硒c e n t e r , t h el e v e lr e l a t i o nb e t w e e ne l e m e n t sa sm a i np a r t ，t h es e to f r e l a t i o n 嬲t h ef o r m l e v e lr e l a t i o nr e c o r d st h ep a r e n t - c h i l d r e ni n f o r m a t i o na n dl e v e l i n f o r m a t i o ni n t h ex m ld o c u m e n t t h i sm o d e le x p r e s s e st h ex m ld o c u m e n t s t r u c t u r ei nac o n c i s ef o r m ；t h ee f f i c i e n c yo ft h eo p e r a t i o no nt h i sm o d e li sh i g h e r t h a nt h ex m lt r e em o d e l a n dt h i sm o d e le n h a n c e st h ee x p r e s s i o na b i l i t yo fl e v e l i n f o r m a t i o nc o m p a r i n gt ot h ef r e q u e n tt r c cm o d e l w h e nb u i l d i n gs t r u c t u r em o d e l f o rl a r g e - s c a l es e to fx m ld o c u m e n t s ，t h et i m ee f f i c i e n c yo fb u i l d i n ge l e m e n tl e v e l e x p r e s s i o nm o d e li ss i m i l a rt ot h et r e es 仃u c l = 1 1 r em o d e l ，a n di ss u p e r i o rt of r e q u e n t p a t hm o d e l c l a s s i f i c a t i o na n dc l u s t e r i n ga r ec o m m o n l yu s e dm e t h o di nx m ls 仃1 l d 腑 m i n i n g 1 1 1 cs i m i l a r i t yb e t w e e nx m l d o c u m e n t si st h eb a s i so fc l a s s i f i c a t i o na n d c l u s t e r i n g ，w i t hi m p a c to nt h em i n i n gr e s u l t sp a p e rc o n s i d e r ss e m a n t i ci m p a c t o nt h ee l e m e n ts i m i l a r i t ya n dl e v e li m p a c to nt h el e v e lr e l a t i o n , p r o p o s e st h e i i s i m i l a r i t yc a l c u l a t i o nm e t h o db a s e do i le l e m e n tl e v e le x p r e s s i o nm o d e la st h e c o r r e s p o n d i n gx m ld o c u m e n t ss i m i l a r i t y i no r d e rt ov e r i f yt h ee f f e c to ft h i s m e t h o d ，t h i sp a p e ra d o p t e dk c e n t e rc l u s t e r i n g a l g o r i t h m t h er e s u l t so ft h e e x p e r i m e n ts h o wt h a tt h es i m i l a r i t yc a l c u l a t i o nm e t h o db a s e do ne l e ma r es u p e r i o r t ot r e ee d i td i s t a n c ea l g o r i t h mb a s e do nt r e em o d e la n dp b c l u s t e f i n ga l g o r i t h m b a s e do nf r e q u e n tp a t hm o d e l k e yw o r d s ：x m l ；e l e m ；s t r u c t u r es i m i l a r i t y ；x m lc l u s t e r i n g i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：搋嘲户 如以年j 月订日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：枷乇带 砩8 年s 只邀e l 第一章绪论 第一章绪论 第一节课题研究背景 随着信息技术和i n t e r n e t 的不断发展与普及，信息化已经成为人类社会经 济发展的重要组成部分。i n t e r n e t 已经作为获取、发布和传递信息的重要工具， 网络上的信息量呈几何级数增长，这使得信息表示和信息交换成为难题。 可扩展标记语言 1 ( 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 ) 是w 3 c 组织推 荐的一种通用标记语言，从s g m l 发展而来，它具有s g m l 的强大功能和可 扩展性，同时又具有h t m l 的简单性。它是w 3 c 最具有前瞻性和最有影响的 标准之一。x m l 凭借自描述性、可扩展性及半结构化等特点，逐渐成为数据表 示和数据交换的标准，在各个领域都得到了广泛的支持和应用。 随着x m l 文档的大量涌现，如何从海量x m l 文档中挖掘出有价值的信息， 成为企业和用户关心的问题。数据挖掘，这个传统的数据管理与数据分析方法， 正逐步涉及x m l 数据领域。2 0 0 2 年，n a y a k 等人提出了x m l 文档知识发现 的概念【2 】。x m l 文档数据挖掘涉及到x m l 、数据挖掘、机器学习、数据库、 信息检索等多个方面的知识与技术。 常用的数据挖掘方法，如分类、聚类分析、关联规则挖掘等都能够用于x m l 文档数据挖掘领域。x m l 分类挖掘的目的是，根据x m l 文档实例的某种特性， 将该文档归类到预定义的类别中，分类的依据通常为x m l 文档的模式( d t d 或s c h e m a ) 。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 文档作为研究对象，包含内容和结构两部分。内容是指嵌套在x m l 文档层次结构中的数据( 主要是文本) 。结构指x m l 文档的层次模型结构。因 此，在x m l 数据挖掘研究的最初阶段，针对挖掘对象的不同，x m l 数据挖掘 通常被分为内容挖掘和结构挖掘两个方向。 伴随着x m l 数据挖掘研究的不断深入，基于x m l 文档结构的数据挖掘( 主 要是分类和聚类) 在很多方面得到了很好的应用。特别是近几年不断发展和广 为流行的x m l 数据库，以及i n t e r n e t 上的信息检索和语义w e b ( 以x m l 作为 数据传递载体和交换标准) 等。而x m l 内容挖掘则很少有专家和学者问津。 因此学者们开始重新思考x m l 数据挖掘的定义和内涵，特别是x m l 内容挖掘 的价值和意义。 i n e x ( i n i t i a t i v ef o r t h ee v a l u a t i o no fx m lr e t r i e v a l ) 是关于x m l 检索的 国际会议组织，在最近几年的研究中其对x m l 数据挖掘任务做了详细的定义 与说明。它把x m l 数据挖掘分为x m l 结构挖掘( s o ) 和x m l 结构与内容挖 掘( s c ) 【3 】，其中s c 的任务不再只是针对x m l 中的数据进行处理，而是综合 结构与数据两方面的信息，进而提取出人们关心或者有价值的内容知识。 在这个组织的领导和组织下，许多成熟的x m l 数据挖掘算法被提出，这 些算法有聚类挖掘也有分类挖掘，既有针对s o 任务的，也有针对s c 任务的。 n a y a k 4 在针对s o 任务的聚类挖掘方面进行研究；、研c o u s 骶【6 】在针对s c 任务 的聚类挖掘方面进行研究；y o n 一7 】在针对s o 任务的分类挖掘方面进行研究； n d 8 】在针对s c 任务的分类挖掘方面进行研究，他们中有些人的研究同时兼具 了几个方面，具体情况见图2 2 。 由于有前期工作的基础，s o 的研究正在不断完善中，而s c 的研究还处于 起步阶段，但是随着内容挖掘的定义的改变，二者之间不再是那种对立或者格 格不入的关系，而是一种基础和辅助的关系。s o 是s c 的基础，可以为s c 提 供很多有价值的信息，而s o 中的很多成熟的技术可以被s c 借鉴。 相信随着人们对s o 任务研究的不断深入，在s c 任务的研究一定会获得启 发并取得进展。 2 第一章绪论 第三节主要研究工作及论文组织结构 随着x m l 数据挖掘研究的不断深入，人们越来越发现，x m l 数据的表示 形式( 即表示模型) 对x m l 数据的处理有着极其重要的作用和影响。x m l 树 型结构模型及频繁路径模型是两种最常用的x m l 文档结构表示模型。树型结 构模型是最直观、最易于理解的表示模型，但随着文档规模的增大，树型模型 的处理效率降低，时间开销增大；频繁路径模型表示形式简单，但其表示信息 不如树型结构完整，只是近似地反映x m l 文档的结构，以其为模型进行聚类， 准确率不高。综合上述两种模型的优缺点，本文提出了一种针对x m l 文档结 构聚类的模型元素层次表达式模型，并介绍了基于层次表达式模型的文档 相似度计算方法，进行了聚类分析。主要研究工作有如下方面： 建立元素层次表达式模型e l e m 元素层次表达式模型是对树型结构模型的继承和发展，它忽略了x m l 文 档中属性、注释、文本等节点类型，只考虑元素节点。模型记录x m l 文档中 的元素父子节点关系及关系所在的层次信息作为元素层次表达式，组成元素层 次表达式模型。改善了树型模型不易处理、难于操作的缺点，并弥补了频繁路 径模型在层次信息表示方面的不足。 精简元素层次表达式模型 x m l 文档中可能含有大量的重复元素，重复元素使元素层次表达式模型规 模庞大冗余。处理表达式模型中的重复元素与重复的元素层次表达式，有助于 减小模型的规模，得到一个简洁、表达信息完整的结构表示模型，为相似度计 算打下良好基础。 建立基于元素层次表达式模型的x m l 文档相似度计算方法一l e m s x m l 文档的相似度计算方法根据表示模型的不同而有所区别，通常将表示 模型的相似度看作对应的x m l 文档的相似度。论文介绍了用于x m l 树型结构 模型的树编辑距离算法和用于频繁路径模型的p b c l u s t e r i n g 算法。针对本文提 出的元素层次表达式模型，定义了基于元素层次表达式模型的x m l 文档相似 度计算方法，该计算方法将x m l 文档的语义信息纳入计算之中，得出x m l 文档间的语义与结构相似度。 聚类分析 x m l 文档的相似度计算是结构聚类的基础。论文通过经典的聚类算法 - k 中心点算法，对x m l 文档进行聚类分析。并设计实验，对比了基于元 3 第一章绪论 素层次表达式模型的相似度计算方法与树编辑距离、p b c l u s t e r i n g 算法的正确 率。 本论文的组织结构如下： 第一章介绍x m l 数据挖掘的研究背景，目前的研究热点，并介绍了本文 的主要研究工作。 第二章主要介绍了x m l 数据挖掘的基本知识，及x m l 文档数据挖掘的研 究进展。 第三章首先简要介绍了几种常见的x m l 文档的结构模型m l 文档树 型结构模型及频繁路径模型，分析了两种模型的特点及主要应用领域。本文以 x m l 文档结构聚类为研究目的，提出了一种新的x m l 文档结构表示模型 元素层次表达式模型，并介绍了模型的构建方法。 第四章简要介绍了基于树型结构模型的树编辑距离相似度计算方法，及基 于频繁路径模型的p b c l u s t e r i n g 相似度计算方法，后着重提出了基于元素层次 表达式模型的相似度计算方法一l e m s ，并辅以实例说明。 第五章介绍了k 中心点聚类算法，设计了x m l 文档聚类实验，并主要比 较了l e m s 相似度计算方法与树编辑距离算法、p b c l u s t e r i n g 算法的时间效率 和聚类效果。 第六章对全文进行总结，提出了本文存在的不足，并展望进一步的研究工 作。 4 第二章x m l 数据挖掘的相关研究 第二章x 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 3 c 设计的一种可扩展的 标记语言。x m l 起源于s g 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 pl a n g u a g e ) 是一种通用的文档结构描 述符号化语言，主要用来定义文献模型的逻辑和物理类结构。它提供了一种可 以无限扩展的语言，允许任何人根据自己的需要加以扩充。它主要用于大量高 度结构化数据的防卫区和其他各种工业领域，利于分类和检索。由于有太多的 可选功能，s g m l 变得过于复杂，以至于很难编写出针对这种语言的普通解释 器，且s g m l 不适于w e b 数据描述。 h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 是超文本标记语言，它定义了一套固 定的标记，来描述一定数目的元素，比较适合w e b 页面的开发。h t m l 的标记 较少，只支持固定的标记集，不能支持特定领域的标记语言，缺少s g m l 的柔 性和适应性。 x m l 将s g m l 的强大功能与h t m l 的广泛性结合了起来，并消除了上述 两种置标语言的缺点。x m l 继承了s g m l 的可扩展性，允许使用者创建和使 用他们自己的标记而不是h t m l 的有限词汇表，可以作为特定领域信息共享与 数据交换的基础。而x m l 的结构化数据表示方式，使得用户界面与结构化数 据分离，因此w e b 用户所追求的先进功能在x m l 环境下更容易实现。简单来 说，x m l 是一种自描述、半结构化和可扩展的标识语言，是一种定义语言的语 言，也是一种元语言。 x m l 是w e b 上表示结构化信息的一种标准文本格式，并没有复杂的语法 和数据定义。它作为新一代数据表示和数据交换的标准，具有如下特点： 1 可扩展性：x m l 允许使用者创建和使用他们自己的标记，因此x m l 可以 开发各种不同专业的特定领域的标记语言。 2 灵活性：h t m l 的格式、超文本和图形用户界面语义的混合特性限制了它 的发展。而x m l 提供了一种结构化的数据表示方式，使得用户界面分离 于结构化数据。因此，w e b 用户所追求的许多先进功能在x m l 环境下更 5 第二章x m l 数据挖掘的相关研究 容易实现。 3 自描述性：x m l 文档通常包含一个文档类型声明，因而x m l 文档是自描 述的。x m l 表示数据的方式真正做到了独立于系统应用，并且数据能够重 用。x m l 文档被看作是文档的数据库化和数据的文档化。 4 可移植性：x m l 是以文本形式描述的，适合各种平台环境的数据交换。在 一种平台上编写的x m l 文档无须更改即可移植到其他平台上。 5 半结构化：x m l 文档的机构可以通过模式来描述，通过模式来验证文档的 有效性较容易。 x m l 的特点决定了其优秀的性能表现，它的出现解决了因多种多样数据格 式带来的交换障碍，使各个领域的数据交换成为可能。 第二节x m l 数据挖掘 2 2 1 数据挖掘概述 近年来，数据挖掘引起了信息产业界的极大关注，主要原因是存在可以广 泛使用的大量数据，并且迫切需要将这些数据转换成有用的信息和知识。如何 从数据的海洋中迅速、准确地挖掘出有价值和有指导意义的信息己成为人们关 注的焦点。知识发现过程由数据清理、数据集成、数据选择、数据变换、数据 挖掘、模式评估与知识表示几个步骤组成。数据挖掘是知识发现中最重要的步 骤之一，因为它能发现隐藏的模式。简单地说，数据挖掘是从存放在数据库、 数据仓库或其它信息库中的大量数据中挖掘有趣知识的过程。 根据挖掘任务的不同，数据挖掘可以分为分类和预测、聚类、关联规则发 现、序列模式发现、依赖关系和依赖模式发现等技术，下面介绍几种常用的数 据挖掘方法。 1 分类( c l a s s i f i c a t i o n ) 分类的目的是使用一个分类函数或者分类模型，将数据库、数据仓库或其 它信息库中的数据项映射到给定类别中的某一个类别中去。分类在商业上应用 最广泛。 2 聚类( c l u s t e r i n g ) 聚类主要是根据记录的特征将其划分为群或聚类，使得一个聚类中的记录 相似，但与其它聚类中的记录不相似。相似程度由记录的距离定义。与分类不 6 第二章x m l 数据挖掘的相关研究 同，聚类分析的输入是一组未分类的记录，它根据一定的规则合理地划分记录 集合。聚类分析是数据挖掘最重要的技术之一。 3 关联规贝j j ( a s s o c i a t i o n ) 关联规则是描述一个事物中对象同时出现的规律的知识模式。在大量记录 中发现有趣的关联关系，通过量化的数值描述一个对象出现对另外一个对象出 现有多大的影响。 4 序列模式( s e q u e n c ea n a l y s i sa n dt i m es e q u = c o 序列模式分析也是为了挖掘数据间的联系，与关联规则分析法类似。但序 列模式分析更侧重于分析数据间的因果关系。 2 2 2x 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 文档由于半结构化特性，其上的数据挖掘不同于结 构化数据挖掘和文本挖掘。x m l 文档不仅包含数据信息，还包含文档结构。因 此，x m l 数据挖掘也可以分为文档内容挖掘和文档结构挖掘两类。n a y a k 等人 提出了对x m l 文档数据挖掘的分类方式【2 】，如图2 1 所示。 x m l 内容挖掘是对文档中包含在元素开始标签和结束标签之间的文本进 行挖掘，可以分为文档内容分析与文档结构分类。文档内容挖掘的方法与传统 的数据方法类似，可以转换为传统的关系型数据的挖掘。而结构挖掘以x m l 文档结构为挖掘对象，是从x m l 文档的结构中发现有价值知识的过程。文档 的结构信息通过有根、有序的标签树表示，其中的标签对应于x m l 文档的t a g 。 x m l 结构挖掘首先将x m l 文档转换为某种结构模型，然后对结构模型进行数 据挖掘分析，得到挖掘结果。在实际应用中，结构挖掘与内容挖掘并非没有交 集。有些模型可以综合考虑结构信息与内容信息。 7 第二章x m l 数据挖掘的相关研究 图2 1 l 数据挖掘分类 x m l 数据挖掘方法主要有分类、聚类和关联规则。分类与聚类是目前较常 用到的技术，其上的研究成果也最为显著。i n e x ( i n i t i a t i v ef o r t h ee v a l u a t i o no f x m l r e t r i e v a l ) 是关于x m l 检索的国际会议，近两年，i n e x 的研究方向从信 息检索的相关问题转向x m l 文档数据挖掘。图2 2 所示的为i n e x2 0 0 5 和 i n e x2 0 0 6 t 3 1 在x m l 数据挖掘中分类与聚类方面的研究成果。 图2 2x m l 文档数据挖掘的发展 i n e x2 0 0 5 针对结构挖掘( s t r u c t u r eo n l y , s o ) 与结构内容挖掘( s t r u c t u r ea n d 8 第二章x m l 数据挖掘的相关研究 c o n t e n t , s o ) ，而2 0 0 6 更着重于结构内容挖掘( s c ) 。分类挖掘的目标是能够区分 来源于不同数据源的数据，而聚类挖掘是为了发现隐藏在数据源中的信息。 i n e x2 0 0 5 和i n e x2 0 0 6 的数据集如表2 1 所示，数据集m o v i e 为基于i m d b 9 】 的人造数据集，而i e e e 与w i k i p e d i a 来源于真实数据。 表2 1i n e x 会议数据集 c o r p u s n bd o c sn bn o d el a b e l su s c df o rs ou s c df o rs c m o v i e 9 ，4 6 3 1 9 0y e sn o i e e e 1 2 ，1 0 8 1 5 0y e sy e s w i k i p e d i a 1 5 0 0 0 01 0 0 0 0y e sy e s 从图2 2 中可以看出，d o u c e t 1 0 1 、h a g e n b u c h n e r 1 1 1 、n a y a k 4 1 、d ek n i j t = 【1 3 】 等人的研究主要基于四种模型：向量模型、神经网络模型、相似度模型及频繁 树模型。d o u c e t 研究基于向量模型的聚类方法。它综合考虑x m l 文档的结构 和内容信息，将其转化成向量，并使用k - m e a n s 算法聚类。d o u c e t 提出在文档 描述过程中要考虑结构信息和内容信息所占的比重；h a g e n b u c h n e r 提出了一种 使用神经网络模型的方法，该方法既可以只聚类x m l 结构又可以聚类x m l 结构和内容；n a y a k 提出了基于相似度模型的聚类方法。该方法通过计算 c p s i m ( c o m m o n p a t hs i m i l a r i t y ，频繁路径相似度) 来衡量一篇x m l 文档与一个 x m l 文档聚类( 集合) 之间的相似度；d eg a a i j f 提出一种基于频繁属性树模型 的x m l 文档分类算法。而上述四种模型则是目前x m l 文档结构挖掘的常用模 型。 分类和聚类是x m l 数据挖掘最常用的技术，x m l 文档间的相似度描述 x m l 文档间的近似程度，是分类与聚类分析的基础。文献 1 4 总结了目前相似 度计算的研究进展，将相似度计算分成了结构级( s t r u c t u r e 1 e v e l ) 与元素级 ( e l e m e n t 1 e v e l ) 两大类，如图2 3 所示。 9 第二章x m l 数据挖掘的相关研究 图2 3 相似度研究进展 结构级的相似度计算有三个研究方向：文档间的结构和内容相似度，可细 分为文档聚类、文档更新检测，文档的相似度查询及频繁树查询；文档与模式 间的相似度计算；以及从文档中抽取模式信息。 结构级的相似度计算方法将树的整体结构看作比较的重要因素，而将语义 看作决定相似度的非重要因素。而元素级的相似度计算多指模式的匹配，其更 注重语义信息，模式相似度匹配也分为三个研究方向：实例级的模式相似度匹 配；模式级的模式相似度匹配；以及实例与模式混合的模式相似度匹配，与上 述两种相比较，实例与模式混合的模式相似度匹配结果更准确。 i 0 第三章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 文档最重要的组成部分，结构模型 应该保留x m l 文档的层次关系与元素语义信息；x m l 文档通常包含着大量重 复结构，结构模型应对重复结构进行消减，以最简洁的表现形式描述文档结构； 结构模型通常被用来做进一步研究，如数据挖掘分析、数据查询、信息检索等， 因此结构模型还应便于操作，有利于相关研究。总之，x m l 文档的结构模型是 表示文档结构的重要手段，是研究文档结构的重要依据，也是x m l 研究者广 泛关注的问题。 本章首先介绍常用于x m l 文档数据挖掘的两种表示模型：x m l 树型模型 和频繁路径模型，再根据本文的研究目的，提出一种新的x m l 文档结构表示 模型元素层次表达式模型。为了详细说明各种表示模型，先介绍文献 1 】中 定义的x m l 文档的基本概念。 定义3 1 元素 x m l 元素e ，是指文档中的某个开始标签到相应的结束标签之间的内容， 还有一种特殊的元素空元素( 即用 表示的元素) 。 定义3 2 元素名称 元素名称是指元素标签的签名，又称为元素标签。通常用元素名称代表元 素。 定义3 3 根元素 一篇x m l 文档有且仅有一个根元素r o o t ，它不出现在其它任何元素的内 容中。根元素也叫文档元素，在其内部拥有整个逻辑文档。 定义3 4 父元素、子元素、兄弟元素 第三章x m l 文档的元素层次表达式模型 对于每一个非根元素c ，文件中另有一个元素p ，c 在p 的内容中，而不 在其它任何被p 所包含的元素的内容中，p 被称为c 的父元素( p a r e n t ) ，c 被 称为p 的子元素( c h i l d ) ，同在p 的内容中，且不在其它任何被p 所包含的元素 的内容中的其它元素，称为c 的兄弟元素( s i b l i n g ) 。 第一节x m l 文档结构模型的相关研究 3 1 1 树型结构模型 x m l 文档具有半结构化特性，本身含有层次结构。树型结构是对x m l 文 档最直观的诠释。w 3 c 组织提出了x m l 文档对象模型1 5 】( d o c u m e n to b j e c t m o d e l ，简称d o m ) 作为x m l 文档的树型表示模型。d o m 允许程序动态地访 问、更新x 1 v i l 文档的各个组成部分。 d o m 将x m l 文档分为若干类，较为常用的几种节点与x m l 文档节点的 对应关系如表3 1 所示： 表3 1d o m 节点与x i l 节点对应表 dom节点xml节点 声明节点 元素节点 属性节点 文本节点 注释节点 声明语句 元素 属性 元素和属性的具体内容 注释 d o m 能够完整地表示一个x m l 文档的信息，但其中的声明节点、注释节 点等节点信息并不是x m l 文档结构的必要表示信息，d o m 树含有较多的冗余 信息。文献 1 6 在d o m 树的基础上进行了改进，提出了一种树型表示模型 - x m l 文档树，作为x m l 文档的逻辑模型。 x m l 文档树是一种有序的、含有节点标签的树型结构，以x m l 文档的根 元素作为树模型的根节点，元素的属性也看作元素节点的子节点。x m l 文档树 既能够体现x m l 文档的层次特性，又能够表达x m l 文档元素的语义。 ) a l 文档树的定义如下： 定义3 5x m l 文档树 1 2 第三章x m l 文档的元素层次表达式模型 一篇x m l 文档d ( e 表示x m l 文档元素的集合) 可以表示为一棵有序 标签树t = ( y ，r o o t ，e d ，t y p e ，l a b ，v a l ， ) ，其中： y 是x m l 节点的集合： r o o t v 是树的根节点； 二元关系e dcv 2 是边的集合，如果u 是v 的父节点或v 是“的子节点，则 ，1 ，) e 1 ) ； 有穷字母表是由文档d 的元素和属性标签组成的集合； 函数t y p e ：v 一 e l e m ，a t t r ，t e x t 确定节点类型，t y p e ( v ) = e l e m 若v 为元素， t y p e ( v ) = a t t r 若1 ，为属性，t y p e ( v ) = t e x t 若1 ，为文本； 屹= r i v e v a t y p e ( v ) = e l e m 表示元素节点集合，圪= r i v e v a t y p e ( v ) = a t t r 表 示属性节点集合，巧= v l v e g t y p e ( v ) = t e x t 表示文本节点集合； 函数l a b ：圪u 圪一返回元素或属性节点的标签，记作l a b ( v ) = ，v e 圪v 圪 且，： 。= f i t = l a b ( v ) a v e l 表示元素节点标签的集合，。= i l l = l a b ( v ) a v e 圪 表 示属性节点标签的集合； 函数v a l ：圪u 巧一s t r 返回属性或文本节点的值，s t r 是x m l 文档中所有合 法字符串的集合； 二元关系c v 2 定义x m l 文档顺序，在文档d 中如果节点u 出现在v 之前 或u = v ，则( 甜，v ) 或记作u ，。 丁称为x m l 文档树。 x m l 文档中的元素在x m l 文档树中以节点的形式表示，包括根节点、内 部节点和叶节点。其中，根节点r o o t 对应x m l 文档中的根元素，叶节点对应 x m l 文档中的文本或x m l 文档中内容为空的元素。图3 2 为图3 1 所示的x m l 文档的文档树。 1 3 第三章x m l 文档的元素层次表达式模型 张三 0 0 1 a 公司 z h a n g a a a c o m ( 0 1 0 ) 6 2 3 4 5 6 7 8 五街号 北京市 北京 1 0 0 0 0 1 图3 1x m l 文档示例s a m p l e x m l 图3 2s a m p l e x m l 的文档树 x m l 文档树能够全面地反映x m l 文档的内容和结构，是一种直观、易于 理解的表示模型。x m l 文档树中包含x m l 文档元素、属性、文本等信息。而 x m l 文档的结构通常指元素及元素之间的关系，如父子元素关系、兄弟元素关 系等。因此，在研究x m l 文档结构的过程中，通常不考虑文档的文本内容和 1 4 第三章x m l 文档的元素层次表达式模型 属性，只考虑元素。将x m l 文档树的属性节点与文本节点删除，只保留元素 节点，得到的结构称为x m l 元素树 1 7 1 。 x m l 元素树只考虑x m l 文档结构的基本内容：元素及元素之间的关系。 元素之间的关系包含父子元素关系，兄弟元素之间的顺序关系等。x m l 元素树 的节点全部是元素节点，该结构能够完整清晰地描述x m l 文档的结构。x m l 元素树的定义如下： 定义3 6x m l 元素树 x m l 文档元素树可以表示为t = ( 圪，。，l a b , ，r o o t ) ，其中， r o o t v 是树的根节点； 圪= 1 ，i v v t y p e ( v ) = e l e m 表示元素节点集合； 。= p i ， l a b ( v ) = l a y 圪 表示元素节点标签的集合； 函数t a b , ：圪一。，返回元素节点的标签。 x m l 元素树r 中元素节点的标签与x m l 文档d 的元素可以建立一一对 应的关系，即丁中v v e 圪，在d 中有且仅有一个元素e e ，满足l a b ( e ) = l a b , ( v ) 。 图3 3 显示了图3 1 所示的x m l 文档对应的元素树。 图3 3s a m p l e x m l 的元素树 x m l 文档树型模型( d o m 树、文档树、元素树) 能全面地反映x m l 文 档的结构，是最直观、最易于理解的表示模型，也是x m l 数据挖掘经常采用 的模型。树型模型表示信息完整，能较好地表示x m l 文档的层次结构信息。 以其为基础进行相似度计算，聚类结果较好。但树型结构也有其弊端，随着x m l 文档规模的增大，树型结构也随之增大，在树型结构上对x m l 文档进行处理 的效率降低，时间开销增大。因此，许多研究者根据不同的研究需要，对x m l 1 5 第三章x 儿文档的元素层次表达式模型 树型结构模型进行适当的变形，得到适应其研究需要的其他模型。 3 1 2 频繁路径模型 x m l 文档通常表示为文档树、元素树等树型结构。当研究对象为x m l 文 档集合时，另一种模型一频繁路径模型，可以作为x m l 文档的结构表示模型。 频繁路径模型既可以表示集合中多篇文档的共性，也可以表示单个文档的特性。 因此，其在x m l 文档集合的研究中占用重要的地位。 为了介绍如何在路径集合模型的基础上构造频繁路径模型，先给出文献 1 4 】 介绍的频繁路径的相关定义。 定义3 7 叶结点路径 在有序标签树中，从根节点到叶节点的路径叫做叶结点路径，简称路径。 所有的叶节点路径组成x m l 文档的路径集合。 定义3 8 子路径 在x m l 路径集合中，