（计算机应用技术专业论文）基于网格的分布式数据挖掘体系结构研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 随着信息技术在社会生活各个领域的快速应用，人们越来越重视数据收集工作， 建立了数量众多的数据库，把它们广泛应用于商业、行政、教育、科研等不同行业。 同时，为了从丰富的数据资源中找到自己需要的有益信息，人们又提出了数据挖掘和 分布式数据挖掘的方法。前者能在大量数据中自动发现感兴趣的知识。后者则利用了 分布式技术来实现数据挖掘。目前，分布式数据挖掘已经成为数据挖掘的主流形式。 另一个方面，网格作为一种新型的分布式计算技术，逐渐成熟。网格具有超强的 计算处理能力、良好的系统扩展能力和高效的分布式资源管理能力。它突破了计算能 力的限制、存储能力的限制、资源分布的限制、资源共享方式的限制，适用于计算密 集型、数据密集型应用。利用网格技术进行分布式数据挖掘是一种全新的尝试。为此， 本文对基于网格的分布式数据挖掘体系结构进行了研究，提出网格分布式数据挖掘的 解决方案，即在网格中间层之上，为网格应用建立分布式数据挖掘中间层，为用户提 供了更加通用的分布式数据挖掘平台。 论文的前四章是相关技术知识背景。首先介绍了分布式数据挖掘技术，阐述了分 布式数据挖掘的概念、模式、研究内容、工作流程，指出了传统分布式数据挖掘系统 存在的主要问题。接着对网格技术进行了总体描述，研究了它们的概念、特点，及其 应用领域。然后具体地分析了w e b 服务资源架构的技术规范，研究了g l o b u s 项目工 具包g t 4 服务组成。 论文第五章，进行了网格分布式数据挖掘中间层设计。分析了网格分布式数据挖 掘体系结构，提出了网格分布式数据挖掘中间层模型，将分布式数据挖掘中间层划分 为四个服务资源：全局w s 资源、局部w s 资源、算法w s 资源、数据分配w s 资源， 定义了它们的服务接口和资源属性，描述了服务调用的流程。 最后，进行了中间层服务资源原型实现。描述了各个w e b 服务资源的资源属性 文档，实现了操作这些资源属性文档的接口，使用统一建模描述语言描述了各个w e b 服务资源的静态结构图。并且，通过安装网格中间件，建立了基于局域网的网格试验 环境，以一个分布式挖掘实例进行了试验，从而论证了论文提出的网格分布式数据挖 掘中间层的可行性。 关键词：数据挖掘，分布式数据挖掘，网格计算，w e b 服务资源 重庆大学硕士学位论文英文摘要 a b s t r a c t w h i l ei n f o r m a t i o nt e c h n o l o g yi sa p p l i e di ne v e r yf i e l do ft h eh u m a ns o c i e t yq u i c k l y , p e o p l er e g a r dc o l l e c t i n gd a t aa sa ni m p o r t a n ta f f a i r , a n db u i l dal o to f d a t a b a s e su s e do nt h e i n s t i t u t i o no fb u s i n e s s ，g o v e r n m e n t ，e d u c a t i o n ，a n ds c i e n t i f i cr e s e a r c h m o r e o v e r , f o rt h e s a k eo fp i c k i n go u tu s e f u li n f o r m a t i o nf r o mt h e s ed a t ar e s o u r c 宅，t h er e s e a r c h e r sr a i s e d a t a - m i n i n gt e c h n o l o g ya n d d i s t r i b u t e d d a t a - m i u i n gt e c h n o l o g y t h e f i r s to n em a y a u t o m a t i c a l l yf i n do u tt h ek n o w l e d g ef r o md a t a b a s e s ，t h el a s to n ei m p l e m e n td a t a - m i n i n g o nd i s t r i b u t e dt e c h n o l o g y c u r r e n t l y , t h ed i s t r i b u t e dd a t a - m i n i n gi st h ep r i m a r yf o r m o nt h eo t h e rh a n d ，a san e wd i s t r i b u t e dt e c h n o l o g y ，t h eg r i dt e c h n o l o g yh a sb e e n m a t u r e i t p r o v i d e s a ne f f i c i e n t m a n a g i n gw a yo fd i s t r i b u t e dr e s o u r c e ，s t r o n g c o m p u t a t i o n a lp o w e r , e x c e l l e n ts y s t e me x p a n s i b i l i t y , b r e a k st h el i m i to fc o m p u t a t i o n a l p o w e r , s t o r a g e , r e s o u r c ed i s t r i b u t i n g , t h ew a y o fs h a r i n gr e s o u r c e i ts h o u l db eaf i r e - n e w e x p e r i m e n tc o m b i n i n gg r i da n dd i s t r i b u t e dd a t a - m i n i n gt e c h n o l o g y a sar e s u l t ，t h i sp a p e r d or e s e a r c ho nt h ea r c h i t e c t u r eo ft h ed i s t r i b u t e dd a t am i n i n g ，p r o p o s e sas o l u t i o no f d i s t r i b u t e dd a t a - m i n i n gb a s e do ng r i d ，n a m e l y , a b o v et h eg r i dl a y e r , an e wl a y e ro f d i s t r i b u t e dd a t a - m i n i n gi sb u i l da sau n i v e r s a ld a t a - m i n i n gp l a t f o r m a s s o c i a t e dt e c h n o l o g i e sa r er e s e a r c h e db e f o r e c h a p t e r5i n t h ep a p e r f i r s t l y , d i s t r i b u t e dd a t am i n i n ga r ed i s c u s s e da n da n a l y z e d ，a n dt h ep r o b l e mo c c u r r e do nc u r r e n t d i s t r i b u t e dd a t am i n i n gs y s t e mi s p r o p o s e d s e c o n d l y , t h eg r i dt e c h n o l o g yi sa n a l y z e d s u m m a r i l y , i n c l u d i n gi t sc o n c e p t ，g o a la n dm a i na p p l i c a t i o n t h e ，w e bs e r v i c er e s o u r c e f r a m ei sd i s c u s s e di nd e t a i l ，a sw e l la st h e 鲥di m p l e m e n tp r o j e c t g l o b u st o o l k i t4 i t i st h ed e s i g np a r to ft h ed i s t r i b u t e dd a t a - m i n i n gl a y e ri nt h ec h a p t e r5 t h e a r c h i t e c t u r eo f d i s t r i b u t e dd a t a - m i n i n go ng r i di sa n a l y z e d d i s t r i b u t e dd a t a - m i n i n go ng r i d i sb r o u g h to u t i na d d i t i o n , t h ec o m p o n e n t so ft h ew h o l ea r c h i t e c t u r e ，g j 【o b a lw e bs e r v i c e r e s 0 1 1 r c e ，l o c a lw e bs e r v i c ei s o l i e c c , a l g o r i t h mw e bs e r v i c er e s o u l - c 4 0a n dd a t a m a r kw e b s e r v i c er e s o u r c ea r ed e s i g n e dr e s p e c t i v e l y , i n c l u d i n gi n t e r f a c ed e f i n i n g ，s e r v i c ew o r k f l o w f i n a l l y ，a l lw e bs e r v i c e r e s o u r c e sa r ei m p l e m e n t e d t h er e s o u r c e p r o p e r t i e s d o c u m e n t so fw e bs e r v i c e sa r ed e s c r i b e d ，t h eo p e r a t i o ni n t e r f a c e so fw e bs e r v i c e sa r e i m p l e m e n t e d ，a n dt h es m i l et o p o l o g i e so fw e b s e r v i c er e s o u r c e sa r ep r o t r a c t e db yu m l f u r t h e r m o r e ，al o c a lg r i di sb u i l tt h r o u g hi n s t a l l i n gt h eg r i dm i d d l ew a r eo ns o m e c o m p u t e r sl i n k e dt o g e t h e r a n do nw h i c ham i n i n gi n s t a n c er u n n i n gs u c c e s s f u l l yp r o v et h e f e a s i b i l i t yo f t h ep r o p o s e da r c h i t e c t u r ei nt h ep a p e r 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 dd a t am i i l i n g ，g r i dc o m p u t i n g , w e bs e r v i c e r e s o u r c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特， j j ) j i l 以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖盘堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：参战、1 学位论文版权使用授权书 本学位论文作者完全了解重鏖太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重迭太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：鸯i 刃一1 签字日期：沙司年6 月中日 导师签名：哲学贝 签字日期：沙刁年6 月咿日 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 论文的研究背景及选题意义 近十几年来，人们利用信息技术产生和搜集数据的能力大幅度提高，数以万计 的数据库被用于商业、行政，科研和教育等行业。要想使数据真正成为一个公司或 机构的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大 量的数据可能成为包袱，甚至成为垃圾。因此，面对人们被数据淹没却饥饿于知识 的挑战，数据挖掘【l 】和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其 强大的生命力。 数据挖掘( d a t am i n i n g ，d m ) 就是从大量数据中提取和挖掘知识【2 】。数据挖掘 的对象可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学 的，也可以是非数学的；可以是演绎的，也可以是归纳的。挖掘出的知识可以被用于 信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是- - i 3 广义的交叉学科，涉及人工智能、统计与数据库等多种技术。它汇 聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算 等方面的学者和工程技术人员。 分布式数据挖掘 3 , 4 1 ( d i s t r i b u t e dd a t am i n i n g , d d m ) 就是使用分布式计算技术， 从分布式数据库中发现知识的过程【s 】。在现实应用环境中，绝大部分的大型数据库 都是以分布式的形式存在的。而且，对于大型数据库来说，要进行分析挖掘的数据 数量一般相当巨大，可用海量来形容，如果仅仅使用传统数据挖掘方式，昂贵的挖 掘硬件系统和极长的挖掘时间都是无法容忍的。因此分布式数据挖掘是数据挖掘的 一个主要研究方向。 目前为了实现真正意义上的分布式数据挖掘方面已经进行了不少的研究，取得 了一定的成果。比如文献【6 】中提出的j a m 系统，它采用从局部学习构成全局学习 环境的方式；文献 7 】中提出的k e n s i n g t o n 数据挖掘基础架构，它是基于c o r b a 来 进行远程通信和访问的；文献【8 】中提出的b o d h i 系统是一个基于a g e n t 的系统。 它们都较为圆满地实现了分布式数据挖掘。然而，这些分布式数据挖掘系统或多或 少仍然存在以下这些缺陷： 1 ) 系统大多是紧耦合的，局部网络或节点出现故障，将使整个分布式挖掘系统 停止，甚至崩溃。 2 1 系统的动态伸缩性差，无法根据用户的要求动态地发现合适的算法、数据集， 也无法根据网络的状况，动态地添加或减少参与挖掘的计算资源。 3 ) 系统对硬件要求高，一般需要使用大型机或机群系统，挖掘能力、存储能力 重庆大学硕士学位论文1 绪论 受到挖掘硬件限制。 上述缺陷是由于现有成熟的分布式计算技术的局限性所造成的。解决这些缺陷 需要寻找一种新型的分布式计算技术，而网格技术正是这种要求的最好选择。网格 【9 】是在动态变化的、拥有多个部门、或团体的复杂虚拟组织内，能提供灵活的、安 全的协同资源共享或问题求解的计算环境。网格突破了计算能力的限制、存储能力 的限制、资源分布的限制、资源共享方式的限制，其适用于计算密集型、数据密集 型应用。是解决复杂海量、分布数据的访问、存储、组织和管理的一种有效技术。 网格技术与分布式数据挖掘相结合，可以将网格技术高效的分布式资源管理能力、 良好的系统伸缩能力和超强的计算处理能力应用于数据挖掘中，为数据挖掘提供有 力保障。为此，本文提出了一种结合网格技术的分布式数据挖掘解决方案，即将分 布式数据挖掘模型应用于网格中间层之上，建立网格分布式数据挖掘中间层，为用 户提供分布式数据挖掘平台。 1 2 国内外研究现状综述 1 2 1 数据挖掘与分布式数据挖掘技术 数据挖掘的产生是一个逐渐演变的过程，电子数据处理的初期，人们就试图通 过某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习的 过程就是将一些己知的并已被成功解决的问题作为范例输入计算机，机器通过学习 这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类 的问题。随后，随着神经网络技术的形成和发展，人们的注意力转向知识工程，知 识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给计算 机输入已被代码化的规则，而计算机是通过使用这些规则来解决某些问题。专家系 统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。8 0 年代人们 又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其成果应用于 处理大型商业数据库。在8 0 年代末提出了一个术语知识发现，简称k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 。它泛指所有从数据源中发掘模式或联系的方法，人们接受了 这个术语，并用k d d 来描述整个数据发掘的过程，包括最开始的制定业务目标到 最终的结果分析，而用数据挖掘( d a t am i n i n g ) 来描述使用挖掘算法进行数据挖掘的 子过程。 数据挖掘又被称作从数据库中发现知识( k d d ) ，k d d 研究在学术界空前繁荣。 k d d 一词首次出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会议上。到目 前为止，由美国人工智能协会主办的k d d 国际研讨会己经召开了十多次，规模由 原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用， 注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 2 重庆大学硕士学位论文 1 绪论 分布式数据挖掘d d m ( d i s t r i b u t e dd a t am i n i n g ) 则是利用分布式技术进行数据挖 掘的方法。它包含两层含义：第一，就是使用分布式算法，从逻辑上或物理上分布 的数据源中发现知识的过程。这里主要强调数据源的分布性。第二，是指与某个数 据挖掘任务相关的用户，数据，挖掘软件以及其他软组件是地理上分散的。这里主 要强调的是软组件的分散性。分布式数据挖掘系统是一个发展非常迅速，而且具有 广阔应用前景的研究领域。目前在数据挖掘理论研究和数据挖掘应用方面都取得了 很大进展。近年来，分布式数据挖掘已经引起各应用领域的足够重视。 p a d m a 系统是h i l l o lk a r g u p t a 等提出的一个基于a g e n t 的并行分布式数据 挖掘系统。该系统不限定于特定的数据挖掘领域。p a d m a 系统由如下组件构成： 数据挖掘a g e n t 、协调各a g e n t 工作的f a c i l i t a t o r 和用户接口。数据挖掘a g e n t 负 责读取数据并提取高层次的信息。a g e n t 通过f a c i l i t a t o r 并行工作。f a c i l i t a t o r 负 责协调各a g e n t 工作并提供信息给用户接口，同时接收用户的反馈信息给各个 a g e n t 。p a d m a 系统有一个图形化的基于w e b 的用户接口用来把各a g e n t 提取 的信息展现给用户。f a c i l i t a t o r 接收用户接口以标准s q l 格式提交的查询，这些查 询被广播给各a g e n t 。a g e n t 提取与特定查询相关的信息。f a c i l i t a t o r 收集这些信息 并将其展现给用户。该系统使用p p f s ( p a r a l l e lp o r t a b l ef i l es y s t e m ) 开发，以面向对 象的方式用c + + 语言编码，提供了一个可扩展的架构。使用m p i ( m e s s a g ep a s s i n g i n t e r f a c e ) 进行底层的消息交换和通信。该系统可以划分为如下三个功能模块：并 行数据读取和查询处理模块、收集汇总模块、用户交互和结果展现模块。 j a m ( j a v aa g e n t sf o rm e t a - l e a m i n g ) 系统是a l p r o d r o m i d i s 等设计的一个分 布式数据开采系统。在这个系统中提出了使用m e t a - l e a r n i n g 进行分布式数据开采 的思想。m e t a - l e a r n i n g 是一种计算高层c l a s s i f i e r s ( 称为m e t a - c l a s s i f i e r s ) 的技术， 即把各个数据库上分别独立计算的c l a s s i f i e r s 以某种原则汇集成高层c l a s s i f i e r s 的 技术。该系统使用j a v a 语言编写，具有较好的平台无关性。 其它的分布式数据挖掘系统还有p i t t s b u r g h 大学的a r o n i s 教授等设计的 w o r l d 系统、c h a v c z 的c h a l l e n g e r 系统等。 1 2 2 网格技术 网格这一术语于2 0 世纪9 0 年代中期提出的，用来表述一种适用于高端科学和 工程的分布式计算的体系结构。网格作为一种新型的网络计算平台，提供了共享和 协调使用各种资源的机制，能够将异构的、动态的、地理上分布的计算资源创建为 一个虚拟计算系统，以获得理想的服务质量【9 ，1 0 。美国g l o b u s 项目的领导人i a n f o s t e r 在什么是网格? 判断是否是网格的三个标准一文中，网格必须同时满足三个条件 h i 。 协调分布的资源 重庆大学硕士学位论文 1 绪论 网格集成和协调存在于不同控制域内的资源和用户，例如，用户的桌面计算和 集中计算，同一公司的不同管理单元，或是不同的公司的不同管理单元。并且网格 还处理分布资源场景中出现的问题，如安全、策略、付费和成员资格等。 使用标准的、开放的和通用的协议和接口 网格建立在多目标协议和接口之上。这些协议和接口用来处理这些基本问题， 如认证、授权、资源发现和资源访问。 提供最好的服务质量 网格允许协调使用它的组成资源，以便提供各种服务质量，如响应时间、吞吐 量、可用性和安全性。网格还可能需要协同分配多种资源类型来满足复杂用户的需 求，这样的组合系统效用远大于它的各个部分效用之和。 网格被誉为继i n t e m e t 和w e b 之后的第三次信息技术浪潮。网格有别于w e b 的 基本特征就在于服务的形式。目前，w e b 要创建应用环境，还要依靠开发人员按照 w e b 协议开发，而网格是在更高层次上对这些应用提供的一种服务形式。因此，将 来的应用系统所基于的平台，应该是网格所提供的基本服务。而这种服务的本身， 又会不断动态地加入到网格当中，使得网格服务内容不断丰富。 目前，网格计算技术之所以能够引起社会如此广泛的讨论，主要原因是网格能 够通过网络利用众多闲置的c p u 资源形成高性能的计算能力。但是遇到的问题是， 现有的大量商业应用软件和数据库软件都不支持网格技术，这就是现实与理想的差 距。 对网格计算的发展来说，目前相当重要的一项工作就是建立一个通用的网格服 务标准规范，把网格计算与目前的w e b 服务能够很好地融合。 2 0 0 2 年2 月，在加拿大多伦多市召开的全球网格论坛g g f 会议上，g l o b u s 项 目组和m m 共同倡议了一个全新的网格标准o g s a 。o g s a 是开放网格服务体系， 它把g l o b u s 标准与以商用为主的w e bs e r v i c e s 的标准结合起来，网格服务统一以服 务的方式对外界提供。2 0 0 3 年符合o g s a 规范的g l o b u st o o l k i t3 0 发布，这标志着 o g s a 已经从一种理念、一种体系结构，走到付诸实践的阶段 1 2 , 1 3 。 虽然o g s i 作为o g s a 的核心概念，其自身存在一些缺陷，需要一些新的结构 来解决这些问题。所以采用新的结构代替o g s i 是有必要的，通过转变可以获得网 络服务强有力的支持。2 0 0 4 年1 月，美国a k a m a it e c h n o l c l 百髓、美国t h e g l o b u s a l l i a n c e 、惠普、m m 、美国s o n i cs o f t w a r e 和美国t i b c os o f t w a r e 六公司公布了统 一网格计算和w e b 服务的新标准w s - n o t i f i c a t i o n 和w s - r e s o u r c e f r a m e w o r k 。w e b 服务资源框架( w s r f ) 是o g s i 的重构和发展，并利用了新的w e b 服务标准。w s r f 基本保留了o g s i 中的所有功能，同时更改了一些语法，并且还在其表示中采用了 不同的技术。w e b 服务通知【1 4 1 ( w s n ) 为w e b 服务提供基于消息发布和预定能力。 4 重庆大学硕士学位论文 1 绪论 w s r f 和w s n 都是建立在己存在的w e b 服务定义和技术基础上的，帮助实现了网 格计算、系统管理和w e b 服务的统一。 1 3 论文研究的内容及组织 由于网格在分布式计算方面具有突出的优势，数据挖掘应用于网格环境，建立 基于网格的分布式数据挖掘，将会带来显而易见的好处。本文的研究目标就是利用 网格计算技术构建网格分布式数据挖掘中间层，设计实现了基于网格的分布式数据 挖掘系统，并用实验验证系统的可行性。论文的研究内容包括： 研究数据挖掘与分布式数据挖掘技术。网格分布式数据挖掘属于分布式数据 挖掘范畴，传统分布式数据挖掘技术已相当成熟，它的挖掘方法、挖掘模式、挖掘 流程可以为研究网格分布式数据挖掘提供帮助。 研究网格技术。网格是一种新型分布式计算技术，要构建基于网格的分布式 数据挖掘系统，必须要对网格技术有一个全面了解，需要研究网格的体系结构，及 有关的技术规范。同时，需要对网格实现项目g l o b u s 进行研究，了解网格工具包 g t 4 结构、服务组成。 研究并设计网格分布式数据挖掘中间层。首先要研究基于网格的分布式数据 挖掘体系结构，对网格分布式数据挖掘中间层进行功能划分，设计服务模块。然后 对服务主要模块进行设计，给出每个服务模块的结构组成、主要接口操作、运行流 程。 研究网格分布式数据挖掘中间层原型实现。网格环境是系统开发和运行平台， 需要研究网格中间件安装、构建。网格环境构建完成后，要实现网格中间层的各个 服务资源，给出服务资源接口的静态结构图和服务资源描述文档。最后，利用挖掘 实例检验系统的可行性。 本文的组织：第二章分布式数据挖掘技术，对分布式数据挖掘的主要流程、技 术手段进行了阐述。第三章网格技术，描述了网格的内涵、特点及体系结构。第四 章网格w s r f 规范与g t 4 工具包。分析了w s r f 的主要技术规范，剖析了g t 4 的 组成结构。第五章网格分布式数据挖掘中间层的设计。第六章，网格分布式数据挖 掘中间层服务的实现，并进行了实验验证。第七章，总结与展望。 5 重庆大学硕士学位论文 2 分布式数据挖掘 2 分布式数据挖掘 2 1 分布式数据挖掘概述 数据挖掘a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 【1 5 】。 分布式数据挖掘( d d m ) 就是使用分布式计算技术，从分布式数据库中发现、知识 的过程。随着数据挖掘技术从理论到实践的成熟和发展，在分布式数据库环境中进行 数据挖掘，是我们必须面对的问题。信息时代中的数据具有分布的天然本质，我们需 要在分布、异构的数据源上执行数据挖掘，并得到整合的知识。数据集的分布本质以 及数据的巨大性，不可避免地导致了高昂的通信开销。传统的数据挖掘模型不适宜处 理用户、数据和计算资源的协同。为了应对这种情况，出现了分布式数据挖掘， d i s t r i b u t e dd a t am i n i n g ( d d m ) t 1 6 , 1 7 。概括讲，分布式数据挖掘是对划分为物理、地理 分布的数据子集实施挖掘的过程。 2 2 分布式数据挖掘的方法 2 2 1 数据库分割方式 分布式数据挖掘的数据源是分布式数据库，或者是把集中式数据库按水平方式或 垂直方式划分后分布在不同站点的分布式数据集。在水平划分情况下，各站点的数据 是同质( 或同构) 的，即每个站点上的数据具有相同的特征( 或属性) 集。在垂直划分情 况下，各站点的数据是异质( 或异构) 的，即每个站点上的数据具有不同的特征( 或属性) 集。 因此，根据分布式数据的是水平划分或垂直划分，将分布式数据挖掘的方法分为 基于垂直分割的分布式数据挖掘方法和基于水平分割的分布式数据挖掘方法。基于垂 直分割的分布式数据挖掘系统有k a r g u p t o 、p a r k 等到提出的汇集型数据挖掘系统 c d m 。基于水平分割的分布式数据挖掘系统有s t o l f o 的j a m 系统、k a r g u p t o 的 p a d m a 系统、c h a v e z 的c h a l l e n g e r 系统。两种方法的分布数据库形式如图2 1 、2 2 所示。 6 重庆大学硕士学位论文 2 分布式数据挖掘 x lx 2x 3 x 4 1o 01 o 21 0o 0 31l1o x 1 x 2x 3x 4 1 00l 1 20l 0 0 i 3lll0 图2 1 水平分布数据库 f i 9 2 1h o r i z o n t a ld i s t r i b u t e dd a t a b a s e x lx 2x 3 x 5 1o 0l l 2 ll00 3lllo 图2 2 垂直分布数据库 f i 9 2 2v e r t i c a ld i s t r i b u t e dd a t a b a s e 2 2 2 两种基本方法 分布式数据挖掘的方法可以分为两步式挖掘方法和三步式挖掘方法。 在两步式挖掘方法中，数据库分布于各地，局部挖掘在各个局部数据库上进行， 然后再将运算结果返回给全局端进行挖掘【- 8 】。整个过程，不需要数据传输和移动。如 图2 3 所示： 在每个分布的数据节点实施传统的知识发现； 将每个站点获得的局部结果整合为一个统一的知识模型。 图2 3 两步式数据挖掘方法 f i 9 2 3t w o s t e pm o d eo f d a t a - m i n i n g 在三步式挖掘方法中，实行集中数据管理策略，局部挖掘节点与数据库节点分离， 7 重庆大学硕士学位论文 2 分布式数据挖掘 数据集被分配并传输至局部节点，再由局部节点在指定的数据子集上进行挖掘，最后， 由全局端进行汇斟19 】。如图2 4 所示： 将数据集分割为p 个子集，p 是处理器的数量，并将每个子集指派给不同的 处理器； 在每个数据子集上应用数据挖掘算法； 整合局部的知识模型，生成全局一致的知识模型。 图2 4 三步式数据挖掘方法 f i 9 2 4t h r e e - s t e pm o d eo f d a t a - m i n i n g 2 2 3 两种方法的优缺点 在上述两种分布式数据挖掘模式中，可以看到：第一种方法强调数据源固有的分 布特性，局部挖掘运行在分布的数据库节点上，不需要数据的移动，使得该模式复杂 度不高，实现起来相对简单；第二种方法实现了集中的数据管理策略，数据库存储节 点与数据挖掘节点分离，数据必须要移动到局部挖掘节点之上，需要较高的通信成本。 另一方面，第一种方法的局部数据挖掘依赖于数据库存储节点，当分布的数据库 存储不均衡，数据过于集中于某一个子数据库时，将会使整个数据挖掘出现负载不均 衡，从而影响到挖掘性能。第二种方法采用的集中的数据管理策略，实行数据动态调 度，使得整个系统的负载更加均衡，而且，由于数据库存储节点与计算节点的分离， 使参与局部挖掘的节点数目可以远远大于数据库节点数目上，数据可以分成小块，运 行于普通的计算终端上，从而更加有效地利用各种闲置计算资源。 两种方法具有一定的相关联性。三步式挖掘方法中，如果数据已经被事先分配到 局部节点上，那么它实际上就转化为了二步式挖掘方法。可以说，二步式数据挖掘方 法是三步式数据挖掘方法的简化形式，而三步式数据挖掘方法更具有代表性。因此， 论文的研究将以三步式挖掘方法为参考。 8 重庆大学硕士学位论文 2 分布式数据挖掘 2 3 分布式数据挖掘的流程 分布式数据挖掘按照挖掘模式的不同，可分为两种流程。图2 5 描述了三步式数 据挖掘流程。首先要对数据进行预处理，把数据转换为统一格式。然后按照某种策略 分配数据，将数据分割成数据子块，传送至局部挖掘节点。局部挖掘节点收到数据块 后，对数据块进行局部数据挖掘。所有局部节点完成挖掘后，将结果送到全局端汇总。 最后呈现给用户。两步式数据挖掘流程略有不同，减少了数据分配环节。 数据清理、集 i 成，转化为统 i 一数据可格式 、l l 采用某种策略 1 分割数据产生 若干数据子集 上 传送数据子集到 局部挖掘节点 上 局部挖掘节点 对数据子集进 行局部挖掘 j r 局部挖掘将产 生的结果送到 全局挖掘节点 全局挖掘节卢汇 总局部数据，进 行全局挖掘，形 成全局结果 图2 5 分布式数据挖掘流程 f i 9 2 5w o r k f l o wo f d i s t r i b u t e dd a t a - m i n i n g 2 4 分布式数据挖掘的研究内容 对分布式数据挖掘的研究可以分为两大类： 数据挖掘算法。它关注知识整合中分布式数据挖掘算法和有效技术的开发。分 布式数据挖掘算法的核心概念是将每个局部数据集独立进行挖掘，然后对获得的结果 整合为一个全局的数据模型。 分布式数据挖掘体系结构。它关注分布式数据挖掘体系结构的开发，着重强调 9 重庆大学硕士学位论文2 分布式数据挖掘 支持分布式数据挖掘软件系统的构成。 2 5 现有分布式数据挖掘系统的主要缺陷 传统分布式数据挖掘系统主要存在着以下不足之处： 系统大多是紧祸合的，局部网络或节点出现故障，将使整个分布式挖掘系统停 止，甚至崩溃。 系统的动态伸缩性差，无法根据用户的要求动态地发现合适的算法、数据集， 也无法根据网络的状况，动态地添加或减少参与挖掘的计算资源。 系统对硬件要求高，一般需要使用大型机或机群系统，挖掘能力、存储能力受 到挖掘硬件限制。 2 6 小结 数据挖掘是一种新兴的数据分析处理技术，帮助人们从大量的、混乱的结构化和 非结构化的数据中发现知识。分布式数据挖掘是利用分布式计算技术来进行数据挖掘 的一种新的知识发现方法。本章着重阐述了数据挖掘和分布式数据挖掘技术主要研究 的内容、挖掘过程、挖掘方法，并提出了传统的分布式数据挖掘主要缺陷。 1 0 重庆大学硕士学位论文 3 网格技术 3 网格技术 3 1 网格的内涵 3 1 1 网格的概念 网格具有两种定义，包括广义的定义与狭义的定义【2 0 】。 广义的网格是一个集成的计算与资源环境，或者说是一个计算资源池。网格能够 充分吸纳各种计算资源，并将它们转化成一种随处可得的、可靠的、标准的、具有经 济价值的计算能力。它的计算资源包括网络通信能力、数据资料、仪器设备，甚至人 也是资源。 狭义的网格是指一般被称为计算网格，即主要用于解决科学与工程计算问题的网 格。根据求解问题的特点，人们又提出了多种名称的网格，如以数据密集型问题的处 理为核心的数据网格，以解决科学问题为核心的科学网格。以全球地球系统模型问题 求解为主要目的地球系统网格等。 3 1 2 网格的目的 网格是借鉴电力网的提出来的，网格的最终目的是希望用户在使用网格计算能力 时，就如同现在使用电力一样方便例。我们在使用电力时，不需要知道它是从哪个发 电站输送出来的，也不需要知道该电力是由什么样的发电机产生的，不管是水力发电， 还是火力发电，我们使用的是一种统一形式的电能。网格也希望给用户提供的是与地 理位置无关、与具体的计算设施无关的通用的计算能力。 网格和电力网都有资源消费者和资源提供者，对于电力网来说资源提供者是发电 站，对于网格来说资源提供者是计算机、存储设备、网络设备等物理资源；对于电力 网来说，资源消费者就是各种消耗电能的设备，对于网格来说资源消费者就是使用网 格资源求解问题的用户。不管是电力网还是网格，他们都有覆盖范围广泛，组成资源 多样的特点。正如电力网中需要有大量的变电站等设施对电网进行调控一样，网格中 也需要大量的管理节点来维护网格的正常运行。 3 2 网格的特点 3 2 1 分布与共享 分布性是网格的一个最主要的特点。网格的分布性首先是指网格的资源是分布 的。组成网格的计算能力不同的计算机，各种类型的数据库乃至电子图书馆，以及其 它的各种设备与资源，是分布在地理位置互不相同的多个地方，而不是集中在一起的。 图3 1 反映了网格的分布性。 重庆大学硕士学位论文 3 网格技术 图3 1 网格的分布性【2 0 1 f i 9 3 1d i s t r i b u t i n gc h a r a c t e r i s t i co f g r i d 2 0 ) 因为网格资源是分布的，因此基于网格的计算一定是分布式计算而不是集中式计 算。在网格这一分布式环境下，需要解决资源与任务的分配和调度问题、安全传输与 通信问题、实施性保障问题、人机交互以及人与人之间交互的问题等等。 网格资源虽然是分布的，但是它们却可以充分共享，即网格上的任何资源都可以 提供给网格上的任何使用者。共享是网格的目的，没有共享便没有网格，解决分布资 源的共享问题，是网格的核心内容。分布是网格硬件在物理上的特征，共享是在网格 中间件支持下实现的逻辑上的特征，这两者对于网格来说都是十分重要的。 3 2 2 自相似性 网格的另一个非常重要的特征是自相似性( 2 - 】。自相似性是许多自然事物的一个重 要特征，网格也不例外。网格的局部和整体之间存在着一定的相似性，局部往往在许 多地方具有全局的某些特征，而全局的特征在局部也有一定的体现。当然，从另一个 方面来说，网格的整体与局部之间具有自相似性，也必须具有不同的地方。 3 2 3 动态性与多样性 网格的动态性( 2 2 】包括动态增加和动态减少两个方面的含义。原来拥有的资源或者 功能，在下一时刻可能就会出现故障或者不可用；而原来没有的资源，可能随着时间 的推移会不断地加入进来。 网格资源的动态变化特点要求网格管理必须充分考虑并解决好这一问题，对于网 格资源的动态减少或者资源出现故障的情况，要求网格能够及时采取措施，实现任务 的自动迁移，做到对高层用户透明或者尽可能减少用户的损失。 网格资源的动态增加需要提高网格的扩展性问题，也就是说在网格的设计与实现 时，必须考虑到新的资源能否很自然地加入到网格中来，并且可以和原来的资源融合 在一起，共同发挥作用。网格的扩展性要求体现在规模、能力、兼容性等几个方面。 一开始网格的规模往往不是特别大，不需要也不可能一步到位，但是网格应该能够允 许对它自身进行多种形式的扩展，网格规模扩展后，网格的相应管理软件也应该能够 满足扩展性的要求，网格软件的升级要能够向下兼容。 网格的多样性主要体现在网格资源的异构和多样性。在网格环境中可以有不同体 1 2 重庆大学硕士学位论文 3 网格技术 系结构的计算机系统和类别不同的资源， 不同类别资源之间的通信和互操作问题。 为网格软件的设计提出了更大的挑战。 3 2 4 自治性与管理的多重性 因此网格系统必须能够解决这些不同结构、 正是因为异构性或者说资源多样性的存在， 网格上的资源，首先是属于某一个组织或者个人的。因此网格资源的拥有者对该 资源具有最高级别的管理权限，网格应该允许资源拥有者对他的资源有自主的管理能 力，这就是网格的自治性【2 3 】。 但是网格资源也必须接受网格的统一管理，否则不同的资源就无法建立相互之间 的联系，无法实现共享和互操作，无法作为一个整体为更多的用户提供方便的服务。 因此网格的管理具有多重性。一方面它允许网格资源的拥有者对网格资源具有自 主性的管理，另一方面又要求网格资源必须接受网格的统一管理。 3 3 网格的体系结构 网格的体系结构包括两种主要形式，一种是以协议为中心的五层沙漏结构伫4 】，另 一种是以服务为中心的开放网格服务结构【2 5 1 。 3 3 1 五层沙漏结构 五层沙漏结构是一种影响十分广泛的结构，它的主