（计算机应用技术专业论文）基于xml和概念层次树的数据挖掘研究.pdf

曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士囱论文基于x m l 和概念 层次树的数据挖掘研究，是本人在导师指导下，在曲阜师范大学攻读博士 f 口硕士曰学位期间独立进行研究工作所取得的成果。论文中除注明部分外 不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均己在文中己明确的方式注明。本声明的法律结果将完全由本 人承担。 作者签名：石啄淘孑n 日期：) 1 0 阳勿、v 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 基于x m l ，和概念层次树的数据挖掘研究系本人在曲阜师范大学攻读 t| 博士口硕士d 学位期间，在导师指导下完成的博士口硕士口学位论文。 本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位 的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定， 同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅 和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文， 可以公开发表论文的全部或部分内容。 作者签名：弓长i 轫釉 日期：沙c d z 、 新獬形形 醐珈肌歹 幕于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 数据挖掘和知识存储表示。在x m l 数据挖掘中 结合概念层次树和关联规则的相关技术提出了一种基于概念层次树的x m l 数据挖掘算法， 该算法通过概化操作，不仅降低了时间复杂度，并且挖掘出更容易被理解和接受的规则， 对基于x m l 数据的关联规则的挖掘具有一定的理论价值和实际意义。 最后设计实现了一个电子商务数据挖掘系统，来验证分析本文提出的数据挖掘系统框 架和算法。 关键词：数据挖掘；x m l ；关联规则；概念层次树 a b s t r a c t a l o n gw i t ht h ei m p p r o v e m e n to f t h ex m lt e c h n o l o g ym o r ea n dm o r ew e bd a t ab e g a nt ob e r e p r e s e n t e du s i n gx m l 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 d r e p r e s e n to faw i d ev a r i e t yo fd a t ao nt h ew e b a n de l s e w h e r ed u et oi t ss c a l a b i l i t y , f l e x i b i l i t y , p l a t f o r mi n d e p e n d e n c e ， s i m p l i c i t y , s t a n d a r d i z a t i o na n d s oo n ，t h e r e f o r e ，t h e r eh a v eb e e n i n c 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 t c a l le x t r a c tr u l e sa n dp a t t e r s nf r o mx m ld a t a , h o w e v e r , t h ex m l d a t ao nt h ew e bi st o oc o m p l e xa n ds e m i s t r u c t u r e dw i t hn oc e r t a i n d e s c r i p t i o np a t t e r n t h u s ，w ec a nn o td i r e c t l ya p p l yt o x m ld a t aw h t ht h et r a d i t i o n a ld a t a m i n i n gm e t h o d sf o rr e l a t i o n a ld a t a b a s e s h e n c e ，i ti s ag r e a tc h a l l e n g et od e v e l o pe f f i c i e n ta n d s c a l a b l em e t h o d sf o rx m ld a t am i n i n g i nt h i sp a p e r ，c o m b i n e dx m l b a s e dd a t am i n i n gc o n c e p ta n dh i e r a r c h yt r e eo fk n o w l e d g e ，i h a v ep r o p o s e dad a t am i n i n gs y s t e mf r a m e w o r kt h a tb a s e do nx m l a n dh i e r a r c h i c a lt r e e a c c o r d i n gt oe a c hs t e pi nt h ef r a m e ih a v ed e s c r i b e di n t e r r e l a t e di m p l e m e n t a t i o nt e c h n o l o g y , i n c l u d i n gd a t ap r e p r o c e s s i n g ，d a t as t o r a g e ，x m l d a t am i n i n ga n dk n o w l e d g es t o r a g ea n de x p r e s s a c c o r d i n gt ot h ef r a m e w o r ka n d t h ea s s o c i a t i o nr u l e sr e l a t e dt e c h n o l o g i e sp r e s e n tad a t am i n i n g a l g o r i t h mt h a tb a s e do nx m l a n dt h ec o n c e p th i e r a r c h yt r e e ，w h i c hn o to n l yr e d u c e st h et i m e c o m p l e x i t y , b u ta l s om a k em i n i n g r e s u l t se a s i e rt ou n d e r s t a n d x m l b a s e dd a t am i n i n go fa s s o c i a t i o nr u l e sh a v es o m et h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e f i n a l l y , t h i sp a p e rd e s i g n sa n di m p l e m e n t sa ne c o m m e r c ed a t am i n i n gs y s t e m ，w h i c hv e r i f i e s a n da n a l y z e st h ep r o p o s e da l g o r i t h ma n ds y s t e mf r a m e w o r k k e y w o r d s ：d a t am 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 t r e e u 基于x m l 和概念层次树的数据挖掘研究 目录 第一章绪论1 1 1 研究背景和意义1 1 2 研究现状1 1 3 论文组织结构2 第二章数据挖掘及x m l 技术概述4 2 1 数据挖掘技术概述4 2 1 1 数据挖掘的任务一4 2 1 2 数据挖掘的对象5 2 1 3 数据挖掘的过程6 2 2x m l 技术概述7 2 2 1x m l 技术特点7 2 2 2x m l 语法8 2 2 3x m l 在数据挖掘中的应用9 第三章基于x m l 的数据挖掘系统设计1o 3 1 数据源1 0 3 2 数据预处理( 数据的x m l 化) l o 3 2 1 数据转换10 3 2 2 数据x m l 规范化1 2 3 3x m l 数据存储1 2 3 4 基于x m l 和概念层次树的数据挖掘1 3 3 4 1 概念层次树1 3 3 4 2 基于x m l 和概念层次树的数据挖掘算法1 7 3 4 3 基于x m l 和概念层次树的数据挖掘流程图及主要j a v a 源码2 4 第四章挖掘算法在电子商务系统中的应用2 7 4 1 电子商务挖掘系统设计2 7 4 2 电子商务挖掘系统的模块划分2 8 4 3 电子商务挖掘系统的性能分析3 0 第五章结论与展望3 3 5 1 结论3 3 5 2 进一步的工作3 3 参考文献 3 4 在校期间发表的学术论文3 7 致 射3 8 i i i 基于x m l 和概念层次树的数据挖掘研究 第一章绪论弟一早三百下匕 随着全球网络化、信息化的飞速发展，网络上的信息越来越多，w e b 已成为人们获取 信息的重要途径。数据的快速增长大大超出了人们从中分析并提取有用知识的能力。数据 挖掘作为- i - j 新兴的学科逐渐形成。数据挖掘特别是基于x m l 的数据挖掘在w e b 服务、 政府、电子商务、图书馆和医学等领域有着广泛的应用。 数据挖掘日渐成为新的研究热点，基于x m l 的数据挖掘更是受到人们越来越多的关 注。本章对论文选题的背景和意义进行了简要介绍，阐述了本文主要的研究内容和组织结 构。 1 1 研究背景和意义 在一九九八年八月份所召开的第十一届国际人工智能联合会议上，第一次提出了数据 库中知识发现的概念。在接下来的几年中所召开的国际人工智能联合会议都热烈地讨论了 该议题，程序研发者和各个领域的专家就数据挖掘的相关问题如海量数据分析算法、数据 统计、知识运用、知识表示等问题都做了相关讨论【l 】。数据挖掘技术随着信息技术的不断 发展逐渐成为解决“数据爆炸”问题所出现的非常有效的手段，同时深受信息产业界的极 大关注，主要就怎么把企业界存在的大量数据转化成有用的知识信息，并应用于商务管理、 市场分析、生产控制、科学领域、工程设计等实用领域【2 】。所谓数据挖掘就是从大量的、 有噪声的、不完全的、随机的、模糊的数据集中识别潜在的、有效的、新颖的信息，然后 产生容易理解的模式。 x m l 因其简单、灵活、开放、通用以及可扩展、结构化等特点从提出之后发展大约十 几年并越来越成熟，并且成为i n t e r n e t 上数据表示和数据交换的事实标准，应用于数据交 换、发布、集成、存储和管理。正是因为x m l 的日益成熟，受到了m i c r o s o f t 、i b m 、o r a c l e 、 s u n 、h p 等大公司的大力支持1 3 j 。所以，以x m l 形式描述的数据量呈爆炸式增长趋势， 同时发展的x m l 数据库包括支持x m l 数据格式和以x m l 为数据源的数据库达到几十个。 x m l 数据库的快速发展迫切需要与之相适应的数据挖掘技术，然而传统数据挖掘技术主要 面向结构性很强的结构化数据，无法解决变化的、具有复杂层次结构的x m l 数据挖掘问 题，所以我们必须研究针对x m l 数据的特有挖掘方法【4 1 。 1 2 研究现状 本世纪以来，随着x m l 的广泛应用和国内国外对以x m l 为数据源的数据挖掘研究越 来越多，人们也越来越重视基于x m l 的数据挖掘，对数据挖掘和x m l 结合起来的研究重 点转移到x m l 表达的w e b 数据模型，包括x m l 数据存储和数据查询等相关专业技术问 题。 国际上对于x m l 的数据挖掘研究大体分为两派，一派是以传统的数据库技术为主要 支撑，重点研究如何利用现有的数据库技术实现对x m l 数据的有效管理，研究国家主要 基于x m l 和概念层次树的数据挖掘研究 包括美日等信息强国以及亚洲一些新兴的经济体1 5 j 。另一派是基于x m l 技术，重点研究 如何对x m l 文档进行有效的管理，目标是研究一种能够对w e b 上的x m l 数据进行有效 管理的x m l 数据库，研究国家主要以一些欧洲国家为主，德国和法国在这个领域成果显 著，英国也加大了在这方面研究的投入1 6 】。在国内同样也有一些机构和部分院校致力于处 理和挖掘x m l 信息的研究工作。 我们结合x m l 的特点和挖掘目标将x m l 数据分为结构挖掘和内容挖掘两大类。x m l 结构挖掘就是把x m l 文档的结构当做一棵有序、有根的标记树，对x m l 文档树进行挖掘。 因为对树的研究成果较多，频繁结构挖掘也与序列挖掘和关联规则挖掘有紧密联系，它主 要涉及到树的同构和树的模式匹配，所以对于频繁子树的挖掘主要就是对树的操作。例如 m j z a k i 7 j 采用基于新的数据结构s c p o e 1 i s t 和t r e e m i n e 算法来挖掘森林或未排序的树中 的所有频繁子树，a s a i 8 1 采用改进a p f i o f i 算法和s u b s u m p t i o n i n c l u s i o n 理论识别树中的频 繁标记树来检测最大频繁树。 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 数据映射到现有的关系模型或对象模型中对其进行挖掘，但是x m l 的自身特点会 导致在映射过程中可能产生问题；第三种结合文本挖掘方法，将x m l 转换成文本进行挖 掘，如使用矢量空间模型( v s m ) 将文档空间看做是由一组正交词条矢量所组成的矢量空间， 通过统计词频、缩减维数等步骤，达到机器学习和获得知识的目的，但是没有考虑到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 的由来， 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 技术概述 2 1 数据挖掘技术概述 当今在国内外数据库研究和人工智能研究的最前沿的学术问题就是在数据库中进行知 识发现，主要包括数据选择、预处理、数据挖掘、结果解释、评价四个步骤。知识发现的 目的就是希望从大量的繁杂的数据中寻找有效、有用的和容易被理解的模式【9 j ，由此可以 看出数据挖掘是数据库中知识发现的一个核心步骤，涉及从各种数据中提取令人感兴趣信 息的模式挖掘算法。 首次提出基于数据库知识发现的学术问题是在一九八九年的第十一界国际人工智能联 合会议的专题研讨会上【l o 】，会上讨论该技术涉及知识获取、专家系统、模式识别、机器学 习、统计学、高性能计算、智能数据库和数据可视化等领域。关于数据挖掘的比较正式的 概念提出是1 9 9 5 年在美国召开的计算机年会上，该会议给出一个数据挖掘的定义，即数 据挖掘就是从数据库中抽取未知的、隐含的、具有潜在使用价值信息的过程【l 。 g p i a t e t s k y s h a p i r o 、w j f r a w l e y 等人在1 9 9 6 年给出了一个公认的数据挖掘定义，他们认 为数据挖掘就是从大型数据库的数据中提取人们感兴趣的、隐含的、潜在的和事先未知的 有用信息，并表示为规则、概念、模式等形式1 1 2 1 。 综合数据挖掘的众多概念，可以总结出数据挖掘就是从大量的、模糊的、随机的、有 噪声的和不完全的数据中，提取人们感兴趣的、潜在有用的、隐含在其中的潜在的知识和 有用信息的过程。通过分析这个定义可以看出：对于数据源要求必须是大量的、真实的、 有噪声的，来自于关系数据库、空间数据库、面向对象数据库，也可以来自文本数据源、 多媒体数据，以及分布在w e b 上的异构数据源：对于挖掘方法可以使用不同的办法来发 现知识，如数学的和非数学的方法，演绎的和归纳的方法等，但是发现的知识必须是用户 可理解、可接受、可运用的概念、规则、模式、规律和约束等，并应用于查询优化、信息 管理、过程控制、决策支持或者用于数据自身的维护等各个实用领域。因此，数据挖掘是 - n 汇集了统计学、机器学习、模式识别、信息检索、高性能计算、数据库技术、数据可 视化、空问数据分析和图像与信号处理等不同领域的交叉学科，是一种具有强大实际作用 和光明前途的学科i l3 。 2 1 1 数据挖掘的任务 数据挖掘的任务一般可以分为预测和描述两类：预测性的任务就是在当前数据上推断： 描述性的任务就是来描述数据集中一般特性的数据i l 制。 我们将着重介绍数据挖掘的几个任务： ( 1 ) 关联分析 关联分析是利用关联规则进行数据挖掘，关联分析的研究是数据挖掘领域的一个重要 4 ， 基于x m l 和概念层次树的数据挖掘研究 部分。关联分析的目的是挖掘隐藏在数据i 日j 的相互关系。通过进行挖掘，人们能够得到形 如“在某一段时间内，年龄在2 0 到3 0 岁的顾客，购买了电脑后又购买操作系统之类的 知识。 设q = q l ，q 2 ，o e 9 q m 是一组项集，n 为事务m 的集合，其中每个事务m 都是一组 项集，且m c _ q ，如果a 至m ，a 是q 中的一个项集，则称事务m 支持项集a ，关联规则 是形如aj b 的蕴涵式，其中a c _ q ，- b c _ q ，且a 1 7b = o 。 可信度：设事务集n 罩支持项集a 的事务中，有e 的事务同时也支持项集b ，e 则 称为关联规则aj b 的可信度，也就是说在事务t 中出现了a 且同时出现b 的概率。 支持度：设事务集n 中当有f 的事务同时支持a 和b ，f 则称为关联规则aj b 的 支持度，也就是说a 和b 两个项集的并集在所有的事务中出现的概率。 关联规则挖掘算法因为搜索频繁项集策略的不同可以分为宽度优先和深度优先搜索两 大类。其中a p r i o r i 算法是一种经典的宽度优先算法【l5 1 ，它可以分成两个步骤：第一，找 出所有支持度大于设定阈值的项集，具有最小支持度的项集称为频繁项集；第二，由频繁 项集产生关联规则，所有满足置信度阈值的规则都作为算法的结果被保留下来。 a p r i o r i 算法需要多次扫描数据库，当数据量较大时，算法的效率急剧下降，所以有很 多人集中在产生候选项集的方法和候选项集支持度的计算上对a p r i o r i 算法进行改进，以期 提高效率。 ( 2 ) 预测 预测是采用回归分析方法并利用历史数据找出变化规律，建立模型来预测未来数据的 种类、特征等，也就是说利用大量的历史数据，以时间为变量建立线性或非线性回归方程。 ( 3 ) 分类 分类是用规则或决策树模式描述代表一个类别的整体信息的概念描述即内涵描述，并 将数据库中的元组映射到某个给定的类别上。 ( 4 ) 聚类分析 聚类分析是当代分类学与多元分析结合的多元统计方法，采用统计分析、机器学习、 神经网络等方法将分类对象置于一个多维空间中，按照它们空间关系的亲疏程度进行分 类，也就是说，为了使同一类的事务具有高度的相似性而根据事务彼此不同的属性将具有 相似属性的事务聚为一类【1 6 】。 ( 5 ) 时序模式 找出在时序模式中的某个最小时间内出现比率一直高于最小百分比且会随着形式的 变化做出适当的调整的规则。“相似时序”是在时序模式中一个有重要影响的方法，它按 时间顺序查看时间事件数据库，并且从中找出另一个或多个相似的时序事件。 2 1 2 数据挖掘的对象 数据挖掘的对象主要是关系数据库和数据仓库，这是典型的结构化数据。随着技术的 基于x m l 和概念层次树的数据挖掘研究 发展，数据挖掘对象逐步扩大到半结构化或非结构化数据，这主要是文本数据、图像与视 频数据以及w e b 数据等。 ( 1 ) 关系数据库 关系数据可以通过数据库查询访问。数据库查询使用如s q l 这样的关系查询语言，或 借助于图形用户界面书写。在后一种情形下，用户可以使用菜单制定包含在查询中的属性 和属性上的限制。一个给定的查询被转换成一系列关系操作，如连接、选择和投影，并被 优化，以便有效地进行处理。 ( 2 ) 文本 文本是以文字串形式表示的数据文件。文本分析包括：关键词或特征提取、相似检索、 文本聚类和文本分类等。 ( 3 ) 图像和视频数据 图像和视频数据是典型的多媒体数据。数据以点阵信息及帧形式存储，数据量很大。 图像与视频的数据挖掘包括图像与视频特征提取、基于内容的相似检索、视频镜头的编辑 与组织等。 ( 4 ) w e b 数据 随着i n t e m e t 网的发展和普及，网站数目的迅速增长以及入网人员的急剧增多，使用 网络数据量呈指数增长。w e b 数据挖掘已成为一个崭新的课题。w e b 数据挖掘的特点有 异构数据集成挖掘和半结构化数据模型抽取等，总之，w e b 数据挖掘正在逐步形成热点。 2 1 3 数据挖掘的过程 数据挖掘过程可以分为三个主要的阶段：数据准备、数据挖掘和知识的确认及提炼【1 7 】， 而且根据挖掘的结果不同，这一过程可以反复执行。如图2 1 所示，数据挖掘的基本过程又 可以细分为数据清理、集成、选择、变换、挖掘和模式评估与知识表示七个步骤。 图2 1 数据挖掘过程 6 - 基于x m l 和概念层次树的数据挖掘研究 2 2x 池技术概述 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 ，可扩展标记语言) 是哇i w 3 c ( 万维网协会) 在1 9 9 5 年2 月设计发布的，它是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 ) l 拘- - 个重要的分支【1 8 】。 x m l 是专为w e b 应用服务设计的，用来描述数据的语言，其设计目标是实现s g m l 的丰富 功能和h t m l ( 超文本标记语言) 简单性的结合。 x m l q 的标记( t a g ) 是用户自定义的，并没有严格的规定，用户可以灵活地定义数据。 同时x m l 也是能够进行自解释的语言。x m l 使用d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档类 型定义) 和x m ls c h e m a ( x m l 模式) 来显示数据，使用c s s ( c a s c a d i n gs t y l es h e e t ，层叠样式 表) 或x s l ( e x t e n s i b l es t y l es h e e tl a n g u a g e ，x m l 样式表语言) 来描述这些数据如何显示【1 9 】。 使用s a x ( s i m p l ea p p l i c a t i o nf o rx m l ) 或d o m ( d o c u m e n to b j e c tm o d e l ) 文档对象模型来处 理x m l 数据。由于用x m l 标记能够方便灵活地表示数据，所以用户可以根据标记方便地找 出自己需要的数据。 2 2 1x 技术特点 目前，h t m l 因其简单、易于编写等优点在互联网中有着广泛的应用，但h t m l 因为 其灵活性、可扩展性较差，不适合互联网上大量的数据处理。x m l 克服了h t m l 的种种缺 点，将互联网上的文档规范化，可以自定义标记描述数据，同时保留了h t m l 简洁、适于 浏览和传输等优点，并集成了s g m l 的优良特性，成为下一代互联网的核心，具体地来说 x m l 的优点如下： ( 1 ) 可扩展性 可扩展性是x m l 最重要的特性之一。人们可以根据自己的需求和意愿自定义标记，数 据经过x m l 描述之后，表达方式简洁、易懂，同时也易于其它应用程序做进一步的处理。 比如描述与学生有关的信息时，需要描述学生的姓名、性别、年龄、籍贯等等，就可以用 来创建每一项的标记。 ( 2 ) 结构性 在x m l 中数据和显示互相分离，即数据的存储格式不受显示格式的限制，数据、结构 和显示方式分别描述。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 使用普通文本而不是二进制的数 据格式，用x m l 可以有效地解决各种新旧系统平台、不同应用系统平台间或者不同数据源 之间的数据共享和交互。 7 - 基于x m l 和概念层次树的数据挖掘研究 ( 4 ) 自描述性 x m l 用自定义的标记来显示数据和结构化的信息，任何应用程序都可以方便访问x m l 文档中的数据和清楚理解标记的含义，自描述性使其非常适用于不同应用间的数据交换， 而这种交换并不需要事先定义好数据结构，所以自描述性使x m l 具有很强的开放性。 ( 5 ) 规范性 x m l 是标准通用标记语言s g m l 的一个子集，集成了s g m l 的大部分功能，所以x m l 文档具备一套严谨的语法结构，同时x m l 的语法比s g m l 更加简洁，这样更有利于x m l 解 释器对x m l 文档所含信息的获取。 ( 6 ) 灵活性 x m l 的灵活性主要表现在x m l 文档中数据和结构同x m l 文档的显示是互相分离的， 结构化的数据可以通过可扩展的样式表x s l 将数据呈现在不同的终端设备上，通过使用不 同的x s l 模版，可以将同一文档以不同的外部显示方式显示在浏览器上，使用户获得不同 的视觉感受，但其中所呈现的数据却是一样的f 2 0 1 。 2 2 2x m l 语法 x m l 是一种中介标记语言，用来创造标记语言( 比如h t m l ) 的元语言，可提供描述结 构化资料的格式，是一种描述性的语言。 x m l 文档就是由x m l 标记语言所定义的标记标注的符合x m l 语法规范的文档。x m l 文档由标记和文本数据组成，一个完整的x m l 文档由x m l 声明、处理指令和x m l 元素组 成【2 l 】。 ( 1 ) x m l 声明 x m l 声明是一个x m l 文档的开始，是一种处理指令。主要属性有v e r s i o n 、s t a n d a l o n e 和e n c o d i n g 等。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 文档都有一个根元素，根元素又嵌套着子元素，子元素又可以嵌套着自己的 子元素。一个元素包含一个起始标记和一个结束标记以及两个标记间的内容。标记可由用 户自己定义，具有很强的灵活性。为了更加清晰地描述数据，我们在x m l 文档中引入 c d a t a 数据块，块中所有的内容都可以看作字符数据。当然，x m l 文档也有自己的注释 语句，x m l 处理器不会对它们作任何处理【2 2 】。 如图2 2 所示x m l 文档的基本组成： 8 - 基于x m l 和概念层次树的数据挖掘研究 图2 2 x m l 文档基本组成 下面编写一个简单的x m l 文档。 1 1 声明 1 1 注释 根元素 b l a c k 子元素 m a l e l8 2 2 3x 池在数据挖掘中的应用 x m l 的应用在互联网非常进步的时代越来越实用，使用x m l 来存储、表示和交换的数 据越来越多，这些用x m l 来描述的众多文档可以被看做是一种数据库，那么既然是数据库， 当然希望从数据库里的众多数据中分析出可以供人们参考的规律或者是有用的信息，从而 利用分析的知识为我们做出一定的指导参考【2 3 】。 x m l 的简单、灵活、开放和通用等特点与越来越广泛的应用都说明x m l 的出现给予开 发者诸多的方便：x m l 可以唯一地表示各种类型的数据，并且使这些数据很容易地进行组 合、集成，从而可以通过对x m l 文档的搜索实现对各种类型数据的搜索2 4 1 。同时由于基于 w e b 的数据挖掘非常复杂，而且比单纯对关系数据库或者其它单一数据挖掘更加复杂，所 以x m l 的出现非常容易地解决了这些问题，为w e b 数据挖掘带来一道曙光。 9 - 基于x m l 和概念层次树的数据挖掘研究 第三章基于x m l 的数据挖掘系统设计 本文继承传统数据挖掘过程中数据准备、数据挖掘和知识确认与提炼三个部分，增加 了数据存储的部分，因为x m l 数据库是与其它关系型数据库的存储方式不同的专门针对 x m l 文档的特殊数据库【2 5 】。 总的说来本文提出的基于x m l 和概念层次树的数据挖掘框架包括四个部分：数据预处 理、x m l 数据库存储、x m l 数据挖掘和知识存储与表示，如图3 1 所示。 图3 1 基于x m l 和概念层次树的数据挖掘框架 3 1 数据源 数据的来源多种多样，有文本数据( w o r d 文档、文本文档等) 、w e b 数据和其它结构化 数据等等。文本是以文字串形式表示的数据文件，比如以t x t 为后缀的文件：w e b 数据常 见的是以h t m l 编写的数据，其实w e b 上的数据非常复杂，没有特定的模型描述；结构化 的数据就是有特定结构的数据，比如关系数据库中的表和视图等等。 3 2 数据预处理( 数据的x 化) 传统数据挖掘的数据预处理主要就是消除噪声或不一致的数据，并将多种数据源组合， 除此之外，本文为了给挖掘提供高质量统一的x m l 数据，还需要把各种来源的数据转换成 统一的符合x m l 文档规范的数据。所以数据预处理可以分为两个步骤：数据转换和数据 x m l 规范化【2 6 】。 3 2 1 数据转换 数据转换就是把各种类型的数据转换成x m l 数据，不同数据的结构特点是不一样的， 所以采取的转换技术也不一样。下面我们分别介绍各种类型数据向x m l 数据的转换。 ( 1 ) 在文本数据的转换中，以文字串形式表示的文本数据在转化成x m l 文件时比较麻 烦，需要通过手工编写文件用d o m 技术来解析代码。比如我们可以把两行字符串“a ，b ， c ，d 和l ，2 ，3 ，4 ，按照x m ls c h e m a 的语法，生成一棵d o m 树【2 7 】，其中根节点为 s t r i n g s 和子节点为c h a r s ，如图3 2 所示： l o 一 基于x m l 和概念层次树的数据挖掘研究 表3 1 t l b l e ：s t u d e n t s n a m eg e m d e ra g eh e i g h t t o mm a l e1 81 8 0 c m m a r yf e m a l e2 01 7 4 c m 转换后的x m l 文档： t o m m a l e 18 i8 0 c m m a r y f e m a l e 2 0 i7 4 c m 3 2 2 数据x m l 规范化 在把数据转换成x m l 文档后，必须再检测x m l 数据是否规范化，并且将不符合规范的 数据剔除，符合的保存到x m l 文档中。 3 3x m l 数据存储 x m l 数据存储是一个非常关键的问题，因为这直接影响到x m l 数据的挖掘。由于文件 系统不能存储大量的数据，并且数据的修改也非常麻烦，关系数据库和x m l 数据的转换也 经常出现问题，而面向对象的数据库又发展不够完善，所以使用x m l 数据库存储x m l 数据 是最好的选择。x m l 数据库可以将x m l 数据原样进行存储，便于对标记路径、层次化的数 据进行操作，非常简单和灵活，特别是将复杂的操作变得更加简单3 0 1 。 1 2 基于x m l 和概念层次树的数据挖掘研究 3 4 基于x m l 和概念层次树的数据挖掘 3 4 1 概念层次树 概念层次树( c o n c e p th i e r a r c h yt r e e ) 是数据库中各属性值和概念依据抽象程度不同而 构成的一个层次结构，是属性的一种概括语义的描述。概念分层对多个抽象层次上的挖掘 是非常有用的，对于给定的数值属性，概念分层定义了该属性的一个离散化。通过收集并 用较高层的概念替换较低层的概念，从而使数据得到规约。通过这种泛化，虽然牺牲了细 节，但泛化后的数据更有意义，更容易理解，占有的存储空间更少，还减少了大量的i o 操 作。概念分层以树状的形式表示，形成概念层次树。 ( 1 ) 概念层次树的生成 对于用户和领域专家，人工地生成概念层次树已经是非常耗时的工作。幸好许多分层 蕴含在数据库模式中，并且可以在模式定义级定义。概念分层常常自动地产生，或根据数 据分布的统计分析动态地加以提炼。用机器学习的方式来确定概念层次树的节点，机器根 据预设的参数和生成算法来自动生成概念层次树【3 ，这种方式生成的概念层次树可以很好 地反应数据分布的情况，但缺点是缺少人性化。 概念层次树按照建树的方式来看，概念层次树有自顶向下和自底向上两种方式。自顶 向下是指从概念层次树的根节点到叶子节点逐层生成，这种生成方式的优点是可以有效地 控制概念层次树过于庞大，缺点是缺少针对性；自底向上是指从概念层次树的叶子节点到 根节点逐层生成。依次扫描每一个属性值来确定其上一层的概念，然后对于上层次的概念 用同样的方式迭代生成更高层次的概念，这种方式针对性较强，但是底层的属性一旦发生 变化，概念层次树就会发生较大变化。 本系统采用人工生成和自动生成相结合的自底向上的方式来生成概念层次树，这种生 成方式需要领域专家的参与和机器学习相结合。根据x m l 文档中每个属性的出现频率值和 设定的阈值来构造概念层次树。通过计算各个属性的频率值和预设的阈值相比较，如果该 属性的频率值大于阈值，则把该属性放入概念层次树中。如果该属性小于阈值，则对该属 性进行泛化，重新设定一个概念层次，插入到初始的概念层次树中。若所有的属性都小于 阈值，则要对阈值重新设定。如图3 4 所示： l 基于x m l 和概念层次树的数据挖掘研究 图3 4 概念层次树的生成 以下是生成概念层次树c h t r e e ( c o n c e p th i e r a r c h yt r e e ) 的j a v a 代码： c h t r e e c r e a t e c h t r e e ( f i l ex m l f i l e ) i n tt h r e s h o l d = 1 0 0 ；设定阈值的大小为1 0 0 i n tn = 1 0 ；设定概念层次树的高度上限 c h t r e ec h t r e e = n u l l ；初始化一棵概念层次树 n o d e s e a r c h n o d e s ( x m l f i l e ) ； 扫描x m l f i l e 文件，找出所有节点 f o r ( i n ti = 0 ；i t h r e s h o l d ) a d d n o d e t o s e t ( n o d e i ) 将该属性放入概念节点集合中 e l s e c r e a t e n e w c o n c e p t ( n o d e i ) ；生成新的概念 ) i n s e r t n o d e t o c h t r e e ( m o d e i ) ； 将该属性插入概念层次树中 i f ( c h t r e e ) c h t r e e h e i g h t n ； s y s t e m o u t p r i n t l n ( “概念层次树的高度不能超过限定”) ； r e t u mn u l l ； r e t u r nc h