（计算机应用技术专业论文）面向xml文档的数据挖掘技术研究 (2).pdf

大连理j ：大学硕士学位论文 摘要 数据挖掘是指从大量的、不完全的、有噪声的、模糊的数据中提取出隐含在其中 的、人们事先不知道的但又潜在有用的知识的半自动化的方法，它是解决“数据丰富、 信息贫乏”的有效方法。近十年来，数据挖掘在理论与实践上都得到了广泛研究，并被 应用于商业、工业及自然科学等各个领域。 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 ，可扩展标记语言) 是由s g m l 发展而来的一种简 单、灵活的文本格式，最初是为了适应大规模电子出版的需要而开发出来的，如今，它 以其可扩展、平台独立、灵活、规范、简单等特点以及强大的数据表达能力，在网络及 其他领域的数据表示与交换方面扮演一个越来越重要的角色。越来越多的数据以l 文 档进行存储，在这些数据中隐含着大量的知识信息与各类模式，因此，人们迫切需要一 些有效的方法来从中提取出一些潜在的、有价值的知识，这就是x m l 挖掘。 但是，作为一种树形的半结构化数据，x m l 非- 常复杂且具有异构性，它不能轻易 地被映射到关系模型，这样，传统的面向关系型数据的挖掘方法如a p f i o r i 算法等，并不 能直接应用到m ，挖掘上。因此，开发出有效的针对“l 的数据挖掘方法成为数据挖 掘领域* i i x m l 技术领域的一项重要课题。 基于以上分析，本文首先介绍了传统的数据挖掘技术、x m l 的基本理论及x m l 的特征，然后将x m l 文档作为一棵标记树进行研究，借鉴传统数据挖掘中特征提取的 方法，提出了一种新的基于概念层次的x m l 文档关联规则挖掘方法。实验表明，本文 的方法能够有效地从x m l 文档中抽取出关联规则。 关键词：数据挖掘；x l _ l _ ；关联规则；概念层次 面向x m l 文档的数据挖掘技术研究 r e s e a r c ho fd a t a m i n i n gt e c h n i q u e s f o rx m ld o c u m e n t s a b s t r a c t d a t am i n i n gi san o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u ! ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a a e m s i nd a t a i ti sae f f i c i e n tm e t h o df o rr e s o l v i n gt h ep r o b l e mo f “d a t ar i c h - i n f o r m a t i o np o o l f o rt h el a s td e c a d e s ，d a t am i n i n gi se x t e n s i v e l ys t u d i e di nt h e o r y a n d p r a c t i c e ，a n da p p l m d t ov a r i o u sf i e l d ss u c ha sb u s i n e s s , i n d u s t r y ，a n dn a t u r a ls c i e n c e s x m i ( e x t e n s i b l em a r k u pl a n g u a g e ) i sas i m p l e ，v e r yf l e x i b l et e x t f o r m a td e r i v e df r o m s g m l o r i g i n a l l yd e s i g n e d t om e e tt h e c h a l l e n g e s o fl a r g e s c a l ee l e c t r o n i c p u b l i s h i n g ， n o w a d a y s ，x m l i sp l a y i n ga l li n c r e a s i n g l yi m p o r t a n tr o l ei nt h ee x c h a n g ea n dr e p r e s e n to fa w i d e v a r i e t yo f d a t a o nt h ew e ba n de l s e w h e r ed u e t oi t se x p a n s i b i l i t y ，p l a t f o r m - i n d e p e n d e n c e , f l e x i b i l i t y ，s i m p l e n e s s ，s t a n d a r d i z a t i o na n dp o w e r f u la b i l i t yf o rr e p r e s e n t i n gd a t a h e n c e ，t h e r e h a v eb e e ni n c r e a s i n gd e m a n d sf o re f f i c i e n tm e t h o d st h a te x t r a c tr u l e sa n dp a t t e r n sf r o mx m l d a t a , n a m e l yx m l d a t am i n i n g h o w e v e r ，a sas e m i s t r u c t u r e dd a t a , x m ld a t aa r e ah u g ea m o u n to fc o m p l e xa n d h e t e r o g e n e o u sd a t a m o d e l e d b yt r e e s ，a n dc a n n o tb ee a s i l ym a p p e d i n t oar e l a t i o n a lf r a m e w o r k t h u s ，w ec a n n o td i r e c t l ya p p l yt ox m l d a t ai r a d i t i o n a ld a t am i n i n gm e t h o d sf o rr e l a t i o n a l d a t a b a s e s ，s u c ha sa p r i o r i h e n c e ，i ti sa l li m p o r t a n tc h a l l e n g e t od e v e l o pe f f i c i e n ta n ds c a l a b l e m e t h o d sf o rx m ld a t a m i n i n g a g a j n s ta b o v ea n a l y s e s ，t h i sp a p e rf i r s ti n t r o d u c et h e b a s i ct h e o r yo fx m l , t h ef e a t u r e so f x m ld o c u m e n t sa n dt r a d i t i o n a ld a t am i n i n gt e c h n o l o g y 。t h e nm o d e l x i v l ld a t aa sl a b e l e dt r e e s ， p r o p o s ean e wm e t h o d o l o g yf o re x t r a c t i n ga s s o c i a t i o nr u l e sf r o mx m l d o c u m e n t sb a s eo n c o n c e p th i e r a r c h yo f t r a d i t i o n a ld a t am i n i n gm e t h o d s w ep r e s e n tp r e l i m i n a r ye x p e r i m e n t s s h o w i n g t h a t0 1 1 1 m e t h o dc o u l db e c a p a b l eo f e x t r a c t i n g a s s o c i a t i o nr u l e sf r o mx m ld o c u m e n t s e f f e c t i v e l y k e y w o r d s ：d a t a m i n i n g ；x m l ；a s s o c i a t i o nr u l e s ；c o n c e p th i e r a r c h y i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致 身j 的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名；：酶叠日期： 伽歹3 人连理丁大学硕士学位论文 1 绪论 1 1 研究背景及意义 近年来，随着数掘库技术的迅速发展以及数据库管理系统的广泛应用，人们拥有和 积累的数据越来越多。面对庞大的数据量，人们迫切希望将这些数据转换成有用的信息 和知识，从中找出规律和模式，以便更好地利用这些数据，帮助人们进行决策和研究。 传统的以数据库为中心，进行事务处理、批处理及决策分析等各种类型的数据处理犊 式，己远远不能满足用户的需求。数据挖掘( d a t am i n i n g ) 又被称为“数据库中的知识 发现”( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) 1 1 作为新代的、智能的辅助人类从 海量数据中发现有用知识的技术正是在这种背景下产生并迅速发展起来的。它已被越来 越多的领域所采用，并取得了较好的效果。目前，数据挖掘已经成为一个国际前沿的明 究领域，是数据库研究、开发和应用最活跃的分支之一。 w e b 技术自上个世纪9 0 年代出现以来，极大地改变了人们发布、获取和使用信息 的方式，尤其是近年来，以x m l 2 为基础的新一代w e b 环境的出现，很好地兼容了原 有的w e b 应用，而且可以更好地实现w e b 中的信息共享与交换。其基于文本的方便性 和半结构化特征使得x m l 在信息管理、电子商务、个性化出版、移动通信、网络教 育、电子文档交换等诸多领域得到了广泛应用，而且其应用范围还在不断扩展。x m i _ 已经- j l ：始成为i n t e m e t 上数据描述和交换的事实标准。对于这些越来越多的采用x m 文档格式进行存储、交换和表现的数据，除了已有的信息抽取、w e b 搜索等信息处理力 法之外，人们越来越需要获取更进一步的、深层次的知识，这就需要对其进行数据控 掘，如图1 ，1 所示。 图1 11 0 1 l 挖掘 f i g 1 1x m l m i n i n g 面向x m l 文档的数据挖掘技术研究 但是，难由于x m l 是类半结构化的文本数据，与生具有文本文档和半结构化数 据的诸多弱点，如解析文档时必须采用顺序读取的方式，访问效率不高；对信息的组织 不规则，或者其结构可能经常变化，甚至可能不完整等。而传统的数据挖掘技术主要面 对的是以结构化数据为主的关系数据库、事务数据库和数据仓库，这样，我们不能直接 将传统的基于关系数据库的挖掘方法，如a p f i o r i ，应用到半结构化数据挖掘中。因此， 开发出有效的针对x m l 的数据挖掘方法成为数据挖掘领域和x m l 技术领域的一项重 要课题。 1 2 国内外相关研究 根据x m l 文档的特点及我们的挖掘目标，当前x m l 挖掘的研究可以分为结构挖 掘和内容挖掘两类。所谓结构挖掘，是指将每一个x m l 文档的结构看作是一棵有根、 有序的标记树，在此基础上对树的挖掘。由于对树的研究起步较早，所以在这方面的研 究成果比较多。树的挖掘作为频繁结构挖掘的一种，与关联规则挖掘和序列挖掘有明显 的联系，也牵涉到了树的同构和树的模式匹配。对于频繁子树的挖掘，m j z a l d 采用了 新的数据结构s c o p e l i s t 和t r e e m i n e r 3 算法来挖掘一个森林中的所有频繁予树，经过修 改还可以对未排序的树进行挖掘。a s a i 提出了f r e q t 算法【4 用类似a p f i o f i 的方法对 树进行挖掘，其中产生待选予树的方法与z a k i 的方法比较相近 5 。a l e x a n d r e 等人研究 出了2 步t r e e f i n d e r 方法 6 】，它首先识别树中的频繁标记树，然后基于s u b s u m p t i o n - i n c l u s i o n 理论检测最大频繁树。 此外，一些学者根据x m l 文档的结构特征，对其分类、关联、聚类等挖掘方法进 行了探索。m j z a k i 等人考虑了x m l 文档中结构化的信息，并将其用于构造结构化规 则来实现分类，提出了一种有效的结构化分类器x r u l e s 。w a n gl i a n 等人根据数据的结 构信息，利用距离矩阵的方法提出了对多个x m l 文档进行聚类的方法 7 】。j a c k y 、 a i t l n o n 等人利用x p a t l l 和x q u e r y 技术 8 】 9 】，结合传统挖掘方法，从结构与内容上对 关联规则提取进行探索。 x m l 的内容指的是文档中每个开始标记和结束标记之间的文本部分，对其内容的 挖掘其实也就是对标记的值的挖掘。目前，x m l 的内容挖掘主要有三种途径：第一种 是通过一些专门为x m l 数据或半结构化数据开发的查询语言，如x m l - q l 、x m l - g l 、x q u e r y 等，利用其查询功能，嵌入到其他应用程序中，从而获得数据集进行挖 掘。这种方法的优点是能够将x m l 技术与数据挖掘技术紧密结合越来，但不足也是显 而易见的，比如修改困难、查询开销巨大等。第二种是将x m l 文档的数据结构化，映 射到现有的关系模型或对象模型中，从而可以使用较成熟的数据挖掘方法对其进行挖 2 一 火连理f ：火学硕士学位论文 掘。但是x m l 本身的一些半结构化特点可能会导致在映射过程中产生一些问题。最后 - - ； t 懈决方法是将x m l 文档看作是一个文本，进而使用传统文本挖掘技术进行挖掘。 如使用矢量空间模型( v s m ) 将文档空问看作是由一组正交词条矢量所组成的矢量空问， 通过统计词频、缩减维数等步骤，达到机器学习、获得知识的目的。但这种方法并没有 考虑到x m l 文档仍存在一些结构化的特征。此外，数据量大、数据过于详细也会导致 文档的特征向量巨大，造成挖掘匾难。 1 3 本文的主要工作 由于x m l 规范发布至今不过短短几年的时间，尽管其应用前景非常广阔，但就总 体而言，x m l 相关技术及其应用仍然处于研究、探索阶段，对其进行挖掘的研究更是 如此。虽然也有一些商业化产品出现，如s c i e n t i o 公司的x m lm i n e t 等，但其与传统的 数据挖掘产品相比，还显得非常的不成熟，应用方法及应用领域都很有限。而国内对这 一领域研究的则较少，且多集中于x m l 文档与现有数据库系统的集成，侧重x m l 的 数据交换特点，从文档领域进行深入探讨的不是很多。 本文立足于文档领域，以x m l 挖掘为应用背景，研究、探讨了面向x m l 文档的 挖掘技术。基本出发点是充分发挥传统数据挖掘中成熟丰富的技术优势，兼顾x m l 文 档的结构特点，实现二者的紧密结合，最终达到能够对x m l 文档进行简便、有效的挖 掘这一目的。 本文在全面介绍x m l 挖掘及其相关技术的基础上，根据传统数据挖掘技术中h a r t 等人提出概念层次【1 技术，结合x m l 数据的特点，将特征提取应用于x m l 挖掘中， 针对关联规则提取这一数据挖掘的重要组成部分，提出了基于概念层次的x m l 文档关 联规则挖掘方法，旨在探索出一种面向文档、性能较好的挖掘方法，解决从x m l 这种 半结构化数据中挖掘知识的问题。 综上所述，本文的主要工作及创新筒述如下： ( 1 ) 全面分析了数据挖掘及半结构化数据相关技术的研究现状，并剖析了其中存 在的问题 ( 2 ) 详细介绍了面向x m l 文档挖掘的分类、相关技术及当前研究现状 ( 3 ) 结合x m l 文档结构特征，提出了基于概念层次，对x m l 数据进行关联规则 挖掘的构想，并对其实现方法进行了探讨性研究 1 4 论文结构安排 本文共分五章，各章研究内容组织如下： 一3 面向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 ：大学硕士学位论文 2 数据挖掘概述 2 1 数据挖掘发展回顾 随着大量的数据库中数据迅速不断地增长，人们对数据库的应用已不满足于仅对数 据进行查询和检索。因为仅靠查询检索不能帮助用户从数据中提取带有结论性的有用信 息，也不能充分地发掘和利用数据库中蕴藏的丰富知识，从而造成了信息的浪费，由此 也会产生大量的数据垃圾。数据挖掘正是为解决这一问题而产生并迅速发展起来的用于 开发信息资源的一种新的数据处理技术。 数据挖掘是类深层次的数据分析方法，被认为是解决“数据爆炸知识贫乏”的有效 方法之一，在最近几年里已被数据库界广泛研究。目前一种比较公认的定义是 w j f r a w l e y 和g p i a t e t s k ys h a p i r o 等人提出的 1o ：数据挖掘是从静态的存储于大型数 据库中的结构化数据中提取人们感兴趣的数据模式、内在联系、规律、发展趋势等知 识，这些知识是隐含的、事先不知的、潜在有用的信息。这个定义包括好几层含义：数 据源必须是真实的、大量的、含噪声的：发现的是用户感兴趣的知识；发现的知识要可 接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题即 可。而更广泛的说法是：数据挖掘是在一些事实或观察数据的集合中寻找模式的决策支 持过程，数据挖掘的对象不仅是数据库，也可以是文件系统，或其他任何组织在一起的 数据集合。 数据挖掘的过程可粗略地理解为3 个主要阶段：数据准备( d a t ap r e p a r a t i o n ) 、数 据挖掘( d a t am i n i n g ) n 知识的确认与提炼( k n o w l e d g e v a l i d a t i o na n dr e f i n e m e n t ) ，而且根 据挖掘结果的不问，这一个过程是可以反复执行的，如图2 1 所示。 ld a t a a t 八k n o w l e d g ei k n o w l e d g ev alidationdata p r e p a r a t i o n 啦嘲蚓嘲p 黧夕剖。器篙黧， 图2 1 知识发现过程的反复性 f i g 2 1t h e i t e r a t i v en a t u r eo f t h e k n o w l e d g ed i s e o v e r yp r o c e s s 如果进一步细分，数据挖掘由以下7 个步骤组成 1 ： 5 一 面向x m l 文档的数据挖 睫l | 技术研究 1 ) 数据清理( 消除噪声或不一致数据) 2 ) 数据集成( 多利，数据源可以组合在一起) 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 近年来，数据挖掘引起了信息产业界的极大关注，一些新兴的信息服务产业也对数 据挖掘产生了很大的兴趣，例如：在线服务和电子商务认为数据挖掘可以更好的理解用 户的行为，从而增加商业机会，抢占市场。越来越多的i t 企业看到了这一诱人的市 场，纷纷加入到数据挖掘工具的开发中来，国内外已开发出十多种关于数据挖掘的软 件，例如，m m 公司发布的的“i n t e l l i g e n tm i n e r ”和s a s 公司的“s a ne n t e r p r i s e m i n e r ”，微软公司与o r a c l e 公司都在它们的关系数据库产品中加入了先进的数据挖掘 功能。种种迹象表明，数据挖掘这一研究领域的发展充满了机遇和挑战，已经成为数据 库理论与应用研究的热点。 2 2 数据挖掘的目的和任务 描述数据是数据挖掘的两个高层目标中的第一个，也是最简单的分析步骤，包括对 统计数据的概述( 如平均值和标准方差) 、使用表单、图等可视化数据和在数据中寻求 潜在的有趣联系( 如频繁一起出现的值) 等等。其中收集、发现和选择正确恰当的数据 都是至关重要的。 数据挖掘的第二个目标是预测数据。首先基于模式的在已知结果集上创建一个预测 模型，然后使用原来样本数据以外的数据测试模型得出的结果，最后还要进行模型校 验。比如对于一个已经对某项产品订单作出反应的用户数据库，创建一个模型用于预测 用户对同一订单最有可能发生的反应，然后给一些新的用户发出邮件，根据他们给出的 答复评估模型预测的可信度等。 根据数据挖掘发现知识的不同，可以将其常见任务归纳为以下几类： a ) 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的取值重复 出现且概率很高时，它就可能存在某种关联，可以建立起这些数据项的关联规则。支持 度和置信度是关联分析中比较重要的概念，支持度表示规则所代表的事例占全部事例的 百分比，而置信度表示规则所代表的事例占满足前提条件事例的百分比。 6 一 大连理 ：大学硕一 ：学位论文 b ) 时序模式 通过时间序列搜索出重复发生概率较高的模式。例如，在所有购买了激光打印机的 人中，半年后8 0 的人再购买硒鼓，2 0 的人用旧硒鼓装碳粉。 在时序模式中，需要找出在某个最小时间内出现比率一直高于最小百分比的规则， 这些规则会随着形式的变化做适当的调整。 在时序模式中，一个有重要影响f | 勺方法是“相似时序”。用相似时序的方法，要按 时间顺序查看时间事件数据库，从中找出另一个或多个相似的时序事件。如在胶市中找 有相似波动的股票。 c ) 分类 分类是数据挖掘中应用得比较多的任务。分类是找出一个类别的概念描述，它代表 了这类数据的整体信息，即该类的内涵描述，一般用规则或决策树模式表示。该模式能 把数据库中的元组影射到给定的某个类别上。 d ) 聚类分析 聚类分析是一种多元统计方法，是当代分类学与多元分析的结合。聚类分析是将分 类对象置于一个多维空间中，按照它们空间关系的亲疏程度进行分类。通俗地讲，聚类 分析就是根据事物彼此不同的属性进行辨认，将具有相似属性的事物聚为一类，使同一 类的事物具有高度的相似性。聚类方法包括统计分析方法、机器学习方法、神经网络方 法等。 e ) 偏差检测 数据库中的数据存在很多异常情况，从数据分析中发现这些异常情况也很重要，可 以引起人们的注意。偏差包括很多有用的知识，如：分类中的反常实例、模式的例外、 观察结果对模型预测的偏差、量值随时间的变化等。 偏差检测的基本方法是寻找观察结果与参照之间的差别。观察常常是一个域的值或 多个域值的汇总，参照是给定模型的预测、外界提供的标准或另一个观察。 f ) 预测 预测是利用历史数据找出变化规律，建立模型，并用模型来预测未来数据的种类、 特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变量建立线性或非 线性回归方程。预测时只要输入任意的时间值，通过回归方程就可求出该时间的状态。 2 3 数据挖掘面临的主要问题 当前数据挖掘面临的主要问题有三大类：挖掘方法和用户交互的问题、性能问题 和存储数据的数据类型具有多样性的问题。 ，7 面向x m l 文档的数据挖掘披术研究 ( 1 ) 挖掘方法和用户交互问题 这类问题涉及到数据挖掘技术的多个方面，主要有以下一些内容： a ) 在数据库中挖掘不同类型的知识：由于不同的用户感兴趣的知识类型可能会很 刁i 相同，这就要求数据挖掘系统应用覆盖范围很广的数据分析和知识发现任 务，包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性 分析。这些方式可能以不同的方式使用相同的数据库，并需要开发大量的数据 挖掘技术。 b ) 多个抽象层的交互知识挖掘：由于在进行数据挖掘之前很难知道将要挖掘出来 的是什么样的知识，因此需要数据挖掘的过程具有交互性。对于大型的数据 库，应当使用抽样技术进行交互式的数据探查。交互式挖掘允许用户聚焦搜索 模式，根据返回的结果提出和精炼数据挖掘请求，从而使用户可以以不同的粒 度和从不同的角度观察数据和发现模式。 c ) 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过程， 并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知 识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发 现的模式的兴趣度。 d ) 数据挖掘查询语言和特定的数据挖掘：与现在存在大量的高级程序开发语言相 比，数据挖掘还缺乏- f - j 统一的高级语言用于描述数据挖掘的过程和结果。关 系查询语言( 如s q l ) 只能允许用户提出特定的数据检索查询，而对数据挖掘 高级语言的要求则更高，它应该能够使用户通过说明分析任务的相关数据集、 领域知识、所挖掘的数据类型、被发现的模式必须满足的条件和约束，描述特 定的数据挖掘任务。这种语言应当与数据库或数据仓库查询语言集成，并且对 于有效的、灵活的数掘挖掘是优化的。 e ) 数据挖掘结果的表示和显示：高级语言、可视化表示或其他形式的表示方法可 以使知识易于理解，能够被人们直接使用。这要求系统采用有表达能力的知识 表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 f ) 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况或不 完全的数据对象，它们可能搞乱分析过程，导致数据与所构造的知识模型过分 适应，由此导致所发现的模式精确性很差。这就需要处理数据噪声的数据清理 方法和数据分析方法，以及发现和分析异常情况的孤立点挖掘方法。 一8 人连理：f ：大学硕士学位论文 g ) 模式评估一兴趣度问题：数据挖掘方法发现的模式通常数以千计，怎样从中选择 出用户感兴趣的模式是一个极具挑战性的问题。 ( 2 ) 性能问题 a ) 数据挖掘算法的有效性和可伸缩性：数据挖掘算法的有效性要求算法的运行时 间尽可能地少，而可伸缩性则要求算法能够支持不同大小的数据库容量，算法 的运行时间应尽可能地与数据库的容量保持线性比例的增减关系。 b ) 并行、分布式和增量挖掘算法：并行和分布式数据挖掘算法将数据划分成多个 部分，这些部分可以并行处理，然后将各个处理结果合并。这种类型的算法可 以对付数据库的大容量、数据的广泛分布和些数据挖掘算法的计算复杂性的 问题。而数据挖掘过程的高花费导致了对增量挖掘算法的需求，这种类型的算 法和数据库更新结合在一起，它不必随着数据库的更新重新挖掘全部数据，而 只需要在原有挖掘结果的基础上修正和加强业已发现的知识。 ( 3 ) 关于数据类型的多样性问题 a ) 有关系的和复杂的数据类型的处理：由于数据库类型的多样性，指望一个系统 挖掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定的数 据挖掘系统。 b ) 从异构数据库和全球信息系统中挖掘信息：局域网和广域网( 如互联网) 提供 了大量庞大的、分布式的和异构的数据库。从具有不同语义的结构化的、半结 构化的和非结构化的不同数据源发现知识，是数据挖掘技术面临的一个巨大挑 战。 2 4 数据挖掘的研究与发展方向 数据挖掘现在是数据库研究、开发和应用最活跃的分支之一，它涉及了计算机科学 中的多个领域，这些领域包括传统的数据库技术、人工智能、机器学习、神经网络、统 计学、模式识别、知识库系统、知谈获取、信息提取、高性能计算和数据可视化等学 科。随着这些学科的不断发展，数据挖掘也需要不断地发展。针对数据挖掘现在面临的 主要问题，数据挖掘的研究与开发最主要的方向有以下一些： ( 1 ) 与数据仓库与在线分析处理技术结合：数据仓库可以为在线分析处理和数据挖 掘提供经过滤化的、完整的数据资源。在线分析处理可以看作为一个简化的对 数据进行聚合的数据挖掘形式。与在线分析处理工具相结合，个数据挖掘器 能够深入到一个数据立方体的任意一维，从丽在不同的抽象层上找到用户感兴 趣的形式，由此也增加了数据挖掘与数据仓库系统的用途。 9 面向x m l 文档的数据挖掘技术研究 ( 2 ) 挖掘多种类型的知识：数据挖掘除了最常见的分类与关联之外，还有许多重要 的任务待开发，包括描述、比较，聚合、预测模型以及时间相关形式分析等 等。 ( 3 ) 提供对数据挖掘的查询语言和高效、交互式及特殊数据挖掘的支持：与相关语 言类似，高层次的数据挖掘语言应该能够允许用户定制特殊的数据挖掘任务。 ( d ) 处理复杂数据：关联性和事务性的数据是目前数据挖掘的中心。但是对于半结 构化以及非结构化的数据进行挖掘，也是一个非常重要两极富挑战性的方面。 ( 5 ) 高性能的数据挖掘：高效性和可伸缩性是目前数据挖掘算法的焦点，随着并行 的、分布式的以及增长式的数据挖掘技术的发展，这种趋势将会继续得到发 展。 ( 6 ) 可视化和数据挖掘：数据库内容和数据挖掘结果的可视化可以帮助用户理解和 评估挖掘结果，从而对数据挖掘进行相应的调整，对交互式的数掘挖掘来说， 开发易用与易看的工具是一个很有发展空间的领域。 f 7 ) 数据挖掘的应用：如何将数据挖掘技术应用于现实世界也是一个非常重要的课 题。 1 0 火连理人学硕十学位论文 3 x m l 技术概述 3 1x m l 的发展回顾 x m l 的全称是可扩展标识语言。所谓标识，就是为了处理的目的，在数据中加入 1 匀附加信息。应用标识法描述结构化数掘的形式语言称为标识语言。 首先回顾下x m l 的发展历史。x m l 有两个先驱s g m l ( 标准通用标记语言， s t a n d a r dg e n e 蹦i z e dm a r k u pl a n g u a g e ) 和h t m l ( 超文本标记语言，h y p e r t e x tm a r k u p l a n g u a g e ) 。s g m l 的前身是i b m 公司为解决公司内部大量文档的交换和存储，于 1 9 6 9 年发明的通用标识语言g m l 。经过十年的改进，由g m l 发展为s g m l ，并在 1 9 8 6 年被国际标准化组织公布为国际标准i s 0 8 8 7 9 。s g m l 可用于创建各种不同的标识 语高，为语法标识提供了最强大的工具，同时具有良好的可扩展性，因此在分类和索引 数据中非常有用。但是，s g m l 非常复杂，其复杂程度不适合互联网上的应用。为此， 在1 9 9 0 年产生了h t m l 语言。h t m l 是一个非常简单的s g m l 语言，句法简明紧 凑，功能强大，最早应用于网络信息传输，为推动互联网的发展以及信息和知识在互联 网上的交流发挥了不可替代的作用，目前i n t e m e t 上大多数的w e b 页面仍然是用h t m l 语言书写的。但h n 仉自身的缺点限制了它的进一步发展：h t m l 难以描述信息语义 及其内部结构，不能适应日益增长的信息检索要求和存档要求；h t m l 对表现形式的描 述能力也不足，无法描述矢量图形、科技符号和一些特殊的显示效果；h t m l 松散的语 法规范使得文档结构混乱而缺乏条理；h t m l 的超级链接是单向的，只能在它的某一端 ( 源端) 定义，并确定了它的另一端( 目的端) ，用户只能从源端起到目的端，等等。 在这种情况下，全球信息网协会w 3 c 于1 9 9 6 年组建了一个以来自s u n 的j o nb o s a k 为 主席的工作组，希望创建新规范为软件开发人员和内容创作者提供在网上组织信息的新 工具，并希望能够确保在通过网络进行交互合作时，具有良好的可靠性和互操作性，于 是1 9 9 8 年2 月，w 3 c 正式通过了x m l l 0 版本，2 0 0 0 年1 0 月6 同公布了x m l l 0 第 二版。 x m l 虽然起源于s g m l ，但是它摒弃了s g m l 复杂的特性，以一乖p 开放的自我描 述方式定义数据结构，在描述数据内容的同时突出对结构的描述，从而体现出数据之间 的关系，具有可扩展性、简单性、开放性、互操作性，支持多国语言等优点，从而能较 好地解决h t m l 语言的缺陷，更适合在网络环境下使用。另外，由于x m l 是一种元标 记语言，可以用于定义其他与特定领域有关的的标记语言，由它可以产生出许多种应 用，如c m l ( c h e m i c a lm a r k u pl a n g u a g e ，化学标记语言) 、m a t h m l ( m a t h e m a t i c a l 面向x m l 文档的数据挖拍f 技术研究 m a k u pl a n g u a g e ，数学标记语言) 、s m i l ( s y n c h r o n i z e dm u l t i m e d i al a n g u a g e ，同步的 多媒体集成语言) 等等，如图3 1 所示。 通用标记语言 f 未喜言兰孚 篮标准通用标记语言 挲蒿 倒刨l ! 型倒 可扩展超文本可缩放矢同步多媒 奉手持设备 标记语言量图形语言综合语言标记语言 图3 1x m l 的发展过程 f i g 3 1t h e e v o l u t i o no f x m l o e b l 开放电子 结构语言 值得说明的是，x m l 并不是h t m l 的扩展，而是一种用于定义标记语言的类似于 s g m l 的语言。虽然它们都是s g m l 的子集，但它们之间有着很明显的区别：h t m l 是为了页面中的内容显示而设计的，雨x m l 是为了表示页面中的内容的结构和语言来 设计的；h t m l 是格式化语言，对要表示的内容进行格式信息定义，对数据本身是没有 理解的，而x m l 是结构化语言，是对要表示的内容进行结构信息的定义，揭示文本的 涵义；h t m l 文档主要是供浏览器使用的，而x m l 文档可以允许任何的应用来进行读 写、交换、处理等操作；h t m l 是由一组固定的标、圮组成的，是不支持扩展性的，雨 x m l 继承了s g m l 的可扩展性，允许用户根据自己的需要自定义标记：h t m l 不要求 结构完整性，而x m l 是必须要求文档的结构完整性，等等。 x m l 文件必须经过x m l 解释器( 也称为x m l 处理器) 的解释，爿4 能产生出所需 要的数据，然后再对这些数据进行其他操作，包括显示、执彳亍计算或传送数据给其他系 统实现数据交换等。许多软件供应商都开发了自己的x m l 解释器，其中微软公司的 i n t e m e te x p l o r e r 5 提供了内置的x m l 解释器( 即m s x m l ) ，从而提供了将x m l 信息 集成到各类w e b 文件的方法。当然，x m l 本身并不能满足全部要求，建立在x m l 基 础上的相关技术提供了更加强大的功能，如x m l 链接语言( x l i n k ) 、x m l 指针语言 ( x r ) o i n t e r ) 、可扩展样式语言( x s l ) 、x m l 查询语言及x m ls c h e m a 等。 1 2 人连理一r 大学硕士学位论文 3 - 2 ) ( m l 的主要特点 x m l 克服了h t m l 的种种不足，将互联网上的文档规范化，赋予标记一定的含 义，并保留了h t m l 所具有的简洁、适于传输和浏览的优点，集s g m l 和h t m l 的优 势于一身，成为下一代互联网发展的核心。具体地说，x m l 具备以下一些优点 1 1 1 ： 1 ) 可扩展性：x m l 提供了一个表示信息的框架。它允许信息提供者根据自己的需 求和意愿定义任意的标记，数据经过x m l 的处理之后，表达方式简单易读，同时也易 于由其他应用进行进一步的加工和处理。比如描述与出版的书有关的信息时，需要描述 二挎的书名、作者、译者、出版社等等，就可以创建用于每一项的标记，对于不同的领域 还可以根据不同需要来定义。 2 ) 结构性：数据存储格式不受显示格式的制约，一般包括三个要素：数据、结构以 及显示方式。x m l 使用d t d ( 或x m ls c h e m a ) 规定一套关于标【己符号的语法、语义 规则，比较准确地描述文件资料的内容、含义、结构、特征和关系等信息，而把资料的 外观表现形式交给样式表( 如c s s 、x s l 等) 处理，这样就把信息的内容和其表现形式 合理地隔开，从而大大提高x m l 信息的可理解性、可交换性和重用性。 3 ) 平台独立性：x m l 使用普通文本，而不是二进制的数据格式，具有跨平台的优 点，运用x m l 可以有效地解决新旧系统平台、不同应用系统平台之间或者不同数据源 之间的数据共享与交互问题。 4 ) 自描述性：x m l 以显示语句和隐式嵌套结构描述结构化信息，任何应用都可以 方便访问其中的数据并清楚地了解到标记内容的含义，自描述性使其非常适用于不同应 用问的数据交换，而且这种交换是不以预先规定一组数据结构定义为前提，因此，具备 很强的开放性。 5 ) 灵活性：x m l 文档中，数据、数据结构与文档的表现方式是分离的，它与 h t m l 的组织方式完全不同，结构化的数据通过可扩展的样式表x s l 将数据呈现在不 同的终端设备上，通过使用不同的x s l 模板可以将数据方便地呈现在各种不同系统的 浏览器上，而在这些不同的应用上，数据本身是一样的。 6 ) 规范、简单性：x m l 与h t m l 一样，x m l 也是源于标准通用标记语言 s g m l ，它保留了s g m l 的8 0 的功能，而复杂性只有它的2 0 ，此外，x m l 文档有 一套严谨而简洁的语法结构，这为x m l 解析器获取文档所含信息提供了前提。 1 3 面向x m l 文档的数据挖掘技术研究 3 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 文档一般以一个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 文档所采用的 编码标准) 赋值。 ( 2 ) 处理指令 处理指令为处理x m l 文档的应用程序提供信息。x m l 解析器不处理这些指令， 而将它们原样传给应用程序。应用程序解释这些指令，按照它们提供的信息进行处理。 ( 3 ) x m l 元素 元素是x m l 文档的基本单元。一个元素代表文档中一个逻辑组件。元素可以互相 嵌套，形成树形结构：包含所有其他元素的元素称为根元素，包含在根元素中的元素称 为根元素的子元素，子元素还可以包含自己的子元素。 一个元素包含一个起始标记、一个结束标记和标记之间的数据内容。标识是x m l 语言的精髓，因而标记是x m l 文档的重要组成部分。为了组织数据更加方便、清晰， 可以在x m l 文档中引入c d a t a 数据块，其中所有的内容都可以看作字符数据。此 外，还可以在x m l 文档中加入一些用作解释的字符数据，x m l 处理器不对它们作任 何处理。这种类型的文本称作注释文本。下面是一个描述书目的简单的x m l 文档： x m lr e t r i e v a l 3 0 h n 3 4x m l 的有关技术规范 自从x m l l 0 规范发布以后，x m l 的有关技术规范不断涌现。w 3 c 在1 9 9 9 年先 后推出了n a m e s p a e e sx m l ( x m l 中的命名空间) 、c s s 2 、a s s o c i a t i