（计算机应用技术专业论文）数据挖掘工作流的发现和复用.pdf

中文摘要 由于数据挖掘模式的多样性、挖掘过程的非平凡性、挖掘算法的复杂性，使 得构造一个完整的知识发现流程往往是耗时的，而且需要领域专家和算法设计人 员的多方参与。这些流程不仅可以揭示知识发现过程，而且含有针对某类具有共 性问题的解决方案。因此，如果能够对这些工作流进行发现和复用的话，可以大 大缩短工作流的创建时间，提高工作流的创建质量。 在本文中，我们利用本体论的方法实现了一个数据挖掘工作流发现和复用系 统。主要工作包括： 1 、根据用户的需求和数据挖掘工作流的特点，提出了数据挖掘工作流的四 层描述模型：1 ) 自然语言描述；2 ) 将工作流当作一个原子服务来描述；3 ) 将 工作流当作一个组合服务来描述；4 ) 对工作流的结构进行描述。 2 、根据这个四层描述模型，建立了知识发现领域的本体，在本体中确定了 数据挖掘领域的类，关系，公理，再利用它们对工作流资源进行组织。并利用 o w l 语言实现了该本体。 3 、提出了工作流查询的体系结构，由以下四个部分组成：图形化用户界面， 查询处理模块，关键字查询模块，语义查询模块。在语义查询模块中，利用 s p a r q l 语言实现了基于本体的语义查询。在数据挖掘工作流本体中，利用 t - b o x 中的推理来进行本体的维护，利用a b o x 的推理来回答用户的查询，在 a b o x 中，我们实现了三种类型的推理：1 ) 垂直推理；2 ) 水平推理；3 ) 新关 系的推理。通过这些推理规则的引入，该系统就可以更好的支持用户的复杂查询， 提高了搜索的查全率和查准率。 4 、实现了一个数据挖掘工作流发现和复用的原型系统，该系统采用三层体 系结构，分别为：存储层，管理层和g u i 层。这样可以让用户通过可视化界面 来操作本体以进行数据挖掘工作流的查找，在该系统中，我们还提供了一些规范 化的术语，以规范用户的输入来获得更准确的查询结果。 现阶段，对于工作流设计的生命周期，系统支持工作流的查找，编辑和运行， 但是还不能够支持工作流的发布。系统还不提供工作流的关键字查找。这两个问 题将是我们下一步的研究工作。 关键词：数据挖掘工作流发现复用本体推理 a b s t r a c t a st h ed i v e r s i t yo fm i n i n gp a t t e r n s ，t h en o n - t r i v i a l i t yo fp r o c e s sa n dt h e c o m p l e x i t yo fa l g o r i t h mi nd a t am i n i n g ，i t sa l w a y sat i m e - c o n s u m i n gp r o c e s st o c o n s t r u c tan e ww o r k f l o wf r o mt h ev e r yb e g i n n i n g ，w h i c ho f t e ni n v o l v e st h e p a r t i c i p a t i o no fd o m a i ns p e c i a l i s t sa n da r g o r i t h md e s i g n e r s t h ew o r k f l o wi sn o to n l y ap r o c e s st o d i s c o v e r yk n o w l e d g e ，b u ta l s oc o n t a i n sc o m m o ns o l u t i o n st o c e r t a i n t y p e so fi s s u e s t h e r e f o r e ，t h er e u s eo fe x i s t i n gw o r k f l o w sc a nd e c r e a s et i m ea n d i m p r o v et h eq u a l i t yi nb u i l d i n gn e ww o r k f l o ws i g n i f i c a n t l y i nt h i sp a p e r , w ei m p l e m e n tas y s t e mf o rt h ed i s c o v e r ya n dr e u s eo fd a t am i n i n g w o r k f l o wu s i n gt h eo n t o l o g ya p p r o a c h m ym a i nw o r ki n c l u d e s ： 1 、c o n s i d e r i n gu s e r sr e q u i r e m e n t sa n dc h a r a c t e r so f t h ed a t am i n i n gw o r k f l o w , w ed e s c r i b ew o r k f l o wi nf o u rl e v e l s ：1 ) n a t u r a ll a n g u a g ed e s c r i p t i o n , 2 ) d e c l a r a t i v e d e s c r i p t i o na sa na t o m i cs e r v i c e ，3 ) d e c l a r a t i v ed e s c r i p t i o na sac o m p o s i t es e r v i c e ，4 ) p r o c e d u r ed e s c r i p t i o n 2 、a c c o r d i n gt ot h ed e s c r i p t i o n s ，w ec r e a t eaw o r k f l o wo n t o l o g yi nw h i c hw e d e f i n es o m ec l a s s e s ，r e l a t i o n s ，a x i o m sa n du s et h e mt oo r g a n i z et h ew o r k f l o w r e s o u r s e s t h eo n t o l o g yi si m p l e m e n t e di no w ll a n g u a g e 3 、w ep r o p o s ea na r c h i t e c t u r ec o n s i s t i n go ff o u rm o d u l e s ：g u i ，q u e r yp r e p r o c e s s ， k e yw o r d sq u e r ya n ds e m a n t i cq u e r yf o rs e a r c h i n gw o r k f l o w s i ns e m a n t i cq u e r y m o d u l e ，w ec a r r yo u tt h es e m a n t i cd i s c o v e r yu s i n gs p a r q ll a n g u a g e t h e nw e i n t r o d u c ei n f e r e n c et ot h ew o r k f l o wo n t o l o g yw h e r et - b o xi su s e dt om a i n t a i nt h e o n t o l o g y , a n da - b o x t oa n s w e ru s e r sq u e r y i na b o x ，w ei m p l e m e n tt h r e ek i n d so f i n f e r e n c e s ：1 ) v e r t i c a li n f e r e n c e ，2 ) h o r i z o n t a li n f e r e n c e ，3 ) n e wr e l a t i o n s h i pi n f e r e n c e h a l l ，t h r o u g ht h e s ei n f e r e n c e s ，o u rs y s t e mc a ns u p p o r tc o m p l e xs e a r c h , a n dt h er e s u l t i sv e r yp r e c i s e 4 、w ei m p l e m e n tap r o t o t y p es y s t e mw h i c hh a st h r e el e v e l s ：s t o r a g el a y e r , m a n a g e m e n tl a y e r , g u il a y e r w ea l s op r o v i d es o m es t a n d a r d l i z e dt e r m st on a r r o w t h eq u e r yw o r d sf o ri m p r o v i n gt h eq u e r yp e r f o r m a n c e n o wt h es y s t e mh a ss u p p o r t e dt h ed i s c o v e r y , e d i t o r , a n dr u n n i n go ft h ew o r k f l o w l i f e c y c l e ，b u ti td o e sn o ts u p p o r tt h ew o r k _ f l o wp u b l i s h m e n t a l s ot h es y s t e md o e sn o t s u p p o r tk e y w o r ds e a r c h t h et w oi s s u e sw o u l db eo u rf u t u r ew o r k s k e yw o r d s ：d a t a m i n i n g ，w o r k f l o w , d i s c o v e r y , r e u s e ，o n t o l o g y , i n f e r e n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：韩心、复 签字日期： 娜矿年多月日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权：叁盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 韩小费 签字日期：kg 年月f 日 导师签名雹奄 签字日期：z 唧年月7 日 第一章绪论 1 1 研究背景 第一章绪论 近十几年，随着科学技术的迅速发展，经济和社会都取得了极大的进步，与 此同时，在各个领域产生了大量的数据，人们为了利用计算机技术来处理这些数 据，发明了数据库技术，该技术的迅速发展使得利用计算机处理数据成为可能， 但是面对不断增加如潮水般的数据，人们已不再满足于数据库的查询功能，提出 了深层次问题：能不能从数据中提取信息或者知识为决策服务。对于这个需求， 数据库技术已经显得无能为力了，同样，传统的统计技术也面临了极大的挑战。 这就急需有新的方法来处理这些海量般的数据。于是，人们结合统计学、数据库、 机器学习等技术，提出数据挖掘来解决这一难题。 传统的数据挖掘都是集中式的数据挖掘，即建立一个数据仓库，然后利用工 具进行挖掘，其特点是数据量大，运算时间长，算法有限。然而在很多情况下， 用户的数据可能是分布的，由多个组织所共享的，数据挖掘工具也有可能是由多 个组织提供的。这就产生了对分布式数据挖掘的需求。 网格计算是由很多异构的机器组成，在地理上分布的计算平台，它提供给用 户一个统一的接口。网格计算已经被公认为一个很重要的计算模型了，与其它一 般的分布式计算系统相比，它的特点是大范围的资源共享，创新的计算方式和高 性能的计算。网格计算最初的应用领域是高级科学计算和工程计算，如今网格已 经是高性能计算的基础设施，被用在动态的，多机构的虚拟组织中来实现资源的 共享和问题的求解【l j 。 除了在工业和商业领域使用的计算网格之外，数据网格也不断的发展。数据 网格设计的目标是用来实现大规模的数据方便的存储和移动。它们是加强的计算 网格，是用来支持分布式数据密集型应用。数据网格目前主要的动机就是数据处 理，例如，欧盟数据网格【2 】和日本的网格数据农场【3 】项目等。特别是，g l o b u s 的 数据网格项目 4 】是目前正在进行的定义和发展持久性数据网格中间件，提供下列 功能： 一个高性能，安全，稳健的数据传输机制。 一套用于创建和操纵复制出的大型数据集的工具。 一个保持目录数据集复制品的机制。 第一章绪论 数据网格中间件的关键是对网格上数据的管理，但是在许多科学和商业领域 还需要重要的工具和环境来支持数据的分析和知识的发现。这些环境可以帮助科 学家和工程师们进行基于网格环境的数据建模，模拟和分析的科学实验。同时也 可以帮助管理人员从分布式大型数据中发现有用的知识以支持企业决策。基于这 些目标，数据网格将发展成知识网格，提供许多高层的工具和技术来实现对网格 上的分布式的数据资源进行分布式提取和挖掘【5 】。我们项目的主要的目标就是开 发出这么一个基础结构，以帮助用户实现分布式的知识发现。 网格上的服务采用的是各种各样的服务标准，如w 曲服务【6 】，网格服务等， 所以为了使用这些服务，用户在编写自己的程序时必须按照各种服务标准来调用 所需服务，但是在大部分情况下，很多需要使用该环境的领域专家对编程并不是 很熟悉，所以为了方便用户使用网格环境，我们提供了一个工作流管理系统，使 用者只需要经过简单的培训，就可以利用该系统进行实验过程的创建，运行和保 存，这样的话，研究人员就被从繁重的编程劳动中解放出来，他们可以把有限的 精力和时间放到解决问题的业务流程中，而不必关注具体的编程细节。 随着时间的推移，各行各业就会积累越来越多的工作流，这些工作流中有很 多可以被当作典型范例进行学习和模仿，并且创建一个工作流是一个很复杂，很 耗时的一个过程，如果能够对这些工作流进行发现和复用的话，可以大大缩短工 作流的创建时间，提高工作流的创建质量。 1 2 国内外研究现况 现阶段，对于工作流发现和复用的研究比较多，主要思路有1 ) 利用关键字 来查询，一般的搜索引擎主要采用这种方法；2 ) 利用u d d i 来实现查询，典型 的代表有m y g r i d 项目；3 ) 利用数据仓库来进行查询，典型的代表d i s c o v e r y n e t 项目。 传统的搜索引擎通常是利用关键字进行查询，但是通常情况下，用户对同一 个问题可能有多种表达形式，并且同样的关键字可能有多种意思，这样通过关键 字查询的精度就很有限了。 m y g r i d 项目提供了一个用于生物信息学研究的网格平台，在该平台中，他 们是利用扩展的u d d i 来实现工作流的发现和复用的，在该注册中心中描述了工 作流的输入，输出等信息，但是它不能较好地描述工作流的的功能，服务和内部 结构，这样的话就不能让用户方便的进行查找。 d i s c o v e r yn e t 提供了一个用来进行知识发现的一个网格平台，对于工作流的 发现，他们是利用数据仓库来实现的，其缺点是缺乏语义，查询精度不高。 第一章绪论 1 3 研究内容 为了解决这些问题，我们利用本体对工作流进行了语义描述，这样就增加了 计算机可理解的语义信息，从而大大提高了查询的精度。 本文的主要研究内容包括： 首先针对数据挖掘工作流的特点，对工作流进行了四个层次的描述：1 ) 自 然语言描述，让用户可以通过关键字来进行查找；2 ) 将工作流当作一个原子服 务来描述，让用户可以通过工作流的整体属性来进行查找；3 ) 将工作流当作一 个组合服务来描述，让用户可以通过工作流中含有的服务来进行查找：4 ) 对工 作流的结构进行描述，让用户可以通过结构来查找工作流。 然后根据这四个层次的描述建立了知识发现领域的本体，并利用该本体来组 织数据挖掘工作流的实例资源。在本体的建立过程中，首先由描述模型的每一层 抽象出类，并建立它们之间的相互关系，然后创建公理来对类和类之间的关系进 行限制，最后利用本体来对工作流的实例进行组织。 然后，建立了推理规则，并实现了基于s p a r q l 语言的语义检索。在我们 的系统中，实现了三种类型的推理：1 ) 层次关系的推理，让用户可以通过高层 次的概念来进行查询；2 ) 新关系的推理，可以使用户方便的表达查询需求；3 ) 结构的推理，让用户可以通过大致的工作流结构来进行查询。通过这些推理规则 的引入，我们的系统就可以更好的支持用户的复杂查询，提高了搜索的查全率和 查准率。 最后，实现了数据挖掘工作流发现的原型系统，该系统具有三层体系结构， 分别是：存储层，管理层和g u i 层。在存储层中存放的是本体知识库，管理层 提供一组a p i 来访问本体中的元素，g u i 层给用户提供图形化的用户界面，以 方便用户输入查询条件，并且在该层还提供了一些规范化的术语，以规范用户的 输入来获得更准确的查询结果。 1 4 论文的结构 本文共分七章： 第一章绪论。本章叙述了数据挖掘工作流的发现和复用这个课题的研究背 景，研究内容和本文的章节安排。 第二章相关技术综述。概括性的介绍了数据挖掘，网格计算，工作流，和 语义网等课题相关的技术。 第三章网格数据挖掘环境。本章介绍了我们项目的网格基础环境，并介绍 第一章绪论 了工作流设计的生命周期和工作流的设计环境。 第四章数据挖掘工作流本体的设计。本章首先通过对用户需求和工作流描 述模型应具有的特性进行分析，提出一个工作流的四层描述模型，然后根据该描 述模型建立了数据挖掘工作流的本体，并利用o w l 语言实现了该本体。 第五章基于本体的查询和推理。在查询部分，首先提出了语义检索的体系 结构，然后再详细介绍一下实例工作流的组织结构，最后提出了利用s p a r q l 语言实现本体的查询。在推理部分，首先介绍了基于描述逻辑的推理机制，然后 介绍了o w l 语言与描述逻辑的关系，然后利用描述逻辑对数据挖掘工作流进行 了描述，最后建立了推理规则并实现了基于规则的推理查询。 第六章原型系统的实现。在本章中，首先介绍了工作流发现系统的整体架 构，然后介绍了我们系统的功能。 第七章总结与展望。总结了数据挖掘工作流发现系统的优点和不足，并展 望下一步工作的重点和方向。 第二章相关技术综述 2 1 数据挖掘 第二章相关技术综述 数据挖掘( d a t am i n i n g ) 是从大量数据中提取或“挖掘”知识的过程。数据挖 掘在某些场合也叫做数据库中知识挖掘、知识提取、数据模式分析、数据考古 以及数据捕捞等【_ 7 1 。随着信息技术的高速发展，人们积累的数据量急剧增长，动 辄以t b 计，如何从海量的数据中提取有用的知识成为当务之急。数据挖掘就是 为顺应这种需要应运而生发展起来的数据处理技术。是知识发现( 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 ) 的关键步骤【8 】。在我们的项目中，我们将数据挖掘服务部 署于网格节点中，用户在使用时就可以调用这些服务来进行数据挖掘了，下面简 要介绍一下数据挖掘的任务，过程和常用方法。 2 1 1 数据挖掘的任务 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差 分析等【7 1 。 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 9 1 关联规则挖掘是由r a k e s ha p w a l 等人首先提出的。两个或两个以上变量的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是 找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的 相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( 2 ) 聚类分析( c l u s t e r i n g ) 1 0 】 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 【u j 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 第二章相关技术综述 ( 4 ) 预测( p r e d i c a t i o n ) 。2 】 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 5 ) 时序模式( t i m e - s e r i e sp a t t e r n ) ”“ 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一 样，它也足用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不 同。 ( 6 ) ( d e v i a t i o n ) 1 1 4 1 在偏差叶1 包括报多有片j 构知识，数据库中的数据存在很多异常情况，发现数 据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结 果与参照之间的差别。 2 1 2 数据挖掘的过程 数据挖掘是一个复杂处理过程，其中涉及多个处理步骤。其中包括数据选择 数据清理，数据集成，数据变换，数据挖掘，模式评估，知识表示七个处理步骤川，其l l 数据清理和数据集成被统称为数据预处理。如图2 - 1 所示： 1 ) 数据选择 2 ) 数据清理 3 ) 数据集成 4 ) 数据变换 作。 5 ) 数据挖掘 网2 1 知识发现过程 从数据库中检索与分析任务相关的数据 消除噪声和不致数据 将多种数据源组台在一起 将数据变换成统的适合挖掘的形式，如通过汇总或聚集操 基本步骤，利用智能方法提取数据模式 第二章相关技术综述 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识 2 1 3 数据挖掘的方法 数据挖掘从一个新的角度把数据库技术、人工智能、统计学等领域结合起来， 从更深层次发掘存在于数据内部新颖、有效、具有潜在效用的乃至最终可理解的 模式，数据挖掘有以下几种常用方法【7 】： 1 、神经网络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关 注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型 网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网 络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。 神经网络方法的缺点是“黑箱”性，人们难以理解网络的学习和决策过程。 2 、遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生 全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 在数据挖掘中被加以应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两 个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖 掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。 如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接 和隐层单元；用遗传算法和b p 算法结合训练神经网络，然后从网络提取规则等。 但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。 3 、决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中 找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别 适合大规模的数据处理。最有影响和最早的决策树方法是由q u e a n 提出的著名 的基于信息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决 策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪 性差。针对上述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计 了i d 4 递增式学习算法；钟鸣，陈文伟等提出了i b l e 算法等。 4 、粗集方法 第二章相关技术综述 粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点： 不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处 理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展 起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学 基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在 的。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际上已经研制 出来了一些基于粗集的工具应用软件，如加拿大r e g i n a 大学开发的k d d r ；美国 k a n s a s 大学开发的l e r s 等。 5 、覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合 中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去， 相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。 比较典型的算法有m i c h a l s k i 的a q l1 方法、洪家荣改进的a q l 5 方法以及他的 a e 5 方法。 6 、统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性 关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析 可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用 统计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分析( 用回归方程 来表示变量间的数量关系) 、相关分析( 用相关系数来度量变量间的相关程度) 、差 异分析( 从样本统计量的值得出差异来确定总体参数之间是否存在差异) 等。 7 、模糊集方法， 即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和 模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度 来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础 上，提出了定性定量不确定性转换模型一云模型，并形成了云理论。 2 2 网格计算 网格技术是一种新型计算模式。其目的就是要利用互联网把分散在不同地理 位置的电脑组织成一台“虚拟的超级计算机”，实现计算资源、存储资源、数据 资源、信息资源、软件资源、通信资源、知识资源、专家资源等的全面共享。网 格技术凭借其独特的计算力联合和分布式计算模式，在学科研究、企业信息处理、 电子政务、个人娱乐方面拥有广泛的应用前景。 第二章相关技术综述 网格这一术语于上个世纪9 0 年代中期被提出，被用于表述一种适用于高端 科学和工程的分布式计算体系结构。网格的概念和相关技术最初就是针对科研协 作中的资源共享问题，即网格可以看作是各类资源的整合环境，能够充分吸纳各 种资源，包括计算资源( 各种计算机、工作站等) 、存储资源、应用程序、甚至可 以是科学仪器，并以一种随处可得的、可靠的、标准的、经济的方式提供给用户， 满足网格中多个机构组成的动态虚拟组织间实现协作式资源共享和问题求解的 需要。这里，虚拟组织概念是许多现代计算理论的基础，是一种基于资源共享的 协作式问题求解模式的抽象，可以看作是“基于一些共同的共享规则，由一些个 人或团体形成的集合体，其中的成员以高度可控的方式共享不同的资源，即资源 提供者和使用者必须对哪些资源可以被共享、谁可以共享、共享的条件有清晰的 约定，同时虚拟组织内部不存在资源节点管理和自主性的冲突，允许成员自由地 退出和加入等。网格提供了虚拟组织需要的一个普遍的资源共享框架，这是它与 现今其他分布式系统的主要区别。 到目前为止，网格的发展大致经历了三个阶段，网格架构有三种模型【l6 1 ，即 五层沙漏模型，o g s a 1 5 和w s r f t l 6 】。五层沙漏模型将网格分层设计，各层依次 为构造层、连接层、资源层、汇聚层和应用层。各层中协议数量不同，资源层和 连接层成为网格平台的瓶颈，拥有核心、但是数量最少的协议，实现对上、下层 协议的映射。 2 0 0 2 年g l o b u s 项目组和i b m 公司共同提出o g s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) 模型，该模型将一切资源抽象为服务，包括各种计算资源、存储资 源、网络平台、程序、数据库等。通过服务的概念，将网络中部署的一切资源以 统一的标准接口管理，利用虚拟组织执行接口管理功能【1 7 】。 随后，2 0 0 4 年g l o b u s 和i b m 、h p 又共同提出w s r f ( w e bs e r v i c er e s o u r c e f r a m e w o r k ) 模型，该模型提出将资源与服务区别对待，即资源是有状态的，而 服务是无状态的。于是，原有的网格服务演变为w 曲服务和资源文档。这样做的 目的是定义一个通用且开放的架构，利用w 曲服务对具有状态属性的资源进行存 取，并包含描述状态属性的机制和将机制延伸至w 曲服务中的方式【l 8 1 。 2 0 0 5 年，g l o b u s 联盟发布了g t 4 1 9 】，实现了w s r f 标准。g t 4 提供a p i 来构 建有状态的w e bs e r v i c e s ，其目标是建立分布式异构计算环境。 在我们的项目中，我们利用g l o b u s 的g t 4 创建基础网格环境，并将数据挖 掘服务以w e b 服务的形式部署于网格环境中，这样就可以向用户提供强大的基 于网格的计算能力。 第二章相关技术综述 2 3 工作流技术 2 3 1 工作流技术介绍 以i n t e r a c t 为代表的信息技术的快速发展和成熟应用改变着企业的商业环境， 使商业运行节奏越来越快，企业的价值链更加紧密和多样，这种改变引导软件技 术和软件产品的发展方向：异构性、分布性和协作能力。企业或企业内部之间由 于业务上的联系，会形成各式各样的相对稳定的企业关系，根据这些关系设计灵 活的工作流程，可以使企业生产组织水平和运行效率大大提高。工作流是在企业 级计算中为业务过程建模和实现业务过程重组的软件技术，起源于生产制造业与 办公自动化领域。根据工作流管理联n 0 ( w f m c ) 对工作流的定义，它是指一类能 够完全或者部分自动执行的业务过程，它根据一系列过程规则，使得文档、信息 或者任务能够在不同的执行者之间传递与执行 2 0 , 2 1 】。工作流管理系统是企业对其 业务过程进行敏捷管理的新型信息系统，工作流管理系统维护的是以工作流过程 定义形式表示的企业的业务过程。工作流管理系统的应用，可以加速企业内部商 务和管理流程处理的速度，提高处理的效率，实现处理的自动化或部分自动化。 工作流技术的发展经过十几年的努力，取得一定的结果。但在实际应用中的 效果并不理想，这里与产品的全面性、集成性有关，也与企业应用的状况有关， 具体有以下几点： 1 、工作流底层环境的建立 工作流管理系统必须建立在底层通信的基础上，才能实现分布计算，这要额 外付出经费和精力进行构筑，这是企业所不希望的，从而限制了在企业中的广泛 应用。 2 、标准化程度差 不同的厂商所提供的工作流产品具有自己独立的一套工作流模型、工作流定 义语言、a i p 函数。但难于在不同系统之间进行交互，集成的效果不理想，不能 方便地在不同系统间进行应用对象的重复利用和数据的方便交流。 3 、系统的集成性不理想 工作流管理系统没有达到真正地集成，还是在自己独立地运行，处理一些行 政上的简单的流程业务，不能很好将o a 、e p r 、c r m 、s c m 等具体事务处理系 统紧密地联系在一起，达到数据录入一次即可有效的目的。 4 、实现的复杂性 实施一个完整的工作流管理系统，是一个复杂的过程，要了解其它应用系统 的业务、进行流程处理分析、业务流程的改造、管理规程和操作规范建立等。并 第二章相关技术综述 且还必须有不同软件供应商的全力配合。 5 、系统的安全性 系统中对于并发访问和异常错误缺乏正确和可靠的支持。一旦系统出现非正 常退出，如何恢复数据并保证数据的一致性还需要解决。 2 3 2 工作流管理系统 分布式计算技术的发展大体经历了八十年代的分布式操作系统、经典的客户 机服务器计算模式、九十年代的分布式对象计算模式等几个发展阶段，未来的企 业应用系统将主要是建立在面向对象的、分布的、异构的、自治的环境中的多层 应用系统，系统主要由一个个分布式对象组成，对象各自具有特定的功能，可以 跨越平台，独立于网络协议、编程语言和软硬件平台，实现相互通信，协同工作。 传统分布式计算模型c o r b a 、d c o m 、j a v a r m i 等，依赖底层操作系统和 特定实现语言，大多使用专有协议通过特别的端口进行远程通信，无法在广域网 环境下相互发送消息，实现请求服务，使工作流模型没有较好的互操作性和可复 用性。w e bs e r v i c e 作为一种新的面向函数和方法的应用集成技术，在很大程度 上解决了原有集成技术在i n t e r a c t 远程通信方面的问题。w e bs e r v i c e 基于x m l 文档进行服务描述，服务请求和反馈结果，可以在i n t e r a c t 上通过h t t p 协议进 行传递，很容易的被访问和返回结果。同时，由于w e bs e r v i c e 的相关标准都是 w 3 c 的开放协议，与平台和操作系统无关，不同的平台和操作系统上的w e b s e r v i c e 的实现在很大程度上可以做到互操作，这就使异构平台上应用的集成变得 很容易。 基于g l o b u st o o l k i t4 。0 实现的工作流管理系统 2 2 】对包装成w e bs e r v i c e 的知识 发现服务进行调用和控制，由于w e bs e r v i c e 的标准性、简单性以及松耦合性，可 以比较好地解决传统工作流系统中底层通信环境不一致、标准化程度差以及实现 的复杂性等诸多问题，有利于实现数据共享和信息交换，使得业务流中的不同业 务活动的交互更加简单和方便，方便扩展企业业务系统的功能，可以极大地提高 企业资源信息系统的处理效率。 在我们的项目中，我们采用t a v e m a 系统作为我们的工作流管理系统。利用 它我们就可以方便的实现对知识发现服务的管理，并且利用该系统可以方便的实 现工作流的创建，运行和运行过程监控。 2 4 语义网和本体 语义网最早是由b e m e r s l e e ：于二1 9 9 8 年提出来的，他认为语义w 曲是现 第二章相关技术综述 有万维网的扩展或者是下一代的万维网，其目标是跨越现有万维网在信息处理上 低自动化、低智能化与“信息爆炸”之间的鸿沟，充分利用计算机的强大能力， 使得计算机在“理解”w e b 中信息的“含义”的基础上与人更好地合作，为人们 在网络中的信息获取、访问和交换方面提供更优质更高效的支持。这里，信息的 “含义”即语义( s e m a n t i c ) - - 词所表达的不是自然语言或人的推理，而是表达了 对信息能进行哪些操作。由于机器并不具各智能，语义w e b 的基本思想是在w e b 信息中加入机器可处理的表达语义的元数据，进一步能依据元数据层次上的关 系、规则、逻辑和条件进行推理，从而自动地对信息进行组织、分类和处理。在 此之后，t i mb e m e r sl e e 又提出了语义w e b 体系结构，如图2 2 1 2 3 1 所示，为语义 w e b 技术的研究制定了路线圈。 图2 - 2 语义w e b 体系结构 x v l l ( e x t e n s i b l em a r k e tl a n g u a g e ，可扩展标记语言) 的出现使得已有的不同 类型的数据互操作成为了可能，能消除w e b 上信息在语法描述上的差异。由于 它实现了数据内容和形式的分离，这就迈出了重要的一步，使得传统万维网上的 信息从面向人浏览的同时转为面向计算机自动处理成为可能，因此它构成了语义 w e b 的语洼基础。但x m l 所存在的问题是不具各语义描述能力，为此 r d f ( r e s o u r c ed e s c n p t i o nf r a m e w o r k ，资源描述框架) 被应用来解决x m l 的语义 局限，它借鉴了传统的“属性一值”对蛆及实体关系周，用二元组来表达二元关 系，提供了机器可处理的语义的元数据框架。r d fs c h e m a ( 简记为r d f s ) ；l 八了 一个类似于面向对象的语言中的可扩展的类型( t y p e ) 系统到r d f 中，提供方法定 义合适的定义域和值域，以及类和子类层次使得一些简单的推理能得以实现。 要使计算机之间能够相互理解其处理内容，还要一套共同的标准的形式化的 概念体系，即率体( o n t o l o g y ) ，典型的w e b 本体通常包含一个分类法和一组推理 规则。o w l 是最新推荐的w e b 本体描述语言，是在d a m l 十o i l 的基础上发 第二章相关技术综述 展起来的，作为r d f s 的扩展，它提供了更多基于描述逻辑( d e s c r i p t i o nl o g i c ， d l ) 的原语以支持更加丰富的语义表达和更强的推理能力。逻辑层则是在本体层 定义的术语关系和推理规则之上提供功能更强大的逻辑语言来实现推理，当逻辑 层在本体描述语言之上提供图灵完全的逻辑语言后，语义w e b 就有足够的能力 给出关于事物与事物间关系的断言。证明层的证明语言能对断言的真假给出逻辑 证明。最后数字签名和加密技术用来确保w e b 上信息的可信任性。目前研究较 成熟的最高一层是本体层。 在我们的项目中，我们利用本体来对数据挖掘工作流进行描述，并利用创建 出来的本体来组织数据挖掘工作流实例。这样的话，就很方便的实现工作流的语 义查找。 第三章基于网格的数据挖掘环境 第三章基于网格的数据挖掘环境 基于网格的数据挖掘系统，该项目是天津市重点项目，目的是建立一个基于 网格的数据挖掘系统，让用户能够方便的利用强大的网格计算资源和数据挖掘服 务来进行分布式的知识发现。在该项目中，我们利用g l o b u s 中间件建立网格环 境，然后将数据挖掘服务部署于这个网格环境中，并采用t a v e m a 系统作为数据 挖掘工作流的创建和运行工具，工作流的描述语言采用的是t a v e m a 系统的s c u r f l 语言。下面分别介绍一下网格基础环境，工作流设计的生命周期和工作流设计环 境。 3 1 网格基础环境 3 1 1g l o b u s 项目介绍 g l o b u s 项目【2 4 】是目前国际上最有影响的网格计算项目之一。它发起于九十年 代中期，其前身是卜- w a y 试验环境项目。它的最初目的是希望把美国境内的各 个高性能计算中心通过高性能网络连接起来，方便美国的大学和研究机构使用， 提高高性能计算机的使用效率。随着对g l o b u s 项目的深入研究，针对它的目标也 进一步扩展，希望通过c l o b u s 项目可方便对地理上分布的研究人员建立虚拟组 织，进行跨学科的虚拟合作。目前，g l o b u s 项目把商业计算领域中w e bs e r v i c e 技术融合在一起，希望不仅仅局限于科学计算领域，而且能够对各种商业应用进 行广泛的、基础性的网格环境支持，实现更方便的信息共享和互操作，从而对商 业模式、工作方式和生活方式产生深远的影响。 g l o b u s 项目对信息安全、资源管理、信息服务、数据管理以及应用开发环 境等网格计算的关键理论和技术进行了广泛的研究，开发出基于w e b 服务的工 具包g l o b u st o o l k i t ( g t ) ，用来帮助规划和组建大型的网格试验和应用平台，支 持面向服务的应用程序和分布计算基础设施。g l o b u st o o l k i t 是g l o b u s 项目最重 要的实践成果，其第二版于1 9 9 9 年推出，其后主要有2 0 0 3 年上半年推出的基于 o g s a 体系结构并融合了w e bs e r v i c e 技术的g l o b u st o o l k i t3 0 版和2 0 0 4 年推出 的遵循w s r f 规范的g l o b u st o o l k i t4 0 最新版。 分布式系统面临着诸多的挑战不可预测的网络传输延时，系统组件故障 的威胁，并发操作的控制，以及不同的管理领域间政策协商问题。w e b 服务技术 第三章基于网格的数据挖掘环境 的提出为分布系统中运行在不同平台、框架下应用软件间的互操作提