（计算机软件与理论专业论文）web数据挖掘中xml应用及关联算法改进.pdf

山东大学硕士学位论文 摘要 面向w e b 的数据挖掘是一项复杂的技术，w e b 数据挖掘就是利用数据挖掘技 术从网络文档和服务中发现和提取信息。w e b 上的信息五花八门，传统的 i n t e r n e t 由各种类型的服务和数据源组成，包括w w w 、f t p 、t e l n e t 等，现在有 更多的数据和端口可以使用，比如政府信息服务、数字图书馆、电子商务数据， 以及其他各种通过w e b 可以访问的数据库。 w e b 上各种形式的文档和用户访问信息就构成了w e b 数据挖掘的对象。根据 挖掘对象的不同，我们将w e b 数据挖掘分为三类：w e b 内容挖掘、w e b 结构挖掘、 w e b 用法挖掘。由于x m l 能够使不同来源的结构化的数据很容易地结合在一起， 因而使搜索多样的不兼容的数据库能够成为可能，从而为解决数据挖掘难题带来 了希望。 a p r i o r i 算法在关联规则领域有很大的影响力，然而由于需要过于频繁的扫 描数据库及较大的空间消耗，仍然有需要改进的地方。通过对a p r i o r i 算法进行 深入研究，本文提出了一种a p r i o r i 改进算法，通过比较分析，获得了较好的效 率和性能。 本文完成的主要工作如下： ( 1 ) 完成了对基于x m l 的w e b 数据挖掘的技术研究。本文通过对x m l 这种近几年 出现的具有很大潜力的i n t e r n e t 数据交换技术的研究分析，提出了基于x m l 的w e b 挖掘的新思路，并且完成了对x m l 的w e b 挖掘系统的系统功能设计。 ( 2 ) 实现了) ( m l 到数据库模式的转化工具。本文主要针对x y l 的d t d 文档，提出 了一系列从) ( m l 到关系数据库模式的转换算法，从而也就把基于x m l 的w e b 数据挖 掘与传统的基于关系数据模式的数据挖掘算法建立了联系。 ( 3 ) 对a p r i o r i 算法进行深入分析，并提出了一种优化算法。 关键字：w e b 数据挖掘、关联规则、煳l 、文本挖掘、a p ri o ri 算法 山东大学硕士学位论文 a b s t r a c t w e bm i n i n gi sac o m p l e xt e c h n o l o g y ，w h i c hr e f e rt ot h ep r o c e s so f i n f o r m a t i o no rr e s o u r c ed i s c o v e r yf r o mm i l l i o n so fs o u r c e sa c r o s st h e w o r l dw i d ew e b t h ed o c u m e n t sa n du s e ri n f o r m a t i o nu s e rb r o w s i n go n eo r m o r ew e bl o c a l i t i e sa r et h et a r g e to fw e bd a t am i n i n g w e bm i n i n gc a n d i v i d e di n t od a t am i n i n g 、s t r u c t u r em i n i n ga n dl o gm i n i n ga c c o r d i n gt o d i f f e r e n tm i n i n gt a r g e t a sx m lc a nc o m bi n es t r u c t u r a ld a t ae a s il y ，i t i sp o s s i b l et om i n i n gm u l t i p l ed a t a b a s e i nt h i sp a p e rw es t u d ya n dd i s c u s s t h eu s eo fx m la sd a t as w i t c hp a t t e r ni nw e bd a t am i n i n ga n dw e bl o gm i n i n g a r e a d a t am i n i n gi na s s o c i a t i o nr u l ei sa ni m p o r t a n tr e s e a r c ht o p i ca n d a p r i o r ii st h ec o r ea l g o r i t h mi nm i n i n ga s s o c i a t i o nr u l e w ep r o p o s ea m e t h o dt h a te n h a n c e st h ee f f i c i e n to fa l g o r i t h mb ye v a l u a t i n gt h e p r o b a b i 1i t yo fc a n d i d a t ef r e q u e n ti t e m s e t s i ts h o r t e n st h er u n t i m eo f a l g o r i t h mb yr e d u c i n gt h et i m e so fs c a n n i n gd a t a b a s e af o r m u l ai s p r o v i d e di nt h i sp a p e r i nt h i sp a p e rw ew a n tt od i s c u s st h eu s eo fx m lf o rt h ew e bm i n i n g a r e aa n da c c o m p l i s h e dt h ef o l l o w i n gt a s k s ： 1 s t u d yt h em e t h o dt h a ta p p li e st h ex m lt e c h n o l o g yi nt h ew e bm i n i n g as y s t e mo fw e bm i n i n gb a s e do nx m l i nt h i sp a p e rw es t u d yt h ei n t e r n e t d a t as w i t c ht e c h n o l o g yo fx m lr e c e n ty e a r s w ea d v a n c ean e wm e t h o do f d a t am i n i n gb a s e dx m l a n dw ed e s i g n e dt h ef u n c t i o no fd a t am i n i n gs y s t e m b a s e d f l 2 i m p l e m e n t et h ea l g o r i t h m sf r o mc o n v e r t i n gx m ld o c u m e n t si n t o r e l a t i o n a ld a t a b a s e i nt h i sp a p e rw ea d v a n c eag r o u po fm e t h o d so fs w i t c h x m li n t or el a ti o n a ld a t a b a s ep a t t e r n 3 b a s e do na s s o c i a t i o na n a l y s i s ，a l li m p r o v e da l g o r i t h mo fa p r i o r i i sp r e s e n t e di nt h ep a p e r k e yw o r d s ：w e b _ i n i n g a s s o o i a t i o n 。x m l t e x tm in i n g a p ri o ria i g o ri t h m i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：丛望过堕e t 期：! 竺堡。霎 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丐基婆垫导师签名： 山东大学硕士学位论文 第一章绪论 1 1 研究背景 w e b 上有海量的数据信息，怎样对这些数据进行复杂的应用成了现今数据库 技术的研究热点。数据挖掘就是从大量的数据中发现隐含的规律性的内容，解决 数据的应用质量问题。充分利用有用的数据，废弃虚伪无用的数据，是数据挖掘 技术的最重要的应用。 相对于w e b 的数据而言，传统的数据库中的数据结构性很强，即其中的数据 为完全结构化的数据，而w e b 上的数据最大特点就是半结构化。所谓半结构化是 相对于完全结构化的传统数据库的数据而言。显然，面向w e b 的数据挖掘比面向 单个数据仓库的数据挖掘要复杂得多。 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 是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 p l a n g u a g e ) 的一个子集。总的来说，x m l 是一种中介标示语言，可提供描述结构 化资料的格式：详细来说，x 儿是一种类似于h t 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 技术和通用的数据挖掘技术的发展都有很大的促进作用。 山东大学硕士学位论文 1 2 课题研究状况 1 2 1 数据挖掘技术的研究发展状况 数据挖掘是一个新兴的边缘学科，它汇集了来自机器学习、模式识别、数据 库、统计学、人工智能以及管理信息系统等各学科的成果。多学科的相互交融和 相互促进，使得这一新学科得以蓬勃发展，而且已初具规模。在美国国家科学基 金会( n s f ) 的数据库研究项目中，k d d 被列为9 0 年代最有价值的研究项目。人工 智能研究领域的科学家也普遍认为，下一个人工智能应用的重要课题之一，将是 以机器学习算法为主要工具的大规模的数据库知识发现。 1 9 8 9 年举行的第十一届国际联合人工智能学术会议上首次提出了从数据库 中发现知识( k d d ) 一词。到1 9 9 9 年为止，由美国人工智能协会主办的k d d 国际研 讨会已经召开了8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点 也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学 科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之 一，成为当前计算机科学的一大热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷 纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先 在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新 成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设计 的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值等 问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、数理统计分 析系统的联系和区别，以及相应的基本对策。6 篇论文摘要展示了k d d 在从建立 分子模型到设计制造业的具体应用。 不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威，另一份在线周刊为d s * ( d s 代表决策支持) ，1 9 9 7 年l o 月7 日开始出版。在网上还有一个自由论坛d me m a i l c l u b ，人们通过电子 邮件相互讨论d m k d 的热点问题。而领导整个潮流的d ( d 开发和研究中心，当数 设在美国e m d e n 的i b m 公司开发部。 尽管数据挖掘还是一个很新的研究课题，但它所固有的为企业创造巨大经济 2 山东大学硕士学位论文 效益的潜力，已使其很快有了许多成功的应用，具有代表性的应用领域有市场预 测、投资、制造业、银行、通讯等。 美国钢铁公司和神户钢铁公司利用基于数据挖掘技术的i s p a 系统，研究分 析产品性能规律和进行质量控制，取得了显著效果。通用电器公司( g e ) 与法国飞 机发动机制造公司( s n e c m a ) ，利用数据挖掘技术研制了c a s s i o p e e 质量控制系 统，被三家欧洲航空公司用于诊断和预测渡音7 3 7 的故障，带来了可观的经济效 益。该系统于1 9 9 6 年获欧洲一等创造性应用奖。 享有盛誉的市场研究公司，如美国的a c n i e l s o n 和i n f o r m a t i o n r e s o u r c e s ，欧洲的g f k 和i n f r a t e s tb u r k 等纷纷开始使用数据挖掘工具来应 付迅速增长的销售和市场信息数据。商家的激烈竞争导致了市场快速饱和，产品 的迅速更新，使得经营者对市场信息的需求格外强烈利用数据挖掘技术所形成的 市场预测能力和服务，使这些市场研究公司取得了巨大收益。 英国广播公司( b b c ) 也应用数据挖掘技术来预测电视收视率，以便合理安排 电视节目时刻表。信用卡公司a 1 l l e l i c a l lk x t ，r e s s 自采用数据挖掘技术后， 信用卡使用率增加了1 0 一1 5 。a t & t 公司赁借数据挖掘技术技术侦探国际电话 欺诈行为，可以尽快发现国际电话使用中的不正常现象。 中国的公安部门也在研究利用k d d 技术总结各类案件的共性和发生规律，从 而在宏观上制定最有效的社会治安综合治理的方案和措施；在微观上指出犯罪人 的特点，划定罪犯的范围，为侦破工作提供方向。 1 2 2w e b 数据挖掘现状及发展 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的应 用，使海量数据不断产生。随之而来的问题是如此多的数据让人难以消化，无法 从表面上看出他们所蕴涵的有用信息，更不用说有效地指导进一步的工作。如何 从大量的数据中找到真正有用的信息成为人们关注的焦点，数据挖掘技术也正是 伴随着这种需求从研究走向应用。 近年来，随着i n t e r n e t w e b 技术的快速普及和迅猛发展，使各种信息可以 以非常低的成本在网络上获得，由于i n t e r n e t w w w 在全球互连互通，可以从中 取得的数据量难以计算，而且i n t e r n e t l 舯的发展趋势继续看好，特别是电子 山东大学硕士学位论文 商务的蓬勃发展为网络应用提供了强大支持，如何在w w w 这个全球最大的数据集 合中发现有用信息无疑将成为数据挖掘研究的热点。 w e b 数据挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或 信息。w e b 数据挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、 统计学、人工智能中的机器学习和神经网络等。 尽管w e b 挖掘的形式和研究方向层出不穷，但随着电子商务的兴起和迅猛发 展，未来w e b 挖掘的一个重要应用方向将是电子商务系统。而与电子商务关系最 为密切的是用法挖掘( u s a g em i n i n g ) ，也就是说在这个领域将会持续得到更多 的重视。另外，在搜索引擎的研究方面，结构挖掘的研究已经相对成熟，基于文 本的内容挖掘也已经有许多研究，下一步将会有更多的研究者把多媒体挖掘最为 研究方向。 1 2 3x 札技术的研究发展状况 1 9 9 8 年2 月万维网协会( w 3 c ) 设计了x m l ，它是s g m l 的一个子集，是针对s g m l 和h t m l 的局限性而创立的。它既具有s g m l 的强大功能和可扩展性，同时又具有 h t m l 的简单性。s g m l 中所有非核心的、未被使用的和含义模糊的部分都被删除， 剩下的就成为短小精悍的标记工具x m l 。x m l 保留了s g m l 8 0 的功能，而其复杂 程度则降低到原来的2 0 ( ) ( m l 的规范只有2 6 页，而当初s g m l 的规范却长达5 0 0 页之多) 。 x m l 不像h t m l 那样仅仅应用于w e b 站点，它在电子商务、数据库、知识管理、 数据交流与共享、自然语言转换等方面都有广泛应用。2 0 0 0 年以后x m l 在计算 机科学外的科技领域也得到了应用，例如：m a t h x m l ( 数学x m l ) 、c m l ( 化学煳l ) 、 a m l ( 天文x m l ) 等语言，它们使得专业语言的表示不再困难。 1 2 4 采用l 的w a b 数据挖掘的研究发展状况 2 0 0 0 年以后，国内外把x m l 和数据挖掘结合起来的研究逐渐增多，由于x m l 广泛应用于w e b 上，因此基于x m l 的w e b 挖掘( w e bm i n i n g ) 的研究越来越受到重 视，研究的w e bm i n i n g 包括w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘。现在 x m l 正在成为i n t e r n e t 上数据描述和交换的标准，并且在将来x m l 将代替h t m l 4 山东大学硕士学位论文 | 量皇_ _ n npm | 皇量皇量量量量置墨寡量量置量暑置 而成为w e b 上驻留数据的主要格式，为了将现有的w e b 网页转换为x m l 文档，已。 提出了w m a ( w e bm i n i n ga g e n t ) 系统，现今普遍认为的数据挖掘形式可以分为知 识发现和预言挖掘两大类，上述绝大部分文献在研究基于x m l 的数据挖掘应用 时，往往只注意到了x m l 在w e bm i n i n g 方面的应用，这只是一种基于x m l 文档 的知识发现。而对于x m l 在数据挖掘预言模型中的应用研究的不是太多。x m l 在 数据挖掘预言模型中的主要应用是p m m l ( p r e d i c t i v em o d e lm a r k u pl a n g u a g e ) ， 它是一种基于m m l 的语言，用来对数据挖掘预言模型进行描述和定义。它是由国 际化组织数据挖掘工作组( d a t am i n i n gg r o u p ，简称d m g ) 提出的，它描述了大量 不同的模型，包括预言模型、聚集和关联规则等。 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 概述；第三章， w e b 数据挖掘概述：介绍了w e b 数据挖掘的概念、分类及其介绍等：第四章，基 于x m l 的w e b 数据挖掘技术；第五章，系统设计及a p r i o r i 算法的改进；第六章， 结束语。 第二章数据挖掘技术及x m l 概述 2 1 数据挖掘技术 2 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 ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理 解的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘” 知识。 数据挖掘是在大型数据存储库中，自动地发现有用信息的过程。数据挖掘技 术用来探查大型数据库，发现先前未知的有用模式。数据挖掘还具有预测未来观 测结果的能力，例如，预测一位新的顾客是否会在一家百货公司消费1 0 0 美元以 上。 并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查 找个别的记录，或通过因特网的搜索引擎查找特定的w e b 页面，则是信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 领域的任务。虽然这些任务是重要的，可能涉及使 用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明 显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术 也已用来增强信息检索系统的能力。 数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 不可缺少的一部分，而k d d 是将未加工的数据转换为有用信息的整个过程，如图 1 - 1 所示。该过程包括一系列转换步骤，从数据的预处理到数据挖掘结果的后处 理。 输入数据叶二三三三三三二三三三三_l信息 图2 1 数据库中知识发现( 1 d ) 过程 输入数据可以以各种形式存储( 平展文件、电子数据表或关系表) ，并且可 以驻留在集中的数据存储库中，或分布在多个站点上。数据预处理的目的是将未 加工的输入数据转换成适合分析的形式。数据预处理涉及的步骤包括融合来自多 个数据源的数据，清洗数据以消除噪声和重复的观测值，选择与当前数据挖掘任 务相关的记录和特征。由于收集和存储数据的方式可能有许多种，数据预处理可 能是整个知识发现过程中最费力、最耗时的步骤。 6 山东大学硕士学位论文 2 1 2 数据挖掘的任务 通常，数据挖掘任务分为下面两大类： 1 预测任务。这些任务的目标是根据其他属性的值，预测特定属性的值。 被预测的属性一般称目标变量( t a r g e tv a r i a b l e ) 或因变量( d e p e n d e n t v a r i a b l e ) ，而用来做预测的属性称说明变量( e x p l a n a t o r yv a r i a b l e ) 或自变量( i n d e p e n d e n tv a r i a b l e ) 。 2 描述任务。这里，目标是导出概括数据中潜在联系的模式( 相关、趋势、 聚类、轨迹和异常) 。本质上，描述性数据挖掘任务通常是探查性的，并 且常常需要后处理技术验证和解释结果。 图2 - 2 展示了四种主要数据挖掘任务。 。 ，) 膏鼻 一l 鲁 一- e 。i 埝需多。谚n 式! = ；善雾沙。 l ： ：；纛 孑臣 一 。删：，坼 8：” q “社 。靴 = 芗- 黧47 ：j囊77罩i 。j孱隶。j 。警簿 雯啼管二势， 图2 2 四种主要数据挖掘任务 预测建模( p r e d i c t i v em o d e l i n g ) 涉及以说明变量函数的方式为目标变量 建立模型。有两类预测建模任务：分类( c l a s s i f i c a t i o n ) ，用于预测离散的目 标变量；回归( r e g r e s s i o n ) ，用于预测连续的目标变量。例如，预测一个w e b 用户是否会在网上书店买书是分类任务，因为该目标变量是二值的。另一方面， 预测某股票的未来价格是回归任务，因为价格具有连续值属性。两项任务目标都 是训练一个模型，使目标变量预测值与实际值之间的误差达到最小。预测建模可 以用来确定顾客对产品促销活动的反应，预测地球生态系统的扰动，或根据检查 结果判断病人是否患有某种特定的疾病。 关联分析( a s s o c i a t i o na n a l y s i s ) 用来发现描述数据中强关联特征的模式。 7 澍 拇渚 山东大学硕士学位论文 所发现的模式通常用蕴涵规则或特征子集的形式表示。由于搜索空间是指数规模 的，关联分析的目标是以有效的方式提取最有趣的模式。关联分析的应用包括找 出具有相关功能的基因组、识别一起访问的w e b 页面、理解地球气候系统不同元 素之间的联系等。 聚类分析( c l u s t e ra n a l y s i s ) 旨在发现紧密相关的观测值组群，使得与属 于不同簇的观测值相比，属于同一簇的观测值相互之间尽可能类似。聚类可用来 对相关的顾客分组、找出显著影响地球气候的海洋区域以及压缩数据等。 异常检测( a n o m a l yd e t e c t i o n ) 的任务是识别其特征显著不同于其他数据 的观测值。这样的观测值称为异常点( a n o m a l y ) 或离群点( o u t l i e r ) 。异常检 测算法的目标是发现真正的异常点，而避免错误地将正常的对象标注为异常点。 换言之，一个好的异常检测器必须具有高检测率和低误报率。异常检测的应用包 括检测欺诈、网络攻击、疾病的不寻常模式、生态系统扰动等 2 1 3 各种分析方法的简介 数据挖掘中用到的分析方法大体可以分为如下六种。 1 分类( c l a s s i f i c a t i o n ) 。首先从数据中选出已经分好类的训练集，在该训 练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行 分类。 注意：类的个数是确定的，预先定义好的 2 估值( e s t i m a t i o n ) 。估值与分类类似，不同之处在于，分类描述的是离散 型变量的输出，而估值处理连续值的输出：分类的类别是确定数目的，估值 的量是不确定的。一般来说，估值可以作为分类的前一步工作。给定一些输 入数据，通过估值，得到未知的连续变量的值，然后，根据预先设定的阂值， 进行分类。例如：银行对家庭贷款业务，运用估值，给各个客户记分 ( s c o r e o 1 ) 。然后，根据阈值，将贷款级别分类。 3 预言( p r e d i c t i o n ) 。通常，预言是通过分类或估值起作用的，也就是说， 通过分类或估值得出模型，该模型用于对未知变量的预言。从这种意义上说， 预言其实没有必要分为一个单独的类。预言其目的是对未来未知变量的预 测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准 确性是多少。 8 山东大学硕士学位论文 4 相关性分组或关联规则( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l e s ) 决定 哪些事情将一起发生。 5 聚集( c l u s t e r i n g ) 。聚集是对记录分组，把相似的记录在一个聚集里。聚 集和分类的区别是聚集不依赖于预先定义好的类，不需要训练集。聚集通常 作为数据挖掘的第一步。例如，“哪种类的促销对客户响应最好? ，对于 这一类问题，首先对整个客户做聚集，将客户分组在各自的聚集里，然后对 每个不同的聚集，回答问题，可能效果更好。 6 描述和可视化( d e s c r i p t i o na n dv i s u a l i z a t i o n ) 是对数据挖掘结果的表 示方式。 2 1 4 数据挖掘的流程 数据挖掘的流程包括如下四步： 1 定义问题：清晰地定义出业务问题，确定数据挖掘的目的。数据准备：数 据准备包括：选择数据一在大型数据库和数据仓库目标中提取数据挖掘的目 标数据集；数据预处理一进行数据再加工，包括检查数据的完整性及数据的 一致性、去噪声，填补丢失的域，删除无效数据等。 2 数据挖掘：根据数据功能的类型和和数据的特点选择相应的算法，在净化和 转换过的数据集上进行数据挖掘。 3 结果分析：对数据挖掘的结果进行解释和评价，转换成为能够最终被用户理 解的知识。 4 知识的运用：将分析所得到的知识集成到业务信息系统的组织结构中去。 2 1 5 数据挖掘技术实现 在技术上可以根据它的工作过程分为：数据的抽取、数据的存储和管理、数 据的展现等关键技术。 1 数据的抽取 数据的抽取是数据进入仓库的入口。由于数据仓库是一个独立的数据环境， 它需要通过抽取过程将数据从联机事务处理系统、外部数据源、脱机的数据存储 介质中导入数据仓库。数据抽取在技术上主要涉及互连、复制、增量、转换、调 9 山东大学硕士学位论文 度和监控等几个方面的处理。在数据抽取方面，未来的技术发展将集中在系统功 能集成化方面，以适应数据仓库本身或数据源的变化，使系统更便于管理和维护。 2 数据的存储和管理 数据仓库的组织管理方式决定了它有别于传统数据库的特性，也决定了其对 外部数据的表现形式。数据仓库管理所涉及的数据量比传统事务处理大得多，且 随时间的推移而快速累积。在数据仓库的数据存储和管理中需要解决的是如何管 理大量的数据、如何并行处理大量的数据、如何优化查询等。目前，许多数据库 厂家提供的技术解决方案是扩展关系型数据库的功能，将普通关系数据库改造成 适合担当数据仓库的服务器。 3 数据的展现 在数据展现方面主要的方式有： 查询：实现预定义查询、动态查询、o l a p 查询与决策支持智能查询；报表： 产生关系数据表格、复杂表格、o l a p 表格、报告以及各种综合报表；可视化： 用易于理解的点线图、直方图、饼图、网状图、交互式可视化、动态模拟、计算 机动画技术表现复杂数据及其相互关系；统计：进行平均值、最大值、最小值、 期望、方差、汇总、排序等各种统计分析；挖掘：利用数据挖掘等方法，从数据 中得到关于数据关系和模式的知识。 2 2x 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 ) 是从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 p l a n g u a g e ) 发展而来的一种新的标记语言，由x m l 工作组( 原称s g m l 编审部，于 1 9 9 6 年由w 3 c 主持下成立) 开发，其标准定义是于1 9 9 8 年2 月由w 3 c 批准通过 的。x m l 的目标不在于给w e b 页面增加趣味性，而在于它想通过一种方法对文档 和数据进行结构化处理，从而使其能在部门、客户和供应商之间进行交换。 2 2 1 潮l 的基本内容 x m l 用于对文档进行数字化的表示，把文档转化成某种计算机可读的代码， 使计算机可对这些文档进行诸如存储、处理、查询、传送、显示和打印等工作。 为了使计算机能够有效地处理这些文档，就必须告诉它文档的结构。 l o 山东大学硕士学位论文 - - - -i l 量皇置鼻量| 置量置量一 1 元素与属性：逻辑结构 大多数文档( 如书本和杂志) 都可分成一些组件( 如章节和文章) ，这些组件又 可以分为一些更小的组件( 如标题、段落、图形等等) ，而文档中的具体内容用文 本表示。在) ( m l 中，组件称为元素，表示具体内容的文本称为文档的字符数据。 】( m l 元素用来描述文档的逻辑结构。煳l 文档的这种层次结构见图2 - 3 ： 论文 i 一标题 i ，一摘要 ： ： ；r 一。段落 i i 。一 ；段落 l - 一章节 广厂一o 。 ： ：r 。段落 i ；r - 段落 ii !段落 i 一章节 一章节 图2 - 3 ) ( m l 文档的树形结构 其中，包含所有元素的元素( 如论文) 称为根元素，它是没有前导元素的唯一 元素。根元素直接包含的元素称为子元素，它们也可以包含自己的子元素。元素 还可以包含相关信息，这些信息称为属性，属性用以描述元素的一些特征。 2 实体：物理结构 煳l 提供了一种机制，可以使文本线性地组织，即以多片( m u l t i p l ep i e c e s ) 的形式组织。“文本片这个概念称为实体，每个实体都有名字。x m l 元素是描 述文档的逻辑结构，而实体是描述组成x m l 文档的字节块的位置，即描述文档的 物理结构。 在文档中，可以通过插入实体引用来使用实体，x m l 处理器将会用实体替换 相应的实体引用，这过程称为文本替换。这样，同一文本可在很多不同的环境 中自动地重复使用，在某一处的更新就可以影响到使用这一文本的所有地方，这 种特性称为外部实体。非x m l 对象( 包括图形、电影、声音、原始文本p d f ，h t m l 等) 也可以用同样的方式引用，称为不可分析的实体，也称为数据实体。 3 标记 元素构成x m l 的树形文档，实体管理文档的尺寸和复杂性。而描述文档的逻 山东大学硕士学位论文 辑结构、连接物理实体的记号称为标记。x m l 文档就是由标记和字符数据构成的。 两者都使用u n i c o d e ，都称为x m l 文本，即字符数据+ 标记= x m l 文本。 为了区别于字符数据，标记使用一种特殊的字符，这种字符称为分隔符。最 常见的分隔符是小于号( “ ) 、或与号( “”) 和分号( “；”) 。 在h t m l 和基于s g m l 的语言中都使用了类似的语法。 4 文档类型 文档类型是根据其中的元素定义的。如果两个文档包含了完全不同的元素， 或虽然元素相同，但它们以完全不同的方式组合在一起，那么它们很可能不属于 同一种文档类型。 如果是一个x m l 文档，它必须有某种由元素、属性和组件构成的结构。在为 文档创建样式表的时候，要根据这个结构知道其中的元素，根据元素类型名称知 道它们的含义，然后根据元素确定在何处显示。这种结构就是文档类型。 在x m l 中，可以使用文档类型定义( d o c u m e n tt y p ed e f i n i t i o n 一”d t d ”) 形 式化文档类型，也可以用说明来描述这种文档的结构，但使用d t d 可以让) a i l l 文 档的书写者更专注于自己的工作。 2 2 2x m i _ 的特点和应用范围 x m l 的优势在于它有以下突出特点： 1 良好的可扩展性：在没有x m l 的时候，要想定义一个标记语言并推广利用它 非常困难。而现在x m l 允许各个不同的行业根据自己独特的需要制定自己的 一套标记，并能迅速投入使用，使得制定新的标记语言简单易行。 2 内容的自描述性：x m l 是面向内容的标记语言，在x m l 中的标记一方面限定 了元素的层次结构，另一方面也说明了元素的含义。在) 眦的搜寻结果中由 标记就可知道内容的含义，这也使得搜寻结果更有意义。 3 数据内容与形式的分离- x m l 不仅允许自定义一套标记，而且这些标记不必局 限于显示格式的描述。x m l 允许根据各种不同的规则来制定标记，比如商业 规则，根据数据描述甚至根据数据关系来制定标记。x m l 是自描述语言，在 x m l 中显示样式从数据文档中分离出来放在样式单文件中：在舭中数据检 索可以简单高效地进行。 山东大学硕士学位论文 4 严格的语法要求：严格的语法要求固然表面上显得繁琐，但一个具有良好语 法结构的文档可提供良好的可读性和可维护性，长远来看大有裨益。 5 显示的多样性：x m l 一个非常鲜明的特点是把数据的显示格式和数据的表示 分离。在x y l 中，可以用格式文件如x s l ( e x t e n s i b l es t y l el a n g u a g e ) 来定 义x m l 的显示格式，也可以利用h t m l 作为x m l 的显示模板，把x m l 数据以 数据岛的形式内嵌到h t m l 页面中，这种分离可以实现不同数据源数据的无 缝连接，各种数据可以在中间件上转换为x m l 格式，使得数据很容易地进行 在线交换和传输。 x m l 可应用于如下方面： 1 - 网络客户必须在不同的数据库间传递信息的应用； 2 需要把大部分从服务器下载的数据放到用户端处理的应用： 3 相同的数据对于不同的用户需要有不同的界面的应用； 4 网络情报供应商要把发现的信息精心裁剪，并发送给不同个人用户的应用； 5 在w e b 上发布数据，使w e b 数据更有效地管理： 6 自然语言翻译； 7 w e b 商务应用。 2 2 3x 札与其他文档和数据模型的区别 普通的文本文档是无结构文档，而x m l 文档在某种意义上是一种半结构化数 据。这是因为x m l 文档具有半结构化数据的某些基本特性：结构不规则、结构易 变、结构自包含。但是x m l 文档和普通的半结构化数据模型有很大的不同： 1 有效的x m l 文档具有d t d ，而d t d 则表示了x m l 文档的模式信息。而普通半 结构化数据模型则没有包含这一特点。 2 在普通半结构化数据模型中，标记是标注在边上的；而在x m l 数据模型中， 标记是标注在节点上的。当两个模型都是树结构的时候，这两者是可以相互 转换的，因此也是等价的。而当两个模型是图结构的时候，两者则不是等价 的。当然，在某些应用背景下，x k l l 文档被认为是一个树模型，而另外一些 应用背景下，x m l 文档被认为是图模型( 通过i d ，i d r e f ，i d r e f s 来表明元素之 间的引用关系) 。 山东大学硕士学位论文 3 在x m l 文档中，各个属性和子元素是有次序的，虽然很多场合下，次序是被 忽略的。而普通半结构化数据模型o e m 中，是不考虑次序的。 4 x m l 文档具有属性的概念，普通半结构化数据中没有相应的概念。 5 x m l 文档可以包含处理指令和注释等内容，而普通半结构化数据则没有。 作为h t m l 的扩展，x m l 和h t m l 也有很大的不同： 1 x m l 文档中可以包含d t d ，而h t m l 文档则没有。 2 x m l 文档中的标签是用户自定义的，而h t m l 文档中的标签则是预先由w 3 c 定 义。 3 h t m l 文档主要是用来显示的，是主要给人看的。而x b l l 文档主要用来数据的 存储和交换，主要是用于计算机处理的，其中的标签表明了内嵌内容的大致 信息。 2 2 4x m l 数据处理 数据存取机制 从整体上讲，x y l 定义了应用间传递数据的结构，而且这种结构的描述不是 基于二进制的只能由程序去判读的代码，而是一种简单的能够用通用编辑器读取 的文本。图2 - 4 表示了b i l 的数据存取机制。 图2 - 4x m l 数据存取机制 b t l 数据源多种多样，根据具体的应用，大概可分为下面三种：第一种是x m l 纯文本文档：第二种是关系型数据库：第三种则来源于其他各种应用数据，如邮 1 4 山东大学硕士学位论文 件、目录清单、商务报告等。其中，第一种来源，即x m l 纯文本文档是最基本的 也是最为简单的，将数据存储于文件中，其最大的优点在于可以直接方便地读取， 或者加上样式信息在浏览器中显示，或者通过d o m 接口编程同其他应用相连。第 二种数据来源是对第一种来源的扩展，其目的是便于开发各种动态应用，其优点 则在于通过数据库系统对数据进行管理，然后再利用服务器端应用( 如a s p ，j s p ， s e r v l e t ) 等进行动态存取。这种方式最适合于当前最为流行的基于三层结构的应 用开发，也是本系统所主要面对的数据来源。 对于g t 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 存取技术。d o m 是w 3 c 的一种技术标准，实际上 是提供一组a p i 来存取) ( m l 数据。d o m 可以通过j a v a s c r i p t ，v b s c r i p t 等脚本 程序来实现，也可通过c + + ，j a v a 高级语言来实现。 其次，也可通过d s o ( d a t as o u r c eo b j e c t ) 进行x m l 的数据绑定可以方便地 将x m l 节点同h t m l