（计算机应用技术专业论文）基于加权层次子树的xml文档相似度计算.pdf

摘要 近几年来，随着社会信息化进程的不断深入发展，人类对信息的需求和依赖 程度越来越高，如何从海量的信息资源中快速有效的获取有用的信息，己经成为 研究的热点，这也给信息检索带来了极大的挑战。随着互联网的发展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 文档相似度的影响也就越小。权重系数以 2 的次幂逐层递增。这样计算出来的相似度就会更精确。为了验证基于该模型的 相似度计算效果，本文采用了k 中心点算法进行聚类分析，实验结果表明，基 于这种模型的相似度计算方法要优于树编辑距离和频繁路径等相似度计算方法 得到的效果。 关键词：x m l 加权层次子树模型文档结构相似度文档聚类 a b s t r a c t i nr e c e n ty e a r s ，a l o n gw i t hi n f o r m a t i o n b a s e ds o c i e t yi nt h ep r o c e s so ff u r t h e r d e v e l o p m e n t ，i n f o r m a t i o n o nh u m a nn e e d sa n dd e p e n d e n to nb e c o m eh i g h e r i n c r e a s i n g l y , h o wt oa c c e s su s e f u li n f o r m a t i o nf r o mt h em a s so fi n f o r m a t i o nr e s o u r c e s q u i c k l ya n de f f i c i e n t l yh a sb e e nb e c o m eah o tr e s e a r c h ，t h i si st or e t r i e v ei n f o r m a t i o n p o s e dag r e a tc h a l l e n g e w i t ht h ed e v e l o p m e n to ft h ei n t e r n e t ，x m lw i t hi t so w n s t r u c t u r eo ft h es c a l a b i l i t yo fs e l f - d e s c r i p t i o no ft h ec h a r a c t e r i s t i c so ft h ei n t e r n e th a s b e c o m ead a t as t o r a g ea n dd a t ae x c h a n g es t a n d a r d s t h ec a l c u l a t i o no fs i m i l a r i t yi st h ef o u n d a t i o no ft h ed o c u m e n tr e t r i e v a l ，m i n i n g a n dd e e p s e a t e di n t e l l i g e n c et od e a lw i t h ，s ot h ec a l c u l a t i o no fs i m i l a r i t yt ot h es t u d y b e i n go fg r e a ts i g n i f i c a n c e ，i tc a nb es a i do ft h es i m i l a r i t yo ft h ed o c u m e n t sh a da d i r e c ti m p a c to nt h ec a l c u l a t i o no ft h ef i n a lr e s u l t so ft h es e a r c h o no n eh a n d ，i ft h e s i m i l a r i t yo ft h ed o c u m e n tt h es t r u c t u r eo fh i g h - p e r f o r m a n c ec o m p u t i n ga c c u r a t e ， t h e nt h es e a r c hr e s u l t sw i l lb ea b l et om e e tt h eu s e r se x p e c t a t i o n s o nt h eo t h e rh a n d ， i ft h ed o c u m e n t ss i m i l a r i t yc a l c u l a t i o n sa r ei n a c c u r a t e ，t h ei n q u i r yp r o c e s so fr e c a l l a n dp r e c i s i o nw i l lb eg r e a t l ya f f e c t e d ，a n dt h ef i n a lu s e r sw i l lw a n tt os e et h e i rs e a r c h r e s u l t s w i t hx m l l a n g u a g eh a sb e e nw i d e l yw e l c o m e da n ds u p p o r tb yt h ei n d u s t r y ，a g r o w i n gn u m b e ro fa p p l i c a t i o n sh a sb e e nm a i n l ya sas t o r a g ef o r m a ta n dt r a n s m i s s i o n m e d i a t h e r e f o r e ，h o wt oc a l c u l a t et h es i m i l a r i t yo fx m ld o c u m e n t sp a r t i c u l a r l yi n i t ss t r u c t u r ei st h em a i nt a s k so ft h er e c e n t l ys t u d y b yt h eo n g o i n gr e s e a r c ho nt h ex m ld o c u m e n t s ，i ti sf o u n dt h a tt h ef o r mo f x m l d a t a ( r e p r e s e n t a t i o n a lm o d e l ) t ot h ex m l d a t ap r o c e s s i n gh a sa ni m p o r t a n tr o l e a n di m p a c t w h e nt h et r e eu s e dt oc a l c u l a t et h ed i s t a n c et oe d i tt h ed o c u m e n t s i m i l a r i t y , i ft h et r e et od e s c r i b et h es t r u c t u r eo fa l lt h ei n f o r m a t i o n t h es t r u c t u r eo ft h e t r e ew i l lb eav e r yl a r g e t h em e t h o do ft r e ee d i td i s t a n tc a nn o tb ee f f e c t i v e l yd e a l t w i t ht h ep r o b l e mo fr e p e a te l e m e n t sa n do p t i o n a le l e m e n t s ，s oi ti sd i f f i c u l tt od e a l w i t h ，a n dm o r ei m p o r t a n t l y , i t sag r e a tt i m ec o m p l e x i t yt od e a lw i t hb yt h el o w e r e f f i c i e n c ya n di n c r e a s i n gs p e n d i n gt i m e ；t h em o d e lo ft h ef r e q u e n t l y p a t hi s e x p r e s s e di nas i m p l ef o r m ，b u tt h ei n f o r m a t i o nw h i c h i to u t b r e a ki sn o ts oc o m p l e t e a st r e e - s t r u c t u r e d ，i ti sj u s tt h es i m i l a rt oar e f l e c t i o no ft h es t r u c t u r eo fx m l d o c u m e n t s ，a sam o d e lf o ri t sc l u s t e ra n dt h ea c c u r a c yi sn o th i g h t os y n t h e s i z et h ea b o v e - m e n t i o n e da d v a n t a g e sa n dd i s a d v a n t a g e so fm o d e l ，i n t h i sp a p e r ，w eb r i n gu pas t r u c t u r eo fx m ld o c u m e n t so ft h ec l u s t e rm o d e l - t h e w e i g h t e d l e v e ls u b - t r e em o d e l ，b r i n g i n gu p ad o c u m e n ts i m i l a r i t yc a l c u l a t i o nm e t h o d b a s e do nt h ew e i g h t e d - l e v e ls u b t r e em o d e la n dc a r t i n go u tac l u s t e ra n a l y s i s t h i s s i m i l a r i t yc a l c u l a t i o nm e t h o dc a ne f f e c t i v e l ys i m p l i f yt h ep r o b l e m ，w h i c hr e d u c e st h e c o m p l e x i t yo ft h ep r o b l e m s o l v i n g t h i sa l g o r i t h mc a nq u i c k l ya n da c c u r a t e l y i d e n t i f i e dw i t ht h es a m es t r u c t u r eo fx m ld o c u m e n t s t h i sa r t i c l et a k e si n t oa c c o u n t i n f o r m a t i o no nt h es e m a n t i cs i m i l a r i t ye l e m e n t s ，t h eh i e r a r c h yo fi n f o r m a t i o na n d w e i g h ti n f o r m a t i o n o nt h es i m i l a r i t y , a n du s et h ek - c e n t e rc l u s t e ra n a l y s i s a l g o r i t h m ，w i t ht h er e s u l t ss h o wt h a tt h em e t h o dh a sag o o dc l u s t e r i n ge f f e c t k e y w o r d s ：x m l t h ew e i g h t e d - l e v e ls u b t r e em o d e ls t r u c t u r es i m i l a r i t y x m l c l u s t e r i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞洼王些太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名： 签字r 期：彳年月冲f 1 学位论文版权使用授权书 本学位论文作者完全了解丞洼王些盍堂有关保留、使用学位论文的规 定。特授权丞洼王些盔堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意 学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 芒亨乏 v 签宁f 1 期： 卵年2 月髟r签字同期：c 哆年月约硐 学位论文的主要创新点 一、本文主要研究了基于加权层次子树模型的x m l 文档相似度计 算，在基于加权层次子树模型的x m l 文档的相似度计算中，将x m l 文档的元素语义信息纳入计算中，更加精确了相似度的计算。 二、在x m l 文档相似度计算中，考虑到了层次的权重问题，靠近 根节点层次上的节点比远离根节点层次上的节点占的比重要大，也就 是说在靠近根节点层次上的节点它的相似度要乘以一个大一些的权 重，每一层上的权重系数都不相同，层次越高，权重系数越大，它对 整个x m l 文档相似度的影响也就越大；反之，层次越低，权重系数 越小，它对整个x m l 文档相似度的影响也就越小。权重系数以2 的 次幂逐层递减。这样计算出来的相似度就会更精确。 第一章绪论 1 1 课题背景介绍 第一章绪论 随着信息技术和i n t e m e t 的不断发展与普及，信息化已经成为人类社会经济 发展的重要组成部分。i n t e m e t 已经作为获取、发布和传递信息的重要工具，网 络上的信息量呈几何级数增长，i n t e m e t 上约有3 5 亿个静态h t 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 ) 是w 3 c 组 织推荐的一种基于s g m l 的通用标记语言，x m l 具有s g m l 的强大功能和可 扩展性，同时又具有h t m l 的简单性，是w 3 c 最具有前瞻性和最有影响的标 准之一。x m l 凭借自描述性、可扩展性及半结构化等特点，逐渐成为数据表示 和数据交换的标准，在各个领域都得到了广泛的支持和应用。 随着x m l 文档的大量涌现，如何从海量x m l 文档中挖掘出有价值的信息， 成为企业和用户关心的问题。数据挖掘，这个传统的数据管理与数据分析方法， j 下逐步涉及x m l 数据领域。2 0 0 2 年，n a y a k 等人提出了x m l 文档知识发现的 概念比。x m l 文档数据挖掘涉及到x m l 、数据挖掘、机器学习、数据库、信 息检索等多个方面的知识与技术。常用的数据挖掘方法，如分类、聚类分析、 关联规则挖掘等都能够用于x m l 文档数据挖掘领域。x m l 分类挖掘的目的是， 天津t 业人学硕十学位论文 根据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 出现之前，已有许多工作研究了两棵树( 图) 间的相似测度的问题，其中最自 然和应用最广的测度是树的编辑距离。t a i h l 最早提出了利用编辑距离来度量两 棵树( 图) 间的差异。在t a i 的工作的基础上，z h a n g 和s h a s h a 曲叫等提出了计 算两棵树间的各种编辑距离的算法。 在x m l 文档的数据挖掘研究中，聚类挖掘是其中的热点研究领域，本文 研究的即为x m l 文档的聚类挖掘，根据x m l 文档的不同结构和语义特征，将 其划分为不同的数据类，使同类的文档之间尽可能相似，不同类的文档之间差 别尽可能大。以达到无指导学习的目的。 1 2 国内外研究现状 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 数据挖掘 通常被分为内容挖掘和结构挖掘两个方向。 伴随着x m l 数据挖掘研究的不断深入，基于x m l 文档结构的数据挖掘( 主 要是分类和聚类) 在很多方面得到了很好的应用。特别是近几年不断发展和广 为流行的x m l 数据库，以及i n t e m e t 上的信息检索和语义w e b ( 以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 结构挖掘和x m l 结构与内容挖掘川， 其中结构与内容挖掘的任务不再只是针对x m l 中的数据进行处理，而是综合 结构与数据两方面的信息，进而提取出人们关心或者有价值的内容知识。 在这个组织的领导和组织下，许多成熟的x m l 数据挖掘算法被提出，这 些算法有聚类挖掘也有分类挖掘，既有针对x m l 结构挖掘任务的，也有针对 x m l 结构与内容挖掘任务的。n a y a k 。在针对x m l 结构挖掘任务的聚类挖掘 方面进行研究；v e r c o u s t r e 。在针对x m l 结构与内容挖掘任务的聚类挖掘方面 进行研究；y o n g 0 1 在针对x m l 结构挖掘任务的分类挖掘方面进行研究；x i n g 。 在针对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 数据中可挖掘结构 3 天津i ：业人学硕十学位论文 繁多，因而至今缺乏一个统一的、抽象的模型去描述x m l 数据层次模型的挖 掘过程。 本文对x m l 文档的结构进行了研究，提高了结构模型及基于该结构模型 相似度计算的效率，从而提高了x m l 文档的聚类效果，本文提出了加权层次 子树模型，来描述x m l 文档的结构，并根据这种模型提出了相应的相似度计 算方法，这种模犁比以往的树型结构模型和频繁路径模型要简单，并且包含了 所有的父子节点关系，该模型简化了x m l 文档的描述，从而在很大程度上降 低了解决问题的复杂度和时问分析度。并体现了父节点在整个关系表达式中的 重要性，同时考虑到了节点的权重问题和文档的语义信息，精确的比较了两个 文档的相似度，解决了层次模型所出现的一些问题。 1 3 本文主要研究工作 随着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 文档中不重要的因素，比如， 文档中的属性、文本、注释等节点类型，主要考虑了元素节点。x m l 文档结构 模型要求结构简洁、表示信息完整、易于理解并便于操作，以便能为x m l 文 档聚类研究奠定良好的基础。所以提出了一种新的x m l 文档模型加权层 次子树模型。 2 、精简加权层次子树模型 我们在建立完模型后的第一步便是去重。x m l 文档中会有很多大量的重复 元素，这些重复元素会使我们的模型变得庞大而冗余，所以我们为了模型的处 4 第一章绪论 理效率要去除重复元素和重复的层次表达式，这样就会使我们得到一个简洁、 表达信息完整的结构表达模型，从而为计算相似度打下一个良好的基础。 3 、建立基于加权层次子树模型的x m l 文档相似度计算方法 x m l 文档的相似度计算方法根据表示模型的不同而有所区别，通常将表示 模型的相似度看作对应的x m l 文档的相似度，基于加权层次子树表达式模型， 定义了基于此模型的x m l 文档相似度计算方法，该计算方法将x m l 文档的文 本语义信息纳入计算中，由于考虑到了语义和结构的双重相似度，所以更加精 确了相似度的计算。本文中还考虑到了层次的权重，靠近根节点层次上的节点 比远离根节点层次上的节点占的比重要大，也就是说在靠近根节点层次上的节 点它的相似度要乘以一个大一些的权重，这样计算出来的相似度就会更精确。 4 、聚类分析 论文通过经典的聚类算法k - 中心点算法，对x m l 文档进行聚类分析。 1 4 本文组织结构 本论文的组织结构如下： 第一章介绍x m l 数据挖掘的研究背景，目前的研究热点，并介绍了本文 的主要研究工作。 第二章主要介绍了x m l 数据挖掘的基础知识，以及x m l 文档数据挖掘的 研究进展。 第三章介绍了x m l 、x m l 文档、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 文档的相似度。最后以实验晚明x m l 文档的聚类效果。 第六章对全文进行总结，并期望进一步的研究工作。 5 第二章数据挖掘技术 第二章x m l 数据挖掘技术 2 1 数据挖掘技术概述 2 1 1 数据挖掘的概念 随着互联网的普及、商业的发展，信息的争夺同益激烈，从浩瀚如烟的数据 中寻找出对我们有用的信息来是当务之急，并且迫切需要将这些数据转换成有用 的信息和知识，如何从数据的海洋中迅速、准确地挖掘出有价值和有指导意义的 信息已成为人们关注的焦点。于是，数据挖掘这f - j q ：科产生了。 数据挖掘( d a t am i n i n g ，d m ) 的定义：“数据挖掘是从大量的、不完全的、 有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的但又 是潜在有用的信息和知识的过程”u 引。“数据库的知识发现( k d d ) 是从数据 中发现有用的信息和模式的过程数据挖掘是指使用算法来抽取信息和模式， 是k d d 过程的一个步骤”。 这个定义包括几层含义： 1 、数据源必须是真实的、大量的、含噪声的； 2 、挖掘的是用户感兴趣的知识； 3 、挖掘的知识要可接受、可理解和可运用； 4 、不要求挖掘放之四海皆准的知识，仅支持特定的发现问题。 简单地说，数据挖掘是从存放在数据库、数据仓库或其它信息库中的大量数 据中挖掘有趣知识的过程。数据挖掘是新兴的一门交叉学科，它涉及了网络技术、 统计学、人工智能、信息检索、数据库和数据仓库等学科。 毫不夸张地说，如今的数据挖掘已经成为计算机、信息科学以及相关领域的 一个时髦名词。 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大 量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的 关键性数据。对数据挖掘的定义，不同的机构或个人有着不同的诊释。简单的说， 数据挖掘是从大量数据中提取或挖掘知识。还有一些术语，具有和数据挖掘类似 但稍有不同的含义，如数据库中知识挖掘、知识提取、数据模式分析、数据考 古和数掘捕捞。数据挖掘的本质是在庞大的数据库中寻找出有价值的隐藏事件， 加以分析，并将这些有意义的信息归纳成结构模式，作为企业在进行决策时的参 7 天津：l ：业人学硕+ 学位论文 考依据。 基于数据挖掘的广义观点，典型的数据挖掘系统应具有如下主要成分： 1 、数据库、数据仓库或其他信息库 这是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在 数据上进行数据清理和集成。 2 、数据库或数据仓库服务器 根据用户的数据挖掘请求，数据库或数据仓库服务器负责提取相关数据。 3 、知识库 这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知识可能包 括概念分层，用于将属性或属性值组织成不同的抽象层。用户确信方面的知识也 可以包含在内。可以使用这种知识，根据非期望性评估模式的兴趣度。 4 、数据挖掘引擎 这是数据挖掘系统基本的部分，由一组功能模块组成，用于特征化、关联、 分类、聚类分析以及演变和偏差分析。 5 、模式评估模块 通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以便将搜索聚焦在 有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。该模块也可与数据挖掘 模块集成在一起，这依赖于数据挖掘方法的实现。 6 、图形用户界面 本模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据挖 掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘的中问结果进行搜索式 数据挖掘。典型的数据挖掘系统结构见图2 1 。 2 1 2 数据挖掘的分类 数据挖掘是从数据中发现有用的、先前未知的和最终可理解的模式的过程。 不同的角度有不同的分类方法。根据挖掘任务的不同，数据挖掘可以分为分类和 预测、聚类、关联规则发现、序列模式发现、依赖关系和依赖模式发现等技术， 下面介绍几种常用的数据挖掘方法。 1 、分类( c l a s s i f i c a t i o n ) 分类就是给定一个由元组组成的数据库d 和一个类别集合c ，分类是指要 定义一个映射f ，使得d 中的每一个元组准确的分配到c 中。它的目的是使用一 个分类函数或者分类模型，将数据库、数据仓库或其它信息库中的数据项映射到 给定类别中的某一个类别中去。预测可以视为将一个元组分类到某个可能的类别 集合中。分类常应用于图像与模式的识别、医疗诊断、贷款审批、工业应用中的 8 第二章数据挖掘技术 故障以及金融市场趋势分类n 3 1 。 图2 - 1 数据挖掘系统结构 2 、聚类( c l u s t e r i n g ) 聚类与分类相似，都是将数据进行分组，但与分类不同的是，聚类中的组不 是预先定义的，而是根据实际数据的特征按照数据之间的相似性来定义的。 聚类主要是根据记录的特征将其划分为群或聚类，使得一个聚类中的记录相似， 但与其它聚类中的记录不相似。相似程度由记录的距离定义。聚类分析是数据挖 掘最重要的技术之一。常用的聚类技术有：划分技术、层次技术、基于密度的方 法、基于网格的方法和基于模型的方法。 3 、关联规则( a s s o c i a t i o n ) 关联规则是描述一个事物中对象同时出现的规律的知识模式。在大量记录中 9 天津：j ：业大学硕十学位论文 发现有趣的关联关系，通过量化的数值描述一个对象出现对另外一个对象出现有 多大的影响。 j = 1 1 , 1 2 ，i m ) 是一项目集，d 是一事务数据库，其中每个事务t c j 。每个事 务都有一个标识符，称之为n d 。若a 是一项目集，当且仅当a t 时，我们说 事务t 包含了a 。一条关联规则就是形如a 专b 的蕴含关系，其中a c j ，b c j 且a nb = m 。如果d 中包含aub 的比例是s ，就称关联规则a 寺b 在d 中的 支持度为s ，也可以表示为概率p ( a u b ) ；如果d 中包含a 的同时也包含b 的 比例是c ，则说关联规则a 号b 的置信度为c ，表示为条件概率p ( bia ) 。就是 13 i s u p p o r t ( a j b ) = p ( a ub ) c o n f i d e n c e ( a 辛b ) = p ( bia ) 4 、序列模式( s e q u e n c ea n a l y s i sa n dt i m es e q u e n c e ) 序列模式分析也是为了挖掘数据间的联系，与关联规则分析法类似。但序列 模式分析更侧重于分析数据间的因果关系。 5 、复杂系统的数据挖掘 随着数据挖掘技术的广泛应用，新的数据挖掘领域层出不穷，如空间数据挖 掘技术、多媒体数据挖掘技术、时序数据和序列数据的挖掘、w e b 数据挖掘。其 中，由于i n t e m e t 发展相当迅速，信息数据更新很快，w e b 挖掘成为数据挖掘的 前沿领域。 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 所示。 x m l 内容挖掘是对文档中包含在元素开始标签和结束标签之间的文本进行 挖掘，可以分为文档内容分析与文档结构分类。文档内容挖掘的方法与传统的数 据方法类似，可以转换为传统的关系型数据的挖掘。而结构挖掘以x m l 文档结 构为挖掘对象，是从x m l 文档的结构中发现有价值知识的过程。文档的结构信 息通过有根、有序的标签树表示，其中的标签对应于x m l 文档的t a g 。x m l 结 1 0 第二章数据挖掘技术 构挖掘首先将x m l 文档转换为某种结构模型，然后对结构模型进行数据挖掘分 析，得到挖掘结果。在实际应用中，结构挖掘与内容挖掘并非没有交集。有些模 型可以综合考虑结构信息与内容信息。 图2 - 2x m l 数据挖掘分类方式 x m l 数据挖掘方法主要有分类、聚类和关联规则。分类与聚类是目自i 较常 用到的技术，其上的研究成果也最为显著。i n e x ( 1 n i t i a t i v ef o rt 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 文档数据挖掘。 i n e x 2 0 0 5 针对结构挖掘与结构内容挖掘，而2 0 0 6 更着重于结构内容挖掘。 分类挖掘的目标是能够区分来源于不同数据源的数据，而聚类挖掘是为了发现隐 藏在数据源中的信息。 d o u c e t 3 、h a g e n b u c h n e r 、n a y a k 、d ek n i j f t 6 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 np a t hs i m i l a r i t y ，频 繁路径相似度) 来衡量一篇x m l 文档与一个x m l 文档聚类( 集合) 之间的相 似度；d ek n i j f 提出一种基于频繁属性树模型的x m l 文档分类算法。而上述四 种模型则是目前x m l 文档结构挖掘的常用模型。 天津l ：业人学硕+ 学位论文 分类和聚类是x m l 数据挖掘最常用的技术，x m l 文档间的相似度描述 x m l 文档问的近似程度，是分类与聚类分析的基础。目前相似度计算的研究进 展将相似度计算分成了结构级( s t r u c t u r e 1 e v e l ) 与元素级( e l e m e n t l e v e l ) 两大 类。 结构级的相似度计算有三个研究方向：文档问的结构和内容相似度，可细分 为文档聚类、文档更新检测，文档的相似度查询及频繁树查询；文档与模式间的 相似度计算；以及从文档中抽取模式信息。 结构级的相似度计算方法将树的整体结构看作比较的重要因素，而将语义看 作决定相似度的非重要因素，而元素级的相似度计算多指模式的匹配，其更注重 语义信息，模式相似度匹配也分为三个研究方向：实例级的模式相似度匹配；模 式级的模式相似度匹配；以及实例与模式混合的模式相似度匹配，与上述两种相 比较，实例与模式混合的模式相似度匹配结果更准确。 2 3x m l 数据挖掘的应用现状 数据挖掘是一个多学科领域，涉及数据库技术、统计学、机器学习、信息科 学、人工智能和神经网络等多方面的知识，依赖于所用的数据挖掘方法，以及可 以使用的其他学科的技术，如神经网络、模糊或粗糙集理论、知识表示、归纳逻 辑程序设计或高性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应用，数 据挖掘系统也可能集成空问数据分析、信息检索、模式、识别、图象分析、信号 处理、计算机图形学、经济、商业、生物信息学或心理学领域技术。 x m l 数据挖掘从一丌始就是面向应用的，作为一门新兴技术，它已经被应 用于生物医学和d n 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 数据挖掘的应用是对这些方法的拓 展和深化。 1 2 第二章数据挖掘技术 x m l 数据挖掘的应用领域非常广泛，国外的数据挖掘研究和应用已经取得 了一定的成果，很多企业充分利用数据挖掘技术为自身创造了巨大的商业价值。 数据挖掘的工具也已经大量出现，一类是基于统计