（计算机应用技术专业论文）基于移动代理的分布式数据挖掘研究.pdf

浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 基于移动代理的分布式数据挖掘研究 摘要 随着信息时代的到来和计算机网络技术的飞速发展，在分布式环 境下，如何进行有效的数据挖掘成为信息科学研究领域一个新的课 题。分布式数据挖掘是使用分布式计算技术，从分布式数据库中发现 知识的过程。 移动代理技术是分布式技术与a g e n t 技术相结合的产物。移动代 理是指代表用户完成任务的一段程序，可以在分布式网络环境中自主 地从一台主机迁移到另一台主机。它具有移动性、自治性和异步计算 等特性，可以有效地利用带宽，减少网络流量，改善响应时间。 本文首先分析了移动代理技术在分布式计算方面的优越性，同时 对分布式数据挖掘的体系结构和代价模型进行了深入的分析，在此基 础上提出了一个基于移动代理的分布式数据挖掘模型，并给出了它的 代价模型。相应地我们设计并实现了一个基于移动代理的分布数据挖 掘原型系统( d d 佃b m a ) 。该系统只传送执行挖掘功能的移动代理本 身的代码及局部知识，所以大大减少了网络的数据传输量，且加强了 数据的安全性及隐私性。 在该原型系统的基础上提出并实现一种基于移动代理的分布式关 联规则挖掘算法d a m b m a ，该算法只需在分布式站点与服务器间往返 两次就可完成挖掘任务，具有较高的效率和较低的通信量。实验证明 * 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 该算法的有效性。 最后总结全文，并展望了将来要进行的研究工作。 关键宇：数据挖掘，分布式，移动代理，关联规则 浙江工业大学硕士研究生学位论文 基于移动代理的分布式数据挖掘研究 t h er e s e a r c ho fd i s t r i b u t e dd a t am 叩啪n g b a s e do nm o b 。ea g e n t a b s t r a c t w i t ht h ec o m i n go fi n f o r m a t i o ne r aa n dr a p i d d e v e l o p m e n t o f c o m p u t e rn e t w o r kt e c h n o l o g y , h o wt om i n ee f f i c i e n tk n o w l e d g ef r o m d a t au n d e rd i s t r i b u t e de n v i r o n m e n tb e c o m e san e wt o p i ci ni n f o r m a t i o n s c i e n c er e s e a r c ha r e a s d i s t r i b u t e dd a t am i n i n g ( d d m ) i sap r o c e s s d i s c o v e r i n gk n o w l e d g ef r o md i s t r i b u t e d d a t a b a s e s u s i n g d i s t r i b u t e d c o m p u t a t i o n m o b i l ea g e n ti st h ec o m b i n a t i o no ft h ea g e n tt e c h n i q u ea n dt h e d i s t r i b u t e dc o m p u t i n g ，w h i c hi sap i e c eo fp r o g r a mt h a tc a nf i n i s hs o m e t a s k so nb e h a l fo ft h e i ru s e ra n dm i g r a t ef r o mah o s tt oa n o t h e ri nt h e d i s t r i b u t e dn e t w o r k se n v i r o n m e n t i th a s t h ep r o p e r t i e so fm i g r a t o r y , a u t o n o m o u sa n da s y n c h r o n o u sc o m p u t i n g ，e t c ，m o b i l ea g e n tt e c h n i q u e c a nr e d u c en e t w o r kt r a f f i ca n dr e s p o n s et i m e f i r s t l y ，t h ep a p e ra n a l y z e st h ea d v a n t a g eo fm o b i l ea g e n tt e c h n i q u e ， w h i c hi sa p p l i e dt od i s t r i b u t e dc o m p u t a t i o n ，a n dp e r f o r m sad e e pa n a l y s i s o ft h e a r c h i t e c t u r ea n dc o s tm o d e l so fd d m s t h ed i s t r i b u t e dd a t a 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 m i n i n gs y s t e mm o d e lb a s e do nm o b i l ea g e n ta n di t s c o s tm o d e li s p r o p o s e d a c c o r d i n g l y , w ed e s i g na n di m p l e m e n ta d i s t r i b u t e dd a t a m i n i n gs y s t e mb a s e do nm o b i l ea g e n t t h es y s t e mo n l yt r a n s f e r st h ec o d e o ft h em o b i l ea g e n tw h i c he x e c u t e st h et a s ko fd a t am i n i n ga n dl o c a l k n o w l e d g e ，s oi td e c r e a s e st h et r a n s f e r r e dd a t ag r e a t l ya n ds t r e n g t h st h e s e c u r i t ya n dp r i v a c yo fd a t a w ep r o p o s e da n di m p l e m e n tad i s t r i b u t e d a l g o r i t h mi i l i i l i n g a s s o c i a t i o nr u l e sb a s e do nm o b i l ea g e n tu n d e rt h i sp r o t o t y p es y s t e m t h e a l g o r i t h mc a na c c o m p l i s hm i n i n gt a s kb yt r a v e l i n gt w i c eb e t w e e nt h e s e r v e ra n dd i s t r i b u t e dl o c a t i o n ，s oi th a sh i g h e re f f i c i e n c yo fm i n i n ga n d l o w e ra m o u n to fc o m m u n i c a t i o n ，a l g o r i t h md a m b m ai sp r o v e dt ob e e f f e c t i v eb ye x p e r i m e n t s a tl a s t ，as u m m a r yo ft h ep a p e ri sg i v e na n df u r t h e rr e s e a r c hi n t e r e s t s 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 ，m o b i l ea g e n la s s o c i a t i o nr u l e s 浙江工业大学硕士研究生学位论文 躺一游布烈篡黧 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名：名 幢 隰眵年，月穆日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：年5 月移日日期：吖年月哆日 日期：口r 年f 月玎日 饭撵 孝路 浙江工业大学硕士研究生学位论文 基于移动代理的分布式数据挖掘研究 1 1 概述 第一章绪论 数据挖掘( d m ，d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊 的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用 的信息和知识的过程。分布式数据挖掘是从多个在物理位置上分布的数据库中进 行数据挖掘的过程。分布式数据挖掘已经成为一个备受关注的热点问题。 目前的数据挖掘算法和模型主要采用集中式，大多要求所有被挖掘的数据存 放在一个单一的、集中的数据仓库中。而一个企业的数据资源往往存在于地理位 置分布的数据库中，要使用现在有限的网络带宽把这些大量的数据( 甚至达到g b ) 重新收集到一个集中的地方，必然导致响应时间变长，造成了大量网络带宽资源 的浪费；而挖掘算法通常需要大量的计算资源，这必然要求执行挖掘算法的机器 有相当高的性能，与之相应的在其它分布式站点上的机器有着充裕的计算资源却 不能有效地利用，造成了计算资源的浪费；数据在网络上传输的过程当中，有可 能被篡改，数据的安全性受到威胁：将数据集中到一个地方，分布式站点上数据 的私有性被破坏：此外，大部分集中式数据挖掘算法又大多是集中式算法，不适 合于大容量、分布式的数据挖掘应用。 移动代理技术是智能代理技术与分布式技术结合的产物，它能代表用户在本 地或远程主机执行用户指派的任务，它具有反应能力、自主性、目标驱动、连续 性等特点。移动代理可以通过网络从一台机器移动到另一台机器，在目标机器上 执行一系列的操作后，返回主机或者转到另外一台目标机器上继续执行，由于只 需迁移代理本身的少量代码，大大减少了网络的数据传输量；移动代理无需持续 的网络连接，在网络连接不可靠的情况下，移动代理在完成本身的迁移后便可在 目的地执行任务，网络的连接状况并不会直接影响到移动代理任务的执行。移动 代理的这些特点能很好地解决分布式数据挖掘中数据的异构性及数据集中带来 的大量的网络数据传送等问题。 本文深入地分析了分布式数据系统结构及代价模型，在此基础上，提出了一 种基于移动代理的分布式数据挖掘系统模型，并给出了它的代价模型。在这个原 型系统的基础上，对分布式关联规则算法进行了分析，提出了一种基于移动代理 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 的分布式规则发现算法，该算法只需在分布式站点与服务器间往返两次就可完成 挖掘任务，具有较高的效率和较低的通信量。并将该算法应用于电信系统市场营 销策略分析。 1 2 论文的研究内容 数据存储方式的日益分布化给传统的集中式数据挖掘带来了挑战，分布式数 据挖掘势在必行。数据的分布化及异构性是分布式数据挖掘的难点。集中式分布 挖掘算法已不适应分布式数据挖掘的需要，如何设计新的或改进原有的一些集中 式挖掘算法以适用于分布式数据挖掘也是一个迫切需要解决的问题。本文正是围 绕这两方面展开一些研究工作。本文的具体工作主要有以下几个方面： ( 1 ) 研究了一些典型的分布式数据挖掘系统结构，为更好地评价分布式系统结 构的效率，对它们的代价模型进行了描述。将移动代理技术引入到分布式数据挖 掘中，提出了一种基于移动代理的分布式数据挖掘模型。 ( 2 ) 设计并实现了一个基于移动代理的分布式数据挖掘系统原型。移动代理的 自适应性和移动性，使系统具有良好的可扩展性和可维护性，并具有平台无关性。 ( 3 ) 在研究现有的一些分布式关联规则挖掘算法的基础上，提出了一种基于移 动代理的分布关联规则发现算法，该算法只需在服务器及分布式站点间往返两 次，且只需传送少量的移动代理代码本身及局部知识，具有较高的效率和较少的 通信量。 1 3 论文的组织 本论文系统地阐述了数据挖掘的理论基础及移动代理技术，分析了移动代理 技术在分布式应用的优越性。对分布式数据挖掘系统结构及代价模型进行探讨， 提出一种基于移动代理的分布式数据挖掘系统( d d m b m a ) 原型，并对它的代价 模型进行了描述，对分布式关联规则算法进行了一些探讨，提出了一种基于移动 代理的分布式规则发现算法，应用于电信系统市场营销策略分析。本论文各章节 的安排如下： 第一章：绪论 提出了本文的研究内容，并阐述了本文的组织。 浙江工业太学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 第二章：理论基础与相关技术 系统地阐述了数据挖掘的基本原理，分析了分布式数据挖掘的必要性与难点 问题，对移动代理技术进行了深入的探讨，论述了移动代理技术在分布式应用的 优越性。 第三章：分布式数据挖掘体系结构及代价模型研究 介绍了在构建一个分布式数据系统时的策略上的不同，为更好地评价分布式 数据挖掘系统的性能，分析了c l i e n t s e r v e r 结构模型的代价模型，提出了一种基 于移动代理的分布式数据挖掘系统模型，给出了代价模型。 第四章基于移动代理的分布式数据挖掘系统原型设计 在上一章提出的移动代理分布式数据系统模型的基础上，设计并实现了一个 基于移动代理的分布式数据挖掘系统原型，介绍了系统的一些核心组件的功能。 第五章分布式关联规则算法研究 研究了现有的一些分布式关联规则挖掘算法的特点和不足，提出了一种基于 移动代理的关联规则发现算法。实验证明了算法的完备性和有效性。并将算法 d a m b m a 应用于电信的市场营销策略分析。 第六章总结与展望 总结全文，提出进一步的具体工作。 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 第二章理论基础与相关技术 2 1 数据挖掘原理 2 1 1 数据挖掘基本概念 对于数据挖掘( d m ，d a t am i n i n g ) ，一种比较公认的定义是w j f r a w l e y ，g p i a t e t s k y ，s h a p i r o 等人提出的：数据挖掘就是从大型数据库的数据中提取人们 感兴趣的知识。这些知识是隐含的、事先未知的潜在有用信息，提取的知识表示 为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形 式“1 。这种定义把数据挖掘的对象定义为数据库。而更广义的说法是：数据挖掘 意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。它是一个利用 各种工具在海量数据中发现模型和数据问关系的过程。 人们把原始数据看作是形成知识的源泉。原始数据可以是结构化的，如关系 数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布 在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的：可 以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决 策支持、过程控制等。还可以用于数据自身的维护。因此，数据挖掘是一个跨学 科交叉领域。涉及数据库技术、人工智能、机器学习、神经网络、统计学、模式 识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化等0 1 。 数据挖掘是面向应用的一种技术。数据挖掘中发现的知识都是相对的，是由 特定前提和约束条件、面向特定领域的，同时要能易于被用户理解，最好能用自 然语言表达发现结果。“。 2 1 2 数据挖掘的过程 数据挖掘的过程可以粗略分为：问题定义、数据收集和预处理、数据挖掘算法 执行、以及结果的解释和评估，如图2 1 所示。 4 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 图2 1 数据挖掘过程 ( 1 ) 问题定义( t a s kd e f i n i t i o n ) 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种 知识就成为整个过程中第一个也是最重要的一个阶段。在阿题定义过程中，数据 挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖 掘的要求，另一方面通过对各种学习算法的对比而确定可用的学习算法。后续的 学习算法选择和数据集准备都是在此基础上进行的。 ( 2 ) 数据收集和预处理( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ，是 根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般包括消除噪 声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数据挖掘的对 象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成。数据变换 的主要目的是消减数据维数或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找 出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。 ( 3 ) 数据挖掘( d a t am i n i n g ) 算法执行 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如分 类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用 什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点， 因此需要用与之相关的算法来挖掘：二是用户或实际运行系统的要求，有的用户 希望获取描述型的( d e s c r i p t i v e ) 容易理解的知识，而有的用户只是获取预测准 确度尽可能高的预测型( p r e d i c t i v e ) 的知识。 ( 4 ) 结果解释和评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 数据挖掘阶段发现出来的模式，经过评估。可能存在冗余或无关的模式，这 时需要将其剔除。也有可能模式不满足用户要求，这时则需要整个发现过程回退 到前一阶段。重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换 一种算法。另外，数据挖掘是面向最终用户的，因此需要对发现的模式进行可视 化，或者需要将结果转换为用户易懂的表示。 数据挖掘算法执行，仅仅是整个过程的一个步骤。数据挖掘质量的好坏有两 个影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质量 和数量。整个挖掘过程是一个不断反馈的过程。 2 1 3 数据挖掘的数据来源 数据挖掘所依赖的数据来源多种多样，可以是关系数据库、事务数据库、文 本数据库、多媒体数据库等，主要取决于用户的目的及所处的领域。目前，数据 挖掘的数据主要取自关系数据库与数据仓库。 ( 1 ) 关系数据库 关系数据库是表的集合。通常为关系数据库构造e r 模型。关系数据可以通 过数据库查询访问。数据库查询使用s o l 这样的关系查询语言。关系数据库是数 据挖掘最流行的、最丰富的数据源，因此它是数据挖掘研究的主要数据形式。 ( 2 ) 数据仓库 数据仓库( d a t aw a r e h o u s e ) 己经成为现代数据挖掘的有效平台，并努力实现 紧密藕合。按照“数据仓库之父”w i l lj a mh i n m o n 的描述，数据仓库是一个面 向主题的( s u b j e c t o r i e n t e d ) 、集成的( i n t e g r a t e d ) 、时变的( t i m e v a r i a n t ) 、 非易失的( n o n v o l a t i l e ) 数据集合，支持管理部门的决策过程“1 。 6 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 数据仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通 常驻留在单个站点。数据仓库通过数据清洗、数据变换、数据集成、数据装载和 定期数据刷新来构造，通常，数据仓库用多维数据库结构建模眦。 此外，数据挖掘也要求在数据集市( d a t am a r t ) 上进行。数据集市是数据仓库 的一个部分子集，它聚焦在选定的主题上，是部门范围的。数据集市可以是数据 仓库的一个逻辑子集或是一个物理子集。 ( 3 ) 高级数据库及高级数据库的应用 随着数据库技术的发展，各种高级数据库系统已经出现在开发中，以适应新 的数据库应用需要。即由原来的单一关系数据库发展到事务数据库、面向对象数 据库、文本数据库、空间数据库、多媒体数据库等新的数据库系统。同样，数据 挖掘的数据来源也可以取自这些类型的数据库系统。 2 1 4 数据挖掘所采用的技术方法 ( 1 ) 概念类描述：特征化和区分 概念描述以简洁汇总的形式描述给定的任务相关数据集，提供数据价值的一 般特性，一般应用于描述式数据挖掘。概念或类描述由特征化和比较或区分组成， 有两种一般方法：基于数据立方体o l a p 的方法”3 和面向属性归纳的方法“”。 ( 2 ) 关联分析 关联分析发现关联规则，这些规则展示属性一值频繁地在给定数据集中一起 出现的条件。关联分析广泛用于购物篮、商务管理和决策分析，是商业分析中应 用最为广泛的一种数据挖掘方法和模式“1 。有效的算法包括a p r i o r i 算法和频 繁模式增长( f p 一增长) 算法“。并注重多层关联规则、多维关联规则和基于约束 的关联规则的挖掘“。 ( 3 ) 分类和预测分析 分类和预测是数据分析的两种重要形式，可以用于提取描述重要数据类的模 型或预测未来的数据趋势。主要方法包括：决策树判定树“、贝叶斯分类“。、神 经网络算法1 “、遗传算法“8 3 等。 ( 4 ) 聚类分析 属于无指导学习。对象根据最大化类内的相似性、最小化类内的相似性的原 7 浙江工业大学硕士研究生学位论文 基于移动代理的分布式数据挖掘研究 则进行聚类或分组。聚类分析有广泛的应用包括市场或客户分割、模式识别、生 物学研究、空间数据分析、w e b 文档分类及其他方面n 9 1 。它可以用作独立的数据 挖掘工具来获得对数据分布的了解，也可以作为其他数据挖掘算法的预处理步骤 。许多聚类算法己经被开发出来。 ( 5 ) 孤立点分析 对于欺诈探测。“、定制市场及医疗分析及其他任务是非常有用的。基于计算 机的孤立点挖掘方法包括统计学方法、基于距离的方法和基于偏差的方法。 ( 6 ) 演变分析 描述行为随时间变化的对象的规律或趋势并对其建模，包括时间序列数据分 析、序列或周期模式匹配和基于类似性的数据分析。演变分析可用于趋势分析、 相似性搜索、与时间有关的序列模式挖掘和周期模式挖掘。 ( 7 ) 复杂类型的数据挖掘。4 是数据挖掘技术的当前一个重要的研究领域，极大提升了数据分析能力的深 度和广度，主要包括：对象数据挖掘嘲、空间数据挖掘、多媒体数据挖掘。”、 时序和序列数据挖掘、文本挖掘啪1 和w e b 挖掘啪1 等。 2 1 5 数据挖掘的主要应用与发展趋势 数据挖掘的研究是以应用驱动的，从一诞生，就带上了强烈的应用色彩，由 于数据挖掘本身的特点，在金融、保险业、零售业、医学、制造业、运输业、科 学与工程研究等众多领域都有广阔的应用前景。在金融行业，数据挖掘可以用来 分析客户的信用状况，可以预测贷款偿还情况等，在生物医学领域，可以采用数 据挖掘对d n a 序列进行研究，在生产制造行业，数据挖掘可以应用在机器故障诊 断、库存优化、生产调度等方面。由于数据形式、数据挖掘任务及数据挖掘方法 的多样性，数据挖掘领域有很多挑战性的课题，高效有用的数据挖掘方法、数据 挖掘语言的设计、交互集成的数据挖掘环境的建立等众多的问题，是当前数据挖 掘研究开发人员都需要面对的数据挖掘领域今后的焦点和发展趋势可能表现在 以下几个方面： ( 1 ) 数据挖掘平台的标准化：数据挖掘语言的标准化将使数据挖掘项目的系统 化开发提供便利、并有助于各个数据挖掘系统和功能模块之间的互操作，便于在 8 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 企业中的培训和使用。也许将来数据挖掘语言会象s q l 一样标准化和易于使用。 ( 2 ) 数据挖掘过程中的可视化方法：这个方面的研究可以使知识发现的过程能 够被用户形象的理解，也便于在知识的发现过程中人机交互。 ( 3 ) 可伸缩的数据挖掘方法：传统的数据分析方法大部分都是基于内存的，数 据挖掘面对的是大数据量，因此如何有效的处理大数据量，并且可以是交互式的， 就成为研究的一个方向，一个好的数据挖掘算法，其复杂度应该随数据记录数、 属性数目数呈线性增长。 ( 4 ) w e b 挖掘：i n t e r n e t 目前已经成为巨大的、全球性的信息服务中心，w e b 上存在有大量的信息，有关w e b 内容的挖掘、w e b 日志的挖掘、w e b 结构的挖掘，已 经成为当前和以后数据挖掘领域最重要的热点之一。 ( 5 ) 复杂数据类型挖掘的新方法：目前，地理空间挖掘、多媒体挖掘、时序挖 掘等复杂数据类型的挖掘已经取得了一些进展，但离实际应用还有很大的距离， 因此这一领域的研究也显得很重要。 ( 6 ) 数据挖掘中的隐私保护和信息安全：随着数据挖掘的发展，如何能够确保 隐私安全与信息安全，已经成为当前需要面临的一个重要问题了，因此需要对这 个领域进行研究。 ( 7 ) 分布式数据挖掘算法及分布式数据挖掘平台：随着网络技术的发展及企 业、组织的全球化，企业或组织的数据信息可能分布在不同物理位置上，为了有 效地挖掘出这些数据中的有用的知识，对原有的一些集中式的算法进行分布式的 改进，并构建高效的分布式数据挖掘平台是一个具有挑战性的工作。 2 2 分布式数据挖掘的必要性与关键技术 企业及各种组织的全球分布造成了大量数据或信息存放于不同地理位置，网 络技术、i n t e r n e t 技术及的高速发展及计算机性能的提高使得对这些数据进行分 析、处理。从中挖掘出有价值的知识成为可能，而且已经成为这些企业或组织的 迫切需求。而原来传统的数据挖掘系统大多都是集中式，分布式数据挖掘系统也 就应运而生。 当数据挖掘在这样一种环境下迸行：用户、数据、硬件资源以及挖掘需要的 软件资源在物理上是分布的，我们称它为分布式数据挖掘( d i s t r i b u t e dd a t a 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 m i n i n g ，简称d d m ) ，这是一个使用分布式计算技术，从分布式数据库中发现知 识的过程。典型地，这种环境以异种数据、多用户、大规模数据量为特征。 2 2 1 分布式数据挖掘( d d m ) 基本原理 分布式数据挖掘是近几年才提出的新的研究领域，由于其诱人的应用前景， 目前己有相当数量的研究人员投入到对该领域的研究当中，并且取得了一定的成 果。典型的分布式数据挖掘算法的两个基本步骤是：局部数据分析，生成局部 数据模型( 局部知识) 。组合不同数据站点上的局部数据模型，得到全局数据模 型( 全局知识) 。如图2 2 所示： 图2 2 分布式数据挖掘算法全局知识的生成 2 2 2 分布式数据挖掘的必要性 现在的数据挖掘算法及模型主要采用集中式。即使在数据分布式存储的情况 下，也要求把这些数据重新收集到一个集中的地方( 如数据仓库) 。这要求有高 速的数据通讯网络，并且会导致响应时间变长和数据的私有性和安全性被破坏， 尤其当分布式数据不同构的时候更是这样。虽然网络带在增加，但还是比不上数 据增长的速度，结果导致通过有限的网络带宽来移动大容量的数据，而且现有的 集中式数据挖掘算法不适合于将来大容量、分布式的数据分析应用。此外，由于 数据的私有性和保密性、系统的不兼容性等方面的原因，把所有的数据都综合到 一个集中式平台中也是不现实的。 数据挖掘的最新挑战主要有以下几个方面”1 ： ( l ) 提高数据挖掘算法的可扩展性( s c a l a b i l i t y ) o 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 现在大多数的数据挖掘算法都假设数据能全部载入内存。虽然有一些在大规 模数据集上进行数据挖掘的成功例子，但通常都是在大规模数据集上进行数据采 样，直到被采样的数据能全部载入内存的结果。 ( 2 ) 挖掘非向量( n o n - v e c t o r ) 数据 今天，大多数据挖掘算法都只能挖掘向量数据( v e c t o r - v a l u e dd a t a ) 。扩 展数据挖掘算法，使它们能挖掘新的数据类型是一个重要的挑战。这些数据类型 包括无结构数据、半结构化数据、多媒体数据等 ( 3 ) 挖掘分布式数据 大多数数据挖掘算法都要求所有被挖掘的数据必须存放在一个单一、集中的 数据仓库中。但事实上很多应用中数据都是存放在上分布的数据库中。因此，不 移动数据而直接进行分布式数据挖掘也是一个重要的挑战。另外，随着无线和移 动式计算机越来越流行，也要求开发出能挖掘这些系统数据的算法和系统。 ( 4 ) 提高数据挖掘系统和环境的易使用性 ( 5 ) 数据挖掘过程中的数据的隐私性和安全性 数据挖掘是一种从数据集当中提取有用信息的强有力的方法。随着越来越多 的数值变得有用，滥用数据挖掘的潜在可能性也越来越大。 2 2 3 分布式数据挖掘的关键技术 在分布式数据挖掘中，需要注意下面四个方面关键技术： ( 1 ) 数据一致性 从逻辑上分布或物理上分布的数据源中收集数据是数据挖掘的第一阶段，传 统的方法是先从关系数据库中提取数据表，然后把它存放到一个集中式数据仓库 或数据集市中。因此对分布式数据挖掘系统来说，对所有的数据挖掘过程提供一 个一致的存储结构是非常重要的。此外，在分布式环境中尽可能最小化整个数据 挖掘周期中的数据移动也是非常关键的。另外一个重要的课题是对数据挖掘算法 开发出和s q l 兼容的数据库查询接口，以便能直接访问分布式数据库的信息。 ( 2 ) 并行数据挖掘( p a r a l l e ld a t am i n i n g ) 在服务器端。在大容量数据集上运行数据挖掘要耗费很长时间，因为数据挖 掘算法的时间复杂度都很高。一个比较好的方法是把数据挖掘算法并行化。但传 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 统算法对这些技术的使用都只考虑到对单个数据库的使用，一般来说都是串行算 法。随着并行和分布式技术的发展，越来越多基于并行和分布式的挖掘算法也随 之出现。很多时候并行挖掘算法和分布式数据挖掘算法是可以通用的。 ( 3 ) 知识吸收( k n o w l e d g ea s s i m i l a t i o n ) 在数据分布式和功能分布式的环境中，知识吸收是非常重要的。它的基本思 想是用数据挖掘算法从几个数据集当中( 一般情况下是不相交的) 吸取知识，然 后用这些数据挖掘过程中产生的知识片段合成一个完整的知识。 ( 4 ) 分布式软件引擎( d i s t r i b u t e ds o f t w a r ee n g i n e e r i n g ) 在最近的这些年中，i n t e r n e t 已经成为c l i e n t s e r v e r 计算机模式的世界范 围内的超结构。在这个新的环境中，应用开发主要是开发软件部件，然后再把它 们组合起来。软件部件具有封装性，它和外界的兼容是通过预先定义好的应用程 序接口( a p i ) 来完成的。软件部件最大的优点是支持软件复用，这样系统设计 人员就可以使用现存的软件部件。现在最流行的分布式部件模型是c o r b a 、 a c t i v e x d c o m 和j a v ab e a n s 。 2 3 移动代理( m o b iea g e n t ) 技术 2 3 1 代理( a g e n t ) 的基本概念 二十世纪8 0 年代中后期，从事分布人工智能( d a d 和计算机科学的研究人员 开始对代理进行研究。9 0 年代以来，随着计算机网络、计算机通信技术的发展， 对于代理的研究已经成为分布式人工智能领域的一个热点。使其成为一个迅速发 展的领域。研究人员预言：基于代理的计算将可能成为下一个对软件开发的重大 突破。 代理( a g e n o 是具有目标、知识和一定的思维能力，能作用和受作用于外部环 境，可以维持某种状态( 即保存与自身行为有关的各种数据信息) ，并能够与其 它代理相互协作的物理或逻辑实体。 代理具备下列特性： 自主性( a u t o n o m y ) ：代理可以自主独立的运作，并能控制自己的行为和 内部状态： 2 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 交互性( i n t e r a c t i o n ) ：代理可以与人或其它代理或运行环境进行交互； 反应性( r e a c t i v i t y ) ：代理能感知外部环境的变化并可通过行为改变环 境； 适应性( a d a p t a b i l i t y ) ：代理能根据环境的变化采取与环境相适应的行 为。 2 3 2 移动代理( m o b ii ea g e n t ) 基本概念 当a g e n t 的目标在本地难以满足时，可以让代理移动到其它节点执行来完成功 能，这就是移动代理技术的出发点。 移动代理是一种软件实体，它可自主地在异构的网络上，按照一定的策略移 动，寻找合适的计算资源、信息资源或软件资源，利用与这些资源处于同一主机 或网络的优势，就近处理或使用这些资源，代表用户完成特定的任务m 3 。 移动代理是分布式技术与a g e n t 技术相结合的产物。它除了具有智能a g e n t 的 最基本特性如反应性、自主性、交互性外，移动性( m o b i l i t y ) 是其一个重要特 性。 2 3 3 移动代理系统 移动代理在广义代理的基础上增加了移动性这一特征，能够在网络中自主迁 移。为了实现这一特征，需要为移动代理的执行创建相应的运行环境。 移动代理系统：指能够支持代理创建、执行、迁移、通信等的移动代理运行 环境。 一般来讲，移动代理系统由移动代理( 1 i a ) 和移动代理运行环境( m a e ) 两部 分组成，m a e 也被称为移动代理服务器或移动代理平台，m a 则是只能存活在m a e 中的软件实体，可以从一个m a e 迁移到另一个m a e ，与本地的服务资源进行交互 完成任务。 移动代理技术涉及到计算机网络、分布式系统、通信技术、编程语言以及人 工智能等诸多领域，为了更好地利用好移动代理技术，一个移动代理系统应该考 虑如下方面的问题： ( 1 ) 运行模型： 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 定义移动代理的内部结构，即移动代理作为代理必须具有的一些特性，如代 理的自主、适应、交互、反应和移动等性质。 ( 2 ) 迁移模型( m i g r a t i o nm o d e l ) ： 迁移模型研究如何实现代理迁移的问题，即如何使代理从一个网络节点迁移 到另一个网络节点。 ( 3 ) 通信模型( c o m m u n i c a t i o nm o d e l ) 在基于移动代理技术的分布式应用中，存在着用户、静态代理、移动代理、 移动代理系统甚至是其它非移动代理系统等实体，移动代理为了实现特定的功 能，应该具备与这些实体通信的能力，这是通信代理所要解决的。 ( 4 ) 命名和定位模型( n a m i n ga n dl o c a t i n gm o d e l ) 移动代理系统中有很多的移动代理，它们产生于不同的主机，有着不同的目 的，而且移动代理本身是动态迁移的，位置的概念十分重要。因此要考虑代理的 命名和定位模型，以保证代理名字的唯一性和方便查找代理当前位置的有效性。 ( 5 ) 路由模型( r o u t i n gm o d e l ) 路由模型解决移动代理如何选择迁移路径的问题。为了充分体现移动代理的 自主性和适应性，路由模型能够根据网络运行状况和主机运行状态、资源分布善 等动态规划代理的路由。 ( 6 ) 安全模型( s e c u r i t ym o d e l ) 移动代理系统本身是一个开放的系统，可能会接收到不信任的移动代理，移 动代理也可能到不被信任的m a e 中去执行。安全模型描述如何保证代理的完整性， 防止代理的数据被泄露，代理和服务器的相互信任，代理的授权和服务器资源存 取控制策略等。 2 3 4 典型移动代理系统 目前移动代理已从过去的理论探索进入到实用阶段，因而出现了一些移动代 理系统的开发平台或执行环境，大致可以分为三类：一类基于传统解释性语言： 一类基于j a v a 语言；一类基于c o r b a 平台。 g e n e r a lm a g i c 公司的t e l e s c r i p t l 3 2 1 曾经在过去的几年里被广泛采用。t e l e s c r i p t 平台用t e l e s c r i p t 语言来完成的。t e l e s c r i p ta g e n t 之间的通信有两种方式：两个 1 4 浙江工业大学硕士研究生学位论文基于移动代理的分布式数据挖掘研究 a g e n t 运行在同一个空间时可相互调用对方的方法；而在不同的空间时，需建立 连接，互相传递对象。t e l e s c r i p t 是一个比较成功的移动代理平台，其安全性较 好，执行效率较高。但由于j a v a 的迅速流行，必然导致它的失败。 a g l e t s t 3 3 1 是由i b m 东京实验室用纯j a v a 开发的移动a g e n t 技术，并开发了实 用的平台a g l e tw o r k b e n c h ，供人们开发或执行移动a g e n t 系统。到目前为止， a g l e t 是最为成功和全面的系统。这主要表现在：它提供了一个简单而全面的移 动a g e n t 编程模型：它为a g e n t 间提供了动态和有效的通信机制：它还提供了一 套详细且易用的安全机制。a g l e t 同时传送代码及其状态，a g l e t 以线程的形式产 生于一台计算机上，可随时暂停正在执行的工作，并允许把整个a g l e t 分派到另 一台计算机上，再重新启动执行任务。由于a g l e t 是线程，因此不会消耗太多的 系统资源。a g l e t 中另外一个特色是引入了设计样式( d e s i g np a t t e r n ) 的概念，并提 供了相应的开发包，具有很好的软件重用性。 w + + 的g r a s s h o p p e r 是一种基于c o r b a 的移动代理平台。通过专有的 g r a s s h o p p e ro r b 互联，由于该系统符合m a s i f 规范，也同样可以通过其他 c o r b a 互联。g r a s s h o p p e r 的通信基础设计得非常巧妙，可以通过c o r b a 进行 通信，还可以通过j a v ar m i 和s o c k e t ( 套接字) 连接进行通信，整个通信结构采用 插件技术，具有很好的扩展性。安全服务中采用x 5 0 9 证书实现身份认证，采用 s s l 来保证传输中的安全性，通过用户定的安全管理器来完成资源访问控制，并 实现了数字签名。 2 4 分布式计算模型比较 通信网络的出现使得计算能力的远程使用成为可能。在这一节，我们将简要 讨论已有的各种分布式计算技术，并分析各自的优缺点。 分布式计算( d i s t r i b u t e dc o m p u t i n g ) 是近2 0 年来影响计算技术发展的最活跃 因素之一，它在网络计算平台上部署分布式计算环境，提供开发工具和公共服 务，支持分布式应用，实现资源共享和协同工作。2 0 世纪9 0 年代以来，工业界 普遍遵循这一技术路线，产生了一系列行之有效的技术和广为用户接受的产品。 从8 0 年代中期开始至今，分布式计算已经走过了第一代，目前正处于第二代 的成熟期，并且开始孕育第三代。当前人们所说的分布式计算技术是指在网络计 浙江工业大学硕士研究生学位论文 基于移动代理的分布式数据挖掘研究 算平台上开发、部署、管理和维护以资源共享和协同工作为主要应用目标的分布 式应用系统。 2 4 1c il e n t s e r v e r 模型 2 0 世纪8 0 年代中后期，以支持信息共享的应用需求为核心，形成了面向过 程的第一代分布式计算技术一客户机服务器( c l i e n t s e r v e r ) 模型