(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf_第1页
(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf_第2页
(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf_第3页
(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf_第4页
(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf_第5页
已阅读5页,还剩54页未读, 继续免费阅读

(计算机软件与理论专业论文)基于web+service技术的分布式并行数据挖掘研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

基于w e bs e r v i c e 技术的分布式并行数据挖掘研究 学科:计算机软件与理论 研究生签字:男,妒争足 指导剂黼:锄髟 摘要 数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价 值的知识和规则。它是近年来企业用以分析大型数据集的核心技术和知识发现过程中的关 键步骤。 l u t c m c t n t r a n c t 的高速发展促进了数据库技术的深入应用,由于安全及通信成本、效 率等多方面的原因,大量的分散数据不可能集中起来处理。同时,对挖掘系统的开放性和 易用性的要求越来越高。分布式的数据挖掘就是在这样的背景下提出的。针对以上问题, 本文讨论了一个基于w e b 服务的数据挖掘系统结构。它将w e b 服务这技术引入了数据 挖掘,并在解决上述问题方面做了一些尝试。 本文在一个关联规女| 挖掘的弗行算法c d 算法的基础上,给出了一种基于动态数据集 划分的并行关联规则挖掘算法。实验表明它能更好地实现负载平衡,提高并行数据挖掘的 效率。然后本文基于w e bs e r v i c e 技术设计了一个数据挖掘系统平台,只要遵循我们的数 据模型接口和挖掘模型接口,新的数据挖掘算法可以很容易地集成到系统中来。并且,我 们的平台也是一个具有实际应用价值的、开放的和便于移植的挖掘系统框架。同时,为了 避免大量数据传输造成的效率问题,本文将s m = tc l i e n t 框架引入了这个数据挖掘系统平 台,让客户可以选择数据挖据是在客户端进行还是在服务器端进行,以充分地利用客户端 资源。 关键词:数据挖掘;分布式数据挖据;w e b 服务;关联规则;并行数据挖据 ar e s e r c ho f d i s t r i b u t e da n dp a r a l l e ld a t am i n i n gb a s e do nw e bs e r v i c e d i s c i p l i n e :c o m p u t e rs o f t w a r ea n dt h e o r y s t u d e n ts t 。m 。川朋讲锄如 s u p e r v i s 。rs i g n a t u r e :召易? 多五犯7 维新 n a t am i n i n ga c q u i r e sk n o w l e d g ea n dr u l e st h a ti sc o n n o t a t i v e u n k n o w na n d h a v i n g p o t e n t i a l v a l u ef o r d e c i s i o n - m a k i n g f r o m l a r g ed a t 曲a s e s o r d a t aw a r e h o u s e s i ti s r e c e n t l yk e yt e c h n o l o g i e sf o ra ne n t e r p r i s et oa n a l y z e l a r g ed a t a - s e t sa n d ak e ys t e pi nk n o w l e d g ed i s c o v e r yp r o c e s s t h er a p i dd e v e l o p m e n to fi n t e r n e t i n t r a n e tm a k e sag r e a tp r o g r e s si nd a t a b a s e a p p l i c a t i o n s s i n c et h es e c u r i t ya n dc o s to fc o m m u n i c a t i o na n de f f i c i e n c yo ft h e a p p l i c a t i o n s ,c o l l e c t i n g a n d i n t e g r a t i n g al a r g ea m o u n to f d a t af r o m i n t e r n e t i n t r a n e ts i t e sa r en o tp r a c t i c a lw a y s a tt h es s m et i m e ,m o r ea n dm o r e d e m a n d sh a v ea d d r e s s e do nt h eo p e n i n ga n de a s ya c c e s s i b i l i t y t h ed i s t r i b u t e dd a t a m i n i n ga r i s e sf r o mt h i ss i t u a t i o n ad i s t r i b u t e dd a t am i n i n gs y s t e mb a s o do nw e b s e r v i c ei sg i v e di nt h i sp a p e r i ti n t r o d u c e sw e bs e r v i c ei n t od a t em i n i n ga n dt a k e s s o m et e n t a t i v ee f f o r t si ns o l v i n gt h ea b o v e l i l e n t i o n e d p r o b l e m s o nt h eb a 。s i so f c da l g o r i t h m ,ap a r a l l e la l g o r i t h mf o rm i n i n ga s s o c i a t i o n r u l e s b a s e do nd y n a m i cd a t a s e tp a r t i t i o ni sp r e s e n t e di nt h i sp a p e r t h et e s ts h o w s t h a tt h i sa l g o r i t h mc a ns o l v et h ep r o b l e mo fl o a db a l a n c eb e t t e r ,s oi tc a ni m p r o v e t h ee f f i c i e n c yo fd a t am i n i n g t h ed e s i g no fad a t am i n i n gp l a t f o r mb a s e do nw e b s e r v i c ei sp r e s e n t e di nt h i sp a p e r c o m p l y i n gw i t ho u rd a t ao b j e c ti n t e r f a c ea n d m i n i n gm o d e li n t e r f a c e ,n e wm i n i n ga l g o r i t h m sc a nb ee a s i l yi n t e g r a t e dt oo u rs y s t e m o u rp l a t f o r ma l s oi sav a l u a b l e 、o p e na n de a s y t o - u p g r a d es y s t e ms k e l e t o nf o rd a t a m i n i n ga p p l i c a t i o n t oa v o i dt h ep r o b l e mo ft h et r a n s p o r to fal a r g en u m b e ro f d a t a ,t h ef r a m e w o r ko fs m a r tc 1i e n ti si n t r o d u c o di n t ot h ed a t am i n i n gp l a t f o r m i nt h i sp a p e r t h ec l i e n tc a nc h o o s ew h e t h e rd a t am i n i n gt a k ep l a c ei nt h ec l i e n t e n do ri nt h es e r v i c ee n d ,w h i c hc a nm a k eg o o du s eo ft h er e s o u r c e so ft h ec l i e n t e n d k e yw o r d s :d a t am i n i n g :d i s t r i b u t e d d a t am i n i n g :w e bs e r v i c e :p a r a l l e ld a t a m i n i n i n g 1 绪论 1 绪论 本章首先介绍了数据挖掘的基本知识,包括数据挖掘产生的背景,数据挖掘的功能, 数据挖据技术的发展情况及存在的问题。然后,介绷e bs e r v i c e 技术的产生背景,发展情 况及其特点。最后,以基于w e bs e r v i c e 技术的分布式并行数据挖掘研究为中心出发点,对 数据挖掘系统的一般结构演化,数据挖掘软件的发展进行了分析与总结,指出w e bs e r v i c e 技术对设计开放的数据挖掘系统的重要作用。同时,指出本文的主要工作:基于w e b s e r v i c e 技术的分布式并行数据挖掘的研究。 1 1 1 数据挖掘技术 随着计算机在社会各领域的广泛深入应用,如何处理数量日益增长的数据成为当今数 字化社会面临的一个极具挑战性的问题。在测绘领域,各种先进的测绘工具( 如卫星遥感、 传感器使用) 的应用每天都在产生数量巨大的数据;在金融业,己经计算机化的业务管理系 统也在不断的积累大量的数据:在商业领域中,由于p o s 机和条形码的应用,很多零售企业 每天都在增加大量的业务记录:i - f f e 刚既领域的迅猛发展使得网络中的各种信息日益丰富。 面对大量的g b 级、t 8 级甚至更多的数据,有效的提取出其中蕴含的有价值的知识和信息就 变得具有重要意义,但使用传统的统计和人工判别的方法己经不可能处理如此大量的数据, 需要种智能化、自动化的知识提取工具。在这种背景下,产生了数据挖掘( d a t am i n i n g ) , 通过使用数据挖掘,人们可以从大量数据中得到有益的知识。 数据挖掘( d a t am i n i n g ) 是指从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程 ”j 。抽取的知识是一组规则的集合,这些规则是对数据库中数据属性、模式( p a t t e r n ) 产生 频度、对象簇集等的描述。它是一种新的商业信息处理技术,它对商业数据库中的大量业 务数据进行抽取、转换、分析和其他模型化处理,从中提取辅助商业决策的关键性数据。 最近,一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远 影响的五大关键技术”之首,并且还将并行处理体系和数据挖掘列为未来五年内投资焦点 的十大新兴技术前两位。目前,数据挖掘己经成为数据库系统、人工智能和决策支持研究 方面一个重要的课题,是个新兴的具有广泛应用前景的研究领域。由于其应用范围极其 广泛,可应用于政府管理决策、科学研究、商业经营、企业决策支持等众多领域,所以数 据挖掘被视为一项回报率很高的重要应用技术。学术界和产业界对其高度重视,世界各国 都投入了大量的人力物力进行研究、开发, 目前已取得了一定的进展。其研究和应用前途 不可限量。 数据挖掘( d a t am i n i n g ) 这个术语首先出现在1 9 8 9 盆e 8 月在美国底特律召开的第l l 届国 际人工智能联合会议的专题讨论会上,1 9 9 1 ,1 9 9 3 和1 9 9 4 年又接着继续举行数据挖掘和知 识发现专题讨论会。随着参加会议人数的增多,从1 9 9 5 年开始,每年都要举办一次数据挖 西安工业大学硕士学位论文 掘国际会议。从9 7 年开始,数据挖掘拥有了自己的专门杂志( k n o w l e d g ed i s c o v e r ya n dd a t a m i n i n g ) 。除了对理论和技术的研究外,也出现了相当数量的数据挖掘产品和应用系统,并 且获得了一定的成功,得到了产业界的广泛关注。目前国外较有影响的数据挖据系统或系 统原型有: d b m i n e r i z l :加拿大s i m o nf r a s e r 大学开发的一个多任务数据挖掘系统,它的前身是 d b l e a r n 。系统设计的目的是把关系数据库和数据挖掘集成在起,以面向属性的多级概念 为基础发现各种知识。d b m i n e r 系统具有如下特色:能完成多种知识的发现:泛化规贝4 、 特性规则、关联规则、分类规则、演化知识、偏离知识等:综合了多种数据挖掘技术: 面向属性的归纳、统计分析、逐级深化发现多级规则、元规则引导发现等方法;提出了 一种交互式的类s 叫语言一一数据挖掘查询语言瑚q l ;能与关系数据库平滑集成;实现 了基于客户、服务器体系结构的u n i x 和p c ( w i n d o w s n t ) 版本的系统。 q u e s t :i b m 公司a l m a d e n 研究中心开发的一个多任务数据挖掘系统,目的是为新一代决 策支持系统的应用开发提供商效的数据开采基本构件。系统具有如下特点:提供了专门 在大型数据库上进行各种开采的功能:关联规则发现、序列模式发现、时间序列聚类、决 策树分类、递增式主动开采等;各种开采算法具有近似线性( o ( n ) ) 计算复杂度,可适用 于任意大小的数据库;算法具有找全性,即能将所有满足指定类型的模式全部寻找出来; 为各种发现功能设计了相应的并行算法。 e x p l o r e :由德国国家计算机科学研究中心开发,是一个多模式、多策略发现的数据挖 掘系统; k d w + :由g t e 的k p i a t e t s k y - s h a p i r o 等开发,采用多策略发现和统计方法; 国外主要商业产品系统有: i b mi n t e l l i g e n tm i n e r :由i b mc o r p 开发,是一个采用了多种技术的系统; d a r w i n :由t h i n k i n gm a c h i n e sc o r p 开发,使用了神经网络、遗传算法等; d a t a e r l g i n e :由m i tg 岫h 开发,使用神经网络、模糊逻辑、信号处理等方法: k n o w l e d g es e e k e r :由a n g o s ss o f t w a r el t d 开发,主要使用了规则发现、决策树等 方法。 国内对数据挖掘技术的研究从九十年代开始,主要以理论研究为主。其中具有代表性 的成果有李德毅等提出的发现状态空间理论和隶属云理论、中国科技大学对元模式制导知 识发现的研究等。也有一些应用系统出现。如南京大学计算机系开发的k n i g h t 系统。 1 1 2w e bs e r v i c e 技术 对于什么是w e bs e r v i c e s - - 直没有一个明确的答案,在2 0 0 2 年1 月于旧金山召开的w e b s e r v i c e s 会议就“新代bs e r v i c e s ”的议题进行了讨论。与会者得到的较为一致的看 法认为:w e bs e r v i c e s 是一种基于组件的软件平台,是面向服务的i n t e r n e t 应用。通过对 w e bs e r v i c e s 的构建,人们可以勰望得到个可编程的i n t e r n e t 。这个观点包括了两层含 义:首先,! e bs e r v i c e s 应是应用于i n t e r n e t 的,而不是限于局域网或试验环境。这要求 提出的w e bs e r v i c e s 框架必须适用于现有的i n t e r n e t 软件和硬件环境,即服务的提供者所 提供的服务必须具有跨平台、跨语言的特性。其次,w e bs e r v i c e s 所提供的服务不仅是向 人,更需服务于其它应用系统。现有的w e b 网站也可以认为是面向服务的,但这种服务仅仅 2 西安工业大学硕士学位论文 可以提供给人使用( 只有人类才可以读懂测览器下载的页面) 。而新一代l 拘w e bs e r v i c e s 所 提供的服务应能被机器所读懂,例如其它应用程序及移动设备中的软件系统。这样,我们 可以看出,w e bs e r v i c e s 的发展方向实际上是构造一个在现有i n t e r n e t 技术上的分布计算 系统。 简单的说,w e bs e r v i c e 是建立可互操作的分布式应用程序的新平台。作为一个w i n d o w s 程序员,你可能已经用c 0 惦竞d c 0 雌e 立过基于组件的分布式应用程序。c o m 是一个非常好的 组件技术,但是我们也很容易举出c 0 m 并不能满足要求的情况。而w e bs e r v i c e 平台是一套 标准,它定义了应用程序如何在w e b 上实现互操作性。你可以用任何你喜欢的语言,在任何 你喜欢的平台上写bs e r v i c e ,只要我们可以通过w e bs e r v i c e 标准对这些服务进行查询 和访问。程序设计与网络的发展促进了软件开发与信息交流的能力,为w e bs e r v i c e 奠定了 基础。而计算机技术方面的几个重大发展,他们导致了w e bs e r v i c e 的产生。 2 0 世纪7 0 年代人们意识到结构化编程所带来的好处,于是更高级的软件技术开始出现。 然而,直到2 0 世纪八、九十年代面向对象编程技术的广泛使用,人们才开始感到他们终于 拥有了能大大改进软件开发过程的必要工具。w e bs e r v i c e 吸取了面向对象编程技术的优 点,它允许开发人员利用现有的软件组件构建应用程序。这样,w e bs e r v i c e 技术其实鼓励 了模块化的编程方式,把网络变成了个巨大的程序组件库供开发者使用。 当开发者创建真正的应用程序的时候,会发现不同的任务运行于不同的计算机e 常常 会更有效,甚至是必要的。随着更加强大的计算机和网络的出现,分布式计算也出现了, 一个组织里的计算任务被分布到网络上,而不像从前那样仅由一台中心计算机来完成。n 层应用程序经常被分成每个部分运行于很多台不同的计算机匕。w e bs e r v i c e 通过扩展了有 限的可互操作性而改进了分布式计算的能力。与d c 侧( 分布式对象组件模型) 和c 0 r b a ( 公共 对象请求代理体系结构) 不同的是,w e bs e r v i c e 使用了开放的标准,这意味着w e bs e r v i c e 理论上可以使任何两个软件组件进行通信。而且,基于w e bs e r v i c e 的应用程序比较容易调 试,因为w e bs e r v i c e 使用的是基于文本的通信协议,而不是d c 帆o r b a 采用的二进制通 信协议。这样,相( 言w e bs e r v i c e 能够使各组织最终实现分布式计算的目标n 虽然因特网已经诞生了很长时间,但是万维网还是一个相对较新的发展产物。w e b 使得 计算机用户能够定位并且阅读到几乎各个方面的多媒体文档。过去,大多数应用程序都是 在单机上运行;而现在,我们编写的应用程序可以在世界上成千上万的计算机之间进行通 信。w e bs e r v i c e 和因特网加速并且简化了我们的工作,改变着我们办公和生活的方式。工 作于因特网裥e b 协议之匕的w e bs e r v i c e 扩展了w e b 的功能,使得计算机程序之间能眵通过 w e b 直接交互。为了联系商业伙伴、管理供应链,很多组织在电子数据交换( e d i ) 技术上进 行投资,而w e bs e r v i c e 粼了与e d i 相似的功能,实现起来也更为简单和便宜,由于w e b s e r v i c e 是基于开放标准的,因此较少出现不兼容的问题。另外,w e bs e r v i c e 更有助于构 造松耦合的系统,可以与e d i 系统一起工作,这就使各组织能够同时使用这两种技术或者在 采用w e b 服务的过程中逐步淘汰e d i 。一些公司也正在使用w e bs e r v i c e 和e d i 来实现更加实 惠的商业过程管理系统。 1 2 基于w e bs e r v i c e 技术的分布式并行数据挖掘研究的背景和意义 今天,大多数的数据挖掘以以下两种方法中的一种进行。第一种方法是,通过一个客 3 西安工业大学硕士学位论文 户端或三层数据挖据应用程序访问和分析本地数据。第二种方法是,数据挖掘被显式地或 隐式地嵌入到其它的应用程序中,例如,数据挖掘被嵌入到i b m ,m i c r o s o f t 和o r a c l e 的数 据库产品中。数据挖掘也通常被嵌入到多种多样的应用中,如c l t m 并f l 金融风险应用系统。 通常认为在过去的十年中数据挖据系统的发展经历了以下两个阶段:1 ) c s 系统2 ) 组 件和基于代理的系统【4 j 。 第一代数据挖据系统利用本地数据,是一种c s 或三层架构。利用这些系统,客户前端 通常访问一个具有数据挖据应用程序的服务器( 可能在同一台机器上) 。r # t c s 模型,服 务器也管理数据;对于三层架构,数据用o d b c ,j d b c 或其他相关的协议从另外的数据源访 问。 下一代数据挖据系统是以组件为基础的。组件可能是本地的,依靠微软的c o m 或d c 0 m 平台,或是全局的,依靠象s u n 的j 2 e e 平台。a n g o s s 是一个前者的一个例子,k e n s i n g t o n 是一个后者的例子。 或多或少在同一时间,大量试验性的基于代理的数据挖据系统被开发了出来。这些系 统的基本假定是数据是分布的,代理被用来移动数据,移动被一个局部数据挖据系统产生 的模型,或移动一个局部数据挖据计算产生的结果。今天,很少的基于代理的系统被应用 到实践中。这可能是因为没有基于代理的数据挖据系统可以建设在其上的基于代理的的架 构被广泛采用。基于代理的分布式数据挖据系统的例子包括j 删闭,p a p y r u s n 和b o d h i r 。 w e bs e r v i c e 技术是建立可互操作的分布式应用程序的新平台。它使得各种平台的以 各种不同语言和技术开发的分布式计算技术自& 够相互协作和交互,供现有的或潜在的客户 以一些标准的方式访问。在过去的几年中,w e bs e r v i c e 已经成熟到现在可以实际构建分 布的数据挖掘框架和基于它的数据挖据平台了。事实上,w e bs e r v i c e 有潜力以最基本的 方式改变探索、分析、挖据数据的架构。考虑以下的事实:今天,许多人发现用g o o g l e 定位一个文件有时比在本地磁盘上要快。随着带宽变成普通的资源嗍,访问远程的数据和 服务变得越来越容易,总有天访问远程的数据就像访问本地数据样容易。 由于数据挖掘方法很多,算法复杂,分别适用于不同的应用领域。数据挖掘系统在功 能和方法上很少有相似性,有时甚至在不同的数据集e 进行工作。通用的数据挖掘系统在 实际应用和开发中受到了很大的限制;由于挖掘对象( 数据源) 在地理匕的分布、数据集 中代价太大或根本无法进行、挖掘系统所涉及的软件组件以及用户在地理上的分布、遗留 系统的重用和集成、成本方面的考虑等问题,集中式的数据挖据显然是无法解决的。 于是,考虑到w e bs e r v i c e 技术的特点,我们可以利用w e bs e r v i c e 技术构建一个数 据挖掘系统,它应有以下几个特点:灵活的数据挖据架构,可以根据不同的应用领域,灵 活和快捷的选择最合适的数据挖据方法和数据挖据算法;具有分布式的软件架构,能在更 大程度上满足用户的需求;可以在一定程度上实现分布并行的数据挖掘,提高数据挖掘的 效率。 l 。3 本文的主要任务和结构安排 1 3 1 本文研究的主要内容 ( 1 ) 利用w e bs e r v i c e 技术实现数据挖掘算法的动态绑定,使数据挖掘算法组件化 4 西安工业大学硕士学位论文 随着数据挖掘技术的不断发展,新的挖掘方法和算法的涌现,对于数据挖掘系统,无 论是通用的还是专用的,从系统的升级和维护上来说,都是一个很艰巨的任务。所有这些 方面的因素,都制约着数据挖掘应用的进一步推广。w e bs e r v i c e 技术提供了解决上述数 据挖掘应用瓶颈的有效方法。运用w e bs e r v i c e 技术能结合数据挖掘系统的实际应用情况, 将各种数据挖掘算法以w e bs e r v i c e 的形式发布,在构建挖掘流程时用户可根据需要灵活 的选择算法,与实际的应用系统集成,从而使系统的开发、升级和维护都有较高的效率和 较大的灵活性。同时,因为对每个用户而言,他需要进行挖掘的数据结构一般来说是固定 的,因此可以对各种算法进行比较、评估,最终选择合适的算法组合。从另一个角度来说, 算法设计者可以将自己的算法用w e bs e r v i c e 在网上发布,以实现研究的价值。 ( 2 ) 研究w e bs e r v i c e 技术与分布式数据挖掘的结合点。提出一种跨平台的,易扩展的, 适用于分布环境下的基于w e bs e r v i c e 的分布式数据挖掘系统架构。 w e bs e r v i c e 技术的最大特点就是松耦合、跨平台,这些特点无疑为分布式数据挖掘 提供了良好的支持。分布式数据挖掘不但能挖掘分布的数据,而且还能利用其灵活的架构 更好的满足需求的变化。 ( 3 ) 研究如何利用w e bs e r v i c e 技术来进行分布式并行数据挖掘 高效率的数据挖掘是人们所期望的。但当挖掘的对象是一个庞大的数据集或是许多广 泛分布的数据源时,效率就成为数据挖掘的瓶颈,仅仅采用增量式的数据挖掘算法不能从 根本上提高数据挖掘的效率。利用w e bs e r v i c e 技术,可以将一个挖掘任务分配到多台计 算机e 运行,从而实现并行数据挖掘。随着s a 刚,、u d t 等专门为大量数据传输量身定做的 网络传输协议的不断成熟,数据的传输速度将加快,w e bs e r v i c e 技术将会对并行数据挖 掘提供更好的支持。 本文共分六章。第一章综述了本文的主要内容以及课题的重要意义。第二章介绍与 本文有关的技术。第三章论述7 并行数据挖据,提出了一种新的关联规则的并行挖掘算法, 并用w e bs e r v i c e 技术进行了实现。第四章提出了基于w e bs e r v i c e 的分布式并行数据挖 掘体系结构设计。最后,在第五章总结了本次设计得出的结论,并指出了课题的研究展望。 2 相关知识与研究 2 1 数据挖据技术 2 相关知识与研究 随着数据收集到数据库,大量数据被存储起来,仅仅对这些数据作简单的查 询、报告处理已不能满足日益增长的市场需要。如何对大量的数据进行分析, 从中提取有价值的信息和知识被放入议事日程。数据挖掘继数据收集、数据库 创建、数据提取、事务处理之后成为信息技术发明的又一领域。 信息技术自然演化的进程印证了数据挖掘产生的必然性,6 0 年代,信息技 术开发出原始的文件系统来进行事务处理。7 0 年代网状数据库、层次数据库诞 生并开始流行起来。8 0 年代关系数据库系统得到了飞速发展。s q l 语言、面向 对象技术为数据库应用提供了简单、直观、可靠、友好的用户界面,访闻数据 变得十分方使。8 0 年代中期以来,应用新模型的数据库,如扩充关系的、而向 对象的、对象关系的和演绎的数据库,以及特种数据库包括空间的、时间的、 多媒体的、主动的和科学的数据库相继出现。进入9 0 年代,i n t e r n e t 的迅速发 展进一步形成全球信息系统。为了更好她支持用户决策,数据仓库应运而生。 数据仓库是多个异种数据源在单一站点以一致模式的存储。数据仓库是面向主 题的、集成的、时变的和非易失的数据存储,并能很好地支持联机分析处理 ( o l a p ) 。联机分析处理( o l a p ) 是一种分析技术,包括上卷、下钻、切片、切 块等操作,具有汇总、合并和聚集的功能,提供用户不同角度的数据视图。但 是,对于关联、分类等深层分析,联机分析无能为力。 2 1 1 数据挖掘的定义 数据挖掘是一门广义的交叉学科,它汇聚了数据库、人工智能、数理统计、 可视化、并行计算等不同领域的研究。至今有多种数据挖掘的定义,其中在k d d 9 6 国际会议上,根据知识发现研究领域知名学者的阐述得到一个被一致接受的数 据挖掘定义:数据挖掘是一个非平凡的高级过程,是对数据中有效的、新颖的、 潜在有用的,以及最终可理解的模式的识别。其中的相关术语有如下的含义1 9 l : 数据:是指一个有关事实的集合,它是用来描述事物有关方面的信息,是数 据挖掘的原材料。 新颖:经过数据挖掘提取出的模式必须是新颖的,至少对现有的系统来说应 该如此。 潜在有用:提取出的模式应该是有意义的,可以被人们所利用的。 可被人理解:数据挖掘的一个目标就是将数据库中隐含的模式以容易被人理 解的形式表现出来,从而帮助人们更好地了解数据库中所包含的信息。 模式:是指用高级语言表示的表达一定逻辑含义的信息,通常指数据库中数 西安工业大学硕士学位论文 据之间的逻辑关系。 非平凡:是指在数据挖掘中,知识的发现过程应具有某种不确定性和一定的 自由度,不是一个很确定的过程。 高级过程:数据挖掘是对数据进行更深层处理的过程,往往包括多种循环和 反复,而不是仅仅对数据进行加减求和等简单运算或查询。 2 1 2 数据挖掘的任务和方法 数据挖掘任务用于指定数据挖掘要找的模式类型。数据挖掘所能发现的知 识有如下几种:广义型知识,反映同类事物共同性质的知识;特征型知识,反 映事物各方面的特征知识;差异型知识,反映不同事物之间属性差别的知识; 关联型知识,反映事物之间依赖或关联的知识;预测型知识,根据历史的和当 前的数据推测未来数据,偏离型知识,揭示事物偏离常规的异常现象。 根据数据挖掘所能发现的知识类型可以将数据挖掘任务分成两类:预测性 任务和描述性任务。预侧性挖掘任务是在当前数据上进行推断,以进行对未知 数据的预测。描述性挖掘任务用于发现数据的一般特性,能对数据进行一般性 描述【1 0 1 。具体的说,数据挖掘任务以及它们可以发现的模式类型可以有如下几 种: 1 ) 类概念描述 用汇总的、简洁的、精确的方式描述每个反映数据特性的类或概念有利于 对数据的理解。这种类或概念的描述称为类概念描述。数据特征化是目标类数 据的一般特征或特性的汇总。数据区分是将目标类对象的一般特性与一个或多 个对比类对象的一般特性比较。 2 ) 关联分析 关联分析用于发现事物间的关联规则,这些规则展示属性一一值频繁地在 给定数据集中一起出现的条件。关联规则的一般形式是:如果a 发生,则b 有 c 的可能性发生。其中c 称为关联规则的置信度。关联分析展示了数据间的依 赖关系,根据这种关联性就可从某一数据对象的信息来推断另一数据对象的信 息。 3 ) 分类 分类是这样的过程,通过对己知类别的个体进行归纳,找出描述并区分数 据类或概念的模型,即分类模式。分类模型找出各类的特征属性,以便能够使 用模型预测类标记未知的对象类。分类分为分类和预测两种数据分析形式,可 以用于提取描述重要数据类的模型或预测未来的数据趋势。分类和预测的不同 之处在于分类是预测离散型分类标号,而预测建立连续值函数模型,用于预测 连续型的未知值。 4 ) 聚类 与分类不同,聚类分析数据对象本身。它既不知道具体的数据的分类标准, 也不知道会有些什么类。一般情况下,数据中不提供类标记,而聚类可以用于 西安工业大学硕士学位论文 产生这种类标记。数据可以看成是对象,对象根据最大化类内的相似性、最小 化类间的相似性的原则按照给定的聚类参数进行分解、合并。最后形成对象的 聚类( 簇) ,使得在一个簇中的对象具有很高的相似性,而与其他簇中的对象不 相似。得到的结果由用户进行鉴别,如果不满足目标,需要改动聚类参数,重 新聚类。 5 ) 孤立点分析 数据库中可能包含一些数据对象,它们与数据的一般行为不一致。这些数 据对象称为孤立点。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然 而,在一些应用中( 如欺骗检测) ,孤立点可能比正常出现的数据更有实用价值。 6 ) 数据演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势。尽管这可能包括 与时间相关数据的特征化、区分、关联、分类或聚类,但这类分析的不同特点 是包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。数 据演变分析首先要考虑时间特性和时间周期的层次,如天、周、月、年等,有 时还要考虑日历的影响,如节假日等。 2 1 3 数据挖掘的分类 数据挖掘是一个建立于包括数据库系统、统计分析、机器学习、人工智能、 信息科学等多个领域的交叉学科。数据挖掘采用的技术十分广泛,如神经网络、 模糊集理论、知识表示、归纳逻辑程序设计、或高性能计算等。对于不同数据 类型或不同应用,数据挖掘系统还可集成空间数据分析、信息提取、模式识别、 图象分析、信号处理、计算机图形学、w e b 技术、经济、或心理学等领域的技术。 根据不同的角度,数据挖掘系统可以分类如下【1 1 l : ( 1 ) 根据数据库类型分类 数据挖掘系统可以根据被挖掘的数据库类型分类。不同数据库系统可能采用 不同的数据模型,需要不同的数据挖掘技术。有关系的、面向对象的、对象一 一关系的、或数据仓库的数据挖掘系统。 ( 2 ) 根据应用背景分类 不同数据库系统有不同的应用背景,需要不同的数据挖掘技术。根据所处理 的数据的不同类型分类,有空间的、时间序列的、文本的、多媒体的、w w w 的、 主动的数据挖掘系统。还有异种数据库挖掘系统和遗产数据挖掘系统等。 ( 3 ) 根据挖掘的知识类型分类 根据数据挖掘系统所挖掘的知识类型,即根据数据挖掘的不同功能,如特征、 区分、关联、聚类、趋势和演化分析等进行分类。数据挖掘系统还可以根据所 挖掘的知识的不同粒度或抽象层进行区分,包括泛化知识,原始层知识,或多 层知识等。 ( 4 ) 根据采用的不同技术分类 数据挖掘可以根据所用的数据挖掘方法进行分类。现有的数据挖掘方法很 西安工业大学硕士学位论文 多,可粗分为:机器学习方法、统计方法、神经网络方法和数据库方法等。在 机器学习中,又可以分为:归纳学习方法、基于范例学习、遗传算法等。统计 方法中有:回归分析、判别分析、聚类分析、探索性分析等。神经网络方法中 有:前向神经网络、自组织神经网络等。数据库方法主要是多维数据分析或o l a p ( 0 n l i f i ea n a l y t i c a lp r o c e s s i n g ,联机分析处理) 方法,另外还有面向属性的 归纳方法,在这些方法中又有不同的实现算法和版本。对于不同的应用领域和 不同的数据挖掘任务,所采用的具体方法也是不一样的。 2 1 4 数据挖掘的一般过程 从数据挖掘的定义可以看出,数据挖掘是一个不确定的过程,在实施数据挖 掘的过程中会有很多因素需要考虑,如数据本身、相关领域知识、所采用的数 据挖掘方法和算法、系统的性能等。但根据数据挖掘的一般原理,可以将其过 程分成以下步骤【1 们,如图2 1 所示: 图2 1 数据挖掘过程 ( 1 ) 确定数据挖掘任务 首先熟悉应用领域的数据、背景知识,明确所要完成的数据挖掘任务。 ( 2 ) 数据选择 根据用户要求,从数据库中或其他的数据源中提取与数据挖掘任务相关的数 据,数据挖掘将主要在这些数据中进行。 ( 3 ) 数据预处理 数据预处理包括数据清理、数据集成、数据交换和数据归约( 压缩) 。数据预 处理将与数据挖掘相关的数据从数据库中或其他的数据源中进行合并处理。处 理数据中的遗漏和清洗脏数据等,除去明显错误的数据和冗余的数据,并解决 语义模糊性,并将数据转换成为有效形式,以使数据挖掘更有效。数据预处理 的目的是辨别出需要分析的数据集合,缩小处理范围,提高数据挖掘的质量。 ( 4 ) 数据挖掘 根据数据挖掘任务的要求,选择合适的数据挖掘算法( 包括选取合适参数) , 在数据中寻求感兴趣的模型,并把它生成某种易于理解的形式。 ( 5 ) 模式的评估 西安工业大学硕士学位论文 为了有效地发现对于给定用户有价值的模式,必须在数据挖掘之后使用某种 评估标准对模式进行评估。去掉哪些没有意义或不感兴趣的模式。或者用该种 模式指导和限制挖掘过程,删除模式空间中不满足预先设定的条件的模式,改 善挖掘过程中的搜索性能。 ( 6 ) 知识的表达 根据最终用户的具体任务把数据挖掘产生的有价值的模式以用户能理解的 方式提供给用户,必要时需要返回到前面处理中的某些步骤以进行了反复挖掘。 从以上的处理步骤来看,整个数据挖掘的过程在整体上是顺序执行的,但是 实际的过程并不是这么一个简单的线性流程,各个步骤之间包含了交叉和反复, 模式的产生可能是一个曲折的、循环的过程。 2 1 5 预言模型标记语言( p m m l ) 2 1 5 1p m m l 的定义 p m m l 全称预言模型标记语言( p r e d i c t i r em o d e lm a r k u pl a n g u a g e ) ,它利 用x m l 描述和存储数据挖掘模型,是一个已经被w 3 c 所接受的标准f 1 2 】。p m m l 标准 的目的是一旦一个模型被数据挖掘算法产生,该模型能够被其他数据挖掘工具 可视化这个模型,或者使用这个模型。由于开放的格式,不同提供软件商之间 能够共享模型i ”】。其使用示意图如图2 2 所示。 图2 2p m m l 使用示意图 2 1 5 2p m m l 的目的 ( 1 ) 模型交换:对于复杂的数据挖掘任务,需要应用不同的数据挖掘工具, 因而工具之间必须能够互相交换结果,并在交换结果的同时不用考虑 产生模型的应用工具之间的差异。而这需要有一个开放的数据格式支 持。 ( 2 ) 模型部署( d e p l o y ) :商业智能应用开发的模型易于部署。软件商能够 西安工业大学硕士学位论文 更容易地将数据挖掘结果导入到其他支持这种标准的工具中。从发展 的眼光看,需要将商业智能跨越在i n e t e r n e t 上进行实施部署,p m m l 为这项功能提供了的基础。 ( 3 ) 独立性:独立于平台、应用和操作系统,只定义模型描述,而不是模 型执行的方法 ( 4 ) 标准化:标准化的模型描述就象h t m l 之于i n t e r n e t 一样,将开放模 型的封闭性,开放数据挖掘行业。 2 1 5 3p m m l 的优缺点 优点: ( 1 ) 描述数据挖掘模型的标准 ( 2 ) 在数据挖掘工具之间,以及数据挖掘工具和其他应用之间交换 数据挖掘模型 ( 3 ) 数据挖掘工具外部一种存储模型的有效的方式 ( 4 ) 将模型与数据和工具分离 ( 5 ) 用户易于编辑模型( 作为x m l 文档,可以通过文本编辑器编辑) 缺陷: ( 1 ) 当前,模型并没有真正实现与数据的分离,因为,在建模前需 要经过大量的数据转换 ( 2 ) 没有被所有的数据挖掘软件商采纳 2 1 5 4p m m l 实例d 4 以关联规则为例:交易集合如表2 1 ,最小支持度= o 6 ,最小置信度= 0 5 。 交易编号项目集 t 1 c r a c k e r ,c o k e ,w a t e r t 2 c r a c k e r ,w a t e r t 3 c r a c k e r ,w a t e r t 4 c r a c k e r ,c o k e ,w a t e r 表2 1 交易项目表 它对应的p m m l 模型为: h e a d e rc o p y r i g h t = w w w d m g o r g ” d e s c r i p t i o n = e x a m p l em o d e lf o ra s s o c i a t i o nr u l e s 4n a s s o c i n p u t s t a t sn u m b e r o f t r a n s a c t i o n s = ”4 “ n u m b e r o f ite m s = ”3 ” 西安工业大学硕士学位论文 m i n i m u m s u p p o r t = ”0 6 “ m i n i m u m c o n f i d e n c e = ”0 5 “ n u m b e r o f i t e m s e t s = ”3 ” n u m b e r o f r u l e s = “2 “b a s s o c i t e m r e fi t e m r e f = “1 “n a s s o c i t e m r e fi t e m r e f = 3 h a s s o c i t e m r e fi t e m r e f = 。3 b a s s o c r u l e s u p p o r t = 1 0 “ c o n f i d e n c e = 1 0 ” a n t e c e d e n t = 1 c o n s e q u e n t = 2 。n 2 1 6 数据挖掘体系结构 体系结构选择对一个数据挖掘平台的设计至关重要,与数据挖掘技术和数 据库、数据仓库技术的发展相适应,数据挖掘系统的体系结构也在不断发展演 1 2 西安工业大学硕士学位论文 化。尽管丰富和强大的数据挖掘功能是数据挖掘系统的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论