（计算机应用技术专业论文）基于结构向量空间和树路径模型的xml文档聚类技术研究.pdf

摘要摘要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 文档数据挖掘技术主要分为文档内容挖掘和文档结构挖掘。x m l 内容挖掘本质上是对标记值的挖掘，可以对单个或群组x m l 文档进行挖掘。x m l 的元素标记和嵌套关系表示x m l 文档的结构，结构挖掘实际操作是将x m l 文档的结构看作一棵标记树，在此基础上对树的挖掘。本文主要研究x m l 文档结构的聚类技术。通过研究发现，传统相似度计算方法不能满足嵌套结构的语义要求，树路径模型的聚类算法存在忽略兄弟节点之间关系和未考虑路径权重以及路径匹配方法等问题。为解决上述问题，本文设计了一个新的x m l 文档聚类方法：x m l 文档两阶段聚类方法( t p c m ：t w op h a s ec l u s t e r i n gm e t h o do fx m ld o c u m e n t s ) ，主要研究成果如下：1 、采用x s l t 生成x m l 文档结构框架的简化树，改进x m l 文档结构向量定义和x m l 文档结构相似度计算公式，对x m l 文档集合进行第一阶段聚类。2 、针对树路径模型的相似度算法存在的问题，提出改进的x m l 文档树路径模型，改进了路径之间相似度计算，使x m l 文档结构相似度计算结果更合理。在第一阶段文档集聚类结果基础上，按重聚类标准再进行第二阶段聚类，得出最后聚类结果。3 、对于每个阶段，分别对处理方法和程序流程进行了详细说明，并编程实现，得出了部分测试结果和性能分析。最后实验结果显示，使用t p c m 方法对x m l 文档集合进行聚类，较大地提高了聚类准确率，减少了时间开销。关键词：x m l 数据挖掘结构向量空间模型树路径文档结构相似度文档聚类a b s t r a c ta b s t r a c tx m l ( e x t e n s i b l em a r k u pl a n g u a g e ) s h o w sg r e a ta d v a n t a g eo nt h ed a t ae x p r e s s i o na n de x c h a n g ei nt h en e t w o r ka n do t h e ra r e a s n o w , m o r ea n dm o r ed a t ai ss t o r e db yx m ld o c u m e n t s t h ed a t am i n i n go fx m ld o c u m e n ti sw i d e l ys t u d i e di nt h e o r ya n dp r a c t i c e x m li sc o m p l i c a t e d ，h e t e r o g e n e i t y ,s e m i s t r u c t u r e ，t h et r a d i t i o n a ld a t am i i l i n gm e t h o d so fr e l a t i o n a ld a t ac a nn o tb ea p p l i e dt ox m ld i r e c t l y i ti si m p o r t a n tt oe x p l o r et h ee f f e c t i v et e c h n i q u eo fx m ld a t am i n i n gi nt h ef i e l do fd a t am i n i n g n o w , t h ed a t a - m i n i n gt e c h n o l o g yo fx m ld o c u m e n ti n c l u d e st h em i n i n go fx m lc o n t e n ta n dt h em i n i n go fx m ls t r u c t u r ea th o m ea n da b r o a d m i n i n go fx m lc o n t e n ti se s s e n t i a l l ym i n i n gf o rt a gv a l u e s ，i tc a l lm i n et h es i n g l eo rg r o u px m ld o c u m e n tv a l u e s t h et a ga n dn e s t e dr e l a t i o no fx m le l e m e n t se x p r e s s e st h ex m ls t r u c t u r e m i n i n go fx m ls t r u c t u r ei sm i n i n gf o rt r e eo fx m ld o c u m e n ts t r u c t u r ef o ri tr e g a r d sx m ls t r u c t u r e 嬲at a gt r e e t h i st h e s i sm a i n l ys t u d i e so nc l u s t e r i n gt e c h n i q u eo fx m ld o c u m e n ts t r u c t u r e i tw a sf o u n dt h a tt h et r a d i t i o n a ls i m i l a r i t ym e a s u r ec a nn o ts a t i s f yt h er e q u i r e m e n to fn e s t e ds t r u c t u r es e m a n t i c sa n dt h ec l u s t e r i n ga l g o r i t h mo ft r e ep a t hm o d e lh a ss o m ep r o b l e m sw h i c hi g n o r e dt h er e l a t i o nb e t w e e ns i b l i n gn o d e sa n dt h ep a t hm a t c h i n gm e t h o da n dt h ep a t hw e i g h t st h e s i sp r o p o s e dan e wc l u s t e r i n gm e t h o do fx m ld o c u m e n t s ：t p c m ( t w op h a s ec l u s t e r i n gm e t h o do fx m ld o c u m e n t s ) t h en e x ta r et h em a i nr e s u l t ：1 i nt h ef i r s tp h a s eo fc l u s t e r i n gm e t h o d ，i ta p p l i e sx s l tt og e n e r a t es i m p l i f i e dt r e ef r a m e w o r ko fx m ld o c u m e n ts t r u c t u r e ，t h e ng i v e st h ed e f i n i t i o no fx m ld o c u m e n ts t r u c t u r ev e c t o r , a n di t sf o r m u l ao fs t r u c t u r a ls i m i l a r i t y 2 i nt h es e c o n dp h a s eo ft h ec l u s t e r i n gm e t h o d ，w i t hc o n s i d e r a t i o no ft h ep r o b l e m so nt h es i m i l a r i t ym e a s u r eo ft r e ep a t h ，i ti m p r o v e st h et r e ep a t hm o d e la n di t ss i m i l a r i t ym e a s u r ei no r d e rt 0m a k et h es i m i l a r i t ym e a s u r eo fx m ld o c u m e n t sm o r ea c c u r a t ea n dm o r ea p p r o p r i a t e i ia b s t r a c t一_ - _ - _ _ 一3 f o re a c hm o d u l e ，t h i st h e s i sg i v e sad e t a i l e dd e s c r i p t i o no nt h et r e a t m e n tm e t h o d sa n dp r o g r a mf l o wr e s p e c t i v e l y , t h e ng i v e ss i m p l er e a l i z a t i o n ，a tl a s tg e t sp a r to ft h et e s tr e s u l t sa n df u n c t i o na n a l y s i s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h em e t h o d so ft p c mc a i li m p r o v et h ea c c u r a c yo fx m ld o c u m e n t sc l u s t e r i n g ，a n ds p e n dl e s st i m e k e y w o r d s ：x m ld a t am i n i n g ；s t r u c t u r ev e c t o rs p a c em o d e l ；t h et r e ep a t h ；d o c u m e n ts t r u c t u r a ls i m i l a r i t y ；d o c u m e n tc l u s t e r i n gi南开大学学位论文版权使用授权书本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。学位论文作者签名：黼磊少刁g 年j ，月z 7 日经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。各密级的最长保密年限及书写格式规定如下：南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：乡k 存磊妒舂年j ，只1 7 日第一章引言第一章引言第一节研究背景及意义近几十年来，随着信息技术和计算机网络技术的迅猛发展，信息化已经成为人类社会经济发展的关键因素。目前，随着信息技术的发展，特别是i n t e m e t的迅速发展和网络应用的深入，对信息的使用也逐渐向深层次发展，已进入一个通用的数据访问与共享的时代 1 】。网络信息的迅速增长，人们已将i n t e m e t 作为快速获取、发布和传递信息的重要工具。如今，网络上的内容几乎每时每刻都在更新，信息资源呈几何级数增长。人们获取信息并加以利用的重点不是在于如何获取资料，而是在于如何从海量的资料中去粗取精、去伪存真，以便获得有价值的信息。为了对用户提供更加方便、快捷和准确的信息查询与检索，用于文本挖掘和信息检索等多个领域的聚类技术成为了人们研究的热点。聚类( c l u s t e r i n g ) 是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程，由聚类所生成的簇是一组数据对象的集合。这些对象与同一簇中的对象彼此相似，与其他簇中的对象相异。它是一种无指导学习的基本方法，通常用来发现在无标记数据集中相似的组。文档聚类( d o c u m e n tc l u s t e r i n g ) 就是对文本信息的聚类，用于大量不同领域的文本挖掘和信息检索。最初，文档聚类用来研究提高信息检索的查准率和查全率，或作为查找最相似文档的有效方法。x m l 文档作为一种新的数据形式，是文本内容信息与结构信息的综合体，由于具有结构化、可扩展性、跨平台性等特点，越来越多的数据标准采用x m l 【2 j 。x m l 在信息管理、移动通信、网络教育、电子文档交换、电子商务、个性化出版等诸多领域得到了广泛应用，而且其应用范围还在不断扩展。x m l 逐渐成为信息存储与交换的主要形式，己经开始成为i n t e m e t 上数据描述和交换的事实标准。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 文档等半结构化数据的分析处理有了很多研究成果。有些侧重于半结构化数据集成；l o r e 项目( s t a n f o r d 大学) 【3 j 侧重于半结构化数据的模型以及存储与查询；有些提出采用嵌套定义的向量来描述文档元素，并在此模型基础上利用概率统计方法进行文档分类的扩展向量模型4 j ；有些将半结构化文本与自然语言理解等技术相结合，实现对语义信息的理解；有些基于贝叶斯网络模型进行半结构化文档分类【5 】。也有研究论文提出采用树编辑距离做为x m l 文档的结构相似性计算的方法【6 1 ；还有将x m l 结构信息看作时序关系，采用时序分析的方法进行结构相似性计算【7 】。综上所述，随着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 文档结构表示模型，目前最常用的x m l 文档结构表示模型是树型模型，较好的结构模型对提高结构聚类技术有重要的作用。因此应该综合考虑x m l 文档特点，结合它的树型结构、元素嵌套语义、父亲兄弟关系和重复匹配等来提出适当的结构模型。本文分析了国内外已有的x m l 文档聚类技术，对x m l 文档结构聚类技术进行了研究，提出了一种x m l 文档两阶段结构聚类方法( t p c m ：t w op h a s ec l u s t e r i n gm e t h o do fx m ld o c u m e n t s ) 。该方法首先采用传统的相似度计算和k - m e a n s 聚类算法对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 s l t ( e x t e n s i b l es t y l e s h e e tl a n g u g et r a n s f o r m a t i o n s ) 来产生x m l 文档结构，并将其模型化成树，去除重复的路径和不保留任何与结构无关的内容，采用以结构树路径作为结构单元。将x m l 文档中的每个结构单元看作一个向量，整个x m l 文档则被量化为一组向量，以一个矩阵来表示。利用传统相似度计算和k m e a n s 聚类算法，进行第一阶段x m l 文档聚类。第二步工作：通过分析相关的文献【8 。1 1 】发现它们是将一个x m l 文档模型化为一棵树( 图) ，用树( 图) 间的距离来表示两个x m l 文档间的相似度。通过对x m l 文档的不断深入研究，用树的编辑距离来计算x m l 文档的相似度时，发现传统的相似度的计算方法已不能满足计算有嵌套结构的语义的元素要求。如果用树来描述全部结构信息，树的结构不仅会非常庞大，而且树编辑距离方3第一章引言法不能有效处理在文档中的元素重复和元素可选问题。通过查看国内外相关内容的研究，p r a s a n n ag a n e s a n 等人【l2 j 提出了一种基于树路径的x m l 文档描述模型，并给出了相应的相似度算法，将问题有效地简化。本文分析此技术后，在第一步工作对x m l 文档的一阶段聚类的基础上，第二步针对原模型忽略同父兄弟节点之间的关系和用树路径的完全匹配来比较两条路径的相似度的不足，提出了改进的树路径方法模型，并解决了树路径所出现的一些问题，同时考虑到了兄弟节点之间关系和树路径相似度计算时的重复匹配问题，简化了文档描述，从而降低了解决聚类问题的复杂度，使x m l文档的聚类效果更佳。综上，t p c m 方法先将大量的x m l 文档集合利用x s l t 简化文档结构树，并利用树结构向量空间模型的方法进行第一阶段聚类，然后在x m l 文档类别数较少和不同类别的文档的结构相差较大基础上，利用改进后的树路径模型和相应的相似度计算方法，考虑兄弟节点之间关系和树路径重复匹配问题，在各个文档类中又分别进行了第二阶段聚类。实验结果显示，t p c m 方法包含了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 s l t 简化x m l 文档结构树，把x m l 文档结构向量化表示后进行第一阶段聚类。第四章基于树路径模型的x m l 文档结构聚类研究。分析树路径模型，提出改进的树路径相似度计算方法，考虑兄弟节点之间关系和树路径重复匹配问4第一章引言题，在第一阶段聚类的基础上，再进行第二阶段聚类。第五章是研究方法的设计实现和性能分析。第六章总结与展望。总结全文，并对下一步的研究工作提出了建设性意见。5第二章x m l 文档挖掘的相关研究2 1 1x m l 概述第二章x m l 文档挖掘的相关研究第一节x m l 文档相关技术x m l 是由万维网协会( w 3 c ) 设计特别为w e b 应用服务的s g m l ( s t a n d a r dg e n e r a lm a r k u pl a n g u a g e ) 的一个重要分支。“x m l 是s g m l 的子集，其目标是允许普通的s g m l 在w e b 上以目前h i m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本标记语言) 的方式被服务、接收和处理。x m l 被设计成易于实现且可在s g m l和h t m l 之间互相操作。 【l3 jx m l 是一种自描述的、半结构化的和可扩展的中介标示语言( m e t a m a r k u pl a n g u a g e ) ，它是用来自动描述信息的一种新的标准语言，并提供了一种独立的运行程序的方法来共享数据，而且能通过计算机通信把i n t e r n e t 的功能由信息传递扩展到各种活动中。2 1 2x l v i l 特点x m l 针对h t m l 的优点和缺点，将互联网上的文档规范化，赋予标记一定的含义，同时保留了h t m l 所具有的简洁、适于传输和浏览的优点，结合s g m l 和h t m l 的优势，现已经成为下一代互联网发展的核心。x m l 具备以下一些特点：1 、可扩展性：x m l 提供了一个表示信息的框架。它允许信息提供者根据自己的需求和意愿定义任意的标记，数据经过x m l 的处理之后，表达方式简单易读，同时也易于由其他应用进行进一步的加工和处理。在实际应用中，企业可以用x m l 为电子商务和供应链集成等应用定义自己的标记语言，甚至某些领域的特定行业一起来定义该领域的特殊标记语言，作为该领域信息共享与数据交换的基础。对于不同的领域，行业者们还可以根据本行业的不同需求来定义自己所需的标记。2 、结构性：数据存储格式一般包括三个要素：数据、结构以及显示方式。6第二章x m l 文档挖掘的相关研究x m l 提供了一种结构化的数据表示方式，使得用户界面分离于结构化数据。x m l 使用d t d ( 或x m ls c h e m a ) 规定一套关于标记符号的语法、语义规则，比较准确地描述文件资料的内容、含义、结构、特征和关系等信息。即使不同组中的人也可以使用共同的d t d ( 或x m ls c h e m a ) 来交换数据，还可以使用这个标准的d t d ( 或x m ls c h e m a ) 来验证接收的数据是否有效。x m l 将文档的显示形式交给样式表( 如c s s ，x s l 等) 处理，把信息的内容和表现形式合理地隔开，大大提高了x m l 信息的可理解性、可交换性和重用性。3 、平台独立性：x m l 具有跨平台的优点，不是二进制的数据格式，仅使用普通文本。利用x m l 可以有效地解决新旧系统平台、不同应用系统平台之间或者不同数据源之间的数据共享与交互问题。4 、自描述性和开放性：x m l 文档一般开始时要有一个文档类型声明，具有自描述性质，它使x m l 文档被人看明白和被计算机处理。x m l 文档通过用显示语句和隐式嵌套结构来描述结构化信息，使x m l 中的数据能被任何应用方便地访问并清楚地了解到标记内容的含义。x m l 的自描述性特点非常适用于不同应用间的数据交换。经过众多业界顶尖公司与w 3 c 的工作群组的并肩合作，标准技术被验证，x m l 具备了很强的开放性，并针对网络做了最佳化处理。5 、灵活性：x m l 文档在数据、数据结构与文档的表现方式上是分离的，这点与h t m l 的组织方式完全不同，结构化的数据通过可扩展的样式表x s l将数据呈现在不同的终端设备上，通过使用不同的x s l 模板可以将数据方便地呈现在各种不同系统的浏览器上。6 、规范性和简单性：x m l 源于标准通用标记语言s g m l ，保留了s g m l的8 0 的功能，而复杂性只有它的2 0 。x m l 文档有一套严谨而简洁的语法结构，这是x m l 解析器获取文档所含信息的前提条件。x m l 的标准国际化，规范性好，几乎支持世界上所有的主要语言，应用x m l 的软件都能处理这些语言的任何组合。正是x m l 以上的特点决定了它具有良好的数据存储格式、可扩展性、高度结构化、便于网络传输等优势，使它在许多领域被广泛使用。它便于网页信息组织，不仅能满足不断增长的网络应用需求，而且还能够确保在与网络进行交互时，具有良好的可靠性与互操作性。其卓越的性能表现，将使x m l 成为数据表示的一个开放标准，能够标记更多的信息，使用户很轻松地找到他们需7第二章x m l 文档挖掘的相关研究要的信息。这种数据表示独立于机器平台、供应商以及编程语言，它将为网络计算注入新的活力，并为信息技术带来新的机遇。因此，基于x m l 的知识表示应用日益广泛并在未来有着更加重要的应用。2 1 3x m l 文档的结构x m l 文档是由标记和文本数据组成，标记是由x m l 标记语言所定义的标记，而文本数据是符合x m l 规范的文本，也就是原始的文本。下面介绍一个x m l 文档最基本的构成例子( 一个有关专有名词解释的x m l 文件1 卅) ： x m l x m l 是一种可扩展的源置标语言，它可用以规定新的置标规则，并根据这个规则组织数据 ! c d a t a 张三 z h a n g a a a c o m 】1 、x m l 声明x m l 声明是处理指令的一种，用于为”v e r s i o n 属性( 指明所采用的x m l版本号) 、”s t a n d a l o n e ”属性( 表明x m l 文档是否与个外部文档类型定义相关联) 和“e n c o d i n g ”属性( 指明x m l 文档所采用的编码标准) 赋值。8第二章x m l 文档挖掘的相关研究2 、处理指令处理指令为处理x m l 文档的应用程序提供信息。x m l 解析器不处理这些指令，而将它们原样传给应用程序。应用程序解释这些指令，按照它们提供的信息进行处理。3 、x m l 元素元素是x m l 文档的基本单元。一个元素代表文档中一个逻辑组件。元素可以互相嵌套，形成树形结构。一个元素包含一个起始标记、一个结束标记和标记之间的数据内容，标记是x m l 文档的重要组成部分。引入c d a t a 数据块，是为了组织数据更加方便、清晰，其中所有的内容都可看作字符数据。此外，加入一些用作解释的字符数据，x m l 处理器不对它们作任何处理。这种类型的文本称作注释文本。2 1 4x m ld t d 和x m ls c h e m a2 1 4 1d i d在x m l 中，文档类型定义( d t d ) 【1 4 】提供语法规定，采用一系列正则式给各个语言要素赋予一定的顺序，用来定义文档所具有的逻辑结构。d t d 语法分析将这些正则式与x m l 文件内部的数据模式相匹配，从而判别一个文件是否有效。内部d t d ：在x m l 文件的序言部分加入一个d t d 描述，加入的位置是在x m l 处理指示之后，如下所示：文件体外部d t d ：一批文件可定义一个相同的d t d 外部d t d ，可方便高效地被多个x m l 文件所共享。如：( 此处采用绝对路径，或采用相对路径 )9第二章x m l 文档挖掘的相关研究公用d t d ：使用关键字p u b l i c 来引用由权威机构制定的公用d t d ，如：2 1 4 2s c h e m a由于d t d 并不能完全满足x m l 自动化的处理要求，所以w 3 c 于2 0 0 1 年5 月正式推荐x m ls c h e m a t l 5 。1 7 】为x m l 的标准模式。s c h e m a 将d t d 重新使用x m l 语言规范来定义，充分体现了自描述性的优点。特点如下：一致性：书写方式与x m l 文件书写方式一样。扩展性：s c h e m a 引入了数据类型。易用性：d o m 和s a x 可以访问。规范性：s c h e m a 利用元素的内容和属性来定义x m l 文档的整体结构。互换性：用户可以设计自己的s c h e m a ，并可交换。不同的s c h e m a 可以进行转换，以实现更高层次的数据交换。2 1 5d o m 和s a x2 1 5 1d o mw 3 c 于1 9 9 8 年1 0 月提出了文档对象模型 1 4 d o m ( d o c u m e n to b j e c tm o d e l ) ，d o m 是访问和维护h t m l 和x m l 文档的应用程序接u 1 ( a p i ) ，定义了文档的逻辑结构以及存取和维护文档的方法。通过这个a p i ，w e b 应用程序可任意访问和更改h t m l 和x m l 文档中的数据。d o m 通常把x m l 或者h t m l 文档表示为树状结构，提供了一个标准接口用来表示x m l 文档和h t m l 文档的一组标准对象以及存取和操纵它们。下图显示的是与前文中x m l 文档对应的树形结构。1 0第二章x m l 文档挖掘的相关研究图2 1 专有名词列表x m l 文档的d o m 树2 1 5 2s a xd o m 方法是读取整个文件并将该文件存储在一个树结构中，但这样可能低效、缓慢、消耗资源。因此，x m l d e v 邮件列表的成员开发出一种替代技术就是s a x ( s i m p l ea p if o rx m l ) 。s a x 是一种事件( e v e n t ) 驱动的接口，用基于事件的方式来处理x m l 文档，避免构造完整的文档树状结构，解析器在进入或离开文档、元素、属性、子树时产生s a x 事件。该模型可在不关注文档完整结构的情况下测定其特征或相关数据。用x m l 语法分析器读取并解释x m l 文档，每当它识别出文档中的某些内容，就会生成一个事件。这些事件共同向应用程序描述了文档树。语法分析器传递足够信息来构建x m l 文档树，但是与d o m 解析器不同，是显式地构建树。2 1 6x s l可扩展样式单语言x s l ，它也是由w 3 c 制定的。x s l 是通过x m l 进行定义的，遵守x m l 的语法规则，是x m l 的一种具体应用。这也就是说，x s l1 1第二章x m l 文档挖掘的相关研究本身就是一个x m l 文档，系统可以使用同一个x m l 解释器对x m l 文档及其相关的x s l 文档进行解释处理【l4 1 。x m l 文档本身并没有关于格式方面的信息，它需要专门的样式表为x m l 文档提供格式信息，专门描述结构文档的显示方式、字体、大小等。x s l 组成有两部分：一是描述如何将一个x m l 文档转换为可浏览或可输出的格式；二是定义格式对象f o ( f o r m a t t e do b j e c t ) ，在输出时，根据x m l 文档构造源树，再根据给定的x s l 将这个源树转换为可以显示的结果树，最后按照f o 解释结果树，产生一个可以在屏幕上、纸上或其他媒体中输出的结果。曰曰圄回一一一一一一一一。图2 2 x s l t 的工作流程结果树源树目前，描述树转换的这一部分协议日趋成熟，已从x s l 中分离出来，取名x s l t ( x s l t r a n s f o r m a t i o n s ) ，其正式推荐标准于1 9 9 9 年1 1 月推出。1 2第二章x m l 文档挖掘的相关研究2 1 7x p a t hx p a t h 1 8 1 即为x m l 路径语言( x m lp a t hl a n g u a g e ) ，它是一种对x m l 文档的内容进行定位、检索的语言，是后续更强大的数据检索语言如x q u e t y 的基础。x p a t h 是在x m l 文档的层次结构中使用路径标记，提供选择节点子集的简单语法，识别x m l 文档的某个部分，还提供了操纵字符串、数字和布尔值的函数。x p a t h 不独立使用，主要嵌入在x s l t ，d o m 等宿主语言中应用，比如，在x s l t 的应用中，x p a t h 用在模板( ct e m p l a t e ) 中来检索数据以及定义匹配模式( p a t t o n ) 。2 2 1 数据挖掘综述第二节x m l 文档挖掘技术数据挖掘【1 9 】是一类深层次的数据分析方法，被认为是解决“数据爆炸知识贫乏”的有效方法之一，是从静态的存储于大型数据库中的结构化数据中提取人们感兴趣的数据模式、内在联系、规律、发展趋势等知识。而更广泛的说法是：数据挖掘是在一些事实或观察数据的集合中寻找模式的决策支持过程，数据挖掘的对象不仅是数据库，也可以是文件系统，或其他任何组织在一起的数据集厶口。从技术上讲，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。从广义上理解，数据、信息是知识的表现形式，更把概念、规则、模式、规律和约束等看作知识。关系数据库中的数据是结构化的，文本、图形和图像数据是半结构化的，还有分布在网络上的异构型数据。因此，数据挖掘更是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持，在这种需求下，形成新的技术热点。数据挖掘通过预测未来趋势及行为，做出前瞻的、基于知识的决策。数据挖掘主要有以下五类技术。自动预测趋势和行为，关联分析，聚类分析，概念描述，偏差检测。1 3第二章x m l 文档挖掘的相关研究2 2 2x m l 文档挖掘分类根据x m l 文档的特点，当前x m l 挖掘的研究可以分为结构挖掘和内容挖掘两类。结构挖掘是指将每一个x m l 文档的结构看作是一棵有根、有序的标记树，在此基础上对树的挖掘。x m l 的内容指的是文档中每个开始标记和结束标记之间的文本部分，对其内容的挖掘其实也就是对标记的值的挖掘。挖掘分类图如下：图2 3x m l 挖掘分类2 2 2 1 内容挖掘x m l 内容挖掘传承于一些面向文本挖掘和分析的问题。同义和歧义能引起困难，但是在内容周围的标记可以有助于解决不明确的问题。目前，x m l 的内容挖掘有三种主要方法：一是开发一些x m l 数据或半结构化数据的查询语言，利用其查询功能，嵌入到其他应用程序中，从而获得数据集进行挖掘。优点是能够将x m l 技术与数据挖掘技术紧密结合起来，缺点是修改困难、查询开销巨大等。二是将x m l 文档的数据结构化，映射到现有的关系模型或对象模型中，使用较成熟的数据挖掘方法进行挖掘。缺点是x m l 本身的一些半结构化特点可能会导致在映射过程中产生一些问题。三是将x m l 文档看作一个文本，进而使用传统文本挖掘技术进行挖掘。例如：基于向量空间模型( v s m ) ，将文档空间看作由一组正交词条向量所组成的向量空间，通过统计词频、缩减维数等步骤，达到机器学习、获得知识的目的。缺点是没考虑x m l 文档存在结构化的特征，而且数据量大、数据过于】4第二章x m l 文档挖掘的相关研究详细导致文档的特征向量巨大，造成挖掘困难。内容的挖掘技术主要有：在x m l 文档中的应用分类，把新的x m l 文档内容做标识作为预先确定的类的属性。来减少先前和现在s c h e m a 类的数目。在x m l 内容中聚类方法与新的分类方法一样具有潜力。此外，相似的s c h e m a 更可能有一定数量的值集。结构化分类是基于内容区分相似的结构文档，与结构有关。内容对相似s c h e m a 轮流聚类提供支持。例如：两个有截然不同结构的s c h e m a 可以有同样内容的文档实例，两个有截然不同内容的x m l 文档若他们的s c h e m a s 相似也可以聚类在一起。2 2 2 2 结构挖掘x m l 结构挖掘的本质是d t d 或s c h e m a 的挖掘，包括内部结构挖掘和相互之间结构的挖掘。结构内挖掘是对一个x m l 文档内的结构进行挖掘以发现隐藏在结构内的知识，也就是对d t d 或s c h e m a 的挖掘。方法如下( 以d t d 为例说明) ：分类：d t d 可以用来对x m l 文档的类别进行描述，根据预定义的分类对新x m l 文档进行归类。过程是先收集d t d 文档作为训练集，然后根据训练集对新文档进行分类。聚类：用来识别各种x m l 文档间的相似性。聚类算法收集d t d 并根据自身的相似性进行组合，然后把这些相似性生成新d t d ，即是d t d 训练集的超类。关联规则挖掘：用来描述共同在x m l 文档中出现的标记间的关系。x m l文档可分析为树形结构，它的d t d 也是树形结构。把树形结构的x m l 结构转化为以“事务 为单位的对象，就可以利用已有的数据挖掘关联规则方法挖掘出一些有意义的规则。目前，国内外相关研究有基于概念层次的x m l 文档关联规则挖掘 2 0 】，在此方法中，借鉴h a r tj i aw d 的a o i ( a t t r i b u t eo r i e n t e di n d u c t i o n ) 1 9 】挖掘方法，在x m l 文档挖掘中引入概念层次，提出一种新的面向x m l 文档的关联规则挖掘方法。通过引入概念层次，可以对数据进行概化，压缩x m l 文档的大小，而且使挖掘出来的规则知识更容易理解。1 5第二章x m l 文档挖掘的相关研究结构间挖掘是挖掘x m l 文档之间的结构中的知识，这些知识包括主题、组织方式及节点之间的关系。它可以用于：分类：被应用到命名空间和u r i ，根据关联的d t d ，用来对新x m l 文档进行分类。分类方法是应用用名称空间和u r i s 。具有详细名称空间和u r i 的先前的联合的s c h e m a 集，这些信息是用来分类源自这些地方的新的x m l 文档。聚类：这种方法可以用来进行不同x m l 文档之间的相似度验证。通过聚类算法把一个d t d 的集合根据相互相似度的特征聚合，再在这个通过相似度聚合子集的基础上产生新的泛化的d t d ，这个新的d t d 成为这个d t d 聚合子集的父类，也就是对聚类子集中所有d t d 的泛化。聚类s c h e m a 包括标识相近的s c h e m a ，这些簇被用来定义s c h e m a 的层次。2 2 2 3x m l 文档结构挖掘方法x m l 结构挖掘是对x m l 文档d t d 或s c h e m a 的挖掘，x m l 文档的结构化处理可分3 个步骤：1 、对x m l 文档进行结构的定义，即定义d t d 或s c h e m a ；2 、针对具体某类x m l 文档，制定结构单元提取规则；3 、进行x m l 文档结构化的转换。在x m l 标准中，d t d 是一系列对元素类型、属性、实体和注释的定义，x m l 文档通过定义d t d 来定义一类文档的结构。d t d 产生器对一个给出的x m l 文档生成d t d ，可是d t d 产生器为每个x m l 文档生成截然不同的d t d ，在不同种类和灵活多变的应用中，假定x m l 文档有相同的文档结构是不合理的，因此数据挖掘是困难的。由于应用d t d 作为内部结构有大量的局限性如：限制的数据类型，松散的约束结构，原文内容的局限性，一些研究者提出把x m ls c h e m a 的提取作为x m l d t d 的扩展的建议。如：基于在有规则公式范围内的上下文文法扩展的x m ls c h e m a 提取算法，基于网络语义传达x m l 文档的层次数据结构携带的语义，并转换成一个x m ls c h e m a ，这些算法都非常复杂。一个有语法和文档结构定义的有效文档存在s c h e m a 机制，对良好格式或有效文档进行结构挖掘是简单的。x m l 文档可能不总是有伴随的s c h e m a ，具有良好格式的x m l 文档并不要求都存在s c h e m a 。为描述x m l 文档的语义结构，良好格式的x m l 文档需要用s c h e m a 提取工具来产生s c h e m a 。一般情况下，从不良格式的x m l 文档中进行结构挖掘，是通过应用结构1 6第二章x m l 文档挖掘的相关研究提取途径来进行的，但并不是所有的技术能有效的支持从x m l 文档中利用更好的数据挖掘算法进行结构提取。下面介绍x m l 文档聚类挖掘算法。第三节x m l 文档聚类技术研究目前，国内外部分研究成果以x m l 文档挖掘为应用背景，充分发挥传统数据挖掘中成熟丰富的技术