基于网格服务的分布式数据挖掘.pdf

《基于网格服务的分布式数据挖掘.pdf》由会员分享，可在线阅读，更多相关《基于网格服务的分布式数据挖掘.pdf（4页珍藏版）》请在三一文库上搜索。

1、Computer Engineering and Applications 计算机工程与应用2010， 46 （28） 1引言 在现实的应用环境中，大部分海量数据库都是以分布式 形式存在的， 将这些分布式存储的数据集中到一个数据仓库 中进行集中式挖掘处理， 这样会造成分布式数据的安全性、保 密性方面以及挖掘效率等问题，也给网络通信带宽提出很高 的要求。为了解决这样的问题，传统的分布式数据挖掘已经 做了不少研究， 其中 Agent 技术是众多学者应用最广泛的 1 。 文献 2 中提出的 JAM 系统是一种面向元学习的基于Java和 多 Agent 的分布式系统。文献3中提出的 Kensingto

2、n 数据挖 掘体系结构，它是基于 3层 C/S 结构的并行分布式数据挖掘系 统。文献 4中提出的BODHI 系统是一种基于Agent 的分布 式挖掘系统， 主要利用 Agent 来交换信息， 通过较低的网络通 信负载来保证局部和全局模型的正确性。在文献5中， Krish- naswamy等人也提出了基于分布式Agent 的数据挖掘平台， 主 要是通过 Internet 来传输数据挖掘服务。文献6 提出了基于 移动 Agent 的分布式数据挖掘， 通过移动 Agent 来发现各种数 据挖掘所需的服务从而更好地为数据挖掘服务，从而解决了 由于网络拥塞、 不安全以及不可靠所造成的各种问题。Kar-

3、gupta等提出了 PADMA 分布式数据挖掘模型，它的主要功能 就是利用 Agent技术来完成同构数据站点的分布式数据挖掘 7。 Bailey 等提出了基于Java和移动 Agent 的分布式数据挖掘系 统 Papyrus， 该系统利用Agent 技术完成广域网内异构数据站 点之间的聚类分析 8 。上述这些分布式系统都较好地解决了 传统的集中式数据挖掘所带来的扩展性弱等问题，但这些分 布式系统无法动态发现合适的算法、数据集以及各种计算资 源， 资源之间的共享和协作机制较差。 从文献 9-10 中可以看出， 网格是处理计算和数据密集型 应用的分布式并行计算平台，具有自适应性、 动态性以及良好

4、的扩展性等优势， 而分布式数据挖掘算法和知识发现过程正 是一个计算和数据密集型应用，鉴于网格的优势， 近年来许多 学者就网格平台下分布式数据挖掘进行了深入的研究。An- tonio Congiusta 等提出了基于网格服务的分布式数据挖掘应 基于网格服务的分布式数据挖掘 邓勇， 王汝传，邓松 DENG Yong， WANGRu-chuan， DENG Song 南京邮电大学计算机学院，南京 210003 School of Computer， NanjingUniversity of Posts and Telecommunications， Nanjing 210003， China E-m

5、ail ： DENGYong， WANGRu-chuan ， DENGSong.Distributeddata miningon gridservices.ComputerEngineeringand Appli- cations ， 2010， 46 （28） ： 6-9. Abstract ：This paper presents distributed data miningplatform on grid services， which combines grid services withdistribut- ed data miningto solve problems of t

6、raditionaldata mining.Meanwhile ， this paper implementsDistributedBP Classification Algorithmon GridServices （DBPC-GS） .Simulationexperiments show that contrasted withconcentrative algorithms， the aver- age consumptive time of DBPC-GS decreases apparently， and CPU load is reduced about 40% with incr

7、ements of grid codes. Key words ：distributed data mining ； grid service； BP net； classification 摘要： 在分析传统分布式数据挖掘平台不足的基础上，结合网格服务的思想， 提出了基于网格服务的分布式数据挖掘平台，同 时在该平台上， 实现了分布式BP 网络分类算法 （GBPC-GS） 。仿真实验表明， 与单机环境相比， 随着网格节点数增加， 算法的平均 耗时明显下降， 同时 CPU的负载也下降了约40%。 关键词：分布式数据挖掘； 网格服务；BP网络；分类 DOI ： 10.3778/j.issn.100

8、2-8331.2010.28.002文章编号：1002-8331 （2010） 28-0006-04文献标识码：中图分类号：TP311 基 金 项 目 ： 国 家 自 然 科 学 基 金（the NationalNaturalScienceFoundationofChinaunderGrantNo.60973139 ， No.60773041 ，No.61003039 ， No.61003236 ）； 江苏省自然科学基金（the NaturalScience FoundationofJiangsu Provinceof China underGrant No.BK2008451 ） ； 省 级

9、 现 代 服 务 业 发 展 专 项 资 金 ； 国 家 和 江 苏 省 博 士 后 基 金（No.0801019C ，No.20090451240 ，No.20090451241 ， No.20100471353 ， No.20100471355 ，No.20100471356 ）； 江 苏 省 高 校 科 技 创 新 计 划 项 目（No.CX09B_153Z， No.CX10B-260Z ，No.CX10B-261Z ，No. CX10B-262Z ， No.CX10B-263Z ） ； 江苏省六大高峰人才项目（No.2008118） ； 江苏省计算机信息处理技术重点实验室基金。 作者简

10、介： 邓勇（1977-）， 男，博士生，主要研究方向为网格计算、计算机软件等； 王汝传（1943-） ， 男，教授，博士生导师， 主要研究方向为计算机软 件、 计算机网络、 信息安全、 移动代理技术等； 邓松（1980-） ， 男， 博士生，主要研究方向为网格计算、数据挖掘、 计算机软件等。 收稿日期： 2009-08-11修回日期： 2010-08-23 6 2010， 46 （28 ） 用， 同时指出在知识网格平台下，利用网格服务来搜索网格资 源、 执行分布式数据挖掘算法等 11-13 。DomenicoTalia等在文 献14 中指出了 WSRF 已经成为开发网格应用的标准，同时利 用基

11、于 WSRF 的 Weka4WS 数据挖掘工具在网格平台下实施 具体的分布式数据挖掘。MarioCannataro等为了在网格下更 好实施分布式数据挖掘，提出了知识网格系统，并在文献 15 中详细地描述了知识网格的架构以及具体的实施分布式数据 挖掘技术细节。以上网格下分布式数据挖掘应用都是在以 Globus Toolkit 为网格中间件的基础上开发实现的，开发和部 署过程较为复杂， 而 GT4 WS-core是 Globus Toolkit 的 Java实 现， 为了简化整个网格服务的开发过程同时充分体现网格本 身的优势，本文以 GT4 WS-Core 为基础来开发和部署分布式 数据挖掘中所使

12、用的网格服务，从而可以大大简化整个分布 式数据挖掘开发和部署的过程。 主要工作如下： （1） 提出了以 GT4 WS-Core 为基础的分 布式数据挖掘框架， 并在此框架下， 阐述了基于网格服务的分 布式数据挖掘客户端和服务端开发过程；（2 ） 在上述分布式平 台基础上，实现了基于网格服务的分布式BP网络分类算法； （3） 对分布式BP网络分类算法和传统集中式BP 分类算法进 行了比较实验， 并进行了性能分析。 2基于网格服务的分布式数据挖掘 2.1体系结构 基于网格服务的分布式数据挖掘就是在网格中间件基础 上， 开发和部署网格服务来完成数据挖掘和知识发现过程的 各个步骤，良好的分布式数据挖掘

13、体系结构使得系统具有较 强的可扩展性以及较小的通信代价。整个基于网格服务的分 布式数据挖掘体系结构由客户端和服务端两部分组成，如图 1 所示。其中客户端主要提供图形化界面供用户输入各种参数 以及最后挖掘结果的可视化显示，服务端主要包括核心网格 服务、各种数据挖掘 （Data Mining ， DM）算法资源、 待处理的 数据资源以及计算资源等，所有这些资源都以网格服务的形 式部署在服务端， 整个客户端和服务端的交互也是通过网格 服务进行通信。 其中客户端主要包括参数输入和可视化模块，用户通过 参数输入模块输入具体数据挖掘算法所需要的参数以及远程 网格服务的URL 地址等。可视化模块主要通过各种

14、可视化 的方法对整个数据挖掘过程进行可视化，使得整个分布式数 据挖掘过程更直观。 服务端主要包括资源发现服务、数据传输服务、 挖掘结果 显示服务以及各个部署在远程服务器上的数据挖掘DM 算法 服务等。用户在通过客户端输入相应参数后通过资源发现服 务来找到已经部署相应数据挖掘算法服务和计算资源的 URL ， 利用此 URL 来远程执行数据挖掘过程。由于在基于网 格的分布式数据挖掘过程中，待挖掘的数据资源不一定在用 户已经选择的计算资源上，为了处理这些数据必须通过数据 传输服务把待处理的数据传输到用户选择的计算资源上。而 且为了方便用户监控整个分布式数据挖掘过程，系统要对整 个挖掘过程进行可视化操

15、作，最后通过挖掘结果显示服务来 把最终挖掘得到的结果显示给用户。 在体系结构中采用网格服务来开发和部署分布式数据挖 掘应用，网格服务是建立在Web服务基础上的， 一种动态、 有 状态的特殊的Web服务， 它既能保留 Web服务的优势， 而且能 够克服传统 Web服务的缺陷 16 。而传统的分布式数据挖掘的 体系结构大都是利用Agent 机制来进行分布式数据挖掘的，而 基于网格服务实现分布式数据挖掘理论上具有无限可扩展性 和良好的伸缩性， 且网格服务很容易修改成具有安全特征的 网格服务。 2.2服务端 在基于网格服务的分布式数据挖掘应用中，服务端开发 是最重要的一部分， 整个数据挖掘过程都是在服

16、务端完成的， 这样既能简化客户端的开发，又能充分利用网格资源共享和 协同处理的优势。从图1 中可以看出整个服务端的开发主要 就是利用 GT4 WS-Core来开发挖掘结果显示服务以及各种 DM 算法服务等， 并在数据处理过程中利用已有的资源发现 服务和数据传输服务来进行计算资源的发现以及数据的传 输。故在本文的服务端开发中，各种 DM 算法服务以及挖掘 结果显示服务的开发是最重要的，而对于不同功能的网格服 务开发步骤是一致的，只是具体的参数不同。下面以数据挖 掘算法为例说明如何利用GT4 WS-Core来开发网格服务， 整 个步骤如下所示： （1） 配置开发网格服务相应的环境变量； （2）编

17、写 各 个 网 格 服 务 对 应 的 WSDL 、 WSDD 、 JNDI 、 build.xml 以及必要的属性文件。其中WSDL 文件定义了具体 的网格服务所执行的操作以及必要的参数。WSDD 文件为网 格容器提供了有关网格服务本身的一些信息，提示网格服务 容器如何发布网格服务。JNDI 是查询对象所使用的一个应 用程序编程接口 （API） ， 通过调用这个API ， 应用程序就可以 确定由一个易读的JNDI 名所确定的资源和其他程序对象的 位置。 build.xml 主要用来对GT4 WS-Core 编译文件中的操 作进行协调。属性文件主要包含指导各种编译任务通过. GAR 的创建和部

18、署过程所需的属性； （3） 编写各种 DM 算法的网格服务端代码。各种DM 算法 网格服务代码主要是根据WSDL 文件中定义的各种算法参数 以及各种操作方法进行编写，客户端通过输入参数可以调用 相应的网格服务远程执行分布式数据挖掘。 定义 1 （网格服务，Grid Service） 在具体的基于网格服务 的应用开发中， 一个完整的网格服务可以定义为六元组：GS= WL ， WD ， JD， BUILD ， P， 其中 WL 表示网格服务所需的WS- DL 文件，WD 表示网格服务的部署描述符WSDD 文件，JD表 提出请求 客户端 参数输入可视化 核心网格服务WS-Core 资源发现 服务 数

19、据传输 服务 挖掘结果 显示服务 服务器 1 DM 算法资源 计算资源 服务器 2 DM 算法资源 计算资源 服务器 n DM 算法资源 计算资源 服 务 端 图 1基于网格服务的分布式数据挖掘体系结构图 邓勇， 王汝传，邓松： 基于网格服务的分布式数据挖掘7 Computer Engineering and Applications 计算机工程与应用2010， 46 （28） 示 JNDI 应用程序编程接口， BUILD 表示编译网格服务所需的 build.xml 文档， P表示编译网格服务所需的属性文件。 2.3客户端 一个完整的网格应用程序除了服务端程序，还需要能够 灵活调用相应网格服务

20、的客户端代码。整个网格数据挖掘应 用客户端开发的步骤如下所示： （1） 利用生成的类为远程的网格服务创建一个代理存根； （2） 通过 WS-Core 中自带的 ContainerRegistryService 服务 来查询已有的数据挖掘网格服务，用户根据需要选择在哪几 个远程节点上执行数据挖掘过程； （3） 用户根据待挖掘的数据是否处于远程计算节点上，来 决定是否调用数据传输服务把本地数据传输到指定的远程计 算节点上； （4） 选择需要调用数据挖掘网格服务的地址serviceURL ， 根据这个具体的服务地址，对数据进行分布式数据挖掘； （5） 对于挖掘完成的结果， 用户调用挖掘结果显示服务来

21、 把分布式数据挖掘的结果可视化。 用户利用客户端可以很好地监控网格下分布式数据挖掘 的整个过程，并且对分布式挖掘结果进行有效的可视化显示。 3基于网格服务的分布式BP 网络分类算法 3.1算法描述 针对 BP网络算法对于海量数据训练时间长的缺陷，在图 1 所示的分布式平台下，实现了基于网格服务的分布式BP 网 络 分 类 算 法（Distributed BP Classification Algorithm on Grid Services， DBPC-GS） 。主要思想是首先通过编写BP 算法网格 服务所需的 WSDL 、 WSDD 文件等来开发和部署该网格服务； 其次对海量数据进行数据分块

22、，然后分别通过数据传输服务 把数据传输到部署BP 算法服务的服务端； 最后通过客户端的 网格门户来并行地远程调用和执行BP分类算法，然后通过可 视化技术把分类结果在客户端显示出来。 一个完整的网格平台下算法的实现包括客户端和服务端 两部分，下面分别从服务端和客户端来描述基于网格服务的 分布式 BP网络分类算法， 具体的思想如下所示： 算法 1 基于网格服务的分布式BP网络分类算法 输入：BP 算法服务地址BPGSH ； 输入层节点数InCode ， 隐层节点 数 HideCode ， 输出层节点数OutCode， 学习效率StudyEfficient ； 算法迭 代次数 Echo_Time ；

23、 算法精度Precision 。 输出：分类精度ClassificationPrecision。 Begin 服务端： 1.Receive （InCode， HideCode， OutCode，StudyEfficient ， Echo_Time ， Precision ， BPGSH ， i， SampleData i） ； /从客户端接收BP 算法的参数、 具体的 BP 算法服务地址以及待分类的样本数据块名等各种参数； 2.Initial（） ； /初始化 BP 网络的结构； 3.intTotalNum=Statistics（SampleData）； /统计待分类样本数据的 个数； 4.w

24、hile （echoEcho_Time ） 5.计算隐层、输出层的纯输入和输出； 6.计算输入层到隐层以及隐层到输出层的误差； 7.BP 网络结构的更新； 8.ClassifiedNum+ ； / 统计被正确分类的样本个数； 9.doublePrecision i=ClassifiedNum/TotalNum； /统 计 局 部 分 类 精度； 客户端： 10.intgridcodes=SelectGridCodes （ ）； /选择部署BP 算法服务的 网格节点； 11.for （int i=0； igridcodes ； i+） 12.StringSampleData i=Partitio

25、n （gridcodes ， data ）； /对待分 类的样本数据根据选择网格节点数进行分割； 13.DataTransService（i， SampleData i ）； /通过数据传输服务 把分割好的数据块传送到指定的网格节点处； 14.Receive （InCode ，HideCode ，OutCode ，StudyEfficient， Echo_Time ， Precision ， BPGSH ， i， SampleData i）； /传递服务端所需的 参数； 15.doubleprecision+=DataTransService （Precision i） ； / 把第 i 个网

26、格节点所得到的局部分类精度返回到客户端； 16.ClassificationPrecision=precision/gridcodes； /计算全局分类精度； 17.Show （ClassificationPrecision ）； / 返回分类精度并可视化显示； End 从上述算法的描述中可以看出，整个基于网格服务的分 布式 BP分类算法的执行时间主要包括数据的传输时间以及 BP 算法对于局部数据块的分类时间，且网格下执行BP 算的 时间复杂度并没有改变。下一节的仿真实验表明，在局域网 环境下，随着待处理数据的数据量和复杂度的增大，数据分块 后传输到各个指定网格节点上的时间比BP 算法处理整个

27、海 量数据的时间要小得多。 3.2仿真实验和分析 为了验证基于网格服务开发分布式数据挖掘的可行性和 有效性，在实验室局域网的环境下做了分布式BP 网络分类挖 掘的实验。整个实验平台为Windows XP+WS-Core-4.0.2+ Jdk1.5+Eclipse3.1+Tomcat5.17 ， 所有的程序由Java语言实现。 同时采用了学术界公认的UCI 标准数据集作为测试数据 17。 利用 BP 神经网络算法对文献17 中的 waveform-5000、 isolet5 和 Letter Recognition 数据进行分类， 表 1 给出了它们的 数据属性。表2 给出了 BP 神经网络算法

28、对waveform-5000、 isolet5 和 Letter Recognition 数据进行分类时的参数说明。从 表 1中可以看出数据集较为复杂，利用 BP 神经网络算法对数 据集进行分类是一个非常艰巨的任务。为了更好地利用网格 的计算资源， 把 BP 神经网络算法服务部署到4 个网格节点 中 。 图 2 比 较 在 单 机 和 网 格 平 台 下 利 用 BP 算 法 对 wave- form-5000 、 isolet5 和 Letter Recognition 数据进行分类时的平 均耗时情况。图3 则显示了利用BP 算法对 waveform-5000、 数据集名称 waveform

29、-5000 isolet5 Letter Recognition 数据集大小 5 000 1 559 20 000 数据集属性个数 40 617 16 分类属性个数 3 60 26 表 1数据属性 BP 神经网络算法参数 输入层节点数 隐层节点数 输出层节点数 学习效率 算法迭代次数 算法精度 waveform-5000 40 81 2 0.53 5 000 0.000 1 isolet5 617 1 235 6 0.53 5 000 0.000 1 Letter Recognition 16 33 5 0.53 5 000 0.000 1 数据集名称 表 2BP 神经网络算法参数 8 201

30、0， 46 （28 ） isolet5 和 Letter Recognition 数据在单机和4 个网格节点并行 处理的情况下的CPU 负载变化情况。图4 表明在网格平台 下， 与单机环境相比， BP 神经网络对于waveform-5000 ， isolet5 和 Letter Recognition 数据集仍然保持较高的分类准确率。 由图 2 可知，利用 BP 神经网络在单机和1个网格节点的 条件下， 分别对 waveform-5000、 isolet5 和 LetterRecognition 数据集进行分类时，网格下处理的耗时要高于单机环境。这 是因为在 1 个网格节点的条件下，首先数据要

31、从客户端传输 到服务端，然后服务端分类完数据后，还要把分类的结果传输 到客户端进行处理和显示，所以网格环境下分类两个数据集 的耗时等于算法处理的时间还要加上数据传输的时间。在网 格环境下，随着网格节点数的增加，从图 2中可以看出， BP 算 法总的耗时有着明显的下降，数据集越大在网格下的优势越 明显。 从图 3 中可以看出在单机和1个网格节点的条件下， 网格 下处理的 CPU 负载比单机环境要略高，主要是因为网格环境 下， 除了服务端远程执行数据分类的CPU开销外，还包括客户 端提交数据以及服务端分类结果返回的CPU开销。而在网格 环境下，随着网格节点数量从1增加到 4， CPU负载不断下降，

32、 最大下降了约40%。 虽然从图 2 中看出，利用网格平台进行BP神经网络分类， 提高了 BP 算法处理复杂数据集的效率，减少了 BP 算法运行 时间。但是利用BP算法对 waveform-5000 和 isolet5 数据集进 行分类时，不光要求提高算法的效率，分类的准确率也要求不 能下降，否则利用网格平台来进行分布式数据挖掘在实际问 题上是不可行的。图4 就证明了利用 BP 算法在网格平台下进 行分布式分类挖掘时的准确率和单机环境相比，仍然维持一 个大致相同的分类准确率。 4总结 在分析传统分布式数据挖掘不足的基础上，结合网格服 务的思想，提出了基于网格服务的分布式数据挖掘平台，并在 此平

33、台上，以 BP 算法为例，实现了基于网格服务的分布式BP 网 络 分 类 算法（GBPC-GS）。 针 对 waveform-5000 、 isolet5 和 Letter Recognition 数据集而言， 做了详尽的仿真实验， 仿真结 果表明了基于网格服务的分布式BP 分类算法的平均耗时明 显下降，而且随着网格节点个数的增加，CPU负载最大下降了 约 40%。 参考文献： 1KluschM ， LodiS， MoraG L.Agent-baseddistributeddata min- ing ： TheKDECschemeJ.IntelligentInformationAgents，

34、2003： LNAI2586， 104-122. 2ProdromidisAL， Chan P K ， StolfoS J.Meta-learningindis- tributeddata miningsystems： Issues and approachesC/Kargup- taH，Chan P.AdvancesinDistributedandParallelKnowledge Discovery.S.l. ： MIT/AAAIPress， 1999. 3CharttratichatJ，DarlingtonJ， GuoY， etal.Anarchitecturefor distribut

35、edenterprisedata miningC/LectureNotes inComput- er Science 1593： HPCNEurope 1999.S.l. ： Springer ， 1999. 4KarguptaH.Distributedknowledgediscoveryfromheteroge- neoussitesEB/OL.DIADICLaboratory ，UniversityofMary- land at BaltimoreCountry.http ： /www.cs.umbc.edu/hillol. 5Grossman R， BaileyS， Ramu A， et

36、 al.Thepreliminarydesign of papyrus： Asystems forhighperformance ， distributeddata min- ing over clustersM/KarguptaH， Chan P.Advances in Distribut- edandParallelKnowledgeDiscovery.MenloPark，California ： AAAIPress/The MITPress， 2000： 259-275. 6LiXi-ning ， NiJing-bo.Deployingmobileagentsindistributed

37、dataminingC/LNAI4819 ：PAKDD2007Workshops ，2007： 322-331. 7KarguptaH，HamzaogluI，StaffordB.Scalable，distributeddata miningusinganagent-based architectureC/Proc3rdInterna- tionalConferenceon KnowledgeDiscoveryand DataMining. NewportBeach， California ， USA ： AAAIPress， 1997： 211-214. 8BaileyS，GrossmanR，

38、SivakumarH，etal.Papyrus：Asystem for data miningoverlocaland widearea clustersand super- clustersC/Proc Conference on Supercomputing.S.l. ： ACMPress， 1999. 9Foster I.Globustoolkitversion4： Softwareforservice-oriented systemsC/LNCS3779： Conf on Networkand ParallelComput- ing， 2005： 2-13. 10徐志伟，冯百明，李伟

39、.网格计算技术M. 北京：电子工业出版社， 2004. 11CongiustaA ， TaliaD， TrunfioP.On designingand composing gridservicesfordistributeddataminingM/FutureGenera- tionGrids.S.l. ： SpringerUS， 2006. 1234单机 单机和网格节点数 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 C P U 负 载 /（ % ） waveform-5000 isolet5 Letter Recognition 图 3单机和网格下进行

40、BP 分类的 CPU 负载变化 1234单机 单机和网格节点数 3500 3000 2500 2000 1500 1000 500 0 B P 神 经 网 络 算 法 平 均 耗 时 /swaveform-5000 数据集 isolet5 数据集 Letter Recognition 数据集 图 2单机和网格下进行BP 分类的平均耗时比较 单机1234 单机和网格节点数 waveform-5000 isolet5 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 分 类 准 确 率 /（ % ） 图 4单机和网格平台下BP 算法分类准确率比较 （下转 60页） 邓勇， 王汝传，邓松： 基于网格服务的分布式数据挖掘9